Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness

Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski, Stephan Günnemann

Abstract

End-to-end deep learning has shown promise in approximating solutions for NP-hard combinatorial optimization (CO) problems. However, current evaluation protocols are often overly optimistic because datasets typically capture only simple subproblems and suffer from spurious features. This paper investigates these effects through the lens of adversarial robustness. We derive sound and efficient perturbation models for Boolean Satisfiability (SAT) and the Traveling Salesperson Problem (TSP) that allow for determining true labels without a solver. Our findings reveal that while robust neural solvers can theoretically exist without the typical accuracy-robustness trade-off, current models are highly fragile and fail to generalize to small, mathematically valid perturbations.

Introduction: The Evaluation Gap in Combinatorial Optimization

Combinatorial Optimization problems like SAT and TSP are fundamental to computer science but remain computationally expensive to solve exactly. Recent efforts have turned to Graph Neural Networks (GNNs) to approximate solutions quickly. However, a significant "Catch-22" exists in training these models: generating large datasets requires either fast generators that produce "easy" instances or exact solvers that are exponentially slow.

Conceptual illustration of the evaluation gap. Standard datasets (right) are sparse, allowing models to learn spurious features that do not generalize to the full perturbation space.

As a result, neural solvers often learn spurious features—superficial shortcuts that work on training data but fail to capture the underlying logic. Because test sets are generated using the same methods as training sets, this lack of generalization remains hidden. This research addresses this gap by introducing adversarial robustness to CO, testing whether models truly understand the problem or are simply exploiting dataset biases.

Methodology: Sound and Efficient Perturbations

To test robustness, one must perturb an input and verify the model's response. In CO, however, changing the input usually changes the optimal solution, necessitating a slow exact solver to find the new ground truth. The authors bypass this by designing sound and efficient perturbation models:

  • SAT Perturbations: The authors define logical rules for adding or removing literals and clauses. For instance, in a Satisfiable problem, literals can be modified as long as the specific literals satisfying the statement remain untouched. They employ a relaxed gradient descent method ($L^0$-PGD) to identify the specific allowed changes that most confuse the model.
  • TSP Perturbations: A geometric rule is introduced for adding nodes to a 2D map. If a new node is placed within a specific boundary relative to an existing optimal edge, the new optimal route is guaranteed to simply absorb that node without further rerouting. Gradient descent is used to place these nodes in locations that maximize model error.

Results: Exposing the Illusion of Competence

The empirical results demonstrate a stark contrast between standard test accuracy and adversarial robustness. For deterministic CO problems, the authors argue there is no inherent accuracy-robustness trade-off; a perfect solver should be both 100% accurate and 100% robust. Current models, however, fall far short of this ideal.

Accuracy of NeuroSAT on clean vs. perturbed instances. Adversarial attacks (orange) cause a dramatic performance drop compared to random perturbations (teal) across different problem sizes.

Fragility and Asymmetry

Modifying just 0.2% to 5% of the literals in a SAT problem causes the NeuroSAT model's accuracy on satisfiable instances to plummet from approximately 89% to below 20%. Often, a single gradient update is sufficient to flip the model's prediction. Furthermore, models exhibit an asymmetric bias, finding it significantly harder to recognize perturbed "Satisfiable" instances than "Unsatisfiable" ones.

In TSP tasks, injecting just five adversarial nodes into a 20-node graph fooled decision-TSP solvers in most cases. For route prediction, these attacks increased the optimality gap by over 2%, causing neural networks to perform worse than simple traditional heuristics.

Adversarial Training

Because generating hard CO data is expensive, adversarial attacks serve as an efficient data augmentation strategy. Fine-tuning NeuroSAT with adversarial examples for just 10 epochs significantly improved robust accuracy (e.g., from 39.4% to 44.4% on larger datasets) and enhanced the model's ability to generalize to entirely different problem sizes.

Conclusion and Future Work

The fragility of current neural solvers suggests a fundamental lack of expressiveness in existing GNN architectures for solving NP-hard problems. While adversarial training provides a path forward, the authors propose that adversarial robustness should become a standard evaluation metric. Only by testing against targeted perturbations can we ensure that neural solvers are learning actual algorithms rather than exploiting narrow dataset biases.

Summary updated

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.
BibTeX
@inproceedings{geisler2022generalization,
  author = {Simon Geisler and Johanna Sommer and Jan Schuchardt and Aleksandar Bojchevski and Stephan Günnemann},
  title = {{Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=vJZ7dPIjip3},
}
Figure