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硬/完成的任务领域生成数据带来了实际和理论的挑战,导致评估规程过于乐观。具体地说,大多数数据集只捕捉一个简单的次问题,并可能存在虚假特征。我们通过研究对抗性强力(一个局部的概括性属性)来调查这些影响,以揭示硬性、模式性的具体实例和虚假特征。为此目的,我们为SAT和TSP制作了扰动模型。与其他应用程序不同,在这种应用程序中,干扰模型是围绕不易感性主观概念设计的,我们的扰动模型是高效和健全的,使我们能够在没有解答器的情况下确定扰动性样品的真实标签。奇怪的是,由于这种扰动性,足够直观的神经解析器并不因监管性学习中常见的精确性交错的局限性而受到损害。尽管存在这种强健的解决方案,但我们从经验学中展示出,评估神经解质的模型并没有普遍化。