Oversquashing: When Too Much Information Passes Through Bottlenecks

Intuition First: The Telephone Game Through a Bottleneck

Imagine passing a message through a chain of people, but at one point the chain narrows to a single person who must relay messages from 1,000 people on one side to 1,000 people on the other. That single relay is a bottleneck: the message each person on the far side receives is an extremely compressed, noisy version of the original. Oversquashing is exactly this — distant node information must squeeze through bottleneck edges into a fixed-size embedding, losing fidelity exponentially with distance.

Two Different Problems

Oversmoothing (too many layers → embeddings converge) and oversquashing (long-range info is lost at bottlenecks) are often confused. They are distinct:

The Exponential Growth Problem

In a \(K\)-layer MPNN, node \(v\)’s embedding \(h_v^{(K)}\) depends on every node within \(K\) hops — its receptive field \(\mathcal{N}_K(v)\). On a graph that is locally tree-like with branching factor \(d\), that set grows exponentially:

where \(p\) is the fixed hidden width. The width \(p\) does not grow with \(K\), so the information any single distant node \(u\) can claim shrinks roughly like \(1/d^{K}\). Even if \(u\)’s feature is critical for predicting \(v\)’s label, it is drowned out.

Note the condition: this exponential argument needs the neighbourhood to actually expand. On a path or a cycle, \(\lvert\mathcal{N}_K(v)\rvert\) grows only linearly, and oversquashing there arises from a different mechanism — the decay of the propagation operator over distance, quantified next.

The Jacobian Analysis

Alon & Yahav (2021) identified and named oversquashing; Topping et al. (2022) made it quantitative by bounding the Jacobian

which measures how sensitive \(v\)’s \(K\)-layer embedding is to \(u\)’s input feature \(x_u\). Unrolling \(K\) layers of message passing gives a bound of the form

where \(w\) bounds the norms of the weight matrices, \(c\) bounds the Lipschitz constant of the non-linearity, and \(\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\) is the same propagation matrix as in the oversmoothing post. The topology enters through the single factor \((\hat{A}^{K})_{vu}\).

Two consequences follow. First, if \(u\) is more than \(K\) hops from \(v\) then \((\hat{A}^{K})_{vu} = 0\) exactly — no amount of training can create sensitivity that the receptive field does not contain. Second, when \(u\) is reachable but only through a bottleneck, \((\hat{A}^{K})_{vu}\) is tiny, so the forward signal and the gradient \(\partial \mathcal{L}/\partial x_u\) are both suppressed: the model cannot learn that \(u\) matters for \(v\).

Where Oversquashing Is Severe

Oversquashing is worst when:

1. The path between relevant nodes is long (diameter » number of layers)
2. Bottleneck edges connect high-degree subtrees — many nodes compete through a single edge
3. The graph has tree-like structure (few cycles, exponential neighbourhood growth)

Real examples where this matters:

• Molecular property prediction: computing HOMO-LUMO gap requires whole-molecule reasoning; bottleneck edges are single bonds connecting large fragments
• Social network influence: influence travels through single bridges between communities
• Traffic forecasting: a road closure (bottleneck) affects distant nodes but the effect is diluted through many competing paths

Concrete Worked Example: Jacobian Decay on a Path

Take the path graph on 6 nodes, 1–2–3–4–5–6, and ask how much node 1 can influence node 6, which is 5 hops away. Suppose each message-passing step multiplies by a weight matrix with \(\lVert W \rVert = 0.9\) and the non-linearity is 1-Lipschitz, so the bound above reads \(0.9^{K}\,(\hat{A}^{K})_{6,1}\).

The degrees on this path are \((1,2,2,2,2,1)\), so with self-loops \(\tilde{d} = (2,3,3,3,3,2)\). Computing the relevant entries of \(\hat{A}^{K}\) directly:

Node 6’s embedding is roughly 100× less sensitive to node 1’s feature than node 2’s is, and the gap widens geometrically with distance. If node 1’s feature is the critical signal for a prediction at node 6, it is effectively invisible to the model.

Notice that most of the decay here comes from \((\hat{A}^{K})_{vu}\), not from the weight norms: even with \(\lVert W\rVert = 1\) the ratio would be \(0.408 / 0.00617 \approx 66\). The topology is doing the damage.

Measuring Oversquashing

The sensitivity score \(\lVert \partial h_v^{(K)} / \partial x_u \rVert\) measures how much node \(u\) influences node \(v\) after \(K\) layers. Plotting it for all pairs \((u,v)\) reveals which edges are bottlenecks.

Two topology-only proxies avoid training a model at all:

• Commute time \(\tau(u,v)\) — the expected number of steps for a random walk to go from \(u\) to \(v\) and back. High commute time means information struggles to flow between them.
• Effective resistance \(R(u,v)\), the resistance between \(u\) and \(v\) when each edge is a unit resistor. The two are proportional, \(\tau(u,v) = 2\lvert E\rvert\, R(u,v)\), and effective resistance is the quantity that later work (Di Giovanni et al., 2023) ties directly to oversquashing: pairs separated by high effective resistance are exactly the pairs whose Jacobian is provably small.

Solutions: Graph Rewiring

Graph rewiring adds or removes edges to reduce bottlenecks:

• SDRF (Stochastic Discrete Ricci Flow): adds edges around the most negatively curved edges — edges with negative curvature are bottlenecks
• DIGL: adds edges between nodes with high personalized PageRank similarity
• CurvDrop: removes edges with high negative curvature (bottlenecks) and adds long-range connections

Other approaches:

• Global attention (Graph Transformers): bypasses all bottlenecks — every node attends to every node directly
• APPNP: personalized PageRank allows distant information to flow via many paths simultaneously
• Virtual node: add a single virtual node connected to all other nodes, providing a global communication channel

Curvature and Oversquashing

Topping et al. (2022) connected oversquashing to a notion of discrete Ricci curvature. They introduce the balanced Forman curvature \(\mathrm{Ric}(u,v)\) of an edge — a combinatorial quantity built from the degrees \(d_u, d_v\), the number of triangles containing \((u,v)\), and the 4-cycles through it. An edge is negatively curved when its endpoints share few common neighbours and few short cycles: locally, the edge is the only route between two otherwise separate regions.

The link to oversquashing runs through the Jacobian bound above. Their result is a conditional one, not a blanket guarantee: for a graph containing a sufficiently negatively curved edge, they prove an upper bound on \(\lVert \partial h_v^{(K)}/\partial x_u \rVert\) for pairs \(u,v\) on opposite sides of it, and show that a curvature-guided rewiring (SDRF) increases the curvature of the worst edges. That improves the bound; it does not prove that a trained model’s downstream accuracy must improve. What it does establish is the direction of the connection — from graph geometry (curvature) to information flow (oversquashing).

Summary

Oversquashing explains why GNNs fail on long-range reasoning tasks even when depth is not the bottleneck. Solving it requires either changing the graph (rewiring) or bypassing message passing altogether (Graph Transformers).

References

• Alon, U., & Yahav, E. (2021). On the Bottleneck of Graph Neural Networks and Its Practical Implications. ICLR 2021.
• Topping, J., Di Giovanni, F., Chamberlain, B. P., Dong, X., & Bronstein, M. M. (2022). Understanding over-squashing and Bottlenecks on Graphs via Curvature. ICLR 2022.
• Di Giovanni, F., Giusti, L., Barbero, F., Maschi, G., Lio, P., & Bronstein, M. M. (2023). On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology. ICML 2023.