Maximum Independent Set: Self-Training through Dynamic Programming
Authors: Lorenzo Brusca, Lars C.P.M. Quaedvlieg, Stratis Skoulakis, Grigorios Chrysos, Volkan Cevher
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly constructs two smaller sub-graphs, predicts the one with the larger MIS, and then uses it in the next recursive call. To train our algorithm, we require annotated comparisons of different graphs concerning their MIS size. Annotating the comparisons with the output of our algorithm leads to a self-training process that results in more accurate self-annotation of the comparisons and vice versa. We provide numerical evidence showing the superiority of our method vs prior methods in multiple synthetic and real-world datasets. |
| Researcher Affiliation | Academia | École Polytechnique Fédérale de Lausanne, Switzerland {[first name].[last name]}@epfl.ch |
| Pseudocode | Yes | Algorithm 1 Randomized Comparator-Induced Algorithm |
| Open Source Code | Yes | The code for the experiments and models discussed in this paper is available at: https://github. com/LIONS-EPFL/dynamic-MIS. |
| Open Datasets | Yes | We evaluate our model on three standard datasets, following Karalias and Loukas [2020]: COLLAB [Yanardag and Vishwanathan, 2015], TWITTER [Leskovec and Krevl, 2014] and RB [Xu et al., 2007, Toenshoff et al., 2019]. In addition, we introduce the SPECIAL dataset that includes challenging graphs for handcrafted approaches as we detail in Appendix C. |
| Dataset Splits | Yes | We split the graph datasets into 80% for training and 20% for testing, except for COLLAB and RB datasets where the number of test graphs is much bigger than the number of train graphs. From the training data, a validation set is constructed by dedicating 20% of the data in the buffer to it. |
| Hardware Specification | Yes | Any experiment with a reported execution time has been performed on a laptop with Windows 10 and Python 3.10. The device uses a CUDA-enabled NVIDIA Ge Force GTX 1060 Max-Q GPU with 6GB VRAM, and an Intel(R) Core(TM) I7-7700HQ CPU with a 2.80GHz clock speed, and 16GB of RAM. Our method is implemented in Py Torch. |
| Software Dependencies | Yes | Any experiment with a reported execution time has been performed on a laptop with Windows 10 and Python 3.10. The device uses a CUDA-enabled NVIDIA Ge Force GTX 1060 Max-Q GPU with 6GB VRAM, and an Intel(R) Core(TM) I7-7700HQ CPU with a 2.80GHz clock speed, and 16GB of RAM. Our method is implemented in Py Torch. |
| Experiment Setup | Yes | Training setup: The sizes of the linear layers at each iteration are as follows: 96 32, 96 32, and 96 32. After this module, 4 linear layers follow, with the following sizes: 96 32, 32 32, 32 32, and 64 1. Furthermore, the output of the last GEM iteration has a skip connection into the last dense layer of the model, which is also why the final layer has 64 input neurons. Every linear layer in the entire network is followed by layer normalization [Ba et al., 2016b]. Each model is trained for 300 epochs total with batch size 32 using Adam optimizer [Kingma and Ba, 2014] and a learning rate of 0.001. We split the graph datasets into 80% for training and 20% for testing, except for COLLAB and RB datasets where the number of test graphs is much bigger than the number of train graphs. From the training data, a validation set is constructed by dedicating 20% of the data in the buffer to it. Considering the baseline methods, we trained them for 300 epochs, and in the case of reinforcement learning, for 300 episodes. A precise description of the Hyper-parameters values is reported in Table 3. |