Efficient Correlated Subgraph Searches for AI-powered Drug Discovery

1 Introduction

The motivation of this work is to accelerate AI-powered drug discovery over large molecule databases. The correlated subgraph search (CSS) [Ke et al., 2007] has become an essential building block in effectively identifying molecules for clinical use [Ma et al., 2019; Lin et al., 2020; Zhang et al., 2022; Demir et al., 2022; Yagi and Shiokawa, 2022]. CSS models a biochemical database as a graph database, which is a set of small graphs corresponding to molecules. Given a query graph (molecule), CSS finds the subgraphs (substructures of a molecule) most correlated to the query in a database. Since the correlation between substructures is known to be a trustworthy feature in predicting drug properties [Askr et al., 2023; Yagi et al., 2023], CSS has been applied to the following AI-based drug discovery scenarios:

Ligand-based virtual screening (LBVS). LBVS is a common step to extract molecules, which are most likely to bind to a drug target. Recently, neural network models have become a standard way for large-scale LBVS [Askr et al., 2023; Kawano et al., 2024]. However, due to the structural complexity of molecules, existing models are overwhelmed by low extraction accuracy [Matsugu et al., 2023], and it is still challenging for them to dig out the beneficial molecules for clinical use. To overcome this limitation, CSS has attracted much attention because it can uncover correlated molecule pairs with a high binding probability. For example, [Naoi and Shiokawa, 2023] and [McGibbon et al., 2023] applied CSS to their LBVS models to extract effective features from molecules. Their CSS-based approaches discovered more beneficial molecules than other models. Similarly, CSSbased models achieved a better performance in detecting anticancer drugs [Nguyen and Wei, 2019; Prateek et al., 2020].

Molecule property prediction. CSS can enhance the performance of AI models for predicting molecule properties. [Ma et al., 2019] and [Lin et al., 2020] proposed CSS-based models to predict drug interactions for estimating whether a drug could react with one or more other drugs. The correlated substructures of drugs can reveal non-trivial drug-drug relations among molecules. By capturing such relations, these CSS-based networks outperformed other prediction models regarding the interaction estimation accuracy. Analogously, [Lee et al., 2014] and [Bhattacharjee and Vlachos, 2020] employed CSS to extract correlated proteins that frequently cooccur in an individual. Such proteins derived significant protein patterns to conduct detailed pre-clinical studies.

CSS can also be used in other AI-powered applications such as pathway analysis [Abdel-Hafiz et al., 2022] and molecular dynamics simulation [Yang et al., 2022].

Although CSS is effective, a large computation time is required because it incurs exponential costs [Ke et al., 2007]. For each graph, CSS must explore O(2n ) candidate subgraphs, where n is the number of nodes in the graph. Since subgraph correlation neither yields downward nor upward closure properties, traditional a priori approaches [Yan and Han, 2002; Elseidy et al., 2014] are not directly applicable to reduce the candidates. Furthermore, recent drug discovery requires handling massive databases, which can contain more than 105 molecules [Lipinski and Hopkins, 2004]. Hence, CSS requires several weeks or months for drug discovery.

1.1 Existing Approaches and Challenges

Many studies have strived to overcome the exponential costs in CSS. Although CSS must enumerate correlated subgraph candidates from an exponential space, exploring candidates only from frequent subgraphs is more reasonable. On the basis of this idea, threshold-based methods [Ke et al., 2007; Samiullah et al., 2014; Chowdhury et al., 2021] drop infrequent subgraphs from the database by using user-specified thresholds. For instance, CGSearch [Ke et al., 2007] invokes the frequent subgraph search, gSpan [Yan and Han, 2002], before candidate enumeration. The state-of-the-art method, bFact [Chowdhury et al., 2021], integrates several heuristic thresholds with gSpan to avoid exponential costs. Although these methods mitigate costs, they suffer from two critical drawbacks. First, finding frequent subgraphs still incurs expensive costs. Second, their heuristic thresholds sacrifice the search quality, making effective drug discovery difficult.

Bounding methods [Zou et al., 2009; Ke et al., 2009] have recently attracted attention as alternatives in the AI community [Naoi and Shiokawa, 2023]. These methods theoretically derive the bounds of the correlation coefficient between two subgraphs. For instance, PG-search [Zou et al., 2009] incrementally excludes unpromising subgraphs by following the bounds. To further improve the efficiency, the state-of-the-art method, TopCor [Ke et al., 2009], integrates heuristics with the bounds. Unlike threshold-based methods, these methods guarantee to find the exact top-k correlated subgraphs to a query graph within a reasonable running time.

