# Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 45 references that are in the map.
- First posted on arXiv 27 May 2022.

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

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Dueling Network Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1511.06581/) (2015)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (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)
- [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)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking](https://mlsanity.com/paper/2005.11081/) (2020)
- [Munchausen Reinforcement Learning](https://mlsanity.com/paper/2007.14430/) (2020)
- [The Transformer Network for the Traveling Salesman Problem](https://mlsanity.com/paper/2103.03012/) (2021)
- [Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time](https://mlsanity.com/paper/2006.03750/) (2020)
- [Learning Heuristics over Large Graphs via Deep Reinforcement Learning](https://mlsanity.com/paper/1903.03332/) (2019)
- [Reinforcement Learning Enhanced Quantum-inspired Algorithm for Combinatorial Optimization](https://mlsanity.com/paper/2002.04676/) (2020)

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

- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2406.01661/) (2024)
- [One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction](https://mlsanity.com/paper/2208.10227/) (2022)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [Memory-Enhanced Neural Solvers for Routing Problems](https://mlsanity.com/paper/2406.16424/) (2024)
- [A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization](https://mlsanity.com/paper/2406.11897/) (2024)
- [Unveiling the Limits of Learned Local Search Heuristics: Are You the Mightiest of the Meek?](https://mlsanity.com/paper/2310.19990/) (2023)
- [Nonlocal Monte Carlo via Reinforcement Learning](https://mlsanity.com/paper/2508.10520/) (2025)
- [Large Neighborhood Search meets Iterative Neural Constraint Heuristics](https://mlsanity.com/paper/2603.20801/) (2026)
- [Partitioning Distributed Compute Jobs with Reinforcement Learning and Graph Neural Networks](https://mlsanity.com/paper/2301.13799/) (2023)
- [Enabling Population-Based Architectures for Neural Combinatorial Optimization](https://mlsanity.com/paper/2601.08696/) (2026)
- [Test-Time Adaptation for Unsupervised Combinatorial Optimization](https://mlsanity.com/paper/2601.21048/) (2026)
- [Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization](https://mlsanity.com/paper/2602.20376/) (2026)
- [Blocked Gibbs meets Diffusion Transformers: Unsupervised Learning for Constraint Optimization](https://mlsanity.com/paper/2605.25129/) (2026)

## Abstract (arXiv)

From logistics to the natural sciences, combinatorial optimisation on graphs underpins numerous real-world applications. Reinforcement learning (RL) has shown particular promise in this setting as it can adapt to specific problem structures and does not require pre-solved instances for these, often NP-hard, problems. However, state-of-the-art (SOTA) approaches typically suffer from severe scalability issues, primarily due to their reliance on expensive graph neural networks (GNNs) at each decision step. We introduce ECORD; a novel RL algorithm that alleviates this expense by restricting the GNN to a single pre-processing step, before entering a fast-acting exploratory phase directed by a recurrent unit. Experimentally, ECORD achieves a new SOTA for RL algorithms on the Maximum Cut problem, whilst also providing orders of magnitude improvement in speed and scalability. Compared to the nearest competitor, ECORD reduces the optimality gap by up to 73% on 500 vertex graphs with a decreased wall-clock time. Moreover, ECORD retains strong performance when generalising to larger graphs with up to 10000 vertices.