Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness
Authors: Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski, Stephan Günnemann
ICLR 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section, we show that the assessed SAT and TSP neural solvers are not robust w.r.t. small perturbations of the input using the sound perturbation models introduced in 4 and 5. We first discuss SAT in 6.1 and then TSP in 6.2. We run the experiments for at least five randomly selected seeds. We compare the accuracy on the clean and perturbed problem instances (i.e. clean vs. adversarial accuracy). |
| Researcher Affiliation | Academia | Simon Geisler1 , Johanna Sommer1 , Jan Schuchardt1, Aleksandar Bojchevski2, Stephan G unnemann1 {geisler, sommer, schuchaj, guennemann}@in.tum.de | bojchevski@cispa.de 1Department of Informatics & Munich Data Science Institute, Technical University of Munich 2CISPA Helmholtz Center for Information Security |
| Pseudocode | Yes | Algorithm D.1: Projected Gradient Descent; Algorithm E.1: SAT & DEL Attack; Algorithm E.2: ADC Attack; Algorithm F.1: TSP Attack |
| Open Source Code | Yes | We provide the source code and configuration for the key experiments including instructions on how to generate data and train the models. All proofs are stated in the appendix with explanations and underlying assumptions. We thoroughly checked the implementation and also verified empirically that the proposed sound perturbation models hold. ... code https://www.daml.in.tum.de/robustness-combinatorial-solvers. |
| Open Datasets | Yes | Following Selsam et al. (2019), we train Neuro SAT for 60 epochs using the official parameters and data generation. The random data generator for the training/validation data greedily adds clauses until the problem becomes unsatisfiable which is determined by an exact SAT solver (Ignatiev et al., 2018; S orensson & Een, 2005). ... We also include the external benchmark datasets SATLIB and UNI3SAT (Hoos & St utzle, 2000). |
| Dataset Splits | No | The paper mentions generating training, validation, and test data, and training on a specific number of samples (e.g., 50,000 for Neuro SAT) but does not provide explicit proportions (e.g., 80/10/10 split) or sample counts for training, validation, and test sets. For instance, for TSP, it states: "Dual problem sets are built from each graph for training, validation and test data by increasing and decreasing the true cost by a small factor.", but no specific split details are given. |
| Hardware Specification | No | The paper does not explicitly describe the specific hardware (e.g., GPU models, CPU types, memory) used to run the experiments. |
| Software Dependencies | No | The paper mentions using several software components like PySAT, Concorde solver, Glucose, Mini SAT, and Adam optimizer, but it does not specify concrete version numbers for these software dependencies, which is required for full reproducibility. |
| Experiment Setup | Yes | We use the published hyperparameters by the respective works for training the models. ... We train Neuro SAT for 60 epochs using the official parameters and data generation. ... Additionally, we use Adam (Kingma & Ba, 2015) and early stopping for our attacks. For our attacks, we use the budgets of DEL = 5% as well as SAT = 5% relatively to the number of literals in x and for ADC we add an additional 25% of clauses and enforce the average number of literals within the new clauses. ... Table E.1: Hyperparameters for the attacks on Neuro SAT proposed in 4 (attack steps 500, learning rate 0.1, fraction of perturbed literals 5% of edges, # final samples 20, temperature scaling 5). ... Table F.1: Hyperparameters for the attacks on TSP proposed in 5 (maximum number of adv. nodes 5, attack steps 200/500, learning rate 0.001/0.01, gradient project learning rate 0.002/0.002). |