Although bounding methods have improved efficiency, their computational costs are high to handle massive databases. The bounding methods require at least O(n2 ) time to test a correlation between two subgraphs [Welke, 2020]. That is, these methods totally incur O(NMn2 ) time, where N and M are the numbers of graphs in a database and tested subgraphs in each graph, respectively. In addition, bounding methods cannot exclude enough unpromising subgraphs if a query graph is frequent in the database because the bounds become loose. In the worst case, this incurs O(M) ≈ O(2n ) time, resulting a total time of O(N2nn2 ). Thus, the computational efficiency in CSS remains a challenge.

1.2 Our Approaches and Contributions

In this paper, we present a novel framework, Corgi, that accelerates existing CSS methods while ensuring top-k search accuracy. As discussed in Section 1.1, existing CSS methods suffer from exponential costs since they need to compute almost all subgraph candidates in a database. By contrast, Corgi dynamically removes unnecessary candidate subgraph computations from the database. In practical molecule databases, many graphs share similar substructures due to the limited varieties of chemical elements and valences [Shiokawa et al., 2019]. Since Corgi can effectively exclude such shared substructures by abstracting the database, it avoids exhaustive subgraph candidate computations.

Based on the above idea, we design Corgi with two steps. First, a summarized graph view abstracts a graph database to skip redundant computations for the shared substructures (Section 3.2). Second, a multi-viewed top-k search performs CSS methods over multiple summarized graph views to ensure top-k search accuracy (Section 3.3). Consequently, Corgi has the following attractive characteristics:

• Efficient: Corgi is significantly faster than state-of-theart CSS methods (Section 4.1). Corgi has a better time complexity than existing CSS methods (Theorem 1).
• Accurate: Corgi outputs accurate top-k correlated subgraphs to a query graph (Section 4.3). Corgi theoretically guarantees the top-k search accuracy (Theorem 2).
• Practical: We deployed Corgi in a practical LBVS model for clinical use. Corgi effectively discovered beneficial proteins that activate ADORA2A (Section 4.6).

Corgi is the first solution that achieves a high efficiency while maintaining search accuracy for large databases. We experimentally confirmed that Corgi is up to 48.6 times faster than other state-of-the-art methods. Although CSS plays a crucial role in achieving AI-powered drug discovery, applying it to large databases is challenging due to the expensive cost. By contrast, Corgi is well suited to massive databases and should contribute to various AI-based drug discovery.

2 Preliminary

Table 1 lists the main symbols used in this paper. A molecule is modeled as a graph g = (V, E, l), where a node set V and an edge set E correspond to atoms and chemical bonds, respectively. l is a label function that maps nodes and edges to corresponding chemical elements and bond types, respectively. For simplicity, we denote n = |V | and m = |E|.

Given gi = (Vi,Ei, li) and gj = (Vj,Ej, lj), we denote gi ⊆ gj if an injective function f : Vi → Vj exists such that for every edge (u, v) ∈ Ei, (f(u), f(v)) ∈ Ej, li(u) = lj(f(u)), li(v) = lj(f(v)), and li(u, v) = lj(f(u), f(v)). If gi ⊆ gj, gi is a subgraph of gj (or gj is a supergraph of gi). A graph database D is defined as a set of N graphs (i.e., D = {g1, g2, . . . , gN}). Given a database D and a graph g, we denote Dg = {g′ ∈ D | g ⊆ g′ } as all supergraphs of g in D. The support of g in D, which is denoted as sup(g), is defined as the proportion of Dg in D (i.e., sup(g) = |Dg| |D| ). Additionally, sup(gi, gj) = |Dgi ∩Dgj | |D| is defined as the joint support of gi and gj in D.

We employ the following Pearson's correlation [Reynolds, 1977] to measure the correlation between two graphs. Other measures can be applied in a similar manner [Ke et al., 2008]. Definition 1. Given gi and gj, the Pearson's correlation be-

tween gi and gj is denoted by φ(gi, gj) and is defined as

Note that φ(gi, gj) = 0 if the denominator of Eq. (1) is 0. φ(gi, gj) falls between -1 and 1. φ(gi, gj) = 0 means that the occurrences of gi and gj in D are independent. If φ(gi, gj) > 0, the occurrences of gi and gj are positively correlated in D. Otherwise, they are negatively correlated.

