Introduction
End-to-end geometric deep learning has seen initial success in approximating solutions for combinatorial optimization (CO) problems like the Traveling Salesperson Problem (TSP) or Boolean Satisfiability (SAT). However, neural combinatorial solvers are surprisingly fragile. They often rely on "spurious features" present in their training data rather than learning the underlying logic of the NP-hard tasks. By introducing "sound" adversarial perturbations—where the true solution remains known without needing an exact solver—researchers demonstrate that current models fail on slightly modified instances but can be significantly improved through adversarial training.
The Data Generation "Catch-22"
Training deep learning models for CO problems faces a fundamental "Catch-22" regarding data generation:
- Incomplete Generators: Efficiently generating data often results in "easy" subproblems. These datasets contain statistical shortcuts or spurious features that do not exist in real-world, hard instances.
- Inefficient Solvers: Using exact, traditional solvers to label truly random or hard instances is computationally prohibitive for the large scales required by deep learning.
Because of this dynamic, standard evaluation protocols are often too optimistic. A model might achieve 90% accuracy on a test set simply because it learned the "fingerprint" of the data generator, not because it understands how to solve the actual NP-hard problem. This paper uses adversarial robustness as a lens to expose these weaknesses, revealing hard, model-specific instances and measuring true generalization.
Sound and Efficient Perturbation Models
The authors propose a framework for adversarial attacks specifically tailored to neural CO solvers. The core innovation is the use of sound and efficient perturbation models.
In typical computer vision attacks, we assume a small change (like adding imperceptible noise to pixels) doesn't change the image's label. In CO, however, even a tiny change can flip the answer from "satisfiable" to "unsatisfiable." To avoid needing a slow, exact solver during the attack loop, the authors derived mathematical proofs for specific perturbations where the new label is guaranteed:
- For SAT: They developed rules for adding or removing literals and clauses such that a "Satisfiable" instance stays satisfiable (e.g., by preserving at least one true literal per clause) or an "Unsatisfiable" instance stays unsatisfiable.
- For TSP: They proved conditions under which adding a new node to a graph guarantees that the new optimal tour is simply the old tour with the new node inserted between two specific neighbors.
Using Projected Gradient Descent (PGD), the framework finds the "worst-case" versions of these sound perturbations that most confuse the neural network.
Key Insights: Fragility and the Accuracy-Robustness Trade-off
A major finding of this work is the absence of the standard accuracy-robustness trade-off. In standard machine learning, making a model robust often slightly lowers its clean accuracy. The authors argue that in CO, this trade-off shouldn't exist: a perfect solver is perfectly robust by definition. If a model is expressive enough, robustness and accuracy should improve together.
However, current state-of-the-art neural solvers exhibit extreme fragility.
- NeuroSAT Failure: On a 10-40 variable SAT dataset, adversarial attacks dropped model accuracy from approximately 80% to 20%, whereas random perturbations had almost no effect. Perturbing just 0.2% of the literals caused the recall to drop below 50%.
- Difficulty Imbalance: It is much easier to "fool" a model into thinking a satisfiable SAT instance is unsatisfiable than the reverse. This suggests models struggle to truly "find" the satisfying assignment, relying instead on global graph properties.
- TSP Optimality Gap: For the ConvTSP model, adding just 5 adversarial nodes increased the "optimality gap" (how much longer the predicted route is than the perfect route) significantly, making it perform worse than simple non-neural heuristics.
Adversarial Training as a Path Forward
By training on these hard, model-specific adversarial examples, the models become more robust and generalize better to completely different datasets. For instance, adversarial training improved NeuroSAT's performance on the external UNI3SAT benchmark from 86.0% to 86.9%, and on larger 100-300 variable instances from 64.4% to 67.0%. This proves that robustness directly leads to better "real" solving capability.
Limitations and Future Work
While promising, the approach has limitations. The current attack requires the neural solver to be differentiable (like Graph Neural Networks). Attacking non-differentiable models would require more complex black-box optimization. Furthermore, the "sound" perturbations are mathematically restricted to ensure the label is known; there may be other types of adversarial examples outside this scope. Finally, while adversarial training helps, very strong perturbations can still fool the models, suggesting that current GNN architectures may still lack the raw expressiveness needed to fully capture NP-hard logic.
Summary updated