A Graph Neural Network Assisted Monte Carlo Tree Search Approach to Traveling Salesman Problem
Authors: Zhihao Xing
Shikui Tu
Venue:  (2020)
Keywords: Traveling Salesman Problem
Graph Neural Network
Monte Carlo Tree Search

Abstract: We present a graph neural network assisted Monte Carlo Tree Search approach for the classical traveling salesman problem (TSP). We adopt a greedy algorithm framework to construct the optimal solution to TSP by adding the nodes successively. A graph neural network (GNN) is trained to capture the local and global graph structure and give the prior probability of selecting each vertex every step. The prior probability provides a heuristics for MCTS, and the MCTS output is an improved probability for selecting the successive vertex, as it is the feedback information by fusing the prior with the scouting procedure. Experimental results on TSP up to 100 nodes demonstrate that the proposed method obtains shorter tours than other learning-based methods.

Under review as a conference paper at ICLR 2020
A GRAPH NEURAL NETWORK ASSISTED MONTE CARLO TREE SEARCH APPROACH TO TRAVELING SALESMAN PROBLEM
Anonymous authors Paper under double-bling blind review
ABSTRACT
We present graph neural network assisted Monte Carlo Tree Search approach for the classical traveling salesman problem (TSP). We adopt a greedy algorithm framework to construct the optimal solution TSP by adding the nodes succes- sively. A graph neural network (GNN) is trained to capture the local and global graph structure and give the prior probability of selecting each vertex every step. The prior probability provides a heuristic for MCTS, and the MCTS output is an improved probability for selecting the successive vertex, as it is the feedback in- formation by fusing the prior with the scouting procedure. Experimental results on TSP up to 100 nodes demonstrate that the proposed method obtains shorter tours than other souming-basee methods.
INTRODUCTION
Traveling Salesman Problem (TSP) is classical combinatorial optimization problem and has many practical applications in real life, such as planning, manufacturing, genetics (Applegate et al,, 2006b). The goal of TSP is find the shortest route that visits each city once and ends in the origin city, which is well-known as an NP-hard problem (Papadimitriou 1977.. In the literature, approx- imation algorithms were proposed to solve TSP (Lawler et al.) 1986] Goodrich Tamassia 2015). In particular, many heuristic search algorithms were made to find satisfactory solution within reasonable time. However, the performance of heuristic algorithms depends on handcrafted heuris- ties to guide the search procedure to find competitive tours efficiently. and the design of heuristics
usually requires substantial expertise the problem (Johnson & McGeoch. 1997 Dorigo & Gam- bardella 1997).
Recent advances in deep learning provide a powerful way of learning effective representations from data, leading to breakthroughs in many fields such speech recognition (Lecun al. 2015). Ef- forts of the deep learning approach to tackling TSP has been made under the supervised learning and reinforcement learning frameworks. Vinyals al. (Vinyals al. (015) introduced pointer net- work based on the Recurrent Neural Network (RNN) to model the stochastic policy that assigns high probabilities short tours given an input set of coordinates of vertices. Dai et al. (Dai et al.) (017) tackled the difficulty of designing heuristics by Deep Q-Network (DQN) based on structure (Dai et al. 2016b), and TSP solution was constructed incrementally by the learned greedy policy. Most recently. Kool er al. (Kool et al., 2019) used Transformer-Poine Pointer Network (Vaswani et al., 2017) to learn heuristics efficiently and got close to the optimal TSP solution for up to 100 vertices. These efforts made it possible to solve TSP by an end-to-end heuristic algorithm without special expert skills and complicated feature design.
In this paper, we present new approach to solving TSP. Our approach combines the deep neural network with the Monte Carlo Tree Search (MCTS), so that takes advantage of the powerful feature representation and scouting exploration. A graph neural network (GNN) is trained to capture the local and global graph structure and predict the prior probability, for each vertex, of whether this vertex belongs to the partial tour. Besides node features, integrate edge information into each update-laye in order to extract features efficiently from the problem whose solution relies on the edge weight.

---

Under review as a conference paper at ICLR 2020
Similar to above-learned heuristic approaches, could greedily select the vertex according to the biggest prior probability and yet the algorithm may fall into the local optimum because the algo- rithm has only one shot to compute the optimal tour and never goes back and reverses the decision. To overcome this problem, we introduce a graph neural network assisted Monte Carlo Tree Search (GNN-MCTS) make the decision more reliable by a large number of scouting simulations. The trained GNN is used to guide the MCTS procedure that effectively reduces the complexity of the search space and MCTS provides more reliable policy to avoid stuck in local optimum. Experi- mental results on TSP up to 100 vertices demonstrate that the proposed method obtains shorter tours than other learning- Saaneng-baseed methods.
The remainder of the paper is organized as follows: After reviewing related work in Section 2 we briefly give a preliminary introduction to TSP in Section 3 Our approach is formulated Section Experimental results are given in Section 5 followed by the conclusion in Section 6
2 RELATED WORK
The TSP is a well studied combinatorial optimization problem, and many learning- based algorithms have been proposed. In 1985, Hopfield et al. proposed a neural network to solve the TSP (Hopfield & Tank 1985). This is the first time that researchers attempted to use neural networks to solve combinatorial optimization problems. Since the impressive results produced by this approach, many researchers have made efforts on improving the performance (Bout & Miller 1988 Brandt et al.) 1988). Many shallow network architectures were also proposed to solve the combinatorial optimiza- tion problem (Favata & Walker [991] Fort 1988 Angniol et al., 1988; Kohonen 1982). Recent years, deep neural networks have been adopted to solve the TSP and many works have achieved remarkable results. We summarize the existing learning-bass methods from the following aspects.
ENCODER AND DECODER
Vinylas et al. VVinyals et al. 2015) proposed a neural architecture called Pointer Net (Ptr-Net) to learn the conditional probability of a tour using a mechanism of the neural attention. Instead of using attention to blend hidden units of an encoder to context vector, they used attention as pointers to the input vertices. The parameters of the model are learned by maximizing the conditional probabilities for the training examples in a supervised way. Upon test time, they used a beam search procedure to find the best possible tour. Two flaws exist in the method. First, Ptr-Net can only be applied to solve problems of a small scale (n < 50). Second, the beam search procedure might generate invalid routes.
Bello et al. (Bello et al. 2017 proposed framework to tackle TSP using neural networks and reinforcement learning. Similar to Vinylas el al., they employed the approach of Ptr-Net as a policy model to learn stochastic policy over tours. Furthermore, they masked the visited vertices to avoid deriving invalid routes and added a glimpse which aggregates different parts of the input sequence to improve the performance. Instead of training the model in supervised way, they introduced an Actor-Critic algorithm to learn the parameters of the model and empirically demonstrated that the generalization better compared to optimizing a supervised mapping of labeled data. The algorithm significantly outperformed the supervised learning approach (Vinyals et al., 2015) with up to 100 vertices.
Kool et al. Kooo et al. 2019) introduced an efficient model and training method for TSP and other routing problems. Compared (Bello al. 2017). they removed the influence on the input order of the vertices by replacing recurrence (LSTMs) with attention layers. The model can include valuable information about the vertices by multi-head attention mechanism which plays an important role in the setting where decisions relate directly to the vertices in graph. Similar to (Bello et al.) (017)) they applied reinforcement learning method to train the model. Instead of learning a value function as a baseline, they introduced a greedy rollout policy to generate baseline and empirically showed that the greedy rollout baseline can improve the quality and convergence speed for the approach. They improved the state-of-art performance among 20, 50, and 100 vertices. Independent of the work of Kool et al., Deudon et al. (Deudon et al.) 2018) also proposed a framework which uses attention layers and reinforcement learning algorithm (Actor-Critic) to learn stochastic policy.
2

