Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: To deal with the efficiency and scalability issues in current RL approaches for Max-Cut problem, this paper proposes a new method called ECORD, based on Munchausen DQN’s exploration with GNN pre-computed embedding of each vertex. Running Time Complexity is analyzed. Compared with current baselines, time complexity is reduced from O(|V|^3) to O(|V|^2). Experiments, are conducted on published dataset, show its superiority in efficiency and performance. 
main_review: Although this paper has excellent motivation for improving the efficiency of current GNN based RL for CO problems, I have some concerns about the approach and experiments. 
(1)	Although Maximum Cut problem is one of classic CO problem, it cannot represent all CO problem. For this reason, the title is much larger than the content of this paper, unless the authors can show the generalization of their method for other CO problem.
(2)	Restricting the GNN in the preprocessing step for embedding is a good idea for reducing the complexity in running time. According to experimental results, the paper states the performance is better than ECO-DQN. Then, it is very natural to raise the question: whether is the contribution of GNN very little for the performance? To answer this question, the authors should give some evidence of comparison with GNN-free graph embedding methods. 
(3)	In the experiments, the paper only compared with ECO-DQN and two simple heuristics, which cannot support to claim that the proposed method is better than current SOTA of approximate algorithms. Some of them are efficient for large-scaled problem too.
(4)	If a max-cut problem has multiple best solutions, I wonder whether the convergence of proposed approach can be guarantee with limited learning steps? Are there some test cases for this point in experiments?
(5)	The terminating condition will affect the convergence and performance of the given approach largely. The authors used 2|V| for small-scaled instances and 4|V| for large-scaled ones. Could the authors give some theoretical analysis for the necessary number of learning steps. If could not, the algorithm is hard to be used in practice.
(6)	The largest problem targeted in experiments is about just 10000 nodes. In the era of big data, the scale for testing the scalability is not enough. Many real problem graphs have millions of nodes.

summary_of_the_review: Although this paper has excellent motivation for improving the efficiency of current GNN based RL for CO problems, I have some concerns about the approach and experiments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a scalable deep neural network (DNN)-based solver for the maximum cut problem. The main idea is to use (1) a single graph neural network (GNN) pass to acquire node embeddings and (2) use sequential decoding (without using GNN) to acquire the maximum cut solution. The experiments demonstrate good performance of the proposed algorithm, in particular for speeding up the generation of solutions.    
main_review: Pros:
1. The proposed approach is solid. I think this algorithm can easily extended for solving combinatorial optimization problems other than the maximum cut problem.  
2. The empirical comparison is thorough with respect to the considered baselines. 

Cons:
1. I am mainly concerned with the empirical comparison. 
- The maximum cut problem is a representative application of semi definite programming solvers. See [1] for an example. I think this baseline is necessary for practitioners to see whether if the proposed algorithm has any useful-ness in real-world applications. 
- Gset (considered in this paper) is a popular benchmark for the maximum cut problem and there are several non-DNN-based results that can easily compared with the proposed solvers. For example, the authors can compare with [2]. 
- To my knowledge, [3] is a relatively new GNN-based combinatorial solver that can solve maxcut. Their algorithm can be applied to maximum cut with a minor changes (they solve graph partitioning problem). This comparison is important since [2] is also a GNN-based solver with running time linear with respect to the problem size. They use a single GNN-pass and decode the solution. 
2. It seems that this paper is very similar to [4] in a sense that they both use a GNN to extract node embeddings for the given problems and applies DQN-based training for a node-wise predictor to generate solutions. I think the authors can provide a more thorough comparison between two methods. My current understanding is that [4] pretrains a GNN using supervised learning and ECORD use end-to-end truncated backpropagation.

Minor comments:
1. Ablation studies on using DQN over M-DQN would be useful to see whether if the empirical improvement comes from the proposed scheme, or simply using a better RL algorithm.
2. I hope the authors could provide more reference and related works on ways to solve the maximum cut problem without using DNN.

