Unsupervised Learning for Solving the Travelling Salesman Problem
Authors: Yimeng Min
Yiwei Bai
Carla P Gomes
Venue: NeurIPS 2023 poster (2023)
Keywords: Combinatorial Optimization
Graph Neural Network
Travelling Salesman Problem
TL;DR: use graph neural network, unsupervised learning and search to solve the Travelling Salesman Problem

Abstract: We propose UTSP, an Unsupervised Learning (UL) framework for solving the Travelling Salesman Problem (TSP). We train a Graph Neural Network (GNN) using a surrogate loss. The GNN outputs a heat map representing the probability for each edge to be part of the optimal path. We then apply local search to generate our final prediction based on the heat map. Our loss function consists of two parts: one pushes the model to find the shortest path and the other serves as a surrogate for the constraint that the route should form a Hamiltonian Cycle. 
Experimental results show that UTSP 
outperforms the existing data-driven TSP heuristics.
Our approach is parameter efficient as well as data efficient: the model takes  $\sim$ 10\% of the number of parameters and $\sim$ 0.2\% of training samples compared with Reinforcement Learning or Supervised Learning methods.

Unsupervised Learning for Solving the Travelling Salesman Problem
Yimeng Min Dept. of Computer Science
Yiwei Bai* Dept. of Computer Science Cornell University Ithaca, NY, USA bywbilly@gmail. com
Carla Gomes
Dept. of Computer Science Cornell University Ithaca, NY, USA cateessss.ccrneee
Cornell University Ithaca, NY, USA minêcs. cornell. edu
Abstract
We propose UTSP, an Unsupervised Learning (UL) framework for solving the Travelling Salesman Problem (TSP). We train a Graph Neural Network (GNN) us- ing surrogate loss. The GNN outputs a heat map representing the probability for each edge to be part of the optimal path. We then apply local search to generate our final prediction based on the heat map. Our loss function consists of two parts: one pushes the model to find the shortest path and the other serves as surrogate for the constraint that the route should form Hamiltonian Cycle. Experimen- tal results show that UTSP outperforms the existing data-driven TSP heuristics. Our approach is parameter efficient as well as data efficient: the model takes 10% of the number of parameters and ~ 0.2% of training samples compared with Reinforcement Learning or Supervised Learning methods.
Introduction
Euclidean Travelling Salesman Problem (TSP) is one the most famous and intensely studied NP-hard problems in the combinatorial optimization community. Exact methods, such Con- corde Applegate et al] [2(06]] use the cutting-plane method, iteratively solving linear programming relaxations of the TSP. These methods usually implemented within branch-and-eut framework, integrating the cutting-plane algorithm into muunchandd-ouun search. While these exact methods can find solutions with guaranteed optimality for up tens of thousands of nodes, the execution time can be exceedingly expensive. A different strategy is using heuristics such as LKH Helsgaun [2σXо]]] These heuristics aim to find near-optimal solutions with notable reduction in time com- plexity. Typically, they are manually crafted, drawing upon expert insights and domain-specnt knowledge.
Recently, the success of Graph Neural Networks (GNNs) for variery of machine learning tasks has sparked interests in building data-driven heuristies for approximating TSP solutions. For example, Kwon al [2020] uses a data-driven approach known as Policy Optimization with Multiple Optima (POMO), POMO relies on Reinforcement Learning (RL) and avoids the utilization of hand-crafted heuristics. Quu et al. [202 proposes a Meta-Learning framework which enhances the stability of RL training. Sun and Yang [202]]] applies Supervised Learning (SL) and adopts a graph-based diffusion framework. Additionally, the authors use a cosine inference schedule to improve the efficiency of their model. [loshi al [20 trains their GNN model SL fashion, and the model outputs an edge adjacency matrix that indicates the likelihood of edges being part of the TSP tour. The edge predictions form heat map, which transformed into valid tour through a beam search method. Similarly, Fu all [2021] trains the GNN model on small sub-graphs to generate the corresponding heat maps using SI. These small heat maps are then integrated build large final heat map.
"Equal contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Overall, these learning- based models usually build heuristies by reducing the length of TSP tours via RL or directly learning from the optimal solutions via SL. However, since TSP NP-hard, SL can cause expensive annotation problems due to the costly search time involved in generating optimal solutions. For RI., when dealing with big graphs, the model will run into the sparse reward problem because the reward is decided after decoding a complete solution. The sparse reward problem results in poor generalization performance and high training variance. Furthermore, both RL and SL suffer from expensive large-scale training. These models take more than one million training samples when dealing with TSP with 100 nodes, making the training process very time-consuming.
2
Our Model
In this work, we build a data-driven TSP heuristic in an Unsupervised Learning (UL) fashion and generate the heat map non-autoregreesiiely We construct surrogate loss function with two parts: one encourages the GNN to find the shortest path, and the other acts as a proxy for the constraint that the path should be a Hamiltonian Cycle over all nodes. The surrogate loss enables us to update the model without decoding a complete solution. This helps alleviate the sparse reward problem encountered in RL, and thus, it avoids unstable training or slow convergence Kool et all [201]]. Our UTSP method does not rely on labelled data, which helps the model avoid the expensive annotation problems encountered in SI. and significantly reduces the time cost. fact, due to the prohibitive time cost of building training datasets for large instances, many SI. methods are trained on relatively small instances only Eu et al [2021] et al [ Such SL. models scale poorly to big in- stances, while with our UTSP model, we can train our model on larger instances directly. Overall, our training does not rely on any labelled training data and converges faster compared to RL/SL methods.
The model takes the coordinates as the input of GNN. The distance between two nodes determines the edge weight in the adjacency matrix. After training the GNN, the heat map is converted to valid tour using local search. We evaluate the performance of UTSP through comparisons on TSP cases of fixed graph sizes up to 1,000 nodes. We note that UTSP is fundamentally different from RL, which may also be considered unsupervised. While RI. requires a Markov Decision Process (MDP), and its reward is extracted after obtaining solutions, our method does not use a MDP and the loss function (reward) is determined based on a heat map.
Overall, UTSP requires only a small amount of (unlabelled) data and compensates for it by em- ploying an unsupervised surrogate loss function and an expressive GNN. The heat maps built using UTSP help reduce the search space and facilitate the local search. We further show that the expres- sive power of GNNs critical for generating non- son-smooth heat maps.
3 Methodologies
In this paper, we study symmetric TSP on a 2D plane. Given n cities and the coordinates (zx, yr) E R² of these cities, our goal is to find the shortest possible route that visits each city exactly once and returns to the origin city, where E (1, 2, 3, ..., n) is the index of the city.
3.1 Graph Neural Network
Given a TSP instance, let Dijj denote the Euclidean distance between city i and city j. D E Raxx is the distance matrix. We first build adjacency matrix W E R=x" with W e D,,/ and node feature F E RR*2 hased on the input coordinates, where F, = (xx, yi) and r is the temperature. The node feature matrix and the weight matrix W are then fed into a GNN generate a soft indicator matrix T e 1
In model, we use Scattering Attention GNN (SAG), SAG has both low-pass and band-pass filters and can build adaptive representations by learning node-wise weights for combining multiple different channels in the network using attention- architecture. Recent studies show that SAG can output expressive representations for graph combinatorial problems such as maximum clique and remain lightweight Min et all [2022]]
Let S E TRax denote the output of SAG, we first apply a column-wise Softmax activation to the GNN's output and we can summarize this operation in matrix notation Tu, S.. /S.s/En /E>= St..

---

This ensures that each element in T is greater than zero and the summation of each column is 1. We then use T to build heat map H. where H. E R=x".
In our model, we use H. to estimate the probability of each edge belonging to the optimal solution and use T build surrogate loss of the Hamiltonian Cycle constraint. This will allow build a non-smooth heat map H and improve the performance of the local search.
3.2 Building the Heat Map using the soft indicator matrix
Before building the unsupervised loss, let's recall the definition of TSP. The objective of TSP is identify the shortest Hamiltonian Cycle of graph. Therefore, the unsupervised surrogate loss should act as proxy for two requirements: the Hamiltonian Cycle constraint and the shortest path constraint. However, designing surrogate loss for the Hamiltonian Cycle constraint can be chal- lenging, particularly when working with heat map H. To address this, we introduce the T + H transformation, which enables the model to implicitly encode the Hamiltonian Cycle constraint.
Coordinates
Soft Indicator Matrix T
Heat Map H
Wis
e Disht
T
H
Graph Neural Network
4
3
2
2
5
Input Cities
Route with cycles
TSP solution
We SAG generate non-smooth soft indicator matrix T. The SAG model is function of coordinates and weighted adjacency matrix. We then build the heat map H. based on T using the transformation in Equation II.
Figure 1:
To better understand the T + H. transformation, we show a binary instance in Figure W. Figure II illustrates soft indicator matrix T, its heat map H following the transformation T -> H. and their corresponding routes. When we directly use the soft indicator matrix T as the heat map. It can result in loops (parallel edges) between cities, such as (2,3) and (4.5) Figure DI (middle). After we apply the T + H transformation, the corresponding heat H is a Hamiltonian Cycle, as shown in the right part Figure MI.
3.3 T + H. transformation
build the heat map based on T. mentioned, Hi, is the probability for edge (i.j) belong to the optimal TSP solution. We define H as:
n-1
Σ
puPl+1 + PoPI,
(I)
3

---

where Pr E R is the tih column of T, T [pilpel...Ipnl As shown in Figure II the first row in H is the probability distribution of directed edges start from city and since the third element the only non-zero one in the first row, we then add directed edge - 3 to our TSP solution. Similarly, the first column in H can be regarded as the probability distribution of directed edges which end in city 1. Ideally, given a graph 9 with n. nodes, we want to build soft indicator matrix where each row and column are assigned with one value 1 (True) and n 1 values 0 (False), so that the heat map will only contain one valid solution. In practice, we will build soft indicator matrix T whose heat map H assigns large probabilities to the edges in the TSP solution and small probabilities to the other edges.
Overall, the T + H. transformation in Equation D enables to build proxy for the Hamiltonian Cycle constraint. We further prove that H. represents one Hamiltonian Cycle when each row and column in T have one value (True) and value 0 (False). We refer the proof in appendix [X.
3.4 Unsupervised Loss
In order to generate such an expressive soft indicator matrix T, we minimize the following objective function:
L
A1
j
1)2
+
Hois
Dij DigHiis
Row-wise constraint
No loops
Minimiize the distance
The first term in L. encourages the summation of each row in T to be close to 1. As mentioned, we normalize each column of T using Softmax activation. So when the first term is minimized to zero, each row and column in T are normalized (doubly stochastic). The second term penalizes the weight on the main diagonal of H. this discourages self-loops in TSP solutions. The third term can be regarded as the expected TSP length of the heat map H. where Daj is the distance between city i and j. As mentioned, since 76 corresponds to a Hamiltonian Cycle given an ideal soft indicator matrix with one value 1 (True) and 1 value 0 (False) in each row and column. Then the minimum value of Σ Σー= DigHis, is the shortest Hamiltonian Cycle on the graph, which is the optimal solution of TSP. To summarize, we build a loss function which contains both the shortest and the Hamiltonian Cycle constraints. The shortest constraint is realized by minimizing En_ 2==1 Di,jHa.j. For the Hamiltonian Cycle constraint, instead of writing it in a Lagrangian relaxation style penalty, we use GNN which encourages a non-smooth representation, along with the doubly stochastic penalty, and the T + H transformation.
3.5 Edge Elimination
Given a heat map H. we consider largest elements in each row (without diagonal elements) and set other n M elements as O. Let H denote the new heat map, we then symmetrize the new heat map by Ht' H + H². Let E,j E 1) denote whether an undirected edge (i,j) j) in our prediction not. Without loss of generality,
assume 0 < i < S and define Egj as:
Ei {b.
if = HHz >
otherwise
Let II denote the set of undirected edges (i,j) with Eg 1. Ideally, we would build prediction edge set II with a small M value, and II can cover all the ground truth edges so that we can reduce search space size from n(n 1)/2 to [II. In practice, aim to let II cover as many ground truth edges as possible and use H' to guide the local search process.
4
Local Search
4.1 Heat Map Guided Best-first Local Search
We employ the best-first local search guided by the heat map to generate the final solution. Best-first search is heuristic search that explores the search space by expanding the most promising node selected w.r.t an evaluation function f (node). In our framework, each node of the search tree is

---

complete TSP solution. For the initialization of one search tree, we randomly generate a valid TSP solution and improve using the 2-opt heuristic until no better solution found. The expand action of the search node refers to Eu et all [202T] and is based on the widely used k-opt heuristic Croes [1958], where it replaces k old edges (in the current solution) with new edges, i.e., transforms the old solution to new solution. More formally, we use series of cities, 11, U1, Mg....., Uky Mk+1, to represent an action, where Uk+11 = 41 to ensure it is a valid solution. All the edges (u, vi) (1 S i I k) are removed from the tour and (v;, ui+1 (1 S S k) are added to the tour. Note that once we know ui 2 is deterministically decided. U1 is randomly selected for each expansion, and or U1, Le., forms new TSP tour, leads to an improved solution then we set Uj+1 = ú1 and have a candidate solution. expand action, where K is hyper- parameter which controls the maximal edges we can remove in one action. (3) otherwise, we select 14+1 based on the heat map stochastically. We use Nu.o denote the times the edge (u, v) is selected during the entire search procedure. The likelihood of selecting the edge (u, v) is denoted
is decided subsequently. Then select u/+1 2 1) as follows: (1) if u4+1
(2) if 2 K, then will discard this action and start
by Lu,e = Hupe + av [og(S+1]
and S is the local search's 's total number of expand actions. The first term encourages the algorithm to select the edge with a high heat map value, while the second term diversifies the selected edges. Moreover, when selecting the city u given u, we only consider the cities from the candidate set of This candidate set consists of cities with the top M heat map value or the nearest M cities
NI.+II' where a is a
Among all the possible new solutions, we use the tour's length as the evaluation function f. i.e., select the solution of the shortest tour length as the next search node. For each search node, we try at most T expand actions. From these T expand actions, if no improved solution is found, randomly generate a new initial solution and start another round of best-first local search.
4.2 Updating the Heat Map
We borrow the idea of the backpropagation used in Monte Carlo Tree Search (MCTS). We use to denote the current search node, s' to denote the next search node (s' has to improve s), and ((s) to represent the tour length of node s. The heat map Ht is updated as:
L(s) L(s'), L(s)
H Ho Ho + 3lexp(
- 11.
where ( is a search parameters and (v,, (1 < < k) is the actions used to transform to s'. We raise the importance of the edges that lead to a better solution. If we cannot find an improved solution for the current node, then no update is executed for the heat map.
4.3 Leveraging Randomness
Randomness is shown to be very powerful in the local search community Gomes et all [199]] Bresina [1996], Gomes al [200]] Our local search procedure also employs it to improve perfor- mance. When we stop the current round of local search by not finding an improved solution within T expand actions and switch to new best-first local search with new initial solution, we randomly modify the parameter K. A larger K value results in more time searching from one initial solution. The intuition is that sometimes
want more initial solutions while sometimes we want to search deeper (replace more edges in k-opt) for a specific solution. Besides that, we also randomly decide how construct the candidate set (based the heat map or pairwise distance) for each city before the new round of local search.
5 Experiments
5.1 Dataset
Our dataset contains 2,000 samples for training and 1,000 samples for validation. We use the same test dataset in Eu et all [202T]. The test dataset contains 10, 000 2D-Buclidean TSP instances for 20, 50, 100, and 128 instances for 200, 500, 1, 000. We train our models on TSP instances with 20, 50, 100, 200, 500, and 1,000 vertices. We then build the corresponding heat maps based on these trained models.
5

---

Table 1: Results of SAG Local Search w.r.t existing baselines. We evaluate the models on 10,000
TSP 20 instances and 10,000 TSP 50 instances. Baselines include GAT-RLI: Deudon et all [20
GAT-RL2: Kool all 201:: GCN-SLI: JoshLettll
[20
POMO: Kwon all [022 and Att-
GCRN en all 2021]
TSP20
TSP50 Gap (%)
Method
Type
Length
Gap (%)
Time
Length
Time
Concorde
Solver
3.8303
0.0000
2.31m
5,6906
0.0000
13.68m
Gurobi
Solver
3,8302
-0.0001
2.33m
5,6905
0.0000
26.20m
LKH3
Heuristic
3.8303
0.0000
20.96m
5.6906
0.0008
26.65m
GAT-RLI
RI, S
3.8741
1.1443
10.30m
6,1085
7.3438
19.52m
RI. S
GAT-RLI
3.8501
0.5178
15.62m
5.8941
3.5759
27.8
2-OPT
GAT-RL2
RL.
3.8322
0,0501
16.47m
5.7185
0.4912
22.85m
GAT-RL2
RL.
3.8413
0.2867
6.03s
5.7849
1.6568
34,92s
GAT-RL2
RL, BS
3.8304
0.0022
15.01m
5.7070
0.2892
25.58m
GCN-SLI
SL, G
3.8552
0.6509
19.41s
5.8932
3.5608
2.00m
GCN-SLI
SL, BS
3.8347
0.1158
21.35m
5.7071
0,2905
35.13m
GCN-SLI
SL, BS
3.8305
0.0075
22.18m
5.6920
0.0251
37.56m
POMO
RL
3.83
0.00
38
5.69
0.03
168
SLARL MCTS
23.33s
2.59m
Att-GCRN
3,8300
-0.0074
5.6908
0.0032
1.05m
2.63m
38.23s
1.34m+
UTSP (ours)
UL, Search
3.8303
-0.0009
5.6894
-0.0200
1.04m
2.60m
5.2
Results
Table Results of SAG Local Search w.r.t. existing baselines. We evaluate the models on 10,000
TSP 100 instances and 128 TSP 200 instances. Baselines include GAT-RLI: Deudon et all [208;;
GAT-RL2: Kool et all [201;;; GCN-SLI: loshi at
[2019]]; POMO:
Kwon all [2020] and Att-
GCRN En et all 2021]
TSP100
TSP200
Method
Type
Length
Gap (%)
Time
Length
Gap (%)
Time
Concorde
Solver
7.7609
0.0000
1.04h
10.7191
0.0000
3.44m
Gurobi
Solver
7.7609
0.0000
3,57h
10.7036
-0.1446
40.49m
LKH3
Heuristic
7.7611
0,0026
49.96m
10.7195
0.0040
2.01m
GAT-RLI
RI,
8.8372
13.8679
47.78m
13.1746
22.9079
4.84m
RI. S
GAT-RL1
8.2449
6,2365
4.95h
11.6104
8.3159
9.59m
2-OPT
GAT-RL2
RL, S
7.9735
2.7391
1,23h
11.4497
6.8160
4.49m
GAT-RL2
RL, G
8.1008
4.3791
1.83m
11.6096
8.3081
5,03s
GAT-RL2
RL, BS
7.9536
2.4829
1.68h
11.3769
6.1364
5.77m
GCN-SLI
SL,
8.4128
8.3995
11.08m
17.0141
58.7272
59.11s
GCN-SLI
SL, BS
7,8763
1.4828
31.80m
16.1878
51.0185
4.63m
GCN-SLI
SL, BS*
7.8719
1,4299
1.20h
16,2081
51.2079
3.97m
POMO
RL
7.77
0.14
Im
SLARL
3,94m
20.62s
Att-GCRN
7.7616
0.0096
10.7358
0.1563
MCTS
5.25m
1.33m
5.68m
0.56m+
UTSP (ours)
UL. Search
7.7608
-0,0011
10.7289
0.0918
5.21m
1.1
Table Table and Table present model's performance on TSP 20, 50, 100, 200, 500 and 1,000. The first three lines in the tables summarize the performance of two exact solvers (Concorde and Gurobi) and LKH3 heuristic Helsgaun [2017]] The learning-based methods can be divided into RL sub-category and SL sub-category. Greedy decoding (G), Sampling (S), Beam Search (BS), and Monte Carlo Tree Search are the decoding schemes used in RL/SI.. The 2-OPT' greedy local search heuristic.

---

Table 3: Results of SAG Local Search w.r.t. existing baselines. We evaluate the models on 128
TSP 500 instances and 128 TSP 1000 instances. Baselines include GAT-RLI: Deudon et all [00]]
GAT-RL2: Kool etall [20%; GCN-SLI: Joshretal [2019]]; DIMES:
Quu et [022]; DIFUSCO:
Sun and Yang 212 and At-GGRRN Eu ei all [2021]]
TSPS00
TSP1000
Method
Type
Length
Gap (%)
Time
Length
Gap (%)
Time
Concorde
Solver
16.5458
0,0000
37.66m
23.1182
0.0000
6.65h
Gurobi
Solver
16.5171
-0.1733
45.63h
LKH3
Heuristic
16.5463
0.0029
11.41m
23.1190
0.0036
38.09m
GAT-RLI
RL, S
28.6291
73.0293
20.18m
50.3018
117,5860
37.07m
RL, S
GAT-RLI
23.7546
43,5687
57.76m
47.7291
106.4575
5.39h
2-OPT
GAT-RL2
RI,
22.6409
36.8382
15.64m
42.8036
85.1519
63.97m
GAT-RL22
RI, G
20.0188
20,9902
1.51m
31.1526
34.7539
3.18m
GAT-RL22
RI, BS
19.5283
18.0257
21.99m
29.9048
29.2359
1.64h
GCN-SL.
SL, G
29.7173
79.6063
6.67m
48.6151
110,2900
28.52m
GCN-SLI
SL, BS
30,3702
83.5523
38.02m
51.2593
121.7278
51.67m
GCN-SLI
SL, BS
30.4258
83.8883
30.62m
51.0992
121.0357
3.23h
DIMES
RL+S
18.84
13.84
1.06m
26.36
14,01
2.38m
DIMES
RL+MCTS
16.87
1.93
2.92m
23.73
2.64
6.87m
DIMES
RLAAS+MCTS
16.84
1.76
2.15h
23.69
2.46
4.62h
DIFUSCO
SLAMCTS
16.63
0.46
10.13m
23.39
1.17
24.47m
SL+RL
31.17s +
43.94s +
Att-GCRN
16.7471
1.2169
23,5153
1.7179
MCTS
3.33m
6.68m
1.37m +
3,35m+
UTSP (Ours)
UL, Search
16.6846
0.8394
23.3903
1.1770
1.33m
2.67m
We compare our model with existing solvers as well as different learning-based algorithms. The performance of our method is averaged of four runs with different random seeds. The rumning time for our method is divided into two parts: the inference time (building the heat map 7() and the search time (rumning search algorithm).
On small instances, our results match the ground-truth solutions and generate average gaps of -0.00009 %, -0.002% and -0.00011 % respectively on instances with 20, 50, 100, where the negative values are the results of the rounding problem. The total runtime of our method remains competitive w.r.t. all other learning baselines. On larger instances with 200, 500 and 1, 000, we notice that traditional solvers (Concorde, Gurobi) fail to generate the optimal solutions within reasonable time when the size of problems grows. For RL/SL baselines, they generate results far away from ideal solutions, particularly for cases with n = 1, 000. Our UTSP method is able to obtain 0.0918%, 0.8394% and 1.1770% on TSP 200, 500 and 1, 000, respectively. We remark that UTSP outperforms the existing learning baselines on larger instances (TSP 200, 500, 1000) D More discussion between Fü all [202T]] and UTSP can be found in Appendix C
Our model takes less training time than RIJ/LI method because we require very few training in- stances. Taking TSP 100 as an example, RI/SI. needs 1 million training instances, and the total training time can take one day using a NVIDIA V100 GPU, while our method only takes about 30 minutes with 2,000 training instances. The training data size does not increase w.r.t. TSP size. Our training data consists of 2,000 instances for TSP 200, 500 and 1,000. At the same time, the UTSP model also remains very lightweight. On TSP 100, units and the model consists of 44,392 trainable parameters. In contrast, RL method Kool et all [ takes approximately 700,000 parameters and the SL method in Iloshi all [022 takes ap- proximately 350,000 parameters.
2-layer SAG with 64 hidden
5.3 Expressive Power of GNNs
Our UL method generalizes well to unseen examples without requiring a large number of training samples. This is because the loss function in Equation Ø is fully differenniable w.rt. the parameters
On 500, when we increase the time budget for Search, achieve 0.42% in 1.37m 8.32m.
7

---

in SAG and we are able to train the model in an end-to-end fashion. In other words, given a heat
100
SAG (Training)
80
SAG (Validation)
Loss
GCN (Training)
60
GCN (Validation)
40
0
20
40
60
80
100
Epoch
Figure 2: TSP 100 training curve using Unsupervised Learning surrogate loss. We compare two GNN models: GCN Kıpt and Welling [2016] and SAG Min et al. [2022]. where GCN is low-pass model and SAG is low-pass + band- hand-pass model.
map H. the model learns to assign large weights to more promising edges and small weights to less promising ones through backpropagation without any prior knowledge of the ground truth or any exploration step. However, when using SL, the model learns from the TSP solutions, which
fails when multiple solutions exist or the solutions are not optimal Li et all [2018]. While for RL, the model often encounters an exploration dilemma and is not guaranteed to converge [Begioo aa loshh et aD [20196]] Overall, UTSP requires fewer training samples and has better generalization compared to SL/RL models.
We aim to generate non-smooth soft indicator matrix T and build an expressive heat map Ht to guide the search algorithm. However, most GNNs aggregate information from adjacent nodes and these aggregation steps usually consist of local averaging operations, which can be interpreted as a low-pass filter and causes the oversmoothing problem Wenkel [2022]. The low-pass model generates a smooth soft indicator matrix T,, which finally makes the elements in H become indistin- guishable. So it becomes difficult to discriminate whether the edges belong to the optimal solution not. In model, we assume all nodes in the graph connected, every node has 1 con- nected to neighbouring nodes. This means every node receives messages from all other nodes and we have global averaging operation over the graph, this can lead to severe oversmoothing issue.
To avoid oversmoothing, one solution is to use shallow GNNs. However, this would result nar- row receptive fields and create the problem of underreaching Barceló et all [202M] Our model uses SAG because this scattering based method helps overcome the oversmoothing problem by combin- ing band-pass wavelet filters with GCN-type filters Min all [2022]. Figure Z illustrates the training loss on TSP 100 and the differences between our SAG model and the graph convolutional network (GCN) Kipf and Welling [2016], where GCN only performs low-pass tow-pass filtering
graph signals IN and Machare [2019]. When using GCN, the training loss decreases slowly, and the validation loss reaches plateau after train the model for 20 epochs. This is because the low-pass model gen- crates a smooth T. Such a smooth results an indistinguishable H. detrimentally impacting the training process. Instead, observe lower training and validation loss when using SAG; this suggests that SAG generates a more expressive representation which facilitates the training process.
Figure E illustrates the generated heat maps using GCN and SAG on TSP 100 instance, we choose this instance from the validation set randomly. When using the GCN, due to oversmoothing prob- lem, the model generates smooth representation and H becomes indistinguishable. The elements in H have small variance and most them are 0.01. Instead, the SAG generates a discriminative representation and the elements in the heat map have a larger variance.

---

76
0.175
0.014
0.150
0.012
26
26
0.125
0.010
0.100
0.008
51
51
0.006
0.075
76
0.004
76
0.050
0.002
0.025
0.000
0.000
Figure 3: Left: The heat map H generated using GCN TSP 100. The diagonal elements are set to O. X-axis and y-axis are the city indices, right: The heat map H generated using SAG on TSP 100. The diagonal elements set to O. X-axis and y-axis are the city indices.
Here, train both GCN and SAG with the same loss function. So the differences illustrated in Figure are the direct result of overcoming the oversmoothing problem.
Search Space Reduction
To understand what happens during training process, we study how the prediction edge IT changes with training time. As mentioned, let denote undirected edge set in H'' and denote the ground truth edge set, 77 I'' [1|/L[ the extent of how good our prediction set II covers the solution I. If 77 1, then I' is a subset of I1, which means our prediction edge set successfully covers all ground truth edges. Similarly, r 0.95 means cover 95% ground truth edges.
Overlap Coefficient
1.0
Number of Instances
600
SAG (Validation) (Validation)
SAG (Validation)
400
GCN (Validation)
0.4-
20
40
50
80
100
Epoch
Epoch
Figure 4: Left:Average edge overlap coefficient 7) w.r.t. training epochs using SAG and GCN on TSP 100 (M = 10), right: Number of fully covered instances w.r.t. training epochs using SAG and GCN on TSP 100. The validation set consists of 1,000 samples (M 10).
Figure shows how the average overlap coefficient y changes with training epochs. We calculate the coefficient based on 1,000 validation instances in TSP 100. We notice that the coefficient quickly increases to ~ 98% after we train SAG for 10 epochs. This suggests that the surrogate loss suc- cessfully encourages the SAG to put more weights the more promising edges. We also compare the performance with GCN. Since the loss does not decrease significantly during our training when using GCN (shown in Figure A), it is not surprising to the average overlap coefficient of GCN always maintains at a relatively low level. After training the model for 100 epochs, SAG model has average coefficient of 99. 79.756% while GCN only has 33.893%.
We then study the number of cases where our prediction edge set covers the ground truth solution. Figure g (right) illustrates how the number of fully covered instances (n 1) changes with time.

---

After training the model for 100 epochs, we observe 780 fully covered instances in 1,000 validation samples using SAG while 0 instances using GCN. Finally, we calculate the average of size [II], Our results show that SAG has an average size of 583.134 edges, while for GCN, the number is 738.739
These results also indicate correspondence between the loss and the quality of prediction. In most SL tasks such as classification or regression tasks, a smaller validation loss usually means we achieve better performance and the minimum of the Ioss corresponds the optimal solution (100% accuracy). However, there is no theoretical guarantee that our loss in Equation 2 also measures the solution quality. Our empirical results demonstrate that lower surrogate loss encourages the model to assign larger weights on the promising edges and reduces the search space. This implies that we can assess the quality of the generated heat maps using our loss in Equation
Overall, the UL training reduces the search space from 4950 edges to 583.12 134 edges with over 99% overlap accuracy on average. This helps explain why our search algorithm is able perform well within reasonable search time.
7 Conclusion
In this paper, we propose UTSP, an Unsupervised Learning method to solve the TSP. We build a surrogate loss that encourages the GNN to find the shortest path and satisfy the constraint that the path should be a Hamiltonian Cycle. The surrogate loss function does not rely any labelled ground truth solution and helps alleviate sparse reward problems RL. UTSP uses a two-phase strategy. We first build heat map based on the GNN's output. The heat map is then fed into search algorithm. Compared with RL/SL, our method vastly reduces training cost and takes fewer training samples. We further show that our UL training helps reduce the search space. This helps explain why the generated heat maps can guide the search algorithm. On the model side, our results indicate that low-pass GNN will produce an indistinguishable representation due the oversmoothing issue, which results in unfavorable heat maps and fails to reduce the search space. Instead, after incorporating band-pass operators into GNN, can build efficient heat maps that successfully reduce search space. Our findings show that the expressive power of GNNs is critical for generating non-smooth representation that helps find the solution.
In conclusion, UTSP is competitive with or outperforms other learning-based TSP heuristics in terms of solution quality and running speed. In addition, UTSP takes 10% of the number of parameters and 0.2% of (unlabelled) training samples, compared with RL or SL methods. Our UTSP framework demonstrates that by providing surrogate loss and a GNN which encourages non-smooth representation, we can learn the hidden patterns in TSP instances without supervision and further reduce the search space. This allows to build heuristic by exploiting small amount of unlabelled data. Future directions include designing more expressive GNNs (such as adding edge features) and using different surrogate loss functions. We anticipate that these concepts will extend to more combinatorial problems.
8 Acknowledgement
This project is partially supported by the Eric and Wendy Schmidt Al in Science Postdoctoral Fel- lowship, a Schmidt Futures program; the National Science Foundation (NSF) and the National In- stitute of Food and Agriculture (NIFA); the Air Force Office of Scientific Research (AFOSR); the Department of Energy; and the Toyota Research Institute (TRI).
References
David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. Concorde tsp solver, 2006.
Keld Helsgaun. An effective implementation of the lin-kernighan traveling salesman heuristic. Eu- ropean journal of operational research, 126(1): 16--130, 2000.
Yeong-Day -aa Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances Neural Information Processing Systems, 33:21188-2 11111188-111.... 2020.
10

---

Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinato- rial optimization problems. arXiv preprint arXi::2210.01123. 2022.
Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimiza- tion. arXiv preprint 202.02230..08244, 2023.
Chaitanya Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprini arXiv:1906.01227 2019a.
Zhang-Huu Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large tsp instances. Proceedings of the AAAI Conference on Artificial Intelligence, 35(8):7474 7482, 2021.
Wouter Kool, Herke Hoof, and Max Welling. Attention, learn solve routing problems! In In- ternational Conference on Learning Representations, 2019. URL https://openrevien net/
Korum/1d=Byp Id=BBXBBSRQQT
Yimeng Min, Frederik Wenkel, Michael Perlmutter, and Guy Wolf. Can hybrid geometric scattering networks help solve the maximum clique problem? Advances in Neural Information Processing Systems, 35:22713-22724 2022.
Georges A Croes. A method for solving traveling- salesman problems. Operations research, 6(6): 791-812, 1958.
Carla Gomes, Bart Selman, Henry Kautz, al. Boosting combinatorial search through random- ization. AAAI/IAA,, 98:431-437, 1998.
John L Bresina. Heuristic-biased stochastic sampling. In AAAI/IAAI, Vol. 1, pages 271-278, 1996.
Carla P Gomes, Bart Selman, Nuno Crato, and Henry Kautz. Heavy-tailed phenomena in satisfiabil- ity and constraint satisfaction problems. Journal of automated reasoning, 24(1):67-100, 2000.
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristies for the tsp by policy gradient. In International Conference on the Integration of Constraint Programming. Artificial Intelligence, and Operations Research, pages 170-181. Springer, 2018
Keld Helsgaun. An extension of the lin-kerighhan-hllee helsgaun tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, pages 24-50, 2017.
Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning the
travelling salesperson problem requires rethinking generalization. Constraints, pages 1-29, 2022.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 1rXiv:1609.000 (00.60099000.. 2016.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems, pages 339-548, 2018.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: a methodological tour dhorizon. European Journal of Operational Research, 290(2): 405-421, 2021.
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. On learning paradigms for the travelling salesman problem. aixiv preprint arXiv:I910.0720 2019b.
Frederik Wenkel, Yimeng Min, Matthew Him, Michael Perlmutter, and Guy Wolf. Overcoming oversmoothness graph convolutional networks via hybrid scattering networks. arXiv preprint arXiv:2201.08932, 2022.
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan-Pablo Silva. The logical expressiveness of graph neural networks. In 8th International Conference on Learning Representations (ICLR 2020), 2020.

---

Hoang Nt and Takanori Machara. Revisiting graph neural networks: All we have is low-pas waw-pssssas filters. arXiv preprint 1505.099000955000 2019.
James Joseph Sylvester. The Collected Mathematical Papers of James Joseph Sylvester..., volume University Press, 1909.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 141.6994,, 2014.
12

---

A Discussion
A.1 Definition of heat map
We can write H. as:
H = TVT",
where
0
0
0
0
0
0
:
1
V
0
0
1
0
0
0
1
0
0
0
0
0
0
0/
the Sylvester shift matrix Sylvester [1999]] V E R
We can interpret V a cyclic permutation
operator that performs a circular shift.
A.2
Unsupervised Loss
We can also write Equation / in a more compact form:
11
C A E Th - 1=1
D H
(4)
f=1
Minimize
where DD= XzIn, In E R= is the identity matrix.
Table Search parameters for all the TSP experiments.
8
M
K
T
TSP-20
0
10
8
10
60
TSP-50
0
10
8
[5, 15)
150
TSP-100
0
10
8
[5)
300
TSP-200
0
10
8
[10, 90)
600
TSP-500
0
50
5
[30, 130)
1000
TSP-1000
0
50
5
[10, 110)
2000
B Training and Search Details
We train our model using Adam Kingma and Ba [014]. All models are trained using Nvidia V100 GPU. All the search-related parameters listed in Table EL M is the size of the candidate set of each city. K is the maximal number of edges we can remove in one action, and for each round of local search, actions we will try to expand one node. Here, we set a = to show that our unsupervised model generates an informative heat map. Lower a means the local search algorithm focuses more on the edges with higher heat map value. Actually, in the experiments, we find the results are similar with 1.
randomly select one number from the listed interval. T' is the total number of
C Running Time Discussion
As discussed in Kool et all [201%) running time important but hard to compare since is affected by many factors. In the table M we report the time for solving all the test instances.
13

---

For the UTSP (our method) and the state-of-the the-the-att art leamnin--aas bbatn method Att-GCRN En ct all [202T], we run the search algorithm on exactly the same environment (one Intel Xeon Gold 6326) for fair comparison. And for other baselines, we refer to the results from el [202]]. So, the time there is only for indicative purposes since the computing hardware different.
D Proof
Lemma D.1. Let q; denote the row index of the non-zero element in i-th column in T, Tq,
E (1,2,3, 3, 4, n.). When each row and column in T have one value (True) and 1 value 0
(False), then qi qj if and only if
Proof. If there exist a (1,j) pair where yi qj when i + j. then T.. 1 and Taps Ta: 1. This means 9-tth row has two non-zero elements, which leads to a contradiction.
Lemma D.2. Consider graph 9 with a nodes, for any T E Ruxa with Tiy 2 O, when each row and column in T. have one value (True) and 1 value 0 (False). Then, each row and column in H also have one value 1 (True) and value 0 (False), which means each city corresponds to only one beginning point and one ending poins.
Proof. First, it is clear that for Va, b, Ha,b Zzo. Let's assume Ta,1 To.m 1(a # 6, m).
since H4s = Ek=n
n): we then have
n
n
Hajj
T Ta J. [(mod
1=1
j j=1
T To,
j. n)
j=1
Ta.k =1.
This implies that the summation of each row in H Similarly,
Higb
Te Tr.To. To,4 ((mod n)
T D. bmood a)
E Tek)
k=1
To Tb 1.mol(mmo n) 1.
This suggests the summation of each column in H is 1. Since each element in Higj E Zzo. we can then conclude that each row and column in have one value (True) and n value (False). Also, Hi === Ti (mod n) Ti, = 0, this indicates that the elements in the main diagonal of H. are 0, which implies no self-loops.
R
As mentioned, the i-th row in H is the probability distribution of directed edges start from city i, and the j-th column the probability distribution of directed edges end in city j. Because each and column in H have one value 1 (True) element and H's Hss diagonal entries are all zero, this means that each city is the beginning point of one directed edge and is also the ending point of another different directed edge.
Lemma D.3. There is at least one cycle in which contains n. edges and visits all cities when each row and column in T have one value I (True) and n 1 value O (False).
14

---

1
k
1
k
k x+1
1
π - 1
1
2
3
4
n
n
n
Figure 5: Illustration of building cycle from transition matrix T. Here 9a-1 3, yn n 2.
g++1 = 2, 9n-1 1 1, In = n and Qi 4, this means H contains the following four directed edges: 3 3 n 2, nl 2 - 2, + and -> 4.
Proof. Lemma DJI indicates that q. qj when i # and qi (1,2,3,4,....1) then -0_1 {1,2, 2, 4, 4,..,,,,,,,,,,,, n). From Equation B we have
Hqiqui
qi ++
T To ge ++ [mod m)
1.
Using Lemma DТ since each row and column in H have one value 1 (True) and n 1 value 0
(False), suffices to show that 1 2 Hqugge1 2 1, therefore Hg. 11 = 1. This suggests that there write C as
directed edge from city % to gi+1- We can then construct cycle from H.
91 42 03 + +
+ 41
where + is a directed edge. Since U = 2, 4,... n). cycle visits all n cities and have n edges. One example of how to build Hg.444 from T is shown in Figure B.
Corollary D.4. H represents one Hamiltonian Cycle when each row and column in T. have one value 1 (True) and n value 0 (False).
Proof. From Lemma D.3. cycle C contains edges and visits all cities, if there exists another edge (i,j) which does not belong to then city is the starting point of least two edges and city is the ending point of at least two edges. This results in a contradiction with Lemma D Thus, suffices to conclude that C' visits each city exactly once and H. only contains the edges in This implies that H represents one Hamiltonian Cycle.
15


Reviews:
[{"review_id": "nfxOn45gNM", "reviewer": "Reviewer_vHRb", "summary": "The paper proposes an unsupervised learning-based heuristic to solve the Travelling Salesman Problem. The approach consists of two steps: first a GNN is trained using a surrogate loss to output a heatmap of the edges then the heatmap is used to guide a local search heuristic. The proposed model has significantly less parameters than similar previous methods and its training is very efficient. It is tested on TSP instances with up to 1000 nodes.", "questions": "1. The paper says “Such SL models scale poorly to the big instances” while the approach of [Fu et al 2021] scales remarkably well to instances with up to 10,000. Maybe the authors meant *training* such SL models does not scale?\n\n1. Have the authors tried their model on even larger instances, such as TSP10000?\n\n1. Would the approach apply to the non-Euclidian asymmetric version of the TSP?\n\n1. It would be useful to discuss how the temperature parameter (L73) and the number M (of elements to keep in each row of the heatmap) are fixed. In particular, how is the search space reduction (Sec. 5) affected by the choice of M?\n\n1. L156 “when selecting the city v given u , we only consider the cities from the candidate set of v” —> do you mean the candidate set of *u* instead?\n\n1. “the negative values are the results of the rounding problem” can the authors elaborate on what is meant by the rounding problem?", "limitations": "The limitations are not explicitly mentioned in the paper.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "1. The paper introduces a light-weight model and sample-efficient training procedure to learn a TSP heuristic\n1. Novel idea of a differentiable surrogate loss that encourages the solution to form a hamiltonian cycle \n1. Nice discussion and motivation of the choice of the GNN and precise comparison between GCN and SAG\n1. The paper is clear and easy to follow", "weaknesses": "1. The main weakness is the limited scope: the paper is very specialized to the TSP, esp. the proposed surrogate loss is specific to the TSP.\n1. Missing some related work: e.g. [1] and [2] and the associated baselines in the experiments. These are known to be much stronger baselines than the ones presented in Tables 1-3.\n1. Some unfounded claims:\n    * The paper says “Such SL models scale poorly to the big instances” while [Fu et al 2021] scales remarkably well to instances with up to 10,000. \n    * L198 “We remark that the UTSP takes a shorter total running time (inference + search) and outperform the existing learning baselines on these large instances. ” But the reported computation times are not shorter than Att-GCRN for TSP200 and TSP50.\n    * L216: “when using SL, the model learns from the TSP solutions, which fails when multiple solutions exist or the solutions are not optimal.” Is there any proof/reference to motivate this statement?\n    * L194 “On larger instances with n = 200, 500 and 1, 000, we notice that traditional solvers and heuristics (Concorde,Gurobi and LKH3) fail to generate the optimal solutions within reasonable time when the size of problems grows”. I’m not sure what is meant exactly, since we see for e.g. in Table 3 that LKH still gives the best optimality gap for TSP1000 in 38minutes. Then for Gurobi, I wonder what was the time limit. Since it is an exact solver, it is expected to be slow. However it should return the best solution it found when it reaches the time limit. Can the authors give more details about the results (or lack of) with Gurobi.\n1. The columns TSP200 in Tab 2 and TSP500 in Tab 3 look exactly the same. Is it a typo?\n1. Many components in the approach and there is only one kind of ablation for the choice of SAG versus GCN for the model architecture. It would be interesting to do precise ablations, esp. for the quality and role of the heatmap in the final results. For example by applying the same local search strategy with the heatmap obtained by other models such as the GCN approach of [Joshi et al 2019a] or the Att-GCRN of [Fu et al 2021].\n1. Experiments only on synthetic instances of the same distribution as training. Could be interesting to test on unseen distributions, e.g. TSPlib.\n\n\n[1] Qiu et al, DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems, NeurIPS 2022\n\n[2] Kwon et al POMO: Policy Optimization with Multiple Optima for Reinforcement Learning, NeurIPS 2020", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q**: The main weakness is the limited scope: the paper is very specialized to the TSP\n\nA: TSP stands as one of the 21 NP-complete problems outlined by Karp [Karp].  TSP holds a foundational position in the field of combinatorial optimization owing to its  essence and practical utility. TSP is also fundamentally important within theoretical computer science and operations research domains. In this paper, we demonstrate that we can build unsupervised learning-based heuristics for the TSP, without the need for labeled ground truth solutions (supervised/imitation learning) or reliance on the framework of Reinforcement Learning (RL). We consider this to be a significant advancement.\n\n[Karp] Karp, Richard M. (1972). \"Reducibility Among Combinatorial Problems\" \n\n\n**Q**: Missing some related work:\n\nA: we add new baselines and section, refer to the table in the one page rebuttal pdf.\n\n**Q**: The paper says “Such SL models scale poorly to the big instances” while [Fu et al 2021] scales remarkably well to instances with up to 10,000.\n \t\nA: In [Fu et al.], the model is trained on the small graph and only generates a small heat map, such as for 20 cities or 50 cities. They train the model (in a supervised manner) at a small scale. They apply a series of techniques, such as graph sampling, graph conversion, and merging heat maps. This means that when dealing with large instances such as TSP 200, 500, and 1000, their model always generates a heat map of size 50 by 50, and then the sub heat maps are merged together. Please refer to the Methodologies section in [Fu et al.] for more details.\t\n\t\t\t\n\n**Q**: L198 “...not shorter than Att-GCRN for TSP200 and TSP50.\n\n\t\t\nA: “On large instances”we mean TSP 500 and TSP 1000, refer to the table in the one page rebuttal pdf., we will revise this sentence and add more discussion on the performance.\n\n\n\n**Q**: L216: “when using SL, ...Is there any proof/reference to motivate this statement?\n\nA: In [Li et al.], Section 4.2 \n... when there are multiple optimal solutions for the same graph. ..., two equivalent optimal solutions that induce completely different labellings., …which is not a useful labelling. \nWe will add [Li et al.] into reference.\n\n[Li et al.] \"Combinatorial optimization with graph convolutional networks and guided tree search.\" Advances in neural information processing systems 31 (2018). https://arxiv.org/pdf/1810.10659.pdf\n\n**Q**: L194 ...Can the authors give more details about the results (or lack of) with Gurobi.\n\nA: On TSP 1000 we tried set time limit as LKH running time (38.09m), Gurobi returns a ~18% Gap.\n\n**Q**: The columns TSP200 in Tab 2 and TSP500 in Tab 3 look exactly the same. Is it a typo?\n\nA: We fix the typo, we update the performance in the one page rebuttal pdf.\n\n**Q**: Many components in the approach and there is only one kind of ablation...\n\nA: We include ablation studies to examine how changes in the search hyperparameters affect performance. This is shown in \"Table: Search Hyperparameter Ablation Study on TSP 100\" and \"Table: Search Hyperparameter Ablation Study on TSP 1000\". A lower value of $\\alpha$ indicates that the local search algorithm prioritizes edges with higher heat map values, whereas a higher value of $\\alpha$ aligns more with an MCTS style, similar to the approach described in [Fu et al., 2021].\n\t\n**Q**: Experiments only on synthetic instances of the same distribution as training. Could be interesting to test on unseen distributions, e.g. TSPlib.\n\nA: The objective of this paper is to demonstrate the applicability of UL for the TSP. To assess our model's performance, we conducted evaluations on the same datasets used in [Fu et al., 2021], which serves as our primary baseline. We leave the exploration of TSPlib datasets to future research work.\n\n**Q**: Have the authors tried their model on even larger instances, such as TSP10000?\t\n\nA: Regarding TSP-10000, It is important to highlight that for the TSP-10000 evaluation, these studies [1, 2, 3] also use the same test dataset containing only 16 samples. Consequently, due to the limited size of the dataset, the performance results may not be a reliable indicator. Using the graph sampling technique suggested in [3], we evaluate UTSP and achieve ~3.05% gap in approximately 1 hour. For reference, [3] reported a 4.3% gap in 21 minutes, DIMES achieved a 4.0% gap in 30 minutes, and 3.2% gap in 3.5 hours. DIFUSCO outperforms all others, as it reports the best performance with a 2.5% gap and a time cost of 47 minutes.\n\n[1] DIMES: A differentiable meta solver for combinatorial optimization problems. \n[2] DIFUSCO: Graph-based diffusion solvers for combinatorial optimization. \n[3] Generalize a small pre-trained model to arbitrarily large tsp instances. \n\t\t\t\n\t\t\n**Q**: Would the approach apply to the non-Euclidian asymmetric version of the TSP?\n\nA: Modify the distance matrix $\\mathcal{D}$ in Equation (2) to make it asymmetric.\n\n\n**Q**: It would be useful to discuss ... how is the search space reduction (Sec. 5) affected by the choice of M?\n\nA: We will add discussion on that, overall, increasing $M$ will have more overlapped cases. But then the search space is larger because we consider more possible edges.\n\n**Q**:  L156 “when selecting the city v given u ...\n\nA: Here the candidate set of v means We only select city v from the top M heat map value or the nearest M cities. We will revise this sentence.\n\n\n**Q**: “the negative values are the results of the rounding problem”... what is meant by the rounding problem?\n\nA: Rounding problem: On many instances, the best known solutions reported by Concorde are not strictly optimal (confirmed in (Joshi et al., 2019), possibly due to round-off reasons), which could be slightly improved (< 10−2 ) by our algorithm (Fu et al., 2020). \t\t\n\nFu et al., 2020: Targeted sampling of enlarged neighborhood via Monte Carlo tree search for TSP \n"}, {"review_id": "UWwv9xLazg", "reviewer": "Reviewer_X3D7", "summary": "This paper proposed a novel unsupervised learning method for solving the Travelling Salesman Problem (TSP). It employs a Scattering Attention GNN (SAG) to encode the node information. Then, the learned representation is transformed into a heatmap, which corresponds to the probability of an edge being included in the optimal solution. A novel unsupervised loss is proposed. Based on the learned heatmap, a local search procedure with randomness is used to derive the final solution. Experiments on TSP instances up to 1000 nodes show that the proposed method can use much less training data, and outperforms several existing deep TSP models.", "questions": "Please see the above weaknesses.", "limitations": "The propossed approach is limited to TSP. But this is not a severe limitation since it obtains good results on large-scale problems. It would be better to have some discussions on how to generalize the idea to support other routing problems.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The research motivation is clear.\n\n2. The idea of using SAG to build heatmap, and the proposed unsupervised loss is interesting.\n\n3. Strong empirical performance, with detailed analysis on the expressive power of SAG. \n\n4. Generally good writing and organization.", "weaknesses": "1. Since the proposed method is heatmap based, I suggest to give a detailed review and discussion on heatmap based methods, such as [Fu2021], [Qiu2022], [Joshi2022]. Currently the introduction is mainly from the SL/RL perspective.\n\n2. For fair comprison, I suggest to add some ablation studies on the effect of local search. In the main results (Tables 1-3), it is unclear whether the performance improvement is from the better learning mechanism, or the local search procedure. In addition, the baselines use sampling, beam search and Monte carlo tree search as the decoding strategies, while the proposed method uses local search. This also makes it difficult to compare the effectiveness of the learning mechanism. While Figure 4, 5 and 6 provide some insights, they are still indirect results.\n\n3. The baselines are not up-to-date. It would be much stronger if state-of-the-art methods, such as DIMES [Qiu2022] (also a heatmap based method), could be compared.\n\n4. It is unclear how the training data is generated and whether the baselines are retrained. I guess they are not since GAT [Kool2019] and GCN [Joshi2019] is known to be hard to scale to problem of size 1000.\n\n5. More detailed results on the training efficiency (e.g., a table) could be helpful. Currently only an informal discussion is given on Page 6. \n\n6. The local search mechanism relies on randomness. But how it impacts the results is unclear, including how stable the performance is (std is helpful if reported), and what if no randomness is used.\n\n7. The runtime in Table 2 seems incorrect. For the baselines, most runtime for TSP200 is much faster than TSP100. For your approach, the runtime for TSP200 is faster than TSP50. Please thoroughly check the results.\n\n8. The proposed approach is currently limited to TSP. It would be better to have some discussions on how to extend it to other typical routing problems such as CVRP.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please check the “replies to all reviewer” and the one page rebuttal pdf.\n\n**Q** Since the proposed method is heatmap based, I suggest to give a detailed review and discussion on heatmap based methods, such as [Fu2021], [Qiu2022], [Joshi2022]. Currently the introduction is mainly from the SL/RL perspective.\n\nA: We will  add a related works section and will revise the introduction.\n\n**Q** For fair comprison, I suggest to add some ablation studies on the effect of local search. In the main results (Tables 1-3), it is unclear whether the performance improvement is from the better learning mechanism, or the local search procedure. In addition, the baselines use sampling, beam search and Monte carlo tree search as the decoding strategies, while the proposed method uses local search. This also makes it difficult to compare the effectiveness of the learning mechanism. While Figure 4, 5 and 6 provide some insights, they are still indirect results.\n\nA: We include ablation studies to examine how changes in the search hyperparameters affect performance in the one page rebuttal pdf. This is shown in \"Table: Search Hyperparameter Ablation Study on TSP 100\" and \"Table: Search Hyperparameter Ablation Study on TSP 1000\". A lower value of $\\alpha$ indicates that the local search algorithm prioritizes edges with higher heat map values, whereas a higher value of $\\alpha$ aligns more with an MCTS style, which is similar to the approach described in [Fu et al., 2021].\n\nWe also find a better performance on TSP 100, where the gap is -0.0019 %. \n\n**Q**  The baselines are not up-to-date. It would be much stronger if state-of-the-art methods, such as DIMES [Qiu2022] (also a heatmap based method), could be compared.\n\nA: we add new baselines, refer to the one page rebuttal pdf.\n\n**Q** It is unclear how the training data is generated and whether the baselines are retrained. I guess they are not since GAT [Kool2019] and GCN [Joshi2019] is known to be hard to scale to problem of size 1000.\n\nA: Regarding the training data, our approach aligns with [Fu et al.]. The training data is randomly generated on a 2D plane, and we adopt the same test data set as outlined in their work.\nFor TSP instances with sizes 20, 50, and 100, the test data comprises 10,000 automatically generated 2D Euclidean TSP instances for each size. This test data set is widely utilized by existing learning-based algorithms.\nOn larger instances with n = 200, 500, and 1000, There are 128 instances for each size.\n\t\t\n\t\t\t\n\t\t\n\nRegarding retrain: \n\t\t \t \t \t\t\t\nSee our manuscript, Line 395 to line 398: For UTSP (our method) and the state-of-the-art learning-based method Att-GCRN Fu et al. [2021], we run the search algorithm on **exactly the same environment (one Intel Xeon Gold 6326)** for a fair comparison. \n\nAnd for other baselines, since GAT [Kool2019] and GCN [Joshi2019] have a noticeable gap from Fu et al. [2021], we directly refer to the results from Fu et al. [2021]. \n\t\t\t\t\t \t\t\t\t\n\t\t\t\n\t\t\n\n**Q**:  More detailed results on the training efficiency (e.g., a table) could be helpful. Currently only an informal discussion is given on Page 6. \n\nA: We will add more discussion in the new manuscript. \n\n**Q**: The local search mechanism relies on randomness. But how it impacts the results is unclear, including how stable the performance is (std is helpful if reported), and what if no randomness is used.\n\nA: Here we compare the performance using restart and without restart on  TSP 100 and TSP 1000, all other hyperparameters are the same.\n\nOn TSP 100, using restart, the gap is -0.0019% and the std is 0.00035%.\n\nOn TSP 100, without restart, the gap is -0.0017% and the std is 0.00025%.\n\nOn TSP 1000, using restart, the gap is 1.1770% and the std is 0.075\n\nOn TSP 1000, without restart, the gap is 1.2163% and the std is 0.38.\n\nThe results indicate that introducing randomness (via restarts) helps enhance performance, and has the potential to eliminate the standard deviation in larger TSP instances, such as TSP 1000.\n\n\n**Q**: The runtime in Table 2 seems incorrect. For the baselines, most runtime for TSP200 is much faster than TSP100. For your approach, the runtime for TSP200 is faster than TSP50. Please thoroughly check the results.\n\nA: We evaluate our performance on the same test dataset used in [Fu et al.] and [Qiu et al.].\nIn that dataset, TSP instances with sizes 20, 50, and 100 have **10,000** test samples each. \nHowever, for TSP instances with sizes 200, 500, and 1000, we have a smaller set of only **128** samples.\n\nThat’s why TSP200 is faster than TSP50 and TSP 100.\n\nThe new performance is included in the table one page rebuttal pdf.\n\n\n**Q** The proposed approach is currently limited to TSP. It would be better to have some discussions on how to extend it to other typical routing problems such as CVRP.\n\nA: A common aspect is that both CVRP and TSP share the objective of minimizing the 'distance'. As a result, we can employ expressions such as $\\sum_{ij} H_{ij}D_{ij}$. We will add a future work section in our manuscript.\n\n\n\nReference:\n\nFu et al. Generalize a small pre-trained model to arbitrarily large tsp instances.\nProceedings of the AAAI Conference on Artificial Intelligence, 35(8):7474–7482, 2021\n\nQiu et al. Dimes:\nDimes: A differentiable meta solver for combinatorial optimization problems.\" Advances in Neural Information Processing Systems 35 (2022): 25531-25546.\n"}, {"review_id": "Yt68w1gPOa", "reviewer": "Reviewer_wEAA", "summary": "The authors propose a continuous relaxation of the 2D Euclidian Travelling Salesman Problem. Specifically, they replace the combinatorial optimization problem with a continuous optimization problem of the form\n\n*Minimize f(A) over all column-stochastic matrices $A \\in \\mathbb R^{n \\times n}$*\n\nwhere $f$ is a smooth function and $A$ is a soft indicator matrix whose $t^{th}$ column indicate the city visited at step $t$ of the tour. The matrix $A$ is obtained via a deep net $A = \\phi_\\theta(X)$ where $X$ contains the position of the cities, therefore leading to a problem of the form\n\n*Minimize $f(\\phi_\\theta(X))$ over $\\theta$*\n\nwhich is optimized via SGD. From the soft indicator matrix $A$, the authors build a hard indicator matrix by performing a local search algorithm.\n\nThe proposed approach significantly differs from RL approaches, since it is based on optimizing a smooth objective. It is also significantly different from imitation learning approaches, in which a neural network is trained to imitate  the output of an accurate but slow solver (typically the Concorde algorithm, which is more or less the default TSP solver in the OR community).    \n\nThe proposed approach outperforms previous RL approaches and imitation learning approaches.  \n\n\n\n\n\n\n\n\n \n\n\n", "questions": "Question1: On line 198 the authors write \n> We remark that the UTSP takes a shorter total running time (inference + search) and outperform the existing learning baselines on these large instance. \n\n I am confused: the algorithm from [1] seems faster. Is it not a learning baseline? Again, I think more discussion about [1] is needed.\n\n\nQuestion 2:  The GCN from Kipf and Welling is the `smoothest' GNN. Did you try other GNN/transformer architecture beyond SAG? \n\n[1] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily\n325 large tsp instances. \n ", "limitations": "I did not find a paragraph about the limitation of the proposed approach. Overall this is a very strong work in my opinion. An honest explanation of the shortcomings of the proposed approach would improve the scientific contribution.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "* The proposed approach is simple and outperforms previous deep learning methods when applied to large TSP instance. \n* The accuracy and sample efficiency achieved by the proposed approach are *very* impressive.\n* The TSP problem is an important and prototypical combinatorial optimization problem. The proposed approach, due to its simplicity and performance, has the potential of becoming quite influential.\n\n", "weaknesses": "1.  A more extensive discussion of the existing literature is needed. In particular, the authors should explain the method presented in [1], as it is the only one that achieves results comparable to the proposed approach.  I would recommend to have a `related work' subsection.\n\n2. The presentation could be improved. In particular I find that referring to the matrix $T$ as a transition matrix is very confusing. $H$ is a transition matrix, since $H_{ij}$ is to some extent the probability of moving from i to j. If I understand correctly the proposed relaxation, the $t^{th}$ column of $T$ is a probability distribution over the cities that indicates what is the city most likely to be visited at step $t$ of the tour. So I would refer to $T$ as a soft indicator matrix. The left side of Figure 3 is confusing: I take it as meaning that if $T$ is used as a transition matrix, then it leads to a non-Hamiltonian cycle. I think it is better to not encourage the reader to think of $T$ as a transition matrix. If $T=[p_1, \\ldots, p_n]$ is viewed as a soft indicator matrix that indicates the city visited at time $t$, then the formula for $H$ can be written as a sum of outer products\\\n$\n\\displaystyle H = \\sum_{t=1}^{n-1} p_{t} p_{t+1}^T + p_{n} p_{1}^T\n$\\\nfrom which it is clear that $H$ is a transition matrix. I think equation (1) and the displayed matrix $V$ are unnecessary and take lots space. Similarly, figure 1, 2 and 3 take lots of space and do not bring much clarity in my opinion. I think the space could be better used by describing related works in more depth, adding context for the experimental results (which are very impressive), and also maybe discussing continuous relaxations in general.  Overall, the proposed strategy is very simple (which I see as a strength): I think it could be presented in a  more concise and cleaner manner.\n\n3. The experimental section could be polished. I think it is important to explain what is the \"gap\" and the \"rounding problem\". (Also line 177 is hard to read, and the first paragraph is not well written.) \n\n\n\n\n\n[1] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily\n325 large tsp instances. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*We update the experiment section in the one page rebuttal pdf.*\n\n**Q**: A more extensive discussion of the existing literature is needed. In particular, the authors should explain the method presented in [1], as it is the only one that achieves results comparable to the proposed approach. I would recommend to have a `related work' subsection.\n\nA: We will revise the introduction part and add a new section, refer to the \"replies to all reviewers\".\n\n**Q**: The presentation could be improved. In particular I find that referring to the matrix... I take it as meaning that if $\\mathbb{T}$ is used as a transition matrix, then it leads to a non-Hamiltonian cycle.\n\nA:  **I take it as meaning that if $\\mathbb{T}$  is used as a transition matrix, then it leads to a non-Hamiltonian cycle.** This is correct!\n\nWe will change the transition matrix to  soft indicator matrix, we rewrite $\\mathcal{H}$ as:\n\n$\n\\mathcal{H} = \\sum_{t=1}^{n-1}p_t p^T_{t+1} + p_np_1^T,\n$\n\nwhere $p_t \\in \\mathbb{R}^{n \\times 1}$ is the $t_{th}$ column of $\\mathbb{T}$, $\\mathbb{T} = [p_1|p_2|...|p_n]$.}\n\nWe remove $\\mathbb{V}$, we will remove some figures (to the appendix)  and add more discussion on related works. \n\n**Q**: The experimental section could be polished. I think it is important to explain what is the \"gap\" and the \"rounding problem\".\n\nA: The gap: given a length and the optimal length $l_{opt}$, the gap is defined as:\n$(l-l_{opt})/l_{opt}$.\n\nRounding problem: On many instances, the best known solutions reported by Concorde are not strictly optimal (confirmed in (Joshi et al., 2019), possibly due to round-off reasons), which could be slightly improved (< 10−2 ) by our algorithm (Fu et al., 2020). \n\nWe will revise the experimental section and add above discussions.\n\t\t\t\n**Q**:  line 177 is hard to read: \n\nA: When we apply the T → H transformation and utilize H as the heat map, we observe that H forms a Hamiltonian Cycle. By minimizing the expression $\\sum_{i=1}^{n} \\sum_{j=1}^{n} D_{i,j} \\cdot H_{i,j}$, we can achieve the shortest Hamiltonian Cycle, which represents the solution to the Traveling Salesman Problem (TSP). \t\t\n\n**Q**:  first paragraph is not well written: \n\nA: As mentioned above, we will revise the introduction part and add a related works section.\n\n\nJoshi et al., 2019: Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227, 2019.\n\nFu et al., 2020: Targeted sampling of enlarged neighborhood via Monte Carlo tree search for TSP \n\n\n**Q**: On line 198 the authors write \nWe remark that the UTSP takes a shorter ...on these large instance...the algorithm from [1] seems faster. Is it not a learning baseline? Again, I think more discussion about [1] is needed.\n\nA: We will add more discussion on [1], Here we mean “large instances”like TSP  500 and 1000. As the problem size increases increases, our method performs better and take have a shorter running time, as summarized here (there is a typo is the TSP 500 column in the original manuscript, which overlap with the TSP 200, we update the performance in the one page pdf rebuttal):\n\nResults of SAG + Local Search w.r.t. existing baselines. We evaluate the models on 128 TSP 500 instances and 128 TSP 1000 instances.\n\n| Method | Type | TSP500 (Length) | TSP500 (Gap %) | TSP500 (Time) | TSP1000 (Length) | TSP1000 (Gap %) | TSP1000 (Time) |\n|--------|------|-----------------|----------------|---------------|------------------|-----------------|---------------|\n| Concorde | Solver | 16.5458 | 0.0000 | 37.66m | 23.1182 | 0.0000 | 6.65h |\n| Gurobi | Solver | 16.5171 | -0.1733 | 45.63h | - | - | - |\n| LKH3 | Heuristic | 16.5463 | 0.0029 | 11.41m | 23.1190 | 0.0036 | 38.09m |\n| GAT \\cite{deudon2018learning} | RL, S | 28.6291 | 73.0293 | 20.18m | 50.3018 | 117.5860 | 37.07m |\n| GAT \\cite{deudon2018learning} | RL, S 2-OPT | 23.7546 | 43.5687 | 57.76m | 47.7291 | 106.4575 | 5.39h |\n| GAT \\cite{kool2018attention} | RL, S | 22.6409 | 36.8382 | 15.64m | 42.8036 | 85.1519 | 63.97m |\n| GAT \\cite{kool2018attention} | RL, G | 20.0188 | 20.9902 | 1.51m | 31.1526 | 34.7539 | 3.18m |\n| GAT \\cite{kool2018attention} | RL, BS | 19.5283 | 18.0257 | 21.99m | 29.9048 | 29.2359 | 1.64h |\n| GCN \\cite{joshi2019efficient} | SL, G | 29.7173 | 79.6063 | 6.67m | 48.6151 | 110.2900 | 28.52m |\n| GCN \\cite{joshi2019efficient} | SL, BS | 30.3702 | 83.5523 | 38.02m | 51.2593 | 121.7278 | 51.67m |\n| GCN \\cite{joshi2019efficient} | SL, BS* | 30.4258 | 83.8883 | 30.62m | 51.0992 | 121.0357 | 3.23h |\n| DIMES \\cite{qiu2022dimes} | RL+S | 18.84 | 13.84 | 1.06m | 26.36 | 14.01 | 2.38m |\n| DIMES \\cite{qiu2022dimes} | RL+MCTS | 16.87 | 1.93 | 2.92m | 23.73 | 2.64 | 6.87m |\n| DIMES \\cite{qiu2022dimes} | RL+AS+MCTS | 16.84 | 1.76 | 2.15h | 23.69 | 2.46 | 4.62h |\n| DIFUSCO \\cite{sun2023difusco} |SL+MCTS | 16.63 | 0.46 | 10.13m | 23.39 | 1.17 | 24.47m |\n| Att-GCRN\\cite{fu2021generalize} | SL+RL MCTS | 16.7471 | 1.2169 | 31.17s + 3.33m | 23.5153 | 1.7179 | 43.94s + 6.68m |\n| UTSP (Ours) | UL, Search | 16.6846 | 0.8394 | 1.37m + 1.33m | 23.3903 | 1.1770 | 3.35m + 2.67m |\n\nWe now add DIMES and DIFUSCO, on TSP 500 and 1000, the new baseline DIMES is able to take a shorter running time, but results in a larger gap, we will revise the this section.\n\n\t\t\n**Q**: The GCN from Kipf and Welling is the `smoothest' GNN. Did you try other GNN/transformer architecture beyond SAG? \n\nA: We tried a graph attention network, but we didn't observe a significant improvement compared to GCN. This could be due to the fact that graph attention networks still rely on averaging features of neighboring nodes for similarity calculations.\nDeveloping specific GNNs targeted for solving TSP is a very important topic,  and we believe that there exists more suitable GNN structures, we will leave it for future discussions.\n\n**Q** limitation of the proposed approach. \n\nA: we will add more discussion about limitation and future works.\n"}, {"review_id": "Ti7O9cVDvF", "reviewer": "Reviewer_su5g", "summary": "This paper proposes UTSP, an unsupervised learning framework, to solve the Travelling Salesman Problem (TSP). It consists of two phases, including heat map construction and local searching. Specifically, a surrogate loss function is proposed to train the GNNs, encouraging the model to find the shortest path and respect the TSP constraint implicitly. The built heat map helps reduce the search space and facilitate the local search afterwards. Empirically, with only ~10\\% model parameters and ~0.2\\% training samples, UTSP is competitive with or outperforms baselines in terms of solution quality and inference time. The analyses about search space and smoothing effect are also conducted.", "questions": "* In line 72, why the weight matrix is set as $W_{i,j}=e^{-D_{i,j}/\\tau}$? I do not see any explanation.\n* In line 80, why do you use column-wise Softmax? How about row-wise Softmax, together with the column-wise constraint in Eq. (2)?\n* Could you add more details (e.,g., model structure) about the Scattering Attention GNN (SAG) in Appendix? Currently, it is unclear how to obtain $\\mathbb{T}$ using $W$ and $F$.", "limitations": "It seems that the authors did not discuss the limitations of this work.\n\nNo negative societal impact.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "* The proposed method (in Section 2) is sound and novel. The theoretical proof (in Appendix) is correct.\n* Technically, the proposed method significantly reduces the model parameters and training samples. It does not need labeled data, and avoids the spare reward problem, making it more attractive to the SL and RL-based methods. \n* The empirical analyses of the non-smoothing heat map and reduced search space are interesting. \n* The source code is provided.", "weaknesses": "* The scope of this paper may be limited, since:\n  * The proposed method seems to be only applicable to TSP.\n  * Much domain knowledge is involved in the local search process.\n  * Too many hyperparameters in the proposed method.\n* The review of related work is *too limited*. Many recent works regarding neural methods for solving TSP are missing. It is suggested to add the related work section in Appendix.\n* The presentation of local search (in Section 3) is not clear. Could you illustrate the process using a figure?\n* The theory of the proposed method in Section 2 is quite interesting. However, there seems to be a gap between the theory and the proposed method. For example, the theory is based on the assumption that only one value 1 and $n-1$ value 0 in each row and column of $\\mathbb{T}$. However, the objective function does not exert an explicit constraint on the discreteness of $\\mathbb{T}$ or $\\mathcal{H}$. Based on the empirical result in Figure 5, the maximum value of $\\mathcal{H}$ is around 0.175. Have you considered adding a regularization term to achieve this objective? \n* Insufficient Evaluation:\n  * *Lack of Baselines:* Several recent end-to-end neural methods needed to be compared, including POMO [1], DIMES [2], and DIFUSCO [3].\n  * *Larger Size:* The evaluation of this paper is conducted on TSP1000 (maximally), while recent works [2, 3, 4] (also heat map based methods) consider TSP10000. It is interesting to see how your method performs on large-scale instances.\n  * *Lack of Benchmark Results:* Results on the classical TSP benchmark dataset (i.e. TSPLIB [5]) are needed.\n* Minor:\n  * The citation format is not correct. The authors could use ~\\cite{}.\n  * In line 57, \"does not\" -> \"our method does not\".\n  * In line 182, \"me thods\" -> \"methods\".\n  * Please change the blue and red colors in Fig. 7 and 8. The current version is indistinguishable.\n  * In line 414, the formulation should be $\\mathcal{H}\\_{i,i}=\\sum\\_{k=1}^{n}\\mathbb{T}\\_{i,k}\\mathbb{T}_{i,k+1(\\text{mod }n)}=0$.\n  * In the caption of Figure 9, add $q_{n-1}=1$.\n  * Remove the Checklist on Page 17.\n\n[1] POMO: Policy optimization with multiple optima for reinforcement learning. In NeurIPS 2020.\n\n[2] DIMES: A differentiable meta solver for combinatorial optimization problems. In NeurIPS 2022.\n\n[3] DIFUSCO: Graph-based diffusion solvers for combinatorial optimization. In arXiv:2302.08224.\n\n[4] Generalize a small pre-trained model to arbitrarily large tsp instances. In AAAI 2021.\n\n[5] http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95\n\n----\n\n**Overall**, despite several limitations, I lean towards borderline acceptance since I like the idea of this paper. It would be a good submission if the authors resolve most of the concerns.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q**: The review of related work is too limited. ... It is suggested to add the related work section in Appendix.\n\nA: We add a new section, refer to the  \"replies to all reviewers\", where we include the recent work of [1][2][3][4].\n\n\n**Q**: The presentation of local search (in Section 3) is not clear. Could you illustrate the process using a figure?\n\nA: We will add a figure (refer to the figure in the rebuttal one page pdf). \n\n**Q**: The theory of the proposed method in Section 2 is quite interesting….Have you considered adding a regularization term to achieve this objective?\n\nA: In our model, the “smoothness” of the signal is implicitly encoded in the GNN part. We use Scattering Attention GNN (SAG), SAG has both low-pass and band-pass  filters. We follow the setting in [Min et.al 2022], where the authors use three low pass filters and three band-pass filters (refer to the figure in the rebuttal one page pdf). The number of band-pass filters determines how ‘discrete’ the signals are. When we exclude band-pass filters (setting them to 0), the GNN only consists of 3 low-pass filters, leading to the occurrence of oversmoothing. Consequently, this results in a heat map similar to Figure 5 left, with most elements in $H$ approximately equal to 0.01.\nUpon adding 3 band-pass filters, the maximum value of $H$ increases to around 0.175. This indicates that incorporating band-pass filters enhances the discreteness of $H$, contributing to its higher values and a more distinguishable pattern.\nOverall, the regularization is integrated into the Scattering Attention GNN model. During our experiment, we observed that increasing the number of band-pass filters (or reducing the number of low-pass filters) results in a higher maximum value for $H$. Further elaboration on this observation will be included in the appendix for additional discussion.\t\t\t\t\t\n\n[Min et.al 2022] Min, Yimeng, et al. \"Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem?.\" Advances in Neural Information Processing Systems 35 (2022): 22713-22724.\t\t\t\t\n\t\t\t\n\t\t\n\t\t\n\t\t\n\n\n**Q**: Lack of Baselines:\n\nA: We compare our model with several recent end-to-end neural methods, including POMO [1], DIMES [2], and DIFUSCO [3] , referring to the official comment. \n\n**Q**: Larger Size\n\nA: Regarding TSP-10000, It is important to highlight that for the TSP-10000 evaluation, these studies [2, 3, 4] also use the same test dataset containing only 16 samples. Consequently, due to the limited size of the dataset, the performance results may not be a reliable indicator. By employing the graph sampling technique suggested in [4], we evaluate UTSP and achieve ~3.05% gap in approximately 1 hour. For reference, [4] reported a 4.3% gap in 21 minutes, DIMES achieved a 4.0% gap in 30 minutes, and 3.2% gap in 3.5 hours. DIFUSCO outperforms all others, as it reports the best performance with a 2.5% gap and a time cost of 47 minutes.\n\n\n[1] POMO\n\n[2] DIMES\n\n[3] DIFUSCO: \n\n[4] Fu et al.\n\n**Q**: Lack of Benchmark Results:\n\nTSPlib: The objective of this paper is to demonstrate the applicability of UL for the TSP. To assess our model's performance, we conducted evaluations on the same datasets used in [Fu et al., 2021], which serves as our primary baseline. We leave the exploration of TSPlib datasets to future research work.\n\n\n**Q**: Minor:\n\nA: We fixed the typos.\n\n\n**Q**: In line 72, Why the weight matrix is set...\nA: the temperature parameter is used to help build the adjacency matrix from $W$ the distance matrix $\\mathcal{D}$, a low $\\tau$ (close to zero) will make the graph less connected ( more sparse), while a higher one $\\tau$  will make it more dense, we will add more discussion. \n\n\n**Q**: In line 80, why do you use column-wise Softmax? How about row-wise Softmax, together with the column-wise constraint in Eq. (2)?\n\nA: When we use row-wise Softmax together with the column-wise constraint, we find that the performance of our model is NOT as good as using column-wise Softmax + row-wise constraint. \nTo be specific, taking TSP 100 as an example, when using column-wise Softmax + row-wise constraint, we observed 780 fully covered instances in 1,000 validation samples, as shown in Figure 6 (Right). However, when using  row-wise Softmax, together with the column-wise constraint in Eq. (2), we only observe 82 fully covered instances. \n\nWhy use column-wise Softmax? This is our motivation: \n\nThe heat map $H$ is based on $T$, Eq (1) can be written as:\n$\\mathcal{H}$ as:\n\n$\n\\mathcal{H} = \\sum_{t=1}^{n-1}p_t p^T_{t+1} + p_np_1^T,\n$\n\nwhere $p_t \\in \\mathbb{R}^{n \\times 1}$ is the $t_{th}$ column of $\\mathbb{T}$, $\\mathbb{T} = [p_1|p_2|...|p_n]$.}\nThat is to say, $\\mathcal{H}_{ij}$ is based on the columns of the $\\mathbb{T}$ (see \tFigure 9 in appendix), thus we want to encourage a more distinguishable column representation (ideally n-1  vs  1) in each column of $\\mathbb{T}$.  \nNow, in our model, we have two normalizations. The first one involves column-wise Softmax with row-wise constraints. The row-wise constraint is applied in a penalty form and can be seen as a standard normalization, where all outputs are divided by the sum of all outputs. Comparing this to the column-wise Softmax, the row-wise constraint (standard normalization) encourages a more spread-out representation, whereas the Softmax encourages a more distinguishable representation. Let’s take an example:\n\nsoftmax([1,2])  = [0.2689,      0.7311]\nstandard normalization([1,2]) = [0.3333, 0.6666]\n\nsoftmax([5,10]) = [0.0067, 0.9933]\nstandard normalization([5,10]) = [0.3333, 0.6666]\n\nsoftmax([10,20]) = [4.542e-5, 0.9999]\nstandard normalization([10,20]) =[0.3333, 0.6666]\n\nSince we aim to build a  distinguishable column representation, we apply a softmax on the columns and put a row-wise penalty. \n\n**Q**: Could you add more details (e.,g., model structure) ...\n\nA: We add a figure about the SAG model in the one page pdf rebuttal. We will revise the appendix and add more details about the model."}]

Author rebuttal:
Dear Reviewers, thank you for your comments. 

We updated our model's performance in the tables included in the one-page rebuttal PDF. 

We have incorporated additional baselines: POMO by Kwon et al. [2020] and more recent approaches such as DIMES by Qiu et al. [2022] and DIFUSCO by Sun and Yang [2023].

There is a typ in the TSP 500 column of the original manuscript. We have now corrected this error and updated the correct value, refer to the attached one page pdf.

In one-page rebuttal PDF, we also include Search Hyperparameter ablation study,  an illustration of the Search Process and the overall structure of SAG. We also found better performance on TSP 100. 

We will also update the manuscript, rewrite the introduction part and add a “related works” section to include recent advancements in data-driven methods for the Traveling Salesman Problem (TSP). Here is a preview of the proposed content for the "related works" section:

# Related Works

Researchers have been exploring the application of RL and SL techniques to tackle the TSP [Joshi 2022]. For example, [Kwon, 2020] uses a data-driven approach known as Policy Optimization with Multiple Optima (POMO), which relies on RL and avoids the utilization of hand-crafted heuristics. [Qiu, 2022] proposes a Meta-Learning framework that enhances the stability of REINFORCE-based training. [Sun 2023] applies SL and adopts a graph-based diffusion framework. Additionally, they introduce a cosine inference schedule to improve the efficiency of their model. [Fu 2021] also uses SL in their approach. They incorporate a heat map-based technique into an end-to-end model. Furthermore, they leverage graph sampling to extract small sub-graphs from the initial large graph. Subsequently, they train the GNN model on these sub-graphs to generate the corresponding heat maps, represented as probability matrices over the edges. Finally, the authors merge all the individual heat maps to create the final heat map.


Reference:

[Joshi 2022]:  Joshi, Chaitanya K., et al. "Learning the travelling salesperson problem requires rethinking generalization." Constraints 27.1-2 (2022): 70-98.

[Kwon, 2020]: Kwon et al. (2020). “Policy optimization with multiple optima for reinforcement learning.” Advances in Neural Information Processing Systems 33 (2020): 21188-21198.

[Qiu, 2022]: “A differentiable meta solver for combinatorial optimization problems.” Advances in Neural Information Processing Systems 35 (2022): 25531-25546.

[Sun 2023]: “Graph-based diffusion solvers for combinatorial optimization.” arXiv preprint arXiv:2302.08224 (2023).

[Fu 2021]: “Generalize a small pre-trained model to arbitrarily large tsp instances.” Proceedings of the AAAI conference on artificial intelligence. Vol. 35. No. 8. 2021.


Meta-review: After the rebuttal, the remaining concerns were:
* Limit scope raised by reviewer vHRb and agreed on by the other reviewers. 
* The experiments do not decouple the gains from the unsupervised approach to generating the heatmaps and the local search. Several reviewers asked for this and I and the reviewers did not find the authors answer satisfactory. 

Two reviewers were borderline/leaning to accept, one voted for rejection and one championed the paper saying, "The proposed method is simple and state-of-the-art. [...] Even if it is very specific to the TSP, it shows that a straightforward continuous relaxation of a combinatorial problem, combined with a neural net, can lead to excellent results. I think it is likely to inspire other researchers."

Given that the primary concern is around narrow problem scope rather than a strong technical weakness and that several of the reviewers found the work to be of interest, I'm inclined to recommend acceptance.
Decision: Accept (poster)