In standard convolutional neural networks (CNNs), expanding the receptive field is straightforward: you stack more layers. Each additional layer allows a pixel to integrate context from an exponentially larger neighborhood, enabling the network to learn hierarchical concepts from local edges to global structures.
When we try to port this intuition to Graph Neural Networks (GNNs) via neighborhood message passing, we hit a structural ceiling. To capture long-range dependencies between distant nodes, a GNN must stack multiple message-passing layers. However, as the network deepens to expand its receptive field, its performance typically collapses. This collapse is driven by two distinct but deeply intertwined phenomena: over-smoothing and over-squashing. Together, they form the receptive field bottleneck.
The Twin Failure Modes of Graph Depth
To understand why deep GNNs fail, we must look at what happens mathematically during message passing. In a standard GNN layer, a node updates its representation by averaging or summing the feature vectors of its immediate neighbors.
Over-Smoothing: The Loss of Local Identity
Message passing can be formalised as a form of Laplacian smoothing or diffusion across a graph. If you drop a token of ink into a bucket of water, it initially forms a highly concentrated, distinct pattern. Over time, molecular diffusion spreads the ink until the entire bucket turns a uniform, featureless gray.
In a GNN, node features act like that ink. As shown by Renjie Liao et al. in LanczosNet: Multi-Scale Deep Graph Convolutional Networks, repeated neighborhood aggregations cause node representations to converge toward a uniform state where they become completely indistinguishable from one another. When every node vector looks identical, the model loses the capacity to perform local node classification or edge prediction.
Over-Squashing: The Information Funnel
While over-smoothing describes the washout of features in the feature space, over-squashing describes an information bottleneck caused by graph topology.
Consider a node in a graph where every node has an average of $d$ neighbors. At layer $k$, this node is aggregating information from roughly $d^k$ nodes. In many real-world networks (like social or molecular graphs), this neighborhood grows exponentially. However, the target node must compress this exponentially expanding volume of information into a single, fixed-size hidden vector space. As Xuan Li et al. point out in Neural Atoms: Propagating Long-range Interaction in Molecular Graphs through Efficient Communication Channel, this fixed-size bottleneck forces the network to drop long-range signals, squashing distant context into noise.
Over-Squashing (Structural Funnel):
[ Exponentially Growing Neighborhood (d^k nodes) ]
\ /
\ / (Information compressed)
v v
[ Fixed Vector ]
Over-Smoothing (Feature Diffusion):
[ Distinct Node Features ] -> [ Message Passing ] -> [ Homogenized, Uniform Vectors ]
The Spectral Zero-Sum Game
For years, researchers treated over-smoothing and over-squashing as separate bugs to be fixed independently. However, recent theoretical insights reveal that they are two sides of the same coin, governed by the graph's underlying geometry and its Laplacian spectral gap.
The spectral gap measures how well-connected a graph is. A graph with a large spectral gap (like an expander graph) has high connectivity, meaning information can travel from any node to any other node in very few hops.
- To mitigate over-squashing, you want a large spectral gap so that information flows freely without getting stuck in local bottlenecks.
- However, as Konstantinos Skianis et al. demonstrate in On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks, increasing this connectivity accelerates the diffusion rate of the graph. This means a larger spectral gap causes node representations to homogenize much faster, inducing rapid over-smoothing.
This creates a fundamental zero-sum game. If you alter the graph topology to fix the information bottleneck, you accelerate the washout of local features. As Li Sun et al. argue in Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models, artificially inflating a graph's connectivity to bypass over-squashing directly triggers vanishing gradients and accelerated over-smoothing.
To break this deadlock, Adarsh Jamadandi et al. in Spectral Graph Pruning Against Over-Squashing and Over-Smoothing propose a counter-intuitive solution: selectively deleting edges. By strategically pruning the graph based on its spectrum, they balance the expansion properties that facilitate long-range communication against the diffusion rates that cause feature washout.
Architectural Solutions to the Depth Ceiling
To build graph models capable of true long-range reasoning, researchers have developed several paradigms that decouple the network's depth from its physical message-passing steps.
Multi-Scale and Spectral Filtering
Instead of relying on sequential local steps to reach distant nodes, multi-scale architectures compute low-rank approximations of the graph structure to allow single-hop communication across long distances.
For instance, LanczosNet leverages the Lanczos algorithm to efficiently calculate matrix powers of the graph Laplacian. This allows learnable spectral filters to capture both local details and long-range dependencies simultaneously without stacking dozens of layers. Similarly, Yuxuan Liang et al. introduce Digraph Inception Convolutional Networks, which utilizes Personalized PageRank within an Inception-style multi-scale framework to expand the receptive field on directed graphs while preserving local resolution.
Implicit Layers
Another approach is to move away from explicit layer stacking entirely. Bryan Hooi et al. introduce MGNNI: Multiscale Graph Neural Networks with Implicit Layers, which models feature propagation as an equilibrium point of an implicit function. By solving for the steady-state directly, the model captures infinite-depth global context at a constant memory cost, bypassing the layer-by-layer degradation of signals.
The Illusion of Depth via Residual Connections
A common practice to stabilize deep networks is adding residual connections. However, their role in GNNs is unique. In Analyzing the effect of residual connections to oversmoothing in graph neural networks, Dimitrios Kelesis demonstrates that residual connections do not make GNNs "deeper" in terms of feature abstraction. Instead, they force the model to behave like an ensemble of shallow networks.
By anchoring the hidden representations to the initial input features, residuals prevent over-smoothing by preserving local identity. However, this anchoring creates a secondary trade-off: it restricts the network's capacity to learn complex, non-local interactions, acting as a safety net that inadvertently limits the model's information reach. To make this anchoring more dynamic, Matthew Thorpe et al. propose GRAND++: Graph Neural Diffusion with A Source Term, treating the initial features as a continuous source term in a neural diffusion equation to balance global context with local signal stability.
Adaptive and Non-Uniform Receptive Fields
Graphs are rarely uniform; dense clusters over-smooth rapidly, while sparse regions suffer from "under-reaching" or data scarcity. Treating all nodes with a uniform propagation depth is fundamentally sub-optimal.
[Dense Cluster] --> Needs fewer hops to avoid Over-Smoothing
[Sparse Subgraph] --> Needs more hops to avoid Under-Reaching
To address this structural imbalance, Heesoo Jung et al. develop Dual Policy Learning for Aggregation Optimization in Graph Neural Network-based Recommender Systems. Their framework uses reinforcement learning to adaptively customize the aggregation depth (the number of hops) for individual nodes.
Alternatively, the architecture evaluated in Mixture of Scope Experts at Test: Generalizing Deeper Graph Neural Networks with Shallow Variants trains GNNs of varying depths as independent "scope experts." At test time, a gating mechanism routes each node to the expert that matches its local structural needs, ensuring that deep layers are only utilized when the benefit of long-range context outweighs the injection of neighborhood noise.
Key Foundational Work
LanczosNet: Multi-Scale Deep Graph Convolutional Networks (2019) — contributed 1 concept elements to this direction.
Every Node Counts: Self-Ensembling Graph Convolutional Networks for Semi-Supervised Learning (2018) — contributed 1 concept elements to this direction.
Rethinking Knowledge Graph Propagation for Zero-Shot Learning (2018) — contributed 1 concept elements to this direction.