# Similar Supergraph Search Based on Graph Edit Distance
## 3 Related Work
\begin{table}
\begin{tabular}{l l l} \hline \hline  & **Complete Matching** & **Similar Matching** \\ \hline graph & \(\{g_{i}\in G\mid q=g_{i}\}\) & \(\{g_{i}\in G\mid ed(g_{i},q)\leq\theta\}\) \\ search & \(\{g_{i}\in G\mid g_{i}\subseteq q\}\) & \(\{g_{i}\in G\mid\exists q^{\prime}\subseteq q\,s.t.\,ed(g_{i},q^{\prime}) \leq\theta\}\) \\ search & [15; 16; 17; 18; 19; 20; 21; 22] & This paper (novel problem). \\ \hline subgraph & \(\{g_{i}\in G\mid q\subseteq g_{i}\}\) & \(\{g_{i}\in G\mid\exists g\subseteq g_{i}\,s.t.\,ed(g,q)\leq\theta\}\) \\ search & [2; 3; 4; 5; 14] & There are no papers to our best knowledge. \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Summary of graph search problems and references. CodeTree [17] is a method for the supergraph search problem. It does not distinguish between filtering and verification phases; it filters out graphs that are not contained in a given query graph while verifying unfiltered graphs. In addition, CodeTree does not enumerate or mine patterns in a database. All graphs in a database are stored in the form of one of the graph codes, such as AcGM [33] code or DFS [34] code, in the index in CodeTree. The AcGM and DFS codes are based on adjacency matrices and adjacency lists, which are alternatives to graph representations. The algorithms for constructing an index for a database and searching graphs in the index are independent of the graph codes and, thus, the method can be integrated and extended with various graph codes for representing graphs in accordance with the intended characteristics of those codes. For this reason, the method proposed in this paper is based on CodeTree. In this paper, we focus on the problems in which each database consists of multiple graphs. Other subgraph search problems are to search for a database which consists of \"a single large graph\". Since the number of graphs given as input is two, we need not distinguish the subgraph and supergraph searches. A typical problem of the graph search with a single large graph is to output all embeddings (or occurrences) \(\{(\phi(v_{1}),\phi(v_{2}),\ldots,\phi(v_{|V(q)|}))\}\) in a large graph \(g\) for a query \(q\) consisting of vertices \((v_{1},v_{2},\ldots,v_{|V(q)|})\) when the query \(q\) is a subgraph of the large graph \(g\). This problem is applicable to RDFs (Resource Description Frameworks), where each subject or object and predicate corresponds to a vertex and edge in a graph, respectively; PPI (Protein-Protein Interaction) networks, where each protein and interaction correspond to a vertex and edge, respectively; and intrusion alert networks where each computer and possible attack such as Denial-of-Service and TCP Service Sweep correspond a vertex and edge, respectively. Some of the methods for solving these kinds of problems use not only exact matching [35; 36; 37] but also approximate matching [38; 39; 40; 41] with various similarity measures. The most representative metric for measuring similarity between two graphs is the graph edit distance. Most of methods for graph search problems use this graph edit distance to measure similarities among graphs. Other most representative measures are to use maximum common subgraphs or graph kernels [42; 43] between two graphs. There are two types of problems called maximum common induced subgraph problem [44] and maximum common edge subgraph problem [45] and the problems for finding the maximum common subgraphs in two graphs is NP-complete. In contrast, graph kernels have been proposed to classify graphs in the machine learning domain. The random walk graph kernel [46] returns a high similarity of graphs if random walks on the graphs produce similar sequences of vertex and edge labels. The Weisfeiler-Lehman graph kernel [47] uses the Weisfeiler-Lehman test, which was proposed to solve the graph isomorphism problem. The kernel iteratively relabels each vertex \(v\) by concatenating a label of \(v\) and labels of \(v\)'s adjacent vertices and returns high similarity for two relabeled graphs if the graphs have many common labels.