Standard Graph Neural Networks (GNNs) rely on the message-passing paradigm: to update its own state, a node aggregates feature vectors from its immediate neighbors. To capture long-range dependencies across a graph, this process must be repeated over multiple layers, allowing information to travel hop-by-hop.
However, this iterative neighborhood exchange suffers from a fundamental geometric flaw. As the number of layers increases, the size of a node's receptive field—the neighborhood of nodes it draws information from—grows exponentially. Yet, regardless of how many nodes are in this neighborhood, their collective information must be compressed into a single, fixed-size vector representation.
This structural bottleneck is known as over-squashing. When a graph contains narrow paths, tree-like hierarchies, or highly dense clusters, signals from distant nodes are mathematically diluted or entirely lost before they can reach their destination.
O O O O (Exponentially growing neighborhood)
\ / \ /
O O
\ /
> O < (Structural Bottleneck)
/ \
O O (Fixed-size destination vector)
The Root Cause: Topology vs. Vector Capacity
To build intuition for why over-squashing happens, consider a hierarchical or tree-like graph structure, such as a river network or a corporate command chain. As highlighted by Hongjun Wang et al. in Accelerating flood warnings by 10 hours: the power of river network topology in AI-enhanced flood forecasting, information originating at distant leaf nodes must travel through a sequence of intermediate root nodes. Because the intermediate nodes use fixed-length vectors, they lack the capacity to preserve the cumulative details of an exponentially growing number of upstream paths.
Furthermore, standard message passing is inherently lossy due to what Rongqin Chen et al. term "message flow redundancy" in Redundancy-Free Message Passing for Graph Neural Networks. GNNs repeatedly process the same local information through backtracking and self-loops, causing distant signals to be completely overwhelmed by local noise.
Over-Squashing vs. Over-Smoothing
It is important to distinguish over-squashing from its famous sibling, over-smoothing:
- Over-smoothing occurs when a GNN has too many layers, causing all node representations across the graph to converge toward a uniform global mean. It is a loss of distinction.
- Over-squashing occurs when information cannot effectively pass through topological bottlenecks. It is a loss of long-range communication.
As explored in On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks, these two phenomena often pull architectures in opposite directions. Attempting to fix over-smoothing (e.g., via residual connections or normalization) does not inherently resolve the topological constraints that cause over-squashing.
Strategy 1: Global Attention and Graph Transformers
If the primary bottleneck is the graph's topology, the most direct solution is to bypass the topology altogether. Graph Transformers achieve this by decoupling the model's computational graph from the input graph's edges, allowing every node to attend to every other node.
An early implementation of this idea is GraphTrans, introduced by Paras Jain et al. in Representing Long-Range Context for Graph Neural Networks with Global Attention. GraphTrans applies a standard GNN stack to capture local structure, then passes the node embeddings to a permutation-invariant Transformer layer. By allowing all nodes to communicate directly in the final layers, the model prevents long-range context from being squashed through local bottlenecks.
Taking this further, the Spectral Attention Network (SAN) proposed by Devin Kreuzer et al. in Rethinking Graph Transformers with Spectral Attention treats the graph as fully connected from the start. To prevent the loss of structural identity, SAN injects the full spectrum of the graph Laplacian into the node features.
To make global attention scalable, the "GPS" framework developed by Ladislav Rampásek et al. in Recipe for a General, Powerful, Scalable Graph Transformer separates local message passing from global linear attention. This architecture preserves local structural inductive biases while maintaining an $O(N)$ computational complexity, allowing long-range information to flow across thousands of nodes without bottlenecking.
Strategy 2: Graph Rewiring
Instead of changing the neural network architecture, another school of thought alters the underlying graph structure itself. By adding virtual edges, we can create "information highways" that bypass bottlenecks.
Standard Graph: O --- O --- O --- O --- O
Rewired Graph: O --- O --- O --- O --- O
\_____________________/
(Virtual Edge)
For continuous-time evolving networks, Katarina Petrovic et al. introduced Temporal Graph Rewiring with Expander Graphs. This method uses expander graphs—sparse graphs with high connectivity properties—to link temporally distant nodes, drastically reducing the effective diameter of the network.
In spatial domains like fluid dynamics, high-density node clusters in refined meshes create severe communication bottlenecks. The authors of Adaptive Graph Rewiring to Mitigate Over-Squashing in Mesh-Based GNNs for Fluid Dynamics Simulations address this with AdaMeshNet. This framework dynamically inserts shortcut edges at specific layers based on a "rewiring delay score," ensuring that global physical interactions (like turbulence or boundary layers) can propagate across the mesh without being squashed by localized node density.
Strategy 3: Continuous Dynamics and Structural Encodings
A third approach involves changing how information propagates through time or space, treating the GNN as a continuous physical system.
In Port-Hamiltonian Architectural Bias for Long-Range Propagation in Deep Graph Networks, Simon Heilig et al. model information flow using the principles of energy conservation. By framing the network as a port-Hamiltonian system, the architecture balances lossless propagation with learnable dissipation. This prevents signals from washing out or squashing, enabling successful communication across networks that are thousands of layers deep.
Alternatively, we can mitigate over-squashing by providing the network with global structural awareness right at the input layer. If nodes already know their global positions, they rely less on deep message passing to infer long-range context. Or Feldman demonstrated this in Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings, proving that initializing node features with spectral decompositions of the graph Laplacian allows standard GNNs to capture global properties that are traditionally blocked by message-passing bottlenecks.