Search papers, labs, and topics across Lattice.
This paper introduces the Anisotropic Graph Diffusion Network (AGDN), a novel Graph Neural Network framework specifically designed to address the Traveling Salesman Problem (TSP). By integrating a MixScore transition matrix that combines node similarity with pairwise distance, AGDN effectively maintains connectivity in optimal solutions while facilitating efficient information exchange through an anisotropic diffusion strategy. Experimental results demonstrate that AGDN outperforms existing methods across various instance sizes and node distributions, showcasing its robustness and computational efficiency.
AGDN not only solves the Traveling Salesman Problem more effectively but also maintains optimal connectivity in solutions that traditional methods often overlook.
The Traveling Salesman Problem (TSP) is a cornerstone of combinatorial optimization and arises in many practical scenarios. Although graph-based learning approaches have been explored for TSP, the question of how to exploit graph structure more effectively remains open. We present the Anisotropic Graph Diffusion Network (AGDN), a new Graph Neural Network framework designed to solve TSP. Our method tackles two central difficulties: (1) the lack of informative topological prior in fully connected TSP graphs, and (2) losing connected nodes in the optimal solution after the commonly used graph sparsification techniques. To overcome these issues, we construct a MixScore transition matrix that merges node similarity with pairwise distance, and we develop an anisotropic graph diffusion strategy that supports efficient information exchange across multiple hops. Comprehensive experiments spanning diverse instance sizes and node distributions show that AGDN consistently outperforms existing methods while keeping computation time competitive. Furthermore, AGDN generalizes well to problem sizes and distributions beyond those seen during training. The implementation is publicly available at: https://github.com/LabRAI/AGDN.
