Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: I will give the authors credit for introducing a novel problem to study, but they do not do a sufficient job motivating why the problem is an interesting or important one. At a high level I can buy the story they are trying to tell, but this really needs to be tied closely with a compelling (and, ideally, well studied) application  area. Without this, the claim in the introduction that "it is imperative to develop defense mechanisms" are unjustified. It is not clear to me that scheduling or TSP are problems where you would typically encounter adversarial inputs, and if the authors have concrete cases to illustrate this, please highlight them. If Fraud Coverage is a well-studied or established problem, provide citations to this effect.

Beyond the motivation of the problem itself, it is also not clear to me why the attack model studied in the paper is the "right" one. The authors should spend more time making a convincing case why their model is a plausible one. Again, this justification will need to be tied with a (compelling) application.

Other comments:
* p2: "Combnaotorial"
* The formalism for combinatorial optimization presented on page 3 is unlike any I have seen before. How should we understand what the x variables correspond to: binary indicators on e.g. edges? If so, where are the explicit binary constraints? It is also not clear to me what it means for the constraints to be "usually encoded in graphs".
* What does it mean to "loosen part of the constraint h_i"? Please introduce more formality about what h_i are, what loosen means, etc. 
* I find it interesting that the FC attack against Gurobi essentially seems to find ways to make the problems extremely difficult to solve, as opposed to degrading the solution quality (though that may also occur). I wonder if the authors can gain any insight into what the attack is doing here.
main_review: This paper studies adversarial attacks and defenses against algorithms for combinatorial optimization problems. The authors frame the problem, introduce RL-based algorithms for attack and defense, and present computational experiments.

summary_of_the_review: The authors did not do a sufficient job motivating why the problem or model were interesting or important.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: The authors aim to study the robustness of combinatorial optimization solvers (in particular ones that are based on learning). They treat the task as a graph problem and perform attacks on the underlying graph structure. Additionally, they aim to propose a defense mechanism. Finally, experiments on three different tasks are performed.
main_review: Overall, I like the challenge that authors aim to tackle a lot. The problem is highly important and studying robustness of comb. opt. solvers is highly important. Moreover, the paper is easy follow (even though, the notation is rather confusing; see below).

However, there are some major problems with the paper:

1: The main problem is indeed the actual problem formulation of Eq. (2). This equation is not helpful in studying the robustness of the solvers. Note that the underlying graph G' (resp. Q') is different -- thus, also the objective function of the optimization problem when feeding in this new input *should likely change*. Put differently: Eq. (2) is merely identifying two problem instances G and G' which lead to different objective function values. It does not tell anything about the robustness of the solvers. 
 
[Side note: One might argue that the authors aim for small modifications to G and, thus, the objective function value should also change only slightly. However, in particular for NP-hard comb. opt. problems such assumption is not correct. Indeed, small changes in the input can lead to larger changes in the output. In this case, this is not an issue of the non-robustness of the solver but inherent to the problem setting.]

Given this, all follow up experiments and insights are, unfortunately, not helpful.

If we want to study robustness of the solvers, it would be more appropriate to analyze whether the prediction of the solver is correct when feeding in G -- but incorrect when feeding in G' (in whatever sense correctness is measured). In the current formulation, though, this is not captured at all.

2: The definitions/notations are rather confusing: Q is used as a problem defined on a graph G. What exactly is Q? It seems to be fully determined by G (see Eq. 2). But why is the solver then operating on Q and not G? And what exactly does then the conditioning on G mean?

Moreover, if Q is fully determined via G (resp Q' via G'), how does Eq. 4 make sense? Here the solver is applied on Q' but conditioned on G. How is this possible?

Finally, in some cases f is operating on S(Q) -- at other places f is directly operating on Q, i.e. f(Q). I would appreciate to fix these notations.

3: Experiments: As mentioned above, I am convinced that the current experiments are not helpful in investigating the robustness of solvers as claimed by the authors. 

Besides that, I found the attack to the TSP unclear. The authors state that they "choose an edge and half its value". However, in the model definition they only define edge addition and deletion. Either the authors should update their model description or perform a different kind of experiment.

4: The paper strongly relates their motivation, model, and experiments to graph attacks/defenses. However, the related work on this is very weak. There is a huge literature on these topics which should be discussed more carefully. In particular, I was wondering, why a simple gradient -based attack (relaxing the discrete nature of the data) was not used as comparison.

5: Regarding technical novelty: The authors are highly inspired by other graph based (RL) attacks. Thus, the novelty in this regard is limited as well.

