# Similar Supergraph Search Based on Graph Edit Distance
## 3 Related Work  
In Section 2, we defined the problem tackled in this paper. Recently, much attention has been focused on searching for graphs satisfying some conditions in a database consisting of multiple graphs. Table 1 summarizes graph search problems and the publications that tackle each problem. The subgraph search problem is to find graphs that contain the query graph and can be expressed as follows:  
\[\{g_{i}\in G\mid q\subseteq g_{i}\},\]  
whereas the supergraph search problem is to find graphs that the query graph contains and it can be expressed as follows. \[\{g_{i}\in G\mid g_{i}\subseteq q\}.\]  
These problems contain the subgraph isomorphism problem, which is known to be NP-complete. The similar graph search problem is to find graphs that are similar to the query graph, and can be expressed as  
\[\{g_{i}\in G\mid ed(g_{i},q)\leq\theta\}.\]  
This problem contains the graph edit distance problem, which is known to be NP-complete. Various methods have been proposed to solve these problems. The problem tackled in this paper is to find graphs that are similar to subgraphs of the query graph and contains both the subgraph isomorphism problem and graph edit distance problem. This problem is a novel one, to the best of our knowledge. Since the subgraph isomorphism problem and graph edit distance problem are NP-complete, a naive method for solving either of the problems for a given query graph and for each graph in the database would be unrealistic. Most of the methods proposed in the articles cited in Table 1 are based on filtering and verification and an index in each of the methods has a set of patterns \(P\) extracted from the database in advance. For example, for the supergraph search problem, in the filtering phase,  
\[G^{\prime}=G\setminus\bigcup_{p\in P}\{g_{i}\in G\mid p\
ot\subseteq q,g_{i} \subseteq q\}\]  
is obtained. Subsequently, the verification phase checks whether \(g\subseteq q\), for each graph \(g\in G^{\prime}\). Figure 1(a) shows four graphs in a database and two patterns contained in an index. The index has the information that \(p_{1}\subset g_{1}\), \(p_{2}\subset g_{2}\), \(p_{1}\subset g_{4}\), and \(p_{2}\subset g_{4}\). Given the query shown in Figure 1(c), supergraph search methods first check whether \(p_{1}\subseteq q\) and \(p_{2}\subseteq q\) and then obtain \(G^{\prime}=\{g_{1},g_{3}\}\) in the filtering phase. In the verification phase, they test whether \(g_{1}\subseteq q\) and \(g_{3}\subseteq q\). Since the number of vertices in \(p_{2}\) is less than one for \(g_{2}\), the computation time to check whether \(p_{2}\subseteq q\) becomes less than one for \(g_{2}\subseteq q\) and we do not need to check whether \(g_{2}\subseteq q\) in the filtering phase. The patterns in \(P\) are either paths, trees, cycles, or graphs extracted from databases. The patterns are extracted by the enumeration or mining method. The enumeration method enumerates all subgraphs in graphs in a database, where the subgraphs are restricted to either paths, trees, cycles, or graphs. In contrast, the mining method enumerates all frequent patterns [24], which are defined as  
\[F(G,\sigma^{\prime})=\{p\mid p\subseteq g_{i},g_{i}\in G,\sigma(p,G)\geq \sigma^{\prime}\}\]  
from graphs in a database, where \(\sigma(p,G)\) is defined as the number of graphs in \(G\) containing pattern \(p\):  
\[\sigma(p,G)=|\{g_{i}\in G\mid p\subseteq g_{i}\}|.\]  
The extracted patterns are stored in a tree or lattice structure in the index of the graph database. Enumerating patterns and mining patterns from a database are time-consuming processes.