Title: A GRAPH NEURAL NETWORK ASSISTED MONTE CARLO TREE SEARCH APPROACH TO TRAVELING SALESMAN PROBLEM

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 heuristic 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.

1. INTRODUCTION:

Traveling Salesman Problem (TSP) is a 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 to 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, approximation algorithms were proposed to solve TSP (Lawler et al., 1986; Goodrich & Tamassia, 2015) . In particular, many heuristic search algorithms were made to find a satisfactory solution within a reasonable time. However, the performance of heuristic algorithms depends on handcrafted heuristics to guide the search procedure to find competitive tours efficiently, and the design of heuristics usually requires substantial expertise of the problem (Johnson & McGeoch, 1997; Dorigo & Gambardella, 1997) .

Recent advances in deep learning provide a powerful way of learning effective representations from data, leading to breakthroughs in many fields such as speech recognition (Lecun et al., 2015) . Efforts of the deep learning approach to tackling TSP has been made under the supervised learning and reinforcement learning frameworks. Vinyals et al. (Vinyals et al., 2015) introduced a pointer network based on the Recurrent Neural Network (RNN) to model the stochastic policy that assigns high probabilities to short tours given an input set of coordinates of vertices. Dai et al. (Dai et al., 2017) tackled the difficulty of designing heuristics by Deep Q-Network (DQN) based on structure2vec (Dai et al., 2016b) , and a TSP solution was constructed incrementally by the learned greedy policy. Most recently, Kool et al. (Kool et al., 2019) used Transformer-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 a 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, we integrate edge information into each update-layer in order to extract features efficiently from the problem whose solution relies on the edge weight.

