Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challenges

arXiv:2311.07073 · cs.LG · Submitted 2026-08-14 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Exposition on Over-Squashing Problem on GNNs: Current Methods, Benchmarks and Challenges".

Jane: The paper was written by Dai Shi, Andi Han, Lequan Lin, Yi Guo and Junbin Gao from University of Sydney and Western Sydney University.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the show, everybody. Today we’re digging into a paper that’s been making the rounds on arXiv, and it’s called “Exposition on Over-Squashing Problem on GNNs: Current Methods, Benchmarks and Challenges.” Jane, I gotta say, just the title alone tells you this is a field that’s still figuring itself out.

Jane: Absolutely, Tom. And for our listeners who might not be deep in graph neural networks, let’s break that down. GNNs are these models that learn from data structured as networks — think social networks, molecules, even road maps. They work by passing messages between connected nodes, like neighbors sharing notes.

Tom: Right, and “over-squashing” is this weird problem where, if two nodes are far apart in the network, the information gets squeezed and distorted as it travels through all the intermediate nodes. It’s like trying to whisper a secret through a long line of people — by the time it reaches the end, it’s garbled.

Jane: Exactly. And this paper is basically a big review of everything we know about that problem so far. The authors — Dai Shi, Andi Han, Lequan Lin, Yi Guo, and Junbin Gao — they’ve pulled together all the different ways people have tried to define and measure over-squashing, plus all the methods proposed to fix it.

Tom: And that’s what I love about this paper. It’s not just a list of tricks. They’re trying to build a unified framework. They categorize the solutions into spatial rewiring, spectral rewiring, and what they call implicit rewiring. Spatial means changing the graph locally, like adding edges between nearby nodes. Spectral means looking at global properties, like how well-connected the whole graph is.

Jane: And implicit rewiring is the clever one — that’s stuff like graph transformers, where instead of physically changing the graph, you just let every node attend to every other node. It’s like skipping the game of telephone entirely and just handing the message directly.

Tom: Yeah, and that’s a huge deal because it means we don’t have to mess with the graph structure at all. But the paper also points out that there’s a trade-off — if you make the graph too connected, you run into another problem called over-smoothing, where all the node features start looking the same.

Jane: Right, so it’s a balancing act. And this paper does a great job of laying out that tension. It’s not just about fixing one problem; it’s about understanding how the fixes interact.

Tom: So, Jane, what do you think is the biggest implication here? I mean, this is a survey paper, but it feels like it’s setting the agenda for the next few years of research.

Jane: I think the biggest thing is that they’re calling for a unified definition of over-squashing. Right now, different papers measure it in different ways — some use curvature, some use effective resistance, some use commute time. That makes it really hard to compare results across papers.

Tom: And without a common yardstick, you can’t tell if your new method is actually better or just different. That’s a real problem for the field.

Jane: Exactly. So this paper is like a call to arms. It’s saying, “Hey, we need to standardize how we talk about this problem before we can really make progress.” And that’s a pretty exciting thing to be part of.

Tom: Well, and speaking of progress, next we’re going to get into what the paper actually found when they looked at all these methods side by side. Stay with us.

Summary: Tom: So we’re back with “Exposition on Over-Squashing Problem on GNNs: Current Methods, Benchmarks and Challenges.” Jane, last time we talked about the big picture. Now let’s get into what the paper actually covers in detail.

Jane: Right, so the paper starts by giving us a formal definition of the over-squashing score. Basically, it’s the sensitivity of one node’s features to another node’s initial features after a certain number of layers. They write it as the norm of a Jacobian matrix — that’s just a fancy way of saying, “How much does a change in node A’s input affect node B’s output?”

Tom: And then they show that this score can be bounded by things like the graph’s adjacency matrix, effective resistance, and commute time. So the more paths there are between two nodes, the better the information flows. That makes intuitive sense.

Jane: It does. And then they go through the three categories of solutions we mentioned. The spatial methods use curvature — that’s a geometric property of the graph. If an edge has very negative curvature, it’s a bottleneck, so you add edges around it to relieve the pressure.

Tom: And the spectral methods, like the one based on effective resistance, they try to minimize the total resistance across the whole graph. That’s a more global approach. But the paper points out that these methods can be computationally expensive, especially on large graphs.

Jane: Yeah, and that’s where the implicit methods come in. Graph transformers, for example, just compute attention between all pairs of nodes. That’s powerful, but it’s also quadratic in the number of nodes, so it doesn’t scale well to huge graphs.

