# The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisited

arXiv: https://arxiv.org/abs/2407.09381 · HTML: https://mlsanity.com/paper/2407.09381/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 45 references that are in the map.
- First posted on arXiv 12 Jul 2024.

## Builds on (most cited first, 30 of 34)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology](https://mlsanity.com/paper/2302.02941/) (2023)
- [FoSR: First-order spectral rewiring for addressing oversquashing in GNNs](https://mlsanity.com/paper/2210.11790/) (2022)
- [Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature](https://mlsanity.com/paper/2211.15779/) (2022)
- [Understanding Oversquashing in GNNs through the Lens of Effective Resistance](https://mlsanity.com/paper/2302.06835/) (2023)
- [Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark](https://mlsanity.com/paper/2309.00367/) (2023)
- [DRew: Dynamically Rewired Message Passing with Delay](https://mlsanity.com/paper/2305.08018/) (2023)
- [On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks](https://mlsanity.com/paper/2212.02374/) (2022)
- [Locality-Aware Graph-Rewiring in GNNs](https://mlsanity.com/paper/2310.01668/) (2023)
- [N-GCN: Multi-scale Graph Convolution for Semi-supervised Node Classification](https://mlsanity.com/paper/1802.08888/) (2018)

## Built on by (most cited first, 11 of 11)

- [Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning](https://mlsanity.com/paper/2505.15547/) (2025)
- [Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey](https://mlsanity.com/paper/2411.17429/) (2024)
- [Understanding Rollout Error in Graph World Models](https://mlsanity.com/paper/2606.27780/) (2026)
- [Performance Heterogeneity in Graph Neural Networks: Lessons for Architecture Design and Preprocessing](https://mlsanity.com/paper/2503.00547/) (2025)
- [Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passing](https://mlsanity.com/paper/2506.06582/) (2025)
- [Probing Graph Neural Network Activation Patterns Through Graph Topology](https://mlsanity.com/paper/2602.21092/) (2026)
- [Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey](https://mlsanity.com/paper/2605.00951/) (2026)
- [Bilevel Graph Structure Learning, Revisited: Inner-Channel Origins of the Reported Gain](https://mlsanity.com/paper/2605.07577/) (2026)
- [Local-Global Geometric Insights for Graph Neural Networks via Entropic Curvature](https://mlsanity.com/paper/2607.22381/) (2026)
- [LEED: Local Embedding Evolution Distance for over-smoothing estimation and virtual node selection in GNN](https://mlsanity.com/paper/2608.09596/) (2026)
- [Pair-Centric Graph Rewiring for Over-Squashing via Optimal Transport-Guided Communication Alignment](https://mlsanity.com/paper/2608.10619/) (2026)

## Abstract (arXiv)

Message passing is the dominant paradigm in Graph Neural Networks (GNNs). The efficiency of message passing, however, can be limited by the topology of the graph. This happens when information is lost during propagation due to being oversquashed when travelling through bottlenecks. To remedy this, recent efforts have focused on graph rewiring techniques, which disconnect the input graph originating from the data and the computational graph, on which message passing is performed. A prominent approach for this is to use discrete graph curvature measures, of which several variants have been proposed, to identify and rewire around bottlenecks, facilitating information propagation. While oversquashing has been demonstrated in synthetic datasets, in this work we reevaluate the performance gains that curvature-based rewiring brings to real-world datasets. We show that in these datasets, edges selected during the rewiring process are not in line with theoretical criteria identifying bottlenecks. This implies they do not necessarily oversquash information during message passing. Subsequently, we demonstrate that SOTA accuracies on these datasets are outliers originating from sweeps of hyperparameters -- both the ones for training and dedicated ones related to the rewiring algorithm -- instead of consistent performance gains. In conclusion, our analysis nuances the effectiveness of curvature-based rewiring in real-world datasets and brings a new perspective on the methods to evaluate GNN accuracy improvements.