Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
Authors: Langzhang Liang, Fanchen Bu, Zixing Song, Zenglin Xu, Shirui Pan, Kijung Shin
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimental results validate the effectiveness of our approach, demonstrating its superiority over strong baseline methods in classification accuracy and retention of the Laplacian spectrum. ... We conduct extensive experiments (Sec. 5). GOKU achieves better downstream performance than existing methods in both node and graph classification tasks on 10 datasets, while effectively balancing improving connectivity and preserving graph spectrum. |
| Researcher Affiliation | Academia | 1Kim Jaechul Graduate School of Artificial Intelligence, KAIST, Seoul, Republic of Korea 2School of Electrical Engineering, KAIST, Daejeon, Republic of Korea 3Department of Engineering, University of Cambridge, Cambridge, United Kingdom 4Artificial Intelligence Innovation and Incubation Institute, Fudan University, Shanghai, China 5Shanghai Academy of Artificial Intelligence for Science, Shanghai, China 6School of Information and Communication Technology, Griffith University, Gold Coast, Australia. Correspondence to: Kijung Shin <EMAIL>. |
| Pseudocode | Yes | Algorithm 1 USS Algorithm ... Algorithm 2 ISS Algorithm ... Algorithm 3 GOKU, Graph Densification and Sparsification Algorithm |
| Open Source Code | Yes | Our code is available at https://github.com/Jinx-byebye/GOKU. |
| Open Datasets | Yes | For node classification, we use Cora, Citeseer (Yang et al., 2016), Texas, Cornell, Wisconsin (Pei et al., 2020), and Chameleon (Rozemberczki et al., 2021), including both homophilic and heterophilic datasets. For graph classification, we use Enzymes, Imdb, Mutag, and Proteins from TUDataset (Morris et al., 2019). |
| Dataset Splits | No | Results are averaged over 100 random trials with both the mean test accuracy and the 95% confidence interval reported. ... The paper uses Cora, Citeseer, Texas, Cornell, Wisconsin, Chameleon, Enzymes, Imdb, Mutag, and Proteins datasets, but does not provide specific details on how these datasets were split into training, validation, and test sets (e.g., percentages or specific files for custom splits). |
| Hardware Specification | No | The paper does not provide specific hardware details such as GPU models, CPU types, or memory configurations used for running the experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details such as library or solver names with version numbers needed to replicate the experiment. |
| Experiment Setup | Yes | applying fixed GNN hyperparameters (e.g., learning rate 1e 3, hidden dimension 64, 4 layers) across all methods. ... We fix the spectrum approximation error ϵ = 0.1 ... For the ER approximation algorithm (Koutis et al., 2014), we set δ = 0.1. ... (1; densification) α ∈ {5, 10, 15, 20, 25, 30} ... (2; sparsification) β ∈ [0.5, 1.0] |