Year: 2021

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.

heading: 1 INTRODUCTION
text: Combinatorial Optimization covers some of the oldest and most studied computational problems. Well-known examples are the study of the NP-complete SATisfiability problem for boolean statements or the Traveling Salesperson Problem (TSP). Today, these problems can be solved efficiently with approximate solvers that have been crafted over the previous decades (Festa, 2014). As an alternative to engineered, application-specific heuristics, learning seems to be a good candidate (Bengio et al., 2021) and was studied as a component in traditional solvers (e.g. Haim & Walsh (2009); Singh et al. (2009)). Recently, end-to-end deep learning for NP-hard combinatorial optimization has gained attention, triggered by the widespread success of (geometric) deep learning. Nevertheless,
it is still an open question if and to what extent end-to-end deep learning can effectively and efficiently approximate such NP-hard combinatorial optimization problems.
Moreover, there is a “Catch-22“; even if neural networks could approximate the solutions for NP-hard problems, generating the training data is either (a) incomplete but efficient or (b) complete but inefficient/approximate. An incomplete data generator (a) crafts the problem instances s.t. their labels are know and a complete data generator (b) solves the NP-hard problem instances to obtain the labels. Moreover, regardless of case (a) or (b), it is intractable to obtain a dense sample even for moderate problem sizes due to the large problem space. For the special case of (a) exact polynomial-time data-generators, Yehuda et al. (2020) detail two challenges as a result of the NP-hardness: (1) Easier subproblem: a dataset from an efficient
data generator only captures a strictly easier subproblem. (2) Spurious features: due to the lack of completeness, the resulting dataset can be trivially solvable due to superficial/spurious features. These findings extrapolate to case (b) for a sufficiently sparse sample (i.e. the data could have been generated by an efficient data generator). As a consequence, it is even more concerning that often the same (potentially flawed or biased) data generator is used for training and evaluation. At best, neural solvers are additionally evaluated on small independent datasets (e.g. from benchmarks).
We propose to study neural combinatorial optimization through the lens of adversarial robustness. It is a challenging 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 in Fig. 1 how adversarial attacks practically address the aforementioned challenges for two relevant cases in neural combinatorial optimization: (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 a model’s generalization ability instead of simply testing on the same data generation procedure or a sparse external dataset.
Adversarial robustness is a desirable property for neural combinatorial optimization, since, in contrast 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 a model with high accuracy and high robustness. One key factor to avoid the accuracy robustness trade-off is choosing a perturbation 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/unnoticeable 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 is 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 of adversarial robustness to the field of neural combinatorial solvers to tackle fundamental problems in the evaluation of neural solvers. (2) We propose perturbation 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.

heading: 2 BACKGROUND ON NEURAL SOLVERS
text: Intuitively, combinatorial optimization is the task of finding an optimal element from the finite set of possible solutions (e.g. the truth assignment for a boolean statement). We formalize this as Y = arg minY ′∈g(x) c(x, Y
′) where x is a problem instance, g(x) = Y the finite set of feasible solutions, and c(·) a cost function. Typically, there is also an associated binary decision problem y, such as finding the optimal route vs. checking whether a route of at most cost c0 exists (see § 4 and § 5). Then, for example, a neural solver ŷ = fθ(x) learns a mapping fθ : X → {0, 1} to approximate the decision problem. In this work, θ are the parameters, x ∈ X is the problem instance, and ŷ (or Ŷ ) the prediction. In case of supervised learning, we then optimize the parameters θ w.r.t. a loss `(fθ(x), y) over a finite set of labeled training instances (x, y). However, to obtain the exact labels y for a given x is intractable for larger problem instances due to the exponential or worse runtime. The two important strategies are mentioned in the introduction and visualized in Fig. 1: (a) an efficient but incomplete data generator (b) using a solver to obtain the labels for random samples.

heading: 3 ADVERSARIAL ROBUSTNESS
text: Adversarial robustness refers to the phenomenon that machine learning models can be fooled by small perturbations of the input instance (Szegedy et al., 2014). We define an adversarial attack in
Eq. 1, where the parameters θ are constant and G denotes the perturbation model that describes the possible perturbed instances x̃ around the clean sample x (i.e. the perturbation space) given the original solution Y . We introduce the term h(x̃,x, Y ) since Ỹ 6= Y in the general case.
`adv,G(x, Y ) = max x̃
`(fθ(x̃), Ỹ ) s.t. x̃ ∈ G(x, Y ) ∧ Ỹ = h(x̃,x, Y ) (1)
Sound and efficient perturbation model. Our framework for a neural combinatorial solver fθ 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(x̃,x, Y ) for all possible x̃. 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 imperceptible/unnoticable perturbations (Szegedy et al., 2014).
While we can naively obtain a 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 Ỹ without applying a solver on the perturbed instance x̃. 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 `. (a) We can deal with the ambiguity in Y if the loss is equal for any two optimal solutions/predictions. This can be achieved naturally through 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 a loss that assesses the difference between prediction fθ(x̃) and ground truth Ỹ . For example, a viable loss for TSP is the optimality gap `OG(Ŷ , Y ) = |c(Ŷ )−c(Y )|/c(Y )) that is normalized by c(Y ).
Perturbation strength. With a sound perturbation model, all generated instances x̃ are valid problem instances regardless of how much they differ from x. Hence, in the context of combinatorial optimization, the perturbation strength/budget models the severity of a potential distribution shift between training data and test data. This again highlights the differences to other domains. For example in image classification with the common Lp perturbation model ‖x − x̃‖p ≤ r, the instance changes its true label or becomes meaningless (e.g. a gray image) for a large enough r.
Generalization. Specifically, adversarial robustness is one way to measure the generalization over perturbed instances x̃ is in the proximity of x. Adversarial robustness is important in the context of neural combinatorial solvers since training and validation/test distribution differ from the actual data distribution p(x). First, the data distribution p(x) is typically unknown and highly application-specific. Second, due to theoretical limitations of the data generation process the train and validation/test distribution only captures a simpler sub-problem likely suffering from spurious features (Yehuda et al., 2020). Third, we ultimately desire a general-purpose 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 are neither anomalous 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 a high-dimensional space. Thus, the so-called manifold hypothesis (Stutz et al., 2019) does not apply for combinatorial optimization. Or in other words, it is 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 generalization was reported for many learning tasks (Tsipras et al., 2019). That is, with increasing robustness the accuracy on the test data decreases. Interestingly, with a sound perturbation model and the purely deterministic labels in combinatorial optimization (the solution is either optimal or not), no such trade-off exists. Hence, if the model was expressive enough and we had sufficient compute, there would exist a model with high accuracy and robustness (see § A for more details).
Adversarial training. In adversarial training, we leverage adversarially perturbed instances with the desire of training a 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). Hence, adversarial training can be understood as a powerful data augmentation using hard modelspecific samples. Though it is not the main focus of this work, in § 6, we show that adversarial training can be used to improve the robustness and generalization of a neural combinatorial solver.
Remarks on decision problems. For the binary decision problems, we typically are not required to know Ỹ ; it suffices to know ỹ. Moreover, for such binary problems, we keep the solution constant y = ỹ. Nevertheless, there also exist practical perturbations that change decision the label. For example for SAT, we can add a set of clauses that are false in isolation which makes ỹ = 0.
Requirements for neural solvers. We study neural combinatorial solvers fθ that are often a Graph Neural Network (GNN). We then solve Eq. 1 using different variants of Projected Gradient Descent (PGD) and therefore assume the model to be differentiable w.r.t. its inputs (see § D). For nondifferentiable models, one can use derivative-free optimization (Yang & Long, 2021).

heading: 4 SAT
text: We first introduce the problem as well as notation and then propose the perturbation models (§ 4.1). Last, we discuss the attacks for a specific neural solver (§ 4.2).
Problem statement. The goal is to determine if a boolean expression, e.g. (v1∨v2∨¬v3)∧(v1∨v3), is satisfiable y = 1 or not y = 0. Here, we represent the boolean expressions in Conjunctive Normal Form (CNF) that is a conjunction of multiple clauses k(v1, . . . , vn) and each clause is a disjunction of literals li. Each literal is a potentially negated boolean variable li ∈ {¬vi, vi} and w.l.o.g. we assume that a clause may not contain the same variable multiple times. In our standard notation, a problem instance x represents such a boolean expression in CNF. A solution Y = {l∗1, . . . , l∗n | l∗i ∈ {¬vi, vi}} provides truth assignments for every variable. Hence, in the example above x = (v1∨v2∨¬v3)∧(v1∨v3), y = 1, and a possible solution is Y = {v1,¬v2, v3}. Note that multiple optimal Y exist but for our attacks it suffices to know one.

heading: 4.1 SOUND PERTURBATION MODEL
text: We now introduce a sound and efficient perturbation model for SAT which we then use for an adversarial attack on a neural (decision) SAT solver. Recall that the perturbation model is sound since we provably obtain the correct label ỹ and it is efficient since we achieve this without using a solver. Instead of a solver, we leverage invariances of the SAT problem.
Proposition 1 Let x = k1(v1, . . . , vn)∧ . . . km(v1, . . . , vn) be a boolean statement in Conjunctive Normal Form (CNF) with m clauses and n variables. Then x̃, a perturbed version of x, has the same label y = ỹ in the following cases:
• SAT: x is satisfiable y = 1 with truth assignment Y . Then, we can arbitrarily remove or add literals in x to obtain x̃, as long as one literal in Y remains in each clause.
• DEL: x is unsatisfiable y = 0 and we obtain x̃ from x through arbitrary removals of literals, as long as one literal per clause remains.
• ADC: x is unsatisfiable y = 0. Then, we can arbitrarily remove, add, or modify clauses in x to obtain x̃, as long as there remains a subset of clauses that is unsatisfiable in isolation.

heading: 4.2 NEURAL SAT SOLVER
text: Selsam et al. (2019) propose NeuroSAT, a neural solver for satisfiability-problems that uses a message-passing architecture (Gilmer et al., 2017) on the graph representation of the boolean expressions. The SAT problem is converted into a 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 a clause its node is connected to the respective clause node. NeuroSAT then recursively updates the node embeddings over the message-passing steps using this graph, and in the last step, the final vote ŷ ∈ {0, 1} is aggregated over the literal nodes. L0-PGD. The addition and removal of a limited number of literals is essentially a perturbation with budget ∆ over a set of discrete edges connecting literals and clauses. Similarly to the L0-PGD attack of Xu et al. (2019), we 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 [0, 1] and that we obey the budget ∆. After the attack, we use these weights to sample the discrete perturbations in
{0, 1}. In other words, the attack continuously/softly adds as well as removes literals from x during the attack and afterward we sample the discrete perturbations to obtain x̃.
Attacks. We then use these insights to craft perturbed problem instances x̃ guided by the maximization of the loss `0|1 (see Eq. 1). Specifically, for SAT and DEL, two of admissible perturbations defined in Proposition 1, we optimize over a subset of edges connecting the literal and clause nodes where we set the budget ∆ relatively to the number of literals/edges in x. For ADC we additionally concatenate d additional clauses and optimize over their edges obeying ∆ but keep the remaining x constant. If not reported separately, we decide for either DEL and ADC randomly with equal odds. For additional details about the attacks, we refer to § E.

heading: 5 TSP
text: 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 (§ 5.1). In § 5.2, we detail the attack for a neural decision TSP solver and, in § 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,M) that consist of a finite set of nodes V as well as edges M ⊆ V2 and a weight ω(e) for each possible edge e ∈ V2. We use the elements in V as indices or nodes interchangeably. The goal is then to find a permutation σ of the nodes V s.t. the cost of traversing all nodes exactly once is minimized (i.e. the Hamiltonian path of lowest cost):
σ∗ = arg min σ′∈S c(σ′,G) = arg min σ′∈S ω(σ′1(V), σ′n(V)) + n−1∑ i=1 ω(σ′i(V), σ′i+1(V)) (2)
where S is the set of all permutations and n = |V| is the number of nodes. Although multiple σ∗ 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 a permutation or the equivalent list of nodes. Moreover, we say σ contains edge (I, J) ∈ |M| if I and J are consecutive or the first and last element. In our standard notation x = G, Y = σ∗, and the respective decision problem solves the question if there exist c(σ∗) ≤ c0 of at most c0 cost.

