Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: summary: This paper presents an interesting idea to solve Combinatorial Optimization on Graphs by using Reinforcement Learning in order to modify the underlying graph in order to make it easier for a heuristic algorithm. The reward for the RL algorithm is simply the increase found by the heuristic algorithm between the original graph and the modified one. The authors test their algorithm on several real-world dataset related to DAG scheduling, graph edit distance and hamiltonian cycle problem.
main_review: I like the idea to mix RL with a heuristic algorithm but there are some points which need to be clarified:
1- in each case, a GCN is used in Algorithm 1 to predict P(a_1) and P(a_2|a_1) for adding/removing//modifying edge (a_1,a_2) but I do not understand how the weights of this GCN can be learned? The reward is not a differentiable function?
2- I do not understand how a ResNet block can be used on graphs? On page 5, the authors refer to [20] the Mask R-CNN paper. I do not see the connection, CNN are used on images not graphs?
3- I had a look at the TPC-H dataset but it is not clear at all from the website how this is related to the task. Since the authors are using datasets which are not standard in the ML community, they should explain them and give at least basics statistics.
4- on page 5, the authors say that they use GCN on the graph and on its complement. This is rather surprising as GCN are typically used on sparse graphs. Can they comment on this?
It would have been much better to provide the code associated with the experiments.
limitations_and_societal_impact: OK
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: While many approaches have been proposed for the combinatorial optimization on graphs, authors propose a bi-level framework that incorporates the conventional heuristic solvers into MDP setting. In particular, three kinds of combinatorial problems -- DAG scheduling, graph edit distance, and Hamiltonian cycle problem (HCP) -- are solved by the proposed framework. The main idea of the framework is to apply RL to modify a given (constraint) graph so that a heuristic algorithm over the modified graph can result in the (near-)optimal solution of the original problem. For the framework to work well, the modification of the graph should occur in the direction that 1) the feasible space needs to be reduced and 2) the updated objective function value should be minimized in the end. Experimental results show that the proposed method outperform baseline models on DAG scheduling and graph edit distance problem, while showing comparable performance with the best baseline model on HCP.

The main contributions of the paper is as follows. First, the idea of modifying original graph constraints to find better solutions by using heuristic algorithms is very unique and worth checking. Second, the combination of heuristic algorithms and RL is also a nice direction of solving the combinatorial problem. Finally, authors formulate the three kinds of typical combinatorial problems into the proposed framework and show experimental results on benchmark datasets.
main_review: Originality
Combinatorial optimization on graphs is very broad and authors focus on conventional problems -- DAG scheduling, graph edit distance, and HCP. And the proposed framework to combine MDP and heuristic algorithms is novel because of apply the RL to modify graphs in a certain direction. This direction is very different from a lot of work using RL that directly solves a given problem.

Quality
While the proposed idea is interesting, some technical aspects are unclear or unconvincing. Four main unclear points are following.

1) Proposition in Page 3 does not seem proven. There is no guarantee that x* is the only feasible solution of G* when it is solved by a given heuristic algorithm. Without the proof of that unique solution guarantee, x* is not necessarily a solution of the heuristic solution. While it is not a trivial proof, authors skip this part and conclude.

2) Intuitively, adding more constraints is likely to make the problem harder even for a given heuristic algorithm. Hence, we can imagine that the heuristic algorithm is likely to find a worse solution when more constraints are added. Given the counterintuitive situation (at least apparently), the explanation why the proposed framework will result in a better solution with a fair probability is missing. 

3) Experimental setting is not very convincing. Since heuristic algorithms result in local optimal solutions typically depending on initial settings, more trials with memorization of best results are likely to produce better performance. For a fair comparison, the proposed framework should be also compared with any heuristic MDP replacement such as identity (just more trials), random modifications (perturbations), and so on by equalizing the number of runs of heuristic algorithms.

4) In the Graph Edit Distance (GED) problem, MDP is designed to modify \mathcal{G}_{1} to be more aligned with \mathcal{G}_{2}. This direction seems different from the other cases where the constraints become worse. How the GED problem fulfills Eq.(2) is not straightforward because constraints in matching two graphs are different from running algorithms on one graph.


Clarity
The manuscript is clearly written and easy to follow.

Significance
If all the technical issues described above are resolved, the proposed approach is worth considering, because the proposed framework can envision the direction that RL can boost the performance of many heuristic or state-of-art algorithms by exploiting such algorithms.

