2D Distributed Label Propagation on 400 GPUs

The label propagation algorithm (LPA) is widely used for community detection, graph partitioning, and unsupervised learning, among many other problems. While appearing simple on the surface, high performance implementations of LPA are deceptively challenging to compose, particularly targeting large-scale graphs on GPUs and in distributed memory environments. We present the first widely distributed multi-GPU implementation of LPA, utilizing a novel variant of 2D distributed graph processing. Our method computes label propagation on graphs an order-of-magnitude larger than has previously been done on GPUs, while offering the fastest time-to-solution in the literature for the 128 billion edge 2012 Web Data Commons web crawl graph, the largest current public graph dataset.