Abstract: 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.
Introduction: The Information Bottleneck
In a standard Graph Neural Network, nodes update their states by passing messages to their direct neighbors. To allow nodes that are $K$ hops away to interact, the network must be at least $K$ layers deep. However, empirical evidence shows that adding more layers to GNNs often degrades performance. Historically, the community has attributed this to over-smoothing—a phenomenon where node representations become indistinguishable after too many message-passing steps.
While over-smoothing explains failures in short-range tasks, it does not fully explain why GNNs fail on tasks that require long-range information, such as predicting a molecule's properties based on atoms at opposite ends of the structure. This paper identifies a distinct culprit: over-squashing. Because a node's receptive field grows exponentially with each added layer, trying to compress all that incoming information into a single, fixed-size vector creates a severe information bottleneck.
Over-squashing vs. Over-smoothing
It is crucial to distinguish over-squashing from over-smoothing. Over-smoothing is about representations converging to the same value, making them indistinguishable. Over-squashing, however, is about losing data due to compression. Crucial messages from distant nodes simply fail to reach their destinations intact because the graph topology forces too much information through a single node or edge. This can happen even if the resulting node representations remain distinct.
Theoretical analysis shows that the required hidden dimension size of a GNN must grow exponentially with the problem radius to avoid this bottleneck. Consequently, simply making vectors slightly larger is an insufficient solution for long-range tasks.
Methods and Synthetic Benchmarking
To isolate and measure the bottleneck effect, the authors introduced the Tree-NeighborsMatch synthetic dataset. In this task, a root node must predict a label based on information originating from leaf nodes. By increasing the depth of the tree (the "problem radius" $r$), the researchers can precisely control the amount of long-range information that needs to be squashed.
To demonstrate the impact of this bottleneck in real-world scenarios, the authors employed a diagnostic tool: the Fully-Adjacent (FA) layer. By modifying only the final layer of existing, extensively tuned GNNs to be fully connected (where every node connects to every other node), the network can bypass the multi-hop bottleneck right before making a prediction. This allows distant nodes to interact directly, effectively "breaking" the bottleneck.
Key Results
On the Tree-NeighborsMatch task, standard architectures like GCN and GIN fail to fit the training data perfectly once the problem radius reaches just 4 hops. While gated or attentive models like GGNN and GAT perform slightly better—likely because they can filter out irrelevant data—all models eventually succumb to the bottleneck as the radius increases.
In real-world benchmarks, the intervention of a single FA layer yielded massive improvements:
- Chemistry (QM9): The error rate was reduced by an average of 42% across six different GNN architectures without additional hyperparameter tuning.
- Biology (ENZYMES & NCI1): Error rates dropped by 12% and 4.8%, respectively.
- Program Analysis (VarMisuse): The model achieved a new state-of-the-art accuracy of 88.4%.
Conclusion
The success of the simple FA layer proves that existing GNN models were starving for long-range information lost in the graph topology bottleneck. While the FA layer is a blunt instrument with $O(N^2)$ complexity, its performance gains highlight over-squashing as a primary limiting factor in modern GNNs. Future architectural research should focus on more scalable solutions, such as dynamic edge-rewiring, to specifically address this bottleneck in long-range graph tasks.
Summary updated