heading: 5.1 SOUND PERTURBATION MODEL
text: Adversarially perturbing the TSP such that we know the resulting solution seems more challenging than SAT. However, assuming we would know the optimal route σ∗ for graph x = G, then under certain conditions we can add new nodes s.t. we are guaranteed to 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.
Proposition 2 Let σ∗ be the optimal route over the nodes V in G, let Z 6∈ V be an additional node, and X,Y are any two neighbouring nodes on σ∗. Then, the new optimal route σ̃∗ (including Z) is obtained from σ∗ through inserting Z between X and Y if 6 ∃ (A,B) ∈ V2 \ {(X,Y )} with A 6= B s.t. ω(A,Z) + ω(B,Z)− ω(A,B) ≤ ω(X,Z) + ω(Y,Z)− ω(X,Y ).
Corollary 1 We can add multiple nodes to G and obtain the optimal route σ̃∗ as long as the condition of Proposition 2 (including the other previously added nodes) is fulfilled.
Corollary 2 For the metric TSP, it is sufficient if the condition of Proposition 2 holds for (A,B) ∈ V2 \ ({(X,Y )} ∪ H) with A 6= B where H denotes the pairs of points both on the Convex Hull H ∈ CH(V)2 that are not a line segment of the Convex Hull.

heading: 5.2 NEURAL DECISION TSP SOLVER
text: Prates et al. (2019) propose a GNN (called DTSP) to solve the decision variant of the TSP for an input pair x = (G, c0) with graph G and a cost c0. DTSP predicts whether there exists a Hamiltonian cycle in G of cost c0 or less (y = 1 if the cycle exists).
Our core idea is to inject adversarial nodes to where the coordinates are yet to be determined (metric TSP). We determine the coordinates by maximizing the loss–a continuous optimization problem. This is easy to generalize to the non-metric TSP (omitting Corollary 2), if e.g. the triangle equality does not hold or there is no “simple” cost function concerning the node’s coordinates/attributes. Then, the optimization is performed over the edge weights, but depending on what the weights represent we might need to enforce further requirements.
Unfortunately, from Proposition 2 it is apparent that the constraint is non-convex and it is also not clear how to find a relaxation that is still sufficiently tight and can be solved in closed form. For this reason, when the constraint for a node is violated, we use vanilla gradient descent with the constraint as objective: ω(X,Z) + ω(Y,Z) − ω(X,Y ) − [minA,B ω(A,Z) + ω(B,Z) − ω(A,B)]. This penalizes if a constraint is violated. We stop as soon as the node fulfills the requirement/constraint again and limit the maximum number of iterations to three. Since some adversarial nodes might still violate the constraint after this projection, we only include valid nodes in 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 points allows us to parallelize the constraint evaluation for multiple points, despite the sequential nature, since we can ignore the subsequent nodes.

