# Similar Supergraph Search Based on Graph Edit Distance
## 2 Problem Definition  
A labeled graph is expressed as \(g=(V,E,\Sigma,\ell)\), where \(V\) is a set of vertices, \(E\subseteq V\times V\) is a set of edges, \(\Sigma\) is a set of labels for the vertices and edges, and \(\ell:V\cup E\rightarrow\Sigma\) is a function to assign the labels to the vertices and edges. We denote the set of all vertices in graph \(g\) as \(V(g)\). A graph \(g\) is called a directed graph if the edges in \(g\) have directions;  
Figure 1: Similar Chemical Compounds.  
otherwise, \(g\) is called an undirected graph. A sequence of edges from \(v_{1}\) to \(v_{2}\) is called a path and a graph (for a directed graph, all edges in the graph are replaced with undirected edges.) and a path that exists between any two vertices is called connected.  
Given graphs \(g=(V,E,\Sigma,\ell)\) and \(g^{\prime}=(V^{\prime},E^{\prime},\Sigma^{\prime},\ell^{\prime})\), \(\forall v,v_{1},v_{2}\in V^{\prime}\), when an injective function \(\phi:V^{\prime}\to V\) fulfills the following conditions, \(g^{\prime}\) is called a subgraph of \(g\), which is denoted as \(g^{\prime}\subseteq g\):  
* \((\phi(v_{1}),\phi(v_{2}))\in E\) if \((v_{1},v_{2})\in E^{\prime}\);
* \(\ell^{\prime}(v)=\ell(\phi(v))\);
* \(\ell^{\prime}((v_{1},v_{2}))=\ell((\phi(v_{1}),\phi(v_{2})))\).  
In addition, when \((\phi(v_{1}),\phi(v_{2}))\in E\) iff \((v_{1},v_{2})\in E^{\prime}\), we call \(g^{\prime}\) an induced subgraph of \(g\), which is denoted as \(g^{\prime}\subseteq_{i}g\). Although this paper focuses only on undirected and connected graphs, the methods proposed can easily be extended to directed or unconnected graphs.  
The graph edit distance is the minimum number of edits required to transform a graph \(g\) to another graph \(g^{\prime}\), where an edit is either an insertion, deletion, or relabeling of a vertex or edge. In this paper, we assume that the cost of each edit is \(1\). The number of edits between graphs \(g=(V,E,\Sigma,\ell)\) and \(g^{\prime}=(V^{\prime},E^{\prime},\Sigma,\ell^{\prime})\) is defined as follows:  
\[dist(g,g^{\prime},\varphi)=\sum_{i=1}^{|V^{\prime}|}c_{i\varphi(i)}+\sum_{i=1}^ {|V^{\prime}|-1}\sum_{j=i+1}^{|V^{\prime}|}c\Big{(}(v_{i},v_{j})\to\Big{(}v_{ \varphi(i)},v_{\varphi(j)}\Big{)}\Big{)}, \tag{1}\]  
where we assume that \(|V|\leq|V^{\prime}|\) and \(V\) is extended to \(V^{+}=V\cup\{\varepsilon_{1},\varepsilon_{2},\ldots,\varepsilon_{|V^{\prime}| -|V|}\}\)[23]. In addition, when \(g\) is transformed to \(g^{\prime}\), the mapping between \(V\) and \(V^{\prime}\) is expressed as a bijective mapping \(\varphi:V^{+}\to V^{\prime}\). \(c_{ij}\) is the cost to edit the vertex \(v_{i}\in V^{+}\) to \(v_{j}\in V^{\prime}\) and \(c((v_{i},v_{j})\to(v_{i^{\prime}},v_{j^{\prime}}))\) is the cost to edit edge \((v_{i},v_{j})\in E\) to \((v_{i^{\prime}},v_{j^{\prime}})\in E^{\prime}\). Editing \(\varepsilon_{i}\in V^{+}\) to \(v_{j}\in V^{\prime}\) means performing a vertex insertion in \(g^{\prime}\). Therefore, the graph edit distance \(ed(g,g^{\prime})\) between the graphs \(g\) and \(g^{\prime}\) is defined as follows:  
\[ed(g,g^{\prime})=\min_{\varphi\in\Phi(|V^{\prime}|,|V^{\prime}|)}dist(g,g^{ \prime},\varphi), \tag{2}\]  
where \(\Phi(\alpha,\beta)\) is a set of all possible \(\beta\)-permutations of the integers \(1,2,\ldots,\alpha\). The solution to Equation (2) is one of the quadratic assignment problems, which are known to be NP-complete.  
Given a set of graphs \(G=\{g_{1},g_{2},\ldots,g_{n}\}\), a query graph \(q\), and a threshold \(\theta\) as input, the problem tackled in this paper is to output a set of graphs.  
\[S=\{g_{i}\in G\mid\exists q^{\prime}\subseteq q\,s.t.\,ed(g_{i},q^{\prime}) \leq\theta\}. \tag{3}\]  
In Equation (3), note that \(q^{\prime}\) is a subgraph of \(q\) but not an induced subgraph of \(q\). When \(\theta\) is \(0\) in Equation (3), the problem is equivalent to the original supergraph search problem. Therefore, our problem, represented by Equation (3), is an extension of the supergraph search problem.