[1] Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, 1995
[2] Breakout Local Search for the Max-Cut Problem, 2012
[3] Erdos Goes Neural: an Unsupervised Learning ˝ Framework for Combinatorial Optimization on Graphs, 2020
[4] Learning heuristics over large graphs via deep reinforcement learning, 2019
summary_of_the_review: I think this paper is based on a solid idea and shows good empirical performance. However, at the current state, it is hard to access the significance of this paper since baseline algorithms used in real-world is missing. Furthermore, I would like to see description on the proposed algorithm's difference to existing work of Manchanda et al., (2019) to further support novelty of the proposed method.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper presents a RL-based algorithm for solving the graph-based combinational optimization problem of Max-Cut. The key idea is to formulate the problem as an MDP, where the state is the embedings of all the vertices and the actions are the vertices to be flipped. The idea is implemented with a graph neural network to learn the embeddings and a recurrent encoding to encode the state representations. The network is trained with M-DQN. The proposed algorithm, named ECORD, is shown to be comparable to the previous state-of-the-art ECO-DQN and be significantly faster than ECO-DQN.
main_review: Postiive points:

+ Combinational problem is very general and could have many applications.
+ ECORD is shown to be able to generalize to larger graphs.
+ ECORD is shown to be more efficient than the previous methods
+ The neural architecture is well designed with both GNN to learn vertex embeddings and value network with GRU to learn state embedding.  
+ The paper is very well written.

Negative points:

- It is unclear to me how general the Max-Cut problem is. The Max-Cut is based on graph and only considers two labels. It is unclear whether ECORD can be applied to problems without graph structure or with more than two labels. In particular, when there are more than two labels, the actions space can be ill-defined since flipping will not make sense with more than two labels.
- It is unclear whether Max-Cut is hard enough to use RL. In table 1, even greedy heuristics can have very strong performance. In terms of efficiency, the greedy heuristics should be even more efficient than ECORD.
- It is unclear how ECORD improves the efficiency of ECO-DQN. The methodology section only introduces how ECORD is trained but never compares it with ECO-DQN.
summary_of_the_review: Overall, it remains unclear what combinational problems ECORD can address. The improvement over ECO-DQN or heuristics is not significant. It is unclear how ECORD improves ECO-DQN in terms of efficiency, which is the major contribution of this work.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper describes an RL based method for learning to solve the weighted maximum cut problem. Specifically, it proposes to process an input (fully connected?) graph using a gated graph recurrent network, and use the resulting embeddings as input for a computationally cheap RNN based policy that starts from a random cut (partition of nodes into two subsets) and subsequently 'flips' one of the nodes to move it to the other subset/other side of the cut. This policy ('encoder' + RNN) is trained using a variant of DQN to maximize the result obtained after 2*|V| flips, where V is the number of nodes in the graph. The policy makes use of a so called 'peek', a one-step lookahead of the result of each flip action on the current objective. At test time, the policy constructs multiple (deterministic) trajectories in parallel starting from different (random) initial solutions, where (I assume) the best overall result is returned. In experiments, the resulting algorithm, which is called ECORD, is shown to perform favorably when compared against ECO-DQN (Barrett et al. 2020), which, from skimming the paper, is very similar in strategy but uses a less efficient architecture and a different variant of DQN.
main_review: **Strengths**
- Well written paper, it was nice and easy to read
- The paper presents a sensible approach and good motivation, where it specifically designs an architecture to minimize the computational burden of the algorithm
- The paper addresses scaling, which is an important challenge in neural combinatorial optimization
- The paper applies reasonable baselines such as the heuristic strategy (MCA/MCA-soft)
- The paper takes care to conduct fair comparison (e.g. own implementation with optimizations also for ECO-DQN baseline)

