Learning What to Defer for Maximum Independent Sets
Authors: Sungsoo Ahn, Younggyo Seo, Jinwoo Shin
ICML 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We empirically validate Lw D on various types of graphs including the Erd os-R enyi (Erd os & R enyi, 1960) model, the Barab asi-Albert (Albert & Barab asi, 2002) model, the SATLIB (Hoos & St utzle, 2000) benchmark and real-world graphs. Our algorithm shows consistent superiority over the existing state-of-the-art DRL method (Khalil et al., 2017). Remarkably, it often outperforms the state-of-the-art MIS solver (Ka MIS, Hespe et al., 2019a), particularly on large-scale graphs |
| Researcher Affiliation | Academia | 1School of Electrical Engineering, Korea Advanced Institute of Science and Technology (KAIST), Daejeon, South Korea 2Graduate School of AI, KAIST, Daejeon, South Korea. |
| Pseudocode | No | The paper describes the proposed algorithm's components (state, action, transition, reward) and training (PPO, Graph SAGE), but it does not include a structured pseudocode or algorithm block. |
| Open Source Code | No | The paper does not provide any concrete access to source code, such as a specific repository link, an explicit code release statement, or mention of code in supplementary materials. |
| Open Datasets | Yes | Specifically, we consider the models proposed by Erd os R enyi (ER, Erd os & R enyi, 1960), Barab asi-Albert (BA, Albert & Barab asi, 2002), Holme and Kim (HK, Holme & Kim, 2002), and Watts-Strogatz (WS, Watts & Strogatz, 1998). Next, we consider real-world graph datasets, namely the SATLIB, PPI, REDDIT, as-Caida, Citation, Amazon, and Coauthor datasets constructed from the SATLIB benchmark (Hoos & St utzle, 2000), protein-protein interactions (Hamilton et al., 2017), social networks (Yanardag & Vishwanathan, 2015), road networks (Leskovec & Sosiˇc, 2016), co-citation network (Yang et al., 2016), copurchasing network (Mc Auley et al., 2015), and academic relationship network (Sen et al., 2008), respectively. |
| Dataset Splits | No | The paper mentions "validation scores" in the ablation study but does not provide specific details about the dataset splits (percentages, sample counts, or explicit methodology) for training, validation, and testing across its various experiments. |
| Hardware Specification | Yes | We perform every experiment using a single GPU (NVIDIA RTX 2080Ti) and a single CPU (Intel Xeon E5-2630 v4). |
| Software Dependencies | No | The paper mentions using Graph SAGE architecture and Proximal Policy Optimization (PPO) but does not provide specific version numbers for these software libraries or any other ancillary software used in their implementation. |
| Experiment Setup | No | The paper describes general aspects of the training process (e.g., actor-critic, Graph SAGE, PPO, input features) but does not specify concrete hyperparameters like learning rates, batch sizes, number of epochs, or optimizer settings. |