# FONDUE: A Framework for Node Disambiguation and Deduplication Using Network Embeddings +
## 3 Methods
### Fondue-Nda
#### 3.3.1. A First-Order Approximation for Computational Tractability  
Thus, instead of recomputing the embedding, FONDUE-NDA performs a first-order analysis by investigating the effect of an infinitesimal split of a node \(i\) around its embedding \(\mathbf{x}_{i}\), on the cost \(O(\hat{\mathcal{G}}_{si},\hat{\mathbf{X}}_{si})\) obtained after performing the splitting, with \(\hat{\mathcal{G}}_{si}\) and \(\hat{\mathbf{X}}_{si}\) referring to the ambiguous graph and its embeddings' representation, respectively, after splitting node \(i\). Drawing intuition from Figure 1, when two distinct authors share the same name in a given collaboration network, their respective separate community (ego-network) are lumped into one big cluster. Yet, from a topological point of view, that ambiguous node (author name) is connected to both communities that are generally different, meaning they share very few, if any, links. This stems from the observation that it is highly unlikely that two authors with the same exact name would belong to the same community, i.e., collaborate together. Furthermore, splitting this ambiguous node into two different ones (distinguishing the two authors), would ideally separate these two communities. Thus, to do so, we consider that each community, that is supposed to be embedded separately, is pulling the ambiguous node towards its own embedding region, and once separated, the embeddings of each of the resolved nodes will be improved. So our main goal is to quantify the amount of improvements in the embedding cost function by separating the two nodes \(i^{\prime}\) and \(i^{\prime\prime}\) by a unit distance in a certain direction. We propose to split the assignment of the edges of \(i\) between \(i^{\prime}\) and \(i^{\prime\prime}\), such that all the links from \(i\) are distributed to either \(i^{\prime}\) or \(i^{\prime\prime}\) in such way to maximize the embedding cost function, which could be evaluated by computing the gradient with respect to the separation distance \(\delta_{i}\). Specifically, FONDUE-NDA seeks the split of node \(i\) that will result in embedding \(\mathbf{x}_{i^{\prime}}\) and \(\mathbf{x}_{i^{\prime\prime}}\) with infinitesimal difference \(\mathbf{\delta}_{i}\) (where \(\mathbf{\delta}_{i}=\mathbf{x}_{i^{\prime}}-\mathbf{x}_{i^{\prime\prime}}\), \(\mathbf{x}_{i^{\prime}}=\mathbf{x}_{i}+\frac{\mathbf{\delta}_{i}}{2}\), \(\mathbf{x}_{i^{\prime\prime}}=\mathbf{x}_{i}-\frac{\mathbf{\delta}_{i}}{2}\), and \(\mathbf{\delta}_{i}\to\mathbf{0}\), e.g., Figure 1b), such that \(||\
abla_{\mathbf{\delta}_{i}}O(\hat{\mathcal{G}}_{si},\hat{\mathbf{X}}_{si})||\) is large, with \(\
abla_{\mathbf{\delta}_{i}}O(\hat{\mathcal{G}}_{si},\hat{\mathbf{X}}_{si})\) being the gradient of \(O(\hat{\mathcal{G}}_{si},\hat{\mathbf{X}}_{si})\) with respect to \(\mathbf{\delta}_{i}\). This can be completed analytically. Indeed, applying the chain rule, we find:  
\[\
abla_{\mathbf{\delta}_{i}}O(\hat{\mathcal{G}}_{si},\hat{\mathbf{X}}_{si})=\frac{1}{ 2}\
abla_{\mathbf{x}_{i^{\prime}}}O(\hat{\mathcal{G}}_{si},\hat{\mathbf{X}}_{si}) -\frac{1}{2}\
abla_{\mathbf{x}_{i^{\prime\prime}}}O(\hat{\mathcal{G}}_{si}, \hat{\mathbf{X}}_{si}). \tag{3}\]  
Many recent NE methods like LINE [24] and CNE [6], aim to embed'similar' nodes in the graph closer to each other, and 'dissimilar' nodes further away from each other (for a particular similarity notion depending on the NE method). For such methods, Equation (3) can be further simplified. Indeed, as such NE methods focus on modeling a property of pairs of nodes (their similarity), their objective functions can be typically decomposed as a summation of node-pair interaction losses over all node-pairs. For example, this can be seen in Section 3.3.3 of the current paper for CNE [6], and in Equations (3) and (6) of [24] for LINE. Each of these node-pair interaction losses quantifies the extent to which the proximity between nodes' embeddings reflects their'similarity' in the network.