Abstract
Correlated Subgraph Search (CSS) is a vital tool in AI-driven drug discovery for identifying molecular substructures linked to specific biological properties. However, the exponential complexity of searching large graph databases often renders traditional methods impractical. We present Corgi, a novel framework that utilizes summarized graph views and a multi-view search strategy to achieve significant performance gains. Corgi delivers up to a 48.6x speedup and a 198x reduction in memory usage while maintaining high precision, offering a scalable solution for modern molecular databases.
The Challenge of Correlated Subgraph Search
In drug discovery, molecules are typically modeled as graphs where atoms are nodes and chemical bonds are edges. A Correlated Subgraph Search (CSS) aims to find substructures in a database that are highly correlated with a query molecule's properties, a process essential for virtual screening and predicting drug-drug interactions.
The fundamental challenge is the exponential complexity of the search space; for a graph with $n$ nodes, there are $O(2^n)$ possible subgraphs. Furthermore, correlation does not follow the "downward closure" property used in frequent pattern mining—a large correlated subgraph does not imply its components are also correlated. As molecular databases grow to hundreds of thousands of entries, existing CSS methods become prohibitively slow and memory-intensive.
The Corgi Framework
Corgi addresses these bottlenecks through a two-phase approach designed to reduce the search space without sacrificing accuracy:
- Summarized Graph View (Offline Phase): Corgi exploits the structural redundancy in molecular databases by "folding" frequently occurring node pairs (atom-bond-atom motifs) into single abstracted nodes. This drastically reduces the average size of graphs in the database while preserving underlying connectivity.
- Multi-viewed Top-k (MvTk) Search (Online Phase): Instead of searching the original complex database, Corgi runs the search on multiple different "summarized" versions. This generates a set of candidate subgraphs rapidly. These candidates are then "unfolded" back to their original structures to calculate exact Pearson correlations and filter out false positives.
A key theoretical breakthrough of Corgi is the proof that by using a sufficient number of random summarized views, the system can bound the probability of missing a true top-k result to a user-defined threshold (e.g., $\epsilon = 0.05$).
Experimental Evaluation and Results
The researchers evaluated Corgi using 12 public molecular databases, including NCI, ZINC20, DUD-E, and LIT-PCBA. These datasets represent real-world challenges with varied graph sizes and long-tail distributions.
Corgi demonstrated an average speedup of 29.8x over state-of-the-art CSS methods, reaching up to 48.6x in specific tests. Beyond speed, Corgi’s memory footprint is up to 198x lower than competitors because it operates on abstracted, smaller graph representations. In a practical case study for the ADORA2A receptor, Corgi identified 43 out of 50 active proteins, significantly outperforming existing baselines in both precision and processing time.
Scalability and Insights
Corgi turns structural complexity into an advantage. While previous algorithms struggle as molecules become more complex, Corgi identifies and collapses redundant substructures to keep the search space manageable. Crucially, Corgi demonstrates nearly linear scalability relative to the number of graphs ($N$) in the database.
This efficiency extends to pre-computation; the offline summarization phase takes less than 90 seconds even for databases containing over 300,000 molecules.
Limitations and Future Work
While highly effective for standard drug-like molecules (typically with fewer than 65 nodes), Corgi's computational cost may increase if average graph sizes exceed 200 nodes. Future research will explore "informed folding" mechanisms based on chemical domain knowledge—such as specifically folding known functional groups—to further enhance the quality and accuracy of the summarized views.
Summary updated