Source-linked AI summary
On the Bottleneck of Graph Neural Networks and its Practical Implications
Uri Alon, Eran Yahav
TL;DR
GNNs struggle with tasks requiring information from distant nodes, and the paper attributes this to over-squashing at a message-aggregation bottleneck. It demonstrates the phenomenon theoretically and empirically, finding that breaking the bottleneck improves long-range benchmark performance without additional weights or tuning.
Problem
GNNs have difficulty propagating and fitting information needed for long-range prediction tasks, while prior explanations focused substantially on over-smoothing in short-range settings.
Method
The paper introduces over-squashing, analyzes hidden-size lower bounds, compares GNN architectures, and replaces one sparse layer with a fully-adjacent layer to break the bottleneck.
Results
Breaking the bottleneck reduces error by 42% on QM9, 12% on ENZYMES, and 4.8% on NCI1, while improving VARMISUSE accuracy without additional tuning.
Takeaways & Limitations
Over-squashing is prevalent in long-range GNN benchmarks, and even a simple fully-adjacent layer can improve previously tuned models.
Takeaways & Limitations
The theoretical analysis applies to GCN and GIN, while GAT’s recipient-aware aggregation changes the corresponding radius bound.
Abstract
from arXiv · showhide
Since the proposal of the graph neural network (GNN) by Gori et al. (2005) and Scarselli et al. (2008), one of the major problems in training GNNs was their struggle to propagate information between distant nodes in the graph. We propose a new explanation for this problem: GNNs are susceptible to a bottleneck when aggregating messages across a long path. This bottleneck causes the over-squashing of exponentially growing information into fixed-size vectors. As a result, GNNs fail to propagate messages originating from distant nodes and perform poorly when the prediction task depends on long-range interaction. In this paper, we highlight the inherent problem of over-squashing in GNNs: we demonstrate that the bottleneck hinders popular GNNs from fitting long-range signals in the training data; we further show that GNNs that absorb incoming edges equally, such as GCN and GIN, are more susceptible to over-squashing than GAT and GGNN; finally, we show that prior work, which extensively tuned GNN models of long-range problems, suffers from over-squashing, and that breaking the bottleneck improves their state-of-the-art results without any tuning or additional weights. Our code is available at https://github.com/tech-srl/bottleneck/ .
1 INTRODUCTION
GNNs propagate information through stacked message-passing layers, but long-range tasks expose a bottleneck: exponentially expanding information must be compressed into fixed-size node vectors. The paper introduces over-squashing as an explanation for why distant information is difficult to learn and propagate.
- Message passing: GNN layers aggregate messages from direct neighbors, so distant-node interactions require stacking layers.The required interaction range is called the problem radius.
- Long-range challenges: Over-smoothing does not fully explain poor performance on long-range problems, because much prior evidence concerns short-range tasks.Short-range tasks can often be solved using only local neighborhoods and few layers.
- Long-range challenges: Long-range interaction requires enough layers to reach distant nodes, but each added layer makes the receptive field grow exponentially.This creates a tension between under-reaching and compressing increasingly large neighborhoods.
- Bottleneck: The GNN bottleneck is more harmful than the analogous RNN bottleneck because GNN receptive fields grow exponentially rather than linearly.Both settings compress information into fixed-size vectors, but the growth rate differs.
- Contributions: The paper demonstrates over-squashing, compares its susceptibility across GNN architectures, and shows that a simple bottleneck-breaking modification improves tuned long-range models.Reported error-rate reductions are 42% on QM9, 12% on ENZYMES, and 4.8% on NCI1, with improved VARMISUSE accuracy.
2 PRELIMINARIES
GNNs operate by repeatedly sending, aggregating, and transforming messages between neighboring nodes. Their variants primarily differ in the function used to combine neighbor information with each node’s representation.
- GNN message passing: At each propagation step, nodes compute messages, aggregate incoming messages, and update representations using their previous states.This message-passing process defines the basic operation of GNNs.
- Node representations: Each node begins with an initial representation derived from its label or given features, then updates it using neighboring nodes.The updates produce representations at successive layers.
- Layer definition: A GNN layer is a parametric function applied to each node using its neighbors, and the total layer count K is usually selected empirically.The neighborhood consists of nodes with edges directed into the node being updated.
- Architectural variants: The design of the aggregation function distinguishes GNN variants such as GCN and GIN.Different choices determine how neighbor representations are combined.
- Prediction: For node prediction, the final-layer representation is used to predict a node label; graph prediction instead applies a permutation-invariant readout over final node representations.Readout functions include summation, averaging, or weighted sums.
3 THE GNN BOTTLENECK
Long-range tasks require enough GNN layers for distant nodes to interact, but the resulting exponential receptive-field growth creates over-squashing. Information is compressed into fixed-length vectors, causing crucial messages to fail to reach their destinations.
- Required range: The problem radius r is the required interaction range, and a GNN needs at least K ≥ r layers to connect nodes at that range.Otherwise, distant nodes suffer from under-reaching and cannot interact.
- The bottleneck: As layers increase, each node’s receptive field grows exponentially, so an exponentially growing amount of information is compressed into a fixed-length vector.This compression is the GNN bottleneck known as over-squashing.
- Consequences: Over-squashing causes crucial messages to fail to reach distant destinations, leaving the model to learn mainly short-range signals from the training data.The paper links this behavior to poor generalization on tasks requiring long-range information.
- NEIGHBORSMATCH: NEIGHBORSMATCH requires propagating information from all green nodes to the target so it can match their blue-neighbor counts and predict the corresponding label.The task’s varying graph-specific mappings require this matching to be performed for every graph.
- NEIGHBORSMATCH: In NEIGHBORSMATCH, the target-node bottleneck can prevent the model from fitting the training data perfectly.The paper uses this controlled task to demonstrate the bottleneck empirically and analyze hidden-size lower bounds.
4 EVALUATION
The evaluation uses a controlled synthetic benchmark and prior tuned datasets to test whether over-squashing limits long-range GNN learning and whether modifying graph adjacency alleviates the bottleneck.
- 4.1 SYNTHETIC BENCHMARK: NEIGHBORSMATCH: The controlled NEIGHBORSMATCH benchmark varies problem radius to measure whether over-squashing prevents GNNs from fitting long-range training signals.The TREE-NEIGHBORSMATCH construction uses a binary tree whose depth directly controls the problem radius.
- 4.1 SYNTHETIC BENCHMARK: NEIGHBORSMATCH: At r=4, some GNNs stopped fitting the synthetic data; GCN achieved 70% training accuracy, and at r=5 all models failed to fit perfectly.The bottleneck prevented models from distinguishing training examples even after extensive repetition.
- 4.1 SYNTHETIC BENCHMARK: NEIGHBORSMATCH: GCN and GIN fit at most r=3, whereas GGNN and GAT reached 100% accuracy at r=4 because their aggregation can reduce the information compressed at the final step.GCN and GIN aggregate all incoming neighbors before combining them with the target representation, while GAT can use target-conditioned attention.
- 4.2 QUANTUM CHEMISTRY: QM9: The evaluation replaces only the final graph layer with a fully-adjacent layer, preserving earlier sparse graph layers without adding weights or further tuning.The modified final layer lets topology-aware representations interact directly beyond their original neighbors.
- 4.2 QUANTUM CHEMISTRY: QM9: 42% average error-rate reduction across six GNN types on QM9 and new state-of-the-art accuracies of 88.4% and 83.8% on VARMISUSE support a bottleneck in tuned models.The improvements were obtained without additional tuning; on QM9, the authors also found that increased reachability was not the source of improvement.
- 4.2 QUANTUM CHEMISTRY: QM9: Doubling hidden dimensions improved results by only 5.5%, compared with 42% from an FA layer, while using FA layers for all layers produced 1500% higher error.A semi-adjacent final layer still reduced error by 31.5% on average, showing that full adjacency was not required for the observed effect.
- 4.3 BIOLOGICAL BENCHMARKS: On biological benchmarks, FA models relatively reduced error by 12% on ENZYMES and 4.8% on NCI1.GIN+FA improved over GIN-base by 8.1% on ENZYMES and 1.5% on NCI1.
5 HOW LONG IS LONG-RANGE?
The paper derives combinatorial and empirical lower bounds on hidden dimension as problem radius increases, showing that fitting long-range signals requires rapidly growing representations.
- 5 HOW LONG IS LONG-RANGE?: The TREE-NEIGHBORSMATCH analysis derives a combinatorial lower bound on the hidden size needed to fit data perfectly at problem radius r.The tree has arity m, counting base b, floating-point precision f, and hidden dimension d.
- 5 HOW LONG IS LONG-RANGE?: A single vector of size d must encode the information arriving from all green label-nodes before the target node predicts.The vector distinguishes at most b^(f·d) cases when each of its d elements stores f bits.
- 5 HOW LONG IS LONG-RANGE?: GAT-like architectures can require less compression than GCN and GIN because they use the recipient representation during aggregation.The analysis states that GAT needs to compress information from only half of the leaves in a single vector, increasing the upper bound on r by up to 1.
- 5 HOW LONG IS LONG-RANGE?: For d=32, the maximal problem radius is r=7, so the model cannot reach 100% accuracy for r>7.This follows because the number of label assignments grows factorially with the radius, faster than the vector’s representational capacity.
- 5 HOW LONG IS LONG-RANGE?: The empirical and theoretical minimal d grow exponentially with r; even d=512 empirically fits r=7 at most.The empirical minimum exceeds the combinatorial bound because gradient descent is not guaranteed to find an available encoding.
6 RELATED WORK
The related-work discussion distinguishes over-squashing from under-reaching and over-smoothing, while noting that earlier architectural shortcuts addressed the issue without explicitly identifying its bottleneck.
- Under-reaching: Under-reaching occurs when nodes farther than K edges cannot be observed by a GNN with K layers.Over-squashing can occur even when information is reachable within K edges, making it a tighter limitation than under-reaching.
- Over-smoothing: Over-smoothing describes node representations becoming indistinguishable as layers increase, and it was mainly demonstrated on short-range tasks.This phenomenon helps explain why few layers can be empirically optimal for local problems.
- Avoiding over-squashing: Prior work used virtual edges, supersource nodes, or analytical shortcuts to shorten effective graph distances.These approaches did not explicitly explain their solutions through over-squashing or identify its cross-domain bottleneck.
7 CONCLUSION
The paper explains long-range GNN failures through over-squashing: a bottleneck compresses exponentially growing information into fixed-length vectors, limiting propagation and performance.
- 7 CONCLUSION: A bottleneck causes over-squashing when exponentially growing information is compressed into a fixed-length vector.The paper presents this as a new explanation for a well-known limitation in training GNNs.
- 7 CONCLUSION: Over-squashing can make GNNs learn short-range signals instead of propagating long-range information, harming tasks that depend on distant interactions.The conclusion reports this effect as a consequence of the bottleneck.
- 7 CONCLUSION: The paper finds that GCN and GIN are more susceptible to over-squashing than GAT and GGNN.It also reports that a simple fully-adjacent layer can improve prior long-range benchmark models without additional tuning or weights.
A TREE-NEIGHBORSMATCH – TRAINING DETAILS
The TREE-NEIGHBORSMATCH experiments vary tree depth and GNN architecture, then control long-range distance separately from the amount of information being squashed.
- Data: Each tree depth has a separate dataset with up to 32,000 examples, and leaf labels are encoded as one-hot vectors.Leaf representations also include a one-hot encoding of the number of blue neighbors to isolate the bottleneck from neighbor counting.
- Model: The model uses an initial linear layer, r+1 GNN layers, and a final linear layer with softmax prediction.Experiments compare GCN, GGNN, GIN, and GAT graph layers.
- Training: The training setup uses residual connections, layer normalization, Adam, learning-rate decay, and early stopping after prolonged accuracy stagnation.The reported configuration uses d=32 and a learning rate of 10^-3.
- Training: The study varies activations, normalization, residual connections, batch sizes, and weight unrolling to rule out hyperparameter tuning as the source of degraded performance.Results use configurations selected for training accuracy.
- Over-squashing or just long-range?: When long-range distance is held constant but over-squashing is reduced, all GNN types fit the data to nearly 100% across distances.This controlled setting supports over-squashing, rather than long-range distance itself, as the problem affecting the original experiment.
B.1 ADDITIONAL GNN TYPES
Additional GNN architectures also benefit from breaking the bottleneck with a fully-adjacent layer. Across architectures and properties, this modification improves results.
- GNN-MLP, R-GCN, and GNN-FiLM also benefit from breaking the bottleneck with a fully-adjacent layer.These architectures extend the results beyond R-GIN, R-GAT, and GGNN.
- Adding an FA layer significantly improves results across GGNN, R-GCN, and R-GIN for all properties.
B.2 ALTERNATIVE SOLUTIONS
Alternative solutions show that a fully-adjacent layer is more effective than simply enlarging hidden representations, while preserving graph topology and using only some added edges can still help.
- 43.40% improvement comes from +FA, compared with only a 5.5% error reduction from doubling the hidden dimension.+FA retains the original dimension sizes, whereas 2×d uses d = 256 instead of d = 128.
- Using all GNN layers as FA layers produces more than 1500% higher error, showing that graph topology remains important.Direct interaction must complement topology rather than replace it.
- Adding a second FA layer gives results very similar to +FA, while placing FA in the penultimate layer performs slightly better than +FA.
- -43.4% error is achieved with a full FA layer, while using half the edges still reduces error by 31.5%.The reduction in error correlates with the fraction of edges used in the partial-FA layer.
C BIOLOGICAL BENCHMARKS – TRAINING DETAILS
The biological benchmark experiments use a repeated cross-validation procedure that selects and retrains configurations separately for each GNN type and fold.
- Each dataset is split into 10 folds, and each GNN type selects one configuration from 72 grid configurations using validation data.
- The selected configuration for each fold is trained three additional times, early-stopped on validation data, and evaluated on the test set.The final result averages 30 test runs: 10 folds multiplied by 3 repetitions.
D.1 SYNTHETIC DATASET: TREE-NEIGHBORSMATCH
The paper distinguishes over-smoothing from over-squashing using contrasting graph problems: local dense graphs can smooth without squashing, while tree-based long-range problems can squash without smoothing.
- Over-smoothing and over-squashing are disparate phenomena that arise in different types of problems.
- In a three-node triangular graph with radius r=1, increasing layers may make representations indistinguishable without over-squashing.The receptive field does not grow while long-range messages are compressed.
- TREE-NEIGHBORSMATCH can exhibit over-squashing without over-smoothing because higher tree levels contain more information and nodes need not converge to identical representations.