Similar to above-learned heuristic approaches, we could greedily select the vertex according to the biggest prior probability and yet the algorithm may 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, we introduce a graph neural network assisted Monte Carlo Tree Search (GNN-MCTS) to 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 a more reliable policy to avoid stuck in a local optimum. Experimental results on TSP up to 100 vertices demonstrate that the proposed method obtains shorter tours than other learning-based 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 in Section 4. 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 optimization problem (Favata & Walker, 1991; 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-base methods from the following aspects.

ENCODER AND DECODER:

Vinylas et al. (Vinyals 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 a 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 a framework to tackle TSP using neural networks and reinforcement learning. Similar to Vinylas et al., they employed the approach of Ptr-Net as a policy model to learn a 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 a supervised way, they introduced an Actor-Critic algorithm to learn the parameters of the model and empirically demonstrated that the generalization is 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. (Kool et al., 2019 ) introduced an efficient model and training method for TSP and other routing problems. Compared to (Bello et 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 a graph. Similar to (Bello et al., 2017) , they applied a 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 a stochastic policy.

Input Graph Guided Tree Search Neural Network:

Choose Best Vertex

Figure 1 : 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 vertex is in the tour sequence. Then, with the help of the graph neural network, a developed MCTS outputs an improved probability by scouting simulations. Lastly, we visit the best vertex among unvisited vertices according to 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.e., 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 combinatorial optimization problems. Instead of using a separate encoder and decoder, they introduced a graph embedding network based on the structure2vec (Dai et al., 2016a) to 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 a Graph Neural Network and then convert the matrix into a 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. In this paper, we introduce a new Monte Carlo Tree Search-based algorithm to overcome this problem.

3. PRELIMINARIES TRAVELING SALESMAN PROBLEM:

Let G(V, E, w) denotes a weighted graph, where V is the set of vertices, E the set of edges and w : E → R + the edge weight function, i.e., w(u, v) is the weight of edge (u, v) ∈ E. We use S = {v 1 , v 2 , ..., v i } to represent an ordered tour sequence that starts with v 1 and ends with v i , 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.e., c(G, S)

= |S|-1 i=1 w(S(i), S(i + 1)) + w(S(|S|), S(1)) when |S| = |V |.

4. PROPOSED APPROACH:

For a graph, our goal is to construct a tour solution by adding vertices successively. A natural approach is to train a 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 as input, and the output f (G|S) would be a prior probability that indices how likely each vertex to be selected. Intuitively, we can use the prior probability in a greedy way, i.e., selecting vertex with the biggest probability, to generate the tour sequence incrementally. However, 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, we 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 (MDP). Then in Section 4.2, we describe the GNN architecture for parameterizing f (G|S). Finally, Section 4.3 describes GNN-MCTS for combinatorial optimization problems, especially the TSP. The overall approach is illustrated in Figure 1 .

4.1. TRAVELING SALESMAN PROBLEM AS MARKOV DECISION PROCESS:

We present TSP as a MDP as follows,

• States: a state s is an ordered sequence of visited vertices on a graph G and the terminal state is that all vertices have been visited.

• Transition: transition is deterministic in the TSP, and corresponds to adding one vertex v ∈ S to S.

• Actions: an action a is selecting a vertex of G from the vertices candidate set S.

• Rewards: the reward function r(s, a) at state s is defined as the change of cost after taking action a and transitioning to a new state s , i.e., r(s, a) = -w(v m , v n ), where v m and v n are the last vertex in partial tour sequence S and S respectively.

• Policy: based on the improved probability P generated by the GNN-MCTS, a deterministic greedy policy π(v|S) := arg max v ∈ S P (S, v ) is used.

4.2. DEEP NEURAL NETWORK ARCHITECTURE:

To compute a good policy, information about the global structure of the graph and the current constructed tour sequence S = {v 1 , ..., v i } is required. We tag the nodes which have been visited as 

EQUATION

GRAPH NEURAL NETWORKS:

Similar to the basic GNN, we design the neural network f (G|S; Θ) to compute a l-dimensional feature H v for each vertex of a "tagged" graph. We use H t v to denote the real-valued feature vector associated with v after the computation by the layer t. A GNN model consists of a stack of T neural network layers, where each layer aggregates local neighborhood information, i.e., features of neighbors around each node, and then passes this aggregated information on to the next layer. Specifically, the basic GNN model (Hamilton et al., 2017) can be implemented as follows. In each layer t ∈ [0, T ], a new feature is computed as:

H t+1 v = σ   H t v W t 1 + u∈N (v) H t u W t 2   (1)

where N (v) is the set of neighbors of vertex v, W t 1 and W t 2 are parameter matrices for the layer t, and σ denotes a component-wise non-linear function, e.g., a sigmoid or a ReLU. For t = 0, H 0 v 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 1 , the edge information is not taken into account for MIS, MVC, but, for TSP, edge information cannot be ignored, because the object of TSP is computed based on the edge cost, i.e., the distance between the two vertices. We integrate edge information The architecture on the left (A) is 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 a multilayer perceptron to output the prior probability. The picture on the right (B) depicts the mechanism of computing a new feature of the vertex in one update-layer.

into the new node feature H as follows,

H t+1 v = σ   H t v W t 1 + u∈N (v) H t u W t 2 + 1 |N (v)| u∈N (v) e v,u W t 3   (2)

where e(v, u) is the distance1 between two vertices and W t 3 are parameter matrices for the layer t. Dai et al. (Dai et al., 2017) proposed a graph embedding networks (GEN) based on structure2vec to compute new node feature µ as follows,

EQUATION

where θ 1 ∈ R l , θ 2 , θ 3 ∈ R l×l and θ 4 ∈ R l are model parameters.

Compared with GEN, the key improvements are: 1) Our GNN replaces x v in Equation 3 with H v so that the our GNN could integrate the latest feature of the node itself directly in each update procedure. 2) 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 in 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 0 as follows. Each vertex has a feature tag which is a 3-dimensional vector. The first element is binary and equal to 1 if the partial tour sequence S contains the vertex.

The second and third elements of the feature tag are the coordinates of the vertex. When a 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 0 by adding feature tags of the first and last vertex in partial tour sequence S (see in Figure 2 ).

PARAMETERIZING f (G|S; Θ):

Once feature for each vertex is computed after T iterations, and we use the new feature of vertices to define the f (G|S; Θ), 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 T v as the current state representation of the graph and parameterize f (G|S; Θ) as follows ,

EQUATION

where sum denotes summation operator.

During training, we minimize the cross-entropy loss for each training sample (G i , S i ):

EQUATION

where S i is a tour sequence which is a permutation of the vertices over graph G i and y j is a one-hot vector whose length is N and S(j)-th position is 1.

The architecture of the deep neural networks is illustrated in Figure 2 .

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 as a guide. Each node s in the search tree contains edges (s, a) for all legal actions a ∈ A(s). Each edge stores a set of statistics, {N (s, a), Q(s, a), P (s, a)} where N (s, a) is the visit count, Q(s, a) is 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 a high average rate of winning indicates that the route is strong. While TSP is interested in 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 (Kocsis & 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 c puct of UCT in such a way that it is feasible for a specified interval. It requires substantial trial-and-error on adjusting c puct due to the change in the number of cities. Instead, we address this problem by normalizing the action value of each node n whose parent is node p to [0, 1] as follows,

EQUATION

where b p and w p are, respectively, the best (maximum) and the worst (minimum) action value under p, and Q n is the action value of n. The best action value under p is normalized to the value of 1, the worst action value is normalized to 0, and all other results are normalized to [0, 1]. • AlphaGo used a learned value function (critic) v(s, θ) to estimate the probability of the current player winning from position s, where the parameters θ are learned from the observations (s, π).

However, getting such algorithms to work is non-trivial. Instead, we design a value function h(s) that combines the GNN and beam search to 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 l until reaching an end state. We compute the value of leaf node V l according to the partial tour sequence S corresponding to the end state as follows,

V l = -   |S|-1 i=1 w (S(i), S(i + 1)) + w (S(|S|), S(1))   (7)

The value function is described in algorithm 1.

The GNN-MCTS proceeds by iterating over the four phases and then selects a move to play.

2 value = |S| j=1 f (G|S(1 : j -1), where S is the partial tour sequence corresponding to the state. 

BEAM = BEAM ∪ { state }

Selection Strategy. The first in-tree phase of each rollouts begins at the root of node s 0 of the search tree and finishes when the rollouts reaches a leaf node s l at time step l. At each of these time steps, t<l, we use a variant of PUCT (Rosin, 2011) to balance exploration(i.e., visiting states suggested by the prior policy) and exploitation(i.e., visiting states that have the best value) according to the statistics in the search tree.

EQUATION

where c puct is a constant to trading off between exploration and exploitation.

Expansion Strategy. When a leaf node l is reached, the corresponding state s l is 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

(s l , a) is initialized to {N (s l , a) = 0, Q(s l , a) = -∞ 3 , P (s l , a) = p a }.

Simulation Strategy. Rather than using a random strategy, we use value function h(s) to evaluate the length of the tour that may be generated from the leaf node s l .

Back-Propagation Strategy. For each step t < L, the edge statistics are updated in a backward process. The visit counts are increased, N (s t , a t ) = N (s t , a t ) + 1, and the action value is updated to best value, Q(s t , a t ) = max(Q(s t , a t ), V l ).

Play. At the end of several rollouts, we select node with the biggest P (a|s 0 ) = 1 -Q(s0,a) b Q(s0,b) as the next move a in the root position s 0 . 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. 

5.1.1. BASELINES:

To compute optimal solutions for both TSP, we use two state-of-the-art solvers, Concorde4 (Applegate et al., 2006a) and Gurobi5 (Optimization, 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 et al., 2015) , Bello et 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, to 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 to the optimal tour sequence. We divide the dataset into a training set, a 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 a 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 as follows: we set c puct = 1.3 and beam width = 1 for three problems; we set rollouts = 800, 800 and 1200 respectively for TSP20, TSP50, and TSP100.

5.2. RESULTS:

Besides non-learned algorithms, we mainly compare our method with excellent deep learning-based works that derive tours on the greedy mechanism. We implement and train a Pointer network with supervised learning, but we find that our supervised learning results are not as good as those reported by (Vinyals et al., 2015) . Results of Pointer network on the random instances are from the optimality gaps they report on 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.

Rather than reporting the approximation ratio c c * , where c is the objective solution value of tour S and c * is the best-known solution value of instance G, we use the average optimality gap c-c * c * = c c * -1 mentioned in (Kool et al., 2019) . Table 1 reports the gap between the solution of each approach and the best-known solution for TSP20, TSP50, and TSP100. Our approach performs favorably against other methods up to 100 nodes on the "random" and "clustered" instances. Table 7 in appendix C reports the confidence interval on different confidence levels.

5.3. RUNNING TIMES:

Running times are important but hard to compare because they can vary by two orders of magnitude as a result of implementation (Python or C++) and hardware (CPU or GPU). Our method is slower than other learning-based methods due to the look-ahead search. Our code is written by Python and we note that the MCTS procedure can speed up by rewritten code to C++. We test our algorithm, Gurobi and learning-based methods on a machine with 32 virtual CPU system (2 * Xeon(R) E5-2620)) and 8 * 2080ti. At each epoch, we test 32 instances in parallel and after 10 epochs, we report the time it takes to solve on each test instance (in Table 2 ).

5.4. GENERALIZATION TO LARGER PROBLEMS:

In order to explore the generalization of our method, we train the GNN on TSP100 random instances and test our method on random instances including TSP200, TSP300 and TSP500. We mainly compare the learning-based methods proposed by Kool et al. and Dai et al. which made the best performance before our work respectively in Encoder-Decoder and Graph Embedding framework. The results (in Table 3 ) show that our algorithm could generalize to larger problems well than other learning-based algorithms even if trained in the small-scale instances.

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 1) 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 best (biggest) action value as the next move in the root position. 2) average. As with the strategy used in AlphaGo, 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 as the next move in the root position.

