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

Official implementation of AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network.

Authors: Bolin Shen, Ziwei Huang, Zhiguang Cao, and Yushun Dong

Venue: This work has been accepted by the Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining.

TL;DR: AGDN solves TSP by combining a MixScore transition matrix with anisotropic graph diffusion, enabling effective multi-hop information exchange, strong performance across diverse instance sizes and distributions, and robust out-of-distribution generalization.

Quick Start

Clone the repository and install the Python dependencies:

git clone https://github.com/LabRAI/AGDN.git
cd AGDN
pip install -r requirements.txt

Run the supervised pipeline:

cd supervised
python main.py --train
python main.py --test

Run the supervised search step:

cd supervised/search
bash ./new-solve-100.sh 0.1 6 10 0 30 3 0 0

Run the unsupervised pipeline:

cd unsupervised
python train.py \
  --num_of_nodes 100 \
  --EPOCHS 300 \
  --batch_size 32 \
  --temperature 3.5 \
  --C1_penalty 20.0 \
  --nlayers 2 \
  --hidden 64 \
  --rescale 1.0 \
  --moment 1 \
  --model agd \
  --device 0

See supervised/README.md and unsupervised/README.md for the full training, inference, search, and hyperparameter commands.

Requirements

The code was developed for Python 3 with PyTorch and CUDA-enabled GPU training. Install the main Python dependencies with:

pip install -r requirements.txt

The search component under supervised/search also requires a C++ compiler such as g++.

Repository Structure

AGDN-Official/
├── supervised/       # Supervised AGDN/GatedGCN training, testing, and TSP search
├── unsupervised/     # Unsupervised AGDN training and heatmap generation
├── requirements.txt  # Python dependencies
└── README.md         # Project overview

Resources

This repository builds on and benefits from the following open-source projects:

• GatedGCN: chaitjo/graph-convnet-tsp
• Unsupervised learning: yimengmin/UTSP
• MCTS for TSP: Spider-scnu/Monte-Carlo-tree-search-for-TSP

We thank the authors and contributors for releasing their code.

Citation

To be updated.