Other weakness
When the three problems are implemented, authors use all different neural network structures. While it is non-trivial to design neural network structure for MDP on graphs, authors do not suggest any guidance or ablation study when using different kinds of network structure.
limitations_and_societal_impact: Authors provide enough limitations societal impact.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper proposes a hybrid bi-level method for combinational optimization problems on graphs, which combines traditional heuristics for combinational optimization and machine learning including reinforcement learning, graph neural networks, etc. 
main_review: Pro：
1. The problem is important and meaningful. 
2. This paper proposes a bi-level hybrid solver for graphs, which can be used for several tasks on graphs. 
3. The authors conducted experiments on several different datasets for various tasks, which demonstrates that the model is general and effective. 

Cons:
1. The codes are not submitted, which raises concerns about reproducing the results. 
2. This paper overclaims on this point: “we take an initiative for developing a general hybrid approach that integrates traditional heuristic solvers with machine learning algorithm”
3. It is not clear about the range of the problems that the framework is useful for. 

Details:

The idea of combining heuristics for combinational optimization and machine learning for solving combinational optimization problems on graphs is interesting. I agree that although deep learning is powerful, it is usually unfeasible to use deep learning to directly solve some hard combinational optimization problems on graphs. The experimental results show that this model has the advantages of two parts: automated editing the graph with reinforcement learning and efficiently solving the remaining problem by heuristics for combinational optimization. 

However, I am confused about the following issues, and I hope the authors can answer these questions in the rebuttal stage,
1. It would be better if the authors can provide several examples for the proposition (line 119) for understanding. What is the exact meaning of “If all constraints are encoded by the graph structure”? Can it be formally defined? What problems can be solved and what cannot? The related statements are vague. 

2. Furthermore, the proof states that given G and G’, we can find constraints that make x* is the output of a given heuristic algorithm. In my opinion, it’s different from given G and constraints, we can find G* that x* would be the solution (what the proposition proposes). 

3. It would be better if the authors can provide more details about the training process and plot the learning curves which can help us understand how the convergence process is. 

4. The authors should provide more examples in experiments as case studies.

5. The following is overclaimed, “we take an initiative for developing a general hybrid approach that integrates traditional heuristic solvers with machine learning algorithm”. Actually, there are existing works that combine these two things. For example, meta-learning for heuristic algorithm search can combine them. This area starts in 1970 and has many papers. For recent ones, please check Frank Hutters' papers which are published around 2010.

6. It seems RL is not the only method for searching for the graph, the authors should compare their RL-based method with evolutional search and stochastic search, etc., which can be used for the graph search/modification. 

7. The motivation of some designs is not clear, e.g., the design of the GCN module in Sec. 4.1.1 (maybe because of the page limit). Because the problem is defined based on graphs, how to use or design GCN would be key, but the description in this paper about GCN design is very short.

limitations_and_societal_impact: Please see "Cons" above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper is part of the newly emerging literature on solving combinatorial optimization problems using machine learning approaches (particularly reinforcement learning). It focuses on problems on graphs. It proposes a new hybrid approach which uses RL to modify the structure of the input graph into a surrogate graph, which is then given to an existing heuristic. The idea is that this simplifies the task for RL (since it only needs to modify the original graph instead of solving the problem) while allowing us to improve the performance of the heuristic. Experiments are given on three example tasks, showing that the proposed method improves over the heuristics on their own in terms of solution quality, and also outperforms an attempt to solve the entire task with RL. 

main_review: To my knowledge, the idea of using RL to modify the input graph is novel. It represents a nice way to combine data-driven and algorithmic means of solving optimization problems. The experimental results show an improvement over the individual heuristics used, indicating that learning to modify the structure of the graph can actually improve the performance of the heuristic. Accordingly, I think that the paper does make a valuable contribution. 

A few comments/questions:

First, test sets are often small (10-20 instances). Error bars should be reported to see if the improvements are significant (and/or more instances should be added to the test set). This is important to assess the validity of the results, aside from other comments about adding new content to the paper. 

Second, it would be preferable to show results on at least one domain for which an existing RL method can be applied exactly. Developing and tuning a RL solver for an optimization problem can require a lot of effort, so to provide the most informative comparison between the single and bi-level frameworks, it would be good to see an example where another set of authors has produced a strong baseline. 

Third, how does the inference time compare to the runtime of the heuristics? I.e., does RL add significantly to the runtime cost?

Fourth, is it possible to develop an understanding of how RL tends to modify the input graph? 

limitations_and_societal_impact: yes
review_title: null

Meta-review: This interesting paper explores a bilevel approach to solving combinatorial optimization
problems by using a learning algorithm to edit the graph until a 
(non-learning-based) heuristic can return the solution. 
The exposition should be improved, experiments should show ablation studies to understand 
the effect of network structure, and of course, it would be much better for code to be made available;
but the effort taken by the authors in the review period increases my confidence that 
the camera-ready version will address these issues.
Decision: Accept (Poster)