On the Bottleneck of Graph Neural Networks and its Practical\n Implications

Since the proposal of the graph neural network (GNN) by Gori et al. (2005)\nand Scarselli et al. (2008), one of the major problems in training GNNs was\ntheir struggle to propagate information between distant nodes in the graph. We\npropose a new explanation for this problem: GNNs are susceptible to a\nbottleneck when aggregating messages across a long path. This bottleneck causes\nthe over-squashing of exponentially growing information into fixed-size\nvectors. As a result, GNNs fail to propagate messages originating from distant\nnodes and perform poorly when the prediction task depends on long-range\ninteraction. In this paper, we highlight the inherent problem of over-squashing\nin GNNs: we demonstrate that the bottleneck hinders popular GNNs from fitting\nlong-range signals in the training data; we further show that GNNs that absorb\nincoming edges equally, such as GCN and GIN, are more susceptible to\nover-squashing than GAT and GGNN; finally, we show that prior work, which\nextensively tuned GNN models of long-range problems, suffers from\nover-squashing, and that breaking the bottleneck improves their\nstate-of-the-art results without any tuning or additional weights. Our code is\navailable at https://github.com/tech-srl/bottleneck/ .\n