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

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 obscures a basic question: which Hamiltonian structures can a model represent and learn tractably, and how does learning them directly lead to better tours? In this study, we directly answer this question by learning a structurally meaningful latent object for TSP, 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 the penalty-free 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 learns interpretable, tour-like structure, and ablations verify that edge perturbation and certificate-guided sharpening jointly improve both this structure and the tour cost. C2TSP also yields strong decoding performance, transfers zero-shot to metric non-Euclidean instances, and remains robust as a candidate source for the LKH heuristic.