Problem statement. We formulate the problem addressed in this paper. Given a graph database D and a query graph q, we focus on the top-k CSS problem to find k subgraphs that are the most positively correlated to q in D. This is defined as

Problem 1. Given a graph database D, a query graph q = (Vq,Eq, lq), and k ∈ N+, the top-k CSS problem is a task to find k subgraphs of graphs in D, Tk(D) = {g1, g2, . . . , gk} to maximize ∑gi∈Tk(D) φ(q, gi).

In the worst case, Problem 1 incurs O(N2nn2 ) time. Hence, existing methods fail to complete CSS on large databases.

3 Proposed Framework: Corgi

We present our framework to accelerate existing CSS methods with top-k search accuracy assurance.

3.1 Basic Ideas

Corgi aims to accelerate CSS methods while ensuring top-k search accuracy. Existing CSS methods explore the exponential number of subgraph candidates in D. By contrast, Corgi introduces two approaches to remove unpromising subgraph computations without sacrificing search quality. The first approach theoretically derives summarized graph views of D. The views produce small summaries of D, which require significantly fewer search costs than their original counterparts. The second approach employs a multi-viewed top-k (MvTk) search to guarantee the search accuracy. Although the views improve the efficiency, they may lead to false negatives or positives. To overcome this, the MvTk search refines the search results using multiple summarized graph views. Unlike existing methods, Corgi computes limited subgraph candidates while maintaining the top-k search accuracy.

Our ideas have two main advantages. (1) Corgi finds the top-k correlated subgraphs with a short running time in realworld molecule databases. In practical drug discovery, the molecules often share similar substructures due to the limited varieties of chemical elements and valences. Our ideas successfully handle such structural properties because the summarized graph views can drastically reduce the graph sizes in D if graphs have similar substructures. This allows Corgi to enhance its performance even for large databases. (2) Corgi produces the same search results as existing CSS methods. We theoretically demonstrated that Corgi does not miss opportunities to find the top-k subgraphs if it uses a sufficient number of views. Thus, Corgi can guarantee the top-k search accuracy, unlike existing CSS methods.

3.2 Summarized Graph View

We introduce the summarized graph view to reduce the computational costs of CSS methods. It is a set of abstracted graphs generated by folding a set of node pairs in D. First, we formally define the node pairs to be folded in the view.

Definition 2. For (u, v) ∈ E, a node pair is denoted by 〈l(u), l(u, v), l(v)〉. Given D = {g1, g2, . . . , gN} and p ∈ N+, Ap(D) is a set of p folded node pairs of D expressed as

where L(D) = ⋃gi∈D ⋃(u,v)∈Ei{〈l(u), l(u, v), l(v)〉}, and ψ is a function that randomly selects a node pair 〈l(u), l(u, v), l(v)〉 from L(D)\Ap-1(D).

Definition 2 indicates that Ap(D) is composed of p independent node pairs, which are randomly selected from L(D).

For convenience, the following function is defined to map node v to u if 〈l(u), l(u, v), l(v)〉 ∈ Ap(D).

Definition 3. Given the folded node pairs Ap(D), a mapping function πAp(D)(v) is defined as

Finally, we define the summarized graph view.

Definition 4. Given D = {g1, g2, . . . , gN} and Ap(D), a summarized graph view, which is denoted by ˆD, is defined as ˆD = { ˆ g1, ˆ g2, . . . , ˆ gN}, where ˆ gi = ( ˆ Vi, ˆ Ei, ˆ li) is an abstracted graph composed of

and ˆ li is a label mapping function of ˆ gi .

Definition 4 indicates that folding node v into u ∈ Vi generates an abstracted graph ˆ gi if the corresponding node pair 〈l(u), l(u, v), l(v)〉 is included in Ap(D). By querying correlated subgraphs on the summarized graph view, Corgi can significantly reduce the search space of CSS methods compared to their original counterparts. This is because, as shown in Definition 4, ˆD drastically reduces the average graph size in D by folding the node pairs in Ap(D).

From Definition 4, we have the following property:

Lemma 1. Given D and Ap(D), a summarized graph view ˆD can be obtained in O((p · mn )N) time, where n and m are the average number of nodes and edges in D, respectively.

Proof. For every graph g in D, Definition 4 requires folding at most p node pairs included in Ap(D). Given a node pair 〈l(u), l(u, v), l(v)〉 ∈ Ap(D), Corgi can fold node v into u by removing node v and edges incident on v. This incurs O( mn ) time, where mn is the average degree of g [Shiokawa et al., 2013]. Hence, Definition 4 requires O((p · mn )N) time.

