Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 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. 


review_title: Official Blind Review #4

final_score: rating: 1: Reject
review_content: 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.


The paper has several drawbacks:
- 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.

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

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


Additional comments:
- 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”.

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

- Table 3 title is confusing.

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: 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 '\right)' 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).
review_title: Official Blind Review #3

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