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.
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.
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