Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey

2026-05-05 · Source: cs.LG updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences · Depth: Expert, extended

Summary

A survey by Davide Buscaldi and Fragkiskos D. Malliaros reviews graph rewiring techniques to enhance Graph Neural Network (GNN) performance by mitigating over-squashing and over-smoothing. These phenomena, which degrade information flow and make node representations indistinguishable, stem from message passing interacting with input topology. The survey categorizes rewiring methods into structural-fix, which modify topology based on measures like discrete curvature, effective resistance, random walk-based metrics, and spectral gap, and feature-aware, which use node attributes for rewiring. It details specific techniques such as Ollivier Curvature, Augmented Forman Curvature, and Delaunay Rewiring. The authors also discuss practical trade-offs, including performance attribution, hyperparameter sensitivity, and computational complexity, emphasizing that rewiring should be evaluated beyond just downstream accuracy.

Key takeaway

For research scientists developing or deploying GNNs, understanding graph rewiring is crucial for overcoming performance limitations in heterophilic graphs or those with long-range dependencies. You should consider implementing rewiring strategies, either structural-fix or feature-aware, to explicitly modify graph topology. Evaluate these methods not only by downstream accuracy but also by their impact on structural diagnostics like effective resistance or commute times, ensuring the chosen technique aligns with the task's effective radius and computational constraints.

Key insights

Graph rewiring modifies GNN topology to combat over-squashing and over-smoothing, improving information flow.

Principles

• Topology directly impacts GNN information flow.
• Rewiring can be static (preprocessing) or dynamic (during training).
• Evaluation needs structure-level diagnostics, not just accuracy.

Method

Graph rewiring involves adding, removing, or reweighting edges based on topological descriptors (e.g., curvature, effective resistance, spectral gap) or node features to optimize information propagation.

In practice

• Use curvature-based rewiring to alleviate bottlenecks.
• Employ feature-aware methods when graph topology is noisy.
• Consider virtual nodes to reduce graph diameter.

Topics

• Graph Rewiring Techniques
• Over-squashing Mitigation
• Over-smoothing Mitigation
• Graph Topology Modification
• Discrete Curvature

Best for: Research Scientist, AI Scientist, Machine Learning Engineer, AI Student

Related on AIssential

• Graph Hierarchical Recurrence for Long-Range Generalization — Graph Hierarchical Recurrence (GHR) improves long-range generalization and parameter efficiency in graph learning.
• Learning From Structure: Topology-Aware AI for Dental Scans` — Topology-aware GNNs can automate dental scan segmentation, significantly reducing manual annotation time.
• A Gentle Introduction to Graph Neural Networks — GNNs leverage graph structures to model relationships, enabling predictions across diverse data types and tasks.
• Graph Reduction in Multirelational Networks: A Spreading-Oriented Reduction Benchmark — Graph reduction's impact on influence maximization performance varies significantly by network type and reduction strategy.
• Beyond Homophily: Towards Generalized Graph Reconstruction Attack and Defense — GNNs are vulnerable to graph reconstruction attacks, but a Markov chain approximation can inform both stronger attacks and effective defenses.
• Beyond Soft Masks: Hard-Perturbation Mixup Explainer for Robust GNN Explainability — HPME uses hard perturbations and structural mixup to generate robust, in-distribution GNN explanations by eliminating irrelevant information.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.LG updates on arXiv.org.