BUG: Balanced DFS-Based Subgraph Matching with a ReUse Strategy on GPUs

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 experiments on real-world and synthetic datasets demonstrate that our approach achieves up to a 25.59× speedup compared to prior works.