Table 1 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 ave. to denote "average" strategy. The empirical results show that using the "best" strategy is 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 contributes to the presented approach. First, we use our GNN to generate solutions in a greedy way, i.e., selecting the vertex with the biggest prior probability at each step; we refer to this version as GNN-MCTS-t. Then we use a GNN-MCTS which replaces the value function h(s) (see in algorithm 1) with random rollout to 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 1 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 as MCTS.

Table 1 shows the gap between the solution of each approach and the best-known solution on different 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 resources 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 a suitable value function, can 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 an 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 function. Since the beam width mainly affects the accuracy of value function, we use the result of value function as a measure and report the Gap as defined in Table 1 . Specifically, we set beam width to 1, 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 4 and Table 5 show that as the beam width increases, the performance of the value function will get better while the time cost will become larger. We need to make a trade-off between accuracy and time cost.

5.6. COMPARISON WITH OTHER DEEP NEURAL NETWORKS:

Compared with the basic GNN, our 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 8 (see in appendix D).

We also compare the performance of GEN and our GNN to support the key improvements made by our GNN. Similar to the above comparison experiment, we generate tour sequences by using neural network in a greedy way. The performance of GEN and our GNN is reported in Table 8 . Furthermore, we use GEN and our GNN to guide MCTS separately on "random" and "clustered" instances, including TSP20, TSP50 and TSP100. We refer to MCTS with GEN as GEN-MCTS. Table 1 reports the quality of solutions and shows that MCTS can get shorter tours when guided by our GNN.

