# Similar Supergraph Search Based on Graph Edit Distance
## 1 Introduction  
The coronavirus disease (COVID-19) has been spreading widely since 2019. In Japan, ravipiravir (brand name: Avigan) has been examined as a promising antiviral medication against COVID-19. Favipiravir was initially developed as a medication to treat influenza. When Favipiravir is ribosylated, its structure resembles acadesine, which is a precursor to inosine. Inosine is the previous stage of guanosine and adenosine, which are components of RNA [1]. With this treatment, the RNA synthetase of a virus mistakenly incorporates ravipiravir, instead of guanosine, into the replicating virus. This causes RNA synthesis to stop and limits the replication of viruses inside the body. Figure 1 shows the chemical structures of guanosine, inosine, acadesine, and ribosylated ravipiravir. The substructure \(\alpha\), drawn in red, is common to all of guanosine, inosine, and acadesine. Therefore, in order to find candidate compounds for a new drug, it may be useful to search for compounds containing a substructure, provided as a query, in a database that consist of many compounds (i.e., substructure search). Conversely, if many substructures relevant to new drug development are known, it can be useful to search for substructures contained in a newly developed chemical compound, provided as a query, in a database recording these substructures (i.e., superstructure search). This paper discusses methods related to the latter task. The substructure drawn in blue in Figure 1 is similar to the substructure \(\alpha\), but they do not match perfectly. In the situation shown, the substructure \(\alpha\), which contributes to anti-influenza agents, is registered in a database. The database contains various substructures for which its medicinal effects, side effects and so on are known. If ribosylated ravipiravir is given as the query and the substructure \(\alpha\) is the output as the search result, we may be able to discover that ribosylated ravipiravir is anti-influenza. Therefore, such a search engine for chemical compounds would be very useful and effective. A compound can be represented as a graph, in which the vertices and edges correspond to the atoms and chemical bonds, respectively. The aforementioned substructure and superstructure search correspond to subgraph search [2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14] and supergraph search [15; 16; 17; 18; 19; 20; 21; 22], respectively, which are actively being studied by researchers. A graph is a highly versatile data structure for representing information in many fields. It can be used to represent human relationship networks, protein interaction networks, resource description frameworks (RDF), computer-aided designs (CAD), and computer vision images; moreover, subgraph and supergraph search are used for many applications in addition to searching for compounds. However, there is no method for searching for graphs that are similar to subgraphs of a query graph and no method applicable to the resemblance between substructures shown in Figure 1. This paper proposes the problem of similar supergraph search and also proposes a method to solve it. In this paper, we measure the similarity between two graphs \(g\) and \(g^{\prime}\) by the graph edit distance. The graph edit distance is the minimum number of edits required to transform g to another \(g^{\prime}\), where an edit is either an insertion, deletion, or relabeling of a vertex or edge. The number of graphs obtained by editing the graph \(g\) times increases drastically, especially when the numbers of vertices and edges are large and the varieties of vertex and edge labels are wide. Such a drastic increase in edited graphs makes it difficult to find similar graphs. However, some real applications need to obtain a subset of graphs edited \(\theta\) times. For example, editing the substructure in a broken ellipse of Figure 1 is not admissible, whereas editing the remainder of the blue substructure is admissible.