**Weakness**
- The paper only considers maximum cut, while title suggests general combinatorial optimization. As multiple aspects (flipping, peek feature) are specific to max-cut it is unclear how the proposed method can generalize to other problems. I think 'Learning to Solve Maximum-Cut' would be a more suitable title for this work.
- The approach, presented as novel RL algorithm, is very similar to ECO-DQN, but the differences are not explained, so it is unclear what are contributions and what is 'reused' from ECO-DQN. From skimming the ECO-DQN paper it seems the major differences are the architecture (GNN 'encoder' + cheap RNN policy rather than expensive GNN for every step) and algorithm (different DQN variant).
- The term SOTA is confusing, maybe even misleading. I don't think RL/GNN is clearly SOTA for maximum cut in general (see e.g. the Leleu et al. baseline in the ECO-DQN paper), which is suggested in the abstract and title of section 4.1. To avoid confusion, I think the authors should use 'best RL-based method' and keep the term SOTA for the best exact/heuristic/RL solver in general. When claiming SOTA, I think the paper should also refer to relevant max-cut literature.
- The experiments do not support the strong claims: generalization is only compared against ECO-DQN and not against heuristic baselines. Also, some general baselines are missing, especially LeLeu et al. from the ECO-DQN paper.
- The theoretical novelty is limited as the 'learning to explore' idea and max-cut setup is from ECO-DQN (Barrett et al.). The idea of encoder + (rapid) decoder architecture for combinatorial problems is similar to Drori et al. (and some earlier works on neural combinatorial optimization).

Overall, I like the paper but I think it is too incremental and too narrowly focused on max-cut to be published at ICLR.

**Detailed comments/questions/suggestions:**
- 'to equal or surpasses' -> 'to equal or surpass'
- Do MCA-soft and MCA also use 50 trajectories? (I assume so but it is not mentioned)
- Fig 2b displays linear step time, but you also run 2|V| steps so more steps for larger graphs so overall time is quadratic? Also, does blue correspond to ECORD? (labels in Fig 2a?)
- If you did a reproduction of ECO-DQN (which is a great thing!) I think it would be helpful to list both original and reproduced results for clarity in Table 1 (unless they are very similar)
- 'Heurisitcs' typo Table 1
- It may be good to mention other solution strategies are possible as well, e.g. rounding a relaxed solution (https://www.cl.cam.ac.uk/teaching/1617/AdvAlgo/maxcut.pdf)
- How does MCA and MCA-soft perform in Table 2?
- What defines exactly ECORD when claiming/suggesting that 'in principle it could be applied to any CO problem defined on a graph' (in discussion)?
- For the GNN 'encoder', is the input graph fully connected? If so, how does the 'encoder' scale?
- Given the focus on max-cut only, I think some more related work on max-cut (non-RL) could be included.
summary_of_the_review: Overall, I like the paper, which is quite nice to read and presents a sensible and effective approach for solving the maximum cut problem using RL. Especially, the authors specifically addressed scaling to larger instances by making the architecture more efficient, which is an important and challenging topic.

Unfortunately, I still think the paper should be rejected given that
1) it is too much focused on max-cut and unclear how this framework can solve general combinatorial problems, as the title suggests
2) it is quite incremental to Barrett et al. (2020) AND not clear about the differences and
3) some important baselines are missing.
review_title: null

Meta-review: The paper proposes an efficient RL-based approach for solving the weighted maximum cut problem. The proposed approach shares high-level insights with prior work such as ECO-DQN (Barrett et al.) and S2V-DQN; the key contribution is to demonstrate that the proposed cheap action decoding and stochastic policy strategy can improve the scalability without sacrificing much of the quality of the solution on the tasks considered in this paper.

The reviewers in general find the paper well presented, and especially note that the clear motivation for improving the efficiency of current GNN-based RL baselines, particularly represented by ECO-DQN. 

A common concern among the reviewers is that the original title is misleading; the authors acknowledge that they should properly position the paper to avoid confusion that they were to address general combinatorial optimization problems (as the current title suggests). Notably, many combinational optimization problems can be reduced to max-cut as suggested in the authors’ responses; demonstrating the performance in (some of) these problems via a max-cut reduction would be helpful to support the significance of this work.

Beyond the title and positioning of this work, there were also initial confusions among the committee in terms of the choice of both (RL or supervised) learning-based and heuristic-based baselines. The authors did an excellent job in clarifying many of the questions in terms of related work and baselines (the clarity of the work has improved over the rebuttal phase). However, despite the additional ablation study and newly added baselines, there remain concerns/questions in the choice of task domains (lack of hard problem instances where existing solvers, learning- or heuristics -based may fail due to (possibly higher) computational complexity). Given the empirical focus of the paper, this appears to be an important concern, and not all reviewers are convinced the current empirical results are significant to warrant acceptance of this work.
Decision: Reject