---

Under review as a conference paper at ICLR 2020
Inpa Grogh
Naual Netur
Guidel Swarcchh
Clos Fost Vortow
Figure I: Approach overview. First, the graph is fed into the graph neural network, which captures global and local graph structure and generates a prior probability that indicates how likely each ver- tex is in the tour sequence. Then, with the help of the graph neural network, developed MCTS outputs an improved probability by scouting simulations. Lastly, we visit the best vertex among un- visited vertices according the improved probability. The above process will loop until all vertices are visited.
They combined the machine learning methods with an existing heuristic algorithm, i.c., 2-opt to enhance the performance of the framework.
GRAPH EMBEDDING
Dai et al. (Dai et al. 2017) proposed a framework, which combines reinforcement learning with graph embedding neural network, to construct solutions incrementally for TSP and other combina- torial optimization problems. Instead of using a separate encoder and decoder, they introduced a graph embedding network based on the structure2vee (Dai et al.] (016a) capture the current state of the solution and the structure of a graph. Furthermore, they used Q-learning parameterized by the graph embedding network to learn a greedy policy that outputs which vertex being inserted into the partial tour. They adopt the farthest strategy (Rosenkrantz et al. 2013) to get the best insertion position of the partial tour.
Nowak et al. (Nowak et al. 2017) propose a supervised manner to directly output a tour as an adjacency matrix based on Graph Neural Network and then convert the matrix into feasible solution by beam search. The author only reports an optimality gap of 2.7% for n 20 and slightly worse than the auto-regressive data-driven model (Vinyals et al. 2015).
The performance of the above-mentioned methods was suffered due to the greedy policy which selects the vertex according to the biggest prior probability or the value. this paper, we introduce new Monte Carlo Tree Search-based algorithm to overcome this problem.
PRELIMINARIES
TRAVELING SALESMAN PROBLEM
Let G(V, E, w) denotes weighted graph, where is the set of vertices, E the set of edges and w E + RR the edge weight function. i... w(u, v) is the weight of edge (u, v) E E. We use = [v1, U2, 0 to represent an ordered tour sequence that starts with vi and ends with vs and S = V \ S the set of candidate vertices for addition, condition on S. The target of TSP is to find
a tour sequence with the lowest cost, i.c., c(G,S) = = i=1 " S(i 1)) + ((((())..S when ||| [V]
PROPOSED APPROACH
For a graph, our goal to construct tour solution by adding vertices successively. A natural approach is to train deep neural network of some form to decide which vertex being added to the partial tour at each step. That is, a neural network f would take the graph G and the partial tour sequence S input, and the output f(G would be prior probability that indices how likely each vertex to be selected. Intuitively, we can use the prior probability greedy way, i.c., selecting vertex with the biggest probability, generate the tour sequence incrementally. However,
3

---

Under review as a conference paper at ICLR 2020
deriving tours in this way might fall into the local optimum because the algorithm has only one shot to compute the optimal tour and never goes back and reverses the decision. To overcome this problem, enhance the policy-decisions by MCTS assisted with the deep neural network.
We begin in Section 4.1 by introducing how to transform TSP into a Markov Decision Process describe the GNN architecture for parameterizing, [SG Finally, Section 4.3 describes GNN-MCTS for combinatorial optimization problems, especially the TSP. The overall approach illustrated in Figure
(MDP). Then in Section 4.2
4.1 TRAVELING SALESMAN PROBLEM AS MARKOV DECISION PROCESS
We present TSP as a MDP as follows,
States: a state is an ordered sequence of visited vertices on a graph G and the terminal state is that all vertices have been visited.
Transition:
transition deterministic in the TSP, and corresponds to adding one vertex o E S to
S.
Actions: an action a selecting vertex of from the vertices candidate set S.
Rewards: the reward function r(8, a.) at state 8 is defined as the change of cost after taking action and transitioning
new state s', i.e., r(s, a) ((mm Un), where Um and Un are the last vertex in partial tour sequence and S' respectively.
Policy: based on the improved probability P generated by the GNN-MCTS, deterministic
greedy policy π (v]S)) == arg max.res P(S, v') is used.
4.2 DEEP NEURAL NETWORK ARCHITECTURE
To compute good policy, information about the global structure of the graph and the current con- structed tour sequence S = {ui,,.., )i} is required. We tag the nodes which have been visited as Te Intuitively, f(G[S) should summarize the state of such a "tagged" graph and generate the prior probability that indicates how likely each vertex is to belong to S. It is challenging to design a neural network J[G]S) to capture local and global graph structure. order to represent such complicated context, we propose new deep learning architecture based on graph neural networks (GNN) to parameterize S)
GRAPH NEURAL NETWORKS
Similar to the basic GNN, design the neural network f[G[S; to compute I-dimensional feature H, for each vertex of a "tagged" graph. We use H to denote the real-valued feature vector associated with after the computation by the layer A GNN model consists of stack of T neural network layers, where each layer aggregates local neighborhood information, i.c., features of neighbors around each node, and then passes this aggregated information on the next layer. Specifically, the basic GNN model (Hamilton et al. 2017) can be implemented as follows. In each layer E [0, T), new feature computed as:
H = H Σ H uEA(())
(1)
where (v)) is the set of neighbors of vertex v, W and W2 are parameter matrices for the layer and denotes component-wise non-linear function, e.g., sigmoid a ReLU. For t 0, H denotes the feature initialization at the input layer.
The above GNN architecture has been demonstrated to perform well on combinatorial optimizations problems such as Maximal Independent Set (MIS), Minimum Vector Cover (MVC), etc. (Li et al, 2018). As observed from the Equation [ the edge information is not taken into account for MIS, MVC, but, for TSP, edge information cannot be ignored, because the object of TSP computed based the edge cost, i.e., the distance between the two vertices. We integrate edge information

---

Under review as a conference paper at ICLR 2020
Norph
ABA
Y.
Figure 2: Neural network architecture. The architecture on the left (A) used to compute the prior probability map that indicates how likely each vertex is in the tour sequence. Firstly, the "tagged" graph is fed into the GNN to generate new feature expressions for each vertex. Then all new node feature is concentrated into a long vector that denotes the context of the "tagged" graph. Lastly, the vector is fed into multilayer perceptron to output the prior probability. The picture on the right (B) feature of the vertex in one update-
depicts the mechanism of computing
into the new node feature H as follows,
H =
H +
Σ H +
Σ mEN(w)
e W
(2)
[(e
(EN())
where e(v, u) is the distance between two vertices and W are parameter matrices for the layer Dai et al. Dai et al. 2017) proposed graph embedding networks (GEN) based on structure2vec to compute new node feature y follows,
p5 relu OIx, + 02
Σ uEA((e)
mh +0g
Σ relu(O,w(1,u))
uEN(e)
where 01 E RR, 02 Ag E Rixl and 0₂ E RR' are model parameters.
Compared with GEN, the key improvements are: 1) Our GNN replaces 2, in Equation with He so that the our GNN could integrate the latest feature of the node itself directly in each update procedure. One can regard each update process in the GEN as one update layer of the our GNN, i.e., each calculation is equivalent to going one layer forward, and counting T times is the T layers. Parameters of each layer our GNN are independent, while parameters are shared between different update processes in GEN which limits the ability of the neural network. 3) Instead of aggregating edge weight by "sum" " operation, we use "average" operation to balance the weight of node and edge feature. Experimental results show that the above improvements enhance the performance of the neural network.
We initialize the node feature Hº follows. Each vertex has feature tag which is 3-dimensional vector. The first element is binary and equal to if the partial tour sequence 5 contains the vertex. The second and third elements of the feature tag are the coordinates of the vertex. When partial tour has been constructed, it can not be changed, and the remaining problem is to find a path from the last vertex, through all unvisited vertices, to the first vertex. To know the first and the last vertex in partial tour sequence S, besides basic feature tags described above, we extend the node feature H by adding feature tags of the first and last vertex in partial tour sequence (see Figure
PARAMETERIZING O)
Once feature for each vertex is computed after T iterations, and we use the new feature of vertices to define the S[G θ), which outputs the prior probability indicating how likely each vertex is to belong to partial tour sequence S. More specifically, we fuse all vertex feature H as the current
Euclidean distance: given two points (#1,8)) and (3), v2) two-dimensional plane,
J2 21)² (y2 y1)²
5

---

Under review as a conference paper at ICLR 2020
state representation of the graph and parameterize f(G]S; follows,
[[G|S; θ) softmax(sumi) (H) sum H)))
(4)
where sum denotes summation operator.
During training, we minimize the cross-entropy loss for each training sample (G,, S.):
N
((S, ((:
Σ
yj log f(C 1);
(5)
j=1
where S; is tour sequence which is permutation of the vertices over graph G; and yj is a one-hot vector whose length is and S())-th position is 1.
The architecture of the deep neural networks is illustrated in Figure]
4.3 GRAPH NEURAL NETWORK ASSISTED MONTE CARLO TREE SEARCH
Similar to the implementation in (Silver et al. 2016), the GNN-MCTS uses deep neural networks guide. Each node in the search tree contains edges (s, a) for all legal actions A()). Each edge stores a set of statistics,
(N(s, a), Q(x,a)) a(),a)
where (s,, a) is the visit count, Q(s, a) the action value and P(s, a) is the prior probability of selecting that edge.
To be mentioned, three biggest differences between GNN-MCTS and AlphaGo are:
When playing the game of Go, the branch with high average rate of winning indicates that the route is strong. While TSP is interested finding the extreme, the average value makes no sense if several suboptimal routes surround the extreme route. Instead of recording the average action value, we propose to track the best action value found under each node's subtree for determining its exploitation value.
In the game of Go, it is common to use {0, 0.5, 1} to denote the result of a game composed of loss, draw, and win. Not only is this convenient, but it also meets the requirements of UCT (Koesis & Szepesvári 2006) for rewards to lie in the [0, 1] range. In TSP, an arbitrary tour length can be achieve that does not fall into the predefined interval. One can solve this issue by adjusting the parameter Cpuct of UCT in such way that it is feasible for specified interval. It requires substantial tridl-and-error on adjusting Cpuct due to the change the number of cities. Instead, address this problem by normalizing the action value of each node whose parent is node p to [0, 1] as follows,
Qu wp bp
Q- 2p Wp
Q.
(6)
where bp and wp are, respectively, the best (maximum) and the worst (minimum) action value under p, and Qn is the action value of n. The best action value under p is normalized to the value of 1, the worst action value normalized to 0, and all other results are normalized to [o, 1].
AlphaGo used a learned value function (critic) v(s, 0) estimate the probability of the current player winning from position where the parameters are learned from the observations (s, T). However, getting such algorithms to work non-trivial. Instead, we design a value function h(ss) that combines the GNN and beam search evaluate the possible tour length from the current state to the end state. Guided by the output of GNN, the value function executes beam search from the state corresponding to the leaf node / until reaching end state. We compute the value of leaf node Vi according to the partial tour sequence S corresponding to the end state as follows.
11 Σ
Vi2 =
w (S(),, + w (S(SS),
The value function is described in algorithm
The GNN-MCTS proceeds by iterating over the four phases and then selects move to play.
value -T] f(G]S(1 j 1), where S is the partial tour sequence corresponding the state.

---

Under review as a conference paper at ICLR 2020
Algorithm Value Function
start denotes the state of leaf node I
B denotes the beam width
1: Initialize BEAM = {start}
2: while BEAM o Ø do
3: SET= Ø
4:
for state BEAM do
5: for successor of state do
6:
Compute value of the successor SET SET U successor
7:
8:
BEAM =
9:
while SET * Ø and B < (SET] do
10:
state = successor in SET with smallest value
11:
SET \ state
12:
for state SET do
13:
if state is end then
14:
return state in SET with biggest value else
15:
16:
BEAM = BEAM U { state }
Selection Strategy. The first in-tree phase of each rollouts begins at the root of node so of the search tree and finishes when the rollouts reaches leaf node 8/ at time step At each of these time steps, t<l, variant of PUCT (Rosin) 2011) to balance exploration(i.c. visiting states suggested by the prior policy) and exploitation(iee. visiting states that have the best value) according to the statistics in the search tree.
0t = arg max (Q(s;, (st,a))
(8)
No,
b(s
Uss, = Cpuct a) 1+ 1s,,a
(9)
where Spuct is constant to trading off between exploration and exploitation.
Expansion Strategy. When leaf node reached, the corresponding state s; evaluated by the deep neural network to obtain the prior probability p of its child nodes. The leaf node is expanded and the statistic of each edge (st, a) is initialized to (N(s), a) = 0, Q(s,,))) a) -x P(st.a) a) = }.).
Simulation Strategy. Rather than using random strategy, use value function h(ss) evaluate the length of the tour that may be generated from the leaf node st.
Back-Propagation Strategy. For each step l < L, the edge statistics updated in backward process. The visit counts are increased, N(s, 0z) = N(s,, at) + 1, and the action value is updated best value, Q(+;, a.) = max az), Vi)-
Play. At the end of several rollouts, we select node with the biggest P(a(sp) =1 ((a..a) E. Qu as
the next move in the root position sg. The search tree will be reused at subsequent time steps: the child node relating to the selected node becomes the new root node, and all the statistics of sub-tree below this child node is retained.
In the experiment, initialize the -5.0,-10.0 and -15.0 respectively for TSP20, TSP50, and TSP100.

---

Under review as a conference paper at ICLR 2020
Table I: Our method baselines. The gap % is w.r.t. the best value across all methods
Random
Clustered
Method
n=20
n=50
n=100
n=20
==50
1O0
Obj.
Gap
Obj.
Gap
Obj.
Gap
Obj.
Gap
Obj.
Gap
Obj
Gap
Concorde
3.92
0.0%
5.68
0.0%
1.73
0.0%:
3.30
0.0%%
3.38
0.0%
3.39
0.0%
Gurobi
3.92
0.0%
5.68
0.0%%
7.73
0.0%
3.30
0.0%
3.38
0.0%
3.39
0.0%
Nearest Neighbor
4.57
16.50%
7.02
23.43%
9.63
24.58%
3,95
19.48%
4.18
23.76%
4.23
25.025
Nearest Insertion
4.40
12.24%
6.77
19.08%
9.48
22.64%
3.66
10.62%
3.97
17.36%
4.08
20.46%
Random Insertion
4.08
4.12%
6.09
7.12%
8.45
9.24%
3,46
4.67%
3.65
7.93%
3.72
9.70%
Furthest Insertion
4.03
2.73%
5.98
5.29%
8.33
7.78%
3.40
2.87%
3.58
5.91%
3.64
7.55%
Vinyals et al. (gr.)
3.97
1.30%
6.41
18.58%
Bello al. (gr.)
3.99
1.83%
5.95
4.75%
8.26
6.82%
Kool et al. (gr.)
3,93
0.36%
5.78
1.75%
8,08
4,57%
Dai et
4.113
2.76%%
5.98
5. 26%
8.33
7.76%%
3.37
2.07%
3.58
6.01%
3.66
8.17%
GNN-MCTS
3.92
0.03%
5.70
0.32%
1.53%
3,30
0.00%
3.39
0.34%
3,44
1.61%
MCTS
6.37
62.45%
18.43
224.28%
40.27
430.83%
4,98
50.09%
9.26
173.99%
14.00
313.33%
GEN-MCTS
3,92
0.12%
5.75
1.31%
8.08
4.53%
3.31
0.21%
3.42
1.04%
3.55
4.72%
GNN MCTS-t
2.21%
5.26%
11.34%
3.37
2.19%
3.73
10.22%
GNN-MCTS-P
3.92
0.09%
5.77
1.47%
8.06
4.24%
3.31
0.14%
3.44
1.70%
3.54
4.39%
GNN-MCTS-v
3.92
0.08%
5.77
1 1.64%
8.06
4.24%
3.30
0.04%
3.42
1.13%
3.58
5.67%
GNN MCTS,
1.62%
7.21%
3.34
EXPERIMENTS
5.1
EXPERIMENTAL SETUP
5.1.1 BASELINES
To compute optimal solutions for both TSP, we use two state-of-the-arr solvers, Concorde (Ap plegate et al. 2006a) and Gurobi 5 Optimizatiion 2013). We compare against Nearest, Random and Farthest Insertion, as well as Nearest Neighbor, which are non-learned baseline algorithms that also derive a tour by adding vertices successively. Additionally, we compare against excellent deep learning-based methods based on the greedy framework as mentioned in Section 2 most importantly Vinyals et al. (Vinyals al. 2015), Bello al. (Bello et al. 2017), Kool et al. (Kool et al. 2019
and Dai et al. (Dai et al. 2017).
5.1.2 TRAINING AND TESTING
We generate 50,000 instances (see in appendix A for TSP20, TSP50, and TSP100, respectively. train GNN (settings are in appendix B We use state-of-art solvers (Gurobi and Concorde) to obtain the optimal tour sequence for each instance. Then we generate N samples for each instance according the optimal tour sequence. We divide the dataset into training set, validation set, and a test set according to the ratio of 8: 1: 1. We use Adam (Kingma & Ba 2014) with 128 mini-batches and learning rate 10-3 Training proceeds for 30 epochs on machine with 2080ti GPU. After training models for TSP20, TSP50, and TSP100, respectively, we use pre-trained GNN to guide GNN-MCTS. During testing, we randomly generate 1000 instances for the above three problems. The parameter settings of the GNN-MCTS used in our experiments are follows: we set Cpact = 1.3 and beam width = for three problems; we set rollouts = 800, 800 and 1200 respectively for TSP20, TSP50, and TSP100.
5.2 RESULTS
Besides non-learned algorithms, mainly compare method with excellent deep baaming--bssd works that derive tours on the greedy mechanism. We implement and train Pointer network with supervised learning, but we find that our supervised learning results not as good those ported by (Vinyals et al., 2015). Results of Pointer network on the random instances are from the optimality gaps they report 20, 50 vertex graphs. For other deep learning- based methods, we use experimental settings suggested by authors to train and get the same performance as reported.
http:://wah.uuaaeooooooooesoeeee http://www.gurobiccc
8

---

Under review as a conference paper at ICLR 2020
Rather than reporting the approximation ratio e-, where es the objective solution value of tour S and f=
c" is the best-known solution value instance G, we use the average optimality gap < = - mentioned in (Kool al. 2019). Table I reports the gap between the solution of each approach and the best-known solution for TSP20, TSP50, and TSPI00. Our approach performs favorably against other methods up 100 nodes the "random" and "clustered" instances. Table 7 in appendix reports the confidence interval on different confidence levels.
5.3 RUNNING TIMES
Rumning times are important but hard to compare because they can vary by two orders of magnitude result of implementation (Python C++) and hardware (CPU GPU). Our method is slower than other learning- basnn methods due to the look-ahead search. Our code is written by Python and note that the MCTS procedure Gurobi and learning-base based methods on machine with 32 virtual CPU system (2 Xeon(R) ES- 32 instances in parallel and after epochs, we report
speed up by rewritten code to C++. We test algorithm,
2620)) and 8 2080ti. each epoch, the time it takes to solve on each test instance (in 2).
5.4 GENERALIZATION TO LARGER PROBLEMS
In order to explore the generalization of our method, we train the GNN on TSPI00 random instances and test our method on random instances including TSP200, TSP300 and TSP500. We mainly compare the learning-basd -bsed methods proposed by Kool et al. and Dai et al. which made the best Encoder-Decood
performance before our work respectively The results (in Table show that our algorithm could generalize to larger problems well than other learning-base algorithms even trained in the small-scale instances.
and Graph Embedding framework.
5.5
ABLATION STUDY
5.5.1 AVERAGE VS BEST
We analyze the effect of different strategies used in the GNN-MCTS procedure. The comparison of different strategies are best. Different from AlphaGo, we track the best action value found under each node's subtree for determining its exploitation value. At the end of several rollouts, we select the node with the hest (biggest) action value as the next move in the root position. 2) average. As with the strategy used in AlphaGoo which is common in a two-player game, we track the average action value found under each node's subtree as exploitation value. Rather than selecting the node with the best (biggest) action value, we select the most visited node the next move in the root position.
Table I shows the gap between solutions of our approach with two strategies and the best-known solution for TSP20, TSP50, and TSP100. We refer GNN-MCTS to denote "best" strategy and refer GNN-MCTS to denote "average" strategy. The empirical results show that using the "best" strategy far better than using the "average" strategy for TSP.
5.5.2 COMPONENT CONTRIBUTION ANALYSIS
We conduct a controlled experiment on the TSP test set to analyze how each component con- tributes the presented approach. First, we use our GNN generate solutions in a greedy way, ie., selecting the vertex with the biggest prior probability at each step; we refer to this version as GNN-MCTS-t. Then we use GNN-MCTS which replaces the value function h(s) (see in algorithm
Table Running times of different method
Table Gap of different methods on larger in-
TSP20
TSP50
TSP100
stances
Dai et al.
0.007s
0.018s
0.043s
TSP200
TSP300
TSP500
Kool et al.
0.036s
0.054s
0.084s
Kool et al.
8.19%
12.32%
20.40%
Gurobi
0.017s
0.2s
1.9s
Dai al.
11.11%
11.70%
11.84%
Our
3.2s
6.6s
31.4s
Our
1.91 %
2.99% %
4.37%
9

---

Under review as a conference paper at ICLR 2020
Table 4: Gap of different beam width
Table 5: Time cost of different beam width
w=1
w=5
w=10
w=1
w=5
w=10
TSP20
2.25%
1.50%
1.50%
TSP20
55ms
265ms
534ms
TSP50
5.32%
3.64%
3.38%
TSP50
147ms
730ms
1461ms
TSP100
11.37%
8.11%
7.48%
TSPI00
323ms
1639ms
3338ms
D with random rollout generate tours; we refer to this version as GNN-MCTS-v, Furthermore, we take the GNN prior out of the picture and initialize prior probability to for newly expanded nodes; we refer to this version as GNN-MCTS-p. Lastly, a pure MCTS which removes GNN prior and value function is listed for comparison; we refer this version MCTS.
Table showss the gap between the solution of each approach and the best-known solution on differ- ent TSP problems. The results from GNN-MCTS-p and GNN-MCTS show that GNN prior could help MCTS to effectively reduce the search space so that MCTS can allocate more computing re- sources to nodes with high value. Furthermore, the results from GNN-MCTS-V and GNN-MCTS show that value function h(s) can estimate the path length from the leaf node well and the MCTS, which uses suitable value function, perform better than using a random rollout. Lastly, the gap of performance between GNN-MCTS-t and GNN-MCTS shows that the developed MCTS can efficiently avoid algorithm falling into local optimal and plays important role in enhancing the performance of our method.
5.5.3 ANALYSIS OF VALUE FUNCTION
We conduct experiments to explore the effects of different widths on the performance of value func- the result of value
tion. Since the beam width mainly affects the accuracy of value function, function as a measure and report the Gap as defined in Table Specifically, we set beam width to 5, 10 and test performance of the value function on random instances including TSP20. TSP50, and TSP100. We also count the time cost of the different settings of the beam width.
The experimental results of Table and Table 5 show that as the beam width increases, the perfor- mance of the value function will get better while the time cost will become larger. We need to make trade-off between accuracy and time cost.
5.6 COMPARISON WITH OTHER DEEP NEURAL NETWORKS
Compared with the basic GNN, GNN integrates edge information for computing new node feature, and it should extract more information and perform well than basic GNN. To support this statement, we compare the performance of basic GNN and our GNN on random instances, including TSP20, TSP50, and TSP100. We generate tour sequences by using the neural network in a greedy way, i.e., selecting vertex with the biggest prior probability at each step. The performance of two GNN is reported in Table (see in appendix D)
We also compare the performance of GEN and our GNN support the key improvements made by our GNN. Similar to the above comparison experiment, we generate tour sequences by using neural network in greedy way. The performance of GEN and our GNN is reported Table g Furthermore, we use GEN and our GNN to guide MCTS separately on "random" and "clustered" instances, including TSP20, TSP50 and TSP We refer to MCTS with GEN as GEN-MCTS. Table I reports the quality of solutions and shows that MCTS can get shorter tours when guided by our GNN.
CONCLUSION
We proposed a graph neural network assisted Monte Carlo Tree Search (GNN-MCTS) for the clas- sical traveling salesman problem. The core idea of our approach lies in converting the TSP into tree search problem. To capture the local and global graph structure, we train a graph neural network (GNN) which integrates node feature and edge weight into the feature update process. Instead of using the prior probability output by GNN a greedy way, we designed a GNN-MCTS to provide scouting simulation that the algorithm could avoid being stuck into the local optimum. The exper-
10

---

Under review as a conference paper at ICLR 2020
imental results show that the proposed approach can obtain shorter tours than other staning-based methods. We see the presented work as a step towards a new family solvers for NP-hard prob- lems that leverage both deep learning and classic heuristics. We will release code to support future progress in this direction.
REFERENCES
Bernard Angniol, Gal De La Croix Vaubois, and Jean Yves Le Texier. Self-organizing feature maps and the travelling salesman problem. Neural Networks, 1(4):289-293, 1988.
David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. Concorde tsp solver. Concorde: http://www.math.c wwwterloo. http:eeeww...ccss////cooeeeeeee. 2006a.
David L Applegate, Robert E Bixby, Vasek Chvatal, and William J Cook. The traveling salesman problem: a computational study. Princeton university press, 2006b.
Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combina- torial optimization with reinforcement learning. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings, 2017.
D. E. Van Den Bout and T. K. Miller. A traveling salesman objective function that works. In IEEE International Conference on Neural Networks, 1988.
R. D. Brandt, Wang Yao, A. J. Laub, and S. K. Mitra. Alternative networks for solving the traveling salesman problem and the list-matching problem. In IEEE International Conference on Neural Networks, 1988.
Hanjun Dai, Bo Dai, and Le Song. Discriminative embeddings of latent variable models for struc- tured data. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York Ciry, NY, USA, June 19-24, 2016, pp. 2702-22222000 2711, 2016a.
Hanjun Dai, Bo Dai, and Le Song. Discriminative embeddings of latent variable models for struc- tured data. In International Conference on Machine Learning, pp. 2702-2711, 2016b.
Hanjun Dai, Elias Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. In Advances in Neural Information Processing Systems 30, pp. 6348-6358. 2017.
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis Martin Rousscau. Learning heuristics for the tsp by policy gradient. In International Conference on the Integration of Constraint Programming, 2018.
Marco Dorigo and Luca Maria Gambardella. Ant colonies for the travelling salesman problem. Bio Systems, 43(2):73, 1997.
F. Favata and R. Walker. A study of the application of kohonen-type neural networks to the travelling salesman problem. Biological Cybernetics, 64(6):463 1991.
J. C. Fort. Solving combinatorial problem via self-organizing process: An application of the kohonen algorithm the traveling salesman problem. Biological Cybernetics,59() 59(1)333-40, 1988.
Michael T Goodrich and Roberto Tamassia. The christofides approximation algorithm. Algorithm Design and Applications, Wiley, pp. 513-514, 2015.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs.
In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
J. J. Hopfield and D. W. Tank. "neural" computation of decisions in optimization problems. Biolog- ical Cybernetics, 52(3):141, 1985.
David S Johnson and Lyle A McGeoch. The traveling salesman problem: case study in local optimization. Local search in combinatorial optimization, 1(1):215-100, 1997.

---

Under review as a conference paper at ICLR 2020
David S. Johnson, Gregory Gutin, Lyle A. Megeoch, Anders Yeo, Weixiong Zhang, and Alexei Zverovitch. Experimental analysis of heuristics for the atsp. Local Search in Combinatorial Optimization, 2001.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning, pp. 282-293. Springer, 2006.
Teuvo Kohonen. Self-organized formation of topologically correct feature maps. Biological Cyber- netics, 43(1):59 69, 1982.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. Erratum: The traveling
salesman problem: guided tour of combinatorial optimization. Journal of the Operational Research Society, 37(6):655-63 655, 1986.
Y Lecun, Y Bengio, and G Hinton. Deep learning. Nature, 521(7553):436, 2015.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems, pp. 539-548, 2018.
Alex Nowak, Soledad Villar, Afonso S Bandeira, and Joan Bruna. note on learning algorithms for quadratic assignment with graph neural networks. stat, 1050:22, 2017.
Gurobi Optimization. Gurobi optimizer 5.0. Gurobi: http://www.gunbii.omm, 2013.
Christos H. Papadimitriou. The euclidean travelling salesman problem is np-complete. Theoretical
Computer Science, 4(3):237-244, 1977.
Daniel J. Rosenkrantz, Richard Edwin Stearns, and Philip M. Lewis. An analysis of several heuris- tics for the traveling salesman problem. In Fundamental Problems in Computing. Essays in Honor of Professor Daniel J. Rosenkrantz. pp. 45-69, 2013.
Christopher D. Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Arti- ficial Intelligence, 613))200--30, 2011.
D Silver, A. Huang, C. J. Maddison, Guez, I. Sifre, den Driessche G Van, Schrittwieser, Antonoglou, V Panneershelvam, and M Lanctot. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):4444489, 2016.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention all you need. In International Conference on Neural Information Processing Systems, pp. 5198-5998999 6608, 2017.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In International Conference on Neural Information Processing Systems, 2015.
12

---

Under review as a conference paper at ICLR 2020
A INSTANCE GENERATION
To evaluate our method against other approximation algorithms and deep learning- approaches, use an instance generator from the DIMACS TSP Challenge (Johnson al., 2001) generate two types of Euclidean instances: "random" instances consist of points scattered uniformly at random in the [10%, 10 square: "clustered" instances include n points that are clustered into n/ 100 clusters. We consider three benchmark tasks, Euclidean TSP20, 50 and 100, for which we generate train set of 50,000 instances and
of 1,000 instances.
B GRAPH NEURAL NETWORK SETTINGS
Our GNN has T 3 uode-update layers, which is deep enough for nodes to aggregate information associated with their neighbor vertices. Since the input is a "tagged" graph with 9-dimensional feature on vertices, the input contains vectors of size H 9. The width of other layers are identical: I = 64 for é 1,2.
The proposed GNN has a deep architecture that consists of several node-update layers. Therefore, as the model gets deeper with more layers, the more information can be aggregated by nodes. We train proposed GNN with the different number of layers on random instance from TSP20. We greedily the prior probability, i.., selecting the vertex with the biggest prior probability, to derive tour sequence. We report Gap as defined in Table T The result of Table 6 show that the performance of GNN will become better the number of network layers increases.
Table 6: Effect of the number of layers on random instances
Layers
T=1
T=2
T=3
Gap 5.1%
3.2%
2.2%
C CONFIDENCE INTERVAL ON DIFFERENT CONFIDENCE LEVELS
Table 7: Confidence interval on different confidence levels
Confidence level
90%
95%
99%
n=20
3.922:10.046
3.922-t0.054
3.922+t0.071
Random
n=50
5.701=:0.041
5.701=100048
5.701
n=100
7.850:0.003
7.850+1.0047
7.850+L0.062
n=20
3.305:10.08
3.305-10093
3.305+t0.12
Clustered
n=50
3.391=0.051
3.391440001
3.391000.080
n=100
3.442+000036
3.442+0.043
3.442+0.056
D PERFORMANCE OF DIFFERENT NETWORKS
Table 8: Performance of different networks n=50
n=20
n=100
GNN
4.8%
21.1%
58.9%
GEN
4.1%
12.5%
21.9%
Our
2.2%
5.3%
11.3%
13


Reviews:
[{"review_id": "ryxI8_Q1qS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes learning a TSP solver that incrementally constructs a tour by adding one city at a time to it using a graph neural network and MCTS. The problem is posed as a reinforcement learning problem, and the graph neural network parameters are trained to minimize the tour length on a training set of TSP instances. A graph neural network architecture called Static Edge Graph Neural Networks is introduced which takes into account the graph of all cities in a given problem instance as well as the partial tour constructed so far in an episode. The network predicts probabilities for the remaining cities to be selected as the next city in the tour, which is then used to compute a value function that guides MCTS. Results on synthetic TSP instances with 20, 50, and 100 cities show that the approach is able to achieve better objective values than prior learning-based approaches. Applying AlphaZero-like approaches to TSP is an interesting test case for understanding how well they can work on hard optimization problems.\n\n\nThe paper has several drawbacks:\n- The evaluation seems to be flawed as there is no mention of running time of the various algorithms being compared anywhere in the text. It’s not possible to make a fair comparison without controlling for running time. As an extreme example, even random search will eventually find the global optimum if given sufficient time. So the results are not very meaningful without the running times.\n\n- Novelty is fairly low. The changes in SEGNN compared to previous works are incremental or not novel, and the overall idea is the same as AlphaGo/Zero. While I don’t think novelty is a strict requirement, if it is absent, then it should be compensated with strong empirical results, but the paper lacks that as well.\n\n- A discussion on whether the approach can plausibly scale to much larger TSP instances is missing. First, there is the question of whether learning can succeed on much larger instances. Second, even if good policies can indeed be learned, can they provide competitive running times compared to the state-of-the-art TSP solvers? Graph net inference’s compute cost scales linearly with graph size (number of cities), and since multiple inference passes need to be performed per step (to pick the next city to add to the current partial tour), the overall cost scales quadratically. This is worse than the empirical scaling of solvers like LKH and POPMUSIC. One has to consider approaches with cost that scales roughly linearly to be able to compete with state-of-the-art solvers. It should be noted that TSP instances with <= 100 cities are really trivial for the best solvers, and outperforming them with a learning-based approach may not be plausible until much larger instances are considered (e.g., > 10K cities). The ML community needs to move away from evaluating on small instances if the long term goal is to beat state-of-the-art solvers with learning.\n\n\nAdditional comments:\n- There are a lot of typos. A few that I caught: Tables 1 and 7 say “Rondom”, “approximation ration”, “ReLu”, “provides a heuristics”, “Similar to the implement”.\n\n- Table 6 gives the highest test accuracy during training, but this could be misleading (e.g., there could be random spikes in test performance during training). A smoother metric should be used.\n\n- Table 3 title is confusing.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Syga-qC2FS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors introduce a new Monte Carlo Tree Search-based (MCTS) algorithm for computing approximate solutions to the Traveling Salesman Problem (TSP). Yet since the TSP is NP-complete, a learned heuristic is used to guide the search process. For this learned heuristic, the authors propose a Graph Neural Network-derived approach, in which an additional term is added to the network definition that explicitly adds the metric distance between neighboring nodes during each iteration. They perform favorably compared to other TSP approaches, demonstrating improved performance on relatively small TSP problems and quite well on larger problems out of reach for other deep learning strategies.\n\nI believe that the paper is built around some good ideas that tackle an interesting problem; the Traveling Salesman Problem and variants are popular and having learning-based approaches to replace heuristics is important. In particular, choosing to use an MCTS to tackle this problem feels like a natural approach, and using a GNN as a learning backend feels like a encourage better performance with fewer training samples. However, there are too many questions raised by decisions the authors have made to warrant acceptance in the current state; I would be willing to revise my score if some more detailed analysis of these points were included.\n\nFirst, the heuristic value function: this value function h(s) is defined in the appendix but should be motivated and described (in detail) in the text body. As written, this information is not included in the main body of the paper yet is critical for the implementation. Also, though it is intuitively clear why a random policy is unlikely to result in a poor result, it is never compared against; how does the performance degrade if the heuristic value function is not used? Finally, the parameter 'beam width' used in the evaluation of the value function but is only set to 1 in all experiments. Some experiments should be included to show how increasing beam width impacts performance (or the authors should provide a reason these experiments were not run). Finally, it seems as if there already exists heuristic methods (against which the paper compares performance); could these be used instead of this value function?\n\nAdditionally, how is the set of Neighbors defined? It is suggested in the text that it is not all nodes, but not using all nodes is a limiting assumption. Relatedly, it would be helpful if the authors could better motivate their additional term in Eq. (2); at the moment, though using the euclidian distance to weight the edges, it is unclear why this function is a better choice than something else, for instance a Gaussian kernel or a kernel with finite support. In addition, the authors motivate that the distance between nodes is very important for the performance of the system, yet the coordinates of each vertex are included as part of the input vector so that (in principle) the network could learn to use this information. A comparison against a network implemented using the basic GNN model, defined in Eq. (1), should be included to compare performance.\n\nIn summary, there are a few choices that would need to be better justified for me to really support acceptance. However, there are some quite interesting ideas underpinning this paper, and I hope to see it published.\n\nMinor comments:\n- Overall, I like the structure of the paper. At the beginning of all major sections there is an overview of what the remainder of the section will contain. This helps readability. I also like the comparison between the proposed work and AlphaGo, which popularized using deep learning in combination with MCTS; this enhances the clarity of the paper.\n- The related work section would be more instructive if it also gave some information about the limitations of the alternative deep learning approaches and how the proposed technique overcomes these. My assumption is that all approaches discussed in the second paragraph are \"greedy\" and suffer from the limitations mentioned in the introduction. However, I am not sufficiently familiar with the literature to be certain. A sentence or two mentioning this or relating that work to the proposed MCTS approach would be informative.\n- The last paragraph of the Related Work section, discussing the work of Nowak et al 2017 and Dai et al 2017, introduces some numbers with no context: e.g., \"optimality gap of 2.7%\". It is unclear at this stage if this number is good or bad. Some more context and discussion of this work might be helpful for clarity, particularly since the Nowak work seems to be the only other technique using GNN.\n- Some general proofreading for language should be performed, as there are occasionally typos or missing words throughout the paper. Some examples: \"compute the prior probability that indicates how likely each vertex [being->is] in the tour sequence\"; \"Similar to the [implement->implementation], in Silver...\"; \"[Rondom->Random]\" in tables.\n- In Sec. 4.1, it is unclear what is meant by \"improved probability \\hat{P} of selecting the next vertex\".\n- I believe there is an inconsistency in the description of the MCTS strategy. Though the action value is set to the 'max' during the Back-Propagation Strategy, the value of Q is initialized to infinity.\n\nSuggestions for improvement (no impact on review):\n- Clarity: the language in the 3rd and 4th paragraphs of the introduction [begins with \"In this paper, ...\"] could be made clearer.\n  - The language \"part of the tour sequence\" is not quite clear, since, when the process is complete, all points will be in the tour. It should be made clearer that the algorithm is referring to a \"partial tour\" as opposed to the final tour. This clarity issue also appears later in Sec. 4.\n  - \"Similar to above-learned heuristic approaches...\" It might be clearer if you began the sentence with \"Yet,\" or \"However,\" so that it is more obvious to the reader that you intend to introduce a solution to this problem.\n- Equation formatting: Please use '\\left(' and '\\right)' for putting parenthesis around taller symbols, like \\sum.\n- When describing the MCTS procedure, I have seen the word \"rollouts\" used much more frequently than \"playouts\". Consider changing this language (though the meaning is clear).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1eL7g195S", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "EDIT: After the authors response and update of the contributions to indicate that the main contribution of the paper is the application of GNNs and MCTS to the TSP (rather than the original claims that that the model architecture and search approach were novel contributions), I increased my score from Weak Reject to Weak Accept. However, given that the paper is now more focused on solving the TSP, and I am not an expert on that specifically I had to reduce my experience assessment, as while I am more confident now that the paper is technically correct, it is harder for me to judge if the paper should be accepted in terms of empirical strength since I am not familiar with TSP baselines.\n\nThe authors propose an MCTS-based learned approach using Graph Neural Networks to solve the traveling salesman problem (TSP) agents. \n\nThe authors write the TSP as an MDP where the state consists of the nodes visited by the agent and the last node visited by the agent, the action consists of selecting the next node to visit, and the reward at each step is the negative cost of the travel between the last node and the next node. \n\nThe learned part of the model uses a “static-edge graph neural network” (SE-GNN). This network allows to access the full graph context, including edge features, to make node predictions. This is listed as the first paper contribution. At train time, this network is trained to predict the probability of each unvisited node to be next in the optimal path. This is trained via supervised learning using optimal paths precomputed with state of the art TSP solvers.\n\nAt test time, they use MCTS with a variant of PUCT, where the pre-trained SE-GNN is used as the prior policy, and there is a selection strategy during search that balances the prior probability, and the Q values estimated by MCTS, using max based updates (e.g. during back up new Q estimates replace old estimates if and only if the are larger than the previous ones). This is listed as the second paper contribution. Authors show that the approach beats other learned solvers in the TSP problem by a large margin in terms of optimality gap.\n\nWhile I think the work is interesting, I am not sure that what the authors cite as main contributions of the paper are truly the main contributions. In my opinion the main contribution would be the state of the art performance at solving the TSP using learned methods. I cannot, however, recommend acceptance due to the following reasons.\n\nWith respect to the first claim “SE-GNN that has access to the full graph context and generates the prior probability of each vertex”, there are already many models that allow to condition on edge features, including InteractionNetworks, RelationNetworks and GraphNetworks. This paper has a good overview of this family of methods and most of them allow to access the full graph context too (https://arxiv.org/abs/1806.01261). Most of these models are very well known and are in principle more expressive than the one proposed in this paper, and allow generalization to different graph sizes, so the motivation for introducing a new model is not very clear, specially if these baselines are not compared.\n\nWith respect to the MCTS contribution at test time, it seems that the changes made to the algorithm compared to AlphaGo, are very specific to the TSP and there is not much discussion about which other sort of problems may benefit from the same modifications, so it is hard to evaluate its value as a standalone contribution independent from the TSP.\n\nOn the basis of state of the art performance at solving the TSP using learned methods:\n* The model requires access to a dataset with optimal solutions to train it, and I doubt it can solve the problems faster than Gurobi in terms of wall time. For this result to be more interesting, the authors should be able to show that the model can generalize to larger problems (where the combinatorial complexity may start making approaches like Gurobi struggle). However it is not clear if the model can generalize to larger graphs.\n* Beyond that I am not an expert on TSP specifically, and I don’t know the TSP literature, so I cannot give a strong recommendation.\n\nThere are some additional papers that may be relevant to this line of work:\n* (MIP, NeurIPS 2019) Learning to branch in MIP problems using similar technique pretraining a GNN and use it to guide a solver at test time (no MCTS though) (https://arxiv.org/abs/1906.01629) \n* (SAT, SAT Conference 2019) Learning to predict unsat cores (similar to the previous one but for SAT problems) (https://arxiv.org/abs/1903.04671)\n* (Structural construction, ICML 2019) Building graphs by choosing actions over the edges of a graph solving the full RL problem end to end, and also integrating MCTS with learned prior both at train time and test time (together and independently) (http://proceedings.mlr.press/v97/bapst19a/bapst19a.pdf)\n\nSome additional typos/ feedback:\n* It would be good to have a pure MCTS baseline with not learned prior as an additional ablation (e.g. taking the SE-GNN prior out of the picture).\n* In the “Selection Strategy” paragraph, the action is said to be picked as argmax(Q + U), where U is proportional to the prior for each action. However, Q is said to be initialized to infinite. This would mean that at the beginning of search all actions will be tied at infinite value, and my default assumption would be that in these conditions an action is chosen uniformly at random. I suspect what happens in this case is that the action with the highest prior is picked to break the tie at infinite, however if this is the case this should be indicated in the math.\n* In the “Expansion Strategy” paragraph, the Q values are said to be initialized to infinite. However in the Back-Propagation strategy it is said they are updated using newQ = max(oldQ, value_rollout). If this was true the values would always remain infinite, I assume the max is not applied if the previous value was still infinite.\n* In the “Play” paragraph: The action is said to be picked according to the biggest Q value at the root, I assume in cases where the planning budget is smaller than the number of nodes, and not all actions at the root are explored, the actions that have not been explored are masked out.\n* Non-exhaustive list of typos: “Rondom” —> “Random”, “provides a heuristics” —> “provides a heuristic”, “strcuture2vec” — > “structure2vec”, weird line break at top of page 8. \n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is a contribution to the recently emerging literature on learning                                                        
based approaches to combinatorial optimization.                                                                                    
The authors propose to pre-train a policy network to imitate SOTA solvers for                                                      
TSPs.                                                                                                                              
At test time, this policy is then improved, in an alpha-go like manner, with                                                       
MCTS, using beam-search rollouts to estimate bootstrap values.                                                                     
                                                                                                                                   
The main concerns raised by the reviewers is lack of novelty (the proposed                                                         
algorithm is a straight forward application of graph NNs to MCTS) as well a the                                                    
experimental results.                                                                                                              
Although comparing well to other learning based methods, the algorithm is far                                                      
away from the performance of SOTA solvers.                                                                                         
                                                                                                                                   
Although well written, the paper is below acceptance threshold.                                                                    
The methodological novelty is low.                                                                                                 
The reported results are an order of magnitude away from SOTA solvers, while previous work                                         
has already reported the general feasibility of learned solvers to TPSs.                                                           
Furthermore, the overall contribution is somewhat unclear as the policy relies                                                     
on pre-training with solutions form existing solvers. 
Decision: Reject