# Similar Supergraph Search Based on Graph Edit Distance
## 4 Straightforward Method for Constrained Problem
In addition, letters in the matrices are edge labels and zeros in the matrices and they indicate that there are no edges._  
\[\begin{array}{c}A\!\!\!A\!\!A\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\  
**Lemma 1**.: _If two AcGM codes are the same, the graphs represented by the codes are isomorphic._  
Proof.: If two adjacency matrices are the same, the graphs represented by the matrices are isomorphic. Since each AcGM code of a graph \(g\) corresponds one-to-one with an adjacency matrix of \(g\), if two AcGM codes are the same, the graphs represented by the codes are isomorphic.  
In contrast, if two graphs are isomorphic, their AcGM codes are not necessarily the same. This means that there are multiple AcGM codes of \(g\) that fulfill Definition 1. Thus, we denote the set of all AcGM codes of graph \(g\) as \(\Omega(g)\).  
**Lemma 2**.: _When an AcGM code \(c\) is a prefix of another code \(c^{\prime}\), \(g(c)\) is connected and is an induced subgraph of \(g(c^{\prime})\)._  
Proof.: Given an AcGM code \(c\) of a graph \(g\), let its corresponding adjacency matrix be \(A\). All submatrices \(A^{\prime}\) of \(A\) obtained by iteratively deleting the last row and column of \(A\) represent induced and connected subgraphs of \(g\). According to Definition 5, AcGM codes for the matrices \(A^{\prime}\) must be prefices of the AcGM code for \(A\).  
From the above discussion, one straightforward method for outputting the subgraphs defined by Equation (4) is to compute the graph edit distance between a graph \(g_{i}\in G\) and a graph \(g(c^{\prime})\), represented by a prefix \(c^{\prime}\subseteq c\) for \(c\in\Omega(q)\). However, computing the edit distance between \(g_{i}\) and \(g(c^{\prime})\) by Equation (2) is not feasible. Therefore, we discuss a method for computing the edit distance by using the codes of \(g_{i}\) and \(g(c^{\prime})\).  
**Lemma 3**.: _Given the following AcGM codes:_  
\[c = \ell(u_{1})\ell(u_{2})x_{1,2}\cdots\ell(u_{a})x_{1,a}\cdots x_{a- 1,a} \tag{6}\] \[c^{\prime} = \ell(u^{\prime}_{1})\ell(u^{\prime}_{2})x^{\prime}_{1,2}\cdots \ell(u^{\prime}_{b})x^{\prime}_{1,b}\cdots x^{\prime}_{b-1,b}, \tag{7}\]  
_where \(a\) and \(b\) are the numbers of vertices in \(g(c)\) and \(g(c^{\prime})\), respectively, and the \(i\)-th vertex in \(g(c)\) maps to the \(i\)-th vertex in \(g(c^{\prime})\), the number of edits \(ed(c,c^{\prime})\) to transform \(g(c)\) to \(g(c^{\prime})\) is the following:_  
\[ed(c,c^{\prime}) = \sum_{1\leq i\leq\min\{a,b\}}\delta^{\prime}(\ell(u_{i}),\ell(u^{ \prime}_{i}))+\sum_{1<j\leq\min\{a,b\}}\sum_{1\leq i<j}\delta^{\prime}(x_{i,j},x^{\prime}_{i,j})\] \[+|a-b|+ \begin{cases}\sum_{b<j\leq a}\sum_{1\leq i<j}\delta^{ \prime}(x_{i,j},0)&(b<a)\\ 0&(a=b)\\ \sum_{a<j\leq b}\sum_{1\leq i<j}\delta^{\prime}(0,x^{\prime}_{i,j})&(a<b),\end{cases}  \tag{8}\]  
_where \(\delta\) is the Kronecker delta and \(\delta^{\prime}(\alpha,\beta)=1-\delta(\alpha,\beta)\). The complexity of solving Equation (8) is \(O((\max\{a,b\})^{2})\). The \(ed(c,c^{\prime})\) function is symmetric: \(ed(c,c^{\prime})=ed(c^{\prime},c)\)._  
Proof. : The first term of Equation (8) is the sum of the numbers of edits that occur because of differences between the \(i\)-th (\(1\leq i\leq\min\{a,b\}\)) vertices in \(g(c)\) and \(g(c^{\prime})\) and its second term is the sum of the numbers of edits that occur because of differences between edges  
Figure 3: Example of a graph. \((i,j)\) (\(1\leq i<j\leq\min\{a,b\}\)) in \(g(c)\) and \(g(c^{\prime})\). Its third term is the sum of the numbers of edits to insert vertices in \(g(c)\) or \(g(c^{\prime})\) and its fourth term is the sum of the numbers of edits to insert edges in \(g(c)\) or \(g(c^{\prime})\). Since Equation (8) defines the number of edits between two graphs under the known mapping such that \(\varphi(i)=i\) for all \(i\) (\(1\leq i\leq\max\{a,b\}\)), it corresponds to Equation (1). Therefore, Equation (2) is formalized by using Equation (8) as the following lemmas.