# EmbedPart: Embedding-Driven Graph Partitioning for Scalable Graph Neural Network Training

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 57 references that are in the map.
- First posted on arXiv 1 Apr 2026.

## Builds on (most cited first, 26 of 26)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks](https://mlsanity.com/paper/1909.01315/) (2019)
- [DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs](https://mlsanity.com/paper/2010.05337/) (2020)
- [Structure-aware Interactive Graph Neural Networks for the Prediction of Protein-Ligand Binding Affinity](https://mlsanity.com/paper/2107.10670/) (2021)
- [Sampling methods for efficient training of graph convolutional networks: A survey](https://mlsanity.com/paper/2103.05872/) (2021)
- [Survey on Graph Neural Network Acceleration: An Algorithmic Perspective](https://mlsanity.com/paper/2202.04822/) (2022)
- [Relational Deep Learning: Challenges, Foundations and Next-Generation Architectures](https://mlsanity.com/paper/2506.16654/) (2025)
- [Ginex: SSD-enabled Billion-scale Graph Neural Network Training on a Single Machine via Provably Optimal In-memory Caching](https://mlsanity.com/paper/2208.09151/) (2022)
- [BRIGHT -- Graph Neural Networks in Real-Time Fraud Detection](https://mlsanity.com/paper/2205.13084/) (2022)
- [Demystifying Graph Sparsification Algorithms in Graph Properties Preservation](https://mlsanity.com/paper/2311.12314/) (2023)
- [More Recent Advances in (Hyper)Graph Partitioning](https://mlsanity.com/paper/2205.13202/) (2022)
- [Graph Neural Network Training Systems: A Performance Comparison of Full-Graph and Mini-Batch](https://mlsanity.com/paper/2406.00552/) (2024)
- [Comprehensive Evaluation of GNN Training Systems: A Data Management Perspective](https://mlsanity.com/paper/2311.13279/) (2023)
- [Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints](https://mlsanity.com/paper/2103.12594/) (2021)
- [Accelerating Sampling and Aggregation Operations in GNN Frameworks with GPU Initiated Direct Storage Accesses](https://mlsanity.com/paper/2306.16384/) (2023)
- [Out-of-Core Edge Partitioning at Linear Run-Time](https://mlsanity.com/paper/2203.12721/) (2022)
- [HongTu: Scalable Full-Graph GNN Training on Multiple GPUs (via communication-optimized CPU data offloading)](https://mlsanity.com/paper/2311.14898/) (2023)
- [DiskGNN: Bridging I/O Efficiency and Model Accuracy for Out-of-Core GNN Training](https://mlsanity.com/paper/2405.05231/) (2024)
- [Spinner: Scalable Graph Partitioning in the Cloud](https://mlsanity.com/paper/1404.3861/) (2014)
- [Partitioner Selection with EASE to Optimize Distributed Graph Processing](https://mlsanity.com/paper/2304.04976/) (2023)
- [An Experimental Comparison of Partitioning Strategies for Distributed Graph Neural Network Training](https://mlsanity.com/paper/2308.15602/) (2023)
- [Cut to Fit: Tailoring the Partitioning to the Computation](https://mlsanity.com/paper/1804.07747/) (2018)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are widely used for learning on graph-structured data, but scaling GNN training to massive graphs remains challenging. To enable scalable distributed training, graphs are divided into smaller partitions that are distributed across multiple machines such that inter-machine communication is minimized and computational load is balanced. In practice, existing partitioning approaches face a fundamental trade-off between partitioning overhead and partitioning quality. We propose EmbedPart, an embedding-driven partitioning approach that achieves both speed and quality. Instead of operating directly on irregular graph structures, EmbedPart leverages node embeddings produced during the actual GNN training workload and clusters these dense embeddings to derive a partitioning. EmbedPart achieves more than 100x speedup over Metis while maintaining competitive partitioning quality and accelerating distributed GNN training. Moreover, EmbedPart naturally supports graph updates and fast repartitioning, and can be applied to graph reordering to improve data locality and accelerate single-machine GNN training. By shifting partitioning from irregular graph structures to dense embeddings, EmbedPart enables scalable and high-quality graph data optimization.