GTSM: A multi-edge-centric temporal subgraph matching framework on GPUs
Jiezhong He, Menghan Jia, Yixin Chen, Zhouyang Liu, Dongsheng Li · ACM Transactions on Architecture and Code Optimization · 2025
Temporal subgraph matching aims to identify subgraphs in temporal networks that satisfy both structural and temporal constraints, with applications ranging from social network analysis to fraud detection. As this NP-hard problem involves massive computation on large graphs, GPU acceleration becomes critical. However, existing edge-centric approaches suffer from computational redundancy, inefficient memory management, and limited scalability on large graphs, hindering efficient GPU acceleration. To address these challenges, we propose GTSM, 1 a GPU-optimized temporal subgraph matching system featuring three innovations: (1) A multi-edge-centric paradigm that reduces redundant search space through multi-edge compressions along with an efficient decompression algorithm; (2) A memory-bound optimization that maximizes GPU resource utilization; (3) A heterogeneous BFS-DFS execution model where CPU performs Breadth-First Search (BFS) to ensure load balancing across GPUs. Experiments demonstrate that GTSM achieves a 5.5×-93.2× speedup over the state-of-the-art GPU systems, while solving 10%–40% more queries. With our heterogeneous execution model, our system achieves near-linear scaling in multi-GPU configurations.