# Partitioning Trillion-edge Graphs in Minutes

arXiv: https://arxiv.org/abs/1610.07220 · HTML: https://mlsanity.com/paper/1610.07220/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2016.

## Built on by (most cited first, 3 of 3)

- [More Recent Advances in (Hyper)Graph Partitioning](https://mlsanity.com/paper/2205.13202/) (2022)
- [An Experimental Comparison of Partitioning Strategies for Distributed Graph Neural Network Training](https://mlsanity.com/paper/2308.15602/) (2023)
- [GLISP: A Scalable GNN Learning System by Exploiting Inherent Structural Properties of Graphs](https://mlsanity.com/paper/2401.03114/) (2024)

## Abstract (arXiv)

We introduce XtraPuLP, a new distributed-memory graph partitioner designed to process trillion-edge graphs. XtraPuLP is based on the scalable label propagation community detection technique, which has been demonstrated as a viable means to produce high quality partitions with minimal computation time. On a collection of large sparse graphs, we show that XtraPuLP partitioning quality is comparable to state-of-the-art partitioning methods. We also demonstrate that XtraPuLP can produce partitions of real-world graphs with billion+ vertices in minutes. Further, we show that using XtraPuLP partitions for distributed-memory graph analytics leads to significant end-to-end execution time reduction.