Scalable, Multi-Constraint, Complex-Objective Graph Partitioning

George M. Slota, Cameron Root, Karen Devine, Kamesh Madduri, Sivasankaran Rajamanickam

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


We introduce XtraPuLP, a distributed-memory graph partitioner designed to process irregular trillion-edge graphs. XtraPuLP is based on the scalable label propagation community detection technique, which has been demonstrated in various prior works as a viable means to produce high quality partitions of skewed and small-world graphs with minimal computation time. Our XtraPuLP implementation can also be generalized to compute partitions with an arbitrary number of constraints, and it can compute partitions with balanced communication load across all parts. On a collection of large sparse graphs, we show that XtraPuLP partitioning is considerably faster than state-of-the-art partitioning methods, while also demonstrating that XtraPuLP can produce partitions of real-world graphs with billion+ vertices and over a hundred billion edges in minutes. Additionally, we demonstrate XtraPuLP on a variety of applications, including large-scale graph analytics and sparse matrix-vector multiplication.

Original languageEnglish (US)
Article number9115834
Pages (from-to)2789-2801
Number of pages13
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number12
StatePublished - Dec 1 2020

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Scalable, Multi-Constraint, Complex-Objective Graph Partitioning'. Together they form a unique fingerprint.

Cite this