Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero
Authors: Kenshin Abe
Zijian Xu
Issei Sato
Masashi Sugiyama
Venue:  (2021)
Keywords: Graph neural network
Combinatorial optimization
Reinforcement learning

Abstract: There have been increasing challenges to solve combinatorial optimization problems by machine learning. 
Khalil et al. (NeurIPS 2017) proposed an end-to-end reinforcement learning framework, which automatically learns graph embeddings to construct solutions to a wide range of problems.
However, it sometimes performs poorly on graphs having different characteristics than training graphs.
To improve its generalization ability to various graphs, we propose a novel learning strategy based on AlphaGo Zero, a Go engine that achieved a superhuman level without the domain knowledge of the game.
We redesign AlphaGo Zero for combinatorial optimization problems, taking into account several differences from two-player games.
In experiments on five NP-hard problems such as {\sc MinimumVertexCover} and {\sc MaxCut}, our method, with only a policy network, shows better generalization than the previous method to various instances that are not used for training, including random graphs, synthetic graphs, and real-world graphs.
Furthermore, our method is significantly enhanced by a test-time Monte Carlo Tree Search which makes full use of the policy network and value network.
We also compare recently-developed graph neural network (GNN) models, with an interesting insight into a suitable choice of GNN models for each task.

Under review as a conference paper at ICLR 2021
SOLVING NP-HARD PROBLEMS ON GRAPHS WITH Ex- TENDED ALPHAGO ZERO
Anonymous authors Paper under double-blind review
ABSTRACT
There have been increasing challenges to solve combinatorial optimization prob- lems by machine learning. Khalil et al. (NeurIPS 2017) proposed an end-to-end reinforcement learning framework, which automatically learns graph embeddings to construct solutions to a wide range of problems. However, sometimes performs poorly graphs having different characteristics than training graphs. To improve its generalization ability to various graphs, we propose a novel learning strategy based on AlphaGo Zero, a Go engine that achieved superhuman level without the domain knowledge of the game. We redesign AlphaGo Zero for combinatorial optimization problems, taking into account several differences from two-player games. In experiments on five NP-hard problems such as MINIMUM VERTEX- COVER and MAXCUT, our method, with only policy network, shows better generalization than the previous method to various instances that are not used for training, including random graphs, synthetic graphs, and real-world graphs. Furthermore, our method is significantly enhanced by test-time Monte Carlo Tree Search which makes full use of the policy network and value network. We also compare recently-develope interesting insight into suitable choice GNN models for each task.
graph neural network (GNN) models, with an
INTRODUCTION
There is no polynomial-time algorithm found for NP-hard problems [7], but they often arise in many real-world optimization tasks. Therefore, variety of algorithms have been developed in a long history, including approximation algorithms [2, 14], meta-heuristee based on local searches such as simulated annealing and evolutionary computation [15, 10), general-purposs. exact solvers such as CPLEX and Gurobi [16], and problem-specific exact solvers [1, 25).
Recently, machine learning approaches have been actively investigated to solve combinatorial opti- mization, with the expectation that the combinatorial structure of the problem can be automatically learned without complicated hand-crafted heuristics. In the early stage, many of these approaches focused on solving specific problems [17, 5] such the traveling salesperson problem (TSP). Khalil et al. [19] proposed a general framework to solve combinatorial problems by a combination of reinforcement learning and graph embedding, which attracted attention for the following does not require any knowledge on graph algorithms other than greedy selection based on network outputs. Furthermore, learns algorithms without any training dataset. Thanks these advantages, the framework can be applied to diverse range of problems over graphs and it also performs much better than previous learning-basse based approaches. However, we observed poor empirical performance on some graphs having different characteristics (c.g., synthetic graphs and real-world graphs) than random graphs that were used for training, possibly because of the limited exploration space their Q-learning method.
reasons:
In this paper, to overcome its weakness, we propose novel solver, named CombOpt Zero. CombOpt Zero is inspired by AlphaGo Zero [33], a superhuman engine of Go, which conducts Monte Carlo Tree Search (MCTS) to train deep neural networks. AlphaGo Zero was later generalized to AlphaZero [34] so that it can handle other games; however, its range of applications is limited to two-player games whose state is win/lose (or possibly draw). We extend AlphaGo Zero to a bunch of combinatorial
www.cplex.com

---