In practice, mn should be a small constant in real-world molecule databases. Specifically, the real-world databases examined in Section 4 have d = mn = 1.61 on average (Table 2). Thus, Lemma 1 implies that Definition 4 incurs a nearly linear scalability against the database size. In other words, O((p · mn )N) ≈ O(pN) time. In Section 4, we experimentally evaluate the overhead of Definition 4.

Here, we further derive the following properties, which are essential to discuss our MvTk search shown in Section 3.3.

Lemma 2. Let g′ ⊆ gi be a top-k correlated subgraph, and (u, v) be an edge between u ∈ V ′ and v ∈ Vi\V ′ . If node u is folded into v, g′ can be a false negative result.

Proof. Let ˆ gi be an abstracted graph obtained by folding node u into v on gi. g′ ̸⊆ ˆ gi clearly holds even if g′ ⊆ gi because no injective mapping of u exists in ˆ gi. Thus, CSS methods fail to extract g′ from ˆ gi .

Lemma 3. Let ˆ gi and ˆ g be abstracted from gi and g, respectively. If ˆ gi ⊆ ˆ g but gi ̸⊆ g, then ˆ gi can be a false positive.

Proof. Since ˆ gi ⊆ ˆ g, ˆ g can be regarded as the top-k subgraph in spite of gi ̸⊆ g. Thus, ˆ gi can be a false positive.

Lemmas 2 and 3 indicate that Definition 4 may lead to false negatives or positives in the top-k search results.

3.3 MvTk Search

The MvTk search is introduced to guarantee the top-k search accuracy on the summarized graph views. As shown in Lemmas 2 and 3, Corgi produces false negative or positive results if it performs CSS on a summarized graph view. The MvTk search employs (1) an extraction step and (2) a validation step to exclude false negatives and positives, respectively.

(1) Extraction step. To avoid false negatives, Corgi extracts candidate subgraphs C using multiple summarized graph views. Let CSS(D, q, k) be an existing CSS method that returns top-k subgraphs correlated to q in D. First, we define the candidate subgraphs C.

Definition 5. Given a query q and T summarized graph views ˆD1, ˆD2, . . . , ˆDT , a set of candidate subgraphs C is defined as C = ⋃Ti=0 ˆ Tk( ˆDi), where ˆ Tk( ˆDi) is the top-k search result of CSS( ˆDi, ˆ qi, k) and ˆ qi is a query graph abstracted by Ap(D) corresponding to ˆDi.

C is T × k correlated subgraphs obtained by querying ˆ qi on ˆDi for all views ˆD1, ˆD2, . . . , ˆDT . Recall that Ap(D) is randomly selected from Definition 2. Consequently, ˆ Tk( ˆD1), . . . , ˆ Tk( ˆDT ) can have diverse correlated subgraphs. Herein, we derive the following property from Lemma 2:

Lemma 4. Given a summarized graph view ˆD, and the corresponding folded node pairs Ap(D), the false negative ratio of top-k CSS on ˆD is 1 - (1 - p |L(D)| )m, where m = 1N ∑gi∈D 1 2ni ∑gj⊆gi mj .

Proof. Suppose a subgraph gi ∈ D is a top-k correlated subgraph of a query graph q (i.e., gi ∈ Tk(D)). From Lemma 2, gi is a false negative subgraph if Ei has at least one folded edge in ˆD. Recall that D has |L(D)| node pairs by Definition 2, and p pairs are now folded in ˆD. Thus, each edge in Ei is folded with a probability of p |L(D)| . That is, gi is a false negative subgraph with the probability of 1-(1- p |L(D)| )mi . Averaging mi over all subgraphs in D gives a probability 1- (1- p |L(D)| )m. This completes the proof.

On the basis of Lemma 4, we can theoretically demonstrate that the subgraph candidates bound the false negative ratio.

Lemma 5. Given subgraph candidates derived from T summarized graph views, the subgraph candidates can bound false negative ratio by ϵ ∈ [0, 1] if T satisfies

Proof. Let P = 1 - (1 - p |L(D)| )m. Then, Inequation (6) can be rewritten as T ≥ log(ϵ) log(P) . Since log(P) < 0, we can derive P T ≤ ϵ. From Definition 5 and Lemma 2, Corgi fails to avoid false negatives only if all summarized graph views yield the false negative top-k search results. Lemma 4 shows that the false negative subgraphs have a probability of P T . Hence, P T ≤ ϵ indicates that the false negative ratio of Corgi is bounded by ϵ. This completes the proof.

