Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness
Authors: Simon Geisler
Johanna Sommer
Jan Schuchardt
Aleksandar Bojchevski
Stephan Günnemann
Venue: ICLR 2022 Poster (2022)
Keywords: Generalization
Neural Combinatorial Optimization
Adversarial Robustness

Abstract: End-to-end (geometric) deep learning has seen first successes in approximating the solution of combinatorial optimization problems. However, generating data in the realm of NP-hard/-complete tasks brings practical and theoretical challenges, resulting in evaluation protocols that are too optimistic. Specifically, most datasets only capture a simpler subproblem and likely suffer from spurious features. We investigate these effects by studying adversarial robustness -a local generalization property- to reveal hard, model-specific instances and spurious features. For this purpose, we derive perturbation models for SAT and TSP. Unlike in other applications, where perturbation models are designed around subjective notions of imperceptibility, our perturbation models are efficient and sound, allowing us to determine the true label of perturbed samples without a solver. Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustness trade-off common in supervised learning. Although such robust solvers exist, we show empirically that the assessed neural solvers do not generalize well w.r.t. small perturbations of the problem instance.

Published as a conference paper at ICLR 2022
GENERALIZATION OF NEURAL COMBINATORIAL SOLVERS THROUGH THE LENS OF ADVERSARIAL ROBUSTNESS
Simon Geisler'; Johanna Sommer',, Jan Schuchardt', Aleksandar Bojchevski", Stephan Günnemann'
(geisler, Sormer, schuchaj, guennemann 8 iin. tum. de bojchevsk i spa s de DDpartmeen of Informatics & Munich Data Science Institute, Technical University of Munich
CCISPA Helmholtz Center for Information Security
ABSTRACT
End-to-end (geometric) deep learning has seen first successes in approximating the solution of combinatorial optimization problems. However, generating data the realm of up-hard//complett tasks brings practical and theoretical challenges, resulting in evaluation protocols that are too optimistic. Specifically, most datasets only capture a simpler subproblem and likely suffer from spurious features. We investigate these effects by studying adversarial robustness-a local generalization property- to reveal hard, model-specific instances and spurious features. For this purpose, we derive perturbation models for SAT and TSP. Unlike in other ap- plications, where perturbation models are designed around subjective notions of imperceptibilityy our perturbation models are efficient and sound, allowing us determine the true label of perturbed samples without a solver. Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustnet Although such robust solvers exist, show empirically that the assessed neural solvers do not generalize well w.r.t. small perturbations of the problem instance.
trade-off common in supervised learning.
INTRODUCTION
Combinatorial Optimization covers some of the most studied computational problems. Well- known examples are the NP-complete SATisfiability problem for boolean statements or the Trav- eling Salesperson Problem (TSP). These problems can be solved efficiently with approximate solvers that have been crafted over the previous decades (Festa 2014). As alternative to gineered, application-specife heuristics, learning seems to be good candidate (Bengio et al. 2021
and was studied as component in traditional solvers (e.g. Haim & Walsh (2009)). Despite deep learning for combinatorial optimization gaining attention recently, it is still an open question if and what extent deep learning can effectively approximate NP-hard problems.
Accessible
Sparse dataset
Perturlation space
3 High approsinatiin urror
Perturbation space high appr exiinatiii erter
Moreover, there is "Catch-22": even if neural networks could solve NP-hard problems, gen- erating the training data is either (a) incomplete but efficient (b) complete but inefficient (or approximate). An incomplete data generator (a) crafts the problem instances s.t. their labels are known and a complete data generator (b) ob- tains the labels via (approximately) solving the random instances. Additionally, a dense sample intractable even for moderate problem sizes due to the large problem space X.
Figure I: Adversarial examples can enhance the coverage of problem space X and find model- specific regions with difficult examples. Left, shows the asymptotic coverage of an efficient, incomplete data generator (Yehuda et al.) 2020). Right, shows the important case (X is large) of sparse sample of possibly complete generator.
"qual contribution

---

Published as a conference paper at ICLR 2022
For the special case of (a) exact polynomial-time data- -att-rennratoos, Yehuda al. (2020) detail two challenges as a result of the NP-hardness: (1) Easier subproblem: a dataset from an efficient data generator only captures strictly easier subproblem. (2) Spurious features: due to the lack of completeness, the resulting dataset can be trivially solvable due to superficial/spuriou features. These findings extrapolate
case (b) for sufficiently sparse sample (i.e. data could have been generated by an efficient data generator). Thus, it is concerning that often the same (potentially flawed) data generator is used for training and evaluation.
Adversarial robustness is challenging local generalization property that offers a way of fixing the too optimistic model performance estimates that are the result of evaluations on incomplete datasets. We illustrate this in Fig. I] for two relevant data generation schemes: (a) to the left we discuss an incomplete, efficient data generator and (b) to the right we discuss a sparse sample of a potentially complete data generator. With a suitable choice of perturbation model, we (a) possibly extend the reachable space by an efficient data generator or (b) cover the space around each instance in the sparse dataset. In other words, such adversarial attacks aim to find the intersection of the uncovered regions and hard, model-specific samples. Therefore, it is possible to detect the described defects. Adversarial robustness more realistically evaluates model's 's generalization ability instead of simply testing on the same data generation procedure or sparse external dataset.
Adversarial robustness is desirable property for neural combinatorial optimization, since, in trast to general learning tasks, in combinatorial optimization we do not have an accuracy robustness trade-off in the sense of (Suggala et al. (2019). This means, there exists model with high accuracy and high robustness. One key factor to avoid the accuracy robustness trade-off is choosing a pertur- bation model that guarantees the correct label of the perturbed sample (we call them sound). This is in stark contrast to other domains where one relies on imperceptible perturbations.
We instantiate our adversarial attack framework for the NP-complete SAT and TSP. Nevertheless, most of the principles can be transferred to other combinatorial optimization problems. Note that often such problems can be even reduced onto one another, as the case for e.g. SAT and the maximum independent set. Having said this, we select SAT because of its general applicability and the notoriously challenging TSP due to its practical importance (e.g. for supply chain optimization). We then use our attacks to show that the evaluated neural SAT and TSP solvers are highly non-robust.
Contributions. (1) We bring the study adversarial robustness to the field of neural combinatorial solvers to tackle fundamental problems in the evaluation of neural solvers. (2) We propose pertur- bation models for SAT and TSP s.t. we efficiently determine the updated solution. (3) We show that the models for SAT and TSP can be easily fooled with small perturbations of the problem instance and (4) that adversarial training can improve the robustness and generalization.
2 BACKGROUND ON NEURAL SOLVERS
Intuitively, combinatorial optimization is the task of finding optimal element from the finite set of possible solutions (e.g. the truth assignment for a boolean statement). We formalize this as Y arg eg(a) c(x, Y') where is problem instance, g(x) = Y the finite set of feasible solutions, and c(.) cost function. Typically, there is also an associated binary decision problem such as finding the optimal route vs. checking whether route of at most cost Co exists (see [S 4 and 5). Then, for example, a neural solver the decision problem. In this work, 0 are the parameters, x X is the problem instance, and ğ (or
fo (xx learns mapping fe X + {0, to approximate
Y) the prediction. In case of supervised learning, we then optimize the parameters w.r.t. a loss ((fo(()) (m)) y) over a finite set of labeled training instances (æ. y). However, obtain the exact labels y for given x is intractable for larger problem instances due to the exponential or worse runtime. Two ways to generate data pairs mentioned in the introduction and visualized in FFg. 1 (a) an efficient but incomplete data generator (b) using a solver to obtain the labels for random samples.
3 ADVERSARIAL ROBUSTNESS
Adversarial robustness refers to the robustness of machine learning model small perturbation of the input instance (Szegedy et al. 2014). We define an adversarial attack in [Eq. I where the parameters 0 are constant and G denotes the perturbation model that describes the possible perturbed
2

---

Published as a conference paper at ICLR 2022
instances ã around the clean sample (i.e. the perturbation space) given the original solution Y. Since Y * Y in the general case, we introduce Y h(æ, x, Y) to model how the solution changes.
ladv, (xx, Y) max C ((f(())))) s.t. E G(,, Y h(a,z,Y)
(1)
Sound and efficient perturbation model. Our framework for a neural combinatorial solver fo stands out from many other works on adversarial robustness since we choose the perturbation model G s.t. we provably know a solution Y h(2 x, Y) for all possible z. We call such a perturbation model sound. This stands in contrast to other domains, where we usually hope to preserve the label using the subjective concept of imperceptiheelmmoiccbbe perturbations (Szegedy et al.) 2014).
While we can naively obtain sound perturbation model for combinatorial optimization using a solver, this is intractable for realistic problem sizes. We therefore propose to use perturbation models that are efficient and sound. That is. we can determine the updated solution Y without applying solver on the perturbed instance T. For example, if we add a node to a TSP instance, the optimal route including the new node will change, but we can efficiently determine Y for the chosen G.
Important technical details arise due to (a) the potentially non-unique Y and (b) non-constant Y while perturbing the input. One way to handle both effects is through the choice of the loss f. (a) We can deal with the ambiguity in Y if the loss is equal for any two optimal solutionss/rrddittions. This can be achieved naturally by incorporating the cost c(Y) of the combinatorial optimization problem. (b) Since the solution Y can change throughout the optimization, it is important to choose loss that assesses the difference between prediction fø( and ground truth Y. For example, viable loss for TSP is the optimality gap (Yo Y) = (<)))<(())((())) that is normalized by c(Y).
Perturbation strength. With a sound perturbation model, all generated instances ø are valid prob- lem instances regardless of how much they differ from æ. Hence, in the context of combinatorial optimization, the perturbation strength/budget models the severity of potential distribution shift between training data and test data. This again highlights the differences other domains. For ex- ample in image classification with the common I." perturbation model ||æ x lp S r, the instance changes its true label or becomes meaningless (e.g. a gray image) for a large enough
Generalization. Specifically, adversarial robustness is one way to measure the generalization over perturbed instances & the proximity of æ. Adversarial robustness is important in the context of neural combinatorial solvers since training and validation/test distribution differ from the actual data distribution p(æz). First, the data distribution p(æ:) is typically unknown and highly application- specific. Second, due to thcoretical limitations of the data generation process the train and valida- tion/test distribution likely captures a simpler sub- uub-problem suffering from spurious features (Ychuda) et al. 2020). Third, we ultimately desire a general-purpos solver that performs well regardless of p(x) (in the limits of a polynomial approximation).
We stress that in the context of combinatorial optimization, adversarial examples neither anoma- lous nor statistical defects since all generated instances correspond to valid problem instances. In contrast to other domains, the set of valid problems is not just a low-dimensional manifold in high-dimensional space. Thus, the so-called manifold hypothesis (Stutz et al.) [2119] does not ap- ply for combinatorial optimization. In summary, critical for neural solvers to perform well on adversarial examples when striving for generalization.
Accuracy robustness trade-off. A trade-off between adversarial robustness and standard general- ization was reported for many learning tasks (Tsipras et al.) 2019). That is, with increasing robust- ness the accuracy on the test data decreases. Interestingly. with sound perturbation model and the purely deterministic labels in combinatorial optimization (the solution is either optimal or not), no such trade-off exists. Hence, the model was expressive enough and we had sufficient compute, there would exist a model with high accuracy and robustness (see S A for more details).
Ad veresaria training. In adversarial training, we leverage adversarially perturbed instances with the desire of training robust model with improved generalization. For this, adversarial attacks reveal the regions that are both difficult for the model and not covered by training samples (see Fig. 1.. powerful data augmentation using hard model-
Hence, adversarial training can be understood specific samples. Though is not the main focus of this work, in S 6 we show that adversarial training be used to improve the robustness and generalization of neural combinatorial solver.
3

---

Published as a conference paper at ICLR 2022
Remarks decision problems. For the binary decision problems, typically not required to know Y; it suffices to know y. Moreover, for such binary problems, we keep the solution constant y = 9, but there also exist practical perturbations that change the label of the decision problem. For example for SAT,
add set of clauses that are false in isolation which makes jj
Requirements for neural solvers. We study neural combinatorial solvers fo that are often a Graph Neural Network (GNN). We then solve Eq. I Juiing different variants of Projected Gradient Descent
(PGD) and therefore assume the model to be differentiable w.r.t. its inputs (see $ D For non-
differentiable models, can derivative-free optimization (Yang & Long 202
4 SAT
We first introduce the problem as well as notation and then propose the perturbation models $ 4.1 Last, discuss the attacks for a specific neural solver (S 4.2)
(U1 Ves), not y O. Here, we represent the boolean expressions in Conjunctive Normal Form (CNF) that is conjunction of multiple clauses k(u1..... Un) and each clause is disjunction of literals 4. Each literal is a potentially negated boolean variable 4 E {-u;, v;) and w.l.o.g. we assume that clause may not contain the same variable multiple times. In our standard notation, problem instance æ represents such boolean expression CNF. A solution Y .fi.....44 L |t {-u,, e.}} provides truth assignments for every variable. Hence, in the example above x = (v1 Vug A (v1 V va), = 1, and a possible solution is Y = {vi, U22 23). Note that multiple optimal Y exist but for our attacks it suffices to know one.
Problem statement. The goal is to determine if a boolean expression, e.g. (e) satisfiable y
4.1 SOUND PERTURBATION MODEL
We now introduce a sound and efficient perturbation model for SAT which we then use for an adversarial attack neural (decision) SAT solver. Recall that the perturbation model is sound since we provably obtain the correct label ÿ and it is efficient since we achieve this without using a solver. Instead of using a solver, leverage invariances of the SAT problem.
Proposition 1 Let x li (wz, vn) AA..... ........ (oi....., Un) be a boolean statement in Conjunctive Normal Form (CNF) with m clauses and variables. Then 2, a perturbed version of x. has the same label y = ÿ in the following cases:
SAT: x satisfiable = 1 with truth assignment Y. Then, we can arbitrarily remove or add literals in a to obtain æ; as long one literal in Y remains in each clause.
DEL: x unsatisfiable y = 0. Then, we can obtain & from x through arbitrary removals of literals, as long as literal per clause remains.
ADC: æ is unsatisfiable
0. Then, we can arbitrarily remove, add, or modify clauses in x to obtain ã, as long as there remains subset of clauses that is unsatisfiable in isolation.
4.2
NEURAL SAT SOLVER
Selsam et al. 2019) propose NeuroSAT, neural solver for saiisfiaility-problemss that uses message-passing architecture (Gilmer et al., 2017) on the graph representation of the boolean ex- pressions. The SAT problem is converted into bipartite graph consisting of clause nodes and literal nodes. For each variable there exist two literal nodes; one represents the variable and the other its negation. If a literal is contained in clause its node is connected to the respective clause node. Ne then recursively updates the node embeddings over the message-passe steps using this graph, and in the last step, the final vote {0, 1} is aggregated over the literal nodes.
Attacks. We then use these insights to craft perturbed problem instances क guided by the maximiza- tion of the loss Ladrez (see [Q.. 1p. Specifically, for SAT and DEL, two of admissible perturbations defined in Proposition I] we optimize over a subset of edges connecting the literal and clause nodes where we set the budget A relatively to the number of literals/edges in æ. For ADC additionally concatenate additional clauses and optimize over their edges obeying A but keep the remaining æ constant. If not reported separately, decide for either DEL and ADC randomly with equal odds.
4

---

Published as a conference paper at ICLR 2022
Lº-PG.. The addition and removal of limited number of literals is essentially perturbation with budget A over a set of discrete edges connecting literals and clauses. Similarly to the L attack Xu et al. 2019),
continuously relax the edges in {0, 1} to [0, 1] during optimization. We then determine the edge weights via projected gradient descent s.t. the weights are within [o, 1] and that obey the budget A. After the attack,
these weights to sample the discrete perturbations in {0, 13. In other words, the attack continuously/softly adds as well as removes literals from æ during the attack and afterward sample the discrete perturbations to obtain T. For additional details about the attacks, we refer to E
5 TSP
We first introduce the TSP including the necessary notation. Then, we propose a perturbation that adds new nodes s.t. we know the optimal route afterward (8 5.1p. In 5.2 we detail the attack for neural decision TSP solver and, S 5.3 we describe the attack for a model that predicts the optimal TSP route Y.
Problem statement. We are given a weighted graph G (V, that consist a finite set of nodes V as well edges M. 722 and weight w(e) for each possible edge V2, We the elements in V as indices or nodes interchangeably. The goal is then to find a permutation of the nodes s.t. the cost of traversing all nodes exactly is minimized (i.e. the Hamiltonian path of lowest cost):
arg min ((d' arg min
Σ ((d
o'E3
where $ is the set of all permutations and n | is the number of nodes. Although multiple a² might exist here it suffices to know one. An important special case is the "metric TSP", where the nodes represent coordinates in a space that obeys the triangle inequality (e.g. euclidean distance). For notational ease, we interchangeably use as permutation the equivalent list of nodes. Moreover, we say a contains edge (I, E [M] if and are consecutive or the first and last element. In standard notation question if there exist c(a") S Co of at most co cost.
G, Y a², and the respective decision problem solves the
5.1 SOUND PERTURBATION MODEL
Adversarially perturbing the TSP such that know the resulting solution seems more challenging than SAT. However, assuming we would know the optimal route a* for graph = G. then under certain conditions we can add new nodes s.t. we are guaranteed know the perturbed optimal route ã² Note that this does not imply that we are able to solve the TSP in sub-exponential time in the worst case. We solely derive an efficient special case through leveraging the properties of the TSP.
Let a² be the optimal route over the nodes V in G, let Z & V be an additional node, and P,Q are any two neighhouring nodes on a* Then, the new optimal route o* (including Z) is obtained from o² through inserting Z between P and Q if (A, E V2 ((P,Q)) with A B s.f. wiA Z) +
Proposition 2
wi B, Z) w| A, B) (P, Z) w(Q (PP,Q)
Corollary We can add multiple nodes G and obtain the optimal route 5" as long as the condi- tion of Proposition 2 (including the other previously added nodes) is fulfilled.
Corollary For the metric TSP, is sufficient if the condition of Proposition 2 holds for (A, B) E 42 \ (A(P, }}} } U HI) with A + B where H. denotes the pairs nodes both the Convex Hull HI E CH(V)² that are not a line segment of the Convex Hull.
5.2 NEURAL DECISION TSP SOLVER
Prates al. 2019) propose GNN (called DTSP) to solve the decision variant of the TSP for an input pair æ = (G, co) with graph G and a cost cp. DTSP predicts whether there exists a Hamiltonian cycle in G of cost eo less (y 1 if the cycle exists).
Based on our perturbation model, we inject adversarial nodes. For the metric TSP, we determine their coordinates by maximizing the binary cross-entropy-a continuous optimization problem. This
5

---

Published as a conference paper at ICLR 2022
easy generalize to the non-metric TSP (omitting Corollary 2). if e.g. the triangle equality does not hold or there no "simple" cost function concerning the node's 's coordinates/attriutes Then, the optimization is performed over the edge weights, but depending on what the weights represent we might need to enforce further requirements.
Unfortunately, the constraint in Proposition 2] is non-convex and it is also not clear how find relaxation that is still sufficiently tight and can be solved in closed form. For this reason, when the constraint for node is violated, we use vanilla gradient descent with the constraint objective: w(P, 2) + (Q, 2) wPP, Q) - [minA, w(A, 2) + w(B, 2) w(A, B)]- This penalizes if a constraint is violated. We stop as soon as the node fulfills the requirement/constrain again and limit the maximum number of iterations to three. Since some ad adversarial nodes might still violate the constraint after this projection, we only include valid nodes each evaluation of the neural solver. Moreover, for optimizing over multiple adversarial nodes jointly and in a vectorized implementation, we assign them an order and also consider previous nodes while evaluating the constraint. Ordering the nodes allows us parallelize the constraint evaluation for multiple nodes, despite the sequential nature, since we can ignore the subsequent nodes.
5.3 NEURAL TSP SOLVER
Joshi al. (2019) propose a Graph Convolutional Network (ConvTSP) to predict which edges of the euclidean TSP graph are present in the optimal route. The probability map over the edges is then decoded into a permutation over the nodes via a greedy search or beam search. We use the same attack as for the TSP decision problem (see 5.2) with the exception of having different objective with changing label Y Although the optimality gap E(Y, Y) and common in the TSP literature (Kool et al., 2019), it proved to be tough to backpropagate through the decoding of the final solution from the soft prediction. Hence, for ConvTSP we maximize the cross-entropy over the edges. Hence, we perturb the input s.t. the predicted route is maximally different from the optimal solution y and then report the optimality gap.
)-(()/((()) is natural choice
EMPIRICAL RESULTS
In this section, we show that the assessed SAT and TSP neural solvers are not robust w.r.t. small perturbations of the input using the sound perturbation models introduced in $ 4 and 5 We first discuss SAT in in 6. and then TSP in 6.2 We use the published hyperparameters by the respective works for training the models. We run the experiments for at least five randomly selected seeds. We compare the accuracy on the clean and perturbed problem instances (i.e. clean vs. adversarial accuracy). Since no directly applicable prior work exists, we compare the random baseline that randomly selects the perturbation s.t. the budget is exhausted. Moreover, we use Adam (Kingma & Ba 2015) and early stopping for our attacks. For further details we refer to S E and S F as well as the code nttpp:: wwww. dam.1 in. um. de wwwbustneeeee cow.bussteess-cobiaattte comb mitttiiiitto
solvers.
1.0
1.0
0.6
Accuracy
0.6
0.9
Accuracy
0.8
0.4
0.4
0.8
0.6
Rand
0.2
Rand
0.4
Adv
0.7
Adv
Clean
SÂT
Clean
ADC
DEL
Clean
SAT
Clean
ADC
DEL
(a) SAT 10-40
(b) SAT 50-100
Figure 2: Efficacy of adversarial attacks as introduced in $ and assessment of (un)robustness of the Ne model on the 10-40 dataset. Recall that SAT IS the attack on the satisfiable problem instances and ADC well as DEL are the attacks on unsatisfiable problem instances.

---

Published as a conference paper at ICLR 2022
6.1 SAT
Setup. Following Selsam et al. (019), we train NeuroSAT for 60 epochs using the official parameters and data generation. The random data generator for the training/validation data greedily adds clauses until the problem becomes unsatisfiable which is determined by an exact SAT solver [[gnatiev et al. 2018 Sörensson & Een 2005). We are then left with an unsatisfiable problem instance and a satisfiable problem instance if we omit the last clause (i.e. the dataset is balanced). For each instance pair, the number of variables is sampled uniformly within a specified NeuroSAT range and then the number of literals in each clause is drawn from a geometric distribution. We name the dataset accordingly to the range of numbers of variables. For example, the training set 10-40 consists of problem instances with 10 40 variables. For our attacks, we use the budgets of ADEL 5% as well as ASAT = 5% relatively to the number of literals in x and for ADC we add an additional 25% of clauses and enforce the average number of literals within the new clauses.
Acouracy
0.75
0.50
0.25
Attack Steps
Figure 3: SAT Attack on
Attack efficacy and model (un)robustness. From the results of our adversarial attacks presented in Fig. 2 apparent that the studied model NeuroSAT is not robust w.r.t. small perturbation of the input. Additionally, Fig. 3 shows that for the SAT attack, one gradient update step already suffices decrease the accuracy to 26% (see also | I). All this shows the efficacy of our attacks and perturbation model, it also highlights that the standard accuracy gives a too optimistic impression of the model's 's performance. We hypothesize that the model likely suffers from challenges (1) easier subproblem and/or (2) spurious features, while it is also possible that the fragility is due to lack of expressiveness.
0.75
Accuracy
0.50
Adv Rand
0.25
0.10 Ratio of pert, literals A
0.01
0.05
Figure 4:
Rob. on satisfiable problems (SAT) over budgets A.
Difficulty imbalance. is much harder for the model to spot satisfiable instances than unsatisfiable ones. This is apparent from the clean accuracy and even more obvious from the ad-
Probability SAT
Clean
Pert.
0.5
versarial accuracy. Even with moderate budgets, we are able to lower the adversarial accuracy to values below 20% for satis-
fiable instances while for unsatisfiable instances we barely get
10
20
Message passing steps
below 50% even on the larger problem instances 50-100. An intuitive explanation is given by the fact that is impossible to find solution for unsatisfiable instance (and it is cheap to verify a candidate solution). Similarly, [Selsam et al. (2019) hypothesize that NeuroSAT only changes its prediction if it finds solution. Thus, it is even more remarkable how we are still able to fool the neural solver in 30% of the cases (DEL attack).
Figure 5: NeuroSAT's prediction
over the message passing steps.
Qualitative insights. We show in Fig. how NeuroSAT's decision evolves over the message- passing steps for satisfiable instances. NeuroSAT comes to its conclusion typically after 15 message- passing steps for the clean samples. For the perturbed samples, NeuroSAT almost never comes to the right conclusion. For the instances where NeuroSAT predicts the right label. it has hard time doing so since converges slower. For a specific adversarial example see
Attack budget. We study the influence of the budget A and, hence, the similarity of vs. ã. in Fig. 4 It suffices to perturb 0.2% of the lit- erals for the recall to drop below 50% using our SAT perturbation model. This stands in stark con- trast to the random attack, where the accuracy for the satisfiable instances is almost constant over the plotted range budgets.
Table 1: Accuracy comparison of regular train- ing with a 10% larger training set and adversar- ial finetuning of 10 extra epochs (17%).
Data
Regular
Extra data
Adv. train
Train
89.0 +: 0.06
89.1 + 0.05
88.8
0.06
10-10 10-40
Test
89.1 + 0.10
89.1 + 0.07
89.6 2: 0.06
Random
86.4 + 0.09
86,3 0.11
87.3 0.07
Attack
50.0 1.16
49.6 1.52
54.0 0.48
Test
81.1 + 0.64
81.2 + 0.89
82.7
0.50
Hard model-specific samples. The surprisingly weak performance (Fig. 2 and 4 of the random baselines shows how much more effective our at-
Random
78.6 0.80
79.0 1.02
80.8 0.46
Attack
3.15
37.9 2.62
44.4 L.19
3-10
92.3 0.57
92.7 + 0.30
93,0
0.33
100-300
64.4
6 1.63
67.0
: 0.74
tacks are and justifies their minimally larger cost (see / Hp. In G. show the difficulty is indeed
SATLIB
66.1 3.07
4.71
63.7 1.88
UNI3SAT
86.0 0.75
85.1 +: 0,80
86,9 0.39
7

---

Published as a conference paper at ICLR 2022
model-specific. Assuming that hard model-specific instances are the instances that are important to improve the model's 's performance, we can lower the amount of labeled data (potentially expen- sive). Of course, cannot do anything about the cocomleetss of the problem, but adversarial robustness opens the possibility to use the expensively generated examples as effectively as possible.
Adversarial training for SAT. We conjecture that if the models expressive enough, would now be able to leverage the adversarial examples for an improved training procedure. Therefore, similar Jeddi et al. (2020), we perform an adversarial fine-tuning. That is, train the models for another 10 epochs including perturbed problem instances. We use the same setup as for the attacks presented above but we observed that too severe perturbations harm NeuroSAT's performance (e.g. a budget of 5% suffices to push the accuracy below 20% for the satisfiable instances). We therefore lower the budget of the satisfiable instances 1% and perturb 5% of the training instances. For fair comparison, we also compare to model that was trained on 10% larger training set. To compare the solvers' capability to generalize for the different training strategies, we choose datasets of differ- ent problem sizes and also include the external benchmark datasets SATLIB and UNI3SAT (Hoos & Stützle 2000). We consistently outperform the regularly trained models in terms of robustness as well as generalization (with the exceptions SATLIB). We report the results in Table
6.2 TSP
Setup. In our setup we follow Prates et al. (2019) and generate the training data by uniformly sampling n (20,0400 40) nodes/coordinates from the 2D unit square. This is converted into fully connected graph where the edge weights represent the L L2~distances between two nodes. near- optimal solution Y for training and attacks is obtained with the Concorde solver (Applegate al., 2006). For the decision-variant of the TSP, we produce two samples from every graph: a graph with y = and cost-query of=1 = c(a²) (1+ d) and a second graph with 0 and cost-query d), where d = 2% (Prates et al. 2019), For predicting the TSP solution use ConvTSP (Joshi et al. 2019) but keep the setup identical to decision equivalent. We attack these models via adding five adversarial nodes and adjust 6 as well as Y accordingly.
y=0 = c(c=")
Decision TSP Solver. If a route of target cost exists, our attack successfully fools the neural solver most of the cases. This low adversarial accuracy highlights again that the clean accuracy is far too optimistic and that the model likely suffers from challenges (1) easier subproblem and/or (2) spurious features. In 7 we see that the changes are indeed rather small and that the perturbations lead to practical problem instances. For further examples see K
Concarde
* Pert. False
Part. True
Label: Route Exists
Label: No Route Exists
0.9
0.8
Accuracy
0.8
0.6
Clean
Rand
0.7
Adv
Figure DecisionTSP for problems with n (20, 40) nodes and five adversarial nodes.
Figure 7: Examples of the optimal route Y and perturbed routes for TSP.
Difficulty imbalance. For the TSP, we also observe an imbalance in performance between both classes. This is naturally explained with look the non-decision TSP version where solver constructs a potential route Y. Since e(Y) 2 <(Y) such network comes with the optimal precision of 1 by design.
Attacking TSP Solver. For CSnVTSP five new adversarial nodes suffice to exceed an optimality gap of 2%. Note that naive baselines such the "farthest insertion" achieve an optimality gap of 2.3% on the clean dataset (Kool et al. 2019). Moreover, for the class "route exists" we can compare the performance the decision TSP. Even though the model performs better than DTSP, attacks degrade the performance relatively by 10%. In Fig. 9 we can also view the predicted routes and observe that the prediction differ severely between the clean and perturbed problem instance.
8

---

Published as a conference paper at ICLR 2022
Conconte
Route Prediction
Route Exists
0.04
Optimality Gap
0.90
0.03
Accuracy
0.85
0.02
0.80
0.75
0.01
Figure 8: CSnyTSP for problems with v 20 nodes and five adversarial nodes. We plot the opti- mality gap (left) and the decision TSP performance (right).
Exemplary problem instances where the attack successfully changed the op- timal route for ConvTSP that show drastic changes of the prediction.
Figure 9:
7 RELATED WORK
Combinatorial Optimization. Further important works about neural SAT solvers are (Amizadeh jet al.
2019 Yolcu & Póczos 2019 Kurin et 2019 Cameron al., 2020 and for neural TSP
solvers (Khalil et al. 201 |017 Deudon et al. 2018 Bresson & Laurent 2021] Wang et al. 2021 Bello
cct al.
2016
Kool et al. 2019). We refer to the recent surveys surveys (Bengio et al. 2021 Cappart
al.
2021
Vesselinova et al. 2020) for a detailed overview and discussion.
There are only very few works on generalization of neural combinatorial solvers. One exception are FFanççis al. (2019) and Joshi et al. (2021). They empirically assess the im- pact of different model and training pipeline design choices on the generalization (for TSP) while discuss the generation of hard model-specific instances. A work by [Selsam & Bjørner (2019) studies generalization for their NeuroSAT model (Selsam et al. 2019) and proposes data augmen- tation technique relying on traditional solvers. Moreover, they study hybrid model consisting of a simplified Ae and a traditional solver. In summary, previous works about generalization of neural combinatorial solvers analyze specific tasks while we propose a general framework for combinatorial optimization and study TSP and SAT to show its importance.
Generalization.
Adversarial Robustness. Adversarial robustness has been studied in various domains including computer vision (Szegedy et al. 2014) and graphs (Zügner et al., 2018 Dai et al.) 2018). refer to Günnemann (2021) for a broad overview of adversarial robustness of GNNs. Specifically, for TSP we optimize the continuous input coordinates (or edge weights) but use our own approach due to the non-convex constraints. For attacking the SAT model we need to perturb the discrete graph structure and rely on L by Xu et al. 2019) proposed in the context of GNNs.
Hard sample mining. Deriving adversarial examples might appear similar to hard sample min- ing (Sung) 1995). However, hard sample mining aims in spotting hard problem instances in the train data unlike we who also perturb the problem instances (of the training data or any other dataset). Moreover, if we combine augmentations with hard sample mining, only create randomly per- turbed instances and their generation is not guided by the model. The surprisingly weak random baseline in experiments gives impression about how effective such approach might be.
DISCUSSION
We bring the study of adversarial robustness to the field of neural combinatorial optimization. In contrast to general learning tasks, we show that there exists a model with both high accuracy and robustness. A key finding of work is that the assessed neural combinatorial solvers are all sen- sitive w.r.t. small perturbations of the input. For example, we can fool NeuroSAT (Selsam et al.) 2019) for the overwhelming majority of instances from the training data distribution with moderate perturbations (5% of literals). We show that adversarial training can be used to improve robust- ness. However, strong perturbations can still fool the model, indicating lack of expressiveness. In summary, contemporary supervised neural solvers seem to be very fragile, and adversarial ro- bustness is an insightful research direction to reveal as well as address neural solver deficiencies for combinatorial optimization.

---

Published as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
We provide the source code and configuration for the key experiments including instructions on how to generate data and train the models. All proofs are stated in the appendix with explanations and underlying assumptions. We thoroughly checked the implementation and also verified empirically that the proposed sound perturbation models hold.
ETHICS STATEMENT
Solving combinatorial optimization problems effectively and efficiently would benefit wide range of applications. For example, it could further improve supply chain optimization or auto-routing electric circuits. Since combinatorial optimization is such a fundamental building block it is needless to detail how big of an impact this line of research could have. Unfortunately, this also includes applications with negative implications. Specifically, the examples about supply chain optimization and electric circuits also apply to military applications. Nevertheless, we believe that the positive impact can be much greater than the negative counterpart.
Unarguably, studying adversarial robustness in the context of combinatorial optimization comes with the possibility of misuse. However, not studying this topic and, therefore, being unaware of the model's robustness imposes an even greater risk. Moreover, since we study white-box attacks we leave the practitioner with huge advantage over possible real-world adversary that e-g. does know the weights of the model. Aside from robustness, we did not conduct dedicated experiments on the consequences on e.g. fairness for our methods or the resulting models.
REFERENCES
Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. Learning to solve circuit-sat: An unsu- pervised differentiable approach. In 7th International Conference on Learning Representations, ICLR, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. Concorde tsp solver, 2006.
Gilles Audemard and Laurent Simon. Predicting learnt clauses quality in modern sat solvers. In Proceedings of the 21st International Jont Conference on Artifical Intelligence, IJCAI'09, San Francisco, CA, USA, 2009. Morgan Kaufmann Publishers Inc.
Irwan Bello, Hieu Pham, Quoc Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint 1eXiv:1611.0900 2016.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimiza- tion: A methodological tour d' horiozo.. European Journal of Operational Research, 290(2), 2021. Publisher: Elsevier.
Xavier Bresson and Thomas Laurent. The transformer network for the traveling salesman problem. CoRR, abs/2103.03012 2021.
Chris Cameron, Rex Chen, Jason Hartford, and Kevin ecyton-Brown Predicting propositional satis- fiability via end-to-end learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličkovié. Combinatorial optimization and reasoning with graph neural networks. arXiv:2102.09544 [cs, math, stat], Apr. 2021. arXiv: 2102.09544.
M. Cutler. Efffccentt special case algorithms for the n-line planar traveling salesman problem. Ner- works, 10(3), 1980. _eprint: https://onlineliraayy http:///wlinniibbaa.iiwwll..ee. wttp////i/p///11.1000/////e////
Hanjun Dai, Hui Li, Tian Tian, Huang Xin, Lin Wang, Zhu Jun, and Song Le. Adversarial attack on graph structured data. 35th International Conference Machine Learning, ICML, 2018.
10

---

Published as a conference paper at ICLR 2022
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Marths Rousseau. Learning heuristics for the tsp by policy gradient. In Willem-Jan van Hoeve, editor, Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Cham, 2018. Springer International Publishing.
Festa. A brief introduction to exact, approximation, and heuristic algorithms for solving hard combinatorial optimization problems. In 2014 16th International Conference on Transparent Optical Newworks (ICTON), July 2014. ISSN: 2161-2064.
Antoine François, Quentin Cappart, and Louis-Martin Rousseau. How to evaluate machine learning approaches for combinatorial optimization: Application to the travelling salesman problem. arXiv preprint ar arXiv: 13121, 2019.
Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnemann. Robustness of graph neural networks at scale. In Neural Information Processing Systems, NeurIPS, 2021.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. 34th International Conference on Machine Learning, ICML, 3, 2017.
Stephan Günnemann. Graph neural networks: Adversarial robustness. In Lingfei Wu, Peng Cui, Jian Pei, and Liang Zhao, editors, Graph Neural Networks: Foundations, Frontiers, and Applications, chapter 8, Springer, Singapore, 2021.
Shai Haim and Toby Walsh, Restart Strategy Selection Using Machine Learning Techniques. In Oliver Kullmann, editor, Theory and Applications of Satisfiability Testing SAT' 2009, Lecture Notes in Computer Science, Berlin, Heidelberg. 2009. Springer.
Holger Hoos and Thomas Stützle. SATLIB: An online resource for research on SAT. In SAT 2000.
Apr. 2000. Journal Abbreviation: SAT 2000.
Alexey Ignatiev, Antonio Morgado, and Joao Marques-Silva. PySAT: A Python toolkit for prototyp- ing with SAT oracles. In SAT, 2018
Ahmadreza Jeddi, Mohammad Javad Shafiee, and Alexander Wong. A Simple Fine-tuning Is All You Need: Towards Robust Deep Learning Via Adversarial Fine-tuning. arXiv:2012. [cs],
Dec. 2020. arxiv: 2012.13628.
Chaitanya K. Joshi, Thomas Laurent, and Xavier Bresson. An Efficient Graph Convolutional Net- work Technique for the Travelling Salesman Problem. 1xXiv:190.001227 [cs, stat], Oct. 2019.
arXiv: 1906.01227.
Chaitanya K. Joshi, Quentin Cappart, Louis-Matin Rousseau, and Thomas Laurent. Learning TSP Requires Rethinking Generalization. arXiv:2006.0703 [cs. stat], Sept. 2021. arXiv: 2006.07054.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. Advances in Neural Information Processing Systems, 30, 2017.
Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In 3rd Interna- tional Conference on Learning Representations, {ICLR) 2015, 2015.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, Learn to Solve Routing Problems! In 7th International Conference on Learning Representations, ICLR 2019, 2019.
Vitaly Kurin, Saad Godil, Shimon Whiteson, and Bryan Catanzaro, Improving SAT solver heuristics with graph networks and reinforcement learning. CoRR, abs/1909. 18800, 2019.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018.
Marcelo O. R. Prates, Pedro H. C. Avelar, Henrique Lemos, Luis C. Lamb, and Moshe Y. Vardi. Learning to solve comoleee problems: A graph neural network for decision TSP. In The Thirty-Thrrd AAAI Conference Artificial Intelligence, AAAI 2019. AAAI Press, 2019.
11

---

Published as a conference paper at ICLR 2022
Günter Rote. The N-line Traveling Salesman Problem, 1991.
Daniel Selsam and Nikolaj Bjørnr. Guiding nigh-Performance SAT Solvers with Unsat-Core Pre- dictions. PrXXiv:903.0444 [es], July 2019. arXiv: 1903.04671.
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill. Learning SAT solver from single-bit supervision. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
David Stutz, Matthias Hein, and Bernt Schicle. Disentangling Adversarial Robustness and General- ization. In IEEE Conference Computer Vision and Pattern Recognition, CVPR 2019, 2019.
Arun Sai Suggala, Adarsh Prasad, Vaishnavh Nagarajan, and Pradeep Ravikumar. Revisiting Adver- sarial Risk. In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, Apr. 2019. ISSN: 2640-3498.
Kah Kay Sung. Learning and example selection for object and pattern detection. PhD Thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 1995.
Christian Szegedy, W. Zaremba, llya Sutskever, Joan Bruna, D. Erhan, Ian J. Goodfellow, and R. Fer- gus. Intriguing properties of neural networks. 2nd International Conference on Learning Repre- sentations, ICLR, 2014.
Niklas Sörensson and Niklas Een. Minisat v1.13-a sat solver with conflict-clause minimization. International Conference on Theory and Applications of Satisfiability Testing, 01 2005.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness May Be at Odds with Accuracy, In 7th International Conference on Learning Repre- sentations, ICLR 2019, 2019.
N. Vesselinova, R. Steinert, D. F. Perez-Ramire, and M. Boman. Learning Combinatorial Optimiza- tion on Graphs: A Survey With Applications to Networking. JEEE Access, 8, 2020. Conference Name: IEEE Access.
Runzhong Wang, Zhigang Hua. Gan Liu, Jiayi Zhang, Junchi Yan. Feng Qi. Shuang Yang. Jun Zhou, and Xiaokang Yang. A bi-level framework for learning to solve combinatorial optimization on graphs. CORR, (ix//1066.4927, 2021.
Han Xu, Yao Ma, Hao-Chen Liu, Debayan Deb, Hui Liu, Ji-Liang Tang, and Anil K. Jain. Ad- versarial Attacks and Defenses in Images, Graphs and Text: A Review. International Journal of Automation and Computing, 17(2), Apr. 2020.
Kaidi Xu, Hongge Chen, Sijia Liu, Pin Yu Chen, Tsui Wei Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. IJCAI International Joint Conference on Artificial Intelligence, 2019-Augus, 2019.
Runze Yang and Teng Long. Derivative-fres free optimization adversarial attacks for graph convolutional networks. PeerJ Computer Science, 7, Aug. 2021. Publisher: PeerJ Inc.
Gal Yehuda, Moshe Gabel, and Assaf Schuster. It's Not What Machines Can Learn, It's What We Cannot Teach. In International Conference Machine Learning. PMLR, Nov. 2020. ISSN: 2640-3498.
Emre Yolcu and Barnabás Póczos. Learning local search heuristics for boolean satisfiability. In NeurIPS, 2019.
Daniel Zügner,, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. International Conference on Knowledge Discovery and Data Mining, KDD, 2018.
12

---

Published as a conference paper at ICLR 2022
A ACCURACY ROBUSTNESS TRADEOFF FOR COMBINATORIAL SOLVERS
If the accuracy robustness trade-off existed for neural combinatorial optimization, it would imply that it is hopeless to strive for an accurate general-purpose neural combinatorial solver. Fortunately, this is not the case. To show this built upon the ideas of Suggala et al. (2019) but we only consider the special case of combinatorial decision problems where each possible prediction Y is either true or false (i.e. no stochasticity of the true label as long as we account for the ambiguity in Y).
For general learning tasks, Suggala et al. (2019) refined the classical definition of adversarial ro- bustness s.t. there is provably no such trade-off in general classification tasks if either the dataset "margin separable" or when we restrict the perturbation space to label-preserving for a Bayes optimal classifier.
For combinatorial optimization with a sound perturbation model G we can argue both ways. First, due the soundness never encourage wrong prediction (i.e. the margin condition is natu- rally fulfilled). This contrast to e.g. image classification where an instance close to the decision boundary with the common L perturbation model || øIlp changes its true label or becomes meaningless (e.g. a gray image) for large enough r. Second, the Bayes optimal classifier for combi- natorial optimization solves the optimization problem perfectly p(æ) (with support(p(zz) S X). For these reasons, we do not need to include the Bayes optimal classifier in the definition of the attack (Eq. Tp.
More formally, we show by contradiction that any minimizer f arg min ser R (f) is optimal w.r.t. men R(.). Let f be an optimal classifier w.r.t. R(() for combinatorial decision problem.
We assume the loss & equal for all possible optimal Y, to account for the multiple possible and define the adversarial risk
Radv Gf) (xwp(()
max ((fo(z), h x, Y7) &EG(o,Y)
for any data distribution p(x) and the standard risk R(f)) E Em-p(a) (2), W.l.o.g, we assume the best possible risk zero R (i.e. the prediction is always true).
Suppose f and f differ in their prediction (ax) # (ax) over non-empty subset of support (x))..
Since f* is optimal and there is no stochasticity in the true label Y, it is always correct with standard risk R(f*) and, analogously, Radv, =.
Thus, cannot be an optimizer of f arg min R(f) if its predictions differs over a non-empty subset of sp())
Note that this also holds for support(p(zz) C (upport(G(p(z))) C X which is indeed the interesting case for contemporary data generators and models.
B PROOF OF PROPOSITION
Proposition 1 Let x ki (vi,..., , Un) A... km (UI...., Un) be a boolean statement in Conjunctive Normal Form (CNF) with clauses and variables. Then æ. perturbed version of æ, has the same label y = ÿ in the following cases:
1 with truth assignment Y. Then, literals in x to obtain æ, as long as one literal in Y remains in each clause.
SAT: is satisfiable
arbitrarily remove add
DEL: æ is unsatisfiable y = and we obtain from æ through arbitrary removals of literals, as long as one literal per clause remains.
ADC: æ is unsatisfiable y = Then, we can arbitrarily remove, add, or modify clauses in æ to obtain ă, as long as there remains subset of clauses that is unsatisfiable in isolation.
W.L.ogg we assume that an empty clause is true. That is, we evaluate the expression the empty clauses not there. Moreover, assume to know one possible Y (multiple might exist).
13

---

Published as a conference paper at ICLR 2022
SAT: Every disjunctive clause evaluates to one, if one literal is true. Since we keep at least one literal Y each clause, every clause evaluates to one. The statement evaluates to one since the conjunction of true statement is also true.
DEL: Since every clause is disjunction of literals, the removal of one/some of the literals strictly reduces the number specifiable assignments. That is, removing any literal 1 from its clause removes the possibility satisfy this clause through 4 = 1.
Since the clauses are conjunctive, all clauses need to evaluate to true. If subset of clauses it not satisfiable by themselves (i.e. not all can true at the same time), the expression necessarily resolves to 0.
ADC:
Hence, all conditions in Proposition I do not change the satisfiability but might alter Y. It is apparent that the updated Y can be obtained efficiently. D
C PROOF OF PROPOSITION 2
Let a* be the optimal route over the nodes in G, let 7 V be an additional node, and P are any two neighhouring nodes on a". Then, the new optimal route a* (including 7.) is obtained from of through inserting Z between P and Q if B (A, B) E V X (((P))) with A # B s.t. (A, 2) + (B, 2) w(A, B3) S w () w(Q 2) w(P.Q).
Proposition 2
Corollary We can add multiple nodes G and obtain the optimal route 5* as long the condi- tion of Proposition 2) (including the other previously added nodes) is fulfilled.
Corollary For the metric TSP, it is sufficient if the condition of Proposition 2 holds for (A, B) E V \
(I(P. Q}} U HI) with * B where H denotes the pairs of nodes both on the Convex Hull H. E CH(V) that are not a line segment of the Convex Hull.
Proof. We proof by contradiction. We define S) E 12 ((P.Q)) to be the two neighboring
nodes of Z on o" Suppose w(P, Z) + (Q, Z) (P.Q) 5* would not contain the edges w P,P,2. Z) well as wQ,
< <w Z) w(S Z) w S) and
We know by optimality of that
- (6:
and by optimality of Ø* that
+t))) 2(0')
Thus,
- 11) (R; () wRR
c(o") +
and equivalently
" (Q, w (R,2) + w 2) (R
which leads to a contradiction.
Since do not know what edges contained in 5" (i.e. what nodes could be R and S) we state the stricter condition A (A, B) E V2 ((P,)) Q)} with A * B s.t. (A,, Z) + (B, (A, S w w(P, 2) + w(Q, 2) (P.
If multiple o* exist, then this statement holds for any optimal route that has a direct connection between and Q. Corollary I follows by induction and Corollary is due to the fact that the in metric space the optimal route o* must be a simple polygon (i.e. no crossings are allowed). This was first stated for an euclidean space as "the intersection theorem" by [Cutler (1980) and is direct consequence of the triangle inequality. Also note, alternatively to the proof presented here, one can also unfold the dynamic program proposed by Rote (199I) to end up at Proopossiiooon
14

---

Published as a conference paper at ICLR 2022
D PROJECTED GRADIENT DESCENT (PGD)
PGD is one of the most success- ful and widely studied approaches to craft adversarial examples. For a further techniques and a broader overview of adversarial robustness in various domains, we refer to Xu al. 2020).
Algorithm D.1: Projected Gradient Descent
Data: Problem (x: Y) and possibly y. Solver fo(-).
Loss f, budget A, attack steps learn rate
20 < initialize(xx, Y)
for t E {0,
...., 1,..,...,
1 do
f(+1 + update @2 ar, (E. 3,
All our attacks roughly match the framework of Algorithm D.I] First, we initialize the perturbed instance, or, alternatively, we can use some variable that models the difference to the clean instance (line 1). Initial- ization strategies that we consider are random initialization initializing the clean instance. Then we perform the attack for steps and in each step update the perturbed instance through a gradient descent step (line 3). For faster con- vergence we additionally use Adam as optimizer (Kingma & Ba 2015). After the gradient update we perform a projection step that ensures we stay within the budget A or satisfy other constraints. For simplicity, we omit the fact that we use early stopping in all our algorithms. Specifically. each attack step we check if the current perturbed instance 2t+1 comes with the best loss so far. Then, af- ter attack steps we assign the best possible a. < arg (e(...)....e {(Jo( h( æ, Y)). This happens right before we (optionally) perform postprocessing. Finally, we return the perturbed instance ø with solution Y' or decision label y.
1
end
T t postprocess Tg. A)
return ã, ( x. YY
Limitations. As discussed in 3 we require the model to be differentiable w.r.t. its input. For- tunately, most neural combinatorial solvers rely on GNNs and therefore this does not impose an issue. However, even if assessing non-differentiable model one could revert to frrivative-free optimization (Yang & Long 2021).
For some combinatorial optimization problems the number of variables we need to optimize over can be very large. For example, when attacking a Maximum Independent Set neural solver (Li et al.) 2018) using our perturbation models for SAT, we need to construct graph that blows up quickly. Nevertheless, this could be done with derivative-fres optimization (Yang & Long 2021] or a scalable variant of of L PPD called projected randomized block coordinate descent (Geisler al. 2021).
E SAT ATTACK DETAILS
SAT model description. Selsam al. (2019) propose model the input problem as a bipartite graph as described in B 4.2 We instantiate the model as described in their paper: over 26 message passing steps the GNN updates its embeddings of size 128. Clause nodes and literal nodes have separate LSTMs to update their embeddings with messages produced by 3-layer MLPs. After the last message passing steps, the output vote on whether the problem is satisfiable or not obtained by transforming the clause embeddings with an additional vote-MLP and averaging over the final votes of the literal nodes. The paper also notes that the number of message passing steps has to be adapted to the problem size. As no specific values are provided, we use 64 steps for the50-100 dataset and 128 steps for the SATLIB and uni3sat data.
Selsam et al. 2019) trained their model in a single epoch on a large dataset consisting of "millions of samples". However, since SSelsam et al. (2019) did not publish their dataset used total of 60,000 samples with the very same data generation strategy. We then use 50,000 of the samples to train the model for 60 epochs. With this strategy closely match the reported performance. For the larger train set in Table I] we generate an additional 5,000 samples. During training we use the same perparaameesss as described in the paper. Please use the referenced code for exactly reproducing the dataset.
15

---

Published as a conference paper at ICLR 2022
Optimization Problem. We restate the optimization problem for adversarial attack SAT decision problem. The SAT attack tries to find a perturbed instance è that maximizes the loss s.t. every clause contains at least one literal Ij that is present in the solution assignments Y = ('7,....1,, 1 1 E (-m;, 11))- Here we omit that we additionally constrain the number of inserted/removed literals relatively to the number of literals in the clean instance via budget A.
max ((o()))
Aky E ē (1g E k with 1j =17)
(E.1)
The ADC attack maximizes the loss by adding clauses to the problem, meaning that every clause k; the original problem æ has to be present also the perturbed instance ă, as these clauses ensure that the problem remains unsatisfiable:
max {(o(@)) s.t. Vk; Ex E
(E.2)
Lastly, the DEL attack optimizes over what literals to delete from the problem's 's clauses, as long as no clause is removed completely. This results in the following optimization problem:
max (ff(((( 0) s.t. vk, k Sk.
A nonempty(k:)
(E.3)
#
Attack Details. The attack SAT problems modifies the literals that contained in clauses. This means specifically that we optimize over the edges represented by the literals-clauses adjacency matrix A E (0, 1) 2nxm. We implemented these attacks such that they can operate batches of problems, however we omit this at this point in the following for an improved readability.
Algorithm E. describes in detail SAT and DEL (see Proposition 1). The difference of the adja- cency matrix A to the adversarially perturbed version A is modelled via the perturbation matrix M: (#: Á A ① M). We then optimize over M. During the SAT attack, we allow deletions and additions of edges, as long as one cluution-preserving truth assignment per clause, described by the indicator T onchot(Y) ). preserved (line 7). For the DEL attack only deletions are al- lowed, under the constraint that no clause can be fully deleted (lines & 10). Additionally, a global budget is enforced (line 6). For details on the budget as well as other hyperparameters of the tack, we refer to Table E. For the ADC attack described in Algorithm E.2 the perturbation matrix M (0, 1)22 2m describes additional clauses appended to the original problem (line 4). The attack can freely optimize over M but the number of literals/edges. A is enforced s.t. on average each clause contains as many literals as a clause A (line 6).
Table E.1: Hyperparameters for the attacks NeuroSAT proposed in
SAT
DEL
ADC
attack steps learning rate
500
500
500
0.1
0.1
0.1
fraction of perturbed literals A
5% of edges
5% of edges
25% of clauses
# final samples temperature scaling
20
20
20
5
5
Because the attack optimizes over a set of discrete edges with a gradient based method, similarly (Xu al. 2019), we relax the edge weights to [0, 1] during the attack. Before generating the perturbed problem instance A, we sample the discrete M' from a Bernoulli distribution where the entries of the matrix M represent the probability of success. In contrast to (Xu et al.) 2019) we sample 19 instead 20 times but add an additional sample that chooses the top elements in M. Thereafter, take the sample that maximizes the loss. Moreover, our projection differs slightly from the one proposed by Xuu et al. (2019) since we iteratively enforce the budget instead of per- forming bisection search.
16

---

Published as a conference paper at ICLR 2022
Algorithm E.1: SAT & DEL Attack
Data: Adjacency A E {0, 1]2nxm,
edge budget A, steps s, learning rate solution T' E {0, 1
Algorithm E.2: ADC Attack
SAT model Jo. label y
Data: Adjacency A E {0, 1]2nxm
Result: Perturbed Adjacency Á
clause budget w, steps s, learning
Initialize M 0 (22xx
rate a; SAT model fo
for t E {0, 1...., 1 do
Result: Perturbed Adjacency A
y then A + A + M
Initialize M <- 0 2mxm.
else Å + A M
2 A + avg(A, axis = 0) m
for E {0, 1, .....
1] do
M + update( M, a, V((fo(A),))
Á append( (.A, M
M project-budget(M.. A)
if y then M t M T
s
M update M, a, fo
else
M + project-budget(M, A)
M - M * A M ensure-no-del(MM)
end
8 M'
sample(M))
end
Á < appendddn, M')
end
13 M' +- sample(M)
14 A + A + M'
Computational complexity. All three attacks operate for steps. Under the assumption that the models are linear w.r.t. the number of edges in the graph representation of the problem (for forward and backward pass), each step has time complexity of O(mn). Therefore. the overall attack has time complexity of (nms)). Under the same assumption for the memory requirements of V P the total space complexity is (nmm).
F TSP ATTACK DETAILS
For simplicity only discuss the case of metric TSP. This is also what the used neural sovers are mainly intended for. The TSP attack actually implemented in a batched fashion. However, for an improved readability omit the details here. We refer to table Table F.] for details on the attack hyperparameters.
DTSP model. The DTSP model employs a GNN to predict whether there exists route of certain cost on an input graph (Prates et al., 2019). The model sequentially updates the embeddings of both nodes and edges that were initialized by 3-layer MLP with the coordinates input. After multiple message passing steps, the final prediction is then based on the aggregation of the resulting edge embeddings. We follow the training guidelines deseribed in the paper and train 220 graph samples. The graphs are generated by sampling from the unit square (x E [0, 1]mx²) and solutions obtained with the concorde solver (Applegate each graph for training, validation and test data by increasing and decreasing the true cost by a small factor.
2006). Dual problem sets are built from
ConyTSP model. The ConvTSP model aims at predicting the optimal route Y = over given graph via GCN (Joshi et al. 2019). predicts probability map over the edges indicating the likelihood of an edge being present in an optimal solution. These lay the basis for different solution decoding procedures. We employ their greedy search method, where the graph traversed based on the edges with the highest probabilities. We follow the training procedure described in the paper as well as the data generation technique. Data is generated the same way as for the DTSP model, however the target represents binary indicators whether During training, the binary cross entropy between the target and the probability maps over the edges is minimized, and solution-decoding technique is only applied during inference.
edge is present in the optimal solution.
Optimization problem. We again restate the optimization problem from Eq. for the specific case of TSP. We add A nodes to the original problem [0, 1 to create larger, perturbed problem
17

---

Published as a conference paper at ICLR 2022
Table F.1: Hyperparameters for the attacks on TSP proposed in
DTSP
ConvTSP
maximum number of adv. nodes A
5
5
attack steps learning rate gradient project learning rate
200
500
0.001
0.01
0.002
0.002
gradient project steps
3
instance æ E [0, (1((++))))))+)))))))))))))))(( xx2 which maximizes the loss:
max (()) s.t. VI; with i
Proposition 2 holds
(F.1)
Attack details. The input of the TSP is represented by the coordinates [0, 1|nx2 for the nodes. Additionally, we know the near-optimal route Y obtained with the Concorde solver which we use ground truth. During the TSP attack we add additional adversarial nodes Z E [0. 1] 1]Ax2 to the input problem æ. The adversarial nodes are initialized by randomly sampling nodes until they fulfill the constraint from Proposition 2 (line 1). For the attack, described in Algorithm F.I. operate solely on the coordinates of the adversarial nodes and assume that the model converts the coordinates into weighted graph. For the DTSP model, additionally calculate the updated route cost on (accordingly to y) and append it to the input. For simplicity, we omitted this special case in Algorithm F.1 Moreover, for the DTSP we do not pass Y to the loss; instead, we use the decision label y that kept constant throughout the optimization. We then obtain the updated coordinates Z for the perturbed solution Y (lines 5-6). In the project step (line 7), only consider the coordinates in Z that violate the constraint. As discussed in 5.2 we perform gradient descent on the constraint due its non-convexity. We decide against optimizing the Lagrangian since this would require evaluating the neural solver fe and, therefore, is less efficient. For the projection, we update the adversarial node i that violates the constraint with
w((, w(A,B))
Z. w (.. (Q, -(P())
min + (A,EE
until the constrain is fulfilled again but for at most three consecutive steps.
Algorithm F.1: TSP Attack
Data: Node Coords as [0, 1|x22 steps 8,
learning rate TSP model fo. Adversarial Coords E [o, 1] Ax2
Result: Perturbed Node Coords
[0, 1] ()
Initialize Z <- random-allowede for é {0, 1,...... , 1) do
mask t- is- wew-ooostraint-ullllleee. (Z
+ append( xx Z [mmas]) Ý +
Z update( Z, a. vl(fo(W)) (W),
Z + project Z, x);
end return ã, Y
Computational complexity. We again assume that the model has a linear time and space complex- ity. This time it is linear w.r.t. the O(n²) number of elements in the distance matrix between the input coordinates. The most costly operation we add, the check the constraint is violated or not for each of the potentially added nodes A. This operation has time and space complexity of
18

---

Published as a conference paper at ICLR 2022
Table G.I: Runtime in milliseconds for the Glucose and MiniSAT solver on 100 clean and perturbed
problem instances from 50-100
Perturbed
DEL
ADC
SAT
0.1897 + 0.20
0.1944 + 0.13
0.1315 + 0.06
Glucose
0.0335 0.03
0.0816 + 0.11
0.1391 0.08
0.1351 + 0.07
0.1510 0.11
0.0980 + 0.05
MiniSAT
0.0189 0.02
0.0587 + 0.09
0.1383 0.31
(n²) since we need to evaluate the distances to all nodes (except the special case where both nodes are on the convex hull but non-adjacent, see Corollary 2). However, checking the constraint has the same complexity as the neural solver. Therefore, the overall space complexity turns out to be O(An²) = (n?) and the time complexity is O(n2s) with the number of attack steps s.
G THF-THE-S THE-SHELF SAT SOLVERS: TIME COST OF PERTURBED INSTANCES
Comparison SAT Solvers. We test two SAT-solver's runtime all attacks for both clean per- turbed samples from the 50-100 dataset to better understand the difficulty of the samples for non- neural SAT solvers. Table G.T shows the mean well the standard deviation of the Glucose Audemard & Simon 2009) well as the MiniSAT (Sörensson & Ecn 2005) solver. The results suggest that both solvers can more quickly find that sample unsatisfiable for perturbed samples from both the DEL and the ADC attacks. For perturbed satisfiable samples, the runtime increases compared the clean sample for the MiniSAT solver while Glucose solver needs about the same time as for the clean sample to find a solution.
H CONVERGENCE NEUROSAT
Complementary to Fig. we also present the convergence for 100 randomly chosen satisfiable instances from the 10-40 dataset. We see that the observations drawn from Fig. SJalso hold here: (1) rarely an instance is predicted as SAT despite the moderate budget of perturbing 5% of the literals and (2) NeuroSAT identifies the sample as satisfiable requires more message passing steps to do so.
1.0
Probability SAT
Clean
Perturbed
0.5
0.0
Message Passing Steps
Figure H.1: Clean vs. perturbed: NeuroSAT's prediction over the message passing steps.
EFFICIENCY NEUROSAT ATTACKS
To better understand the efficiency of the NeuroSAT attacks and how many gradient update steps are needed to flip the model's prediction, we show additional results for the attack strength over several attack step budgets s Fig. I.I The indicated number of gradient update steps are taken during the attack, while retaining the learning rate from Table E. and early stopping
instance level. The results in Fig. I.T show that only gradient update step suffices for the SAT attack to decrease the accuracy from 79% to 26%. Compared to the results from From/Fig.. where the random attack draws a single sample and only decreases the accuracy to 74%, the importance the guidance through the gradient update becomes apparent. For the DEL attack the NeuroSAT model, the attack strength
19

---

Published as a conference paper at ICLR 2022
converges around 200 steps, showing again the imbalance between the labels with regards to how many misclassification the attack can force.
0.8
1.0
Accuracy
0.6
Accuracy
0.9
0.4
0.8
0.2
5
50
50
Attack Steps
Attack Steps
(a) SAT Attack
(b) DEL Attack
Figure I.1: Attacks on NeuroSAT with varying number of attack steps
further compare the efficiency of the attacks to the random baseline. Random samples are drawn until the loss matches or exceeds that of the adversarially perturbed sample. We introduce a cut-off at 20000 samples and report the mean number of samples for the SAT and DEL attack on the budgets A 0.01 and A 0.05.
In Table 1.1
Table I.1: Number of random samples to match optimized loss
0.01
0.05
SAT
1257
9532
We observe that the additional computational cost of generat- ing adversarial samples is justified, given the random baseline per- forms comparably well only with several thousand random samples drawn. While the efficiency of the proposed approach in general is important to consider for practical relevance, it is not sufficient to only compare to the random baseline terms of sample efficiency. There are several other aspects to consider, like additional computational and storage overhead for larger, denser dataset or to what extent larger dataset of random or adversarial examples can improve generalization.
DEL
749
4854
J QUALITATIVE RESULTS SAT
To illustrate the changes SAT problems, provide example for successful attack small and fairly simple problem (from SAT-3-10). While the model recognizes the problem below as satisfiable with 100% confidence, the SAT attack perturbes it (modified clauses highlighted blue) such that the model votes 'satisfiable" with only 0.59% confidence.
Clean SAT Problem:
+ -01---3----------- -VV ( 1V3V4 (V3VVV1333VVV2VV 4)
(-4V-3 VVV-3V12)/A (1
4V 22 V 3) A (- 3V-2VV
-V) ((-44 12-44-22V1VV -2V1V3) A (-2V1V
((-4V
[V -2v1v3) A
3V EVV-2V-2 -1 V -VV
(1V2V3V4) 22 ((<4 3 V2
[ 44 1 4) (3
44V -2-2 -2 A V
(-4 V A
-4V v (
(-4
3
-1 4) (-3V-I)
Perturbed SAT Problem:
(-1V-3v1y2) (1 -VV
4)A
1 (-4V -0 (-4V 2 3) A
2 Y 4) A
VV3)
3V V) ( 3 4) A
3
1
(1
V 2
4)
(1 (1v2 A
44V-2V1) (-4V -V (1
3 V 4)
A 3 V
TC
2
4) A (-4 -3V-
- 3 V 3 - V
(4
V
(-4
-4V-2V-1 (V
(-4
3-3
(-3VV=)
20

---

Published as a conference paper at ICLR 2022
K QUALITATIVE RESULTS TSP
In this section complement the figures Fig. and Fig. 9 with further examples. In Fig. K.1 examples for the attack DTSP further examples ConvTSP Fig. K.2
plot further
Concorde
Pert. False
Pert. True
Figure K.1: Examples of the optimal route Y and perturbed routes y for Decision
Concorde
Perturbed
Clean
Adv. Points
(c)
Figure K.2: Exemplary problem instances where the attack successfully changed the optimal route for ConyTSP that show drastic changes of the prediction.
21


Reviews:
[{"review_id": "qRAIa9DeVf", "reviewer": "Reviewer_Eun2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "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. \n\nThere 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "ien1Syp-gT4", "reviewer": "Reviewer_7Apu", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "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.\n\nLanguage-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\nvariable 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.\n\nTo 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).\n\nIt 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "gEZ7BIOoz6B", "reviewer": "Reviewer_4nmR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "### After Author Response\nSince the authors' response and the revised submission have addressed my major concerns in:\n1. how to position their work among previous works, and\n2. the practical efficiency of the proposed method (in the combinatorial problem showcase)\n\nI believe this paper is of good quality and would be happy to raise my rating from 5 to 6.\n\n----------------------------------------------\n### Strengths:\n#### 1. The paper is dealing with an important and interesting problem.\n#### 2. The authors illustrate their insights and method well with two combinatorial problems of significant theoretical and practical interests.\n#### 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).\n#### 4. The paper is well-written and easy to follow in general.\n\n### Weaknesses / Concerns:\nAs 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.\n#### 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.\n#### 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).\n#### 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.\n#### 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.\n\n*Reference:*\n\n*Gal Yehuda, Moshe Gabel, and Assaf Schuster. (2020) It’s Not What Machines Can Learn, It’s What We Cannot Teach.*\n\nFinally -- this is not so important -- there are a few typos / word duplicates that could be spotted.", "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.", "summary_of_the_review": "### After Author Response\n1. 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.\n2. The paper shows that adversarial training with the adversarial data may be a useful practical method for improving neural solver's generalization performance.\n\n-----------------------------------\n### Initial Summary\n\nWhile 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).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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)