Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors propose to evaluate and improve the robustness and generalization of neural combinatorial solvers with adversarial examples, that is, perturbed inputs that fool the neural network to generate outputs with high loss. The authors claim that their proposal reconciles the tension between the hardness results from Yehuda et. al. (2020) and the overly-optimistic evaluation results from previous work. Furthermore, they instantiate their proposal with two classic combinatorial problems -- SAT and TSP, where adversarial examples are generated without the need to run potentially exponential-time solvers. They show that adversarial examples not only expose the fragility of common neural solvers, but can also help improve their generalization and robustness via adversarial training.
main_review: ### After Author Response
Since the authors' response and the revised submission have addressed my major concerns in:
1. how to position their work among previous works, and
2. the practical efficiency of the proposed method (in the combinatorial problem showcase)

I believe this paper is of good quality and would be happy to raise my rating from 5 to 6.

----------------------------------------------
### Strengths:
#### 1. The paper is dealing with an important and interesting problem.
#### 2. The authors illustrate their insights and method well with two combinatorial problems of significant theoretical and practical interests.
#### 3. For the SAT problem, they show adversarial training improves robustness (under the same attacks, so it is expected) and generalization (which is encouraging; though for a fair comparison, sample generation efficiency may also need to be considered, see Concern 3).
#### 4. The paper is well-written and easy to follow in general.

### Weaknesses / Concerns:
As this work seems to be a direct response to Yehuda et. al. (2020) (see e.g. Abstract and Introduction of this work), I believe it would be very helpful to compare and clarify the relation of their results.
#### 1. Data generation. Yehuda et. al. (2020) argues there is no efficient data generation procedure that is complete for these NP-hard problems. This work is no exception as otherwise it contradicts the NP-hardness assumption.
#### 2. Easier subproblem. The sound and efficient perturbation model has to be incomplete, i.e. it only covers a subset of problem instances no greater than Yehuda et. al. (2020) dictates. That said, it is possible (but not necessarily true) that with the adversarial perturbation procedure, the space covered in the training set is enlarged, and is closer to the size upper bound implied by Yehuda et. al. (2020).
#### 3. Spurious features. While adding adversarially perturbed data to the training set could potentially eliminate some spurious features, so could adding more random data, as long as random data sampling distribution covers the space of adversarial samples. Since adversarial samples require more computation to generate relative to random samples, from a practical perspective it would be helpful to compare the overall efficiency of the two training paradigms, including sample efficiency and the time required to obtain a single sample.
#### 4. Novelty. While there seems to be no previous work on adversarial training of neural combinatorial solvers, this idea falls into the "Data Augmentation" category for data generation in Yehuda et. al. (2020), with some loosely related previous work.

*Reference:*

*Gal Yehuda, Moshe Gabel, and Assaf Schuster. (2020) It’s Not What Machines Can Learn, It’s What We Cannot Teach.*

Finally -- this is not so important -- there are a few typos / word duplicates that could be spotted.
summary_of_the_review: ### After Author Response
1. The paper presents a novel idea -- using adversarially perturbed problem instances to evaluate the generalization performance of neural combinatorial solvers, and shows it exposes the weakness of some state-of-the-art models.
2. The paper shows that adversarial training with the adversarial data may be a useful practical method for improving neural solver's generalization performance.

-----------------------------------
### Initial Summary

While I believe the technical results presented in the paper are valid, I tend to disagree with the authors on the significance / potential limits of their approach, in particular on their response to the theoretical challenges raised by Yehuda et. al. (2020).
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper pinpoints the problems with neural combinatorial solvers and studies the notion of adversarial robustness for the scenario. Benefits are gained by introducing such a notion, which then allows the evaluations of neural SAT and TSP solvers.
main_review: At the start of the paper, the authors set out clearly the problem being addressed by the work and the motivation behind it. A nice summary of the contributions is also set out early on in the paper, though the work will be of most relevance for the specific topic of learning combinatorial solvers. In terms of presentation, the paper is self-contained with relevant background material provided, followed by concise technical work. The evaluation of the work is also sufficient. 

There are occasional loaded terminologies in the texts, which makes it a bit difficult to follow (for me). But that is probably unavoidable given the limited amount of space and this specific field of research.
summary_of_the_review: Overall, I feel this is a worthy piece of work that is relevant, presented clearly, and accompanied by a good evaluation.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Motivated by the emergence and fast development of the area of neural optimisation solvers having been proposed for a vast number of combinatorial problems, this paper is devoted to studying the adversarial robustness of such solvers. In particular, given the intractability of the target combinatorial problems, the paper proposes to evaluate neural solvers based on adversarial robustness. As an example, the authors aim at perturbing SAT and TSP problems and evaluating the robustness of the corresponding state-of-the-art neural solvers on the perturbed problem instances. The paper shows that the existing solvers are susceptible to adversarial attacks. Moreover, the paper claims that the issue may be alleviated if additional training of the solvers is performed on the perturbed instances.
main_review: First, I should say that although I am no expert in the area of adversarial robustness, I am used to working in combinatorial optimisation and automated reasoning (in particular, SAT solving). Hence, I view this paper from the perspective of a SAT and CP practitioner.

Language-wise the paper seems to be well written. The discussion flow is clear and easy to follow. The notation and the concepts studied are properly introduced. Some minor issues with the notation include the lack of relation of "y" and the corresponding CNF formulas as well as the inconsistency in the use of "y = 0" and "y = -1" for unsatisfiable formulas. Another minor issue is that the example solution Y ignores
variable v3. Regarding notation, I should also say that the paper implicitly assumes what "clean accuracy" and "perturbed accuracy" are - it would help to define them explicitly.

To the best of my knowledge, all the theoretical claims presented in the form of propositions are correct. Moreover, the experimental results convincingly show that the SOTA neural solvers suffer from the lack of adversarial robustness, which is crucial given the hardness of combinatorial problems and the vital need to solve them exactly. I do believe this is a nice result that shows clear limitations of the current generation of neural combinatorial solvers and, more importantly, a possible way towards resolving the problem (more on this in the next paragraph).

It is also interesting to see that additional (adversarial) training helps alleviate the problem to some extent, although I am convinced that the issue of adversarial robustness will inevitably appear in any neural solver (as it is intrinsic to ML in general). Therefore, neural solvers will never reach the point when they could be used to replace the current complete solutions. For those who disagree, the paper proposes a way to go.
summary_of_the_review: As a result, I believe the paper offers a solid contribution that should be interesting enough for the community working in the area of neural solvers for combinatorial problems. Furthermore, I believe the message conveyed by the paper on the lack of robustness in SOTA solvers must be heard as, otherwise, neural solvers will never be able to even catch up with exact and complete solutions for the studied problems and instead will continue to be perceived as no more than a nice exercise for ML practitioners.
review_title: null

Meta-review: The paper studies how neural combinatorial solvers can be susceptible to adversarial examples and what implications does this susceptibility have on the evaluation of neural solvers. Besides proposing some successful adversarial attacks, the authors provide a method for adversarial training and show its effectiveness on improving robustness and generalization. All the reviewers agreed that this paper provides a set of very interesting and novel results.
Decision: Accept (Poster)