FoSR: First-order spectral rewiring for addressing oversquashing in GNNs
Authors: Kedar Karhadkar, Pradeep Kr. Banerjee, Guido Montufar
ICLR 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We find experimentally that our algorithm outperforms existing graph rewiring methods in several graph classification tasks. [...] We empirically demonstrate that the proposed method results in faster spectral expansion (a marker of reduced oversquashing) and improved test accuracy against several baselines on several graph classification tasks (see Table 1). |
| Researcher Affiliation | Academia | Kedar Karhadkar UCLA kedar@math.ucla.edu Pradeep Kr. Banerjee MPI Mi S pradeep@mis.mpg.de Guido Montúfar UCLA & MPI Mi S montufar@math.ucla.edu |
| Pseudocode | Yes | The steps of our method are outlined in Algorithm 1. [...] Algorithm 1 Fo SR: First-order Spectral Rewiring |
| Open Source Code | Yes | The computer implementation of the proposed methods along with scripts to re-run our experiments are made publicly available on https://github.com/ kedar2/Fo SR. |
| Open Datasets | Yes | Datasets We consider graph classification tasks REDDIT-BINARY, IMDB-BINARY, MUTAG, ENZYMES, PROTEINS, COLLAB from the TUDataset (Morris et al., 2020) where the topology of the graphs in relation to the task has been identified to require long-range interactions. |
| Dataset Splits | Yes | For optimizing hyperparamters and evaluating each configuration, we first select a test set consisting of 10 percent of the graphs and a development set consisting of the other 90 percent of the graphs. We determine accuracies of each configuration using 100 random train/validation splits of the development set consisting of 80 and 10 percent of the graphs, respectively. |
| Hardware Specification | Yes | We conducted all our experiments on a local server with 2x 22-Core/44-Thread Intel Xeon Scalable Gold 6152 processor (2.1/3.7 GHz) and 8x NVIDIA Ge Force RTX 2080 Ti graphics card (11 GB, GDDR6). |
| Software Dependencies | No | All the experiments were implemented in Python using Py Torch (Paszke et al., 2019), Num Py (Harris et al., 2020), Py G (Py Torch Geometric) (Fey and Lenssen, 2019), with plots created using Matplotlib (Hunter, 2007). While software names are listed with citations, specific version numbers (e.g., PyTorch 1.9) are not provided in the text. |
| Experiment Setup | Yes | The hyperparameter values are reported in Appendix D.1. [...] Table 4: Common hyperparameters Dropout 0.5 Number of layers 4 Hidden dimension 64 Learning rate 10-3 Stopping patience 100 epochs. [...] We train all models with an Adam optimizer with a learning rate of 10-3 and a scheduler which reduces the learning rate by a factor of 10 after 10 epochs with no improvement in validation loss. |