6. CONCLUSION:

We proposed a graph neural network assisted Monte Carlo Tree Search (GNN-MCTS) for the classical traveling salesman problem. The core idea of our approach lies in converting the TSP into a 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 in a greedy way, we designed a GNN-MCTS to provide scouting simulation so that the algorithm could avoid being stuck into the local optimum. The exper-

A INSTANCE GENERATION:

To evaluate our method against other approximation algorithms and deep learning-based approaches, we use an instance generator from the DIMACS TSP Challenge (Johnson et al., 2001) to generate two types of Euclidean instances: "random" instances consist of n points scattered uniformly at random in the [10 6 , 10 6 ] 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 a train set of 50,000 instances and a test set of 1,000 instances.

B GRAPH NEURAL NETWORK SETTINGS:

Our GNN has T = 3 node-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 0 = 9. The width of other layers are identical: H t = 64 for t = 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 use the prior probability, i.e., selecting the vertex with the biggest prior probability, to derive tour sequence. We report Gap as defined in Table 1 . The result of Table 6 show that the performance of GNN will become better as the number of network layers increases. 

:

Euclidean distance: given two points (x1, y1) and (y1, y2) in two-dimensional plane, D = (x2 -x1)

+ (y2 -y1) 2

In the experiment, we initialize the Q to -5.0, -10.0 and -15.0 respectively for TSP20, TSP50, and TSP100.

http://www.math.uwaterloo.ca/tsp/concorde/

http://www.gurobi.com/

Figures and Tables:

Figure2: Neural network architecture. The architecture on the left (A) is 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 a multilayer perceptron to output the prior probability. The picture on the right (B) depicts the mechanism of computing a new feature of the vertex in one update-layer.

Our method vs baselines. The gap % is w.r.t. the best value across all methods

