Research map / Graph learning / GNN architectures
Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GOKU, a graph rewiring method that densifies a graph via inverse spectral sparsification and then sparsifies it with effective-resistance and feature-similarity sampling, to mitigate GNN over-squashing while preserving the Laplacian spectrum and edge count.
Problem
Over-squashing in message-passing GNNs caused by structural bottlenecks; existing rewiring methods often distort the graph spectrum and add many edges, increasing cost and over-smoothing risk.
Approach
A densification-sparsification rewiring (DSR) paradigm: treat the input graph as a spectral sparsifier of an unknown latent graph, reconstruct that latent graph via inverse (unimportance-based) spectral sparsification guided by the Fiedler vector and degrees, then apply importance-based spectral sparsification using effective resistance weighted by feature cosine similarity, keeping the output no
Key results
- GOKU with GCN achieves the best average ranking (AR 1.90) across 10 datasets, e.g., 72.4% on Texas vs 49.4% for BORF and 69.4% on Cornell.
- With GIN, GOKU attains AR 1.80, the best among methods, with 60.2% on Texas and 57.6% on Wisconsin.
- On SBM graphs, GOKU raises homophily (e.g., 0.7558 to 0.7822 on the L-High graph with 80,352 edges) and scales near-linearly in running time (about 65 s on the largest graph).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| apply GOKU rewiring instead of no rewiring | GCN · Texas | accuracy: 44.2 -> 72.4 | Helped |
| apply GOKU rewiring instead of no rewiring | GCN · Cornell | accuracy: 41.5 -> 69.4 | Helped |
| apply GOKU rewiring instead of no rewiring | GCN · Wisconsin | accuracy: 44.6 -> 68.8 | Helped |
| apply GOKU rewiring instead of no rewiring | GCN · Chameleon | accuracy: 59.2 -> 63.2 | Helped |
| apply GOKU rewiring instead of no rewiring | GCN · Mutag | accuracy: 68.8 -> 81.0 | Helped |
| apply GOKU rewiring instead of no rewiring | GCN · Citeseer | accuracy: 72.3 -> 73.6 | Helped |
| add sparsification to densification-only GOKU (ablation) | GOKU · Mutag | accuracy: 78.0 -> 81.0 | Helped |
| add sparsification to densification-only GOKU (ablation) | GOKU · Imdb | accuracy: 48.2 -> 49.8 | Helped |
| add sparsification to densification-only GOKU (ablation) | GOKU · Chameleon | accuracy: 62.7 -> 63.2 | Helped |
| add densification to sparsification-only GOKU (ablation) | GOKU · Mutag | accuracy: 76.8 -> 81.0 | Helped |
| add densification to sparsification-only GOKU (ablation) | GOKU · Imdb | accuracy: 48.8 -> 49.8 | Helped |
| add densification to sparsification-only GOKU (ablation) | GOKU · Proteins | accuracy: 70.1 -> 71.9 | Helped |
Surprising findings
- Densification-only (GOKU-D) enhances connectivity more than full GOKU but does not always yield better downstream accuracy, attributed to over-smoothing or disrupted community structure.
- On Cora with GCN, GOKU (86.8) slightly underperforms BORF (87.5) and GTR (87.3), and on Enzymes it is tied with LASER at 27.6.
Limitations
- Spectral sparsification relies on weighted graphs, and edge weights may add complexity for GNNs.
- Hyperparameters alpha and beta are tuned on validation sets, and gains on some datasets are small (e.g., Cora, Imdb).
Experimental setup
Datasets: Cora Citeseer Texas Cornell Wisconsin Chameleon Enzymes Imdb Mutag Proteins
Benchmarks: Cora Citeseer Texas Cornell Wisconsin Chameleon Enzymes Imdb Mutag Proteins
Metrics: classification accuracy average ranking homophily level effective resistance running time Laplacian spectrum similarity
Baselines: NONE SDRF FoSR BORF GTR Delaunay Rewiring (DR) LASER
Builds on: spectral sparsification SDRF FoSR BORF Delaunay rewiring
Closest papers by meaning
- Locality-Aware Graph Rewiring in GNNs (ICLR 2024 · similarity 0.91)
- PANDA: Expanded Width-Aware Message Passing Beyond Rewiring (ICML 2024 · similarity 0.91)
- Spectral Graph Sparsification Preserves Representation Geometry in Graph Neural Networks (NeurIPS 2026 · similarity 0.90)
- Joint Graph Rewiring and Feature Denoising via Spectral Resonance (ICLR 2025 · similarity 0.90)
- Spectral Graph Pruning Against Over-Squashing and Over-Smoothing (NeurIPS 2024 · similarity 0.89)
- Graph Cascades: Contagion-Based Mesoscopic Rewiring for Structure-Aware Graph Machine Learning (NeurIPS 2026 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.