# Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSP

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

## Key facts

- Cited by 58 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 8 Sep 2018.

## Built on by (most cited first, 30 of 58)

- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning](https://mlsanity.com/paper/2106.01086/) (2021)
- [A Survey on Neural-symbolic Learning Systems](https://mlsanity.com/paper/2111.08164/) (2021)
- [SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networks](https://mlsanity.com/paper/2207.07888/) (2022)
- [Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness](https://mlsanity.com/paper/2110.10942/) (2021)
- [Explaining the Explainers in Graph Neural Networks: a Comparative Study](https://mlsanity.com/paper/2210.15304/) (2022)
- [Link Scheduling using Graph Neural Networks](https://mlsanity.com/paper/2109.05536/) (2021)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Analytics and Machine Learning in Vehicle Routing Research](https://mlsanity.com/paper/2102.10012/) (2021)
- [An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problem](https://mlsanity.com/paper/2107.07076/) (2021)
- [Augment with Care: Contrastive Learning for Combinatorial Problems](https://mlsanity.com/paper/2202.08396/) (2022)
- [Learning Connectivity with Graph Convolutional Networks for Skeleton-based Action Recognition](https://mlsanity.com/paper/2112.03328/) (2021)
- [Annealed Training for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2207.11542/) (2022)
- [Learning to Solve Vehicle Routing Problems: A Survey](https://mlsanity.com/paper/2205.02453/) (2022)
- [A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization](https://mlsanity.com/paper/2211.03074/) (2022)
- [Graph World Model](https://mlsanity.com/paper/2507.10539/) (2025)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networks](https://mlsanity.com/paper/2104.03546/) (2021)
- [Maximizing Influence with Graph Neural Networks](https://mlsanity.com/paper/2108.04623/) (2021)
- [Generalization in Deep RL for TSP Problems via Equivariance and Local Search](https://mlsanity.com/paper/2110.03595/) (2021)
- [WISK: A Workload-aware Learned Index for Spatial Keyword Queries](https://mlsanity.com/paper/2302.14287/) (2023)
- [NN-Steiner: A Mixed Neural-algorithmic Approach for the Rectilinear Steiner Minimum Tree Problem](https://mlsanity.com/paper/2312.10589/) (2023)
- [Can Graph Neural Networks Learn to Solve MaxSAT Problem?](https://mlsanity.com/paper/2111.07568/) (2021)
- [Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networks](https://mlsanity.com/paper/2204.01366/) (2022)
- [Maximum Independent Set: Self-Training through Dynamic Programming](https://mlsanity.com/paper/2310.18672/) (2023)
- [Towards a Generic Representation of Combinatorial Problems for Learning-Based Approaches](https://mlsanity.com/paper/2403.06026/) (2024)
- [Learning to Pool in Graph Neural Networks for Extrapolation](https://mlsanity.com/paper/2106.06210/) (2021)
- [Computing Steiner Trees using Graph Neural Networks](https://mlsanity.com/paper/2108.08368/) (2021)
- [Graph Learning and Its Advancements on Large Language Models: A Holistic Survey](https://mlsanity.com/paper/2212.08966/) (2022)
- [A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks](https://mlsanity.com/paper/2406.13125/) (2024)

## Abstract (arXiv)

Graph Neural Networks (GNN) are a promising technique for bridging differential programming and combinatorial domains. GNNs employ trainable modules which can be assembled in different configurations that reflect the relational structure of each problem instance. In this paper, we show that GNNs can learn to solve, with very little supervision, the decision variant of the Traveling Salesperson Problem (TSP), a highly relevant NP-Complete problem. Our model is trained to function as an effective message-passing algorithm in which edges (embedded with their weights) communicate with vertices for a number of iterations after which the model is asked to decide whether a route with cost <C exists. We show that such a network can be trained with sets of dual examples: given the optimal tour cost C*, we produce one decision instance with target cost x% smaller and one with target cost x% larger than C*. We were able to obtain 80% accuracy training with -2%,+2% deviations, and the same trained model can generalize for more relaxed deviations with increasing performance. We also show that the model is capable of generalizing for larger problem sizes. Finally, we provide a method for predicting the optimal route cost within 2% deviation from the ground truth. In summary, our work shows that Graph Neural Networks are powerful enough to solve NP-Complete problems which combine symbolic and numeric data.