gMatch Method Overview

논문 컨텍스트

Paper title: gMatch: Fine-Grained and Hardware-Efficient Subgraph Matching on GPUs Abstract: Subgraph matching is a core operation in graph analytics, supporting a broad spectrum of applications from social network analysis to bioinformatics. Recent GPU-based approaches accelerate subgraph matching by leveraging parallelism but rely on a coarse-grained execution model that suffers from scalability and efficiency issues due to high memory overhead and thread underutilization. In this paper, we propose gMatch, a hardware-efficient subgraph matching approach on GPUs. gMatch introduces a fine-grained execution model that reduces memory consumption and enables flexible task scheduling among threads. We further design warp-level batch exploration and lightweight load balancing to improve execution efficiency and scalability. Experiments on diverse workloads and real-world datasets show that gMatch outperforms state-of-the-art subgraph matching methods, including STMatch, T-DFS, and EGSM, in both performance and scalability. We also compare against state-of-the-art systems for mining small patterns, such as BEEP and G$^2$Miner. While these systems achieve better performance on small datasets, gMatch scales to substantially larger queries and datasets, where existing approaches degrade or fail to complete. Passages referencing this figure: licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 19, No. 8 ISSN 2150-8097. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/SJTU-Liquid/gMatch . 1. Introduction Given a query graph Q Q and a data graph G G , subgraph matching aims to find all embeddings of Q Q in G G . For example, in Figure 1 , the mapping M = { ( u 1 , v 58 ) , ( u 2 , v 57 ) , ( u 3 , v 1 ) , ( u 4 , v 60 ) } M=\{(u_{1},v_{58}),(u_{2},v_{57}),(u_{3},v_{1}),(u_{4},v_{60})\} is a valid embedding, or match , of Q Q in G G . As a fundamental operation in graph analysis, subgraph matching underpins a wide range of real-world applications, including social network recommendation (Gupta et al. , 2014 ) , fraud dete atch M M is treated as a parallel task and a warp, the basic scheduling unit on GPUs, serves as the worker. The task involves extending M M by mapping the next query vertex to valid data vertices. Based on their search strategies, these methods can be classified into two categories: breadth-first search (BFS)-based and depth-first search (DFS)-based. ((a)) Query graph Q Q . ((b)) Data graph G G . Figure 1 . Example query graph and data graph. Early approaches such as GpSM (Tran et al. , 2015 ) , GSI (Zeng et al. , 2020 ) , and cuTS (Xiang et al. , 2021 ) adopt a BFS-based search strategy, which explores the search space level by level. At each iteration, all partial matches are extended by mapping the next query vertex to candidate data vertices. This strategy enables a large number of par hs g g and g ′ g^{\prime} , a subgraph isomorphism is an injective function M : V ​ ( g ) → V ​ ( g ′ ) M:V(g)\rightarrow V(g^{\prime}) s.t. 1) ∀ v ∈ V ​ ( g ) , L ​ ( v ) = L ​ ( M ​ [ v ] ) \forall