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.

研究人员通过学习对抗鲁棒性，研究NP难/ NP完全问题的解决方案的几何深度学习。他们利用SAT和TSP的扰动模型，并研究了局部泛化属性以揭示困难的，与模型特定的实例和虚假特征有关的因素。最终，他们表明了被评估的神经解算器在小的问题实例扰动上没有很好地泛化。

神经组合求解器的广义：从对抗鲁棒性的角度探究