Lemma 5 demonstrates that Definition 5 avoids false negatives if T is sufficiently large. Let n be the average graph size in D. In practice, m ≈ n2 , because molecules generally have m ≈ n, which gives m ≈ 1N ∑gi∈D 1 2ni ∑ni k=1 (ni k )k = n2 .

(2) Validation step. Finally, Corgi excludes false positives from the candidate subgraphs. Lemma 3 indicates that the candidate graphs need to be unfolded to filter out the false positives. To this end, we introduce the following definitions:

Definition 6. Given ˆ g ∈ C folded by Ap(D), the unfolded subgraph of ˆ g is g′ = (V ′ ,E′ , l′ ) such that

and l′ is a label mapping function of g′

Definition 7. Given an unfolded graph g′ and Dg′ , the unfolded candidate subgraphs of g′ , which are denoted by G(g′ ), are defined as G(g′ ) = {g′′ 1 , . . . , g′′ |Dg′ | }, where g′′ i is an induced subgraph gi[V ′ ] of gi included in Dg′ .

From Definitions 6 and 7, we derive the following lemma: Lemma 6. Let ˆ g be an abstracted subgraph of g ⊆ gi. If g′ is the unfolded subgraph of ˆ g, then g is isomorphic to gi[V ′ ].

Based on Definitions 6 and 7, Corgi initially unfolds every candidate subgraph in C into g′ . Then, it induces all unfolded candidate subgraphs fromDg′ by using g′ .

Proof. Suppose that gi[V ′ ] = ( ˙V , ˙E, ˙ l) and g = (V,E, l). Since gi[V ′ ] is a subgraph induced in gi by V ′ , ˙V = V ′ holds. From Definition 6, V ′ = ˆ V ∪ {v | ∃u ∈ ˆ V , 〈l(u), l(u, v), l(v)〉 ∈ Ap(D)} = V . Hence, gi[V ′ ] = gi[V ] = (V, E, l). This completes the proof.

• 6: return I;

Algorithm 2 (Phase 2) MvTk search

Input: D = {g1, g2, . . . , gN}, q, k, I; Output: Tk(D); 1: Tk(D) ← ∅, C ← ∅, G ← ∅; 2: If I = ∅ then Obtain I by Algorithm 1; ▷ (1) Extraction step: 3: for each ˆDt ∈ I do 4: ˆ Tk( ˆDt) ← CSS( ˆDt, ˆ qt, k) by Definition 5; 5: C ← C ∪ ˆ Tk( ˆDt); ▷ (2) Validation step: 6: for each ˆ g ∈ C do 7: G ←G ∪ G(ˆ g) by Definitions 6 and 7; 8: for each g ∈ G do 9: Obtain φk and gk from Tk(D); 10: if φ(q, g) > φk then Tk(D) ← (Tk(D)\{gk}) ∪{g}; 11: return Tk(D);

Lemma 6 indicates that Corgi can exclude false positives by screening all unfolded candidate subgraphs derived from the candidate subgraphs C (Definition 7).

3.4 Algorithm

Algorithms 1 and 2 fully describe Corgi. Corgi is divided into two phases: (Phase 1) view generation and (Phase 2) MvTk search. Phase 1 is an offline step. It is implemented only once prior to Phase 2. By contrast, Phase 2 is an online step, which is executed whenever a query is inputted.

Algorithm 1 constructs T summarized graph views. To estimate a sufficient T value without false negatives, Corgi obtains T from ϵ by Lemma 5 (line 2). Then the views are generated by following Definition 4. Once a query is inputted, Corgi invokes the MvTk search shown in Algorithm 2. In the extraction step, Corgi invokes an existing CSS method denoted by CSS( ˆDt, ˆ qt, k) on each summarized graph view generated by Algorithm 1. Consequently, Corgi obtains T ×k results (i.e., C). In the validation step, Corgi unfolds C into G by Definitions 6 and 7. Afterward, false positives are filtered from G, and Corgi outputs Tk(D).

Finally, Corgi has the following theoretical properties:

Theorem1. Corgi incurs O((k×T)N ·n+T ·FCSS(N, n′ )) time, where n and n′ are the average graph size in D and ˆD, respectively. FCSS(N, n′ ) is the computational cost of CSS methods on N graphs with an average size n′ .