heading: 5.3 NEURAL TSP SOLVER
text: Joshi et 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 identical attack as for the TSP decision problem (see § 5.2) with the exception of having a different objective with variable label Ỹ . Although the optimality gap `(Ŷ , Y ) = c(Ŷ )−c(Y )/c(Y ) is a natural choice 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 crossentropy over the edges which implies we encourage a maximally different route from the optimal solution Ỹ and then report the optimality gap.

heading: 6 EMPIRICAL RESULTS
text: In this section, we show that the assessed SAT and TSP neural solvers are not robust w.r.t. small perturbations of the input despite the sound perturbation models introduced in § 4 and 5. We first discuss SAT in § 6.1 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 unless stated otherwise. 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 to the random baseline that randomly selects the perturbation s.t. the budget is exhausted. Moreover, for our attacks we use Adam (Kingma & Ba, 2015) and early stopping. For further details we refer to § E and § F.
6.1 SAT
1 5 50 Attack Steps
0.25
0.50
0.75
Ac cu
ra cy
Figure 3: SAT Attack on NeuroSAT
Setup. Following Selsam et al. (2019), 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 (Ignatiev et al., 2018; Sö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
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 to 40 variables. For our attacks, we use the budgets of ∆DEL = 5% as well as ∆SAT = 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.
0.01 0.05 0.10 Ratio of pert. literals
0.25
0.50
0.75
Ac cu
ra cy
Adv Rand
0 10 20 Message passing steps
0.5
1.0
Pr ob
ab ili
ty S
AT
Clean Pert.
Figure 5: NeuroSAT’s prediction over the message passing steps.
Difficulty imbalance. It 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 adversarial accuracy. Even with moderate budgets, we are able to lower the adversarial accuracy to values below 20% for satisfiable instances while for unsatisfiable instances we barely get below 50% even on the larger problem instances 50-100. An intuitive explanation is given by the fact that it is impossible to find a solution for an 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 a solution. Thus, it is even more remarkable how we are still able to fool the neural solver in 30% of the cases (DEL attack).
Qualitative insights. We show in Fig. H.1 how NeuroSAT’s decision evolves over the messagepassing steps for satisfiable instances. NeuroSAT comes to its conclusion typically after 15 messagepassing 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 a hard time doing so since it converges slower.
Attack budget. We study the influence of the budget ∆ and, hence, the similarity of x vs. x̃, in Fig. 4. It suffices to perturb 0.2% of the literals for the recall to drop below 50% using our SAT perturbation model. This stands in stark contrast to the random attack, where the accuracy for the satisfiable instances is almost constant over the plotted range of budgets.
Hard model-specific samples. The surprisingly weak performance (Fig. 2 and 4) of the random baselines shows how much more effective our attacks are and justifies their larger cost. Assuming that hard model-specific instances are the in-
stances that are important to improve the model’s performance, we can lower the amount of labeled data (potentially expensive). Of course, we cannot do anything about the NP-completeness 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 were expressive enough, we would now be able to leverage the adversarial examples for an improved training procedure. Therefore, similar to Jeddi et al. (2020), we perform an adversarial fine-tuning. That is, we 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 to 1% and perturb 5% of the training instances. For a fair comparison, we also compare to a model that was trained on a 10% larger training set. To compare the solvers’ capability to generalize for the different training strategies, we choose datasets of different problem sizes and also include the external benchmark datasets SATLIB and UNI3SAT (Hoos & Stü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 1.

heading: 6.2 TSP
text: Setup. In our setup we follow Prates et al. (2019) and generate the training data by uniformly sampling n ∼ U(20, 40) nodes/coordinates from the 2D unit square. This is converted into a fully connected graph where the edge weights represent the L2-distances between two points. A nearoptimal solution Y for training and attacks is obtained with the Concorde solver (Applegate et al., 2006). For the decision-variant of the TSP, we produce two samples from every graph: a graph with y = 1 and cost-query cy=10 = c(σ
∗) · (1 + d) and a second graph with y = 0 and cost-query cy=00 = c(σ
∗) · (1− d), where d = 2% (Prates et al., 2019). For predicting the TSP solution we use ConvTSP (Joshi et al., 2019) but keep the setup identical to its decision equivalent. We attack these models via adding five adversarial nodes and adjust c̃0 as well as Ỹ accordingly.
Decision TSP Solver. If a route of target cost exists, our attack successfully fools the neural solver in 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 Fig. 7, we see that the changes are indeed rather small and that the perturbations lead to practical problem instances.
Difficulty imbalance. For the TSP, we also observe an imbalance in performance between both classes. This is naturally explained with a look at the non-decision TSP version where a solver constructs a potential route Ŷ . Since c(Ŷ ) ≥ c(Y ) such a network comes with the optimal precision of 1 by design.
Attacking TSP Solver. For ConvTSP five new adversarial nodes suffice to exceed an optimality gap of 2%. Note that naive baselines such as 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 on the decision TSP. Even though the model performs better than DTSP, our attacks degrade the performance relatively by 10%. In Fig. 9, we can also view the predicted routes and observe that the prediction can differ severely between the clean and perturbed problem instance.
0.01
0.02
0.03
0.04
O pt
im al
ity G
ap
Route Prediction
Clean Rand Adv
0.75
0.80
0.85
0.90
Ac cu
ra cy
Route Exists
Figure 8: ConvTSP for problems with n = 20 nodes and five adversarial nodes. We plot the optimality gap (left) and the decision TSP performance (right).

heading: 7 RELATED WORK
text: Combinatorial Optimization. Important works about neural SAT solvers besides the ones already presented are (Amizadeh et al., 2019; Yolcu & Póczos, 2019; Kurin et al., 2019) and for neural TSP solvers (Khalil et al., 2017; Deudon et al., 2018; Bresson & Laurent, 2021; Wang et al., 2021; Bello et al., 2016; Kool et al., 2019). We refer to the recent surveys surveys (Bengio et al., 2021; Cappart et al., 2021; Vesselinova et al., 2020) for a detailed overview and discussion.
Generalization. There are only very view works on generalization of neural combinatorial solvers. One exception is Joshi et al. (2021). They empirically assess the impact of different model and training pipeline design choices on the generalization (for TSP) while we 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 propose a data augmentation technique relying on traditional solvers. Moreover, they study a hybrid model consisting of a simplified NeuroSAT 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.
Adversarial Robustness. Adversarial robustness has been studied in various domains including computer vision (Szegedy et al., 2014) and graphs (Zügner et al., 2018; Dai et al., 2018). We refer to Xu et al. (2020) for a broad overview of adversarial robustness in various domains. 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 L0-PGD by Xu et al. (2019) proposed in the context of GNNs.
Hard sample mining. Deriving adversarial examples might appear similar to hard sample mining (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, we only create randomly perturbed instances and their generation is not guided by the model. The surprisingly weak random baseline in our experiments gives an impression about how effective such an approach might be.

heading: 8 DISCUSSION
text: 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 our work is that the assessed neural combinatorial solvers are all sensitive 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 robustness. However, strong perturbations can still fool the model, indicating a lack of expressiveness. In summary, contemporary supervised neural solvers seem to be very fragile, and adversarial robustness is an insightful research direction to reveal as well as address neural solver deficiencies for combinatorial optimization.
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 a 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 a huge advantage over a possible real-world adversary that e.g. does not 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.

heading: A ACCURACY ROBUSTNESS TRADEOFF FOR COMBINATORIAL SOLVERS
text: 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 we 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 robustness s.t. there is provably no such trade-off in general classification tasks if either the dataset is “margin separable” or when we restrict the perturbation space to be label-preserving for a Bayes optimal classifier.
For combinatorial optimization with a sound perturbation model G we can argue both ways. First, due to the soundness we never encourage a wrong prediction (i.e. the margin condition is naturally fulfilled). This is contrast to e.g. image classification where an instance close to the decision boundary with the common Lp perturbation model ‖x− x̃‖p ≤ r changes its true label or becomes meaningless (e.g. a gray image) for a large enough r. Second, the Bayes optimal classifier for combinatorial optimization solves the optimization problem perfectly on p(x) (with support(p(x)) ⊆ X). For these reasons, we do not need to include the Bayes optimal classifier in the definition of the attack (Eq. 1).
More formally, we show by contradiction that any minimizer f∗ = arg minf∈FRadv,G(f) is optimal w.r.t. minf∈FR(f). Let f̂ be an optimal classifier w.r.t. R(f) for a combinatorial decision problem.
We assume the loss ` is equal for all possible optimal Y , to account for the multiple possible Y and define the adversarial risk
Radv,G(f) = Ex∼p(x) [
max x̃∈G(x,Y ) `(fθ(x̃), h(x̃,x, Y )) ] for any data distribution p(x) and the standard risk R(f) = Ex∼p(x) [`(fθ(x), Y )]. W.l.o.g. we assume the best possible risk is zero R∗ = 0 (i.e. the prediction is always true).
Suppose f∗ and f̂ differ in their prediction f∗(x) 6= f̂(x) over a non-empty subset of support(p(x)). Since f∗ is optimal and there is no stochasticity in the true label Y , it is always correct with standard risk R(f∗) = 0 and, analogously, Radv,G(f∗) = 0.
Thus, f̂ cannot be an optimizer of f̂ = arg minf∈FR(f) if its predictions differs over a non-empty subset of support(p(x)).
Note that this also holds for support(p(x)) ⊆ support(G(p(x))) ⊆ X which is indeed the interesting case for contemporary data generators and models.

