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.
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.
The authors propose an MCTS-based learned approach using Graph Neural Networks to solve the traveling salesman problem (TSP) agents. 
The 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. 
The 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.
At 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.
While 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.
With 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.
With 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.
On the basis of state of the art performance at solving the TSP using learned methods:
* 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.
* 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.
There are some additional papers that may be relevant to this line of work:
* (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) 
* (SAT, SAT Conference 2019) Learning to predict unsat cores (similar to the previous one but for SAT problems) (https://arxiv.org/abs/1903.04671)
* (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)
Some additional typos/ feedback:
* 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).
* 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.
* 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.
* 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.
* Non-exhaustive list of typos: “Rondom” —> “Random”, “provides a heuristics” —> “provides a heuristic”, “strcuture2vec” — > “structure2vec”, weird line break at top of page 8.