# FONDUE: A Framework for Node Disambiguation and Deduplication Using Network Embeddings +
## 3 Methods
### Fondue-Nnd  
Using the inductive bias for the NDD problem, the goal is to minimize the embedding cost after merging the duplicate nodes in the graph (Equation (2)). This is motivated by the fact that natural networks tend to be modeled using NE methods, better than corrupted (duplicate) networks, thus their embedding cost should be lower. Thus, merging (or contracting) duplicate nodes (nodes that refer to the same entity) in a duplicate graph \(\hat{\mathcal{G}}\) would result in a contracted graph \(\hat{\mathcal{G}}_{c}\) that is less corrupt (resembling more a \"natural\" graph), thus with a lower embedding cost.  
Contrary to NDA, NDD is more straightforward, as it does not deal with the problem of reassigning the edges of the node after splitting, but rather simply determining the duplicate nodes in a duplicate graph. FONDUE-NDD applied on \(\hat{\mathcal{G}}\), aims to find duplicate node-pairs in the graph to combine them into one node by reassigning the union of their edges, which would result in contracted graph \(\hat{\mathcal{G}}_{c}\).  
Using NE methods, FONDUE-NDD aims to iteratively identify a node-pair \(\{i,j\}\in\hat{\mathcal{V}}_{cand}\), where \(\hat{\mathcal{V}}_{cand}\) is the set of all possible candidate node-pairs, that if merged together to form one node \(i_{m}\), would result in the smallest cost function value among all the other node-pairs. Thus, problem 6 can be further rewritten as:  
\[\underset{\{i,j\}\in\hat{\mathcal{V}}_{cand}}{\operatorname{argmin}}\quad \mathcal{O}\Big{(}\hat{\mathcal{G}}_{c_{ij}}\hat{\mathbf{X}}_{c_{ij}}\Big{)}, \tag{8}\]  
where \(\hat{\mathcal{G}}_{c_{ij}}\) is a contracted graph from \(\hat{\mathcal{G}}\) after merging the node-pair \(\{i,j\}\), and \(\hat{\mathbf{X}}_{c_{ij}}\) its respective embeddings.  
Trying this for all possible node-pairs in the graph is an intractable solution. It is not obvious what information could be used to approximate Equation (8), thus we approach the problem simply by randomly selecting node-pairs, merging them, observing the values of the cost function, and then ranking the result. The lower the cost score, the more likely that those merged nodes are duplicates.  
Lacking a scalable bottom-up procedure to identify the best node pairs, in the experiments our focus will be on evaluation whether the introduced criterion for merging is indeed useful to identify _whether_ node pairs appear to be duplicates.  
FONDUE-NDD Using CNE  
Similarly to the previous section, we proceed by applying CNE as a network embedding method, the objective function of FONDUE-NDD is thus the one of CNE evaluated on the tentatively deduplicated graph after attempting a merge:  
\[\mathcal{O}(\hat{\mathcal{G}}_{c_{ij}},\hat{\mathcal{K}}_{c_{ij }})=\ \log(P(\hat{\mathcal{A}}_{c_{ij}}|\hat{\mathcal{K}}_{c_{ij}}))= \sum_{k,l:\mathcal{A}_{c_{ij},kl}=1}\log\big{(}1+\frac{\sigma_{1}}{\sigma_{2}} \frac{1-P_{kl}}{P_{kl}}\exp\big{(}(\frac{1}{\sigma_{1}^{2}}-\frac{1}{\sigma_{2}^ {2}})\frac{d_{kl}^{2}}{2}\big{)}\big{)} \tag{9}\] \[+\sum_{k,l:\mathcal{A}_{c_{ij},kl}=0}\log\big{(}1+\frac{\sigma_{2}} {\sigma_{1}}\frac{P_{kl}}{1-P_{kl}}\exp\big{(}(\frac{1}{\sigma_{2}^{2}}-\frac{1 }{\sigma_{1}^{2}})\frac{d_{kl}^{2}}{2}\big{)}\big{)},\]  
with the link probabilities \(P_{kl}\) conditioned on the embedding are defined as follows:  
\[P_{kl}(\hat{\mathcal{A}}_{c_{ij}kl}=1|\mathbf{X})=\frac{P_{\hat{A}_{c_{ij},kl}, kl}\mathcal{N}_{+,\sigma_{1}}(\|\mathbf{x}_{k}-\mathbf{x}_{l}\|)}{P_{\hat{A}_{c_{ ij},kl},kl}\mathcal{N}_{+,\sigma_{1}}(\|\mathbf{x}_{k}-\mathbf{x}_{l}\|)+(1-P _{\hat{A}_{c_{ij},kl},kl})\mathcal{N}_{+,\sigma_{2}}(\|\mathbf{x}_{k}-\mathbf{ x}_{l}\|)}.\]Similarly to Section 3.3.3, \(\mathcal{N}_{+,\sigma}\) denotes a half-Normal distribution with spread parameter \(\sigma\), \(\sigma_{2}>\sigma_{1}=1\), and where \(P_{\mathbf{A}_{\tau;\mu},\mu}\) is a prior probability for a link to exist between nodes \(k\) and \(l\) as inferred from the network properties.