Tom: And the paper also reviews the benchmarks. They talk about synthetic graphs like the dumbbell graph and ring-of-cliques, which are specifically designed to test over-squashing. But they also highlight the Long Range Graph Benchmark from two thousand twenty-two which has real-world datasets that require long-range interactions.

Jane: That’s a big deal because, before that benchmark, a lot of the standard datasets didn’t actually require long-range information. So people were testing their methods on data where over-squashing wasn’t even the main challenge.

Tom: Right, so the paper is really pushing for better evaluation practices. They even include a table summarizing the computational complexity of each method, which is super useful for practitioners.

Jane: And they also discuss the relationship between over-squashing and expressive power. If a GNN can’t mix information from distant nodes, then it’s not going to be able to solve tasks that require that long-range dependency. So over-squashing directly limits what the model can learn.

Tom: That’s a really important connection. It’s not just a nuisance; it’s a fundamental limitation on what these models can do.

Jane: Exactly. And the paper also talks about the trade-off between over-squashing and over-smoothing. You fix one, you might make the other worse. That’s a really tricky problem that doesn’t have a clean solution yet.

Tom: So, Meng, you’re the engineer here. What’s your take on the practical side of this?

Meng: Well, Tom, the computational complexity table is the first thing I look at. Some of these rewiring methods are just too slow for real-world applications. If you’re working with a graph with a million nodes, you can’t be computing effective resistance for every pair. So the paper does a good job of flagging which methods are actually feasible at scale.

Tom: That’s a great point. And it leads us right into what the paper suggests for future work. We’ll get into that next.

Improvements: Tom: Welcome back. We’re still on “Exposition on Over-Squashing Problem on GNNs: Current Methods, Benchmarks and Challenges.” Jane, we’ve covered the basics and the summary. Now let’s talk about what the authors say we should do next.

Jane: Right, and one of the biggest things they call for is a unified definition of over-squashing. Right now, different papers use different measures — curvature, effective resistance, commute time. The authors propose a general definition that could encompass all of these.

Tom: And that’s a big deal because it would let researchers compare methods directly. Right now, if one paper says “my method reduces over-squashing” and another says the same thing, they might be measuring completely different things.

Jane: Exactly. They also want a lower bound on the over-squashing score, not just an upper bound. Right now, we know that over-squashing can’t be worse than some value, but we don’t know how good a method can actually get. A lower bound would tell us what’s theoretically possible.

Tom: And they also want to better understand the trade-off between over-squashing and over-smoothing. They suggest that this could be framed like an uncertainty principle — you can’t eliminate both at the same time, so you have to find a balance.

Meng: That’s interesting, but from a practical standpoint, I’d love to see a way to measure over-squashing directly on a trained model. Right now, we’re mostly relying on indirect indicators. The paper mentions that you could compute the Jacobian of the model using automatic differentiation, but nobody’s really done that systematically yet.

Jane: That’s a really good point, Meng. And the paper also highlights the need for better benchmarks. They point out that many existing datasets don’t actually require long-range information, so they’re not good tests for over-squashing mitigation.

Tom: And that’s where the Long Range Graph Benchmark comes in. It’s a step in the right direction, but the authors say we need more datasets like that, especially ones that let us isolate the over-squashing effect from over-smoothing.

Lu: If I can jump in here, Tom. I think the most exciting direction is the connection between over-squashing and expressive power. The paper suggests that over-squashing isn’t just a practical nuisance — it’s a fundamental limit on what GNNs can compute. If we can understand that limit better, we might be able to design architectures that are provably more powerful.

Tom: That’s a really inspiring way to think about it, Lu. It’s not just about fixing a bug; it’s about understanding the theoretical boundaries of these models.

Jane: And the paper also suggests exploring how spatial and spectral rewiring methods affect each other. Right now, they’re treated as separate approaches, but they might be more connected than we think.

Tom: So the bottom line is that this paper isn’t just a review — it’s a roadmap for future research. It tells us where the gaps are and what questions we should be asking.

Jane: And that’s exactly what we’re going to wrap up with in our final segment.

Conclusion: Tom: And we’re back for the final stretch on “Exposition on Over-Squashing Problem on GNNs: Current Methods, Benchmarks and Challenges.” Jane, let’s bring it all together.

Jane: So, to recap, this paper gives us a thorough look at the over-squashing problem in graph neural networks. It defines the problem formally, reviews the different ways to measure it, and categorizes the solutions into spatial, spectral, and implicit rewiring methods.

