# Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 50 references that are in the map.
- First posted on arXiv 8 Jan 2023.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [On First-Order Meta-Learning Algorithms](https://mlsanity.com/paper/1803.02999/) (2018)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (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)
- [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (2019)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [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 a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Matrix Encoding Networks for Neural Combinatorial Optimization](https://mlsanity.com/paper/2106.11113/) (2021)
- [Unsupervised Learning via Meta-Learning](https://mlsanity.com/paper/1810.02334/) (2018)
- [Graph Neural Network Guided Local Search for the Traveling Salesperson Problem](https://mlsanity.com/paper/2110.05291/) (2021)
- [Meta-Learning to Compositionally Generalize](https://mlsanity.com/paper/2106.04252/) (2021)
- [Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing](https://mlsanity.com/paper/2010.12001/) (2020)
- [Graph Neural Networks for Maximum Constraint Satisfaction](https://mlsanity.com/paper/1909.08387/) (2019)
- [Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation](https://mlsanity.com/paper/2207.05984/) (2022)
- [It's Not What Machines Can Learn, It's What We Cannot Teach](https://mlsanity.com/paper/2002.09398/) (2020)
- [Experimental performance of graph neural networks on random instances of max-cut](https://mlsanity.com/paper/1908.05767/) (2019)
- [Neural Learning of One-of-Many Solutions for Combinatorial Problems in Structured Output Spaces](https://mlsanity.com/paper/2008.11990/) (2020)
- [Local algorithms for independent sets are half-optimal](https://mlsanity.com/paper/1402.0485/) (2014)
- [Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs](https://mlsanity.com/paper/1904.02231/) (2019)

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

- [A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2406.01661/) (2024)
- [Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics](https://mlsanity.com/paper/2502.08696/) (2025)
- [Variational Annealing on Graphs for Combinatorial Optimization](https://mlsanity.com/paper/2311.14156/) (2023)
- [Controlling Continuous Relaxation for Combinatorial Optimization](https://mlsanity.com/paper/2309.16965/) (2023)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [Regularized Langevin Dynamics for Combinatorial Optimization](https://mlsanity.com/paper/2502.00277/) (2025)
- [Primal-Dual Neural Algorithmic Reasoning](https://mlsanity.com/paper/2505.24067/) (2025)
- [Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More](https://mlsanity.com/paper/2405.08424/) (2024)
- [Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling](https://mlsanity.com/paper/2409.02135/) (2024)
- [Maximum Independent Set: Self-Training through Dynamic Programming](https://mlsanity.com/paper/2310.18672/) (2023)
- [Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update](https://mlsanity.com/paper/2407.16468/) (2024)
- [Continuous Parallel Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems](https://mlsanity.com/paper/2402.02190/) (2024)
- [Game-Theoretic Co-Evolution for LLM-Based Heuristic Discovery](https://mlsanity.com/paper/2601.22896/) (2026)
- [Learning for Dynamic Combinatorial Optimization without Training Data](https://mlsanity.com/paper/2505.19497/) (2025)
- [An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem](https://mlsanity.com/paper/2408.08484/) (2024)
- [Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphs](https://mlsanity.com/paper/2505.13754/) (2025)
- [Binarizing Physics-Inspired GNNs for Combinatorial Optimization](https://mlsanity.com/paper/2507.13703/) (2025)
- [Test-Time Adaptation for Unsupervised Combinatorial Optimization](https://mlsanity.com/paper/2601.21048/) (2026)
- [UniHetCO: A Unified Heterogeneous Representation for Multi-Problem Learning in Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2603.11456/) (2026)
- [EDISCO: Equivariant DIScrete Diffusion for Euclidean Combinatorial Optimization](https://mlsanity.com/paper/2610.04953/) (2026)

## Abstract (arXiv)

A general framework of unsupervised learning for combinatorial optimization (CO) is to train a neural network (NN) whose output gives a problem solution by directly optimizing the CO objective. Albeit with some advantages over traditional solvers, the current framework optimizes an averaged performance over the distribution of historical problem instances, which misaligns with the actual goal of CO that looks for a good solution to every future encountered instance. With this observation, we propose a new objective of unsupervised learning for CO where the goal of learning is to search for good initialization for future problem instances rather than give direct solutions. We propose a meta-learning-based training pipeline for this new objective. Our method achieves good empirical performance. We observe that even just the initial solution given by our model before fine-tuning can significantly outperform the baselines under various evaluation settings including evaluation across multiple datasets, and the case with big shifts in the problem scale. The reason we conjecture is that meta-learning-based training lets the model be loosely tied to each local optima for a training instance while being more adaptive to the changes of optimization landscapes across instances.