🤖 machine learning

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

This survey comprehensively reviews graph rewiring techniques designed to mitigate the over-squashing and over-smoothing challenges in Graph Neural Networks by modifying graph topology to enhance information propagation, covering their theoretical foundations, implementations, and performance trade-offs.

Original authors: Hugo Attali, Nathalie Pernelle, Davide Buscaldi, Fragkiskos D. Malliaros

Published 2026-05-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hugo Attali, Nathalie Pernelle, Davide Buscaldi, Fragkiskos D. Malliaros

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to pass a secret message across a crowded room full of people. In the world of Artificial Intelligence, specifically Graph Neural Networks (GNNs), the "people" are data points (like nodes in a network), and the "handshakes" between them are the connections (edges) that allow them to share information.

This paper is a survey (a big review) of a new strategy called Graph Rewiring. Think of it as a "room rearranger" for AI. Instead of just teaching the AI how to talk better, this method physically changes the layout of the room to make communication easier.

Here is the breakdown of the problems they are solving and the solutions they offer, using simple analogies.

The Two Big Problems: "The Squeeze" and "The Blur"

The paper identifies two main reasons why these AI models sometimes fail to learn long-distance connections:

1. Over-Squashing (The "Squeeze")
Imagine a narrow hallway where 100 people are trying to whisper a secret to one person at the end. As the message travels down the line, it gets squeezed into a tiny, compressed whisper. By the time it reaches the end, the details are lost.

In AI terms: When information from far-away nodes tries to reach a central node, it gets compressed into a fixed-size memory slot. The AI forgets the specific details of the distant node because there's too much "traffic" on the few paths connecting them.

2. Over-Smoothing (The "Blur")
Imagine a group of people standing in a circle, constantly mixing their paint buckets with their neighbors. If they keep doing this for too long, eventually, everyone's paint turns the exact same muddy brown color. You can no longer tell who was originally red, blue, or green.

In AI terms: As the AI passes information back and forth between neighbors, the unique "identity" of each node gets washed out. They all start looking the same, making it impossible for the AI to tell them apart.

The Solution: Graph Rewiring

Instead of forcing the AI to work with a broken room layout, Graph Rewiring changes the room itself. It adds new shortcuts or removes confusing dead ends to help the message flow better.

The paper categorizes these "room rearrangers" into three main styles:

1. The Structural Fix (The Architect)

This approach looks only at the shape of the connections, ignoring what the people are wearing (their data features). It uses math to find the "bottlenecks" (narrow hallways) and the "dead ends."

How it works: It uses tools like Curvature (measuring how "bumpy" a connection is) or Resistance (measuring how hard it is to get from A to B).
The Analogy: If the Architect sees a hallway that is too narrow (high resistance), they knock down a wall to create a new door. If they see a room that is too crowded with people mixing paint (high positive curvature), they remove some connections to stop the mixing.
Pros/Cons: It's very logical and easy to understand, but it can be computationally expensive (slow) and sometimes needs a lot of "tweaking" (hyperparameters) to get the door placement just right.

2. The Feature-Aware Fix (The Matchmaker)

This approach looks at who the people are (their data features) before rearranging the room.

How it works: It asks, "Do these two people actually have anything in common?" If two distant nodes have very similar data (like two people wearing the same color shirt), the AI might draw a new line between them, even if they weren't originally connected.
The Analogy: Instead of just looking at the hallway, the Matchmaker looks at the guests. If two guests are wearing matching outfits but are on opposite sides of the room, the Matchmaker creates a direct bridge between them so they can talk immediately.
Pros/Cons: This often works better because it uses more information, but it's harder to explain why the AI made a specific change. It's like saying, "I moved the wall because the colors matched," which is a bit more abstract than "I moved the wall because the hallway was too narrow."

3. The Virtual Node (The Central Hub)

Sometimes, the room is just too big.

How it works: This method adds a "Super Node" (like a central megaphone or a master switch) that connects to everyone.
The Analogy: Instead of passing a message person-to-person across a huge stadium, everyone whispers to a central announcer, who then shouts the message to everyone else. This drastically shortens the distance information has to travel.

