MERCURY: Efficient Subgraph Matching on GPUs with Hybrid Scheduling

Subgraph matching finds all distinct subgraphs in the given data graph <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$G$</tex> that are isomorphic to the pattern graph <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$P$</tex>. It is widely used in social networks, chemoinformatics, recommendation systems, anomaly detection, and network security. Unfortunately, subgraph matching is an NP problem with a huge search space that can quickly exhaust computational resources and requires materializing a large number of intermediate results. Even with GPU acceleration, the processing time for subgraph matching tasks on large graphs often fails to meet the needs of real-world applications. Previous systems use coarse-grained thread-mapping strategies and static configuration for symmetry breaking rules and intersection kernels, which lose the opportunity to exploit the fine-grained parallelism of GPUs. In this paper, we first discuss different optimization variants from three aspects:(i) symmetry breaking, (ii) thread-mapping and (iii) intersection kernel, then we propose a novel hybrid scheduling strategy to combine these optimization variants. Based on this scheduling, we developed MERCURY to enable load-balanced and efficient subgraph matching on GPUs. Experiments show that MERCURY outperforms TRUST, SMOG, and H-INDEX up to 3.92×, 19.7×, and 21.6×, respectively, in triangle counting. For general pattern matching tasks, it is up to 52.4× faster than G<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>Miner, and can scale up to 1024 GPU cards.