Tom: And it doesn’t stop there. It also discusses the relationship between over-squashing and expressive power, and the trade-off with over-smoothing. That’s a lot of ground to cover in one paper.

Jane: It is, and that’s what makes it such a valuable resource. For anyone entering this field, this paper is a great starting point. It tells you what’s been done, what hasn’t, and where the open questions are.

Meng: And from my side, the computational complexity table is something I’ll be referencing for a while. It’s rare to see that kind of practical information laid out so clearly.

Lu: I’d add that the call for a unified definition is the most important takeaway. Without that, we’re all speaking different languages, and progress is slower than it needs to be.

Tom: So, what’s the big picture here? This paper is saying that over-squashing is a fundamental challenge for GNNs, and we need to take it seriously if we want these models to work on tasks that require long-range reasoning.

Jane: And the good news is that there are already promising directions. The long-range benchmarks are a great start, and the theoretical work on lower bounds could give us a clearer picture of what’s possible.

Tom: So, for anyone working with graph neural networks, this paper is a must-read. It’s not just a summary; it’s a call to action.

Jane: Well said, Tom. We’re going to say goodbye to this paper and get ready for the next one. Thanks for listening, everyone.

Tom: And remember, if you’re working on GNNs, keep an eye on this space. The next big breakthrough might be just around the corner. See you next time.

Dai Shi, Andi Han, Lequan Lin, Yi Guo, Junbin Gao

University of Sydney · Western Sydney University

cs.LG

Submitted: 2026-08-14

Updated: 2026-08-17

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 68/100

Key concepts

GNNs
Graph Neural Networks are models used to learn from data structured as networks, such as social or road maps. They function by passing messages between connected nodes, where neighboring nodes share information with each other.
Over-squashing
This is a problem where information becomes squeezed and distorted as it travels through multiple intermediate nodes in a network. It is described as the original message becoming garbled by the time it reaches its destination.
Rewiring Methods
Solutions designed to fix over-squashing are categorized into three types: spatial (modifying local graph structure), spectral (optimizing global properties like resistance), and implicit (using mechanisms like graph transformers that bypass physical changes).
Over-smoothing
This is a related issue where all the features of nodes in a network start looking identical. It represents a trade-off problem, often occurring when trying to mitigate over-squashing.

Terminology

Summary

Summary

This paper provides a comprehensive exposition of the over-squashing (OSQ) problem in graph message-passing neural networks (MPNNs). The authors systematically review the problem's formulations, mitigation strategies, theoretical relationships with other GNN issues, empirical validation methods, and open challenges.

The paper begins by defining the OSQ problem, which is conceptually interpreted as a phenomenon of information distortion where the rich information from long-range neighbouring nodes becomes overly compressed into a limited information pack due to the graph connectivity and MPNN architecture. This leads to poor performance in tasks requiring long-range interactions. The OSQ score is formally defined in Definition 1 as the spectral norm of the Jacobian matrix: OSQ(i, s) = ∂h i(l)/∂x s, measuring the sensitivity of node i's representation at layer l to the initial feature of node s. The paper presents several upper bounds for this score. Proposition 1 bounds it via the normalized adjacency matrix: ∂h i(r+1)/∂x s ≤ (αβ)(r+1)(Â(r+1)) is, where α and β bound the derivatives of update and message functions. Proposition 2 extends this to any node pair: ∂h i(r+1)/∂x s ≤ (αβ)(r+1) Σ l=0 r+1 (Â l) is. Proposition 3 provides a bound via effective resistance: ∂h i(r+1)/∂x s ≤ (αβ)(r+1) (d max/d min)2 (r + 2 - (1-µ(r+2))/(1-µ)) - R i,s. Proposition 4 bounds an upgraded symmetric Jacobian obstruction via commute time: ǫ G(1-o(l)) (ρ/ν) R i,s ≤ Ô(l) i,s ≤ (ρ/w) R i,s. Definition 2 extends OSQ to graph-level tasks via the reciprocal of maximal mixing power.

The paper categorizes mitigation strategies into three types. First, spatial rewiring techniques use local topological indicators, primarily graph curvature. The paper reviews Stochastic Discrete Ricci Flow (SDRF), which uses Balanced Forman Curvature (BFC) to identify and add edges to support negatively curved edges while removing positively curved ones. Stochastic Jost and Liu Curvature Rewiring (SJLR) dynamically adds/removes edges during training to address both OSQ and over-smoothing (OSM). Batch Ollivier-Ricci Flow (BORF) provides a cheaper alternative using the original Ollivier-Ricci curvature. AFR-3 uses Augmented Forman Ricci curvature with automatic edge count determination via Gaussian mixture models. The paper also includes graph diffusion methods like DIGL, GRAND, and BLEND, which perform rewiring based on diffusion processes or learned features.

