# FONDUE: A Framework for Node Disambiguation and Deduplication Using Network Embeddings +
## 3 Methods
### FONDUE as a Generic Approach  
To address both the NDA and NDD problems, FONDUE uses an inductive bias that the non-corrupted (unambiguous and deduplicated) network must be easy to model using NE. This allows us to approach both problems in the context of NE. Here we first formalize the inductive bias of FONDUE (Section 3.2). This will later allow us to present both the FONDUE-NDA (Section 3.3) and FONDUE-NDD (Section 3.4) algorithms, each tackling one of the data corruption tasks (NDA and NDD, respectively). The FONDUE Induction Bias  
Clearly, both the NDA and NDD problems are inverse problems, with NDA an ill-posed one. Thus, further assumptions, inductive bias, or priors are inevitable in order to solve them. The key hypothesis in FONDUE is that the unambiguous and deduplicated \(\mathcal{G}\), considering it is a 'natural' graph, can be embedded well using state-of-the-art NE methods. This hypothesis is inspired by the empirical observation that NE methods embed 'natural' graphs well. NE methods find a mapping \(f:V\to\mathbb{R}^{d}\) from nodes to \(d\)-dimensional real vectors. An embedding is denoted as \(\mathbf{X}=(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n})^{\top}\in\mathbb{ R}^{n\times d}\), where \(\mathbf{x}_{i}\triangleq f(i)\) for \(i\in V\) is the embedding of each node. Most well-known NE methods aim to find an optimal embedding \(\mathbf{X}_{\mathcal{G}}^{*}\) for given graph \(\mathcal{G}\) that minimizes a continuous differentiable cost function \(\mathcal{O}(\mathcal{G},\mathbf{X})\). Thus, given an ambiguous graph \(\hat{\mathcal{G}}\), FONDUE-NDA will search for the graph \(\mathcal{G}\), such that \(c(\mathcal{G})=\hat{\mathcal{G}}\) for an appropriate contraction \(c\), while optimizing the NE cost function on \(\mathcal{G}\):  
**Definition 6** (NE-based NDA problem). : _Given an ambiguous graph \(\hat{\mathcal{G}}\), NE-based NDA aims to retrieve the unambiguous graph \(\mathcal{G}\) and the associated contraction \(c\):_  
\[ \begin{split}\underset{\mathcal{G}}{\text{argmin}}& \mathcal{O}\big{(}\mathcal{G},\mathbf{X}_{\mathcal{G}}^{*}\big{)}\\ \text{s.t.}& c(\mathcal{G})=\hat{\mathcal{G}}\ \ \text{for some contraction $c$.}\end{split}  \tag{1}\]  
Ideally, this optimization problem can be solved by simultaneously finding optimal splits for all nodes (i.e., an inverse of the contraction \(c\)) that yield the smallest embedding cost after re-embedding. However, this strategy requires to (a) search splits in an exponential search space that has the combinations of splits (with arbitrary cardinality) of all nodes, (b) to evaluate each combination of the splits, the embedding of the resulting network needs to be recomputed. Thus, this ideal solution is computationally intractable and more scalable solutions are needed (see Section 3.3). Similarly, for NDD, given a duplicate graph \(\hat{\mathcal{G}}\), FONDUE-NDD will search for a graph \(\mathcal{G}\), such that \(c(\hat{\mathcal{G}})=\mathcal{G}\) for an appropriate contraction \(c\), again while optimizing the NE cost function on \(\mathcal{G}\):  
**Definition 7** (NE-based NDD problem). : _Given a duplicate graph \(\hat{\mathcal{G}}\), NE-based NDD aims to retrieve the deduplicated graph \(\mathcal{G}\) and the associated contraction \(c\) of \(\hat{\mathcal{G}}\):_  
\[ \begin{split}\underset{\mathcal{G}}{\text{argmin}}& \mathcal{O}\big{(}\mathcal{G},\mathbf{X}_{\mathcal{G}}^{*}\big{)}\\ \text{s.t.}& c(\hat{\mathcal{G}})=\mathcal{G}\ \ \text{for some contraction $c$.}\end{split}  \tag{2}\]  
Generally speaking, to solve this optimization problem, we would want to find the optimal merging for all the nodes that would reduce the cost of the embedding after computing the re-embedding. Yet, a thorough optimization of this problem is beyond the scope of this paper, and as an approximation we rely on a ranking-based approach where we rank networks with randomly merged nodes depending on the value of the objective function after re-embedding.