How Do We Know It Works?

The paper argues that we shouldn't just look at the final test score (did the AI get the right answer?). We need to check the "health" of the room itself:

Did we fix the bottlenecks? (Are the hallways wider?)
Did we stop the paint from mixing? (Are the colors still distinct?)
Did the message travel faster? (Is the "commute time" shorter?)

The Bottom Line

This survey concludes that Graph Rewiring is a powerful tool, but it's not a "one-size-fits-all" magic wand.

If your data is noisy or the connections are weak, looking at the features (who the nodes are) helps.
If your data is clean but the structure is bad, looking at the geometry (the shape of the connections) helps.
The authors warn that we need to be careful not to just "tune" the settings to get a lucky win on one specific dataset. We need to understand why the new layout helps the AI learn.

In short: Don't just teach the AI to talk better; fix the room so the conversation can actually happen.

Technical Summary: Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing

1. Problem Statement

Graph Neural Networks (GNNs), while powerful for learning from graph-structured data, face two critical limitations that degrade performance, particularly in heterophilic graphs and tasks involving long-range dependencies:

Over-Squashing: This phenomenon occurs when information from distant nodes is excessively compressed into fixed-size node representations. It arises when the graph topology forces many distinct long-range signals to pass through a small set of paths (structural bottlenecks), causing the Jacobian sensitivity of distant nodes to decay rapidly with distance.
Over-Smoothing: This occurs when repeated message passing causes node representations to become indistinguishable. As layers deepen, the aggregation process acts like a diffusion process, progressively reducing the variation across node embeddings until they collapse to a homogeneous state.

Both issues stem from the interaction between the message passing operator and the input graph topology. While existing solutions include edge reweighting (which remains constrained by the original graph support) and multi-hop aggregation (which can exacerbate over-squashing and accelerate over-smoothing due to graph densification), these approaches often fail to fundamentally alter the connectivity structure to facilitate efficient long-range information flow.

2. Methodology: Graph Rewiring

The paper surveys graph rewiring, a class of methods that explicitly modify the graph topology ( $G \to G^+$ ) to promote information propagation while attenuating structural patterns that induce excessive mixing or compression.

2.1 Core Definition

A rewiring operation is defined as a mapping $R: G \to G^+$ , where $G^+ = (V^+, E^+)$ is a modified graph. This can be:

Static: Applied once prior to training.
Dynamic: Evolves during training based on learnable parameters ( $G^+ = R_\theta(G)$ ).
The goal is to obtain a topology more favorable to Message Passing Neural Networks (MPNNs) than the original graph.

2.2 Topological and Connectivity Measures

Rewiring strategies rely on specific metrics to identify bottlenecks and guide structural modifications:

Discrete Curvature: Measures local structural dispersion.
- Ollivier Curvature: Based on optimal transport (Wasserstein distance) between probability measures on neighborhoods.
- Forman Curvatures (Augmented/Balanced): Combinatorial measures incorporating triangles and cycles of various lengths.
- Jost-Liu Curvature: Refines edge-based measures using local clustering (triangles).
- Role: Highly negative curvature often indicates bottlenecks (over-squashing), while high positive curvature can indicate redundant local mixing (over-smoothing).
Effective Resistance: A global measure of connectivity between two nodes considering all disjoint paths. High resistance indicates a bottleneck; low resistance indicates easy communication.
Random Walk-Based Measures: Quantifies connectivity via commute times (expected steps for a random walk to travel between nodes and back) or walk counts. Fewer connecting walks correlate with higher over-squashing risk.
Spectral Gap: Related to the Cheeger constant and the second smallest eigenvalue ( $\lambda_2$ ) of the Laplacian. A small spectral gap indicates near-disconnected components (bottlenecks).

2.3 Rewiring Strategies

The paper categorizes methods based on structural modification, signal source, and efficiency:

A. Structural-Fix Rewiring

These methods modify the graph based solely on topological descriptors ( $S_G$ ) without using node features or labels.

