# Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networks

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 63 references that are in the map.
- First posted on arXiv 8 Apr 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [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)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSP](https://mlsanity.com/paper/1809.02721/) (2018)
- [Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time](https://mlsanity.com/paper/2006.03750/) (2020)
- [Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem](https://mlsanity.com/paper/2012.04461/) (2020)
- [GAP: Generalizable Approximate Graph Partitioning Framework](https://mlsanity.com/paper/1903.00614/) (2019)
- [A State Aggregation Approach for Solving Knapsack Problem with Deep Reinforcement Learning](https://mlsanity.com/paper/2004.12117/) (2020)

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

- [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)
- [A Survey of AI Methods for Geometry Preparation and Mesh Generation in Engineering Simulation](https://mlsanity.com/paper/2512.23719/) (2025)
- [RIDGECUT: Learning Graph Partitioning with Rings and Wedges](https://mlsanity.com/paper/2505.13986/) (2025)
- [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)
- [Learning Fill-in Reduction Ordering via Graph Policy Optimization for Sparse Matrices](https://mlsanity.com/paper/2605.17362/) (2026)
- [Self-Supervised Learning for Sparse Matrix Reordering](https://mlsanity.com/paper/2605.17403/) (2026)

## Abstract (arXiv)

We present a novel method for graph partitioning, based on reinforcement learning and graph convolutional neural networks. Our approach is to recursively partition coarser representations of a given graph. The neural network is implemented using SAGE graph convolution layers, and trained using an advantage actor critic (A2C) agent. We present two variants, one for finding an edge separator that minimizes the normalized cut or quotient cut, and one that finds a small vertex separator. The vertex separators are then used to construct a nested dissection ordering to permute a sparse matrix so that its triangular factorization will incur less fill-in. The partitioning quality is compared with partitions obtained using METIS and SCOTCH, and the nested dissection ordering is evaluated in the sparse solver SuperLU. Our results show that the proposed method achieves similar partitioning quality as METIS and SCOTCH. Furthermore, the method generalizes across different classes of graphs, and works well on a variety of graphs from the SuiteSparse sparse matrix collection.