Research map / Graph learning / GNN architectures
The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisited
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.
Re-evaluates curvature-based graph rewiring (SDRF with BFc, JLc, AFc variants) on real-world node and graph classification benchmarks, finding that selected edges often violate the oversquashing theory and that reported SOTA gains come from hyperparameter sweep outliers.
Problem
Whether curvature-based graph rewiring actually alleviates oversquashing and improves GNN performance on real-world benchmark datasets, given that theoretical bottleneck conditions may not hold there and reported gains may stem from hyperparameter tuning.
Approach
Checks whether SDRF-selected edges satisfy the degree/triangle/four-cycle conditions of the oversquashing theorem (Theorem 4), and replaces single best-run accuracies with full distributions over large random hyperparameter sweeps (training and rewiring hyperparameters) for each curvature notion.
Key results
- Across 9 node-classification and 2 graph-classification datasets, no curvature notion consistently shifts the accuracy distribution away from the no-rewiring baseline.
- Edges selected by SDRF satisfy the corrected Theorem 4 condition 2b in only 0.16% (Chameleon) to 69.88% (Pubmed) of cases, and never satisfy the original condition 2 on most datasets (0% on 9 of 11).
- Top-10% accuracies for rewired variants are often below the no-rewiring baseline (e.g., Cora 58.83 for None vs 28.39 for BFc), with AFc variants only marginally better on Cornell, Wisconsin, and Actor, within the spread.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply curvature-based SDRF rewiring rather than no rewiring | GCN · Node-classification datasets (Texas, Cornell, Wisconsin, Chameleon, Cora, Citeseer, Pubmed, Actor, Squirrel) | mean test accuracy | Mixed |
| Use AFc3 or AFc4 rewiring instead of no rewiring | GCN · Cornell, Wisconsin, Actor | mean test accuracy: 53.66 ± 0.14 -> 54.20 \\pm 1.57; 54.92 ± 0.51 -> 56.37 \\pm 1.60; 27.73 ± 0.02 -> 28.14 ± 1.02 | Helped |
| Use curvature-based rewiring instead of no rewiring | GCN · Chameleon, Squirrel | mean test accuracy: 40.76 ± 3.52 -> 36.93 \\pm 5.14; 36.73 ± 1.96 -> 35.78 ± 1.83 | Hurt |
| Use AFc3 instead of AFc4, omitting four-cycle contributions (ablation) | Augmented Forman curvature rewiring · Wisconsin | mean test accuracy: 54.60 ± 0.80 -> 56.37 \\pm 1.60 | Helped |
| Use BFc3 instead of BFc, omitting four-cycle contributions (ablation) | Balanced Forman curvature rewiring · Chameleon | mean test accuracy: 34.58 \pm 3.19 -> 30.93 \pm 0.10 | Hurt |
| Use the modified BFc implementation instead of BFc (ablation) | Balanced Forman curvature rewiring · Citeseer | mean test accuracy: 35.99 ± 13.82 -> 44.16 ± 12.46 | Helped |
| Rewire using JLc instead of no rewiring | GCN · Pubmed | mean test accuracy: 41.99\pm 12.58 -> 39.47 \pm 8.97 | Hurt |
| Rewire using AFc4 instead of no rewiring | GCN · Citeseer | mean test accuracy: 58.14 ± 7.33 -> 61.67 ± 5.43 | Helped |
| Select edges using the actual modified condition 2b rather than the original condition 2 (ablation) | SDRF rewiring · Cora | rewired edges satisfying condition: 0~(0\%) -> 68~(68.0\%) | Helped |
Surprising findings
- Citation networks, which best satisfy the theoretical bottleneck condition, show no benefit from rewiring and sometimes a larger performance spread.
- The publicly available Balanced Forman curvature implementation miscounts four-cycles, giving BFc(0,1)=0.08 instead of the correct 0.10 on the paper's sample graph.
Limitations
- Only SDRF is studied; other rewiring algorithms are not evaluated.
- Random-grid search with 800 iterations and a grid partly derived from prior best settings may bias the distributions.
- Only GCN is used as the GNN backbone.
Experimental setup
Datasets: Texas Cornell Wisconsin Chameleon Squirrel Actor Cora Citeseer Pubmed MUTAG PROTEINS
Benchmarks: Texas Cornell Wisconsin Chameleon Squirrel Actor Cora Citeseer Pubmed MUTAG PROTEINS
Metrics: mean test accuracy top-10% accuracy mean and std Wasserstein distance between sweep distributions fraction of edges satisfying Theorem 4 condition 2 / 2b
Baselines: No rewiring (None) BFc BFc_3 BFc_mod JLc AFc_3 AFc_4
Builds on: SDRF Balanced Forman curvature Theorem 4 oversquashing bound (Topping et al.) understanding-oversquashing codebase
Closest papers by meaning
- Locality-Aware Graph Rewiring in GNNs (ICLR 2024 · similarity 0.92)
- PANDA: Expanded Width-Aware Message Passing Beyond Rewiring (ICML 2024 · similarity 0.91)
- GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring (ICLR 2025 · similarity 0.89)
- Discrete Curvature Graph Information Bottleneck (AAAI 2025 · similarity 0.89)
- Effective Structural Encodings via Local Curvature Profiles (ICLR 2024 · similarity 0.88)
- Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification (ICML 2025 · 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.