arXiv:2606.19185v1 [cs.LG] 17 Jun 2026
AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network Bolin Shen∗
Ziwei Huang
Florida State University Tallahassee, United States [email protected]
Singapore Management University Singapore [email protected]
Zhiguang Cao
Yushun Dong†
Singapore Management University Singapore [email protected]
Florida State University Tallahassee, United States [email protected]
Abstract 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.
CCS Concepts • Theory of computation → Shortest paths; • Computing methodologies → Neural networks.
Keywords Traveling Salesman Problem, Graph Neural Networks ACM Reference Format: Bolin Shen, Ziwei Huang, Zhiguang Cao, and Yushun Dong. 2026. AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network. In Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD 2026), August 9–13, ∗ This work was done while the author was at Singapore Management University. † Corresponding author.
This work is licensed under a Creative Commons Attribution 4.0 International License. KDD 2026, Jeju Island, Republic of Korea. © 2026 Copyright held by the owner/author(s). ACM ISBN 979-8-4007-2259-2/2026/08 https://doi.org/10.1145/3770855.3817789
2026, Jeju Island, Republic of Korea. ACM, New York, NY, USA, 12 pages. https://doi.org/10.1145/3770855.3817789
Resource Availability: The source code of this paper has been made publicly available at https: //doi.org/10.5281/zenodo.20496880.
1
Introduction
The Traveling Salesman Problem (TSP) is a well-known combinatorial optimization problem [39] with widespread applications such as circuit design [37] and vehicle routing [15]. The objective of a given TSP (referred to as a TSP instance) is to find the shortest possible route that visits a specified set of cities once and returns to the starting point. Accordingly, the search space of TSP is often modeled as a fully connected graph (i.e., a TSP graph) spanning across different cities [22, 35]. Numerous classic methods have already been proposed to handle TSP [4, 31]. However, these methods typically face challenges such as high computational costs [48] and heavy manual efforts [12, 64]. In recent years, learning-based methods [21, 33, 38, 40, 45, 69] have emerged as a promising alternative, where Graph Neural Networks (GNNs) [36, 56] have proven particularly effective [35, 50, 53, 72, 73] due to their natural alignment with TSP’s topological search space. However, the volume of a TSP’s search space grows exponential w.r.t. the total number of nodes. As a consequence, sparsifying the TSP graph is often necessary for the current learning methods to reduce the search space and improve efficiency [44]. Nevertheless, such a sparsification process may remove certain edges that exist in the underlying optimal solution. In these cases, while the nodes originally connected by these edges may still be higher-order neighbors, their relationship becomes much more difficult for the commonly used shallow GNNs to capture [36, 56]. Therefore, this sparsification mechanism widely used by the current methods can severely jeopardize the learning performance. Meanwhile, although stacking multiple convolutional layers can capture multi-hop information, such an approach often leads to other severe issues such as over-smoothing [9, 11, 51, 52] and over-squashing [3, 17, 26, 54]. Despite the critical limitation of the current sparsification mechanism, only limited studies have discussed such an issue [64] or proposed mechanisms to mitigate it [44], leaving the problem of losing edges in the underlying optimal solution unsolved.
KDD 2026, August 9–13, 2026, Jeju Island, Republic of Korea.
Despite the significance of such an issue, it is non-trivial to handle and we mainly face two fundamental challenges: (1) Lack of an Informative Topological Prior: Unlike classical graph learning problems that benefit from the topological prior of the input graph data [29, 56, 65], the TSP graph is often modeled as a fully connected graph without any prior knowledge about the optimal topology [22, 35, 53]. Such a limitation undermines the capability for the model to capture the solution-relevant information from topology, thereby jeopardizing the quality of learned node representations. (2) Lack of Information Exchange: Sparsification may disconnect node pairs that are connected in the optimal solution. If such a situation occurs, the optimal node pairs might still be connected through multi-hop neighbors. However, capturing multihop information is challenging [3, 11, 51]. Therefore, it is crucial to maintain direct connections to efficiently exchange information [2, 57]. An even worse scenario may arise when the optimal node pairs are divided into completely different disconnected graph components. In such a case, graph convolution fails to propagate information between these components [46], jeopardizing information exchange between the optimal node pairs and ultimately affecting the expressiveness of the node embeddings. Therefore, using graph learning to tackle TSP bears pressing challenges and related explorations remain nascent. To handle the challenges above, in this paper, we propose a novel framework named Anisotropic Graph Diffusion Network (AGDN) for solving TSP. Specifically, we first propose the design of MixScore transition matrix, which simultaneously considers node similarity and pairwise distance information as priors, rather than simply treating the TSP graph as a fully connected graph. Such an approach provides an informative topological prior as the input for our graph learning-based framework and thus effectively handles the challenge of lack of an informative topological prior. Subsequently, we introduced Graph Diffusion with Multi-hop Attention, which contains learnable parameters to control the weight of each hop. This enables immediate access to higher-order neighbor information within a single convolution layer. At its core, we adopted the concept of anisotropy, which separates information propagation for each node into incoming and outgoing directions to improve the characterizing granularity of information flow between nodes [7]. Such designs effectively address the critical challenge of lack of information exchange. We summarize our contributions below. Contributions. Our contributions can be summarized as threefold: • Problem Characterization. We pinpoint fundamental limitations in current GNN approaches for TSP, specifically highlighting how graph sparsification disconnects optimal node pairs and how existing methods struggle with multi-hop information propagation in fully connected TSP graphs. • Algorithmic Design. We introduces a novel principled framework AGDN, which combines a novel MixScore transition matrix incorporating structural priors with an anisotropic graph diffusion mechanism that efficiently propagates information bidirectionally through learnable multi-hop attention. • Empirical Evaluations. Extensive empirical evaluations demonstrate strong effectiveness and efficiency in solving TSP, while also exhibiting robust generalization across varying problem sizes, node distributions, and real-world datasets.
Bolin Shen, Ziwei Huang, Zhiguang Cao, and Yushun Dong
2 Preliminary 2.1 Notations Throughout this paper, we adopt the following notational conventions: bold uppercase letters (e.g., 𝑾 ) are used to denote matrices, bold lowercase letters (e.g., 𝒉) are used to denote vectors, and regular lowercase letters (e.g., 𝑑) are used to represent scalars. 𝒉𝑖 is used to represent the 𝑖-th element in a given vector 𝒉. We use a vector (e.g., 𝒉) as the subscript of a function parameterized by it, e.g., 𝑓𝒉 . In this paper, we focus on the two-dimensional plane Euclidean Traveling Salesman Problem, i.e., nodes are positioned in a twodimensional Euclidean space. We define the search space for a TSP instance as a fully connected graph G = (V, E), where each 𝒗 ∈ V is a two-dimensional vector representing the node coordinates in a two-dimensional space (𝒗 ∈ [0, 1] 2 ). 𝑒𝑖 𝑗 ∈ E is the Euclidean distance between node 𝑖 and node 𝑗 in the two-dimensional space.
2.2
Traveling Salesman Problem
The Traveling Salesman Problem is a combinatorial optimization problem in which a salesman is required to visit 𝑛 cities exactly once and return to the starting city while minimizing the total travel distance. TSP can be formulated as 𝑛 ∑︁ min 𝑑𝜋 (𝑖 ),𝜋 (𝑖+1) , 𝜋 ∈Π𝑛
𝑖=1
where Π𝑛 is the set of all possible permutations of the cities, 𝜋 represents a specific tour permutation, and 𝑑𝜋 (𝑖 ),𝜋 (𝑖+1) is the distance between two consecutive cities 𝑖 and 𝑖 + 1 in the tour. The objective is to find an optimal tour 𝜋 ∗ that minimizes the total travel distance.
2.3
Graph Diffusion Operation
In this paper, we mainly focus on the graph diffusion operations designed with a solid mathematical foundation in Spectral Graph Theory [14]. In particular, we define graph diffusion using a generalized diffusion matrix: ∞ ∑︁ 𝑭 = 𝜽𝑘 𝑻 𝑘 , 𝑘=0
where 𝑭 is the diffusion matrix, 𝜽 represents the weight controlling the contribution of diffusion steps, and 𝑻 denotes the transition matrix, which represents the graph structure. To ensure the convergence of the diffusion matrix, constraints are often imposed on the Í∞ weight coefficients, i.e., 𝑘=0 𝜽𝑘 = 1, where 𝜽𝑘 ∈ [0, 1]. Additionally, 𝑻 should satisfy the condition that its eigenvalue 𝜆𝑖 ∈ [0, 1] and it is a stochastic matrix [61]. When 𝑲 approaches infinity, the elements of matrix 𝑭 converge. 𝑭 represents the global dependencies of the graph. A graph learning model that leverages 𝑭 for propagating graph features is a spectral-based graph diffusion network, where a well-known example is Graph Diffusion Convolution [25].
3 Methodology 3.1 Overview In this section, we introduce our framework Anisotropic Graph Diffusion Network (AGDN) designed for addressing TSP without compromising to the traditional sparsification process. We first introduce a modified transition matrix different from the commonly
AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network
KDD 2026, August 9–13, 2026, Jeju Island, Republic of Korea.
S(ource) space Cities
MCTS On Heatmap
mijS
2D Coordinate
MixScore
Node Embedding
Graph Diffusion with Multi-hop Attention
D(estination) space
TSP Objective: find an optimal solution
Pairwise Distance
One TSP instance
mijD mikD Distance Matrix
MixScore
Graph Diffusion with Multi-hop Attention
Self-Attention & Aggregation
Position Encoding
mikS
Heatmap
Find Optimal Solution
Figure 1: Overview of the proposed AGDN framework. Given a fully connected graph representing a TSP instance, we first construct a distancebased transition matrix that encodes edge-wise transition probabilities. We then compute a novel structural descriptor, MixScore, by jointly considering node features and transition information. MixScore is integrated into the diffusion process to obtain propagated node embeddings. To incorporate directional awareness, we introduce an anisotropic information propagation mechanism that guides embedding updates based on directionality. The resulting directional embeddings are used to generate a heatmap over the graph, which reflects the likelihood of edge participation in the optimal tour. Finally, we employ Monte Carlo Tree Search over the heatmap to identify the optimal TSP solution.
used ones [36], which describes the transition probability of each node based on distances. Next, we propose MixScore, which combines node and transition information to capture the structural information of the entire graph. Then we integrate MixScore with the graph diffusion process to obtain the propagated node embeddings. At the same time, we introduce directional information propagation process, which we refer to as the anisotropic mechanism. Finally, the directional node embeddings are aggregated and utilized for generating heatmaps and identify the optimal TSP solution.
3.2
MixScore Transition Matrix
We first propose a transition matrix based on pairwise node distances. Specifically, we notice that if a sparsified adjacency matrix is used for propagating graph information, it inevitably results in disconnected components [44], preventing information from being transmitted across these components. To avoid such an issue, we utilize a fully connected transition matrix to characterize the graph structure. We first compute the pairwise distance for each element in the set E, where 𝑒𝑖 𝑗 represents the distance between node 𝑖 and node 𝑗. Transition matrix 𝑻 is computed as 𝑒 𝑖𝑗 𝑻𝑖 𝑗 = exp − , 𝜎 where 𝜎 is a scaling parameter that controls the sensitivity of the kernel. For smaller values of 𝜎, transition probabilities between distant points remain significant. In contrast, larger 𝜎 values cause these probabilities to diminish rapidly, emphasizing local interactions. Compared to traditional transition matrices based on degree, our transition matrix is calculated using pairwise distance. Since we lack a graph structure, distance effectively captures the transition trend, where closer distances indicate higher probabilities. Additionally, to ensure the convergence of the diffusion matrix as
the diffusion steps approaches infinity, we propose to normalize the transition matrix with 𝑻rw = 𝑫 −1 𝑻 . Based on the design of our transition matrix, we further propose a novel MixScore transition matrix, which encodes both node similarity information and distance information. Specifically, we utilize the widely adopted information propagation mechanism to ensure that neighboring nodes can access the information from each other. Notably, to achieve higher granularity in the learned node embeddings, we propose to learn and maintain node embeddings separately from both incoming and outgoing directions. Here, information from the incoming direction is represented in the S space, and similarly, information from the outgoing direction is represented in the D space. We first map the two-dimensional node coordinates into a higher dimensional latent space using positional encoding [55] to obtain node embeddings 𝑯 ∈ R𝑛×𝑑 . Subsequently, two multi-layer perceptron (MLP) models, 𝑔𝜽S𝑠 and 𝑔𝜽D , are used to 𝑑 project 𝑯 into two different spaces to obtain 𝑯 S and 𝑯 D . Mathematically, node embeddings in 𝑯 S and 𝑯 D are given as 𝑯 S = 𝑔𝜽S𝑠 (𝑯 ), and 𝑯 D = 𝑔𝜽D𝑑 (𝑯 ),
(1)
where 𝑔𝜽S𝑠 and 𝑔𝜽D are parameterized by learnable parameter 𝜽𝑠 𝑑 and 𝜽𝑑 , respectively. This process helps us obtain anisotropic node embeddings, where the information in the two spaces can be learned separately. On the basis of this, we propose to utilize the node embeddings from both directions to define MixScore transition matrix. Here, our intuition is to characterize the propagation of node information from both directions. Therefore, we propose to integrate 𝑯 S , 𝑯 D , and 𝑻rw together. We captured the similarity between any two points by computing the inner product of 𝑯𝑆 and 𝑯𝐷 , while 𝑻𝑟 𝑤 described the transition probability between them. By integrating these two complementary perspectives, we effectively characterized the overall graph structure. We further
KDD 2026, August 9–13, 2026, Jeju Island, Republic of Korea.
Bolin Shen, Ziwei Huang, Zhiguang Cao, and Yushun Dong
propose to use an MLP model 𝑓𝝎 to transform the integration to the space of the MixScore transition matrix. Mathematically, we propose to formulate MixScore transition matrix as ⊤ 𝑴 S = Softmax(ℎ𝜸 ((𝑯 S 𝑯 D )∥𝑻rw )) 𝑎𝑛𝑑 (2a) ⊤ 𝑴 D = Softmax(ℎ𝜸 ((𝑯 D 𝑯 S⊤ )∥𝑻rw )), (2b) where ∥ is the concatenation operator, and ℎ𝜸 denotes an MLP model parameterized by 𝜸 . With the proposed MixScore transition matrix, we are able to encode information from both directions centered on each node into one matrix to characterize the information exchange on the TSP graph effectively.
3.3
Anisotropic Graph Diffusion
We now propose to use MixScore as the transition matrix in the graph diffusion operation to better extract information from the TSP graph. Specifically, the mathematical formulation of the proposed anisotropic graph diffusion is given as GDMHA(𝜽, 𝑴, 𝑯 ) =
𝐾 ∑︁
𝜽𝑘 𝑴 𝑯 .
(3)
𝑘=0
Here we propose to adopt 𝜽𝑘 as the multi-hop attention score, which is initialized with a PageRank-based importance score, i.e., 𝜽𝑘 = 𝛼 (1−𝛼)𝑘 , where 𝛼 is a tunable hyper-parameter. 𝐾 denotes the total number of diffusion steps. Such a design integrated with graph diffusion operation and multi-hop attention mechanism enables us to effectively capture information from multiple hops away for each node in the TSP graph. Based on such a design, we further propose Anisotropic Graph Diffusion, which enables the information to propagate simultaneously in both incoming and outgoing directions for each node. With this design, we are able to characterize the information propagation with higher granularity and thus enhances the model’s ability to capture intricate node relationships. Specifically, the mathematical formulation of the proposed Anisotropic Graph Diffusion is given as 𝑯ˆ S = GDMHA(𝜽 S , 𝑴 S , 𝑯 S ) and
(4a)
𝑯ˆ D = GDMHA(𝜽 D , 𝑴 D , 𝑯 D ),
(4b)
where the information encoded in the incoming and outgoing directions is separately learned in the S and D spaces, respectively. We then obtain 𝑯ˆ S and 𝑯ˆ D in their respective spaces after information propagation. To summarize, the proposed Anisotropic Graph Diffusion enables the model to capture information from the TSP graph by learning embeddings based on information from separated directions together with the multi-hop attention mechanism.
3.4
Node Information Aggregation
To obtain final node embeddings, we propose aggregating the information encoded in the node embeddings from both S and D spaces. To enable each space to focus on the most relevant features from the other, we propose to adopt the self-attention mechanism [55], using 𝑯ˆ S as the query and 𝑯ˆ D as both the key and the value. ′ is given as Mathematically, the updated embedding 𝑯 D ′ 𝑯D = Softmax
! ⊤ 𝑯ˆ S 𝑯ˆ D 𝑯ˆ D . √ 𝑑𝑘
(5)
Finally, we aggregate information from the two independent spaces 𝑯ˆ S and 𝑯ˆ D by using ′ 𝑯˜ = 𝑓𝝓 ( 𝑯ˆ S ∥𝑯 D ),
(6)
where 𝑓𝝓 is an MLP parameterized by 𝝓. Such an asymmetrical node information aggregation between the two spaces empirically helps to reduce the instability and effectively integrates the information from the two distinct spaces.
3.5
Solution Identification and Optimization
We finally introduce how to utilize the aggregated node embeddings 𝑯˜ to obtain the predicted optimal solution to the given TSP problem and conduct the learning optimization. Here, our intuition is to first model edge embeddings between any pair of nodes in the TSP graph based on the learned 𝑯˜ . Then we utilize an attention mechanism to enhance focus on certain specific edges. Finally, we utilize an MLP model to transform the edge embeddings into a predicted heatmap, which highlights the potential routes that involve the optimal route with high probability. Based on such a heatmap, the widely used traditional solvers such as Monte Carlo Tree Search (MCTS) [8] can be guided to search for an optimal route efficiently. Our first step here is to obtain the edge embeddings with the learned 𝑯˜ . Specifically, we propose to construct a set of matrices Eemb = {𝑬 (1) , 𝑬 (1) , ..., 𝑬 (𝑑 ) }, where the 𝑖-th matrix encodes the values at the 𝑖-th dimension of all 𝑛 2 edge embeddings. We propose to model each 𝑬 (𝑖 ) as 𝑬 (𝑖 ) = 𝑯˜ :,𝑖 𝑯˜ :,𝑖⊤ (1 ≤ 𝑖 ≤ 𝑑),
(7)
where 𝑯˜ :,𝑖 is used to denote the 𝑖-th column of the obtained node embedding matrix 𝑯˜ . Our intuition here is to encode pairwise node similarity information to capture their complex relationships in the given TSP graph. We then propose to utilize an edge-level attention mechanism to re-weight each matrix in the constructed set Eemb , so that the edges between certain pair of nodes can be highlighted out of the 𝑛 2 entries to provide better guidance for the proposed model. Specifically, we propose to formulate the attention matrix as 𝑯˜ 𝑯˜ ⊤ 𝑬 attn = Softmax √ , (8) 𝑑𝑘 where 𝑬 attn ∈ R𝑁 ×𝑁 is the matrix of the learned edge-level attention score, which helps quantify the significance of edges based on the latent relationships between nodes. Next, utilize 𝑬 attn to obtain the set of new edge embeddings highlighted by the learned edge-level attention scores. Mathematically, the new edge embedding set is Ẽemb = { 𝑬˜ (1) , 𝑬˜ (1) , ..., 𝑬˜ (𝑑 ) }, where 𝑬˜ (𝑖 ) = 𝑬 (𝑖 ) ⊙ 𝑬 attn (1 ≤ 𝑖 ≤ 𝑑) and ⊙ is the Hadamard product operator. Finally, we construct an 𝑛 × 𝑛 × 𝑑 three-dimensional tensor by stacking all 𝑑 matrices in Ẽemb together. In this three-dimensional tensor, the vector along the third dimension at position (𝑖, 𝑗) on the slice denotes the 𝑑-dimensional embeddings of the edges connecting the 𝑖-th and 𝑗-th node. We propose to utilize an MLP model to perform a binary classification on the existence of each edge in the underlying optimal route, and we construct an 𝑛 × 𝑛 heatmap 𝑨ˆ with the predicted positive probability at each edge.
AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network
Note that we focus on both supervised learning and unsupervised learning settings for model optimization. In supervised learning settings, we directly take the routes yielded by the common solvers [4] as the optimal solution, and then we build a heatmap 𝑨 according to the edges presented in the identified optimal solution. To optimize the model, we utilize the widely adopted cross entropy loss to minimize the difference between the output heatmap 𝑨ˆ and the heatmap 𝑨 built based on the optimal solution. In unsupervised learning settings, we follow the common settings in this domain [47] to minimize the summation of the output 𝑨ˆ with the (𝑖, 𝑗) entry being re-weighted by the corresponding distance value 𝑒𝑖,𝑗 . Here, the intuition is to minimize the average distance between all pairs of nodes with the output probabilities of edge existence, and we introduce details in Appendix. In both cases, the output heatmap 𝑨ˆ highlights the critical edges likely to appear in the optimal solution, and we follow the common settings to utilize common solvers to obtain the optimal routes. Specifically, we extracted the value at the second position of the model’s output heatmap logits as our heatmap. Subsequently, for each heatmap, we retained the top 𝑘 largest values in each row as input for MCTS. The parameters for MCTS were fully configured according to the settings in [47].
4
Theoretical Analysis
In this section, we explore the proposed anisotropic mechanism and the MixScore transition matrix, which together significantly enhance multi-hop neighbor communication for solving the TSP. Building on prior work [7], where the diffusion distance between 1/2 Í nodes is defined as 𝑑𝑡 (𝑥, 𝑦) := 𝑧 ∈ V (𝑞𝑡 (𝑥, 𝑧) − 𝑞𝑡 (𝑦, 𝑧)) 2 , we extend this notion to incorporate our anisotropic diffusion framework through the following definitions. Definition 4.1 (Anisotropic MixScore Diffusion Distance). Let 𝑴 S , 𝑴 D ∈ R | V | × | V | denote the two direction MixScore transition matrices, respectively. For each node 𝑥 ∈ V, define the 𝑘-step transi𝑴 tion distribution from 𝑥 to 𝑧 as 𝑞𝑘 S , and similarly for node 𝑦 ∈ V, 𝑴
define the 𝑘-step transition distribution from 𝑦 to 𝑧 as 𝑞𝑘 D . Then the anisotropic MixScore diffusion distance between nodes 𝑥 and 𝑦 after 𝑘 steps is defined as: ! 2 1/2 ∑︁ 𝑴 𝑴D 𝑴 S 𝑑𝑘 (𝑥, 𝑦) := 𝑞𝑘 (𝑥, 𝑧) − 𝑞𝑘 (𝑦, 𝑧) . 𝑧∈V
This proposition characterizes the diffusion distance induced by directional MixScore matrices, denoted as 𝑴 S and 𝑴 D , capturing information propagation along distinct directions. Further inspired by [7], we generalize the notion of gradient steps to a bi-directional setting and introduce the following definition: Definition 4.2 (Anisotropic Gradient Step). Let 𝑥, 𝑦, 𝑧 ∈ V be nodes such that 𝑧 is a common neighbor of both 𝑥 and 𝑦, and let 𝜙 ∈ R | V | be its first non-trivial left eigenvector. Suppose 𝑴 S and 𝑴 D are defined as in Equation 2. We say that 𝑥 takes a forward gradient step toward 𝑧 under 𝑴 S if 𝜙 (𝑧)−𝜙 (𝑥) is maximized among the neighbors of 𝑥, and that 𝑦 takes a backward gradient step toward 𝑧 under 𝑴 D if 𝜙 (𝑧) − 𝜙 (𝑦) is maximized among the neighbors of 𝑦. Then, performing both updates simultaneously defines an anisotropic gradient step toward 𝑧, yielding updated nodes (𝑥 ′, 𝑦 ′ ).
KDD 2026, August 9–13, 2026, Jeju Island, Republic of Korea.
Then we arrive at the following theorem, which demonstrates that simultaneous gradient descent along both directions leads to a contraction in diffusion distance: Theorem 4.3 (Anisotropic Gradient Step Reduces Diffusion Distance). Let 𝑥, 𝑦, 𝑧 ∈ V be nodes such that 𝜙 (𝑥) < 𝜙 (𝑧) and 𝜙 (𝑦) < 𝜙 (𝑧), and let (𝑥 ′, 𝑦 ′ ) be the result of performing a bidirectional gradient step toward 𝑧 as defined in Proposition 4.2. Then there exists a constant 𝐶 > 0 such that for all 𝑡 ≥ 𝐶, the diffusion distance satisfies: 𝑑𝑘𝑴 (𝑥 ′, 𝑦 ′ ) < 𝑑𝑘𝑴 (𝑥, 𝑦), where 𝑑𝑘𝑴 (·, ·) denotes the diffusion distance under the MixScore transition matrix 𝑴 S and 𝑴 D . This result highlights the effectiveness of our anisotropic graph diffusion mechanism. By integrating direction-specific MixScore matrices, the framework facilitates faster and more robust longrange information aggregation, especially on large-scale TSP instances, thereby validating the effectiveness of our proposed method. We provide a detailed proof in the Appendix A.
5
Experiments
In this section, we aim to evaluate the performance of AGDN with extensive experiments. Specifically, we focus on the three research questions below. RQ1: How effective is the Anisotropic Graph Diffusion Network (AGDN) in solving the TSP? RQ2: How efficient is the AGDN when applied to solve TSP? RQ3: What is the generalization performance of AGDN across different problem sizes, diverse node distributions and real-world datasets?
5.1
Experimental Setup
In this subsection, we outline the most representative settings, and details about implementations can be found in Appendix. Learning Paradigms. We focus on two types of learning paradigms that are commonly studied in TSPs: (1) Supervised Learning: we first utilize a solver to generate optimal solutions and subsequently derive a ground truth heatmap based on the resulting route. The objective is to predict a heatmap that represents the probability of each edge being an optimal edge, which is then used to guide the Monte Carlo Tree Search (MCTS) [8] in generating the final path prediction; (2) Unsupervised Learning: Unlike the supervised approach, this paradigm does not rely on a solver to pre-compute the optimal solution for each TSP instance. Instead, we directly calculate the distance between all pairs of nodes re-weighted by the probabilities of edge existence and minimize the average distance between all node pairs. Baselines. There are four main categories for solving TSPs: operations research (OR) [32], reinforcement learning, supervised learning, and unsupervised learning. For each of these mainstream, we select the most representative works as our baselines. For OR methods, we adopt the widely used Concorde [4] and LKH [31] to solve the problems and derive optimal solutions. For reinforcement learning approaches, we adopt AM [38], POMO [40], and DIMES [50], both of which employ the REINFORCE algorithm [60] as a backbone. In the Supervised Learning category, we compare against GatedGCN [35], which is the first to propose using graphs for solving TSP; Att-GCN [22], which concatenates heatmaps to
KDD 2026, August 9–13, 2026, Jeju Island, Republic of Korea.
Bolin Shen, Ziwei Huang, Zhiguang Cao, and Yushun Dong
Table 1: Performance comparison under different TSPs with the number of nodes being 200, 500, and 1000, respectively. RL, SL, UL, G, AS, and BS denotes Reinforcement Learning, Supervised Learning, Unsupervised Learning, Greedy Search, Active Search, and Beam Search, respectively. ↓ indicates the lower, the better. All results from AGDN are in Bold. Note that we were unable to reproduce the model of [53] under the setting SL+MCTS, a situation also mentioned in [62]. Accordingly, we use N/A to indicate that the code or experimental settings cannot be reproduced, and there are no results available for reference.
TSP-200 TSP-500 TSP-1000 Length ↓ Gap ↓ Time ↓ Length ↓ Gap ↓ Time ↓ Length ↓ Gap ↓ Time ↓
Method
Type
Concorde LKH-3
Exact Heuristics
10.7 10.7
0.00% 3.44m -0.14% 2.01m
16.6 16.6
0.00% 37.7m 0.00% 11.4m
23.1 23.1
0.00% 6.65h 0.00% 38.1h
AM RL+G POMO+EAS-Emb RL+AS+G POMO+EAS-Tab RL+AS+G DIMES RL+G DIMES RL+AS+G
N/A N/A N/A N/A N/A
N/A N/A N/A N/A N/A
N/A N/A N/A N/A N/A
20.0 19.2 24.5 18.9 17.8
21.0% 16.3% 48.2% 14.4% 7.61%
1.51m 12.8h 11.6h 0.97m 2.10h
31.2 N/A 49.6 26.6 24.9
34.8% N/A 114% 15.0% 7.74%
GatedGCN GatedGCN Att-GCN DIFUSCO AGDN(Ours)
SL+BS SL+MCTS SL+MCTS SL+MCTS SL+MCTS
16.2 10.7 10.7 N/A 10.7
51.0% 0.21% 0.16% N/A 0.06%
4.63m 0.52s 20.6s N/A 1.77s
30.4 16.8 17.0 16.6 16.7
83.6% 38.0m 1.28% 1.46s 2.54% 2.20m 0.46% 10.1m 0.74% 2.30s
51.3 24.8 23.9 23.4 23.4
121% 51.7m 7.26% 4.96s 3.22% 4.10m 1.17% 24.5m 1.28% 2.40s
Position UTSP AGDN(Ours)
SoftDist+MCTS UL+MCTS UL+MCTS
N/A 10.7 10.7
N/A N/A 0.09% 0.78s 0.05% 0.66s
16.8 16.7 16.7
1.44% 0.00s 0.84% 0.85s 0.64% 0.64s
23.6 23.4 23.3
2.20% 0.00s 1.18% 1.82s 0.96% 0.97s
enable predictions on TSP of arbitrary sizes; and DIFUSCO [53], the first diffusion-based model for TSP. In the Unsupervised Learning category, we compared against Position [62] and UTSP [47]. Datasets. Our experiments focus on the widely studied two dimensional Euclidean TSP. The dataset used in this study was derived from the work of [22], including 1 million training instances and 10,000 test instances for TSP-100. And for TSP-200, TSP-500, and TSP-1000, the dataset includes 3,000 training instances and 128 test instances for each problem size. Additionally, these datasets were utilized for the experiments on size generalization. For the distribution generalization experiments, we follow the settings in [21], whose dataset is widely used to evaluate model performance under different node distributions, including Uniform, Cluster, Explosion, and Implosion. We selected test instances from these four distributions for evaluation on TSP-100 and TSP-1000. Metrics. We evaluate the model based on two commonly studied dimensions [38]. (1) Effectiveness: Length represents the length of the optimal solution, with smaller values indicating better performance. To provide a more intuitive understanding of the gap between the near-optimal and optimal solutions, we adopt the Gap metric, which quantifies the relative difference between the predicted route length and the optimal solution, which is given as Gap = (Predicted Length − Optimal Length)/Optimal Length × 100%. Such a metric directly reflects the quality of the identified solution in comparison to the optimal solution. (2) Efficiency: Time represents the duration required for the model’s inference process. Additionally, we will discuss the number of learnable parameters
3.18m N/A 63.5h 2.08m 4.49h
in the model. Overall, we consider a model to be more efficient if it requires less inference time and utilizes fewer parameters.
5.2
Effectiveness Evaluation for AGDN
To answer RQ1, we conduct experiments on TSP problems of three different sizes to evaluate the effectiveness of AGDN. Specifically, we focus on approaches that integrate heatmap generation with Monte Carlo Tree Search (MCTS) [8]. This combination has demonstrated superior performance in prior studies [62]. To evaluate the effectiveness of the model, we analyze its performance in both Supervised Learning and Unsupervised Learning frameworks table 1. (1) In supervised learning, AGDN achieved the shortest paths in most cases, resulting in the lowest gap relative to the optimal solution. The exception is DIFUSCO [53], where the validation issue of the results is widely reported [62]. Compared to the widely used GatedGCN with MCTS method, our approach achieved improvements of 71%, 42%, and 82% across different problem sizes, respectively. This demonstrates that our method indeed generates higher-quality heatmaps, further proving its effectiveness. (2) In the unsupervised learning framework, AGDN demonstrates consistent performance improvements. Compared to the state-of-the-art model, UTSP [47], our approach achieves enhancements of 44%, 24%, and 26% on TSP200, TSP-500, and TSP-1000, respectively. Since both methods adopt the MCTS algorithm for path searching and use exact same search strategy as UTSP, the impact of the search process can be excluded. These results further demonstrate that AGDN is capable of generating higher-quality heatmaps, reaffirming its effectiveness and its
AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network
KDD 2026, August 9–13, 2026, Jeju Island, Republic of Korea.
Table 2: Performance comparison under different TSP sizes including TSP-200, TSP-500, and TSP-1000.
TSP-200 TSP-500 TSP-1000 Length ↓ Gap ↓ Time ↓ Length ↓ Gap ↓ Time ↓ Length ↓ Gap ↓ Time ↓
Method
Type
Concorde LKH-3
Exact Heuristics
GatedGCN SL+MCT AGDN(Our) SL+MCT
10.7 10.7
0.00% 3.44m -0.14% 2.01m
16.6 16.6
0.00% 37.7m 0.00% 11.4m
23.1 23.1
0.00% 6.65h 0.00% 38.1m
10.8 10.7
0.26% 0.53s 0.17% 1.73s
16.7 16.7
1.16% 1.47s 0.87% 2.33s
25.9 23.4
12.1% 5.00s 1.28% 2.40s
Table 3: Performance comparison under different node distributions.
0 20 40 60 80
Rows
Rows
0 20 40 60 80
0
20 40 60 80 Columns
0 20 40 60 80 Columns
(a) Sparsification Result
(b) MixScore by AGDN
1.0 0.8 0.6 0.4 0.2 0.0
applicability in unsupervised settings. From fig. 2, we observe that the adjacency matrix obtained after the traditional sparsification mechanism (collected from GateGCN) contains only binary elements, while MixScore effectively learn continuous weights across all node pairs, which helps achieve better performance.
Inference Time (s)
Parameters (×1e6)
1.5
2.0
GatedGCN (Params) AGDN (Params) GatedGCN (Inference Time) AGDN (Inference Time)
1.8 1.5 1.2
1.0
1.0
0.5 0
0.8 5
10
15
Hops
20
25
0.5
Figure 3: Efficiency comparison between AGDN and GatedGCN under different number of hops for information aggregation. We observe that AGDN demonstrates clear superiority in both total number of parameters and inference time.
5.3
Efficiency Evaluation for AGDN
To answer RQ2, we conducted experiments to compare the efficiency between the proposed AGDN and one of the most representative graph learning-based baselines, GateGCN. We note that that one layer of GatedGCN and one diffusion step in the proposed
Uniform
Cluster
Method
TSP-100
TSP-1000
TSP-100
TSP-1000
LEHD BQ-NCO INViT-2V INViT-3V GCN-MCT
0.57% 5.90% 1.65% 0.95% 0.00%
2.76% 3.91% 6.15% 5.99% 2.04%
4.51% 8.86% 3.12% 2.47% 0.01%
13.7% 19.2% 9.32% 8.63% 2.10%
AGDN
0.00%
1.44%
0.01%
2.17%
Distri
Figure 2: We compare structure information bwteen GatedGCN and AGDN. (a) is derived from GatedGCN, showing the sparsified result obtained through 𝑘-NN; while (b) is leaned by AGDN. AGDN exhibits better capability to capture the graph structure.
2.0
Distri
Explosion
Implosion
Method
TSP-100
TSP-1000
TSP-100
TSP-1000
LEHD BQ-NCO INViT-2V INViT-3V GCN-MCT
0.68% 6.41% 1.85% 1.12% 0.00%
5.99% 7.21% 9.11% 8.57% 2.87%
1.17% 6.40% 1.95% 1.12% 0.00%
4.25% 5.43% 6.63% 6.35% 3.18%
AGDN
0.00%
2.60%
0.00%
2.47%
AGDN enable them to capture information from one-hop farther away for each node in the TSP graph. To ensure fair comparison, we propose to compare efficiency on TSP-200 in cases where 5, 10, 15, 20, and 25 hops are enabled for such information aggregation to enforce the same receptive field, respectively. Specifically, we propose to evaluate the efficiency from two perspectives: The number of parameters (×1e6) and the inference time (seconds). From the experimental results shown in fig. 3, we observe that the number of parameters in both models grows w.r.t. the number of hops. However, AGDN requires significantly fewer parameters compared to GatedGCN under the same number of hop (i.e., the same size of receptive field). This is because with the proposed design, AGDN can aggregate 𝑘-hop information within a single layer without increasing the parameter count. In contrast, GatedGCN requires one more convolutional layer to aggregate information from one more hop away. Moreover, our inference time outperforms that of GatedGCN in most cases, and such an advantage becomes more significant when the hop number becomes larger. This shows that AGDN is more suitable for solving TSP problems requiring information from farther away for each node. This experiment strongly demonstrates that AGDN achieves a consistently better efficiency compared to the widely used GatedGCN.
KDD 2026, August 9–13, 2026, Jeju Island, Republic of Korea.
Bolin Shen, Ziwei Huang, Zhiguang Cao, and Yushun Dong
Table 4: Experimental Results on the Real-World Dataset TSPLIB
Method
tsp225 Length Gap
pcb442 Length Gap
pr1002 Length Gap
Concorde
8.22
0.00%
13.4
0.00%
16.4
0.00%
GatedGCN AGDN
8.26 8.25
0.49% 0.31%
13.5 13.5
1.15% 0.75%
17.1 16.8
4.25% 2.76%
5.4
Evaluation of Generalization Ability
To answer RQ3, in this subsection, we evaluate the models’ generalization ability across three dimensions. First, we examine performance on TSPs with varying problem sizes (i.e., different total numbers of nodes) and node distributions, both of which are widely acknowledged as critical factors for assessing generalization [18, 21, 45]. Additionally, we assess the transferability of the models to real-world TSP instances drawn from the TSPLib [1], which pose greater structural and distributional complexity than synthetic data and have been widely used in several related works [21, 27]. This comprehensive evaluation allows us to rigorously test the robustness and scalability of the proposed AGDN framework in both synthetic and practical scenarios. Generalization across Different Problem Sizes. We conduct performance comparison by training the learning-based models on TSP-100 and testing them on TSP-200, TSP-500, and TSP-1000, and we present the quantitative results in table 2. We observe that the proposed AGDN model consistently shows superior performance in finding high-quality routes (measured by the commonly used Gap metric) compared with the widely used GateGCN model. Notably, we observed a remarkable improvement of 89% specifically on TSP-1000, highlighting the effectiveness of AGDN in being generalized to large-scale TSPs. These findings demonstrate that AGDN exhibits superior generalization capabilities. Meanwhile, in terms of efficiency, we observe AGDN shows consistent superiority as discussed in Section 5.3, which further consolidates the advantages of our proposed method. Generalization across Different Node Distributions. We examine the performance of AGDN on problems with different node distributions in TSP-100 and TSP-1000. Here we focus on comparing the performance on the Gap metric, since it directly reflects the quality of the route identified by the model. We compared the stateof-the-art models across various distributions [18, 45]. From table 3, we have observations below. (1) Uniform Distribution: When nodes are evenly distributed across the space, AGDN achieves the best results, validating consistent superiority derived in our previous observations. (2) Cluster Distribution: When nodes are grouped into several dense regions, AGDN remains one of the most competitive models across all baselines. (3) Explosion Distribution: When all nodes are distributed outward toward the periphery, AGDN achieves the best performance in both cases. This can be attributed to the model’s ability to capture and effectively propagate global information. (4) Implosion Distribution: When a subset of nodes is concentrated at a central point while the rest are distributed outward, AGDN continues achieving the best results. The evaluation demonstrates the outstanding ability of the proposed AGDN to consistently exhibit superiority under different node distributions. Generalization on Real-World Dataset. We further evaluate the generalization ability of our proposed AGDN using real-world
datasets from TSPLib [1]. Specifically, we select three representative TSP instances: tsp225, pcb442, and pr1002, which contain 225, 442, and 1002 nodes, respectively. We compare our method against the baseline model GatedGCN. Both models are trained on the TSP-100 dataset and then evaluated on each of the real-world TSP instances. We report two metrics: Length, which denotes the total length of the predicted shortest path, and GAP, which measures the relative difference between the predicted path length and the known optimal solution. The results are summarized in Table 4. As shown in the table, our AGDN method consistently outperforms GatedGCN across all real-world datasets. This experiment provides strong evidence of the superior generalization ability of AGDN, not only does it achieve excellent performance on synthetic data, but it also delivers state-of-the-art results on real-world TSP problems.
6
Related Works
Graph Learning with Diffusion. Diffusion [66–68] in graph learning [13, 36, 42, 59, 70, 71, 74] has been explored through various theoretical frameworks. These approaches can be broadly categorized into two classes based on their mathematical foundation: Spectralbased [14] and partial/ordinary differential equations(PDE/ODE)based [20, 30] diffusion methods. (1) Spectral-based Diffusion Methods leverage the principles of spectral graph theory to enhance the learning process. A prominent example is Graph Diffusion Convolution (GDC) [25], which improves graph learning by introducing a generalized graph convolution. GDC incorporates diffusion methods such as the heat kernel [16, 28] and personalized PageRank [24, 41] to overcome the limitations of noisy and arbitrarily defined edges in graphs. (2) PDE/ODE-based Diffusion Methods: Another line of research leverages mathematical frameworks such as partial differential equations (PDEs) [20] and ordinary differential equations (ODEs) [30], to model graph diffusion, treating graph learning as a continuous process [6]. Notable examples include Graph Neural Diffusion (GRAND)[10], which utilizes heat equation to describe the temporal evolution of graph signals, and Graph Neural Ordinary Differential Equations (GDE)[49], where the relationship between inputs and outputs is governed by a continuous-time dynamical system, capturing the evolution of graph signals through ordinary differential equations. Solving TSPs with Graph Learning. Solving TSP with graph learning has become a prevalent approach, where three mainstreams of methods are commonly adopted. (1) Supervised Learning: The use of GatedGCN to construct a heatmap to find route from node embeddings was first introduced by [35], and numerous subsequent efforts explored graph-based approaches. For example, [22] demonstrated the ability to generalize across TSP instances of arbitrary sizes, removing constraints imposed by the training dataset size. [53] introduced a novel approach using graph diffusion to denoise and generate high-quality solutions. (2) Reinforcement Learning: Beyond supervised learning, reinforcement learning frameworks have effectively incorporated graphs. DIMES employed REINFORCE [60] to train a GNN, yielding notable performance improvements. (3) Unsupervised Learning: [47] pioneered the integration of graph models into an unsupervised learning framework, achieving state-of-the-art results without relying on labeled data. These advancements highlight the versatility and potential of graph
AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network
learning in addressing TSP challenges. Despite these explorations, they generally overlook the lack of an informative topological prior and fail to avoid the limitation of lacking node information exchange brought by the graph sparsification mechanism. Different from these works, AGDN achieves an informative topological structure without compromising to the limitation of sparsification.
7
Conclusion
In this paper, we propose the Anisotropic Graph Diffusion Network (AGDN), a novel framework designed to address the challenges faced by current GNN-based models in solving the Traveling Salesman Problem (TSP). Specifically, we have identified two key issues that current GNNs encounter when addressing TSP, i.e., lacking informative topological prior and information exchange between nodes in the TSP graphs. To address these issues, we propose a novel framework named AGDN integrated with a MixScore transition matrix that encodes both node similarity and pairwise distance information, along with an anisotropic graph diffusion mechanism that enables efficient multi-hop information propagation. Experiments showed AGDN significantly outperformed existing methods across different problem sizes, diverse node distributions and realworld datasets while maintaining strong generalization capabilities. The results validate AGDN’s effectiveness in both supervised and unsupervised learning settings, demonstrating superiority over current state-of-the-art approaches.
Acknowledgments This research is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: AISG3-RP-2022-031). We would also like to thank the anonymous reviewers for their constructive feedback.
References [1] n.d.. https://www.math.uwaterloo.ca/tsp. [2] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. 2019. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning. PMLR, 21–29. [3] Uri Alon and Eran Yahav. 2020. On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05205 (2020). [4] David L Applegate, Robert E Bixby, Vašek Chvátal, William Cook, Daniel G Espinoza, Marcos Goycoolea, and Keld Helsgaun. 2009. Certification of an optimal TSP tour through 85,900 cities. Operations Research Letters 37, 1 (2009), 11–15. [5] Gilbert Babin, Stéphanie Deneault, and Gilbert Laporte. 2007. Improvements to the Or-opt heuristic for the symmetric travelling salesman problem. Journal of the Operational Research Society 58, 3 (2007), 402–407. [6] Paul I Barton and Constantinos C Pantelides. 1994. Modeling of combined discrete/continuous processes. AIChE journal 40, 6 (1994), 966–979. [7] Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. 2021. Directional graph networks. In International Conference on Machine Learning. PMLR, 748–758. [8] Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. 2012. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games 4, 1 (2012), 1–43. [9] Chen Cai and Yusu Wang. 2020. A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006.13318 (2020). [10] Ben Chamberlain, James Rowbottom, Maria I Gorinova, Michael Bronstein, Stefan Webb, and Emanuele Rossi. 2021. Grand: Graph neural diffusion. In International conference on machine learning. PMLR, 1407–1418. [11] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. 2020. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI conference on artificial intelligence, Vol. 34. 3438–3445.
KDD 2026, August 9–13, 2026, Jeju Island, Republic of Korea.
[12] Jinbiao Chen, Jiahai Wang, Zizhen Zhang, Zhiguang Cao, Te Ye, and Siyuan Chen. 2024. Efficient meta neural heuristic for multi-objective combinatorial optimization. Advances in Neural Information Processing Systems 36 (2024). [13] Zhan Cheng, Bolin Shen, Tianming Sha, Yuan Gao, Shibo Li, and Yushun Dong. 2025. Atom: A framework of detecting query-based model extraction attacks for graph neural networks. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2. 322–333. [14] Fan RK Chung. 1997. Spectral graph theory. Vol. 92. American Mathematical Soc. [15] Geoff Clarke and John W Wright. 1964. Scheduling of vehicles from a central depot to a number of delivery points. Operations research 12, 4 (1964), 568–581. [16] Edward Brian Davies. 1989. Heat kernels and spectral theory. Number 92. Cambridge university press. [17] Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein. 2023. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Learning. PMLR, 7865–7885. [18] Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Marc Andreoli. 2024. Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization. Advances in Neural Information Processing Systems 36 (2024). [19] Matthias Englert, Heiko Röglin, and Berthold Vöcking. 2014. Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP. Algorithmica 68, 1 (2014), 190–264. [20] Lawrence C Evans. 2022. Partial differential equations. Vol. 19. American Mathematical Society. [21] Han Fang, Zhihao Song, Paul Weng, and Yutong Ban. 2024. INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformer. arXiv preprint arXiv:2402.02317 (2024). [22] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. 2021. Generalize a small pretrained model to arbitrarily large tsp instances. In Proceedings of the AAAI conference on artificial intelligence, Vol. 35. 7474–7482. [23] Chengrui Gao, Haopu Shang, Ke Xue, Dong Li, and Chao Qian. 2023. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. arXiv preprint arXiv:2308.14104 (2023). [24] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997 (2018). [25] Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. 2019. Diffusion improves graph learning. Advances in neural information processing systems 32 (2019). [26] Jhony H Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos D Malliaros. 2023. On the trade-off between over-smoothing and over-squashing in deep graph neural networks. In Proceedings of the 32nd ACM international conference on information and knowledge management. 566–576. [27] Yong Liang Goh, Zhiguang Cao, Yining Ma, Yanfei Dong, Mohammed Haroon Dupty, and Wee Sun Lee. 2024. Hierarchical neural constructive solver for real-world tsp scenarios. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 884–895. [28] Alexander Grigoryan. 2009. Heat kernel and analysis on manifolds. Vol. 47. American Mathematical Soc. [29] Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Advances in neural information processing systems 30 (2017). [30] Philip Hartman. 2002. Ordinary differential equations. SIAM. [31] Keld Helsgaun. 2017. An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University 12 (2017), 966–980. [32] Frederick S Hillier and Gerald J Lieberman. 2015. Introduction to operations research. McGraw-Hill. [33] Ziwei Huang, Jianan Zhou, Zhiguang Cao, and Yixin Xu. 2025. Rethinking light decoder-based solvers for vehicle routing problems. In International conference on learning representations. [34] Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, and Jiang Bian. 2023. Pointerformer: Deep reinforced multi-pointer transformer for the traveling salesman problem. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37. 8132–8140. [35] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. 2019. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227 (2019). [36] Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016). [37] Scott Kirkpatrick, C Daniel Gelatt Jr, and Mario P Vecchi. 1983. Optimization by simulated annealing. science 220, 4598 (1983), 671–680. [38] Wouter Kool, Herke Van Hoof, and Max Welling. 2018. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475 (2018). [39] Bernhard H Korte, Jens Vygen, B Korte, and J Vygen. 2011. Combinatorial optimization. Vol. 1. Springer. [40] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. 2020. Pomo: Policy optimization with multiple optima for
KDD 2026, August 9–13, 2026, Jeju Island, Republic of Korea.
reinforcement learning. Advances in Neural Information Processing Systems 33 (2020), 21188–21198. [41] Amy N Langville and Carl D Meyer. 2004. Deeper inside pagerank. Internet Mathematics 1, 3 (2004), 335–380. [42] Lincan Li, Bolin Shen, Chenxi Zhao, Yuxiang Sun, Kaixiang Zhao, Shirui Pan, and Yushun Dong. 2025. Intellectual property in graph-based machine learning as a service: Attacks and defenses. arXiv preprint arXiv:2508.19641 (2025). [43] Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. 2023. T2t: From distribution learning in training to gradient search in testing for combinatorial optimization. Advances in Neural Information Processing Systems 36 (2023), 50020–50040. [44] Attila Lischka, Jiaming Wu, Rafael Basso, Morteza Haghir Chehreghani, and Balázs Kulcsár. 2024. Less Is More-On the Importance of Sparsification for Transformers and Graph Neural Networks for TSP. arXiv preprint arXiv:2403.17159 (2024). [45] Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. 2023. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. Advances in Neural Information Processing Systems 36 (2023), 8845–8864. [46] Mary McGlohon, Leman Akoglu, and Christos Faloutsos. 2008. Weighted graphs and disconnected components: patterns and a generator. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. 524–532. [47] Yimeng Min, Yiwei Bai, and Carla P Gomes. 2024. Unsupervised learning for solving the travelling salesman problem. Advances in Neural Information Processing Systems 36 (2024). [48] SG Ozden, Alice E Smith, and Kevin R Gue. 2017. Solving large batches of traveling salesman problems with parallel and distributed computing. Computers & Operations Research 85 (2017), 87–96. [49] Michael Poli, Stefano Massaroli, Junyoung Park, Atsushi Yamashita, Hajime Asama, and Jinkyoo Park. 2019. Graph neural ordinary differential equations. arXiv preprint arXiv:1911.07532 (2019). [50] Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. 2022. Dimes: A differentiable meta solver for combinatorial optimization problems. Advances in Neural Information Processing Systems 35 (2022), 25531–25546. [51] T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. 2023. A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303.10993 (2023). [52] T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. 2023. A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303.10993 (2023). [53] Zhiqing Sun and Yiming Yang. 2023. Difusco: Graph-based diffusion solvers for combinatorial optimization. Advances in Neural Information Processing Systems 36 (2023), 3706–3731. [54] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. 2021. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2111.14522 (2021). [55] A Vaswani. 2017. Attention is all you need. Advances in Neural Information Processing Systems (2017). [56] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph attention networks. arXiv preprint arXiv:1710.10903 (2017). [57] Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. 2020. Multi-hop attention graph neural network. arXiv preprint arXiv:2009.14332 (2020). [58] Mingzhao Wang, You Zhou, Zhiguang Cao, Yubin Xiao, Xuan Wu, Wei Pang, Yuan Jiang, Hui Yang, Peng Zhao, and Yuanshu Li. 2025. An Efficient Diffusionbased Non-Autoregressive Solver for Traveling Salesman Problem. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1. 1469–1480.
Bolin Shen, Ziwei Huang, Zhiguang Cao, and Yushun Dong
[59] Zebin Wang, Menghan Lin, Bolin Shen, Ken Anderson, Molei Liu, Tianxi Cai, and Yushun Dong. 2025. Cega: A cost-effective approach for graph-based model extraction and acquisition. arXiv preprint arXiv:2506.17709 (2025). [60] Ronald J Williams. 1992. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning 8 (1992), 229–256. [61] Chenguang Xi, Van Sy Mai, Ran Xin, Eyad H Abed, and Usman A Khan. 2018. Linear convergence in optimization over directed graphs with row-stochastic matrices. IEEE Trans. Automat. Control 63, 10 (2018), 3558–3565. [62] Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song, and Jiang Bian. 2024. Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems. arXiv preprint arXiv:2406.03503 (2024). [63] Yubin Xiao, Di Wang, Boyang Li, Huanhuan Chen, Wei Pang, Xuan Wu, Hao Li, Dong Xu, Yanchun Liang, and You Zhou. 2024. Reinforcement learning-based nonautoregressive solver for traveling salesman problems. IEEE Transactions on Neural Networks and Learning Systems (2024). [64] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. 2021. Neurolkh: Combining deep learning model with lin-kernighan-helsgaun heuristic for solving the traveling salesman problem. Advances in Neural Information Processing Systems 34 (2021), 7472–7483. [65] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 (2018). [66] Rongchao Xu, Zhiqing Hong, and Guang Wang. 2025. AutoSTDiff: Autoregressive Spatio-Temporal Denoising Diffusion Model for Asynchronous Trajectory Generation. In Proceedings of the 2025 SIAM International Conference on Data Mining (SDM). SIAM, 538–547. [67] Rongchao Xu, Lin Jiang, Dahai Yu, Ximiao Li, and Guang Wang. 2026. SynHAT: A Two-stage Coarse-to-Fine Diffusion Framework for Synthesizing Human Activity Traces. arXiv preprint arXiv:2604.14705 (2026). [68] Ling Yang, Zhilong Zhang, Yang Song, Shenda Hong, Runsheng Xu, Yue Zhao, Wentao Zhang, Bin Cui, and Ming-Hsuan Yang. 2023. Diffusion models: A comprehensive survey of methods and applications. ACM computing surveys 56, 4 (2023), 1–39. [69] Hang Yi, Ziwei Huang, Yining Ma, and Zhiguang Cao. 2026. RADAR: Learning to Route with Asymmetry-aware DistAnce Representations. In International conference on learning representations. [70] Dahai Yu, Lin Jiang, Rongchao Xu, and Guang Wang. 2026. HealthMamba: An Uncertainty-aware Spatiotemporal Graph State Space Model for Effective and Reliable Healthcare Facility Visit Prediction. [71] Dahai Yu, Dingyi Zhuang, Lin Jiang, Rongchao Xu, Xinyue Ye, Yuheng Bu, Shenhao Wang, and Guang Wang. 2025. UQGNN: Uncertainty Quantification of Graph Neural Networks for Multivariate Spatiotemporal Prediction. In Proceedings of the 33rd ACM International Conference on Advances in Geographic Information Systems. 52–65. [72] Ni Zhang and Zhiguang Cao. 2026. Hybrid-balance gflownet for solving vehicle routing problems. Advances in Neural Information Processing Systems 38 (2026), 16797–16821. [73] Ni Zhang, Jingfeng Yang, Zhiguang Cao, and Xu Chi. 2025. Adversarial generative flow network for solving vehicle routing problems. In International conference on learning representations. [74] Kaixiang Zhao, Bolin Shen, Yuyang Dai, Shayok Chakraborty, and Yushun Dong. 2026. GraphIP-Bench: How Hard Is It to Steal a Graph Neural Network, and Can We Stop It? arXiv preprint arXiv:2605.12827 (2026).
AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network
A
Proof of Theoretical Results
Proof of Theorem 4.3. We are inspired by the proof strategy of Theorem 2.3 in [7]. Let 𝜙 1 denote the first non-trivial eigenvector of 𝑳, where 𝑳 is the normalized Laplacian associated with 𝑴, associated with eigenvalue 𝜆1 , and suppose 𝑥, 𝑦, 𝑧 ∈ V satisfy 𝜙 1 (𝑥) < 𝜙 1 (𝑧) and 𝜙 1 (𝑦) < 𝜙 1 (𝑧). Let (𝑥 ′, 𝑦 ′ ) be the nodes obtained from (𝑥, 𝑦) by simultaneously taking a forward gradient step from 𝑥 to 𝑧 under 𝑴 S , and a backward gradient step from 𝑦 to 𝑧 under 𝑴 D . Define diffusion distance under 𝑴 as: ∑︁ 𝑑𝑘𝑴 (𝑥, 𝑦) 2 = 𝑒 −2𝑘𝜆𝑖 (𝜙𝑖 (𝑥) − 𝜙𝑖 (𝑦)) 2 ,
KDD 2026, August 9–13, 2026, Jeju Island, Republic of Korea.
the surrogate loss. In our model, since anisotropic information is no longer present, we only employ the transition matrix 𝑻𝑟 𝑤 to propagate neighbor information during graph diffusion. Additionally, due to the absence of information from two separate spaces, we also omitted the node aggregation process and directly used the node embeddings to predict the soft indicator matrix T. Sparsification. To reduce additional noise, we applied sparsification to the transition matrix. It is worth noting that the retained connections significantly exceed those in all current approaches. Specifically, for GatedGNN, it retains 20% of the edges, whereas our approach retains 70% of the edges.
𝑖 ≥1
where 𝜙𝑖 𝑛−1 𝑖=0 are the orthonormal eigenvectors of 𝑳. We aim to
B.3
show:
Architecture. For our model, we used three layers, and in each layer we applied BatchNorm followed by Dropout to normalize the node embeddings. Next, we used the ReLU activation function, and a residual layer was incorporated to fuse node embeddings. Finally, The anisotropic node embeddings were concatenated and then mapped to the hidden dimension using a linear layer. We then use this fused embedding to predict heatmap. Parameters. The design of our model parameters includes a hidden dimension of 128 and drop probability of 0.5. The diffusion step K is set to 5, and the weights of the PageRank-based diffusion matrix are initialized with a teleport probability of 0.1. Training. During training, we used the Adam optimizer to optimize our model. The weight decay was set to 1.0 for all cases. Our model is trained for 20 epochs, and the final epoch is used for testing. Specifically, we applied StepLR to decay the learning rate, with a decay factor 𝛾 = 0.8 for every 8 epochs. In addition, we applied gradient clipping using clip_grad_norm(1.0) to prevent exploding gradients and stabilize training.
𝑑𝑘𝑴 (𝑥 ′, 𝑦 ′ ) 2 < 𝑑𝑘𝑴 (𝑥, 𝑦) 2 . The reduction in distance is primarily due to the contraction along 𝜙 1 , since: (𝜙 1 (𝑥 ′ ) − 𝜙 1 (𝑦 ′ )) 2 < (𝜙 1 (𝑥) − 𝜙 1 (𝑦)) 2, as both 𝑥 and 𝑦 move toward the higher-potential node 𝑧, effectively reducing their separation in the direction of 𝜙 1 . As in [7], we have bound: ∑︁ ∑︁ 𝑒 −2𝑘𝜆𝑖 (𝜙𝑖 (𝑥 ′ ) − 𝜙𝑖 (𝑦 ′ )) 2 − (𝜙𝑖 (𝑥) − 𝜙𝑖 (𝑦)) 2 ≤ 𝑒 −2𝑘𝜆2 Δ𝑖 , 𝑖 ≥2
𝑖 ≥2
where each Δ𝑖 denotes the change in squared difference on eigencomponent 𝑖. Since this term decays exponentially faster than 𝑒 −2𝑘𝜆1 , there exists a threshold 𝐶 > 0 such that for 𝑘 ≥ 𝐶, the overall distance decreases: 𝑑𝑘𝑴 (𝑥 ′, 𝑦 ′ ) 2 < 𝑑𝑘𝑴 (𝑥, 𝑦) 2 . Thus, we can conclude that the anisotropic gradient step yields a contraction in diffusion distance. □
B Reproducibility B.1 Data Preprocessing We directly used the dataset from the UTSP repository, which is entirely consistent with the setup in previous work [22]. We first performed preprocessing by rescaling the node coordinates for each sample. We introduced a scale ratio 𝜖 and denoted the rescaled ˜ For nodes in a TSP instance, the rescaling node coordinates as 𝑣. is expressed as 𝑣˜ = 𝜖 · (𝑣 − 𝑣¯), where 𝑣¯ denotes mean value of coordinates in a TSP instance, and 𝜖 = 2.0 is set for TSP-100 and TSP-200 tasks, and 𝜖 = 4.0 is set for TSP-500 and TSP-1000 tasks.
B.2
Experimental Settings
Supervised Learning. Our settings in the supervised mode are entirely consistent with those described in the GatedGCN [35]. Our training and inference processes are entirely consistent to eliminate any discrepancies. Unupervised Learning. Our settings in the unsupervised mode are fully consistent with those mentioned in the UTSP [47], including the MCTS parameters used, which are also identical to those described in the paper. In unsupervised learning, a surrogate loss is proposed to optimize the model, which requires the construction of a soft indicator matrix T. As a result, our anisotropic design becomes unnecessary. Therefore, we removed this mechanism and ensured that the model’s output aligns with the requirements of
B.4
Implementation of AGDN
Implementation of Baseline
GatedGCN. We implemented GatedGCN entirely based on the code released in [35] repository. We set the sparse ratio to 0.2, meaning each node remains connected to the closest 20% of nodes. The encoder consisted of 3 layers, with a hidden dimension of 128. Then we standardized our model and GatedGCN model to use Monte Carlo Tree Search for searching the predicted paths. UTSP. For UTSP, we strictly follow the original experimental settings described in [47]. The model is trained for 300 epochs with a batch size of 32 for TSP-200 and 64 for TSP-500 and TSP-1000. We use the Adam optimizer with a learning rate of 3 × 10−3 , weight decay of 0.0, and apply a StepLR scheduler with a step size of 20 and a decay factor 𝛾 = 0.8. Others. The results of other baselines in Table 1 are obtained directly from the official implementations and results reported in UTSP [47] and DIFUSCO [53]. For the baselines presented in Table 3, we strictly follow the official results reported in INViT [21].
B.5
Computing Resources
The training and inference of our model were conducted on an Nvidia RTX 6000 Ada GPU. The CPU used was an AMD EPYC 7763 64-Core @ 2.45 GHz, providing 128 threads. The server is configured with 1000 GB of DDR4 RAM. Monte Carlo Tree Search is performed on the CPU, utilizing 32 threads for evaluation.
KDD 2026, August 9–13, 2026, Jeju Island, Republic of Korea.
C
Bolin Shen, Ziwei Huang, Zhiguang Cao, and Yushun Dong
Supplementary Experiments
C.3
To further demonstrate the effectiveness of our proposed method, we conduct a comprehensive set of supplementary experiments. In the following, we first analyze the robustness of AGDN, including the impact of hop depth selection, sparsification ratio choices, and different decoder strategies. In addition, we introduce a broader range of baseline methods to provide a more extensive and thorough comparison with our approach.
C.1
Robustness Analysis: Sensitivity to Hop Depth
We first investigate the sensitivity of AGDN to the choice of hop depth, which controls the range of neighborhood aggregation. We evaluate AGDN on TSP1000 with different hop depths while keeping all other settings fixed.
Robustness Analysis: Different Decoders
To examine whether the performance gains of AGDN depend on a specific decoding strategy, we further compare AGDN with a widely used graph-based baseline, GatedGCN, under different decoders. Specifically, we consider two commonly adopted local search decoders: 2-opt [19] and Or-opt [5], and evaluate all methods on TSP200, TSP500, and TSP1000. Table 7: Comparison of AGDN performance under different decoder strategies, along with comparisons to GatedGCN. The best results are highlighted in bold, and the second-best results are underlined. Model (Decoder)
TSP200 Gap (%) TSP500 Gap (%) TSP1000 Gap (%)
GatedGCN (2-opt) GatedGCN (Or-opt) AGDN (2-opt) AGDN (Or-opt)
1.530 ± 0.14 1.217 ± 0.11 0.703 ± 0.48 0.445 ± 0.04
3.553 ± 0.20 2.498 ± 0.17 1.274 ± 0.19 1.117 ± 0.06
13.91 ± 1.01 11.50 ± 0.87 1.774 ± 0.19 1.491 ± 0.01
Table 5: AGDN performance on TSP1000 under different hop settings.
Setting
Length
Gap (%)
hops = 15 hops = 24 hops = 30
23.37 23.37 23.37
1.049 1.038 1.024
As shown in the Table 5, varying the hop depth from 15 to 30 results in negligible differences in both tour length and optimality gap. In particular, the tour length remains identical across all settings, and the gap varies by less than 0.03%. These results indicate that AGDN is highly robust to the hop depth parameter, and its performance does not rely on a carefully tuned range of neighborhood hop depths.
C.2
Robustness Analysis: Sensitivity to Sparsification Ratio
We further analyze the impact of the sparsification ratio (𝑠𝑝), which determines the proportion of retained edges during graph sparsification. We conduct experiments on TSP200, TSP500, and TSP1000, varying the sparsification ratio from 0.1 to 1.0. The results are reported in Table 6. Across all problem scales, AGDN exhibits consistently stable performance under different sparsification ratios. The optimality gaps remain within a narrow range, and no clear degradation is observed even under aggressive sparsification. This suggests that AGDN does not depend on a specific sparsification level and can effectively leverage both sparse and dense graph structures. Table 6: Performance of AGDN under different 𝑠𝑝 settings.
𝑠𝑝
TSP200 Gap (%)
TSP500 Gap (%)
TSP1000 Gap (%)
0.1 0.3 0.5 0.7 1.0
0.054 0.045 0.063 0.060 0.056
0.654 0.631 0.642 0.674 0.662
0.956 1.021 0.988 1.049 0.966
As shown in the Table 7, AGDN consistently outperforms GatedGCN across all problem scales and both decoding schemes. Notably, even when using the same decoder, AGDN achieves substantially lower optimality gaps, indicating that its advantage stems from the proposed graph representation and learning mechanism rather than a particular decoding heuristic. Furthermore, both models benefit from the stronger Or-opt decoder compared to 2-opt, yet the relative performance gap between AGDN and GatedGCN remains large and stable. This observation confirms that the effectiveness of AGDN is decoder-agnostic and does not rely on a specific post-processing or local search strategy.
C.4
Comparison with Broader Baselines
Table 8: Performance comparison between AGDN and additional baseline methods, where AGDN (SL) denotes the supervised learning setting and AGDN (UL) denotes the unsupervised learning setting. OOM indicates out-of-memory errors. The best results are highlighted in bold, and the second-best results are underlined. Model PointerFormer [34] BQNCO [18] ELG [23] HierTSP [27] NAR4TSP [63] DEITSP [58] T2TCO [43] NeuroLKH [64] AGDN (SL) AGDN (UL)
TSP200 Gap (%) TSP500 Gap (%) TSP1000 Gap (%) 1.45 4.51 1.64 2.23 3.07 0.40 0.55 0.53 0.06 0.05
12.5 4.02 7.16 12.1 12.0 2.15 2.78 0.83 0.74 0.64
20.7 4.19 11.4 22.8 16.1 3.68 𝑂𝑂𝑀 0.90 1.28 0.96
In this section, we further compare AGDN with a broader set of baseline methods. The results in Table 8 show that the proposed AGDN consistently demonstrates strong performance, achieving the best results on both TSP200 and TSP500. Notably, NeuroLKH, as a heuristic-based method, can spend significantly longer decoding time to obtain more accurate solutions. For example, on TSP1000, NeuroLKH requires 1183 seconds for decoding, whereas AGDN requires only 0.97 seconds while still achieving highly competitive and impressive performance.