# Scalable Edge Partitioning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Aug 2018.

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

- [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)
- [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)
- [Scaling Knowledge Graph Embedding Models](https://mlsanity.com/paper/2201.02791/) (2022)
- [SNI-GNN: SmartNIC-Assisted Full-Graph GNN Training with In-Network Embedding Prediction](https://mlsanity.com/paper/2608.06441/) (2026)

## Abstract (arXiv)

Edge-centric distributed computations have appeared as a recent technique to improve the shortcomings of think-like-a-vertex algorithms on large scale-free networks. In order to increase parallelism on this model, edge partitioning - partitioning edges into roughly equally sized blocks - has emerged as an alternative to traditional (node-based) graph partitioning. In this work, we give a distributed memory parallel algorithm to compute high-quality edge partitions in a scalable way. Our algorithm scales to networks with billions of edges, and runs efficiently on thousands of PEs. Our technique is based on a fast parallelization of split graph construction and a use of advanced node partitioning algorithms. Our extensive experiments show that our algorithm has high quality on large real-world networks and large hyperbolic random graphs, which have a power law degree distribution and are therefore specifically targeted by edge partitioning