# FONDUE: A Framework for Node Disambiguation and Deduplication Using Network Embeddings +
## 4 Experiments
### Node Disambiguation
#### 4.2.2 Quantitative Evaluation of Node Identification  
In this section, we focus on answering \(\mathbf{Q}_{1}\), namely, given a contracted graph, FONDUE-NDA aims to identify the list of contracted (ambiguous) nodes present in it. We first discuss the datasets used in the experiments in the following section. Baselines.As mentioned earlier in Section 1, most entity disambiguation methods in the literature focus on the task of re-assigning the edges of an already predefined set of ambiguous nodes, and the process of identifying these nodes in a given non-attributed network, is usually overlooked. Thus, there exists very few approaches that tackle the latter case. In this section, we compare FONDUE-NDA with three different competing approaches that focus on the identification task, one existing method, and two heuristics. _Normalized-Cut_ (_NC_) The work of [16] comes close to ours, as their method also aims to identify ambiguous nodes in a given graph by utilizing Markov clustering to cluster an ego network of a vertex \(u\) with the vertex itself removed. NC favors the grouping that gives small cross-edges between different clusters of \(u\)'s neighbors. The result is a score reflecting the quality of the clustering, using normalized-cut (**NC**):  
\[NC=\sum_{i=1}^{k}\frac{W(C_{i},\overline{C_{i}})}{W(C_{i},C_{i})+W(C_{i}, \overline{C_{i}})},\]  
with \(W(C_{i},C_{i})\) as the sum of all the edges within cluster \(C_{i}\), \(W(C_{i},\overline{C_{i}})\) the sum of the for all the edges between cluster \(C_{i}\) and the rest of the network \(\overline{C_{i}}\), and \(k\) being the number of clusters in the graph. Although [17] also worked on identifying nodes based on topological features, their method (which is not publicly available) performed worse in all the cases when compared to [16], so we only chose the latter as a competing baseline. _Connected-Component Score_ (_CC_) We also include another baseline, connected-component score (**CC**), relying on the same approach used in [16], with a slight modification. Instead of computing the normalized cut score based on the clusters of the ego graph of a node, we account for the number of connected components of a node's ego graph, with the node itself removed. _Degree_ Finally, we use node degree as a baseline. As contracted nodes usually tend to have a higher degree, by inheriting more edges from combined nodes, degree is a simple predictor for the node ambiguity. Evaluation Metric.FONDUE-NDA ranks nodes according to their calculated ambiguity score (how likely is that node to be ambiguous). The same process goes for NC and CC. At first glance, the evaluation can be approached from a binary classification perspective, by considering the top X ranked nodes as ambiguous (where X is the actual number true-positive), and, thus, we can use the usual metrics for binary classification, such as F1-score, precision, recall and AUC. However, this requires knowing beforehand the number of true-positive, i.e., the number of actual ambiguous nodes (or setting a clear cutoff value), which is only possible in labeled datasets and controlled experiments. In real world settings, if FONDUE-NDA is to be used to detect ambiguous nodes in unlabeled networks, practical application is rather more restricted, as it is more useful to have relevant nodes (ambiguous) ranked more highly than non-relevant nodes. Thus, it is necessary to extend the traditional binary classification evaluation methods, that are based on binary relevance judgments, to more flexible graded relevance judgments, such as, for example, cumulative gain, which is a form of graded precision, as it is identical to the precision when rating scale is binary. However, as our datasets are highly imbalanced by nature, mainly because ambiguous nodes are by definition a small part of the network, a better take on the cumulative gain metric is needed. Hence, we employ the normalized discounted gain to evaluate our method, alongside the traditional binary classification methods listed above. Below, we detail each metric.