Zicang Xu’s paper BUG: Balanced DFS-Based Subgraph Matching with a Reuse Strategy on GPUs was accepted by GraphChallenge 2025.

Subgraph matching is a fundamental problem in graph analysis with wide-ranging applications in domains such as bioinformatics, fraud detection, social networks, and recommendation systems. Despite extensive optimization efforts on CPU platforms, the NP-hard nature of subgraph matching limits the performance, especially on large-scale datasets. Leveraging the massive parallelism and high memory bandwidth of GPUs offers significant acceleration potential. However, existing GPU-based solutions face key challenges. BFS-based approaches suffer from excessive memory consumption due to the exponential growth of partial matches, while more DFS-based methods, though memory-efficient, struggle with severe load imbalance and inefficient computation reuse.

In this work, we propose two complementary strategies to address these issues. First, we introduce a work-offload mechanism that dynamically balances workload across warps using a global task queue, significantly improving resource utilization. Second, we employ a combination of symmetry breaking and a reuse strategy to reduce redundant set intersections during the enumeration process. The experiment results show that these strategies significantly improve the performance of subgraph matching on GPUs.