Proof. From Lemma 1, Algorithm 1 incurs O(p · mn )N) ≈ O(N) time since p · mn ≪ N. In Algorithm 2, the extraction step repeats the CSS method T times, requiring O(T · FCSS(N, n′ )) time. The validation step computes Definitions 6 and 7 |C| = k × T times. Since Definitions 6 and 7 totally require O(p + N · n) time, lines 67 in Algorithm 2 incur O((k × T)N · n) time. Additionally, lines 8-10 need O(N) time. Overall, Corgi requires O((k ×T)N · n+T · FCSS(N, n′ )) time.

Corgi has smaller computational costs than other state-ofthe-art methods, which require O(N2nn2 ) time. In practice, n′ ≪ n since Corgi repeatedly folds node pairs to generate the summarized graph view. Specifically, Table 2 shows that the real-world databases examined in the next section have at most n′ ≤ 10.1, while n ≤ 35.6. Thus, Corgi improves computational costs compared to existing CSS methods.

Theorem 2. If ϵ = 0 in Algorithm 1, Corgi outputs the same top-k correlated subgraphs as existing CSS methods.

Proof. By Lemma 5, Corgi can avoid false negatives if ϵ = 0. Additionally, from Lemma 6, it can exclude all false positives included in the unfolded candidate subgraphs. Thus, Corgi outputs the same results as existing CSS methods.

4 Experimental Evaluation

We evaluated the effectiveness of Corgi in a comparison experiment with three types of state-of-the-art CSS methods.

• Corgi: Our framework proposed in Section 3. We employed TopCor [Ke et al., 2009] for the CSS method invoked in Algorithm 2 and set ϵ = 0.05 and T to the

smallest value derived by Lemma 5. For each database, p is set to the largest possible value.

• Threshold-based methods: We evaluated CGStream [Pan and Zhu, 2012] and bFact [Chowdhury et al., 2021], which enumerate all subgraphs having a correlation larger than a threshold θ. By following [Ke et al., 2009], θ is varied from 1.0 to 0.0 in 0.1 decrements to obtain top-k correlated subgraphs.
• Bounding methods: We evaluated TopCor [Ke et al., 2009] and iTopCor [Latsiou and Papadopoulos, 2011], which automatically specify the bounds to output the exact top-k correlated subgraphs.
• Single-graphmethods: We evaluated CSM-A [Prateek et al., 2020], which extracts top-k correlated subgraphs from a single graph. Candidate subgraphs are extracted by applying CSM-A to every graph in the databases, and subsequently filtering false positives.

Evaluations were conducted on a server with an Intel Xeon CPU 2.90 GHz and 1 TiB RAM. All methods were implemented in C/C++ using the "-O3" option.

Datasets. We tested 12 public molecule databases published by NCI [Nicklaus et al., 2012], DUD-E [Mysinger et al., 2012], LIT-PCBA [Nguyen et al., 2020], and ZINC 20 [Irwin et al., 2012]. Table 2 shows their statistics, where n, n′ , and d denote the average graph size, the average summarized graph view size, and the average degree, respectively. For more details, please refer Appendix A.

Query. Consistent with [Ke et al., 2009; Prateek et al., 2020], ten queries are generated for each database by randomly selecting subgraphs from the database. The results are averaged over the above ten queries. Following the practical requirement of drug discovery [Garcia-Hernandez et al., 2019; Naoi and Shiokawa, 2023], we regard a query as not finishing if its running time exceeds 7,200 seconds.

4.1 Efficiency

Pre-computation time. As discussed in Section 3, Corgi invokes the view generation phase prior to the MvTk search phase. Here, we assess the pre-computation time by comparing Corgi with bFact because both require the precomputations. Table 3 shows the running time consumed in the pre-computations, where "> 7, 200 sec." indicates the corresponding pre-computation did not finish within 7,200 seconds. Corgi is significantly faster than bFact. As proved in Lemma 1, the pre-computation time of Corgi is proportional to N, whereas bFact fails to complete the pre-computation for N ≥ 40, 000. Corgi requires at most 90 seconds, which is negligible compared to the query processing time.