summary_of_the_review: The paper aims to tackle an important problem. However, the introduced model definition (Eq. 2) is incorrect / not helpful in this regard. Thus, unfortunately, the conclusions drawn are very questionable. Moreover, notations, related work, and experiments needs improvements.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the adversarial attacks and defenses problem of combinatorial optimization problems. The paper presents ROCO framework, to conduct attack and defense by maximizing/minimizing the difference between the calculated optimum values between the perturbed graph and the original graph. Both RL-based and heuristics-based solutions are proposed and implemented on three combinatorial optimization tasks.
main_review: Concerns:
- The defined *robustness*, *adversarial attack* and *defense* in this paper are not reasonable. The paper considers the differences between $f(S(Q^\prime)|G^\prime)$ and $f(S(Q)|G)$ as the robustness of a solver, which makes little sense. It is common that a small perturbation in the graph can make the optimal result of a CO problem change a lot, but this is an intrinsic property of CO problem, and is unrelated to the *robustness* of a solver. A reasonable definition of *robustness* can be $-(f(S(Q)|G)-f^*)$, where $f^*$ is the ground truth optimal value. Then the attack is to find some $G$ that makes some solvers find sub-optimal solutions that are far from the ground truth optimum.
- For the *defense*, 
    - What does "the defense RL agent can not only play a defensive role against the attacked problem instance, but can also help further improve the solution of normal instances" mean? I think modifying the graph itself to get better results is unacceptable for CO tasks. After modification, the problem becomes a different problem, and the solution to it means little to the original problem.
    - For Eq.4, how can the defender access the original graph $G$ to be part of its objective? If the original graph is accessible, then no other actions are meaningful as we should directly adopt the original graph.
- The scope of the claims in this paper are too broad and should be narrowed down to specific tasks and solvers that the proposed ROCO can work on. For a trivial example, the shortest path finding problem is a combinatorial optimization problem with deterministic, optimal and efficient solver. The Bellman Ford method or Dijkstra method for it are deterministically robust and should not be able to be attacked in any ways.
- The proposed solutions have limited novelty.

Minor:
- Should it be $f(S(Q^\prime)|G^\prime) -f(S(Q^\prime| G))$ in Eq.4?
summary_of_the_review: My main concern is about the problem setting. I think the definition of *robustness*, *adversarial attack* and *defense* about CO in this paper are unreasonable. By modifying the original graph in CO tasks, the problem becomes a different problem and the solution lose its meaning to the original problem.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper presents a framework of adversarial attack and defense for solvers to combinatorial optimization problems. In particular, the attacker can modify the problem instance by removing graph edges, while the defense side seeks to add edges to mitigate the attacking effect. The paper presents attack methods based on reinforcement learning and heuristic methods, and proposes a defense method based on reinforcement learning. Experimental studies are provided on three combinatorial problems.
main_review: $\textbf{Strengths}$
-	Enhancing the robustness of combinatorial optimization solver is an interesting and timely problem.
-	Under the proposed scheme, the presented attack and defense methods are reasonable. 

$\textbf{Weaknesses}$
-	The main weakness is that the considered attack-defense scheme seems to be problematic. From the very beginning, I am confused about the definition of an attack. In my opinion, an attack on the CO-solver should try to prevent the CO-solver from producing a high-quality solution to the *original input* (but not the perturbed input). But the proposed attack method aims to maximize $f(S(Q^{‘}|G^{‘}))$ rather than $f(S(Q^{‘}|G))$. 
-	Similarly, the effect of the defense should be measured by the quality of the solution to the original input, which is however unknown to the defender because it has been perturbed by the attacker. In such a sense, if the defender knows the attacker’s strategy, they can mitigate the attack by identifying the removed edge; otherwise, unless an input distribution is known, there seems no meaningful defense method. 
-	Assuming the proposed attack-defense scheme is reasonable, the proposed reinforcement methods are reasonable but do not contribute new techniques.
-	In experiments, maybe I missed something, but I did not see the setting of the number (K) of edges that are allowed to be changed; to me, experimenting with different K is necessary. In addition, only three fixed graphs are considered for DAG scheduling, and for demonstrating its statistical significance, it is better to experiment with a collection of random instances and examine the average performance. 

It would be better if the paper could elaborate on the following questions:
- Why strong nonlinearity and NP-hardness can cause the vulnerability defined in this paper?
- What does it mean by saying that the parameters are universal?
- From the attacker’s standpoint, what is the purpose of setting $f(Q^{‘})\geq f^*(Q)$? I do not see that such a setting can result in a better attack. 
- Relaxing the candidate space does not necessarily mean that the solver should perform better, because the performance is measured with respect to the optimal solution which can have a better objective value in the relaxed space. For example, if we relax the metric space to general space, some problems can exhibit stronger approximation hardness. 


summary_of_the_review: This paper considers an interesting problem, but the adopted settings need better justifications, and the proposed methods are unfortunately not novel.
review_title: null

Meta-review: The paper aims at developing mechanisms for adversarial attack and defense towards combinatorial optimization solvers, where the solver is treated as a black-box function and the original problem’s underlying graph structure is attacked under a given budget. While the reviewers found the problem novel and interesting, they are not convinced by the problem formulation and the proposed solutions, as well as the experimental setup. Some of the points that the reviewers brought up during the discussion include: (i) the attack to the TSP does not follow the main paper's attack principle of adding and deleting edges, (ii), in general, it has not been explained why all these modification are really "relaxations", (iii) the notations are very confusing, and (iv) while authors' response on loosening the constraints makes sense, but the experiments (i.e., the TSP problem setting) in this work are not consistent with such clarification. Addressing the above points will significantly improve the manuscript.
Decision: Reject