# Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness

arXiv: https://arxiv.org/abs/2110.10942 · HTML: https://mlsanity.com/paper/2110.10942/

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 45 references that are in the map.
- First posted on arXiv 21 Oct 2021.

## Builds on (most cited first, 27 of 27)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Adversarial Attacks and Defenses in Images, Graphs and Text: A Review](https://mlsanity.com/paper/1909.08072/) (2019)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Disentangling Adversarial Robustness and Generalization](https://mlsanity.com/paper/1812.00740/) (2018)
- [Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking](https://mlsanity.com/paper/2005.11081/) (2020)
- [Guiding High-Performance SAT Solvers with Unsat-Core Predictions](https://mlsanity.com/paper/1903.04671/) (2019)
- [The Transformer Network for the Traveling Salesman Problem](https://mlsanity.com/paper/2103.03012/) (2021)
- [Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSP](https://mlsanity.com/paper/1809.02721/) (2018)
- [A Simple Fine-tuning Is All You Need: Towards Robust Deep Learning Via Adversarial Fine-tuning](https://mlsanity.com/paper/2012.13628/) (2020)
- [It's Not What Machines Can Learn, It's What We Cannot Teach](https://mlsanity.com/paper/2002.09398/) (2020)
- [A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2106.04927/) (2021)
- [Can Q-Learning with Graph Networks Learn a Generalizable Branching Heuristic for a SAT Solver?](https://mlsanity.com/paper/1909.11830/) (2019)
- [Revisiting Adversarial Risk](https://mlsanity.com/paper/1806.02924/) (2018)
- [How to Evaluate Machine Learning Approaches for Combinatorial Optimization: Application to the Travelling Salesman Problem](https://mlsanity.com/paper/1909.13121/) (2019)

## Built on by (most cited first, 30 of 35)

- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Attacking Large Language Models with Projected Gradient Descent](https://mlsanity.com/paper/2402.09154/) (2024)
- [BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization](https://mlsanity.com/paper/2301.03313/) (2023)
- [MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts](https://mlsanity.com/paper/2405.01029/) (2024)
- [Towards Omni-generalizable Neural Methods for Vehicle Routing Problems](https://mlsanity.com/paper/2305.19587/) (2023)
- [Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation](https://mlsanity.com/paper/2210.07686/) (2022)
- [Pareto Set Learning for Neural Multi-objective Combinatorial Optimization](https://mlsanity.com/paper/2203.15386/) (2022)
- [Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalization](https://mlsanity.com/paper/2402.16891/) (2024)
- [Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization](https://mlsanity.com/paper/2502.02941/) (2025)
- [Transformers Meet Directed Graphs](https://mlsanity.com/paper/2302.00049/) (2023)
- [Are Defenses for Graph Neural Networks Robust?](https://mlsanity.com/paper/2301.13694/) (2023)
- [Rethinking Light Decoder-based Solvers for Vehicle Routing Problems](https://mlsanity.com/paper/2503.00753/) (2025)
- [Learning to Handle Complex Constraints for Vehicle Routing Problems](https://mlsanity.com/paper/2410.21066/) (2024)
- [Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directions](https://mlsanity.com/paper/2306.15427/) (2023)
- [Cross-Problem Learning for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2404.11677/) (2024)
- [CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention](https://mlsanity.com/paper/2412.00346/) (2024)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Pareto Set Learning for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2501.06773/) (2025)
- [Revisiting Robustness in Graph Machine Learning](https://mlsanity.com/paper/2305.00851/) (2023)
- [REINFORCE Adversarial Attacks on Large Language Models: An Adaptive, Distributional, and Semantic Objective](https://mlsanity.com/paper/2502.17254/) (2025)
- [Promoting Generalization for Exact Solvers via Adversarial Instance Augmentation](https://mlsanity.com/paper/2310.14161/) (2023)
- [Collaboration! Towards Robust Neural Methods for Routing Problems](https://mlsanity.com/paper/2410.04968/) (2024)
- [Machine Learning Insides OptVerse AI Solver: Design Principles and Applications](https://mlsanity.com/paper/2401.05960/) (2024)
- [Efficient Training of Multi-task Neural Solver for Combinatorial Optimization](https://mlsanity.com/paper/2305.06361/) (2023)
- [SafePowerGraph: Safety-aware Evaluation of Graph Neural Networks for Transmission Power Grids](https://mlsanity.com/paper/2407.12421/) (2024)
- [Learning to Segment for Vehicle Routing Problems](https://mlsanity.com/paper/2507.01037/) (2025)
- [Adaptive Stabilization Based on Machine Learning for Column Generation](https://mlsanity.com/paper/2405.11198/) (2024)
- [Towards Efficient Constraint Handling in Neural Solvers for Routing Problems](https://mlsanity.com/paper/2602.16012/) (2026)
- [CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimization](https://mlsanity.com/paper/2602.08210/) (2026)
- [Chain-of-Context Learning: Dynamic Constraint Understanding for Multi-Task VRPs](https://mlsanity.com/paper/2603.01667/) (2026)

## Abstract (arXiv)

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.