GSAP: A GPU-Accelerated Stochastic Graph Partitioner

Graph partitioning is essential for understanding the structure of a dataset, such as social networks and web pages. Among various graph partitioners, stochastic block partitioning (SBP) has shown promise in handling complex graphs with varying community sizes or strong intra-community connections. However, the sequential nature of the Monte Carlo Markov Chain iterations and the stochastic proposal generation process limit the efficiency and scalability of SBP. To overcome this limitation, this paper introduces GSAP, a GPU-accelerated stochastic graph partitioner, to enhance the runtime performance of SBP. We propose a parallel algorithm to speed up the generation process of stochastic proposals on GPU. Additionally, we accelerate the calculation of the minimal description length by dividing the formulation into several independent computations. To achieve better performance, we introduce an efficient blockmodel update algorithm to dynamically manage the blockmodel matrix on GPU. Our experimental results on the 2022 HPEC GraphChallenge dataset demonstrate that GSAP can achieve up to 12.3 × and 60.9 × runtime speedup on a single A4000 GPU compared to two CPU-parallel state-of-the-art SBP algorithms.