ExCC: External Memory Connected Components on Large Graphs

Abstract

Connected Components (CC) is a foundational primitive in graph analytics, yet scaling it to billion-edge graphs on GPUs remains challenging as real-world graphs exceed GPU capacity. A naïve solution to oversubscribe GPU memory is UVM. However, UVM triggers excessive page faults under the irregular access patterns, while out-of-GPU-memory frameworks either introduce significant preprocessing overhead or suffer from random-access I/O bottlenecks. We present ExCC, an external-memory CC algorithm that keeps the full graph in host-pinned RAM and streams edge batches to the GPU through a three-phase pipeline of union-find merging. ExCC achieves predictable sequential I/O behavior across all phases, demonstrating average speedups of 1.98x over UVM, 4.03x over Subway, and 2.81x over EMOGI on billion-scale graphs.