Under review as a conference paper at ICLR 2021
problems by simple normalization technique based on random sampling. In the same way as AlphaGo Zero, CombOpt Zero automatically learns a policy network and value network by self-play based on MCTS. We train our networks for five kinds of NP-hard tasks and test on different instances including standard random graphs (e.g., the Erdös-Renyi model [11] and the Barabási-Alber model [3)) benchmark graphs, and real-world graphs. We show that, with only greedy selection on the policy network, CombOpt Zero has a better generalization to a variety of graphs than the existing method, which indicates that the MCTS-based training strengthens the exploration of various actions. When more computation time is allowed, using the MCTS at test time with the full use of both the policy network and value network significantly improves the performance. Furthermore, we combine our framework with several graph neural network models [21, 39, 28), and experimentally demonstrate that an appropriate choice of models contributes to improving the performance with significant margin.
BACKGROUND
In this section, we introduce the background which our work is based on.
2.1
MACHINE LEARNING FOR COMBINATORIAL OPTIMIZATION
Machine learning approaches for combinatorial optimization problems have been studied in the literature, starting from Hopfield & Tank [17], who applied variant of neural networks to small instances of Traveling Salesperson Problem (TSP). With the success of deep learning, more and more studies were conducted including Bello et al. [5], Kool et al. [23] for TSP and Wang al. [37] for MAXSAT.
Khalil et al. [19] proposed an end-to-end reinforcement learning framework S2V-DQN, which attracted attention because of promising results in a wide range of problems over graphs such as MINIMUM VERMUMMEEREE and MAXCUT. Another advantage of this method is that does not require domain knowledge Q-network (DQN) where the Q-function is upproximated by a graph embedding network, called structure2vec (S2V) [9]. The DQN is based on their reinforcement learning formulation, where each action is picking up a node and each state represents the "sequence of actions". In each step, a partial solution S C V. i.e., the current state, is expanded by the selected vertex v² = arg ma V(N(S)) (h((S),) v) to (S))",, where f(-) is a fixed function determined by the problem that maps state to a certain graph, so that the selection of will not violate the problem constraint. For example, in MAXIMUMINDEPENENTTS
specific algorithms or any training dataset. It optimizes deep
h(S) corresponds to the subgraph of the input graph = (V, E) induced by VS(S UN()), where ((S) is the open neighbors of S. The immediate reward is the change in the objective function. The Q-network, i.e, S2V learns fixed dimensional embedding for each node.
In this work, we mitigate the issue of S2V-DQN's generalization ability. We follow the idea of their reinforcement learning setting, with a different formulation, and replace their Q-learning by a novel learning strategy inspired by AlphaGo Zero. Note that although some studies combine classic heuristic algorithms and learning- based approaches (using dataset) to achieve the state-of-th of-te-----e-r performance [26, 12], we stick to learning without domain knowledge and dataset in the same way as S2V-DQN.
2.2 ALPHAGO ZERO
AlphaGo Zero [35] is well-known superhuman engine designed for use with the game of Go. It trains deep neural network fo with parameter 0 by reinforcement learning. Given a state (game board), the network outputs fs( (p, v). where p is the probability vector of each move and v E 1-1, 1] is a scalar denoting the state value. If v is close to 1, the player who takes a corresponding action from state is very likely to win.
The fundamental idea of AlphaGo Zero is to enhance its own networks by self-play. For this self-play special version of Monte Carlo Tree Search (MCTS) [22], which we describe later, is used. The network is trained in such a way that the policy imitates the enhanced policy by MCTS π, and the value imitates the actual reward from self play (i.e. if the player wins and z -1 otherwise).
2

---

Under review as a conference paper at ICLR 2021
More formally, it learns to minimize the loss
L = (2 v)² + CrossEEtroppy(p T) + Grog |0|
where Crog is nonnegative constant for L2 regularization.
MCTS is heuristic search on game trees. In AlphaGo Zero, the search tree is rooted tree, where each node corresponds to a state and the root the initial state. Each edge (s, a) denotes action a at state and stores tuple (N(s, a); ((,, a), Q(s a), P(x,a) where (ss, a) is the visit reseectiveee count, W(s. (s, a) and ((,, a) are the total and mean action value respectively, and P(s, a) the prior
probability. One iteration of MCTS consists of three parts: select, expand, and backup. First, from the root node, we keep choosing an action that maximizes an upper confidence bound
VLA ((s.a)) Q(s.a) + Cpuct P(s,a) a) 1+ 1+,(s,a)
where Cpuct is a non-negative constant (select). Once it reaches to unexplored node s, then the edge values are initialized using the network prediction (p, v) fe(s) (expand). After expanding new node, each visited edge is traversed and its edge values are updated (hackup) so that Q maintain the mean of state evaluations over simulations: Q(s,a) N(s.a) Es'(a.--s' Us', where the sum is taken over those states reached from after taking action After some iterations, the probability vector
((so,a)+/+ for each Asp where calculated by πa Σ. (xa.b))//
temperature parameter.
AlphaGo Zero defeated its previous engine AlphaGo [33] with 100-0 score without human knowledge, i.e., the records of the games of professional players and some known techniques in the history of Go. We are motivated to take advantage the AlphaGo Zero technique in our problem setting since also aim at training deep neural networks for discrete optimization without domain knowledge. However, we cannot directly apply AlphaGio Zero, which was designed for two-player games, to combinatorial optimization problems. Section 3.2 and 3.3 explains how resolve this issue.
2.3 GRAPH NEURAL NETWORK
A Graph Neural Network (GNN) is a neural network that takes graphs as input. Kipf & Welling [21] proposed the Graph Convolutional Network (GCN) inspired by spectral graph convolutions. Because of its scalability, many variants of spatial based GNN were proposed. Many of them can be described as a Message Passing Neural Network (MPNN) [13]. They recursively aggregate neighboring feature vectors to obtain node embeddings that capture the structural information of the input graph. The Graph Isomorphism Network (GIN) [39] is one of the most expressive MPNNs in terms of graph isomorphism. Although they have good empirical performance, some studies point out the limitation of the representation power of MPNNs [39, 30). Maron et al. [27] proposed an Invariant Graph Network (IGN) using tensor representations of graph and was shown be universal [29, 18). Since requires high-order tensor in middle layers, which is impractical, Maron et al. [28] proposed 2-IGN+, a scalable and powerful model.
All of these models, as well as S2V [9] used in S2V-DQN, are compared in the experiments to test the difference in the performance for combinatorial optimization. The detail of each model is described in Appendix B.
3 METHOD
In this section, we give a detailed explanation of our algorithm to solve combinatorial optimization problems over graphs. First, we introduce our reinforcement learning formulation for NP-hard problems. Then, we explain the basic ideas of our proposed CombOpt Zero in light of the difference between 2-player games and our formulation. Finally, we describe the whole algorithm.
3.1 REDUCTION TO MDP
Following S2V-DQN [19], reduce graph problems into reinforcement learning setting. Here, introduce our formulation based on a Markov Decision Process (MDP) [4]. A deterministic MDP is defined (S, A,, T, R),, where S' is set of states, A, is set of actions from the state S,
3

---

Under review as a conference paper at ICLR 2021
S0
$1
$2
$3
.44
(0:20
(9.9)
(L.)
R(so.
R(s
0
R(52.
R(53.
Figure I: Example of MaxCut MDP trainsitions. In the transition sequence, the upper left and center node are colored in o, the right and lower left node are colored o, resulting in the cumulative reward 3.
T: S A, + S is a deterministic state transition function, and : S x A₂ - R is an immediate reward function. our problem setting on graphs, each state 8 E S is represented as a labeled graph, a tuple = dG. G = (V, E) is graph and d: V + is node-labeling function, where T. is label space.
For each problem, we have set of terminal states Send Given state repeat selecting an action a from A, and transiting to the next state T(s, a). until s Send holds. By this process, we get sequence of states and actions [so, Gos $1, (11 ..., QN-1 SN] of N steps where & E Send- which we call a trajectory. For this trajectory, we can calculate the simple sum of immediate rewards EN-1 R(s,, an), and we define r" (s) be the maximum possible sum of immediate rewards out of all trajectories from state s. Let Init be function that maps the input graph the initial state. Our goal is to, given graph Go, obtain the maximum sum of rewards r" (Init(Go))
Many combinatorial optimization problems can be accomodated in this framework by appropriately defining L. A,, T, R. Init, and Sond (see Appendix G). Now we take MAXCUT as an example. Let C. be cut set between V' C V and V'V, i.e., {(u, v) MAXCUT asks for subset V that maximizes the size of cut set C. Below, we explain our MDP formulation of MAXCUT.
u E V', ve V\V)).
In each action, we color node by 0 or 1 and remove it while each node keeps track of how many adjacent nodes have been colored with each color. A, = {(x,e) e) x E V,C E {0, 1}} denotes a set of possible coloring of node, where (I, means coloring node x with color L = N², representing the number of colored (and removed) nodes in each color (i.e., 4o is the number of (previously) adjacent nodes of z colored with 0, and same for 41, where / = d(x)). Init uses the same graph as Go and sets d(x)) = (0, 0) for all x E V. T(s, (2,, c)) increases the e-th value of d(xx) by one for x' N(x)) and removes and neighboring edges from the graph. Send is the states with the empty graphs. R(s, (zr, c)) is the (1 c)-th (i.c., 1 if e = 0 and 0 if c 1) value of d(x), meaning the number of edges in the original graph which has turned out to be included in the cut set (i.e., colors of the two nodes are different).
Figure 1 shows some possible MDP transitions for MAXCUT. It is easy check that finding a sequence that maximizes the sum of rewards is equivalent to solving the original problem. One of the important differences from the formulation of Khalil et al. [19] is that we do not limit the action space to a set of nodes. This flexibility enables the above formulation, where actions represent node coloring. See Appendix F for the details.
3.2 EXTENDING ALPHAGO ZERO
We have seen that many combinatorial optimization problems can be reduced to the deterministic MDP formulation, which is similar to the problem setting of AlphaGo Zero However, since AlphaGo Zero is designed exclusively for Go (or AlphaZero for two-player games), it still can not be directly applied for our MDP settings. Here, we cxplain how to extend AlphaGo Zero to our MDP formulation of combinatorial problems with respect to three main differences from Go.
Graph Input In our problem setting, the states are represented by (labeled) graphs of different sizes, while the boards of Go can be represented by 19 19 fixed-size matrix. This can be addressed easily
4

---

Under review as a conference paper at ICLR 2021
50
+ R ap)
R()
Mn + on max
52
Figure 2: Backup. After estimating the reward of the expanded node, we iteratively update the rewards of its ancestors.
by adopting GNN instead of convolutional neural networks in AlphaGo Zero, just like S2V-DQN. The whole state s = (G, d) can be given to GNN, where the coloring d is used as the node feature.
Range of Final Results While the final result of Go is only win or lose (or possible draw), the answer to combinatorial problems can take any integer or even real number. AlphaGo Zero models the state value with the range of [-1, 1]. meaning that the larger the value is, the more likely the player is to win. A naive extension of this is to directly predict the maximum possible sum of rewards r" (s). That may, however, grow infinitely in our problem setting usually depending on the graph size, which causes issues. In our preliminary experiments, it did not work well due to difficulty in balancing the scale in equation I or in equation 2. For example, in equation 2, the first term could be too large when the answer is large, causing less focus on P(s, a) and N (N, To mitigate these issues, propose a reward normalization technique. Given a state s, the network outputs (p. q) - fo(s). While p is the same as AlphaGo Zero (action probabilities), is vector representing normalized state action value instead of a scalar state value. Intuitively. qa predicts "how good the reward is compared to the solution obtained by random actions" when taking action a from state 8. Formally, we train the network so that la predicts (R(s, a) + r* (T(s; a)) /a)//.,. where Hıs and o, are the mean and the standard deviation of the cumulative rewards by random plays from state s. Similarly, we also let W(s, a) and (s,, a) hold the sum and mean of normalized action value estimations over the MCTS iterations. By virtue of this normalization, we no longer need to care about the difference of scales in equation 1 and equation 2. When we estimate the state value of s, we consider taking action a which maximizes qa and restoring the unnormalized value by u4 and 0g:
S0 (1s + a, (maxae A, qa) (otherwise).
(s E Send),
Testim (s)
(3)
Various Immediate Rewards Since the immediate reward of Go is always zero, the backup phase of AlphaGo Zero is simple: Update each edge value so that Q(s, a) keeps the mean of state value predictions over expanded states from after taking action a. Although we have various immediate rewards in our MDP formulations, all of these can be handled easily. Each time we go back to the parent node in the backup, add the immediate reward of the edge to the current reward: r + + R(s, a) when going up path (s, a). Note that since we use normalization technique, is initialized by equation 3. Figure illustrates the process. We can apply the same strategy when calculating the normalized cumulative reward in data generation (See Section 3.3 for the details).
3.3 ALGORITTMS
Based on the discussion so far, now we are ready to introduce the whole algorithm of our proposed CombOpt Zero.
Each edge stores a tuple (N a), W(s, a), Q(s, P(s, a)) in the same way as AlphaGo Zero. Additionally, each node s stores a tuple (Ms:ox), the mean and the standard deviation of the results by random plays. Given an initial state sp. we repeat the iterations of the three parts: select, expand, and backup. Select is same as AlphaGo Zero (keep selecting a child node that maximizes equation 2). Once we reach unexpanded node 5, we expand the node. (p, q) fa(s) is evaluated and each edge value is updated as N(s, a) = O, W(s, a) = O, Q(s, a) = O, and P(s, a) = Pa for Ay. At the same time, (Ma, o.) is estimated by random sampling from In backup. for each node& s' and the corresponding action in a backward pass, (ss', a') is incremented by one in the same way AlphaGo Zero. The difference is that Q(8 a') is updated hold the estimation of the
MCTS
5

---

Under review as a conference paper at ICLR 2021
normalized mean reward from s'. We approximate the non-normalized state value by equation and calculate the estimated cumulative reward from s' by adding the immediate reward each time move back to the parent node (Figure 2 illustrates this process). After sufficient iterations, π is calculated from (s0. a) in the same way as AlphaCio Zero. While the number of the iterations is fixed in AlphaGo Zero, in our proposed CombOpt Zero, since the size of action space differs by states, we make it proportional to the number of actions: As. Following AlphaGo Zero, we add Dirichlet noise to the prior probabilities only for the initial state so explore the various initial actions. The pseudocode is available in Algorithm 1 in Appendix A.
Training Following AlphaGo Zero, the training of CombOpt Zero is composed of three roles: data generators, learners, and model evaluators. The model that has performed best so far is shared among all of these three components. The data generator repeats generating self-play records for a randomly generated graph input, by the MCTS based on the current best model. The records are the sequence of (s, a, π, z²), which means action a was taken from s depending on the MCTS-enhanced policy and the normalized final cumulative reward was z'. 2' can be calculated in the same way as backup in MCTS: after generating the self-play trajectory, it first calculates the cumulative sum of immediate rewards for each state in reverse order and normalizes them with μl, and 0s- The pseudocode of the data generator is available in Algorithm in Appendix A. The learner randomly samples mini-batches from the generator's data and updates the parameter of the best model so that minimizes the loss
C (='--qo.) 400²²= + CrossEntropy (p. π + Greg 1|12.
We train qu to be closer to the normalized cumulative reward 2'. The model evaluator compares the updated model with the best one and stores the better one. Since we can not put two players in match, the evaluator generates random graph instances each time and compare the performance on them.
EXPERIMENTS
In this section, show some brief results of our experiments mainly on MINIMUMWVERTEXCOVERR MAXCUT, and MAXIMUMCLIQUE. Refer to Appendix for the full results and Appendix for further analyses for each problem.
Competitors Since we aim at solving combinatorial optimization problems without domain knowl- edge or training dataset, S2V-DQN our main competitor. Additionally, for each problem, we prepared some known heuristics or approximation algorithms to compare with. For instance, for MIN- IMUM V I VEREXCOVER we implemented simple randomized 2-approximation algorithm (2-approx) and an interger programming by CPLEX solver. For MAXCUT, we used randomized algorithm by semidefinite programming [14] and two heuristics, non-lineat optimization with local search [6] and cross-entropy method with local search [24] from MQLib [10]. See Appendix H for competitors of other problems and the details.
Training and Test We trained the models for two hours to make the training of both CombOpt Zero and S2V-DQN converge (Only 2-IGN+ was trained for four hours due to its slow inference). Note that CombOpt Zero was trained on 4 GPUs while S2V-DQN uses single GPU because of its implementation, which we discuss in Section 4.4. For the hyperparameters of the MCTS, we referred the original AlphaGo Zero and its reimplementation, ELF OpenGo [36]. See Appendix C for the detailed environment and hyperparameters. Since we sometimes observed extremely poor performance for a few models both in S2V-DQN and CombOpt Zero when applied to large graphs, we trained five different models from random parameters and took the best value among them at the test time. Throughout the experiments, all models were trained on randomly genrated Erdös-Remt Renyi (ER) [11] graphs with 80 < n < 100 nodes and edge probability p 0.15 except for MAXCUT, where nodes were 40 < n < 50 and for MAXIMUMCLIQUE, where edge probability was p = 0.5. As the input node feature of MAXCUT, we used a two-dimensional feature vector that stores the number of adjacent nodes of color 1 and color 2. For the other problems, we used a vector of ones. In tests, to keep the faimess, CombOpt Zero conducted greedy selection network policy output p. which is the same way as S2V-DQN works (except for Section 4.2 where we compared the greedy selection and MCTS).

---

Under review as a conference paper at ICLR 2021
Table 1: Generalization Comparision between CombOpt Zero and S2V-DQN. COZ and DQN are short for CombOpt Zero and S2V-DQN respectively. Smaller is better for MINIMUM VERTEX- COVER and larger better for MAXCUT. Three sections stand for Erdós-Rent Renyi models, other syntheric graphs such as BA graphs and Watts-Strogatz graphs, and real-world graphs.
MVC
MAXCUT
MVC
MAXCUT
COZ
DQN
COz
DQN
COZ DQN
COZ
DQN
cr100_1
76
76
494
527
er er1000
900
898
12561
14424
er5000_
4484
4482
63389
71909
ba ha100_5
63
63
337
343
cora
1258
1258
4260
4243
ba0000 5
592
594
3492
3465
citeseer
1462
1461
3933
3893
ba5000_5 5
2920
2927
17381
16870
web-edu
1451
1451
4712
4289
ws100
web-spam
2299
2319
20645
21027
ws100
78
78
335
335
road-min,
1324
1329
3080
3015
ws ws1000 2
492
496
999
973
bio-yeast
456
457
1769
1751
ws ex1000044
635
636
1536
1327
bio-SC-..
1039
1053
10893
11890
ws1000_
787
784
3312
3287
rt dama
369
369
3698
3667
reg_ 100_5
63
207
205
soc-wiki...
407
406
2119
2064
reg 1000_5
632
634
2051
2046
socfb-bo...
1796
1793
42063
37140
tree tree100
44
44
99
98
tree 1000
439
440
999
982
Table 2: Improvement by test-time MCTS for MAXIMUMCLIQUE, Larger is better. Results with test-time MCTS shown in the parentheses. Bold values the best solution among learning based approaches (COZ and S2V-DQN). Underlined values are the best among all methods.
CombOpt Zero
2-IGN+
GIN
GCN
S2V
S2V-DQN
CPLEX
cora
4
(5)
4
(5)
3
(5)
4
(5)
4
5
citeseer
4
(6)
5
(6)
4
(6)
4
(6)
4
6
web-cdu
16
(30)
16
(30)
16
(16)
16
(30)
16
30
web-spam
10
(20)
16
(17)
7
(17)
(17)
16
20
soc- sik-wiki-vote
5
(7)
(7)
6
(7)
6
(7)
6
7
socfb-bowdoin47
14
(23)
15
(23)
7
(22)
13
(23)
14
23
Dataset We generated ER and Barabási-Albert (BA) graphs [3] of different sizes for testing. ER100_1 15 denotes ER graph with 100 nodes and edge probability p 0.15 and BA BA100_5 denotes a BA graph with 100 nodes and 5 edges addition per node. Also, we used 10 real-world graphs from Network Repository [32], including citation networks, web graphs, bio graphs, and road map graphs, all of which were handled as unlabeled and undirected graphs. Refer to Appendix H for the full results on these 10 graphs. For MINIMUM V VERTEX and MAXMUMINDEEENDENTTE additionally tested on DIMACS 2, difficult artificial instances. We generated other synthetic instances Section 1.
we
4.1 COMPARISON GENERALIZATION ABILITY
We compared the generalization ability of CombOpt Zero and S2V-DQN to various kinds of graphs. To see the pure contribution CombOpt Zero, here CombOpt Zero incorporated the same graph representation model as S2V-DQN, namely S2V. Table shows the performance for MINIMUM TEXCOVER and MAXCUT on various graph instances (see Appendix C for the explanation of each graph). While S2V-DQN had better performance on ER graphs, which were used for training, CombOpt Zero showed a better generalization ability to the other synthetic graphs such as BA graphs, Watts-Strogate graphs [38], and regular graphs (i.e., graphs with the same degree of nodes). It was interesting that CombOpt Zero successfully learned the optimal solution of MAXCUT on trees (two-coloring of puts all the edges into the set), while S2V-DON does not. Appendix
hhtps://uringg.e.hbbg.uuu h/tt:///wmmn////eeeeeeooooore.m

---

Under review as a conference paper at ICLR 2021
visualizes how CombOpt Zero achieves the optimal solution trees. CombOpt Zero also generalized better to real-world graphs although S2V-DQN performed better on a few instances, which might be because some real-world graphs have similar characteristies ER random graphs.
4.2 TEST-TIME MCTS
The greedy selection in Sections 4.1 and 4.3 does not make full use of CombOpt Zero. When more computational time is allowed test-time, CombOpt Zero can explore better solutions using the MCTS. Since the MCTS on large graphs takes a long time, we chose MAXIMUMCLIQUE as case study because solution sizes and the MCTS depths are much smaller than the other problems. We used the same algorithm as in the training (Algorithm 1) with the same iteration coefficient (Cter = 4) and 7 0, and selected an action based on the enhanced policy л. In all the instances, the MCTS finished in a few minutes on a single process and single GPU, thanks to the small depth of the MCTS tree. The improvements are shown in Table 2. Note that the solutions by CPLEX except for scfb-bowdoin was optimal since the execution finished within the cut-off time. Considering this fact, CombOpt Zero with test-time MCTS gaining the same result CPLEX all the instances, while S2V-DQN on no instances, is promising.
4.3 COMBINATION WITH DIFFERENT GNN MODELS
We compared the performance of CombOpt Zero with four different GNN models (2-IGN+, GIN, GCN, and S2V). See Appendix H for all the results of the 5 problems. One interesting insight was that the best GNN models were different across the problems. For example, while GIN had the best performance in MAXCUT, GCN performed slightly better in MINIMUM Although GCN performed significantly worse in MAXCUT, it did almost the best for the other four hard problems. 2-IGN+, a theoretically more expressive GNN, did not work well except for MAXIMUMCLIQUE. Since we observed that the performance training instances did not significantly differ among different GNN models, the test performance difference is possibly because of the generalization ability of each GNN for specific combinatorial structure, which we put as future research. Overall, CombOpt Zero was strongly enhanced with a proper GNN model. Also, is worth noting that, in few instances, CombOpt Zero outperformed CPLEX on MUNIMUMVERTEXCOV or SOTA heuristic solvers on MAXCUT (see Table 5 and Table 6 in Appendix I).
4.4 TRADEOFFS BETWEEN COMBOPT ZERO AND S2V-DQN
Here, we summarize some characteristics of CombOpt Zero and S2V-DQN. During the training, CombOpt Zero used 32 processes and four GPUs described in Appendix C, while S2V-DQN used a single process and GPU because of its implementation. CombOpt Zero takes a longer time to generate self-play data than S2V-DQN due to the MCTS process. For this reason, CombOpt Zero needs a more powerful environment to obtain stable training. On the other hand, since CombOpt Zero much more sample-efficient than S2V-DQN (see Appendix D), the bottleneck of the CombOpt Zero training is the data generation by the MCTS. This means that it can be highly optimized with an enormous GPU or TPU environment as in Silver et al. [35], Silver al. [34), and Tian al. [36].
By its nature, S2V-DQN can be also combined with other GNN models than S2V. However, S2V- DQN is directly implemented with GPU programming, is practically laborious to combine various GNN models. On the other hand, CombOpt Zero is based on PyTorch franework [31] and it is relatively easy to implement different GNN models.
5 CONCLUSION
In this paper, we presented a general framework, CombOpt Zero, to solve combinatorial optimization on graphs without domain knowledge. We showed that CombOpt Zero worked well for combinatorial problems in relatively small computational resources (four GPUs) compared to the original AlphaGo Zero. The Monte Carlo Tree Search (MCTS) in the training time successfully helped the wider explo- ration than the existing method and enhanced the generalization ability to various graphs. Another advantage of our method is that the test-time MCTS significantly strengthened the performance more computation time is allowed.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
[1] Takuya Akiba and Yoichi Iwata. Branch-and-reduce exponential/fpt algorithms in practice: A case study of vertex cover. Theoretical Computer Science, 609:211-224 2016.
[] Vincet Bafna, Piotr Berman, and Toshihiro Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM Journal on Discrete Mathematics, 12(3):289- 297, 1999.
[3] Barabási and Albert. Emergence of scaling in random networks. Science, 286 5439:509-12, 1999.
[4] Richard Bellman and Ronald Albert Howard. Dynamic Programming and Markov Processes. John Wiley, 1960.
[5] Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. Neural combi- natorial optimization with reinforcement learning. ArXiv, abs/1611.000 1.09940, 2016.
[6] Samuel Burer, Renato Monteiro, and Yin Zhang. Rank-two relaxation heuristics for max- cut and other binary quadratic programs. SIAM Journal on Optimization, 12, 07 2001. doi: 10.1 10.1137/S1052222343334444
[7] Stephen A. Cook. The complexity of theorem-proving procedures. In ACM Symposium on Theory Computing, 1971.
[8] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipezuk, Michal Pilipezuk, and Saket Saurabh. Parameterized algorithms. In Springer International Publishing, 2015.
[9] Hanjun Dai, Bo Dai, and Le Song. Discriminative embeddings of latent variable models for structured data. In International Conference on Machine Learning, 2016.
[10] lain Dumning, Swati Gupta, and John Silberholz. What works best when? a systematic evaluation of heuristics for max-cut and qubo. INFORMS Journal on Computing, 00:608-624, 08 2018. doi: 10. 20.1288//occ
[11] Paul Erdos. On random graphs. Publicationes mathematicae, 6:290-297, 1959.
[12] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. In Advances in Neural Information Processing Systems, pp. I 35554-15566 2019.
[13] Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In International Conference Machine Learning, 2017.
[14] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maxi- mum cut and satisfiability problems using semidefinite programming. J. ACM, 42:1115-1145, 1995.
[15) Teofilo F. Gonzalez. Handbook of Approximation Algorithms and Metaheuristics (Chapman Hall/Cre Computer & Information Science Series). Chapman & Hall/CRC, 2007. ISBN 1584885505.
[16] LLC Gurobi Optimization. Gurobi optimizer reference manual, 2019. URL httt:://www. /www. gurobi com.
[17] John Hopfield and David W. Tank. "neural" computation of decisions in optimization problems. Biological Cybernetics, 52:141-152, 1985.
[18] Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Neural Information Processing Systems, 2019.

---

Under review as a conference paper at ICLR 2021
[19] Elias Boutros Khalil, Hanjun Dai, Yuyu Zhang, Bistra N. Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Neural Information Processing Systems, 2017.
[20] Subhash Khot and Nisheeth K Vishmoi. On the unique games conjecture. Foundations of Computer Science, volume 5, pp. 3, 2005.
[21] Thomas N. Kipf and Max Welling. Semi-supervien classification with graph convolutional networks. In International Conference Learning Representations, 2017.
[22] Levente Kocsis and Cs. Szepesvari. Bandit based monte-carlo planning. In European Conference on Machine Learning, 2006.
[23] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Reprexentations, 2018.
[24] Manuel Laguna, Abraham Duarte, and Rafael Marti, Hybridizing the cross-entropy method:
An application to the max-cut problem. Computers & Operations Research, 36:487-498, 02 2009. doi: 10. 2016//.cor:2007.100.0 10.001.
[25] Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F Werneck. Finding near-optimal independent sets at scale. Journal of Heuristics, 23(4):007-229, 2017.
[26] Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolu- tional networks and guided tree search. In Neural Information Processing Systems, 2018.
[27] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. ArXiv, abs/18 81 812.0990.. 2018.
[28) Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Neural Information Processing Systems, 2019.
[29] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International Conference on Machine Learning, 2019.
[30] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. Association for the Advancement of Artificial Intelligence, 2018
[31] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In Neural Information Processing Systems, pp. 8024 8035. Curran Associates, Inc., 2019.
[32] Ryan A. Rossi and Nesreen Ahmed. The network data repository with interactive graph analytics and visualization. Association for the Advancement of Artificial Intelligence, 2015.
[33] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484, 2016.
[34] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy P. Lillicrap, Karen Simonyan, and Demis Hassabis. Mastering chess and shogi by self- self-play with general reinforcement learning algorithm. ArXiv,
2017.
[35] David Silver, Julian Schrittwesser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 350(7676)3354, 2017.
10

---

Under review as a conference paper at ICLR 2021
[36] Yuandong Tian, Jerry Ma, Qucheng Gong, Shubho Sengupta, Zhuoyuan Chen, James Pinkerton, and C. Lawrence Zitnick. Elf opengo: An analysis and open reimplementation alphazero. In International Conference Machine Learning. 2019.
[37] Po-Wei Wang, Priya L. Donti, Bryan Wilder, and J. Zico Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In International Conference on Machine Learning 2019.
[38] Dunean J. Watts and Steven H. Strogatz. Collective dynamics of 'small-world networks, Nature, 393:440-442, 1998.
[39] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka, How powerful are graph neural networks? ArXiv, abs/ 181 810.00826, 2018.


Reviews:
[{"review_id": "oIJrg8cxzXa", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "This paper proposes an AlphaGo Zero style algorithm for training policies for solving combinatorial optimization problems. The main idea is to generate training data with MCTS for both a policy network and a value network via self-play. Different graph neural networks (GNNs) are considered as learning models to compare their performances. Empirical evaluations on 5 NP-hard class of problems are provided to demonstrate better performance than an existing RL method S2V-DQN. Comparisons are also provided with CPlex and other approximation algorithms for specific classes of problems. \n\nPositives:\n1. The adaptation of the AlphaGo Zero algorithm to combinatorial optimization problem is novel and natural. Some detailed decisions, such as normalizing reward vectors by the distribution generated with random actions, demonstrate careful considerations, and are likely to provide insights for subsequent work on adaptations for other problems.\n\n2. The comprehensive evaluations for different GNN architectures are welcome. As one would expect, there are variations in which architecture is the best for different classes of problems. \n\nNegatives:\n1. The empirical evaluations could be improved with the following additions:\na) Test-time performance of MCTS with S2V-DQN in Table 2\nb) Error bars for the results, as well as information on how many instances per problem class are used for training and testing.\nc) wall-clock time comparisons: using MCTS is used in test-time, how long would the actual wall-clock take?\n\n2. The writing could be improved a lot. It is very difficult to evaluate the paper without reading the Appendix, which contains lots of important details on the algorithm and models. For example,\na) Algorithm 2 is key in describing the data generation procedure and I found it was much easier to understand it by reading both the text description as well as the pseudocode. I suggest including it in the main paper.\nb) The main paper didin’t mention that the MCTS results were shown with S2V as the GNN. This information is in Appendix D. It is important to know that the comparison with S2V-DQN is fair.\nc) Lots of experimental results are in the Appendix as well. I understand there is a page limit but including and discussing them in the main paper would make the paper more convincing.\n\n3. The description for the model f_\\theta is incomplete. While the Appendix describes various GNNs up to the feature extraction step, the information on how the mapping from features to final predictions, action distribution and value estimations, is missing. Please provide them in the \n\n========\nPost-rebuttal comments:\nThank the authors for answering my questions. I think the current version of the paper is below the bar of acceptance at ICLR and I hope the authors can incorporate the answers to make the submission stronger in the future.", "extra_scores": {}, "extra_text": {}}, {"review_id": "eJBK9kmcZPD", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "There has been a sequence of recent works on learning heuristics for combinatorial optimization problems on graphs by treating them as Markov decision processes, and learning by reinforcement a good policy. Since the dynamics of these problems can be readily simulated, in this paper, the authors propose to use AlphaZero, a MCTS variant, with a GNN architecture to learn and predict good solutions. They compare against the approach of Khalil et al. (2017), as well as hand-made heuristics, on three benchmark problems (Min Vertex Cover, Max Cut, Max Clique). There are results on Max Independent Set and Min Feedback Vertex Set in the appendix as well.\n\nI think the main contribution of the paper is in thinking to apply MCTS/AlphaZero to these graph-based combinatorial optimization problems. To do this they need to modify the algorithm a bit, albeit in relatively straightforward ways. Now, since there is no theory, everything relies on the strength of the experimental results, but on this aspect I have issues.\n\nFirst, the authors seem to disregard relevant work done after Khalil et al. (2017). At minimum, I think comparisons with Li et al. (2018) and Mittal et al. (2019) would be warranted. Both of these papers compare against Khalil et al.'s S2V-DQN, and predate this paper, so I think comparisons against them are a must. In addition, relevant concurrent work includes Karalias and Loukas (2020) and Drori et al. (2020), which could be interesting baselines to compare. Also, in terms of literature review, it would be relevant to discuss the recent article of Xing et al. (2020) which also does MCTS, albeit for the TSP only. More generally, there is a large amount of work done with focus on the TSP/VRP, some of which could probably be generalized to any graph-based problem without too much trouble, which should at least be discussed. So the literature review is incomplete and the experimental section is missing competitors.\n\nIn addition, I found the paper not very well written. In addition to many typos, some details, even after digging in the supplementary materials, are left unclear to me.\n1) On p. 8, you write that \"[a]lso, it is worth noting that, in a few instances, CombOpt Zero outperformed CPLEX on MinimumVertexCover\", which seems to indicate that there is a time limit? If so, what is it? The supplementary materials mention (p. 21) that \"[e]mpty cells mean execution did not finish within 2 hours.\", which suggest that there's a 2h time limit for resolution? Or does this refer to the training time, since you write on p. 6 that \"[e]e trained the models for two hours to make the training of both CombOptZero and S2V-DQN converge\"? And if there is a 2h time limit for all the methods, why do you seem to limit heuristics to 10 min, as indicated on p. 14: \"[w]e set the time limit of 10 minutes for these algorithms and used the best found solution as the results.\"? Why not give them 2 hours like the rest?\n2) All these problems have integer programming formulations, so why compare against CPLEX only for Min Vertex Cover? Why not have it as competitor for Max Cut and Max Clique as well?\n3) Why is there no timings? How long did it take for the heuristics to find the solutions at test time, compared to the AlphaZero model? Both for the greedy and MCTS decoding. This should be done despite the difference in hardware.\n4) I think test-time MCTS comparisons should be reported for all problem classes, not just MaximumClique.\n\nFinally, the improvements themselves don't seem particularly big, at least in the greedy decoding case. There's only a few instance classes (all for MaxCut) where there seems to be any significant gain, and without reporting inference time, I'm not sure we can conclude much. As for the MCTS decoding, is there a way of running a similar algorithm from the learned S2V-DQN? Also, the results don't seem to have been repeated over several seeds, which should be done. This is on top of the fact that you use the best prediction among 5 different models - that is, the whole process should be repeated many times, with average objective value and test inference times reported, along with the standard deviations (see Henderson et al. 2017). For example, for the first run, the five models could use seeds 0 to 4; then for the second run, the five models could use seeds 5 to 9; etc. You could then report the average and standard deviation over the total number of runs.\n\nOverall, I think the approach that this paper proposes, namely using a MCTS/AlphaZero-type approach to learn heuristics for graph-based combinatorial optimization problems, has good potential to improve on pure RL methods. After all, since the dynamics are simple enough that we can simulate, it makes sense to make use of that fact. However, at least with the current setup, the experimental section appears too weak for me to be able to conclude that there is really an improvement, with timings, baselines and multiple seeds missing. Moreover, even with a stronger experimental methodology, right now it is not clear to me if the gains are significant. Based on this assessment I would recommend rejection.\n\nReferences\n\n[1] Li, Z., Chen, Q., & Koltun, V. (2018). Combinatorial optimization with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems (pp. 539-548).\n\n[2] Mittal, A., Dhawan, A., Manchanda, S., Medya, S., Ranu, S., & Singh, A. (2019). Learning heuristics over large graphs via deep reinforcement learning. arXiv preprint arXiv:1903.03332.\n\n[3] Xing, Z., Tu, S., & Xu, L. (2020). Solve Traveling Salesman Problem by Monte Carlo Tree Search and Deep Neural Network. arXiv preprint arXiv:2005.06879.\n\n[4] Karalias, N., & Loukas, A. (2020). Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs. arXiv preprint arXiv:2006.10643.\n\n[6] Drori, I., Kharkar, A., Sickinger, W. R., Kates, B., Ma, Q., Ge, S., ... & Udell, M. (2020). Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time. arXiv preprint arXiv:2006.03750.\n\n[7] Henderson, P., Islam, R., Bachman, P., Pineau, J., Precup, D., & Meger, D. (2017). Deep reinforcement learning that matters. arXiv preprint arXiv:1709.06560.", "extra_scores": {}, "extra_text": {}}, {"review_id": "5i5PQNd4TQ5", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "This paper applies AlphaGo Zero to solve combinatorial optimization problems on graphs, replacing the CNN with a graph neural network. The results show that the system typically generalizes better than previous work by Khalil et al to new graph distributions. \n\nOn the positive side, developing techniques which better generalize across problem distributions is an important area in which to improve learning-to-optimize techniques. The experimental results do seem to show that CombOpt Zero has an edge over the results from Khalil et al, often matching the CPLEX solution when test-time MCTS is allowed (though perhaps this shouldn't be counted too heavily, since typically the motivation for such techniques is fast test-time performance). \n\nHowever, I do not think that the paper makes a sufficient contribution to warrant publication at ICLR. The techniques used are mostly an off-the-shelf application of AlphaGo Zero, with the modifications (swapping a GNN in instead of the CNN and normalizing the rewards) being fairly direct. Investigations of off-the-shelf methods can of course be valuable, but I don't think that enough insight was gained from the experimental results in this case. Why is the AlphaGo Zero architecture/training method more effective here? What about it leads to more effective generalization, even though the in-distribution performance is roughly equal? Ultimately, it would be ideal if there was something to be learned from the results beyond the fact that this method offers an empirial advantage in some situations.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes applying AlphaGo Zero style ideas for solving combinatorial optimization problems over graphs with two changes: 
Replacing CNNs with graph neural networks
Normalization of rewards

The reviewers raised valid points about this paper.
1. Lack of technical novelty
2. Experimental results are not strong enough to draw meaningful conclusions
3. Since techniques are mostly off-the-shelf, extracting general knowledge, insights and conclusions from empirical evaluation is important, but unfortunately was missing.

I agree with the review comments. Overall, my assessment is that the paper requires more work  before it is ready for publication.
Decision: Reject