# Connected by Construction: Learning Tractable Near-Tour Marginals for Traveling Salesman Problems

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 25 references that are in the map.
- First posted on arXiv 13 Jul 2026.

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

- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Deep Equilibrium Models](https://mlsanity.com/paper/1909.01377/) (2019)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Efficient and Modular Implicit Differentiation](https://mlsanity.com/paper/2105.15183/) (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)
- [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)
- [Gradient Estimation with Stochastic Softmax Tricks](https://mlsanity.com/paper/2006.08063/) (2020)
- [Unsupervised Learning for Solving the Travelling Salesman Problem](https://mlsanity.com/paper/2303.10538/) (2023)
- [Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization](https://mlsanity.com/paper/2502.02941/) (2025)
- [What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization](https://mlsanity.com/paper/2201.10494/) (2022)
- [Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems](https://mlsanity.com/paper/2406.03503/) (2024)
- [An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem](https://mlsanity.com/paper/1506.07776/) (2015)
- [Learning Lagrangian Multipliers for the Travelling Salesman Problem](https://mlsanity.com/paper/2312.14836/) (2023)
- [Graph Neural Networks are Heuristics](https://mlsanity.com/paper/2601.13465/) (2026)

## Abstract (arXiv)

Learning-based methods for the traveling salesman problem (TSP) are often evaluated through the tours produced after decoding or search, but the learned object itself frequently lives in a surrogate space such as heatmaps, assignments, construction policies, or search-guidance scores. This hides the fundamental question: what Hamiltonian structure has actually been learned before decoding? In this study, we directly answer this question by learning TSP through a structurally meaningful latent object, rather than leaving most of the Hamiltonian structure to the final decoding stage. Based on a connected-by-construction rooted 1-tree Gibbs family, we propose an end-to-end unsupervised learning pipeline called C2TSP. The pipeline learns residual edge perturbations from unbiased TSP cost through implicit differentiation. For structural correction, a smoothed Held--Karp layer restores expected degree balance, while certificate-guided sharpening further pushes the connected distribution toward more tour-like structures. Experiments show that C2TSP yields strong decoding performance while preserving interpretable structural information. Ablations further verify that edge perturbation and certificate-guided sharpening jointly improve both tour cost and tour-like structure.