Query processing time. Figure 1 shows the running time of top-k queries on real-world databases, where DNF indicates that the running time exceeded 7,200 seconds. Corgi achieves the highest overall performance. On average, it is 29.8 times faster than the other CSS methods. Not only does Corgi ensure the top-k search accuracy by Lemma 5, but it is also up to 6.6, 5.9, 48.6, 24.9, and 26.1 times faster than TopCor, iTopCor, CGStream, bFact, and CMS-A, respectively. The superior running time is attributed to the summarized graph view since it drastically reduces the graph sizes (Section 3.2). Corgi is more efficient than the other methods, even if the dataset has a large n. As an example, consider the running times on D2 and D7 in Figure 1. Recall that D2 has a larger n than D7 but these two databases have the same number of graphs (i.e., N = 20, 000). TopCor, iTopCor, CGStream, bFact, and CMS-A show significantly longer running times on D2 compared with the results of D7. This is because these methods incur O(2n ) costs in the worst case. By contrast, Corgi introduces the summarized graph views to help mitigate the exponential costs even if n increases. Thus, Corgi can efficiently find top-k subgraphs for large n.

4.2 Scalability

We experimentally discuss the scalability of Corgi. Figure 2 compares the running time of Corgi with the most competitive method, iTopCor. We varied k as 10, 25, 50, 100, 200, and 400 using D1 (Figure 2 (a)) and N from 10,000 to 60,000 with k = 50 on D4 (Figure 2 (b)). Corgi achieves a better scalability than iTopCor. iTopCor exponentially increases its running time as N increases due to its high time complexity. By contrast, as we proved in Theorem 1, Corgi achieves a nearly linear scalability against N.

Figure 2 (c) shows the running time (k = 100) by varying the average graph size n on the synthetic databases. We used GraphGen [Goyal et al., 2020] to generate five databases by varying the size n as 10, 30, 50, 70, and 90. We produced N = 10, 000 graphs with 10 node labels and 4 edge labels, with a density of 0.15. In the figure, Corgi also outperforms iTopCor for all n settings. Corgi completes CSS within 1,000 seconds even if n ≥ 90, while iTopCor exceeds 7,200 seconds. Corgi can drastically reduce the average graph size by generating summarized graph views. Hence, it can mitigate the exponential costs incurred by the CSS methods.

4.3 Accuracy

One advantage of Corgi is that it outputs the top-k correlated subgraphs with accuracy assurance, while folding graphs to improve the runtime efficiency. To confirm this advantage, we evaluated the top-k search accuracy against the groundtruth top-k search results. We used precision to measure the accuracy compared with the ground-truth results. Since TopCor, iTopCor, and CGStream output exact top-k subgraphs, their results are regarded as the ground truth.

Figure 3 compares the precision scores of Corgi, bFact, and CMS-A to the ground truth. Similar to the previous section, "DNF" indicates that the top-k queries did not finish within 7,200 seconds. Additionally, the dashed lines represent the accuracy (i.e., 1 - ϵ = 0.95), guaranteed by Corgi discussed in Lemma 5. Corgi gives higher precision scores than bFact and CMS-A. Because ϵ = 0.05 for Corgi, it achieves higher precision scores than 1 - ϵ = 0.95 for all settings. By contrast, bFact and CMS-A fail to reproduce the ground-truth results because they exclude subgraphs on the basis of thresholds without theoretical guarantees. As proved in Lemma 5, Corgi can bound the false negative ratio by ϵ. In addition, by Lemma 6, its validation step filters all false positives. Therefore, Corgi can find highly accurate top-k subgraphs.

4.4 Memory Footprint

Herein we experimentally discuss the space costs required by Corgi. We measured the memory footprint of Corgi compared with other CSS methods on the real-world datasets. Figure 4 shows the memory footprint of each method, where "DNF" in the figures indicates the corresponding CSS method could not within 7,200 seconds. In this section, we report results only for D1, D2, D7, and D8 since all methods outputted very similar results.

As shown in Figure 4, Corgi outperforms the other CSS methods in terms of the memory footprint. Specifically, Corgi requires up to a 198 times smaller memory footprint compared to the others. As discussed in Sections 1.1 and 2, existing CSS methods need to enumerate an exponential number of subgraph candidates, which imposes an exponential space cost against graph sizes. By contrast, Corgi drastically reduces the graph size by introducing the summarized graph views. Consequently, our proposed framework successfully mitigates the drastic increase of the memory footprint compared to the other CSS methods.

4.5 Effectiveness of the MvTk Search

We experimentally discuss how the MvTk search effectively avoids false positives and negatives. We measured the precision of the top-k search results of Corgi and their corresponding running time by varying the number of summarized graph views T; T is increased from 1 to the value obtained by Lemma 5 on D1, and we used k = 50 and ϵ = 0.05.