Curvature-Based: Edges are added or removed based on curvature thresholds. Highly negative curvature edges (bottlenecks) are bridged by adding shortcuts; highly positive curvature edges (redundant cliques) are removed to prevent over-smoothing.
Resistance-Based: Iteratively adds edges between node pairs with high effective resistance to minimize global resistance.
Walk-Based: Adds edges between pairs with few connecting walks (low $\Omega_k$ ) to increase path diversity.
Spectral Gap Methods: Constructs graphs (e.g., expanders) with maximized spectral gaps to ensure rapid mixing without bottlenecks.
Virtual Nodes: Augments the graph with auxiliary nodes (e.g., a "master node" or fractal nodes) connected to subsets of original nodes to create multi-scale shortcuts, reducing diameter and effective resistance.

B. Feature-Aware Rewiring

These methods utilize node attributes to guide rewiring, which is crucial when the observed topology is noisy or misaligned with the task.

Geometric Approaches: Reconstructs the graph using Delaunay triangulation in feature space (e.g., DR, TRIGON) to enforce task-relevant connectivity while avoiding negative curvature.
Feature Similarity: Ranks edge additions/deletions based on feature affinity (e.g., cosine similarity), often constrained by community structures (e.g., ComFy).
Spectral Alignment: Enforces consistency between the graph topology and feature geometry by aligning eigenvectors of the adjacency matrix with singular vectors of node features (e.g., JDR).

3. Key Contributions and Survey Scope

This paper provides a method-centric survey of state-of-the-art rewiring approaches, distinguishing itself from previous surveys (e.g., those focusing solely on over-squashing) by:

Comprehensive Categorization: Systematically organizing methods by structural operator, information source (structure vs. features), and computational trade-offs.
Theoretical Underpinnings: Explicitly linking rewiring techniques to the mathematical formalization of over-squashing (Jacobian sensitivity decay) and over-smoothing (asymptotic collapse).
Critical Analysis of Trade-offs:
- Attribution: Structural-fix methods offer clearer causal attribution of performance gains to topology changes, whereas feature-aware methods may conflate topological improvements with feature modeling.
- Hyperparameter Sensitivity: Many structural methods (e.g., curvature-based) are highly sensitive to edit budgets and thresholds, often requiring favorable configurations to show gains.
- Computational Complexity: Curvature and effective resistance calculations can scale quadratically or cubically, while walk-based or spectral approximations offer better scalability for large graphs.

4. Evaluation and Results

The paper emphasizes that rewiring should not be evaluated solely on downstream accuracy. Instead, it advocates for a multi-faceted evaluation protocol:

Structure-Level Diagnostics: Verifying if the rewired graph $G^+$ actually reduces effective resistance, commute times, or shifts curvature distributions away from bottleneck-inducing values.
Model-Level Diagnostics: Measuring improvements in long-range sensitivity (e.g., via Jacobian-based measures).
Benchmarks: Performance is typically validated on heterophilic datasets and long-range interaction benchmarks where standard GNNs struggle.
Baselines: Comparisons should include graph-agnostic baselines (e.g., DeepSets) to distinguish relational benefits from feature-only effects, and matched-budget controls (e.g., random rewiring) to ensure gains are not merely due to increased edge counts.

5. Significance and Future Directions

The paper argues that graph rewiring represents a principled way to intervene on graph structure to improve learning. Its significance lies in shifting the focus from purely architectural changes to modifying the propagation substrate itself.

Future Directions Identified:

Structure-Feature Interplay: Clarifying when rewiring is necessary versus when feature-side mechanisms suffice for long-range learning, and how to combine them under matched constraints.
Generalization and Stability: Leveraging structural proxies (e.g., degree heterogeneity, spectral properties) to predict when topology degrades generalization, guiding rewiring to control propagation amplification rather than just optimizing accuracy.
Rigorous Evaluation: Moving toward clearer problem formulations and evaluation protocols that make claims robust, comparable, and interpretable across different settings.

The authors conclude that progress in this field will depend on more explicit assumptions and evaluation protocols that can robustly attribute performance improvements to specific topological interventions.