Efficient Correlated Subgraph Searches for AI-powered Drug Discovery

Abstract

Correlated subgraph searches (CSSs) are essential building blocks for AI-powered drug discovery. Given a query molecule modeled as a graph, CSS finds top-k molecules correlated to the query in a database. However, the cost increases exponentially with the molecule size. Herein we present Corgi, a framework to accelerate CSS methods while ensuring top-k search accuracy. Corgi dynamically excludes unnecessary subgraphs to overcome the expensive cost without sacrificing search accuracy. Our experimental analysis confirms that Corgi has a shorter running time and improved accuracy compared to existing state-of-the-art methods, while a case study demonstrates that Corgi is suitable for practical AI-powered drug discovery.