Research map / Graph learning / GNN architectures
Spectral Graph Pruning Against Over-Squashing and Over-Smoothing
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.
Shows via Braess-paradox analysis that deleting edges can raise the spectral gap and slow over-smoothing, and proposes greedy spectral-gap rewiring (ProxyAdd/ProxyDelete, plus Eldan-criterion variants) that is applied to GNN rewiring, heterophilic node classification, and graph lottery tickets.
Problem
Over-squashing in message passing GNNs is usually mitigated by adding edges to raise the spectral gap, but this increases over-smoothing; the paper asks whether edge deletions can address both problems jointly.
Approach
Uses the Braess paradox to argue that some edge deletions increase the spectral gap while also removing inter-class edges that cause harmful smoothing; proposes a matrix-perturbation proxy to greedily add or delete edges efficiently, and links this to graph lottery tickets via pruning at initialization.
Key results
- On LRGB, ProxyAdd+GCN reaches 0.2213 F1 on PascalVOC-SP (vs FoSR+GCN 0.2157) and 0.2465 MAE on Peptides-Struct (vs FoSR 0.2499); DRew is best on Peptides-Func (0.6996 AP).
- On Roman-Empire with 5 layers, GCN+ProxyGap (add 50, delete 20) reaches 77.54 accuracy with addition-only and GAT+ProxyGap reaches 86.00 with deletions, versus GAT baseline 80.89.
- Pruning graphs with ProxyDelete for lottery tickets on Pubmed gives 75.25 accuracy versus 76.90 for UGS, with comparable results on Cora and Citeseer.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use ProxyAdd instead of no graph rewiring | GCN · PascalVOC-SP Test | F1: 0.1268±0.0060 -> 0.2213±0.0011 | Helped |
| use ProxyDelete instead of no graph rewiring | GCN · Peptides-Func Test | AP: 0.5930±0.0023 -> 0.6908±0.0007 | Helped |
| use ProxyAdd instead of no graph rewiring | GCN · Peptides-Struct Test | MAE: 0.3496±0.0013 -> 0.2465±0.0004 | Helped |
| use ProxyDelete instead of no graph rewiring | GCN · Roman-Empire, 5 layers | Accuracy: 70.30±0.73 -> 77.45±0.68 | Helped |
| use ProxyGap edge deletions instead of no rewiring | GAT · Roman-Empire, 5 layers | Accuracy: 80.89±0.70 -> 86.00±0.36 | Helped |
| prune graph edges with ProxyDelete rather than UGS graph pruning | UGS lottery-ticket pruning · Cora | Accuracy: 68.46±1.89 -> 69.26±0.63 | Helped |
| prune graph edges with EldanDelete rather than UGS graph pruning | UGS lottery-ticket pruning · Citeseer | Accuracy: 66.50±0.60 -> 64.60±0.00 | Hurt |
| prune graph edges with spectral methods rather than UGS | UGS lottery-ticket pruning · Pubmed | Accuracy: 76.90±1.83 -> 78.00±0.42; 76.90±1.83 -> 75.25±0.25 | Mixed |
Surprising findings
- Deleting edges can increase the spectral gap, contrary to the common assumption that deletions always reduce it.
- Pruning the graph based purely on structure (no features or labels) gives lottery-ticket results comparable to UGS, which uses feature and label information.
Limitations
- Eldan-criterion rewiring does not scale well to large graphs.
- Spectral rewiring ignores node labels and task, so it can hurt in some label configurations (acknowledged in appendix).
- Eigenvector multiplicity (e.g., on ring graphs) can make the Eldan criterion choice ambiguous.
Experimental setup
Datasets: PascalVOC-SP Peptides-Func Peptides-Struct Roman-Empire Amazon-Ratings Minesweeper Cora Citeseer Pubmed Texas Cornell Wisconsin
Benchmarks: Long Range Graph Benchmark (PascalVOC-SP, Peptides-Func, Peptides-Struct) Roman-Empire Amazon-Ratings Minesweeper Cora Citeseer Pubmed
Metrics: test F1 test AP test MAE accuracy test ROC graph sparsity weight sparsity spectral gap cosine distance Dirichlet energy
Baselines: FoSR DRew UGS EldanDelete EldanAdd GCN GAT
Builds on: FoSR Eldan's criterion (Braess paradox for spectral gap) Unified Graph Sparsification (UGS) DRew
Closest papers by meaning
- Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification (ICML 2025 · similarity 0.89)
- Pruning Spurious Subgraphs for Graph Out-of-Distribution Generalization (NeurIPS 2025 · similarity 0.87)
- Effects of Dropout on Performance in Long-range Graph Learning Tasks (NeurIPS 2025 · similarity 0.87)
- Graph Coarsening with Message-Passing Guarantees (NeurIPS 2024 · similarity 0.86)
- Asymmetric Learning for Spectral Graph Neural Networks (AAAI 2025 · similarity 0.86)
- Taxonomy of reduction matrices for Graph Coarsening (NeurIPS 2025 · similarity 0.85)
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.