Table content: <table><tr><td/><td/><td/><td/><td>Random</td><td/><td/><td/><td/><td/><td>Clustered</td><td/><td/></tr><tr><td>Method</td><td/><td>n=20</td><td/><td>n=50</td><td/><td>n=100</td><td/><td>n=20</td><td/><td>n=50</td><td/><td>n=100</td></tr><tr><td/><td colspan="2">Obj. Gap</td><td>Obj.</td><td>Gap</td><td>Obj.</td><td>Gap</td><td colspan="2">Obj. Gap</td><td colspan="2">Obj. Gap</td><td>Obj.</td><td>Gap</td></tr><tr><td>Concorde</td><td>3.92</td><td>0.0%</td><td>5.68</td><td>0.0%</td><td>7.73</td><td>0.0%</td><td>3.30</td><td>0.0%</td><td>3.38</td><td>0.0%</td><td>3.39</td><td>0.0%</td></tr><tr><td>Gurobi</td><td>3.92</td><td>0.0%</td><td>5.68</td><td>0.0%</td><td>7.73</td><td>0.0%</td><td>3.30</td><td>0.0%</td><td>3.38</td><td>0.0%</td><td>3.39</td><td>0.0%</td></tr><tr><td colspan="4">Nearest Neighbor 4.57 16.50% 7.02</td><td>23.44%</td><td>9.63</td><td colspan="5">24.58% 3.95 19.48% 4.18 23.76%</td><td>4.23</td><td>25.02%</td></tr><tr><td colspan="4">Nearest Insertion 4.40 12.24% 6.77</td><td>19.08%</td><td>9.48</td><td colspan="5">22.64% 3.66 10.62% 3.97 17.36%</td><td>4.08</td><td>20.46%</td></tr><tr><td colspan="3">Random Insertion 4.08 4.12%</td><td>6.09</td><td>7.12%</td><td>8.45</td><td>9.24%</td><td colspan="3">3.46 4.67% 3.65</td><td>7.93%</td><td>3.72</td><td>9.70%</td></tr><tr><td colspan="3">Farthest Insertion 4.03 2.73%</td><td>5.98</td><td>5.29%</td><td>8.33</td><td>7.78%</td><td colspan="3">3.40 2.87% 3.58</td><td>5.91%</td><td>3.64</td><td>7.55%</td></tr><tr><td colspan="3">Vinyals et al. (gr.) 3.97 1.30%</td><td>6.41</td><td>18.58%</td><td>-</td><td/><td>-</td><td/><td>-</td><td/><td>-</td><td/></tr><tr><td>Bello et al. (gr.)</td><td colspan="2">3.99 1.83%</td><td>5.95</td><td>4.75%</td><td>8.26</td><td>6.82%</td><td>-</td><td/><td>-</td><td/><td>-</td><td/></tr><tr><td>Kool et al. (gr.)</td><td colspan="2">3.93 0.36%</td><td>5.78</td><td>1.75%</td><td>8.08</td><td>4.57%</td><td>-</td><td/><td>-</td><td/><td>-</td><td/></tr><tr><td>Dai et al.</td><td colspan="2">4.03 2.76%</td><td>5.98</td><td>5.26%</td><td>8.33</td><td>7.76%</td><td colspan="3">3.37 2.07% 3.58</td><td>6.01%</td><td>3.66</td><td>8.17%</td></tr><tr><td>GNN-MCTS</td><td colspan="2">3.92 0.03%</td><td>5.70</td><td>0.32%</td><td>7.85</td><td>1.53%</td><td colspan="3">3.30 0.00% 3.39</td><td>0.34%</td><td>3.44</td><td>1.61%</td></tr><tr><td>MCTS</td><td colspan="12">6.37 62.45% 18.43 224.28% 40.27 420.83% 4.98 50.69% 9.26 173.99% 14.00 313.33%</td></tr><tr><td>GEN-MCTS</td><td colspan="2">3.92 0.12%</td><td>5.75</td><td>1.31%</td><td>8.08</td><td>4.53%</td><td colspan="3">3.31 0.21% 3.42</td><td>1.04%</td><td>3.55</td><td>4.72%</td></tr><tr><td>GNN-MCTS-t</td><td colspan="2">4.00 2.21%</td><td>5.98</td><td>5.26%</td><td>8.61</td><td colspan="4">11.34% 3.37 2.19% 3.57</td><td>5.61%</td><td>3.73</td><td>10.22%</td></tr><tr><td>GNN-MCTS-p</td><td colspan="2">3.92 0.09%</td><td>5.77</td><td>1.47%</td><td>8.06</td><td>4.24%</td><td colspan="3">3.31 0.14% 3.44</td><td>1.70%</td><td>3.54</td><td>4.39%</td></tr><tr><td>GNN-MCTS-v</td><td colspan="2">3.92 0.08%</td><td>5.77</td><td>1.64%</td><td>8.06</td><td>4.24%</td><td colspan="3">3.30 0.04% 3.42</td><td>1.13%</td><td>3.58</td><td>5.67%</td></tr><tr><td>GNN-MCTS ave.</td><td colspan="2">3.98 1.62%</td><td>6.09</td><td>7.21%</td><td>8.83</td><td colspan="4">14.23% 3.34 1.25% 3.63</td><td>7.27%</td><td>3.87</td><td>14.11%</td></tr><tr><td colspan="3">5 EXPERIMENTS</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="4">5.1 EXPERIMENTAL SETUP</td><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>



