# Neural Algorithmic Reasoning for Combinatorial Optimisation

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 58 references that are in the map.
- First posted on arXiv 18 May 2023.

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

- [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)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [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)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [A Gentle Introduction to Deep Learning for Graphs](https://mlsanity.com/paper/1912.12693/) (2019)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Learning the Travelling Salesperson Problem Requires Rethinking Generalization](https://mlsanity.com/paper/2006.07054/) (2020)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [A Generalist Neural Algorithmic Learner](https://mlsanity.com/paper/2209.11142/) (2022)
- [Graph Neural Networks are Dynamic Programmers](https://mlsanity.com/paper/2203.15544/) (2022)
- [Pointer Graph Networks](https://mlsanity.com/paper/2006.06380/) (2020)
- [Relational inductive bias for physical construction in humans and machines](https://mlsanity.com/paper/1806.01203/) (2018)
- [Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks](https://mlsanity.com/paper/2211.00692/) (2022)
- [How to transfer algorithmic reasoning knowledge to learn new algorithms?](https://mlsanity.com/paper/2110.14056/) (2021)
- [Neural Algorithmic Reasoners are Implicit Planners](https://mlsanity.com/paper/2110.05442/) (2021)
- [Dual Algorithmic Reasoning](https://mlsanity.com/paper/2302.04496/) (2023)
- [XLVIN: eXecuted Latent Value Iteration Nets](https://mlsanity.com/paper/2010.13146/) (2020)
- [A (Slightly) Improved Approximation Algorithm for Metric TSP](https://mlsanity.com/paper/2007.01409/) (2020)
- [Persistent Message Passing](https://mlsanity.com/paper/2103.01043/) (2021)
- [Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time](https://mlsanity.com/paper/1704.02844/) (2017)

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

- [GraphArena: Evaluating and Exploring Large Language Models on Graph Computation](https://mlsanity.com/paper/2407.00379/) (2024)
- [Simulation of Graph Algorithms with Looped Transformers](https://mlsanity.com/paper/2402.01107/) (2024)
- [The CLRS-Text Algorithmic Reasoning Language Benchmark](https://mlsanity.com/paper/2406.04229/) (2024)
- [Transformers meet Neural Algorithmic Reasoners](https://mlsanity.com/paper/2406.09308/) (2024)
- [SALSA-CLRS: A Sparse and Scalable Benchmark for Algorithmic Reasoning](https://mlsanity.com/paper/2309.12253/) (2023)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [Primal-Dual Neural Algorithmic Reasoning](https://mlsanity.com/paper/2505.24067/) (2025)
- [Benchmarking ChatGPT on Algorithmic Reasoning](https://mlsanity.com/paper/2404.03441/) (2024)
- [Recurrent Aggregators in Neural Algorithmic Reasoning](https://mlsanity.com/paper/2409.07154/) (2024)
- [Neural Algorithmic Reasoning with Multiple Correct Solutions](https://mlsanity.com/paper/2409.06953/) (2024)
- [NAR-*ICP: Neural Execution of Classical ICP-based Pointcloud Registration Algorithms](https://mlsanity.com/paper/2410.11031/) (2024)
- [KNARsack: Teaching Neural Algorithmic Reasoners to Solve Pseudo-Polynomial Problems](https://mlsanity.com/paper/2509.15239/) (2025)
- [A Denoising Diffusion-Based Evolutionary Algorithm Framework: Application to the Maximum Independent Set Problem](https://mlsanity.com/paper/2510.08627/) (2025)
- [HATSolver: Learning Groebner Bases with Hierarchical Attention Transformers](https://mlsanity.com/paper/2512.14722/) (2025)
- [AlphaZeroES: Direct score maximization outperforms planning loss minimization](https://mlsanity.com/paper/2406.08687/) (2024)
- [Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization](https://mlsanity.com/paper/2502.19377/) (2025)
- [Learning Repetition-Invariant Representations for Polymer Informatics](https://mlsanity.com/paper/2505.10726/) (2025)
- [Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning](https://mlsanity.com/paper/2509.18930/) (2025)
- [Statistical Guarantees for Reasoning Probes on Looped Boolean Circuits](https://mlsanity.com/paper/2602.03970/) (2026)

## Abstract (arXiv)

Solving NP-hard/complete combinatorial problems with neural networks is a challenging research area that aims to surpass classical approximate algorithms. The long-term objective is to outperform hand-designed heuristics for NP-hard/complete problems by learning to generate superior solutions solely from training data. Current neural-based methods for solving CO problems often overlook the inherent "algorithmic" nature of the problems. In contrast, heuristics designed for CO problems, e.g. TSP, frequently leverage well-established algorithms, such as those for finding the minimum spanning tree. In this paper, we propose leveraging recent advancements in neural algorithmic reasoning to improve the learning of CO problems. Specifically, we suggest pre-training our neural model on relevant algorithms before training it on CO instances. Our results demonstrate that by using this learning setup, we achieve superior performance compared to non-algorithmically informed deep learning models.