Presentation
Δ-Motif: Subgraph Isomorphism at Scale via Data-Centric Parallelism
SessionSoftware Tools
DescriptionThe subgraph isomorphism problem—finding pattern graphs within larger data graphs—is central to many HPC applications but remains computationally challenging due to its NP-complete nature. Traditional algorithms rely on backtracking strategies that resist effective parallelization, limiting their utility on GPU architectures and large CPUs.
Motivated by quantum circuit compilation challenges, we developed a fundamentally different approach that reformulates subgraph isomorphism by representing graphs in unified tabular formats, decomposing them into fundamental building blocks called motifs, and expressing the algorithm using standard tabular operations like filters and merges. This approach, implemented through NVIDIA RAPIDS, enables massive parallelization using NVIDIA GPUs.
Our approach achieves speedups of up to 595x on a single NVIDIA H200 GPU, with many benchmarks exceeding 100x, while democratizing high-performance graph processing. Practitioners can now leverage familiar data science tools and open-source libraries to achieve efficient parallel graph analysis, making advanced subgraph isomorphism accessible to a broader community.
Motivated by quantum circuit compilation challenges, we developed a fundamentally different approach that reformulates subgraph isomorphism by representing graphs in unified tabular formats, decomposing them into fundamental building blocks called motifs, and expressing the algorithm using standard tabular operations like filters and merges. This approach, implemented through NVIDIA RAPIDS, enables massive parallelization using NVIDIA GPUs.
Our approach achieves speedups of up to 595x on a single NVIDIA H200 GPU, with many benchmarks exceeding 100x, while democratizing high-performance graph processing. Practitioners can now leverage familiar data science tools and open-source libraries to achieve efficient parallel graph analysis, making advanced subgraph isomorphism accessible to a broader community.
Event Type
Exhibitor Forum
TimeWednesday, 19 November 202510:30am - 11:00am CST
Location130
Quantum & Other Post Moore Computing Technologies