heading: B PROOF OF PROPOSITION 1
text: Proposition 1 Let x = k1(v1, . . . , vn)∧ . . . km(v1, . . . , vn) be a boolean statement in Conjunctive Normal Form (CNF) with m clauses and n variables. Then x̃, a perturbed version of x, has the same label y = ỹ in the following cases:
• SAT: x is satisfiable y = 1 with truth assignment Y . Then, we can arbitrarily remove or add literals in x to obtain x̃, as long as one literal in Y remains in each clause.
• DEL: x is unsatisfiable y = 0 and we obtain x̃ from x through arbitrary removals of literals, as long as one literal per clause remains.
• ADC: x is unsatisfiable y = 0. Then, we can arbitrarily remove, add, or modify clauses in x to obtain x̃, as long as there remains a subset of clauses that is unsatisfiable in isolation.
W.l.o.g. we assume that an empty clause is true. That is, we evaluate the expression if the empty clauses were not there. Moreover, we assume to know one possible Y (multiple might exist).
• SAT: Every disjunctive clause evaluates to one, if one literal is true. Since we keep at least one literal in Y in 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 a disjunction of literals, the removal of one/some of the literals strictly reduces the number of specifiable assignments. That is, removing any literal li from its clause removes the possibility to satisfy this clause through li = 1.
• ADC: Since the clauses are a conjunctive, all clauses need to evaluate to true. If a subset of clauses it not satisfiable by themselves (i.e. not all can be true at the same time), the expression necessarily resolves to 0.
Hence, all conditions in Proposition 1 do not change the satisfiability y, but might alter Y . It is apparent that the updated Y can be obtained efficiently.

