Abstract:
Graph pattern mining (GPM), as a crucial method for the analysis of the graph data, has been widely applied in various domains such as knowledge graphs, financial networks, and bioinformatics analysis. However, compared to traditional graph analysis algorithms, GPM algorithms exhibit higher computational complexity, which limits the capability of existing methods to handle large-scale graphs. As a widely adopted high-performance accelerator, the GPU has garnered significant attention in field of graph pattern mining. Moreover, the performance of the GPU hardware continues to advance rapidly. GPM systems leverage the high parallelism and high bandwidth of GPUs to enable efficient mining of large-scale graphs, while facing three main challenges: 1) efficient graph data storage and access, 2) parallelization of graph computation, and 3) load balancing. Nevertheless, existing surveys in related areas tend to focus either on specific GPM algorithms or on GPU-based graph computing systems, leaving a gap in the systematic review of emerging GPU-accelerated GPM systems. To address this gap, this paper provides a comprehensive survey of such systems. Firstly, we analyze their hardware architecture and workflow, followed by a discussion of graph storage optimizations, including efficient graph data structure design, intermediate result storage optimization, and graph partitioning. Secondly, we summarize graph computational optimization techniques, covering parallel set intersection and search pruning strategies. Thirdly, we examine load balancing methods such as work stealing, straggler abortion, and workload scheduling policies. Finally, this paper outlines the current challenges and suggests future research directions, with the aim of supporting and guiding subsequent studies and system designs.