SCIENCE@home

SIGMo: High-Throughput Batched Subgraph Isomorphism on GPUs for Molecular Matching

Antonio De Caro,G. Cordasco,F. Ficarelli,Biagio Cosenza

Published 2025 in International Conference on Software Composition

ABSTRACT

Subgraph isomorphism is a fundamental graph problem with applications in diverse domains from biology to social network analysis. Of particular interest is molecular matching, which uses a subgraph isomorphism formulation for the drug discovery process. While subgraph isomorphism is known to be NP-complete and computationally expensive, in the molecular matching formulation a number of domain constraints allow for efficient implementations. This paper presents SIGMo, a high-throughput, portable subgraph isomorphism framework for GPUs, specifically designed for batch molecular matching. SIGMo takes advantage of the specific domain formulation to provide a more efficient filter-and-join strategy: the framework introduces a novel multi-level iterative filtering technique based on neighborhood signature encoding to efficiently prune candidates prior to a GPU-optimized join phase using a stack-based DFS traversal. The GPU implementation is written in SYCL, allowing portable execution on AMD, Intel, and NVIDIA GPUs. Our experimental evaluation on a large dataset from ZINC demonstrates up to 1470 × speedup over state-of-the-art subgraph isomorphism frameworks, and achieves a throughput of 7.7 billion matches per second on a cluster with 256 GPUs.

PUBLICATION RECORD

  • Publication year

    2025

  • Venue

    International Conference on Software Composition

  • Publication date

    2025-11-15

  • Fields of study

    Biology, Computer Science

  • Identifiers
    DOI 10.1145/3712285.3759782
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-47 of 47 references · Page 1 of 1

CITED BY