heading: C PROOF OF PROPOSITION 2
text: Proposition 2 Let σ∗ be the optimal route over the nodes V in G, let Z 6∈ V be an additional node, and X,Y are any two neighbouring nodes on σ∗. Then, the new optimal route σ̃∗ (including Z) is obtained from σ∗ through inserting Z between X and Y if 6 ∃ (A,B) ∈ V2 \ {(X,Y )} with A 6= B s.t. ω(A,Z) + ω(B,Z)− ω(A,B) ≤ ω(X,Z) + ω(Y,Z)− ω(X,Y ).
Corollary 1 We can add multiple nodes to G and obtain the optimal route σ̃∗ as long as the condition of Proposition 2 (including the other previously added nodes) is fulfilled.
Corollary 2 For the metric TSP, it is sufficient if the condition of Proposition 2 holds for (A,B) ∈ V2 \ ({(X,Y )} ∪ H) with A 6= B where H denotes the pairs of points both on the Convex Hull H ∈ CH(V)2 that are not a line segment of the Convex Hull.
Proof. We proof by contradiction. We define (L,P ) ∈ V2 \ {(X,Y )} to be the two neighboring nodes of Z on σ̃∗. Suppose ω(X,Z) + ω(Y,Z) − ω(X,Y ) < ω(L,Z) + ω(P,Z) − ω(L,P ) and σ̃∗ would not contain the edges ω(X,Z) as well as ω(Y,Z).
We know by optimality of σ∗ that
c(σ̃∗)− ω(L,Z)− ω(P,Z) + ω(L,P ) ≥ c(σ∗)
and by optimality of σ̃∗ that
c(σ∗) + ω(X,Z) + ω(Y, Z)− ω(X,Y ) ≥ c(σ̃∗).
Thus,
c(σ∗) + ω(X,Z) + ω(Y,Z)− ω(X,Y ) ≥ c(σ̃∗) ≥ c(σ∗) + ω(L,Z) + ω(P,Z)− ω(L,P )
and equivalently
ω(X,Z) + ω(Y, Z)− ω(X,Y ) ≥ ω(L,Z) + ω(P,Z)− ω(L,P )
which leads to a contradiction.
Since we do not know what edges are contained in σ̃∗ (i.e. what nodes could be L and P ) we state the stricter condition 6 ∃ (A,B) ∈ V2 \ {(X,Y )} with A 6= B s.t. ω(A,Z) +ω(B,Z)−ω(A,B) ≤ ω(X,Z) + ω(Y,Z)− ω(X,Y ). If multiple σ∗ exist, then this statement holds for any optimal route that has a direct connection between X and Y . Corollary 1 follows by induction and Corollary 2 is due to the fact that the in metric space the optimal route σ̃∗ 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 a direct consequence of the triangle inequality.

