AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network

• URL: http://arxiv.org/abs/2606.19185v1
• Date: Wed, 17 Jun 2026 15:24:37 GMT
• Title: AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network
• Abstract summary: We present the Anisotropic Graph Diffusion Network (AGDN), a new Graph Neural Network framework designed to solve the Traveling Salesman Problem (TSP)<n>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.<n>AGDN consistently outperforms existing methods while keeping time competitive.
• Score: 50.69521065962045
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Scalable Graph Compressed Convolutions [68.85227170390864]
  We propose a differentiable method that applies permutations to calibrate input graphs for Euclidean convolution. Based on the graph calibration, we propose the Compressed Convolution Network (CoCN) for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2024-07-26T03:14:13Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Learning Strong Graph Neural Networks with Weak Information [64.64996100343602]
  We develop a principled approach to the problem of graph learning with weak information (GLWI) We propose D$2$PT, a dual-channel GNN framework that performs long-range information propagation on the input graph with incomplete structure, but also on a global graph that encodes global semantic similarities.
  arXiv  Detail & Related papers  (2023-05-29T04:51:09Z)
• Mixed Graph Contrastive Network for Semi-Supervised Node Classification [63.924129159538076]
  We propose a novel graph contrastive learning method, termed Mixed Graph Contrastive Network (MGCN)<n>In our method, we improve the discriminative capability of the latent embeddings by an unperturbed augmentation strategy and a correlation reduction mechanism.<n>By combining the two settings, we extract rich supervision information from both the abundant nodes and the rare yet valuable labeled nodes for discriminative representation learning.
  arXiv  Detail & Related papers  (2022-06-06T14:26:34Z)
• FeatureNorm: L2 Feature Normalization for Dynamic Graph Embedding [39.527059564775094]
  Graph convolutional network (GCN) has been widely explored and used in non-Euclidean application domains. In this paper, we analyze the shrinking properties in the node embedding space at first, and then design a simple yet versatile method. Experiments on four real-world dynamic graph datasets compared with competitive baseline models demonstrate the effectiveness of the proposed method.
  arXiv  Detail & Related papers  (2021-02-27T09:13:47Z)
• Co-embedding of Nodes and Edges with Graph Neural Networks [13.020745622327894]
  Graph embedding is a way to transform and encode the data structure in high dimensional and non-Euclidean feature space. CensNet is a general graph embedding framework, which embeds both nodes and edges to a latent feature space. Our approach achieves or matches the state-of-the-art performance in four graph learning tasks.
  arXiv  Detail & Related papers  (2020-10-25T22:39:31Z)
• A Generative Graph Method to Solve the Travelling Salesman Problem [1.552282932199974]
  We propose to use the novel Graph Learning Network (GLN), a generative approach, to approximately solve the Travelling Salesman Problem (TSP) GLN model learns directly the pattern of TSP instances as training dataset, encodes the graph properties, and merge the different node embeddings to output node-to-node an optimal tour.
  arXiv  Detail & Related papers  (2020-07-09T17:23:55Z)
• Graph Representation Learning Network via Adaptive Sampling [4.996520403438455]
  Graph Attention Network (GAT) and GraphSAGE are neural network architectures that operate on graph-structured data. One challenge raised by GraphSAGE is how to smartly combine neighbour features based on graph structure. We propose a new architecture to address these issues that is more efficient and is capable of incorporating different edge type information.
  arXiv  Detail & Related papers  (2020-06-08T14:36:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.