LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation
Authors: David Ireland, Giovanni Montana
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | When tested on three problems (vertex cover, max-cut and influence maximisation) using real graphs with up to 10 million edges, Le NSE identifies small subgraphs yielding solutions comparable to those found by running the heuristics on the entire graph, but at a fraction of the total run time. Experimentally we test Le NSE on three well-know CO problems using established heuristics. Our extensive experimental results demonstrate that Le NSE is capable of removing large parts of the graph, in terms of both vertices and edges, without any significant degradation to the performance compared to performing no pruning at all, but at a fraction of the overall run time. |
| Researcher Affiliation | Academia | 1Warwick Manufacturing Group, University of Warwick, Coventry, United Kingdom 2Department of Statistics, University of Warwick, Coventry, United Kingdom. |
| Pseudocode | Yes | Algorithm 1 Le NSE with Guided Exploration |
| Open Source Code | Yes | Code for the experiments is available in the public Git Hub repo at https: //github.com/davidireland3/Le NSE. |
| Open Datasets | Yes | Each problem is tested using eight real-world graphs obtained from the Snap-Stanford repository (Leskovec & Krevl, 2014). All datasets can be found at http://snap.stanford.edu/data/index.html. |
| Dataset Splits | No | The paper describes train and test splits, stating 'For each graph, we randomly sample a percentage of the graphs edges to form a training graph, with testing then done on the graph formed from the held out edges'. However, it does not explicitly mention a separate validation dataset split. |
| Hardware Specification | No | The paper does not provide specific details about the hardware used to run the experiments, such as GPU models, CPU types, or memory specifications. |
| Software Dependencies | No | The paper mentions software components like 'Adam optimiser' and specific types of layers ('Graph SAGE layers', 'k-pooling layers') but does not provide specific version numbers for any software, libraries, or frameworks used. |
| Experiment Setup | Yes | Table 3. The hyperparameters used when training Le NSE. M denotes the size of the vertex subset we use to induce the subgraphs throughout training, n denotes the number of samples per class in the subgraph dataset, N is the number of training episodes, d corresponds to the dimensionality of the vertex embeddings for the Graph SAGE layers in the encoder whilst d is the final embedding dimension of the encoder, c denotes the frequency with which we perform SGD on the parameters of the DQN as per Algorithm 1, β is the scaling factor in the rewards and Ttrain, Ttest denote the length of the train and test episodes, respectively. |