heading: D PROJECTED GRADIENT DESCENT (PGD)
text: Algorithm D.1: Projected Gradient Descent Data: Problem (x, Y ) and possibly y, Solver fθ(·),
Loss `, budget ∆, attack steps s, learn rate α 1 x̃0 ← initialize(x, Y,∆) 2 for t ∈ {0, 1, . . . , s− 1} do 3 x̃′t+1 ← update(x̃t, αt,∇`(fθ(x̃t), h(x̃,x, Y ))) 4 x̃t+1 ← project(x̃′t+1,x,∆) 5 end 6 x̃← postprocess(x̃E ,∆) 7 return x̃, h(x̃,x, Y )
All our attacks roughly match the framework of Algorithm algorithm D.1. First, we initialize the perturbed instance . Alternatively, we can use some variable that models the difference to the clean instance x (line 1). Initialization strategies that we consider are random initialization or initializing to the clean instance. Then we perform the attack for s steps and in each step update the perturbed instance through a gradient descent step (line 3). For faster convergence we additionally use Adam as optimizer (Kingma & Ba,
Table E.1: Hyperparameters for the attacks on NeuroSAT proposed in § 4
SAT DEL ADC
attack steps 500 500 500 learning rate 0.1 0.1 0.1
fraction of perturbed literals ∆ 5% of edges 5% of edges 25% of clauses # final samples 20 20 20
temperature scaling 5 5 5
2015). After the gradient update we perform a projection step that ensures we stay within the budget ∆ or satisfy other constraints. For simplicity, we omit the fact that we use early stopping in all our algorithms. Specifically, in each attack step we check if the current perturbed instance x̃t+1 comes with the best loss so far. Then, after s attack steps we assign the best possible x̃s ← arg maxt∈{1,...,s} `(fθ(x̃t), h(x̃t,x, Y )). This happens right before we (optionally) perform a postprocessing. Finally, we return the perturbed instance x̃ with solution Y or decision label y.
Limitations. As discussed in § 3, we require the model to be differentiable w.r.t. its input. Fortunately, most neural combinatorial solvers rely on GNNs and therefore this does not impose an issue. However, even if assessing a non-differentiable model one could revert to derivative-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 a graph that blows up quickly. Nevertheless, this could be done with derivative-free optimization (Yang & Long, 2021) or a scalable variant of of L0-PGD called projected randomized block coordinate descent (Geisler et al., 2021).

heading: E SAT ATTACK DETAILS
text: SAT model description. Selsam et al. (2019) propose to model the input problem as a bipartite graph as described in § 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 is 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 Selsam et al. (2019) did not publish their dataset we used a 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 we closely match the reported performance. For the larger train set in Table 1 we generate an additional 5,000 samples. During training we use the same hyperparameters as described in the paper. We make our code available to exactly reproduce the dataset.
Attack Details. The attack on SAT problems modifies the literals that are contained in clauses. This means specifically that we optimize over the edges represented by the literals-clauses adjacency matrix x = A ∈ {0, 1}2n×m. We implemented these attacks such that they can operate on batches of problems, however we omit this at this point in the following for an improved readability.
Algorithm algorithm E.1 describes in detail SAT and DEL (see Proposition 1). The difference of the adjacency matrix A to the adversarially perturbed version Ã is modelled via the perturbation matrix M : (x̃ = Ã = A ⊕M ). We then optimize over M . During the SAT attack, we allow deletions and additions of edges, as long as one solution-preserving truth assignment per clause, described by the indicator T = onehot(Y ), is preserved (line 7). For the DEL attack only deletions
are allowed, under the constraint that no clause can be fully deleted (lines 9 & 10). Additionally, a global budget is enforced (line 6). For details on the budget as well as other hyperparameters of the attack, we refer to Table E.1. For the ADC attack described in Algorithm E.2, the perturbation matrix M ∈ {0, 1}2n×m̃ describes additional clauses appended to the original problem (line 4). The attack can freely optimize over M but the number of literals/edges. ∆ is enforced s.t. on average each clause contains as many literals as a clause in A (line 6).
Because the attack optimizes over a set of discrete edges with a gradient based method, similarly to (Xu et 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 of 20 times but add an additional sample that chooses the top elements in M . Thereafter, we take the sample that maximizes the loss. Moreover, our projection differs slightly from the one proposed by Xu et al. (2019) since we iteratively enforce the budget instead of performing a bisection search.
Algorithm E.1: SAT & DEL Attack Data: Adjacency A ∈ {0, 1}2n×m,
edge budget ∆, steps s, learning rate α, solution T ∈ {0, 1}2n×m, SAT model fθ, label y
Result: Perturbed Adjacency Ã 1 Initialize M ← 02n×m, 2 for t ∈ {0, 1, . . . , s− 1} do 3 if y then Ã← A⊕M 4 else Ã← A−M 5 M ← update(M , α,∇`(fθ(Ã), y) 6 M ← project-budget(M ,∆) 7 if y then M ←M ∗ T 8 else 9 M ←M ∗A
10 M ← ensure-no-del(M ) 11 end 12 end 13 M ′ ← sample(M ) 14 Ã← A⊕M ′
Algorithm E.2: ADC Attack Data: Adjacency A ∈ {0, 1}2n×m,
clause budget ω, steps s, learning rate α, SAT model fθ
Result: Perturbed Adjacency Ã 1 Initialize M ← 02n×m̃, 2 ∆← avg(A, axis = 0) ∗ m̃ 3 for t ∈ {0, 1, . . . , s− 1} do 4 Ã←append(A,M ) 5 M ← update(M , α,∇fθ(Ã), y)) 6 M ← project-budget(M ,∆) 7 end 8 M ′ ← sample(M ) 9 Ã←append(A,M ′)
Computational complexity. All three attacks operate for s steps. Under the assumption that the models are linear w.r.t. the input matrix and the same it true for obtaining the gradient w.r.t. the input, each step has a time complexity of O(mn). Therefore, the overall attack has a time complexity of O(nms). Under the same assumption for the memory requirements of ∇M `, the total space complexity if O(nm).

heading: F TSP ATTACK DETAILS
text: For simplicity we only discuss the case of metric TSP. This is also what the used neural sovers are mainly intended for. The TSP attack is actually implemented in a batched fashion. However, for an improved readability we omit the details here. We refer to table Table F.1 for details on the attack hyperparameters.
DTSP model. The DTSP model employs a GNN to predict whether there exists a 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 a 3-layer MLP with the coordinates as 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 described in the paper and train on 220 graph samples. The graphs are generated by sampling from the unit square (x ∈ [0, 1]n×2) and solutions are obtained with the concorde solver (Applegate et al., 2006). Dual problem sets are built from
each graph for training, validation and test data by increasing and decreasing the true cost by a small factor.
ConvTSP model. The ConvTSP model aims at predicting the optimal route Y = σ over a given graph via a GCN (Joshi et al., 2019). It predicts a 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 is 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 an edge is present in the optimal solution. During training, the binary cross entropy between the target and the probability maps over the edges is minimized, and a solution-decoding technique is only applied during inference.
Attack details. The input of the TSP is represented by the coordinates x ∈ [0, 1]n×2 for the n nodes. Additionally, we know the near-optimal route Y obtained with the Concorde solver which we use as ground truth. During the TSP attack we add additional adversarial nodes Z ∈ [0, 1]∆×2 to the input problem x. The adversarial nodes are initialized by randomly sampling points until they fulfill the constraint from Proposition 2 (line 1). For the attack, as described in Algorithm F.1, we operate solely on the coordinates of the adversarial nodes and assume that the model converts the coordinates into a weighted graph. For the DTSP model, we additionally calculate the updated route cost c0 (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 is 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), we only consider the coordinates in Z that violate the constraint. As discussed in § 5.2, we perform gradient descent on the constraint due to its non-convexity. We decide against optimizing the Lagrangian since this would require evaluating the neural solver fθ and, therefore, is less efficient. For the projection, we update the adversarial node i that violates the constraint with
Zi ← Zi−η∇Zi [ ω(X,Zi) + ω(Y,Zi)− ω(X,Y )− ( min A,B∈x ω(A,Z) + ω(B,Z)− ω(A,B) )]
until the constrain is fulfilled again but for at most three consecutive steps.
Algorithm F.1: TSP Attack Data: Node Coords x ∈ [0, 1]n×2, steps s,
learning rate α, TSP model fθ, Adversarial Coords Z ∈ [0, 1]∆×2
Result: Perturbed Node Coords x̃ ∈ [0, 1](n+∆)×2
1 Initialize Z ← random-allowed-point() 2 for t ∈ {0, 1, . . . , s− 1} do 3 mask← is-constraint-fulfilled(Z,x) 4 x̃← append(x,Z[mask]) 5 Ỹ ← update-solution(x̃, Y ) 6 Z ← update(Z, α,∇`(fθ(W ), Ỹ )) 7 Z ← project(Z,x); 8 end 9 return x̃, Ỹ
Computational complexity. We again assume that the model has a linear time and space complexity. This time it is linear w.r.t. the O(n2) number of elements in the distance matrix between the input coordinates. The most costly operation we add is the check if the constraint is violated or not. This operation has a time and space complexity of O(n2) since we need to evaluate the distances to all nodes (except the special case where both nodes are on the convex hull but are 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(n2) and the time complexity is O(n2s) with the number of attack steps s.
Table F.1: Hyperparameters for the attacks on TSP proposed in § 5
DTSP ConvTSP
maximum number of adv. nodes ∆ 5 5 attack steps 200 500 learning rate 0.001 0.01
gradient project learning rate 0.002 0.002 gradient project steps 3 3
Table G.1: Runtime in milliseconds for the Glucose and MiniSAT solver on 100 clean and perturbed problem instances from 50-100
Perturbed DEL ADC SAT
Glucose 0.1897 ± 0.20 0.1944 ± 0.13 0.1315 ± 0.06 X 0.0335 ± 0.03 0.0816 ± 0.11 0.1391 ± 0.08 MiniSAT 0.1351 ± 0.07 0.1510 ± 0.11 0.0980 ± 0.05 X 0.0189 ± 0.02 0.0587 ± 0.09 0.1383 ± 0.31

heading: G OFF-THE-SHELF SAT SOLVERS: TIME COST OF PERTURBED INSTANCES
text: Comparison SAT Solvers. We test two SAT-solver’s runtime on all attacks for both clean an perturbed samples from the 50-100 dataset to better understand the difficulty of the samples for nonneural SAT solvers. Table G.1 shows the mean as well as the standard deviation of the Glucose (Audemard & Simon, 2009) as well as the MiniSAT (Sörensson & Een, 2005) solver. The results suggest that both solvers can more quickly find that a sample is unsatisfiable for perturbed samples from both the DEL and the ADC attacks. For perturbed satisfiable samples, the runtime increases compared to the clean sample for the MiniSAT solver while Glucose solver needs about the same time as for the clean sample to find a solution.

heading: H CONVERGENCE NEUROSAT
text: Complementary to Fig. H.1, we also present the convergence for 100 randomly chosen satisfiable instances from the 10-40 dataset. We see that the observations drawn from Fig. H.1 also hold here: (1) rarely an instance is predicted as SAT despite the moderate budget of perturbing 5% of the literals and (2) if NeuroSAT identifies the sample as satisfiable it requires more message passing steps to do so.
0 5 10 15 20 25 Message Passing Steps
0.0
0.5
1.0
Pr ob
ab ili
ty S
AT Clean Perturbed
Figure H.1: Clean vs. perturbed: NeuroSAT’s prediction over the message passing steps.

heading: I EFFICIENCY NEUROSAT ATTACKS
text: 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 in Fig. I.1. The indicated number of gradient update steps s are taken during
the attack, while retaining the learning rate from Table E.1 and early stopping on an instance level. The results in Fig. I.1 show that only 1 gradient update step suffices for the SAT attack to decrease the accuracy from 79% to 26%. Compared to the results from Fig. 2, where the random attack draws a single sample and only decreases the accuracy to 74%, the importance of the guidance through the gradient update becomes apparent. For the DEL attack on the NeuroSAT model, the attack strength converges around 200 steps, showing again the imbalance between the labels with regards to how many misclassifications the attack can force.
Table I.1: Number of random samples to match optimized loss
∆ = 0.01 0.05
SAT 1257 9532 DEL 749 4854
In Table I.1 we 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 ∆ = 0.01 and ∆ = 0.05.
We can observe that the additional computational cost of generating adversarial samples is justified, given the random baseline performs 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 in terms of sample efficiency. There are several other aspects to consider, like additional computational and storage overhead for a larger, denser dataset or to what extent a larger dataset of random or adversarial examples can improve generalization.

heading: J QUALITATIVE RESULTS TSP
text: In this section we complement the figures Fig. 7 and Fig. 9 with further examples. In Fig. J.1, we plot further examples for the attack on DTSP and further examples for ConvTSP in Fig. J.2.
(a) (b) (c)
Figure J.1: Examples of the optimal route Y and perturbed routes Ỹ for DecisionTSP.
Concorde Perturbed Clean Adv. Points
(a) (b) (c)
(d) (e) (f)
Figure J.2: Exemplary problem instances where the attack successfully changed the optimal route for ConvTSP that show drastic changes of the prediction.

Review summaries:
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.

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.