Distributed Maximal Independent Set Computation in Hundred Billion-Edge Graphs

Abstract

An independent set of an undirected graph is a subset of vertices where no two vertices included in the set are neighbors. A Maximal Independent Set (MIS) of a graph is an independent set such that no additional vertices can be added to the set without violating the requirements of an independent set. To support modern large graphs, parallel MIS algorithms and their multi-core, GPU, and distributed memory implementations have attracted widespread research interests in recent years. We present a distributed MIS solution to support applications that demand high throughput and scalability. Our solution is designed to support various randomized priority assignment techniques and to compute MIS in a fully asynchronous or round-synchronous manner, the latter is required by some priority assignment techniques. Our MPI-based prototype attains strong scaling by way of multilevel load-balanced graph partitioning, accelerates distributed processing through computationcommunication overlap and message prioritization, and produces deterministic results. We demonstrate scalability using massive datasets: e.g., a real-world web graph with 128 billion edges and 512 compute nodes (16 K CPU-cores), and competitiveness of our solution through empirical comparisons: our implementation comfortably outperforms both CombBLAS-MIS and AGM-MIS, and identifies MIS' of size comparable to those of the key parallel and distributed solutions found in the literature.