Saturn: High Performance Graph Pattern Mining System on Multi-GPU platform

Graph pattern mining, as a core task for analyzing entity relationships, finds extensive applications in fields such as community detection and drug discovery. However, due to its non-polynomial time complexity, large-scale graph processing encounters challenges related to search space explosion and low computational efficiency. Existing GPU-accelerated solutions utilize parallel computing to enhance performance but often suffer from thread idleness caused by the power-law distribution of graph data and excessive CPU intervention in multi-GPU communication, which impede the full utilization of hardware capabilities. This paper presents Saturn, a GPU-based graph pattern mining system, which overcomes the above bottlenecks through computation-communication co-optimization. At computation level, Saturn decouples the loading and querying phases of set operations, employs fine-grained parallel batch processing to dynamically adapt hash and binary search algorithms, and optimizes memory access efficiency via shared memory caching, significantly improving thread utilization. At communication level, it establishes a CPU-free GPU communication model, leveraging high-bandwidth NVLink interconnect and unified memory mechanism for direct cross-device data access, while reducing redundant transmission and link contention through vertex caching and message aggregation scheduling. Experimental results demonstrate that Saturn outperforms state-of-the-art GPU-based graph mining systems on real-world datasets, achieving superior computational parallel efficiency and cross-device communication effectiveness for large-scale graph pattern mining tasks.