Figure 5 (a) shows that Corgi successfully achieves higher precision than 1-ϵ if T = 5, which is derived from Lemma 5. From Lemma 6, Corgi guarantees to exclude all false positives from its top-k search results. That is, Figure 5 (a) indicates that Lemma 5 effectively bounds the false negative ratio. Also, in Figure 5 (b), Corgi has a linear scalability against T . Given T summarized graph views, Algorithm 2 needs to iterate extraction and validation steps T times. Thus, as proved in Theorem 1, Corgi requires a linear running time against T .

4.6 Case Study

To demonstrate the practicality of Corgi, we deployed Corgi into an LBVS model [Naoi and Shiokawa, 2023] to discover proteins that activate the adenosine A2A receptor (ADORA2A). Because ADORA2A regulates the myocardial oxygen demand and increases coronary circulation, proteins activating ADORA2A are potential therapeutic targets for cardiovascular diseases. We executed Corgi, bFact, and CMS-A on a public database containing over 30,000 proteins [Mysinger et al., 2012]. We inputted a query composed of a common substructure of adenosine (Figure 7 (a)), and we set k = 50 and ϵ = 0.05. Once the top-k subgraphs were obtained, we chemically tested how many subgraphs actually activated ADORA2A.

Figures 6 (a) and (b) show the running time and accuracy of the LBVS models in this case study, respectively. The accuracy is the fraction of the top-k graphs that activate ADORA2A. Corgi achieves the best accuracy and shortest running time among the CSS methods. Specifically, Corgi discovered 43 of the 50 proteins that activate ADORA2A. Figure 7 (b) shows the top-5 largest proteins activating ADORA2A obtained by Corgi. We observed that all of the top-5 proteins yield the following chemical properties: (1) the H-bond acceptor ratio is larger than 10, and (2) the partition coefficient is greater than 2. These results are reasonable and consistent with the biochemical researchers' intuition because the properties indicate that the proteins are more lipophilic, one of the standard features activating ADORA2A. These results suggest that Corgi can be a powerful option for AI-powered drug discovery.

5 Conclusion

Corgi is a novel CSS framework that accelerates existing CSS methods for drug discovery while ensuring search accuracy.

(a) A query graph.

(b) The top-5 largest proteins obtained by Corgi. All proteins activate the adenosine A2A receptor.

Figure 8: Distribution of the graph sizes.

Corgi constructs summarized graph views to exclude unnecessary computations. Our experiments demonstrate that Corgi improves the efficiency of state-of-the-art CSS methods. Moreover, Corgi successfully discovered beneficial proteins to activate ADORA2A.

A Distributions of Graph Size

In Section 4, we tested 12 datasets that are detailed in Table 2. As discussed in Sections 2 and 3, existing CSS methods require an exponential costs against the graph size in a database. To support the discussions in Section 4, Figure 8 show the distribution of graph sizes in each dataset.

As shown in the figures, most databases have a limited graph sizes, which is at most n = 65, except for D1, D2, D3, and D4, while NCI datasets yield a long tail distribution. As shown in Figure 1 of the paper, Corgi can complete the query processing within a reasonable time regardless of the graph size distributions. By contrast, in the existing CSS methods such as iTopCor and bFact, their running time is significantly affected by the distribution; if a database has a large graph, they incur a large running time. Unlike existing CSS methods, as discussed in the paper, Corgi can shrink the graph size by introducing the summarized graph views even if databases have a long tail distribution. Hence, it can successfully mitigate the exponential costs incurred by the CSS methods.

B Limitations of Corgi

Corgi still has one limitation in efficiency. Although Corgi has better scalability than other the CSS methods against the average graph size, Corgi still requires a large computation time for the CSS problem if the size significantly increases, e.g., n′ ≥ 200. As proved in Theorem 1, Corgi requires at least O(FCSS(N, n′ )) time, where FCSS(N, n′ ) is the time complexity of existing CSS methods on N graphs with an average graph size n′ . Thus, for a large n′ , Corgi still needs to explore a large search space to solve the CSS problem. However, this limitation does not have a serious impact for our primary focus, i.e., AI-powered drug discovery. This is because that, as shown in Table 2, real-world molecule databases practically have a small average graph size.

Acknowledgments

This paper was partially supported by JST AIP Acceleration Research JPMJCR23U2, JST PRESTO JPMJPR2033, and JSPS KAKENHI 22K17894.

Contribution Statement

H. Shiokawa and Y. Naoi are equally contributed to this paper.