# Similar Supergraph Search Based on Graph Edit Distance
## 8 Experimental Evaluation  
For our experimental evaluation, we used the three real-world datasets used in [18] which were downloadable from [[https://github.com/SNUCSE-CTA/IDAR](https://github.com/SNUCSE-CTA/IDAR)]([https://github.com/SNUCSE-CTA/IDAR](https://github.com/SNUCSE-CTA/IDAR)) on 1 March 2021. The datasets consisting of chemical compounds are called AIDS, NCI, and PubChem. Each atom, chemical bond, atom type, and bond type in a chemical compound corresponds to a vertex, edge, vertex label, and edge label, respectively. Sets of queries and databases containing graphs were generated from each of the datasets. One hundred query graphs, each containing more than 100 vertices, were selected from each of the datasets. Each generated database contained between 10,000 and 100,000 graphs and each of the graphs was generated by one of two different methods [18]. In the first method, each graph in a database consisted of vertices and edges on a random walk on a graph randomly selected from one of the datasets. This type of database is called _rand_. In the second method, each graph in a database was a frequent subgraph with a minimum support value of 0.1% [24] that is enumerated from one of the datasets. This type of database is called _freq_. In the experiments, vertices corresponding to hydrogen were removed, which is similar to the experiments in [2,14,17,30]. Table 2 summaries graphs in databases and queries in our experiments. Since the problem of similar supergraph search is a novel problem proposed in this paper, there are no methods for solving this problem other than our proposed method to the best of our knowledge. Although we cannot compare our proposed method with other methods, our method is based on CodeTree (We use \"CodeTree\" to name the method proposed in [17] and \"code tree\" to represent the index used in CodeTree). This is proposed in [17] and our method with \(\theta=0\) is equivalent to CodeTree. Our proposed method was implemented in Java and the experiments reported in this section were conducted on a workstation with an AMD Ryzen Threadripper 3970X 3.7 GHz CPU and 64 GB main memory. First, we conducted experiments for Algorithm 4 with Equation (17). Figures 7-9 show the average computation time (query processing time) \(t\), the average number of nodes \(n\) in the code tree that our method traversed, and the average number of solutions \(|S|\), respectively, for various numbers of graphs \(|G|\) in a database and various thresholds \(\theta\). The computation time increased as the number of graphs in a database increased, as shown in Figure 7. Although the time complexity of Algorithms 1 and 2 is linearly related to the number of graphs in the database, the computation time of our method was sublinear for the number of graphs in the database because Algorithm 4 maintains the correspondence between a vertex of a query graph and vertices of multiple graphs in the database simultaneously. In contrast, the computation time increased exponentially as \(\theta\) was increased, as shown in Figure 7. This is because the number of graphs reachable by editing a graph \(q^{\prime}\subseteq q\ \theta\) times increases exponentially. Although the computation time increased as the database size increased for _freq_ databases, the rate of increase was less than for _rand_ databases. This is because the numbers of nodes in code trees for _freq_ databases are smaller than those for _rand_ databases and the former numbers are relatively unchanged by the increase in database size, as shown in Figure 10. The reason why the numbers of nodes in code trees are largely unaffected by database size is that frequent subgraphs enumerated from the datasets are similar to each other and the AcGM codes of similar frequent subgraphs have common prefixes. This is because a subgraph of a frequent subgraph is also a frequent subgraph, which is a consequence of the anti-monotonic property of the support value [24].