# Deep Learning and Spectral Embedding for Graph Partitioning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 32 references that are in the map.
- First posted on arXiv 16 Oct 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [GAP: Generalizable Approximate Graph Partitioning Framework](https://mlsanity.com/paper/1903.00614/) (2019)
- [Preconditioned Spectral Clustering for Stochastic Block Partition Streaming Graph Challenge](https://mlsanity.com/paper/1708.07481/) (2017)

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

- [SEMPART: Self-supervised Multi-resolution Partitioning of Image Semantics](https://mlsanity.com/paper/2309.10972/) (2023)
- [Agglomeration of Polygonal Grids using Graph Neural Networks with applications to Multigrid solvers](https://mlsanity.com/paper/2210.17457/) (2022)
- [Factorization-in-Loop: Proximal Fill-in Minimization for Sparse Matrix Reordering](https://mlsanity.com/paper/2511.09093/) (2025)
- [Bridging the Gap between Sparse Matrix Reordering and Factorization: A Deep Learning Framework for Fill-in Reduction](https://mlsanity.com/paper/2605.17339/) (2026)
- [Self-Supervised Learning for Sparse Matrix Reordering](https://mlsanity.com/paper/2605.17403/) (2026)

## Abstract (arXiv)

We present a graph bisection and partitioning algorithm based on graph neural networks. For each node in the graph, the network outputs probabilities for each of the partitions. The graph neural network consists of two modules: an embedding phase and a partitioning phase. The embedding phase is trained first by minimizing a loss function inspired by spectral graph theory. The partitioning module is trained through a loss function that corresponds to the expected value of the normalized cut. Both parts of the neural network rely on SAGE convolutional layers and graph coarsening using heavy edge matching. The multilevel structure of the neural network is inspired by the multigrid algorithm. Our approach generalizes very well to bigger graphs and has partition quality comparable to METIS, Scotch and spectral partitioning, with shorter runtime compared to METIS and spectral partitioning.