# FONDUE: A Framework for Node Disambiguation and Deduplication Using Network Embeddings +
## 3 Methods
### Problem Definition
#### 3.1.1 Formalizing the Node Disambiguation Problem  
To formally define the NDA problem as an inverse problem, we first need to define the forward problem which maps an unambiguous graph onto an ambiguous one. This formalizes the 'corruption' process that creates ambiguity in the graph. In practice, this happens most often because identifiers of the entities represented by the nodes are not unique. For example, in a co-authorship network, the identifiers could be non-unique author names. To this end, we define a node contraction:  
**Definition 1** (Node Contraction).: _A node contraction \(c\) for a graph \(\mathcal{G}=(V,E)\) with \(V=\{1,2,\ldots,n\}\) is a surjective function \(c:V\rightarrow\hat{V}\) for some set \(\hat{V}=\{1,2,\ldots,\hat{n}\}\) with \(\hat{n}\leq n\). For convenience, we will define \(c^{-1}:\hat{V}\to 2^{V}\) as \(c^{-1}(i)=\{k\in V|c(k)=i\}\) for any \(i\in\hat{V}\). Moreover, we will refer to the cardinality \(|c^{-1}(i)|\) as the multiplicity of the node \(i\in\hat{V}\)._  
A node contraction defines an equivalence relation \(\sim_{c}\) over the set of nodes: \(i\sim_{c}j\) if \(c(i)=c(j)\), and the set \(\hat{V}\) is the quotient set \(V/\sim_{c}\). Continuing our example of a co-authorship network, a node contraction maps an author onto the node representing their name. Two authors \(i\) and \(j\) would be equivalent if their names \(c(i)\) and \(c(j)\) are equal, and the multiplicity of a node is the number of distinct authors with the corresponding name.  
We can naturally define the concept of an ambiguous graph in terms of the contraction operation, as follows.  
**Definition 2** (Ambiguous graph).: _Given a graph \(\mathcal{G}=(V,E)\) and a node contraction \(c\) for that graph, the graph \(\hat{\mathcal{G}}=(\hat{V},\hat{E})\) defined as \(\hat{E}=\{\{c(k),c(l)\}|\{k,l\}\in E\}\) is referred to as an ambiguous graph of \(\mathcal{G}\). Overloading notation, we may write \(\hat{\mathcal{G}}\triangleq c(\mathcal{G})\). To contrast \(\mathcal{G}\) with \(\hat{\mathcal{G}}\), we may refer to \(\mathcal{G}\) as the unambiguous graph._  
Continuing the example of the co-authorship network, the contraction operation can be thought of as the operation that replaces author identities with their names, which may map distinct authors onto a same shared name. Note that the symbols for the ambiguous graph and its set of nodes and edges are denoted here using hats, to indicate that in the NDA problem we are interested in situations where the ambiguous graph is the empirically observed graph.  
We can now formally define the NDA problem as inverting this contraction operation:  
**Definition 3** (The Node Disambiguation Problem).: _Given an ambiguous graph \(\hat{\mathcal{G}}=(\hat{V},\hat{E})\), NDA aims to retrieve the unambiguous graph \(\mathcal{G}=(V,E)\) and associated node contraction \(c\), i.e., a contraction \(c\) for which \(c(\mathcal{G})=\hat{\mathcal{G}}\)._  
To be more precise, it suffices to identify \(\mathcal{G}\) up to an isomorphism, as the actual identifiers of the nodes are irrelevant.