Second, spectral rewiring techniques optimize global graph indicators. Expander Graph Propagation (EGP) uses Cayley graphs to provide supplementary connectivity. Total Effective Resistance Rewiring (GTR) adds edges to minimize total effective resistance. Random Local Edge Flip (RLEF) preserves graph connectivity via the Cheeger constant. First Order Spectral Rewiring (FOSR) maximizes the spectral gap while adding edges. Dynamic Rewiring with Delay (DRew) provides layer-dependent rewiring with a delay mechanism. Locality-Aware SEquential Rewiring (LASER) balances locality preservation and connectivity improvement.

Third, implicit rewiring methods do not explicitly rewire the graph but achieve equivalent effects. Diffusion-based methods include Fractional Diffusion (FLODE) using fractional graph Laplacians, Hypo-elliptic Diffusion which propagates features with their histories, and Quantum Diffusion Convolution (QDC) using quantum diffusion kernels. Transformer-based methods like Graphormer and Difformer compute attention over fully connected graphs, effectively creating dense implicit rewiring.

The paper discusses the relationship between OSQ and expressive power, noting that the sensitivity measure can indicate how powerfully an MPNN mixes node features. It also examines the trade-off between OSQ and OSM, where edges with highly positive curvature contribute to OSM while negatively curved edges contribute to OSQ.

For empirical validation, the paper reviews synthetic datasets including dumbbell graphs, ring-of-cliques graphs, and RingTransfer. Classic benchmarks include citation networks (Cora, Citeseer, Pubmed), TUDataset, ZINC, ogbg-molpcba, and QM9. The paper emphasizes the importance of long-range benchmarks introduced by Dwivedi et al., including Pascal1VOC-SP, COCO-SP, PCMQ-Contact, Peptide-func, and Peptides-struct. It also summarizes computational complexities of various methods in Table 2.

Finally, the paper presents open questions. Theoretically, it calls for lower bounds on the OSQ score, a unified definition (proposing Definition 5), deeper understanding of the OSQ-OSM trade-off, determining optimal network depth, and exploring relationships between spatial and spectral methods. Empirically, it highlights the need for direct numerical measures of OSQ and methods to isolate OSQ effects from OSM.

Improvements for AI systems

Based on the paper, here are the specific improvements I can make to AI systems, along with the resulting capabilities:

1. Improved AI System: Long-Range Dependency-Aware Graph Neural Network (GNN)

  • Improvement: I will implement a dynamic graph rewiring mechanism that combines spatial and spectral indicators. Specifically, the system will use the Balanced Forman Curvature (BFC) (Eq. 14) to identify negatively curved edges (which cause over-squashing) and effective resistance (Eq. 5) to globally assess connectivity. Instead of a static pre-processing step (like SDRF), the rewiring will be layer-dependent (like DRew) to adapt as features evolve. The system will add edges to reduce effective resistance between distant nodes while simultaneously removing edges with high positive curvature to prevent over-smoothing, using a locality-aware constraint (like LASER) to ensure we don't destroy the original graph's community structure.

  • What it can do: It can accurately classify nodes in graphs where predictions depend on interactions between nodes that are more than 2-3 hops apart (e.g., predicting protein function based on distant amino acid residues, or classifying social network users based on long-range community influence). It will outperform standard GCN/GAT models on the Peptides-func and Peptides-struct benchmarks from the Long Range Graph Benchmark (LRGB), where the average graph diameter is large and long-range dependencies are critical.

2. Improved AI System: Curvature-Aware Graph Transformer

  • Improvement: I will modify the attention mechanism of a graph transformer (like Graphormer) to incorporate Ollivier-Ricci curvature (Eq. 12) as an explicit bias term in the attention score calculation. The attention weight between nodes i and j will be adjusted based on the curvature of the path between them. For edges with highly negative curvature (which cause information bottlenecks), I will increase the attention weight to compensate for the information loss. For edges with highly positive curvature (which cause over-smoothing), I will decrease the attention weight to preserve local feature distinctiveness. This directly addresses the trade-off between OSQ and OSM within the attention mechanism itself.

  • What it can do: It can perform graph-level regression and classification on molecular datasets (e.g., ZINC, QM9) where the target property depends on both local functional groups and long-range molecular interactions. It will show improved performance on PascalVOC-SP and COCO-SP for node classification, where objects are spatially distant but semantically related. The system will also be more robust to graph perturbations, as the curvature-aware attention will prevent information from being squashed in bottleneck regions.

