# Graph Neural Networks are Heuristics

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 23 references that are in the map.
- First posted on arXiv 19 Jan 2026.

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

- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Snapshot Ensembles: Train 1, get M for free](https://mlsanity.com/paper/1704.00109/) (2017)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Unsupervised Learning for Solving the Travelling Salesman Problem](https://mlsanity.com/paper/2303.10538/) (2023)
- [Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set](https://mlsanity.com/paper/2206.13211/) (2022)
- [Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem?](https://mlsanity.com/paper/2206.01506/) (2022)
- [Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut](https://mlsanity.com/paper/2210.00623/) (2022)
- [A (Slightly) Improved Approximation Algorithm for Metric TSP](https://mlsanity.com/paper/2007.01409/) (2020)
- [Reply to: Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set](https://mlsanity.com/paper/2302.03602/) (2023)
- [Reply to: Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems](https://mlsanity.com/paper/2303.12096/) (2023)
- [Structure As Search: Unsupervised Permutation Learning for Combinatorial Optimization](https://mlsanity.com/paper/2507.04164/) (2025)

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

- [Connected by Construction: Learning Tractable Near-Tour Marginals for Traveling Salesman Problems](https://mlsanity.com/paper/2607.12127/) (2026)

## Abstract (arXiv)

Graph neural networks are usually treated as auxiliaries for combinatorial optimization: they imitate algorithms, guide search, or supply scores to classical procedures. We show that this auxiliary role is not intrinsic. A GNN can itself be a heuristic. For the Euclidean Travelling Salesman Problem, we train a non-autoregressive GNN with no labels, rewards, sequential decoding, search, or local improvement. A differentiable Hamiltonian-cycle objective is the only supervision. The trained model produces a complete tour in one forward pass, while dropout and snapshots from a single training trajectory provide solution diversity without engineered moves. The heuristic is therefore learned, not programmed. It is also fast: batched inference remains in the millisecond regime on GPUs. Experiments on TSP100, TSP200, and TSP500 show that the model consistently improves over nearest-neighbor greedy baselines. These results identify unsupervised GNNs as a class of fast learned heuristics for combinatorial optimization.