Oversquashing
Oversquashing is a limitation of message-passing neural networks in which information from a large graph region must pass through a comparatively small representational channel. The resulting compression reduces the influence of distant input features on a node’s final representation, even when those features are relevant to the prediction task. The phenomenon occurs most prominently when a graph contains narrow cuts separating regions whose neighborhoods grow rapidly with distance.
Oversquashing is distinct from oversmoothing, although both effects can arise as the number of message-passing layers increases. Oversmoothing causes node representations to become progressively less distinguishable because repeated aggregation approaches a low-frequency equilibrium. Oversquashing instead concerns the amount of information that must be encoded and transmitted through intermediate nodes or edges. A network can therefore exhibit oversquashing while maintaining substantial representational differences among its nodes.
Message-passing formulation
A message-passing layer updates the representation (h_v^{(\ell)}) of a node (v) by combining its current state with messages from adjacent nodes:
[ h_v^{(\ell+1)}
\Phi_\ell \left( h_v^{(\ell)}, \operatorname{AGG} \left{ \Psi_\ell \left( h_v^{(\ell)},h_u^{(\ell)},e_{uv} \right) : u\in N(v) \right} \right). ]
Here, (N(v)) denotes the neighborhood of (v), while (e_{uv}) denotes information associated with an edge. The functions (\Phi_\ell) and (\Psi_\ell) are learned transformations, and the aggregation operator is invariant to the ordering of neighboring nodes.
After (L) layers, the representation of (v) depends only on nodes within its (L)-hop receptive field. In a graph with rapid neighborhood growth, the number of potentially relevant inputs increases exponentially with (L). Those inputs are compressed into vectors whose dimensionality usually remains fixed across layers. When many dependency paths converge on a small cut, the intermediate representations on that cut form an information bottleneck.
This mechanism differs from ordinary dimensional compression applied independently to individual observations. The compressed objects are structured messages whose effects must remain distinguishable after several nonlinear transformations. Information arriving from separate graph regions can become entangled before reaching the target node, causing the network to lose distinctions required by a long-range task.
Topological origin
The severity of oversquashing depends on how efficiently information can travel between separated graph regions. Consider a vertex set (S) containing many nodes relevant to a target (v). If most paths from (S) to (v) cross a small boundary, the boundary has to carry a quantity of dependency information that grows with the size of (S). Increasing network depth enlarges the receptive field but does not enlarge that boundary.
Trees provide a standard illustration. The number of nodes at distance (r) from the root grows exponentially when the branching factor exceeds one. Every signal from those nodes must nevertheless pass through the root’s immediate neighbors. A fixed-width hidden state at each neighbor consequently represents information originating from an exponentially expanding set of leaves.
The same structure occurs in graphs that are not trees. Community boundaries, bridge edges, and sparsely connected separators concentrate communication along limited routes. This concentration is described by concepts from graph expansion, conductance, and multicommodity flow. These concepts measure different aspects of the relation between graph volume and available transport capacity.
The connection with discrete Ricci curvature provides a local geometric description. Negatively curved regions commonly exhibit neighborhood expansion together with diverging shortest paths. When such paths are forced through a narrow local structure, message passing has limited capacity to preserve the influence of every source. Curvature does not by itself determine oversquashing, because the learned transformations and the prediction target also affect information transmission.
Sensitivity and Jacobian analysis
Oversquashing is quantified through the sensitivity of a target representation to a distant input. For nodes (u) and (v), this sensitivity is represented by the Jacobian
[ J_{vu}^{(L)}
\frac{\partial h_v^{(L)}}{\partial h_u^{(0)}}. ]
A small norm of (J_{vu}^{(L)}) indicates that changes at (u) have little effect on the representation computed at (v). Bounds on this norm typically contain powers of a normalized adjacency matrix or another graph propagation operator. They also contain factors derived from the derivatives of the learned transformations. The graph-dependent term records the number and weight of walks connecting the two nodes, while the transformation-dependent term records how strongly the network preserves perturbations along those walks.
A distant node can have low sensitivity even when many walks connect it to the target. The contribution of each walk is repeatedly normalized and mixed with contributions from other sources. Where a large collection of walks shares the same intermediate vertices, those vertices mediate a disproportionate fraction of the total dependency.
In 2023, You Watanabe introduced the route-load decomposition, which separated Jacobian attenuation caused by learned transformations from attenuation caused by shared graph corridors. The decomposition assigned each intermediate cut a load equal to the accumulated sensitivity of dependencies crossing that cut. Applied to transportation and molecular graphs, it distinguished long paths with distributed capacity from shorter paths concentrated through a single separator. The route-load formulation became one of several cut-based diagnostics used to compare architectures under equal hidden-state dimensionality.
The Jacobian account does not identify oversquashing with vanishing gradients. Vanishing gradients concern the propagation of optimization signals through computational depth, whereas oversquashing concerns the representation of many graph dependencies through restricted channels. The two effects interact because a compressed dependency can also produce a small training gradient, but neither condition logically requires the other.
Historical development
Uri Alon and Eran Yahav established the modern terminology in their analysis of bottlenecks in graph neural networks. Their work connected poor performance on long-range tasks with the exponential growth of receptive fields and the bounded size of node representations. This formulation separated the phenomenon from earlier accounts based only on insufficient depth.
Jake Topping, Francesco Di Giovanni, Benjamin Chamberlain, Xiaowen Dong, and Michael Bronstein subsequently related oversquashing to graph geometry through discrete curvature. Their analysis showed how negatively curved bottlenecks constrain information flow and how graph rewiring changes the relevant geometric structure. Later work expanded the analysis through spectral quantities, effective resistance, and commute-time geometry.
These developments shifted the theoretical emphasis from nominal receptive-field size to effective communication capacity. A node may lie inside the formal receptive field while exerting negligible influence on the computed output. Distance therefore describes accessibility, whereas sensitivity describes whether the accessible information survives aggregation.
Architectural responses
Graph rewiring alters the communication structure by adding edges or changing edge weights before message passing. Edges that cross a narrow separator create additional routes between regions and reduce the concentration of messages on the original bottleneck. Rewiring also changes the model’s inductive bias because the computational graph no longer coincides exactly with the input graph.
A virtual node supplies a shared communication channel connected to every ordinary node. Information can then move between distant regions without traversing every edge of the original graph. The virtual representation remains finite-dimensional, so it relocates the bottleneck rather than eliminating finite communication capacity.
Global attention mechanisms permit direct interactions between distant nodes. Their communication pattern avoids dependence on shortest paths in the original graph, although attention scores still compress many candidate interactions into finite representations. Sparse attention restricts these interactions according to a learned or predetermined connectivity structure.
Positional encodings augment node features with information derived from the graph’s global organization. They allow a model to distinguish nodes whose local neighborhoods are similar but whose structural locations differ. Such encodings reduce the need to reconstruct every global relation through repeated local aggregation, but they do not transmit arbitrary input-dependent information between distant nodes.
Higher-order graph networks represent subgraphs or tuples instead of representing only individual vertices. Their state space provides additional channels for relational information, while its computational size increases with the order of the represented structures. The oversquashing problem consequently becomes a capacity question over the lifted computational domain.
Relation to task structure
Oversquashing affects tasks whose outputs depend on interactions across graph bottlenecks. In molecular prediction, distant functional groups can influence a property through the structure connecting them. In algorithmic graph tasks, a local output can depend on reachability or on information distributed across a separator. In both settings, successful computation requires more than the inclusion of relevant nodes in a receptive field.
Tasks dominated by local evidence exhibit less sensitivity to the phenomenon because most relevant information originates near the prediction site. The same architecture can therefore perform differently on two datasets sharing similar graph statistics. The difference follows from which dependencies the target function requires, rather than from topology alone.
Oversquashing is consequently a joint property of the graph, the computational architecture, and the dependency structure of the target. Graph topology determines available routes, model design determines representational capacity along those routes, and the target determines which information must cross them. Analyses that omit any one of these components describe only part of the phenomenon.