Efficient GPU-Accelerated Local Subgraph Counting

Abstract

Local subgraph counting computes the exact number of occurrences of a query graph around every vertex in a data graph. By capturing local higher-order structure, it supports extensive applications in network analysis and graph learning. The fastest existing method, SCOPE, accelerates counting through query graph decomposition, but it is designed for single-threaded CPU execution. As a result, it struggles on large graphs and cannot take advantage of modern GPU hardware. A naïve GPU adaptation is also ineffective: as the number of parallel GPU threads grows, the memory footprint of their intermediate results quickly drains the device memory. We develop a high-performance GPU solution for local subgraph counting that preserves SCOPE's tree-decomposition framework while explicitly resolving the tension between massive GPU parallelism and limited device memory. Our approach compresses the intermediate join-and-aggregate results and proposes an insert-failure restart mechanism that guarantees correctness under bounded memory. We further design a key-mapping strategy that enables lock-free hash tables for higher throughput, eventually integrating these components into a complete GPU execution framework capable of handling arbitrarily complex queries. Experiments show that our GPU-accelerated method achieves up to a 35× speedup over a multi-threaded SCOPE implementation, reducing the processing time for a million-scale graph from days to about 20 minutes and making local subgraph counting practical at large scale.