Variational Annealing on Graphs for Combinatorial Optimization
Authors: Sebastian Sanokowski, Wilhelm Berghammer, Sepp Hochreiter, Sebastian Lehner
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We evaluate VAG-CO on various CO problems that are studied in the recent literature. Additionally, we evaluate VAG-CO on synthetic datasets where solving the corresponding CO problem is known to be particularly hard. Finally, we discuss experiments on the impact of entropy regularization and subgraph tokenization. |
| Researcher Affiliation | Academia | Sebastian Sanokowski1,2 Wilhelm Berghammer2 Sepp Hochreiter1,2 Sebastian Lehner1,2 1 ELLIS Unit Linz and LIT AI Lab 2 Institute for Machine Learning, Johannes Kepler University Linz, Austria sanokowski@ml.jku.at |
| Pseudocode | No | The paper describes the 'Autoregressive Solution Generation' procedure in numbered steps but these are textual descriptions, not structured pseudocode or algorithm blocks. |
| Open Source Code | Yes | Our code is available at: https://github.com/ml-jku/VAG-CO. |
| Open Datasets | Yes | In the MIS problem the task is to find the largest subset of independent, i.e. unconnected, nodes in a graph. As an optimization objective for VAG-CO we use Eq. 2 with the Ising energy function for MIS (see Tab. 1). Here, the energy function Epqq consists of two terms EApqq and EBpqq, that depend on the binary representation of the solution q σ 1 2 with q P t0, 1u N. When qi 1 the corresponding node is defined to be included in the set and it is excluded otherwise. The first term EApqq is proportional to the number of nodes that are in the set, whereas EBpqq is proportional to the number of independence violations, i.e. the number of connected nodes within the set. By selecting A, B P R such that A ă B we ensure that all minima satisfy EB 0 since in this case excluding a violating node from the set always reduces the energy. In our experiments, we choose A 1.0 and B 1.1. We follow the procedure of [Karalias et al., 2022] and use a 0.6{0.1{0.3 train/val/test split on the aforementioned datasets and use only the first 1000 graphs on the COLLAB dataset. The results |
| Dataset Splits | Yes | We follow the procedure of [Karalias et al., 2022] and use a 0.6{0.1{0.3 train/val/test split on the aforementioned datasets and use only the first 1000 graphs on the COLLAB dataset. |
| Hardware Specification | Yes | All runs with VAG-CO were conducted either on A100 Nvidia GPU with 40 GB Memory or an A40 Nvidia GPUs with 48 GB Memory. In case of COLLAB MVC an A100 with 80 GB Memory is used. |
| Software Dependencies | No | The paper mentions using PPO, GNNs, MLPs and states that Gurobi version 10.0.0 was used for baseline comparisons. However, it does not provide specific version numbers for the software libraries or frameworks used to implement their own methodology (e.g., PyTorch, TensorFlow, etc.). |
| Experiment Setup | Yes | For MFA-Anneal we used a learning rate of 1 ˆ 10 4, 2000 annealing steps Nanneal and a start temperature T0 of 0.1 except for RRG-100 MIS and for RB-200 MVC. In RRG-100 MIS a T0 of 0.015 is used and in RB-200 MVC T0 0.05. For MFA with and without annealing we trained for 2000 epochs and used a learning rate of 5 ˆ 10 5 except for ENZYMS MIS and RB-200 MVC, where a learning rate of 1 ˆ 10 4 is used. All runs with MFA used a batch size H of 32 and we sampled n S 30 solutions. Furthermore, we used 8 GNN layers, and 6 random node features per node. In the RB-200 MVC experiment 10 GNN layers were used. In our experiments we always chose ϵ 0.1, c V 0.5 and nrepeat 2. On VAG-CO we iteratively tuned the learning rate (lr P r5 10 4, 1 10 3s), initial temperature (T0 P r0.05, 0.7, 0.1s), number of GNN layers (L P r3, 4s) and number of annealing steps (Nanneal P r3000, 6000s) on the ENZYMES MIS validation dataset. We then initially test these hyperparameters on other datasets and adapt the number of annealing steps and the initial temperature. The choice of all hyperparameters in VAG-CO is listed in Tab. 7. |