Source-linked AI summary
On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio', Michael Bronstein
TL;DR
Over-squashing in MPNNs remains less understood than other limitations, despite methods aimed at mitigating it. This theoretical work analyzes width, depth, and graph topology, finding that topology has the greatest impact and that over-squashing occurs among nodes with high commute time.
Problem
Over-squashing in MPNNs is less understood than other limitations, despite its causing node features to become insensitive to information at distant nodes.
Method
The paper theoretically analyzes how MPNN width, depth, and graph topology affect over-squashing, supported by experimental validation and an analysis of rewiring methods.
Results
Graph topology has the greatest impact on over-squashing, which occurs among nodes with high commute time; width can partly mitigate it, whereas depth generally cannot.
Takeaways & Limitations
Commute time provides a strong indicator of whether over-squashing is likely, independently of layer count, and the analysis justifies graph-rewiring approaches.
Takeaways & Limitations
The analysis strictly applies to MPNNs that weigh edge contributions equally up to degree normalization, while attention or gating mechanisms may either mitigate or amplify over-squashing.
Abstract
from arXiv · showhide
Message Passing Neural Networks (MPNNs) are instances of Graph Neural Networks that leverage the graph to send messages over the edges. This inductive bias leads to a phenomenon known as over-squashing, where a node feature is insensitive to information contained at distant nodes. Despite recent methods introduced to mitigate this issue, an understanding of the causes for over-squashing and of possible solutions are lacking. In this theoretical work, we prove that: (i) Neural network width can mitigate over-squashing, but at the cost of making the whole network more sensitive; (ii) Conversely, depth cannot help mitigate over-squashing: increasing the number of layers leads to over-squashing being dominated by vanishing gradients; (iii) The graph topology plays the greatest role, since over-squashing occurs between nodes at high commute (access) time. Our analysis provides a unified framework to study different recent methods introduced to cope with over-squashing and serves as a justification for a class of methods that fall under graph rewiring.
1. Introduction
The paper investigates how MPNN width, depth, and graph topology shape over-squashing, addressing gaps in prior theoretical understanding. It proves that width can partly mitigate the problem, depth may fail through vanishing gradients, and topology has the greatest impact through commute time.
- Motivation: Prior work leaves over-squashing less understood than expressivity and over-smoothing, especially regarding its causes and remedies.Open questions concern width, depth, graph spectrum, and topology beyond local curvature bounds.
- Scope: The study examines width, depth, and graph topology as the architectural and structural factors participating in over-squashing.The analysis aims to determine what can and cannot fix the phenomenon.
- Width: Width can mitigate over-squashing, but potentially at the cost of generalization, and experiments verify this result.This result is formalized in Theorem 3.2.
- Depth: Depth may not alleviate over-squashing: with layers comparable to graph diameter, distant nodes are likely to experience it.The paper establishes this behavior in Theorem 4.1 and validates the topology dependence experimentally.
- Depth: With an arbitrary large number of layers, MPNNs are generally dominated by vanishing gradients, including architectures with residual connections.Theorem 4.2 analytically characterizes conditions for vanishing loss gradients in a large class of MPNNs.
- Topology: Graph topology has the greatest impact: over-squashing occurs among nodes with high commute time, explaining why spatial and spectral rewiring methods alleviate it.The paper validates the commute-time relationship empirically and uses it to unify recent rewiring approaches.
2. Background and related work
MPNNs exchange messages locally through graph edges, which makes them efficient and effective for short-range dependencies but vulnerable to over-squashing over long distances. The background reviews curvature, spectral, spatial, and rewiring-based perspectives, motivating graph-topology analysis as a unified explanation.
- Message-passing paradigm: GNNs map graphs and node features to node-level or graph-level predictions, while MPNNs compute node representations by stacking message-passing layers.Each layer uses permutation-invariant aggregation and combines the current node state with neighbor messages.
- Message-passing paradigm: A graph shift operator restricts each layer’s message exchange to adjacent nodes, enabling short-range dependencies while exploiting graph sparsity.The operator has nonzero entries exactly on graph edges in the stated formulation.
- Over-squashing: Over-squashing arises because reaching distance r requires at least r layers while the receptive field can send exponentially many messages as r grows.This expansion can cause information loss and make node features insensitive to distant nodes.
- Existing theory: Earlier curvature-based analysis links over-squashing to high-negative-curvature edges but applies only to propagation up to 2 hops.The paper seeks a broader topology- and spectrum-based characterization.
- Rewiring: Recent remedies replace G with a rewired graph R(G) designed to improve connectivity, including spatial additions and spectral approaches.Rewiring is defined as exchanging messages on R(G), whose adjacency is R(A).
- Spatial methods: Spatial rewiring reduces graph distances but can densify the graph, increasing computational complexity and risking mixed local and non-local interactions.Higher-order structures may also require additional domain knowledge and computational overhead.
- Spatial methods: Diffusion operators based on adjacency powers access nonlocal hops but are not suited to mitigate over-squashing because they are implicated in the phenomenon.The paper distinguishes this from rewiring that changes graph connectivity.
- Spectral methods: The Cheeger constant measures graph connectedness, and a small value indicates communities separated by few edges where cross-community information may be over-squashed.Its relation to the smallest positive Laplacian eigenvalue motivates spectrum-dependent rewiring.
3. The impact of width
The analysis shows that increasing MPNN width can mitigate over-squashing, but this raises sensitivity globally and may harm generalization. Experiments on graph-transfer tasks confirm that larger hidden dimensions improve long-range performance across topologies.
- Theoretical analysis: Theorem 3.2 bounds feature sensitivity using the message-passing matrix, nonlinearity regularity, weight magnitudes, and hidden width.The analysis studies Jacobians after m layers and defines S_r,a := c_rI + c_aA as the adopted message-passing matrix.
- Theoretical analysis: Increasing hidden dimension can compensate for exponentially decaying message influence and mitigate over-squashing.The compensation is not topology-targeted because width, weights, and Lipschitz contributions affect sensitivity globally.
- Theoretical analysis: Larger width may increase over-fitting and poorer generalization by increasing the model’s overall contribution and sensitivity.Theorem 3.2 therefore identifies a trade-off between reducing over-squashing and making the whole network more sensitive.
- Empirical validation: Across CrossedRing, Ring, and CliquePath, higher hidden dimensions help GCN solve graph-transfer tasks at larger source-target distances.The experiments keep the number of layers equal to the source-target distance while varying hidden dimension.
4. The impact of depth
The paper shows that increasing depth does not generally resolve over-squashing. At depths comparable to graph distance, distant-node interactions remain squashed in topology-dependent ways; with many layers, vanishing gradients can dominate.
- Shallow-diameter regime: When depth is comparable to graph diameter, over-squashing occurs for sufficiently distant nodes, with the threshold depending on graph topology.Theorem 4.1 attributes the sensitivity threshold to model terms and graph quantities such as minimal degree and walk counts.
- Shallow-diameter regime: Topology orders the observed difficulty as CliquePath hardest, Ring intermediate, and CrossedRing comparatively easier across GIN, SAGE, GCN, and GAT.The same architecture can achieve perfect accuracy on some topologies, so the performance drop is not simply vanishing gradients.
- Shallow-diameter regime: The relevant topology-dependent sensitivity is captured more precisely by graph connectivity quantities than by distance alone.For graph-transfer topologies, effective resistance provides a better picture of topology’s impact than distance alone.
- Large-depth regime: If cσµ(c_r + c_a) < 1, loss gradients decay exponentially toward zero as the number of layers increases.This is a sufficient condition from Theorem 4.2 for vanishing gradients in a broad class of MPNNs.
- Large-depth regime: As depth increases, MPNNs generally transition from topology-dependent over-squashing to model-wide vanishing gradients.The large-depth regime can make the entire model insensitive rather than selectively improving long-range interactions.
5. The impact of topology
The analysis links over-squashing to graph topology through access and commute times, showing that high-time node pairs exchange information poorly independently of layer count. This yields a framework explaining why graph rewiring can mitigate the problem.
- 5.1. On over-squashing and access time: Access time measures the expected steps for a random walk to reach a node, while commute time includes the return trip.High access or commute time indicates that two nodes struggle to visit each other, depending on topology beyond simple distance.
- 5.1. On over-squashing and access time: The Jacobian obstruction increases with access time, so high-access-time pairs are less able to exchange information within the MPNN.The obstruction aggregates sensitivity contributions across all layers and includes an exponentially decaying error term.
- 5.1. On over-squashing and access time: Increasing the number of layers cannot fix the access-time obstruction, which remains independent of depth.This extends the depth analysis by showing that topology imposes a separate information-flow barrier.
- 5.2. On over-squashing and commute time: Nodes at small commute time exchange information better, whereas high commute time creates over-squashing when the task depends on their interaction.The commute-time result is expressed through a symmetric obstruction and applies in both directions between node pairs.
- 5. The impact of topology: The topology of the graph has the greatest impact on over-squashing, which occurs among nodes with high commute time.The commute-time obstruction is independent of the number of layers, up to errors decaying exponentially with depth.
- 5.3. A unified framework: A larger Cheeger constant decreases obstruction across node pairs, rigorously supporting rewiring methods that improve graph connectivity.Bounded-degree expanders are especially suited because their commute time is O(|E|), making the bound O(1) with respect to graph size.
- 5.3. A unified framework: Adding edges lowers effective resistance, providing a topological explanation for why spatial rewiring helps combat over-squashing.Commute time equals 2|E| times effective resistance, linking the random-walk and rewiring perspectives.
- 5.3. A unified framework: The commute-time and effective-resistance connection unifies spatial and spectral rewiring explanations.The analysis also relates bounded effective resistance to less-negative curvature under stated assumptions.
6. Conclusion and discussion
The paper concludes that width can partly mitigate over-squashing, depth generally fails as vanishing gradients dominate, and topology has the largest role. It also identifies model-class and analytical-scope limitations and leaves several methodological questions open.
- 6. Conclusion and discussion: Width can partly mitigate over-squashing, whereas depth generally fails because over-squashing spills into vanishing gradients.The paper identifies graph topology as the largest factor and commute or access time as a depth-independent indicator.
- 6. Conclusion and discussion: The analysis rigorously justifies why recently proposed spatial and spectral rewiring methods alleviate over-squashing.The conclusion presents this as a consequence of the topology-based framework.
- Limitations: The formal analysis applies strictly to MPNNs that weight edge contributions equally up to degree normalization.Attention and gating mechanisms may mitigate over-squashing through pruning, but can also amplify it by reducing useful pathways.
- Limitations: Theorem 5.5 holds in expectation, while the Jacobian obstruction generally represents average behavior rather than an exact refined analysis.A more refined analysis is left for future work.
- Where to go from here: The work does not determine which spatial or spectral rewiring method is preferable, when, or why.It also leaves the relationship between over-squashing and over-smoothing for future investigation.
B. Proofs of Section 3
The proofs establish sensitivity bounds for regular MPNNs by inducting over layers and tracking Jacobians of node features. These bounds show how architecture width and graph propagation affect information sensitivity.
- B. Proofs of Section 3: The appendix extends the sensitivity argument to a more general MPNN class that can stack multiple layers in aggregation.The main-document model is recovered by adapting the same inductive proof.
- B. Proofs of Section 3: The proof framework models MPNN layers using learnable update, residual, and message-passing maps with Lipschitz bounds.The formulation includes GCN, SAGE, and GIN under their respective adjacency normalizations.
- B. Proofs of Section 3: A small Jacobian derivative means that a node representation is first-order insensitive to information in another node's initial features.The proofs therefore use Jacobians to quantify information propagation through the network.
- B. Proofs of Section 3: Theorem B.1 bounds node-feature sensitivity after m layers using the update map and the propagated matrix expression (c_rsI + c_mpA)^m.The result is proved by induction on the number of layers.
C. Proofs of Section 4
The proofs of Section 4 sharpen sensitivity bounds for nodes separated by graph distance under symmetric normalization. They show that distance suppresses sensitivity, while unnormalized propagation requires an expected analysis.
- C. Proofs of Section 4: The appendix assumes symmetric normalization A = D^-1/2AD^-1/2 for the Section 4 bounds.The arguments extend to random-walk normalization because of matrix similarity.
- C. Proofs of Section 4: For unnormalized adjacency, expected sensitivity still becomes exponentially larger at smaller distances than at larger distances.Graph Transfer experiments confirm that GIN struggles with long-range dependencies, slightly more than GCN.
- C. Proofs of Section 4: Theorem C.1 provides a sharper distance-based bound that contains Theorem 4.1 as a special case.Its parameters include the activation Lipschitz constant, maximal weight entry, minimum degree, and maximal-length walk count.
- C. Proofs of Section 4: For nodes at distance r, the sensitivity bound excludes the first r terms because no walk connects them at shorter lengths.The remaining polynomial is then bounded using the normalized adjacency operator.
- C. Proofs of Section 4: The appendix completes the distance-bound proof through polynomial expansion and induction.The resulting argument establishes Theorem 4.1.
C.1. Vanishing gradients result
The analysis shows that sufficiently deep MPNNs become dominated by vanishing gradients, limiting gradients reaching earlier layers. The proof derives bounds using Lipschitz activations, bounded weight spectral norms, and Frobenius-norm control.
- C.1. Vanishing gradients result: Increasing the number of layers can cause gradients for weights entering earlier layers to vanish.Theorem C.2 establishes this for MPNNs with quadratic loss under Lipschitz activations satisfying σ(0) = 0 and bounded weight spectral norms.
- C.1. Vanishing gradients result: The proof rewrites the MPNN update using Kronecker products to bound the final-layer solution and the loss gradient.The argument uses the quadratic loss, Lipschitzness of σ, and σ(0) = 0.
- C.1. Vanishing gradients result: The gradient analysis bounds operator growth through the spectral norms of weight matrices and eigenvalues of the normalized graph operator.The largest singular value of a Kronecker product is bounded by the product of its factors’ largest singular values.
- C.1. Vanishing gradients result: The resulting bound depends on the Frobenius norm of the input node features through a constant independent of the number of layers.The proof absorbs ||H(0)||F into the constant C.
D. Proofs of Section 5
The proofs connect Jacobian sensitivity to graph spectral structure and effective resistance under a shared activation-probability assumption. Degree normalization removes a steady-state random-walk contribution, enabling bounds related to access time.
- D. Proofs of Section 5: Assumption D.1 treats all computation-graph paths as activated with the same success probability ρ.Expectations over derivatives are therefore averages over Bernoulli activation variables along paths.
- D. Proofs of Section 5: The proof expresses the graph operator through the spectral decomposition of the normalized Laplacian.The operator is written as Sr,a = crI + caD−1/2AD−1/2, with Laplacian eigenvectors and eigenvalues controlling the expansion.
- D. Proofs of Section 5: Effective resistance converts the spectral bound into commute time, linking the Jacobian obstruction to graph access between nodes.The proof uses 2Res(v, u)|E| = τ(v, u).
- D. Proofs of Section 5: Under cr ≥ ca and λn−1 < 2 for non-bipartite graphs, Sr,a is positive definite.This property supports the subsequent expected Jacobian-obstruction bound.
- D. Proofs of Section 5: Degree normalization removes a potentially diverging layer-dependent term proportional to node degrees.The removed term reflects the steady state of random walks rather than the information-propagation effect of interest.
E. Graph Transfer
The graph-transfer experiments test whether MPNNs can move a target’s one-hot feature to a distant source across three topologies. They use fixed source-target distance examples and vary hidden dimension while matching layers to distance.
- E. Graph Transfer: Ring, CrossedRing, and CliquePath transfer tasks require the source node to recover the target node’s feature.The topologies differ in their connectivity while preserving specified source-target distances.
- E. Graph Transfer: Figure 4 illustrates the three task topologies with source and target nodes separated by r = 5.Nodes marked S are sources and nodes marked T are targets.
- E. Graph Transfer: The experiments use p = 5 input dimensions, 5000 training graphs, and 500 test graphs per task.The target receives a random one-hot feature, making random guessing 20% accuracy.
F. Signal Propagation
The signal-propagation experiments isolate how graph topology affects information travel by comparing propagation distance with total effective resistance. Across four datasets and four MPNN architectures, lower resistance corresponds to farther propagation.
- F. Signal Propagation: The experiment measures whether total effective resistance is related to the ease of information propagation in MPNNs.A source node receives unit mass while all other nodes receive zero vectors, and propagation is evaluated over graphs from four datasets.
- F. Signal Propagation: Figure 5 compares information decay against normalized total effective resistance across PROTEINS, NCI1, PTC, and ENZYMES.The panels report GIN, SAGE, GCN, and GAT separately.
- F. Signal Propagation: Lower total effective resistance is expected to correspond to larger average propagation distance.Propagation distance is the average distance traveled by the initial unit mass relative to the source node.
- F. Signal Propagation: The experiments show that MPNNs propagate information farther when effective resistance is low.Random initialization and the absence of a training task isolate signal propagation from vanishing gradients.