HistCore: Scalable $k$-Core Decomposition on GPUs with Locality-Aware Computation

A $k$-core is a maximal subgraph in which every vertex has degree at least $k$. As a basic task in complex network analysis, $k$-core decomposition reveals the nested sequence of all $k$-cores of an input graph for $k=1,2, \ldots, k_{\text {max }}$. As real-world graphs continue to grow in size and complexity, high-performance algorithms have become increasingly important. Recent works have leveraged single GPU to accelerate this task via a global peeling process, achieving excellent performance. However, the level-by-level peeling process suffers from limited scalability due to the long k-core sequence in real-world graphs, not only underutilizing the growing GPU compute power, but also struggling to process ever-growing graphs in multi-GPU settings due to frequent synchronization. In this paper, we exploit the inherent locality of $k$-core to propose a scalable GPU-based $k$-core decomposition framework that scales nearly linearly with single-GPU compute power and efficiently supports multi-GPU processing. Technically, we design a redundancy-free, GPU-friendly locality-aware $k$-core algorithm and then propose a local subgraph convergence mechanism to further reduce multi-GPU synchronization overhead. Our evaluation on an NVIDIA RTX PRO 6000 Blackwell GPU shows that HistCore outperforms recent single-GPU methods by 3.7× on average. On up to four RTX 3090 Ti GPUs, HistCore achieves an average speedup of $\text{1 6. 3} \times$ over NVIDIA's cuGraph and successfully processes all 8 billion-edge graphs.