# Machine Learning-based Two-Stage Graph Sparsification for the Travelling Salesman Problem

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 41 references that are in the map.
- First posted on arXiv 22 Apr 2026.

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

- [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)
- [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)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem](https://mlsanity.com/paper/2110.07983/) (2021)
- [Generalization of Machine Learning for Problem Reduction: A Case Study on Travelling Salesman Problems](https://mlsanity.com/paper/2005.05847/) (2020)
- [Learning to Reduce Search Space for Generalizable Neural Routing Solver](https://mlsanity.com/paper/2503.03137/) (2025)
- [Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman Problems](https://mlsanity.com/paper/2207.03876/) (2022)
- [Learning to Sparsify Travelling Salesman Problem Instances](https://mlsanity.com/paper/2104.09345/) (2021)
- [Less Is More -- On the Importance of Sparsification for Transformers and Graph Neural Networks for TSP](https://mlsanity.com/paper/2403.17159/) (2024)
- [Edge Elimination in TSP Instances](https://mlsanity.com/paper/1402.7301/) (2014)
- [Dancing to the State of the Art? How Candidate Lists Influence LKH for Solving the Traveling Salesperson Problem](https://mlsanity.com/paper/2407.03927/) (2024)
- [Probabilistic Analysis of Edge Elimination for Euclidean TSP](https://mlsanity.com/paper/1809.10469/) (2018)
- [Local elimination in the traveling salesman problem](https://mlsanity.com/paper/2307.07054/) (2023)
- [Bandit based Dynamic Candidate Edge Selection in Solving Traveling Salesman Problems](https://mlsanity.com/paper/2505.15862/) (2025)

## Abstract (arXiv)

High-performance TSP solvers such as Lin-Kernighan-Helsgaun (LKH) search within a candidate graph -- a small subset of edges pre-selected for the solver -- rather than over the complete graph. The two leading sparsification heuristics, α-Nearest and POPMUSIC, each fall short of the density-coverage balance: α-Nearest is dense with stable recall, while POPMUSIC is sparser but its recall degrades with scale. Their union closes the recall gap while remaining far below the complete graph in density, leaving room for further reduction. Existing learning-based sparsifiers score edges on the complete graph, an approach that is expensive and largely limited to Euclidean instances. We propose a two-stage method that inverts this logic. Stage~1 takes the union of α-Nearest and POPMUSIC, achieving near-perfect recall at ~6N edges. Crucially, the union annotates each edge with its source provenance -- whether it was endorsed by α-Nearest, POPMUSIC, or both. Stage~2 trains a lightweight classifier on these annotated edges and prunes the lowest-scoring ones. Because dual-source edges are almost always optimal, the learning problem reduces to filtering the single-source subset -- a substantially easier task than classifying all O(N2) edges from scratch. Across four distance types, five spatial distributions, and problem sizes from 50 to 500, the pipeline reduces candidate-graph density by 37-47% while retaining ≥99.69% of optimal-tour edges, and matches or exceeds the coverage of recent Euclidean-only neural sparsifiers at lower density at TSP500.