# Distributed Edge Partitioning for Trillion-edge Graphs

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Aug 2019.

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

- [BGL: GPU-Efficient GNN Training by Optimizing Graph Data I/O and Preprocessing](https://mlsanity.com/paper/2112.08541/) (2021)
- [The Evolution of Distributed Systems for Graph Neural Networks and their Origin in Graph Processing and Deep Learning: A Survey](https://mlsanity.com/paper/2305.13854/) (2023)
- [An Experimental Comparison of Partitioning Strategies for Distributed Graph Neural Network Training](https://mlsanity.com/paper/2308.15602/) (2023)
- [2SFGL: A Simple And Robust Protocol For Graph-Based Fraud Detection](https://mlsanity.com/paper/2310.08335/) (2023)
- [CDFGNN: a Systematic Design of Cache-based Distributed Full-Batch Graph Neural Network Training with Communication Reduction](https://mlsanity.com/paper/2408.00232/) (2024)
- [GLISP: A Scalable GNN Learning System by Exploiting Inherent Structural Properties of Graphs](https://mlsanity.com/paper/2401.03114/) (2024)
- [Scaling Knowledge Graph Embedding Models](https://mlsanity.com/paper/2201.02791/) (2022)

## Abstract (arXiv)

We propose Distributed Neighbor Expansion (Distributed NE), a parallel and distributed graph partitioning method that can scale to trillion-edge graphs while providing high partitioning quality. Distributed NE is based on a new heuristic, called parallel expansion, where each partition is constructed in parallel by greedily expanding its edge set from a single vertex in such a way that the increase of the vertex cuts becomes local minimal. We theoretically prove that the proposed method has the upper bound in the partitioning quality. The empirical evaluation with various graphs shows that the proposed method produces higher-quality partitions than the state-of-the-art distributed graph partitioning algorithms. The performance evaluation shows that the space efficiency of the proposed method is an order-of-magnitude better than the existing algorithms, keeping its time efficiency comparable. As a result, Distributed NE can partition a trillion-edge graph using only 256 machines within 70 minutes.