Li Zeng’s  paper titled “SGSI: A Scalable GPU-friendly Subgraph Isomorphism Algorithm” is accepted by TKDE 2022, which accelerates the subgraph isomorphism of large-scale graphs on GPU.

Subgraph isomorphism is frequently used in fraud detection, commercial recommendation and Telecom network maintenance. Real-life graphs have billions of edges, thus the enumeration of subgraph matches is usually the bottleneck of the entire system. By modelling the GPU architectures and collaborating software and hardware, we improve the performance by >3×.

Existing GPU subgraph isomorphism algorithms are all based on 2-phase table join, and use graph partitioning to support large-scale graphs. In each round, only one partition is processed on GPU. However, for matches across several partitions, they need to perform table join of several partitions, which is rather costly. Besides, these solutions occupy too much GPU memory, which limits their scalability.

In this paper, we propose a highly scalable GPU subgraph isomorphism algorithm (SGSI). SGSI adopts a new vertex-join scheme to avoid duplicated joins, and designs PCSR structures to store edge-labelled graphs on GPU. For large-scale graphs, SGSI performs fine-grain structure division instead of graph partition, which can achieve better transportation and computation between CPU and GPU. Meanwhile, by modelling the computation resources of different levels in GPU, SGSI picks out the best strategy of load balancing. The experiments on both real and synthetic datasets prove the effectiveness of SGSI, which not only performs 3~15× faster than existing methods, but also supports billion-scale graphs efficiently.