# GAP: Generalizable Approximate Graph Partitioning Framework

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2019.

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

- [Semi-relaxed Gromov-Wasserstein divergence with applications on graphs](https://mlsanity.com/paper/2110.02753/) (2021)
- [Partition and Code: learning how to compress graphs](https://mlsanity.com/paper/2107.01952/) (2021)
- [Mask-GVAE: Blind Denoising Graphs via Partition](https://mlsanity.com/paper/2102.04228/) (2021)
- [Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networks](https://mlsanity.com/paper/2104.03546/) (2021)
- [Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling](https://mlsanity.com/paper/2409.02135/) (2024)
- [Reheated Gradient-based Discrete Sampling for Combinatorial Optimization](https://mlsanity.com/paper/2503.04047/) (2025)
- [Deep Learning and Spectral Embedding for Graph Partitioning](https://mlsanity.com/paper/2110.08614/) (2021)
- [Multi-Factor Spatio-Temporal Prediction based on Graph Decomposition Learning](https://mlsanity.com/paper/2310.10374/) (2023)
- [NeuroCUT: A Neural Approach for Robust Graph Partitioning](https://mlsanity.com/paper/2310.11787/) (2023)
- [Robust Heuristic Algorithm Design with LLMs](https://mlsanity.com/paper/2510.08755/) (2025)
- [Robust Regularized Locality Preserving Indexing for Fiedler Vector Estimation](https://mlsanity.com/paper/2107.12070/) (2021)
- [VLSI Hypergraph Partitioning with Deep Learning](https://mlsanity.com/paper/2409.01387/) (2024)
- [Trading off Quality for Efficiency of Community Detection: An Inductive Method across Graphs](https://mlsanity.com/paper/2209.14825/) (2022)
- [Solving the Kidney-Exchange Problem via Graph Neural Networks with No Supervision](https://mlsanity.com/paper/2304.09975/) (2023)
- [GIMM: InfoMin-Max for Automated Graph Contrastive Learning](https://mlsanity.com/paper/2305.17437/) (2023)
- [Efficient Partitioning Method of Large-Scale Public Safety Spatio-Temporal Data based on Information Loss Constraints](https://mlsanity.com/paper/2306.12857/) (2023)
- [NodeNAS: Node-Specific Graph Neural Architecture Search for Out-of-Distribution Generalization](https://mlsanity.com/paper/2503.02448/) (2025)
- [AdaSTORM: Scaling LLM Reasoning on Dynamic Graphs via Adaptive Spatio-Temporal Multi-Agent Collaboration](https://mlsanity.com/paper/2606.16328/) (2026)
- [Relational Compression: A Framework for Relational Fidelity in Constrained Representations](https://mlsanity.com/paper/2609.31816/) (2026)

## Abstract (arXiv)

Graph partitioning is the problem of dividing the nodes of a graph into balanced partitions while minimizing the edge cut across the partitions. Due to its combinatorial nature, many approximate solutions have been developed, including variants of multi-level methods and spectral clustering. We propose GAP, a Generalizable Approximate Partitioning framework that takes a deep learning approach to graph partitioning. We define a differentiable loss function that represents the partitioning objective and use backpropagation to optimize the network parameters. Unlike baselines that redo the optimization per graph, GAP is capable of generalization, allowing us to train models that produce performant partitions at inference time, even on unseen graphs. Furthermore, because we learn the representation of the graph while jointly optimizing for the partitioning loss function, GAP can be easily tuned for a variety of graph structures. We evaluate the performance of GAP on graphs of varying sizes and structures, including graphs of widely used machine learning models (e.g., ResNet, VGG, and Inception-V3), scale-free graphs, and random graphs. We show that GAP achieves competitive partitions while being up to 100 times faster than the baseline and generalizes to unseen graphs.