3. Improved AI System: Adaptive Depth GNN with OSQ-Aware Early Stopping

  • Improvement: I will develop a system that dynamically determines the optimal number of message-passing layers based on the commute time (or effective resistance) between node pairs. Instead of using a fixed number of layers, the system will compute the maximum commute time between any two nodes that need to interact for the task (identified via a task-specific attention mask). The number of layers will be set to be proportional to this commute time, as suggested by the theoretical analysis in the paper (Section 4.1). The system will also monitor the Dirichlet energy of node features at each layer to detect the onset of over-smoothing. If energy drops below a threshold, the system will stop adding layers even if the commute time hasn't been fully traversed, thus balancing the OSQ-OSM trade-off.

  • What it can do: It can handle graphs with highly variable diameters and connectivity. For example, in a citation network where some papers are in a dense cluster (short commute time) and others are in a sparse periphery (long commute time), the system will use a deeper propagation for the periphery nodes to ensure their information reaches the central nodes without over-smoothing the dense cluster. This will lead to more accurate node classification on heterophilic graphs (like Cora, Citeseer, Pubmed with high heterophily) and on synthetic graphs like RingTransfer and Dumbbell graphs.

4. Improved AI System: OSQ-Aware Feature Mixing Regularizer

  • Improvement: I will add a regularization term to the loss function that penalizes the model if the Jacobian norm between node features (the OSQ score, Eq. 2) is too low for node pairs that are known to be important for the task. This requires a task-specific importance matrix that identifies which node pairs should have strong mutual influence. The regularizer will be: L osq = -λ * Σ(i,j) ∈ ImportantPairs log(∂h i(l)/∂x j). This directly forces the model to learn weights that facilitate information flow between these critical pairs, rather than relying on graph rewiring alone. This is a training-time solution that complements the architectural changes.

  • What it can do: It can be applied to any existing GNN architecture (GCN, GAT, GIN) to improve its performance on tasks with known long-range dependencies. For instance, in a traffic prediction task, the important pairs would be the origin-destination pairs that are far apart. The system will learn to route information effectively between these pairs, leading to more accurate traffic flow predictions. This regularizer can also be used to diagnose why a GNN is failing on a specific task—if the OSQ score is low for important pairs even after training, it indicates a fundamental limitation of the architecture.

5. Improved AI System: Benchmark-Aware Model Selection

  • Improvement: I will create a system that automatically selects the most appropriate OSQ mitigation strategy (spatial rewiring, spectral rewiring, or implicit rewiring) based on the characteristics of the input graph and the task. The system will first analyze the graph's curvature distribution (e.g., percentage of edges with negative BFC), spectral gap, and average effective resistance. If the graph has many negatively curved edges, it will prefer a spatial method (like SJLR). If the spectral gap is small, it will prefer a spectral method (like FOSR). If the graph is small enough, it will consider a graph transformer. This is a meta-learning approach that saves the user from manually tuning the rewiring method.

  • What it can do: It can act as a plug-and-play solution for practitioners who are unsure which GNN variant to use. Given a new graph dataset, the system will automatically recommend and configure the best model, saving significant time and computational resources. It will be particularly useful for non-expert users who want to apply GNNs to their specific domain (e.g., biology, social science) without deep knowledge of the OSQ problem.

Abstract

Graph-based message-passing neural networks (MPNNs) have achieved remarkable success in both node and graph-level learning tasks. However, several identified problems, including over-smoothing (OSM), limited expressive power, and over-squashing (OSQ), still limit the performance of MPNNs. In particular, OSQ serves as the latest identified problem, where MPNNs gradually lose their learning accuracy when long-range dependencies between graph nodes are required. In this work, we provide an exposition on the OSQ problem by summarizing different formulations of OSQ from current literature, as well as the three different categories of approaches for addressing the OSQ problem. In addition, we also discuss the alignment between OSQ and expressive power and the trade-off between OSQ and OSM. Furthermore, we summarize the empirical methods leveraged from existing works to verify the efficiency of OSQ mitigation approaches, with illustrations of their computational complexities. Lastly, we list some open questions that are of interest for further exploration of the OSQ problem along with potential directions from the best of our knowledge.

Sources

Related papers