Table content: <table><tr><td/><td colspan="3">Running times of different method</td><td colspan="4">Table 3: Gap of different methods on larger in-</td></tr><tr><td/><td colspan="3">TSP20 TSP50 TSP100</td><td>stances</td><td/><td/><td/></tr><tr><td>Dai et al.</td><td colspan="2">0.007s 0.018s</td><td>0.043s</td><td/><td colspan="3">TSP200 TSP300 TSP500</td></tr><tr><td colspan="3">Kool et al. 0.036s 0.054s</td><td>0.084s</td><td>Kool et al.</td><td>8.19%</td><td colspan="2">12.32% 20.40%</td></tr><tr><td>Gurobi</td><td>0.017s</td><td>0.2s</td><td>1.9s</td><td>Dai et al.</td><td colspan="3">11.11% 11.70% 11.84%</td></tr><tr><td>Our</td><td>3.2s</td><td>6.6s</td><td>31.4s</td><td>Our</td><td>1.91%</td><td>2.99%</td><td>4.37%</td></tr></table>



Table content: <table><tr><td colspan="4">: Gap of different beam width</td><td colspan="3">Table 5: Time cost of different beam width</td></tr><tr><td/><td>w=1</td><td>w=5</td><td>w=10</td><td/><td>w=1</td><td>w=5</td><td>w=10</td></tr><tr><td>TSP20</td><td colspan="3">2.25% 1.50% 1.50%</td><td>TSP20</td><td>55ms</td><td>265ms</td><td>534ms</td></tr><tr><td>TSP50</td><td colspan="3">5.32% 3.64% 3.38%</td><td colspan="3">TSP50 147ms 730ms 1461ms</td></tr><tr><td colspan="4">TSP100 11.37% 8.11% 7.48%</td><td colspan="3">TSP100 323ms 1639ms 3338ms</td></tr></table>

Effect of the number of layers on random instances

Table content: <table><tr><td/><td colspan="2">Layers T=1</td><td>T=2</td><td>T=3</td></tr><tr><td/><td>Gap</td><td colspan="3">5.1% 3.2% 2.2%</td></tr><tr><td colspan="5">C CONFIDENCE INTERVAL ON DIFFERENT CONFIDENCE LEVELS</td></tr><tr><td colspan="5">Table 7: Confidence interval on different confidence levels</td></tr><tr><td colspan="2">Confidence level</td><td>90%</td><td colspan="2">95%</td><td>99%</td></tr><tr><td/><td colspan="4">n=20 3.922±0.046 3.922±0.054 3.922±0.071</td></tr><tr><td>Random</td><td colspan="4">n=50 5.701±0.041 5.701±0.048 5.701±0.064</td></tr><tr><td/><td colspan="4">n=100 7.850±0.039 7.850±0.047 7.850±0.062</td></tr><tr><td/><td colspan="4">n=20 3.305±0.078 3.305±0.093 3.305±0.122</td></tr><tr><td>Clustered</td><td colspan="4">n=50 3.391±0.051 3.391±0.061 3.391±0.080</td></tr><tr><td/><td colspan="4">n=100 3.442±0.036 3.442±0.043 3.442±0.056</td></tr><tr><td colspan="4">D PERFORMANCE OF DIFFERENT NETWORKS</td></tr><tr><td/><td colspan="4">Table 8: Performance of different networks</td></tr><tr><td/><td/><td>n=20</td><td>n=50</td><td>n=100</td></tr><tr><td/><td colspan="4">GNN 4.8% 21.1% 58.9%</td></tr><tr><td/><td colspan="4">GEN 4.1% 12.5% 21.9%</td></tr><tr><td/><td>Our</td><td colspan="3">2.2% 5.3% 11.3%</td></tr></table>

Peer review (iclr2020):
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. I 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. First, 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? Additionally, 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. In 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. Minor comments: - 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. - 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. - 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. - 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. - In Sec. 4.1, it is unclear what is meant by *improved probability hat{P} of selecting the next vertex*. - 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. Suggestions for improvement (no impact on review): - Clarity: the language in the 3rd and 4th paragraphs of the introduction [begins with *In this paper, ...*] could be made clearer. - 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. - *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. - Equation formatting: Please use *left(* and *ight)* for putting parenthesis around taller symbols, like sum. - 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).