On the Bottleneck of Graph Neural Networks and its Practical Implications
Authors: Uri Alon
Eran Yahav
Venue: ICLR 2021 Poster (2021)
Keywords: graphs
GNNs
limitations
understanding
bottleneck
over-squashing

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. 
Our code is available at https://github.com/tech-srl/bottleneck/ .

Published as a conference paper at ICLR 2021
ON THE BOTTLENECK OF GRAPH NEURAL NETWORKS AND ITS PRACTICAL IMPLICATIONS
Uri Alon & Eran Yahav
Technion, Israel
(urial verialon on, yahave] sresstechnion.eer
ABSTRACT
Since the proposal of the graph neural network (GNN) by Gor 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 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 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 over-squashin than GAT and GGNN; finally, we show that prior work, which extensively tuned GNN models of long- range problems, suffer from over-squashing, and that breaking the bottleneck improves their state-of- af-thh--rt results without any tuning or additional weights. Our code is available https:: / com/tech srl/bottleneck/
INTRODUCTION
Graph neural networks (GNNs) (Gori et al. 2005; Scarselli al., 20088] Micheli 2009) have seen sharply growing popularity over the last few years (Duvenaud et al.] 2015 Hamilton et al. 2017] Xuu et al. 2019). GNNs provide general framework to model complex structural data containing elements (nodes) with relationships (edges) between them. A variety of cal-world domains such as social networks, computer programs, chemical and biological systems can be naturally represented as graphs. Thus, many graph-structured domains are commonly modeled using GNNs.
GNN layer can viewed as a passsag-ppassing step (Gilmer et al. 2017), where each node updates its state by aggregating messages flowing from its direct neighbors. GNN variants (Li al. 2016 Veličković et al. 2018 Kipf and Welling 2017) mostly differ in how each node aggregates the representations of its neighbors with its own representation. However, most problems also require the interaction between nodes that are not directly connected, and they achieve this by stacking multiple GNN layers. Different learning problems require different ranges of interaction between nodes in the graph to be solved. We call this required range of interaction between nodes - the problem radius.
In practice, GNNs were observed for this phenomenon is over-smoothing: node representations become indistinguishable when the number of layers increases (Wu al. 2020). Nonetheless, over-smoothing was mostly demonstrated
benefit from more than few layers. The accepted explanation
in short-range tasks (Li et al. 2018 Klicpera et al.] 2018 Chen et al. 2020a; Oono and Suzuki
2020, IZao and Akoglu 2020 Rong et al.) 2020 Chen et al. 2020b) tasks that have small problem radiī where node's correct prediction mostly depends on its local neighborhood. Such tasks include paper subject classification (Sen et al. (2088) and product category classification (Shchur et al.) 2018) 8). Since the learning problems depend mostly on short-range information in these datasets, it makes sense why more layers than the problem radius might be extraneous. In contrast, in tasks that also depend long-range information (and thus have larger problem radii), we hypothesize that the explanation for limited performance is over vverssnuah.ng. We further discuss the differences between over-squashing and over-smoothing in Section 6

---

Published as a conference paper at ICLR 2021
Bottleneck
Bottleneck
input sequence
(a) The bottleneck of RNN seg2seq models
(b) The bottleneck of graph neural networks
Figure The bottleneck that existed in RNN seq2seq models (before attention) strictly more harmful in GNNs: information from node's exponentially-grove growing receptive field is compressed into a fixed-size vector. Black arrows are graph edges; red curved arrows illustrate information flow.
To allow node to receive information from other nodes radius of K, the GNN needs to have least K layers, or otherwise, will suffer from under-reaching these distant nodes will simply not be aware of each other. Clearly, to avoid under-reaching, problems that depend on long-range interaction require as many GNN layers as the range of the interaction. However, as the number of layers increases, the number of nodes in each node's s receptive field grows exponentially, This causes :verssquashin::: information from the exponentially- growiin receptive field is compressed into exed-length node vectors. Consequently, the graph fails to propagate messages flowing from distant nodes, and learns only short-range signals from the training data.
In fact, the GNN bottleneck is analogous to the bottleneck of sequential RNN models. Traditional seq2seq models (Sutskever et al., 2014) Cho et al.) 2014a suffered from a bottleneck at every decoder state the model had encapsulate the entire input sequence into fixed-size vector. In RNNs, the receptive field of node grows linearly with the number of recursive applications. However in GNNs, the bottleneck asymptotically more harmful, because the receptive field of node grows exponentially. This difference is illustrated in Figure
This work does not aim propose new GNN variant. Rather, our main contribution is introducing the over-squashing phenomenon novel explamation for the major and well-known issue of training GNNs for long-range problems, and showing harmful practical implications. We use a controlled problem to demonstrate how over-squashing prevents GNNs from fitting long-range patterns in the data, and to provide theoretical lower bounds for the required hidden size given the problem radius (Section 5). We show, analytically and empirically, that GCN (Kipf and Welling 2017) and GIN (Xu et al. 2019) are susceptible to over- sver-squashnn more than other types of GNNs such as GAT (Veličkovic et al. 2018) and GGNN (Li al., 2016)) We further show that prior work that extensively tuned GNNs to real-world datasets suffer from over-squashing: breaking the bottleneck using simple fully adjacent layer reduces the error rate by 42% in the QM9 dataset, by 12% in ENZYMES, by 4.8% in NCI1, and improves accuracy in VARMISUSE, without any additional tuning.
PRELIMINARIES
A directed graph G = (V,&) E) contains nodes V and edges E, where (u, v) E E denotes an edge from node u node For brevity, in the following definitions we treat all edges as having the same type; in general, every edge can have type and features (Schlichtkrull et al. 2018).
Graph neural networks Graph neural networks operate by propagating neural messages between neighboring nodes. At every propagation step (a graph layer): the network computes each node's ' sent message; every node aggregates received messages; and each node updates its representation by combining the aggregated incoming messages with its own previous representation.
Formally, each node is associated with an initial representation (0) E Rdo, This representation is usually derived from the node's label or its given features. Then, a GNN layer updates each node's
representation given its neighbors, yielding h()) Rd. In general, the k-th layer of a GNN is
2

---

Published as a conference paper at ICLR 2021
B
Figure 2: The NEIGHBORSMATCHH green nodes (A. B have blue neighbors and an alphabetical label. The goal is to predict the label (A, B, or C) of the green node that has the same number of blue neighbors as the target node ? in the same graph. In this example, the correct label is C, because the target node has two blue neighbors, like the node marked with C in the same graph.
parametric function fa that is applied to each node by considering its neighbors:
h h(Aa) fx (b!--1) (
(k-1) 0o)):
(1)
where N2 is the of nodes that have edges v: MG, (u E V (u, E). The total number of layers K is usually determined empirically as hyperparameter.
The design of the function is what mostly distinguishes type of GNN from the other. For example, graph convolutional networks (GCN) define f as:
h =
E (EueNiugo)
(2)
Cu.
where a is a nonlinearity such as ReLU, and Ca,u is a normalization factor often set to v [ N,,, or [Ne| (Hamilton et al. 2017). As another example, graph isomorphism networks (GIN) Xu et al. 2019 update a node's ss representation using the following definition:
(k) = MLP((A) ((1+ ( (k-1) +
> LEN, h(
Usually, the last (K (K-th) layer's output is used for prediction: in node pode-prediction, (K) is used to predict a label for e; in graph-prediction, a permutation-invariaat "readout" function aggregates the nodes of the final layer using summation, averaging, or weighted sum (Li et al. 2016).
THE GNN BOTTLENECK
Given graph G= (V, E) and given node v, denote the problem's 's required range of interaction, the problem radius, by r. r is generally unknown in advance, and usually approximated empirically by tuning the number of layers K. We denote the set of nodes in the receptive field of by ARK which is defined recursively as Nº := Nr, and NC == N U (w (w, u) E E A E N 7K--1p }.
When prediction problem relies on long-range interaction between nodes, the GNN must have as many layers K as the estimated range of these interactions, or otherwise, these distant nodes would be able interact. It is thus required that K 2 However, the number of nodes in each node's receptive field grows exponentially with the number of layers: |N O (exp (K)) (Chen et al. 2018). As a result, an exponentially- -gowiing amount of information squashed into hiee-length vector (the vector resulting from the Σ in Equations ( and (3)) and crucial messages fail to reach their distant destinations. Instead, the model learns only short-ranged signals from the training data and consequently might generalize poorly at test time.
Example Consider the NEIGhBORSM ATCH problem of Figure Green nodes A B have varying number of blue neighbors (O) and an alphabetical label. Each example in the dataset is different graph that has a different mapping from numbers of neighbors to labels. The rest of the
represents general, unknown, graph structure. The goal to predict label for the target node, which is marked with question mark
graph (marked as
?
according to its number of blue

---

Published as a conference paper at ICLR 2021
neighbors. The correct answer is C in this case, because the target node has two blue neighbors, like the node marked with C in the same graph. Every example in the dataset has a different mapping from numbers of neighbors to labels, and thus message propagation and matching between the target node and all the green nodes must be performed for every graph in the dataset.
Since the model must propagate information from all green nodes before predicting the label, bottleneck at the target node is inevitable. This bottleneck causes over-squashing. which can prevent the model from fitting the training data perfectly. We demonstrate the bottleneck empirically in this problem in Section 4 in Section we provide theoretical lower bounds for the GNN's hidden size. Obviously, adding direct edges between the target node and the green nodes, or making the existing edges bidirectional, could ease information flow for this specific problem. However, in real-life domains (e.g., molecules), we do not know the optimal message propagation structure priori, and must use the given relations (such as bonds between atoms) as the graph's 's edges.
Although this is a contrived problem, resembles real-world problems that are often modeled as graphs. For example, computer program in language such as Python may declare multiple variables (i.e., the green nodes in Figure 2 along with their types and values (their numbers of blue neighbors in Figure2) later in the program, predicting which variable should be used in a specific location (predict the alphabetical label in Figure 2 must use one of the variables that are available in scope based on the required type and the required value at that point. We experiment with this VAR MISUSE problem in Section 4.4
Short- vs. long-range problems Much of prior GNN work has focused on problems that were local in nature, with small problem radii, where the underlying inductive bias was that a node's most relevant context is its local neighborhood, and long-range interaction was not necessarily needed. With the growing popularity of GNNs, their adoption expanded to domains that required longer-range information propagation as well, without addressing the inherent bottleneck. In this paper, we focus on problems that require long-range information. That is, a correct prediction requires considering the local environment of node and interactions beyond the close neighborhood. For example, a chemical property of a molecule (Ramakrishnan et al., 2014, Gilmer et al. (017) can depend on the combination of atoms that reside the molecule's opposite sides. Problems of this kind require long-range interaction, and thus, large number of GNN layers. Since the receptive field of each node grows exponentially with the number of layers, the more layers over-squashing more harmful.
In problems that are local in nature (small r) the bottleneck is less troublesome, because GNN can perform well with only few layers (e.g., K-2 layers in Kipf and Welling (2017)), and the receptive field of node can be exponentially smaller. Domains such as citation networks (Sen et al. 2008), social networks (Leskovec and Mcauley| 20122), and product recommendations (Shchur et al. 2018) usually raise short-range problems and are thus nor the focus of this paper. So, how long is long-range? We discuss and analyze this question in Section
4 EVALUATION
First, we wish to empirically show that the GNN bottleneck exists, and find the smallest values of r that raise over-squashing We generated a synthetic benchmark that is theoretically solvable; however, in practice, all GNNs fail to reach 100% training accuracy because of the bottleneck (Section 4.1.. Second, we examine whether the bottleneck exists in prior work, which addressed real-world problems (Sections 4.2 to 4.4p
4.1 SYNTHETIC BENCHMARK: NEIGHBORSMATCH
The NEIGHBBRSMATCH problem (Figure 2 a contrived problem that we designed to provide an intuition to the extent of the effect of over-squashing, while allowing to control the problem radius r. and thus control the intensity of over-squashin. We focus on the training accuracy of a model, to show that over-squahhing prevents models from fitting long-range signals in the training set.
BEREHRREHHH From the perspective of a single node v. the rest of the graph may look like tree of height K, rooted at (Xu et al.) 2018 Garg et al.) 2020). To simulate this exponentially-growe receptive field, we created an instance of the general NEIGHBORSMATOOE problem that we described in Section 3 and portrayed in Figure] 2 We instantiated the subgraph in the
4

---

Published as a conference paper at ICLR 2021
middle of the graph (marked as in Figure 2 as a binary tree of depth depth where the green nodes are its leaves, and the target node is the tree's root. All edges are directed toward the root, such that information is propagated from all nodes toward the target node. The goal, as in Section 3 is to
predict a label for the target node, where the correct answer is the label of the green node that has the same number of blue neighbors as the target node. An illustration is shown in Figure [ in the appendix. This allows us to control the problem radius, i.e., r = depth. In this section we observe the bottleneck empirically; in Section 5 we provide a lower bound for the GNN's hidden size given r.
Model We implemented a network with r+1 graph layers to allow an additional nonlinearity after the information from the leaves reaches the target node. Our PyTorch Geometric (Fey and Lenssen 2019) implementation is available at pt : httpt/tttttb////// com/ wwann//ech-sseee wwwp///otteeeeeee Our
training configuration and hyperparameter ranges are detailed in Appendix
Results Figure 3 shows the following sur- prising results: some GNNs fail to fit the dataset starting from r=4. For example.
0.9
0.8
0.7
the training accuracy of GCN (Kipf and Welling, 2017) at 4= is 70%. At r=5, all GNNs fail to perfectly fit the data. Starting from r=4, the models suffered from over- squashing that resulted in underfitting: the bottleneck prevented the models from dis- tinguishing between different training ex- amples, even after they were observed tens of thousands of times. These results clearly show the existence of over-squashing, start- ing from r-4.
0.6
Acc
0.5
GGNN (train)
0.4
0.3
GAT (train)
0.2
GIN (train)
0.1
GCN (train)
0.34
0.09
0.08
2
3
5
6
8
r (the problem radius)
Figure 3: Accuracy across problem radius (tree depth) in the NEIGHBORSMATCH problem. Over-squashing starts to affect GCN and GIN even at r 4 4.
Why did some GNNs perform better than others? GCN and GIN managed to perfectly fit r=3 at most, while GGNN and GAT also reached 100% accuracy at r-4. This difference can be explained by their neighbor aggregation computation: consider the target node that receives messages in the r "th step. GCN and GIN aggregate all neighbors before combining them with the target node's 's representation; they thus must compress the information flowing from all leaves into a single vector, and only afterward interact with the target node's own representation (Fquations (2) and (3) In contrast, GAT uses attention to weight incoming messages given the target's 's representation: at the last layer only, the target node can ignore the irrelevant incoming edge, and absorb only the relevant incoming edge, which contains information flowing from half of the leaves. That is, a single vector compresses only half of the information. Since the number of leaves grows exponentially with it is expected that GNNs that need to compress only half of the information (GGNN and GAT) will succeed an r that is larger by 1. Following Levy al. (2018), hypothesize that the GRU cell in GGNNs filters incoming edges as GAT, but perform this filtering as alement-wise attention.
If all GNNs have reached low training accuracy, how do GNN-based models usually do fit the training data in public datasets of long-range problems? We hypothesize that they overfit short- range signals and artifacts from the training set, rather than learning the long-range information that was squashed in the bottleneck, and thus generalize poorly at test time.
4.2 QUANTUM CHEMISTRY: QM9
We wish to measure over-squashing in existing models. But, how can we measure over-squashing? Instead, we measure whether breaking the bottleneck improves the results of long-range problems.
Adding a fully-adjacent layer (FA) In Sections 4.2 to we took extensively tuned models from previous work, and modified adjacency in the last layer: given a GNN with K layers, we modified the K-th layer to be a fully-adjacent layer (FA). A fully-adjacent layer is a GNN layer in which every pair of nodes is connected by an edge. In terms of Equations (1) to (3). converting an existing layer to be fully-adjacen
means that Af. = V for every node V, in that layer only. This does not change the type of layer nor add weights, but only changes adjacency of a data sample in a single layer. Thus, the K 1 graph layers exploit the graph structure using their original sparse topology, and only the
5

---

Published as a conference paper at ICLR 2021
R-GIN
R-GAT
GGNN
Property
base
+FA
base
+FA
base
+FA
2.64.t0.11
2.54=000
2.68
2.73
3.85
3.53
alpha
4.65-10.52
2.28
4.65.10.44
2.32.10.16
5.22
2.72.10.12
HOMO
1.42.Lo.01
0.02
1.48.10.03
1.43-10.02
1.67-Lo.07
1.45.10.04
LUMO
1.50.L0.09
1.34
1.53.1:007
1,41-10.03
1.74.10.06
1.63-L0.06
gap
2.27=t0.09
1.96=0.04
2.30
2.08
2.60
2.30=:0.05
R2
15.63
12.61=0.37
52.39 42.5
15.76
35.94-135.77
14.3
ZPVE
12.93=1181
5.33=0.36
14.87
5.98-
17.84+3.61
5.24
UO
1.88
2.21 0011
7.61
2.19
8.65
3.35
U
18.71++23.36
2.32
6.86+
2.11 10.10
9.24-+2.26
2,49
5.62+t0.81
2.26-0.19
7.64
2.27+
9.35++0.96
2.31
5,38:10.75
2.04-024
6.54
2.07
7.14:11.15
2.17::0.29
CV
3.53-L0.37
1.06
4.11
2.03
8.86
2.25
Omega 1.05:0.111
0.80
1,88
0.73
1.57:10.53
0.87
Relative:
-39.54%
-44.5%%
-47.42%
Table 1: Average error rates (5 runs + stdev for each property) the QM9 dataset. The best result for every property in every GNN type is highlighted in bold. Results marked with were previously reported by |Brockshmmdf (2020) and reproduced by us.
K-th layer is an FA layer that allows the topology-awar node-reprexentations to interact directly and consider nodes beyond their original neighbors. Hopefully, this would ease information flow, prevent over-squashing, and reduce the effect of the previously-exisee bottleneck. We re-trained the models using the authors' original code, without performing any additional tuning, to rule out hyperparameter tuning as the source of improvement. Statistics of all datasets can be found in Appendix D
We note that an FA layer is simple solution. Its purpose is merely to demonstrate that over-squashing in GNNs is so prevalent and untreated that even the simplest solution helps. Our main contribution not the solution, but rather, highlighting and explaining the over-squashig problem. This simple solution opens the path for a variety of follow-up improvements and solutions for over-squashing.
Data The QM9 dataset (Ramakrishnan et al. 2014 Gilmer et al. 2017 Wu et al. 2018) contains -130,000 graphs with - -88 nodes. Each graph is molecule where nodes are atoms, and undirected, typed edges different types of bonds between the atoms. The goal is to regress each graph to 13 real-valued quantum chemical properties such as dipole moment and isotropic polarizability.
Models We modified the implementation of Brockschmidt (2020) who performed extensive hyperparameter tuning for multiple GNNs, by searching over 500 configuration;; we took the same splits and their best-found configurations. For most GNNs, Brockschmidt found that the best results are achieved using K =8 layers. This hints that this problem depends on long-range information and relies on both graph structure and distant nodes. We re-trained each modified model for each target property using the same code, configuration, and training scheme as |Brockschmidt (2020), training each model five times (using different random seeds) for each target property task. We compare the "base" models, reported by Brockschmidt, with our modified and re-trained F+FA" models.
Results Results for the top GNNs are shown Table I The main results are that breaking the bottleneck by modifying single layer to be an FA layer significantly reduces the error rate, by 42% on average, across six GNN types. These experiments clearly show evidence for bottleneck in the original GNN models. Results for the other GNNs are shown in Appendix B due to space limitation.
Over-squashing or under-reaching? Barceló al. (202)) discuss the inability observe nodes that are farther away than the number of layers K. We denote this limitation under- reaching: for every fixed number of layers K, local information cannot travel farther than distance K along edges. So, was the improvement of the FA layer in Table [ achieved thanks to the reduction in over-squashing, or did the FA layer only extend the nodes' reachability and prevent under-neaching? To answer this, between any two nodes a graph. We found that the average diameter is 6.35 91, the maximum diameter is 10, and the 90' th percentile is 8, while most models trained with K K=8 layers. That
GNN node to
measured the graphs' diameter in the QM9 dataset the maximum shortest path

---

Published as a conference paper at ICLR 2021
NC11
ENZYMES
SeenProj
UnseenProj
No Struct
69.8
65.211.4
GGNN
base!
85.7
79.3+t1.2
+FA
86.3:1o.7
79.1
base
76.9111.9
59.51556
base
88.3
82,91u08
DiffPool
R-GCN
+FA
77.6.1:..
65.7
+FA
88.4+00.7
83.8+
base 76.0+:1.8
58.2+660
base 87.1
81.120.9
GraphSAGE
R-GIN
+FA
77.7
60.8+
+FA
87.5
81.7.112
base 76.41:1.7
38.91.577
base 86.9+t0.3
81.4+t0.7
DGCNN
GNN-MLP
+FA 7..8.11.5
42.815.3
+FA
87.3++0.2
81.2+t0.5
base! !
80.0
59.6+
base 86.91.0.7
81.2:1099
GIN
R-GAT
+FA
81.5
67.7+55.
+FA
87.9.11.
82.0
Table 2: Average accuracy (30 sudd-) on the biological datasets. i- previously reported by Errica et al. (2020).
Table 3: Average accuracy (5 runs:tstdev)
VARMISUSE. t previously reported by Brockschmidt (2020).
is, at least 90% of the examples in the dataset certainly did not suffer from under-reaching, because the number of layers was greater or equal than their diameter. We trained another set of models with 10 layers, which did not show improvement over the base models. We conclude that the source of improvement was clearly not the increased reachability, but instead, the reduction in over-squashing.
Can larger hidden sizes achieve similar improvement? We trained another set of models with doubled dimensions. These models achieved only 5.5% improvement over the base model (Appendix B.2), while adding the FA layer achieved 42% improvement using the original dimensions and without adding weights. Consistently, in Section 5 we present an analysis that shows how dimensionality increase is ineffective in preventing over-squashing
Is the entire FA layer needed? We experimented with using only a sampled fraction edges in the FA layer. As Appendix [B.3 shows, the fraction of added edges in the last layer correlates with the decrease in error. For example, using only half of the possible edges in the last layer (a "semi-addacent" layer) still reduces the error rate by 31.5% average compared to "base".
shows
If all GNNs benefitted from direct interaction between all nodes, maybe the graph structure not even needed? We trained another set of models (Appendix B.2)) where all K layers FA layers, thus ignoring the original graph topology; these models produced 1500% higher (worse) error.
4.3 BIOLOGICAL BENCHMARKS
Data The NCI1 dataset Wale et al. 2008) contains 4110 graphs with -30 nodes on average, and its task to predict whether a biochemical compound contains anti-lung-cancer activity. ENZYMES (Borgwardi et al. 2005) contains 600 graphs with ~36 nodes on average, and its task is to classify an enzyme to one out of six classes. We used the same 10-folds and split as Errica et al. (2020).
Models We used the implementation of Eirrica et al. (2020) who performed fair and thorough comparison between GNNs. The final reported result is the average random seeds). Additional training details provided in Appendix C
test runs (10 foldsx3
In ENZYMES, Errica et al. found that a baseline that does not use the graph topology at all ("No Struct") performs better than all GNNs. In NCII, GIN performed best. We converted the last layer into an FA layer by modifying the implementation of Errica et al., and repeated the same training procedure. We compare the "base" models from Errica et al. with our re-trained "+FA" models.
Results Results are shown in Table The main results are as follows: (a) in NCII, GIN+EA improves by 1.5% over GIN-base, which previously the best performing model; (b) in ENZYMES. where Errica et al. (2020) found that none of the GNNs exploit the topology of the graph, we find that GIN+FA does exploit the structure and improves by 8. 1.1% over GIN-base and by 2.5% over No Struct.
7

---

Published as a conference paper at ICLR 2021
On average, models with FA layers relatively reduce the error rate by 12% in ENZYMES and by 4.8% in NCII. These experiments clearly show evidence for a bottleneck in the original GNN models.
4.4 PROGRAMS: VARMISUSE
Data VARMISUSE (Allamanis al. 2018 a node-prediction problem that depends long-range information in computer programs. We used the same splits as Allamanis et al. (2018).
Models We the implementation Brockschmiidd (2020) who performed an extensive hyperpa- rameter tuning by searching over 30 configurations for each GNN type. The best results were found using 6- 10 layers, which hints that this problem requires long-range information. We modified the last layer to be an FA layer, and used the resulting representations for node classification. We used the same best found configurations Brockschmidi 2020) add re-trained each model five times.
Results Results are shown in Table 3 The main result is that adding an FA layer to all GNNs improves their SeenProjTess accuracy, obtaining new state-of-the-an of 88.4%. In the UnseenProjTest set, adding an an FA layer improves the results of some of most of the GNNs, obtaining a new state- of-the-art of 83.8%. These improvements are significant, especially since they were achieved on extensively tuned models, without any further tuning by us.
How LONG IS LONG-RANGE?
In this section, we analyze over- squashing combinatorially in the TREE-NHIGHBORSM.rCe We provide combinatorial lower bound for the minimal hidden size that a GNN requires to perfectly fit the data (learn 100% training accuracy) given its problem radius We denote the arity of such a tree by m (=2 in our experiments); the counting base as b=2; the number of bits in floating point variable as f=32; and the hidden dimension of the GNN, i.c., the size of node vector (A) as d.
600
Empirical min
problem.
Combinatorial min d
500
4.122
400
300
256
243
200
106
100
3
8
10
11
The problem radius r
A full tree of arity and problem radius redepth has m² green label-nodes. All (m") possible permutations of the labels {A, B, C. ...) are valid, disregarding the order of sibling nodes. Thus, the number of label assignments of green nodes is (m" (m")!/ (m!)""-) m- parent nodes, where the order of each of their m siblings can be permutated). Right before interacting with the target node and predicting the label, single vector of size d must encapsulate the information flowing from all green nodes (Equations (2) and (3) Such a vector contains d floating point elements, each of them is stored cases that this vector can distinguish between bf-d, The number possible cases that the vector can distinguish between must be greater than the number of different examples that this vector may encounter the training data. This requirement expressed Equation (4). Considering binary trees (m=2), and floating-point values of 3-22 binary (b=2) bits, get Equation (5):
Figure 4: Combinatorial and empirical lower bounds of the model dimension given the problem radius.
(there are m"
bits. Overall, the number of possible
brdd
(m))m TI
(m))
(4)
232-d
22
(2")!
(5)
'The analysis holds for GCN and GIN. Architectures that use the representation of the recipient node to aggregate messages, like GAT, need to compress the information from only half of the leaves in single vector. This increases the final upper bounds by up 1 and demonstrated empirically Section 4.1
8

---

Published as a conference paper at ICLR 2021
Since factorial grows faster than an exponent with constant base, small increase in r requires much larger increase in d. Specifically, for d=32 as in the experiments in Section 4.1 the maximal problem radius is as low r=7. That is, model with d==22 cannot obtain 100% accuracy for r>7
In practice, the problem worse; i... the empirical minimal higher than the combinatorial, because even if solution to storing some information in vector of certain size exists, gradient descent- based algorithm is not guaranteed to find it. Figure[4showw the combinatorial lower bound of d given r. We also repeated the experiments from Section [4.] and report the minimal empirical d for each value r. with r; for example, even d=-12 can empirically fit r=7 most.
r. As shown in Figure 4 the empirical and the theoretical minimal d grow exponentially
RELATED WORK
Under-reaching Barceló et al. (2020) found that the expressiveness of GNNs captures only small fragment of first-order logic. The main limitation arises from the inability of node to be aware of nodes that farther away than the number of layers K, while the existence of such nodes can be easily described using logic. We denote this limitation as under-reaching. Nevertheless, even when information is reachable within K edges, we show that this information might be over-squashed along the way. Thus, the over-squashing limitation described in this paper is tighter than under-reaching.
Over-smoothing As observed before, node representations become indistinguishable and prediction performance severely degrades as the number of layers increases. The accepted explanation to this phenomenon over-smoothing (Li et al. 2018 Wu al. 2020; Oono and Suzuki 2020). This might explain the empirical optimality of few layers in short-range tasks (c.g.. only K = layers in Kipf and Welling (017)) Nonetheless, some problems depend on longer-range information propagation and thus require more layers, to avoid under-reaching. We hypothesize that in long-range problems, the explanation for the degraded performance is over-squashing rather than over-smoothing. For further discussion of over-smoothing vs. over-squashing, see Appendix E
Avoiding over-squashing Some previous work avoid over-squashing by various profitable means: Gilmer et al. (2017) add "virtual edges" to shorten long distances; [Scarselli et al. (2008) add "supersource nodes"; and Allamanii (2018) designed program analyses that serve as 16 "shortcut" edge types. However, none of these explicitly explained these solutions using over-squashing, and did not identify the bottleneck and its negative cross- domain implications.
CONCLUSION
We propose a novel explanation to well known limitation in training graph neural networks: bottleneck that causes over-squashing. Problems that depend on long-range interaction require as many GNN layers as the desired radius of each node's receptive field. This causes an exponentially- growing amount of information to be squashed into a fixed-length vector. As result, the GNN fails to propagate long-range information, learns only short-range signals from the training data instead, and performs poorly when the prediction task depends on long-range interaction.
We demonstrate the existence of the bottleneck in a controlled problem, provide theoretical lower bounds for the hidden size given the problem radius, and show that GCN and GIN to over-squashing than GAT and GGNN. We further show that prior models of chemical, biological and programmatical benchmarks suffer from over-squashing by showing that they can be dramatically improved using a simple FA layer. We conclude that over-squashing in GNNs is so prevalent and untreated in some benchmarks that even the simplest solution helps. Our observations open the path for a variety of follow-up improvements and even better solutions for over-squashing.
susceptible
ACKNOWLEDGMENTS
We would like to thank Federico Errica and Mare Brockschmidt for their help in using their frame- works. We are also grateful (alphabetically): Chen Zarfati, Elad Nachmias, Gail Weiss, Horace He. Jorge Perez, Lotem Fridman. Moritz Plenz, Pavol Bielik, Petar Veličković, Roy Sadaka, Shaked Brody, Yoav Goldberg, and the anonymous reviewers for their useful comments and suggestions.

---

Published as a conference paper at ICLR 2021
REFERENCES
Miltiadis Allamanis, Mare Brockschmidt, and Mahmoud Khademi. Learning to represent programs with graphs. In International Conference on Learning Representations, 2018. URL hntps //openreview. net. nett/Eorumiid-BJOFF
Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2020. URL
net/ Let.:
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21 (suppl__ i47-i56, 2005.
Mare Brockschmidt. Gnn-film: Graph neural networks with feature-wise linear modulation. Proceed- ings of the 36th International Conference on Machine Learning, ICML, 2020.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In Proceedings of the Thirty-Fourth Conference on Association for the Advancement of Artificial Intelligence (AAAI), 2020a.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In International Conference on Machine Learning, pages 942-950, 2018.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pages 1725-177 1735. PMLR, 2020b.
Kyunghyun Cho, Bart van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: Encoder Encoder-decoder approaches. In Proceedings of SSSF-8, Eighth Workshop on Syntax, Semantics and Structure in Statistical Translation, pages 103-111, 2014a.
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint arXiv: 1408.0078 2014b.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, pages 2224-2232, 2015.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In International Conference on Learning Representations, 2020. URL http::///oppeeeeeeeeee net./ forum? d= 6NF
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Vikas K Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. arXiv preprint arXiv:2002.06157 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference Machine Learning-Volle Volume 70, pages 1263-1272. JMLR. org, 2017.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume pages 729-734. IEEE, 2005.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pages 1024-1034, 2017.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
10

---

Published as a conference paper at ICLR 2021
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2018.
Jure Leskovec and Julian J Mcauley. Learning to discover social circles in ego networks. In Advances in neural information processing systems, pages 539-547, 2012.
Omer Levy, Kenton Lee, Nicholas FitzGerald, and Luke Zettlemoyer. Long short-term memory as dynamically computed element-wise weighted sum. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 732-739, 2018.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural
networks. In International Conference on Learning Representations, 2016.
Alessio Micheli. Neural network for graphs: A contextual constructive approach. IEEE Transactions
on Neural Networks, 20(3):498-55 -11,,, 2009.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for
node classification. In International Conference Learning Representations, 2020. URL
htttps::/gpenreviee net teet//forum21d=111d02222
Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1:140022, 2014.
Yu Rong. Wenbing Huang. Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convo- lutional networks on node classification. In International Conference on Learning Representations, 2020.
net/ wtwp:rerwwwweeeeeeoeooo..u.aaa htt.//orrmmm...liixxk.......
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions Neural Networks, 20(1):61 2008
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pages 593-607. Springer, 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurIPS 2018, 2018.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. 2014.
In Advances Neural Information Processing Systems, pages
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Nikil Wale, Ian Watson, and George Karypis. Comparison descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Molcculenet: benchmark for molecular machine learning. Chemical science, 9(2):513-530, 2018.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
11

---

Published as a conference paper at ICLR 2021
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference Machine Learning, pages 5453-5462 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? In International Conference on Learning Representations, 2019. URL https
//openreview. net wtwprrvviwe..eet/ouuneemmmma EyGs E 61
Lingxiao Zhao and Leman Akoglu. Paimorm: Tackling oversmoothing in gnns. In International Conference on Learning Representations, 2020. httptt:s//pppeeeeeeeees//// net ffrmm?
ad=rkecllrtwF
Figure 5: An example of a TRID-NEIGHIBRRMMATO that is an instance of the general NEIGHI BORSMATCH problem that we examine in Section 4 The target node (?) is the root of tree of d (from the target node to the green nodes). The green nodes (A, B, ....) ...) have blue neighbors (O) and alphabetical label. The node B has single blue neighbor; the node C has two blue neighbors; and the node D has no blue neighbors; each other green node has another unique number of blue neighbors. The goal to predict a label for the target node ()) according to its number of blue neighbors. The correct answer is C in this example, because the target node has two blue neighbors, like the green node that is marked with C in the same graph. To make a correct prediction, the network must propagate information from all leaves toward the target node, and make the decision given a single fixed-sized vector that compresses all this information.
A TREE-NEIGHBORMMATCH TRAINING DETAILS
Data We created separate dataset for every tree depth (which equal r, the problem radius) and sampled up to 32,000 examples per dataset. The label of each leaf ("A", "B", "C" in Figure 2 represented as a one-hot vector. To tease the effect of the bottleneck from the ability of GNN to count neighbors, we concatenated each leaf node's 's initial representation with 1-hot vector representing the number of blue neighbors, instead of creating the blue nodes. The target node initialized with learned vector as its (missing) label, concatenated with 1 1-hot vector representing its number of blue neighbors. Intermediate nodes are initialized with another learned vector.
Model The network has an initial linear layer, followed by r ++ GNN layers. Afterward, the final target node representation goes through a linear layer and a softmax to predict its label. We experimented with GCN (Kipf and Welling 2017). GGNN (Li et al. 2016), GIN (Xu et al. 2019) and GAT (Veličkovié et al. 2018) as the graph layers.
In Section 4.
we used model dimensions of d-32. Larger values led to the exact same trend. We added residual connections, summing every node with its own representation in the previous layer to increase expressivity, and layer normalization which eased convergence. We used the Adam optimizer with learning rate of 10 decayed by 0.5 after every 1000 epochs without increase in training accuracy, and stopped training after 2000 epochs of no training accuracy improvement. This usually led to tens of thousands of training epochs, sometimes reaching 100,000 epochs.
12

---

Published as a conference paper at ICLR 2021
MLP
R-GCN
GNN-FiLM
Property
base
+FA
base
+FA
base
+FA
2.36=00.44
2.19=00.04
3.21
2.92-:0.07
2.38
2.26+00.0
alpha
4.27
1.92.10.06
4.22.10.45
2.14:10.08
3.75100111
1.93.10.08
HOMO
1.25.10.04
1.19
1.4510.011
1.37-10.02
1.22:10.07
1.11:1..01
LUMO
1.35.10.04
1.20
1.62.10.04
1.41-10.01
1.30.1.005
1.21
gap
2.04=0.05
1.82=0005
2.42
2.03+00033
1.96=0.06
1.79=0.07
R2
1..86=1.62
12.40=0.84
16.38:0.49
13.55+0..50
15.59=1.38
11.89
ZPVE
12.00=1666
0.68
17.4013.56
5.81+0061
11.00=0.74
4.68=0.49
UO
5.35
1.71
7.82+0.80
1.75++0.18
5.43++0.6
1.60
U
6.20++088
1.72-+0.12
8.24+1.25
1.88+00222
5.95+0.46
1.75+00.8
H
5.96+0.45
1.70
9.05+1.221
1.85++0.18
5.59+0.57
1.93+0.42
G
5.09
0.53
7.0011..51
1.76:1..15
5.17:1.113
1.77=10.05
CV
3.38
1.69
3.9310.48
1.90:1.077
3,46110.1
1.64
Omega 0.84
0.63-10.04
1.0210.05
0.75:10.04
0.98
0.69
Relative:
-40.3%%
-43.40%
-39.53%
Table 4: Average eπror rates and standard deviations the QM9 targets. Best result for every property in every GNN type highlighted in bold. Results marked with f were previously reported by Brockschmidf (2020).
To rule out hyperparameter tuning the source of degraded performance. experimented with changing activations (ReLu, tanh, MLP, none), using layer normalization and batch normalization, residual connections, various batch sizes, and whether not the same GNN weights should be "unrolled" over time steps. The presented results were obtained using the configurations that achieved the best results.
Over-squashing or just long-range? To rule out the possibility that the long-range itself pre- venting the GNNs from fitting the data, repeated the experiment of Figure B for depths 4 to 8, where the distance between the leaves and the target node remained the same, but the amount of over-squashing was in r-2. That is, the graph looks like connected to "chain" of length of up to 6, and the target node is at the other side of the chain. This setting maintains the long-rat mangg in the original problem, but reduces the amount of information that needs to be squashed. In other words, This setting disentangles of the effect of the long-range itself from the effect of the growing amount of information (i.e., from over-squashing) In this setting, all GNN types managed easily fit the data close 100% across all distances, showing that the problem is the amount over-squashing, rather than the long-range itself.
of depth-2, where the root is
B QM9 ADDITIONAL RESULTS
B. ADDITIONAL GNN TYPES
Because of space limitations, in Section 4.2 we presented results on the QM9 dataset only for R-GIN, R-GAT and GGNN. In this section, show that additional GNN architectures benefit from breaking the bottleneck using a fully-adjacent layer: GNN-MLP R-GCN (Schlichtkrull et al. 2018) and GNN-FiLM (Brockschmidt) 2020).
All experiments were performed using the extensively-tums -tune implementation of Brockschmidl 2020) who experimented with over 500 hyperparameter configurations.
Table Contains additional results for GGNN, R-GCN and R-GIN. As shown Table 4 adding an FA layer significantly improves results across all GNN architectures, for all properties.
B.2 ALTERNATIVE SOLUTIONS
Table shows additional experiments, all performed using GCN. base is the original model of Brockschmidh 2020) as in Table +FA is the model that we re- t--iriined with the last layer modified an FA layer.
13

---

Published as a conference paper at ICLR 2021
Property
base
+FA
2xd
All FA
2xFA
Penultimate FA
mu
3.21+0.06
2.92-+0.07
2.99+0.08
11.52
2.89+0.08
2.80-00.88
alpha
4.22:1:.445
2.14:10.08
3.571:0.00
9.19
2.23:10.04
2.1411.11
HOMO
1,4511001
1.37.1002
1.3611887
9.95
1.39
1.34
LUMO
1.62-10.04
1.4110.01
1.4310.04
19.13
1.42.10.04
1.37-10.02
gap
2.42+t0.14
2.03+0.033
2.33+0023
24.62
2.06
2.00=0.03
R2
16.38=0.49
13.55+0.50
18.440766
168.09
13.97=0.56
12.92=0.11
ZPVE
37,40+3.56
5,81
15.8+2.59
591.33
0.79
4.53=00.2
UO
7.82+-0.80
1.7540.18
7.604-2.07
188.59
1.90+10.1
1.98
U
8.24::1.25
1.88
7.65++1.51
189.72
1.71
2.05
9.05+1.21
1.85++0.18
8.67++1.10
191.11
1.83+0.11
1.73
G
1.00
1.76::0.15
2.90#1.15
173.68
1.93:0.11
1.96=:0.2
Cv
3.93
1.90
3.99:0.07
64.18
1.9010.14
1.83
Omega 1.02:10.05
0.75
1.03:0.54
23.89
0.69
0.67
relative
0.0%
-43.40%
-5.50%
+5200%
-43.30%
-45.2%
Table Average error rates and standard deviations on the QM9 targets with GCN using alternative solutions.
2xd oddin is model that was trained with doubled hidden dimension size, d 256 instead of d = 128 as in the base model. As shown, doubling the hidden dimension size leads to a small improvement of only 5.5% reduction in error. In comparison, the +FA model used the original dimension sizes and achieves a much larger improvement of 13.40%
All FA is model that was trained with all GNN layers converted into FA layers, practically ignoring the graph topology. This led to much worse results of more than 1500% higher error. This shows that the graph topology is important in this benchmark, and that direct interaction between nodes (as in a single FA layer) must be performed addition to considering the topology.
2x FA is model where the last layer was modified into FA layer, and additional FA layer was stacked on top of it. This led to results that are very similar to +FA.
Penultimate FA is model where the FA layer is the penultimate layer (the K 1-th), followed by standard GNN layer as the K-th layer. This led to results that are even slightly better than +FA.
base!
0.25
0,5x FA
0.75x FA
+FA (as in Table
Avg. error compared to base
-0%
-8.4%
-3.55%
-37.1%
-43.4%
Table 6: Average error rates and standard deviations on the QM9 targets with GCN, where only a fraction of the edges the FA layer.
B.3 PARTIAL-FA LAYERS
We also examined whether instead of adding "full fully-adjacent layer", we can randomly sample only a fraction of these edges. We randomly sampled only (0.25, 0.5, 0.75) of the edges in the full FA layer in every example, and trained the model for each target property 5 times. Table shows the results of these experiments using GCN. basel is the original model of Brockschmidt (2020) as in Table 4 +FA the model that we re-trained with the last layer modified to an FA layer. (0.25, 0.5, 0.75) FA the models
only fraction of the edges in the FA layer
used.
As shown Table 6 the full FA layer achieves the largest reduction in error (-43.4%), but even adding a fraction of the edges improves the results over the base model. For example, using only half of the edges (0.5x FA) reduces the error by 31.5%. Overall. the percentage used edges in the partial-FA layer is correlated with its reduction in error.
14

---

Published as a conference paper at ICLR 2021
C BIOLOGICAL BENCHMARKS TRAINING DETAILS
used the implementation Errica al. 2020) who performed fair and thorough comparison between GNNs, by splitting each dataset to 10-folds; then, for each GNN type they select configu- ration among grid of 72 configurations according to the validation set, finally, the best configuration for each fold trained three additional times, early stopped using the validation set, and evaluated on the test set. The final reported result is the average of 30 test runs (10-foldsx3). The final standard deviation is computed among the average results of each of the ten folds.
D DATA STATISTICS
D.1 SYNTHETIC DATASET: PRIB-NEIGHBORSMATCCH
Statistics of the synthetic TREE-NEIGHBORRMMTTCH dataset are shown in Table
Table 7: The number of examples, in our experiments and combinatorially. for every value of depth.
Total combinatorial: (2depth!) 2depth
depth
Training examples sampled
2
96
96
3
8000
> 3 105
4
16,000
3 10
5
32,000
> 1036
6
32,000
1090
7
32,000
10217
8
32,000
50909
D.2 QUANTUM CHEMISTRY: QM9
Statistics of the quantum chemistry QM9 dataset, as used in Brockschmidit (2020) are shown in Table 8
Table 8: Statistics of the QM9 chemical dataset (002))
RRamakrishnan et al.
2014 as used by Brockschmidi
Training
Validation
Test
examples
110.462
10,000
10,000
# nodes average
18.03
18.06
18.09
nodes
standard deviation
2.9
2.9
2.9
# edges average
18.65
18.67
18.72
edges standard deviation
3.1
3.1
3.1
D.3 BIOLOGICAL BENCHMARKS
Statistics of the biological datasets, used in Errica et al. (2020), are shown in Table
D.4 VARMISUSE
Statistics the VARMISUSE dataset, as used in Allamanis et al. (2018) and Brockschmidt (2020).
shown in Table TO
15

---

Published as a conference paper at ICLR 2021
Table 9: Statistics of the biological datasets, as used by Errica al. (2020).
NC11
Wale al.
2008
ENZYMES (Borgwardt et al.
2005)
examples
4110
600
classes
2
nodes- average
29.87
32.63
nodes standard deviation
13.6
15.3
edges average
32.30
64.14
edges standard deviation
14.9
25.5
node labels
37
Table 10: Statistics of the VARMISUSE dataset (Allamanis et al. 2018 as used by Brockschmidt (2020).
Training
Validation
UnseenProject Test
SeenProject Test
graphs
254360
42654
117036
59974
# nodes average
2377
1742
1959
3986
edges average
7298
7851
5882
12925
E DISCUSSION: WVER-SMOOTHING VS. WVER-SQUASHING
Although over-smoothing and over-squashing are related, they are disparate phenomena that occur in different types of problems. For example, imagine a triangular graph containing only three nodes, where every node has a scalar value, an edge to each of the other nodes, and needs to compute function its own value and the other nodes' values. The problem radius in this case r=1. As we increase the number of layers, the representations of the nodes might become indistinguishable, and thus suffer from over-smoothing. However, there will be no over-squashing in this case, because there is no growing amount of information that is squashed into fixed-sizes vectors while passing long-range messages. Contrarily, in the TREE- NEIGHBORSMATCH problem, there no reason for over-smoothing occur, because there
two nodes that can converge to the same representation. node in a "higher" level the tree contains twice the information than node a "lower" level. Thus, this is case where vver-squshhnng can occur without over over-smoothing.
16


Reviews:
[{"review_id": "x3fwQbHMTz", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overall, the paper identifies a well-known problem in GNN, that is how to incorporate long-range information into GNN computation. The papers propose that this is due to the \"over-squashing problem\", and provides some arguments and evaluation on this problem. However, I think the motivation is questionable and the solution is too simple.\n\n[Questionable motivation]\nIn Section 3, the paper starts the motivation as described in Figure 2. The paper argues that \"Since the model must propagate information from all green nodes before predicting the label, a bottleneck at the target node is inevitable\". However, this example seems trivial for a GNN to solve, and the argument does not make sense to me. \nIn Figure 2, by simply counting how many blue nodes are within a node's neighborhood, a one-layer GNN can trivially make a correct prediction. Consequently, the whole motivation of Section 3 sounds questionable to me. I think this example should be modified, or at least, explained in a clearer way.\nThe paper further utilizes NEIGHBORSMATCH as the synthetic benchmark. Unfortunately, this evaluation is not convincing to me since a simple GNN can work well based on my understanding above.\n\n[Too simple solution]\nIt is unclear to me why \"Adding a fully-adjacent layer (FA)\" is a good solution to the long-range problem. FA only changes the K-th layer without changing 1 ... K-1 layers. If the over-squashing problem (proposed in this paper) exist, then the input to FA should already severely suffered from the over-squashing problem as there are already K-1 layers computed. This way, it is unclear how FA can get rid of the problem (the paper claims that it can \"prevent over-squashing\"), as much of the useful information has already been \"squashed\" and cannot be recovered. \nThis is not to mention that FA is a very simple trick. To me the technical contribution is too small. I encourage the authors to proposing a more satisfying solution to the proposed over-squashing problem.\n\n[Omitted discussion]\nFinally, the paper fails to stress a straight-forward, widely used solution to the long-range problem: adding skip connections in GNN. Such a technique has been widely used in many GNN papers.", "extra_scores": {}, "extra_text": {}}, {"review_id": "q7iHI913Yop", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces the over-squashing problem in GNNs. The problem is more evident in the graph-structured data where both local neighbors and long-range interactions are required. The paper designs experiments to show that the existing extensively-turned, GNN-based models suffer from the over-squashing problem in long-range prediction tasks. It also shows the improvement of breaking this bottleneck by adding a fully-adjacent layer.\n\nDeveloping deep GNNs is a popular topic and attracts significant efforts. However, training a deep GNN may face with several problems. Besides the over-smoothing, this paper introduces a new type of bottlenecks: over-squashing. It happens when the GNN needs to pass the information of interactions from long-range neighbors. In this case, exponentially increased information is squashed into a fixed-length vector. I personally believe this bottleneck is quite crucial when we develop deep GNNs.\n\nThe overall quality and clarity of this paper are good. It clearly and detailedly explains the over-squashing in long-range problems, and distinguishes it from other similar bottlenecks. It also tries to show the existence of the over-squashing in four different types of datasets. The training details and results are also included. Meanwhile, to my best knowledge, this is the first paper that highlights and analyzes the over-squashing problem in GNNs in detail, and I believe this bottleneck is of vital importance when we design deep GNNs. Therefore, I think the originality and significance of this work are also quite high.\n\nThis paper proposes a solution to the over-squashing, which is to add a fully-adjacent layer to the extensively-tuned state-of-the-art model. By comparing the performance of the modified models and the state-of-the-art models in the four datasets mentioned above, we can clearly see an improvement in terms of the accuracy and the error rates. However, although the authors say that this solution is very simple and mainly for the demonstration purpose, I believe there may be a potential problem within this solution. When we add the fully adjacent layer to the original model, we actually change the data directly. That means the modified model and the original model are trained on different datasets. In this case, I am concerned that we cannot compare these two models directly.  Although the authors clarify that the improvement is not from the under-reaching by considering the graph’s diameter in the QM9 dataset, I am still not fully convinced that we can safely rule out the possibility that the improvement is simply because the changed data makes the tasks easier for GNNs. Since the paper shows the existence of the over-squashing by comparing the performance of these two types of models, I believe it would be much better and more convincing if it can propose a new solution that can avoid changing the data directly.\n\n\nOverall, this paper has the following pros and cons. I believe this paper is of high quality and clarity with supporting experiments and analysis. The bottleneck of over-squashing is also a new problem and worth considering when we develop deep GNNs. But the solution proposed by the authors may be potentially problematic and hence, weaken the results and the conclusions.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "bJOwcATcTar", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper identifies the inherent problem of over-squashing that exists in popular information propagation mechanism in GNN. The hidden dimension of a node vector is fixed while the amount of information need to be preserved can grow exponentially (vs linearly in RNN decoder) with the increase of the depth of the networks. This problem becomes critical when modeling long range interaction is required. Then, the paper provides a simple and intuitive solution which is shown to be effective on both synthetic and multiple real-world datasets.\n\nStrength:\n- The over-squashing problem is important and inherent in (most of if not all) existing information propagation mechanisms in GNN. Considering the prevalence of GNN, clearly identifying and analyzing the problem can significantly contribute to the community and potentially open a new direction of research.\n- The paper provides theoretically analysis on the bottleneck, and further analyzes the relationship of required depth and the hidden dimension, showing the simply increasing the hidden dimension will not solve the problem.\n- The paper provides a simple yet effective solution to mitigate the problem, supported by extensive empirical results on multiple datasets.\n\nMinor comments:\n- Though the baseline methods are relatively well-known, it is will be still be easier to follow if citations are provided when baseline approaches first appear, e.g., mentioning GGNN (Li et al 2016) and GAT (Velickovic et al 2018) at Page 4. These information is not available until Page 11.\n- In Section 4.1, in GAT soft-attention is used, thus the model adaptively combines information from adjacent edges, rather than only consider half of them (which may require hard-attention).", "extra_scores": {}, "extra_text": {}}, {"review_id": "YSRsPCPe-Wp", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors identify the 'over-squashing' issue of GNNs. Specifically, the contributions include: 1) highlighting this ‘over-squashing’ bottleneck that affects the representation ability of GNNs; 2) Experiments on both synthetic data and real-world to validate their hypothesis. In general, the paper is structured well and easy to follow. However, there’re a few questions the authors need to address:\n\nFirst, the differences between over-smoothing and over-squashing has not been discussed thoroughly. Though the authors provide a paragraph in Sec. 6 to bring up the similarity between these two problems, it is not clear what are the actual differences between them. I suggest the authors to provide more explanation or experimental results to validate they are indeed different problems. In addition, the authors mention ‘bottlenecks’ in a few places of this paper but do not provide an explicit definition of this 'bottleneck`' thus it is unclear to readers what it indicates.\n\nAlso, I suggest the authors provide more rationale on why making the graph to be fully connected in the last layer of GNN can break the bottleneck introduced by this over-squashing issue. It is interesting to see multiple GNNs perform better by introducing this change, but it would be better if the authors can elaborate on the insights behind adopting this technique.\n\nIt is good to see the authors attempt to validate their hypothesis by first using a synthetic dataset, I suggest the authors to further justify why it is the over-squashing issue that makes the GNNs fail to perform well when the number of layer increases. There can be multiple reasons that GNNs fail in this case, e.g., over-smoothing, and analyzing why these models fail helps readers better understand the motivation of conducting this synthetic data evaluation.\n\nFor the other experiments, one question is that why the authors use a different set of GNN implementations in the biological benchmarks (Sec. 4.3) rather than the implementation of Brockschmidt used in Sec. 4.2 and 4.4. I suggest the authors further justify the models used here.\n\nI also suggest the authors to revise the caption of Fig. 2 as it is unclear what ‘predict the label C’ means without checking the content in Sec. 3.\n\nIn summary, though the papers provide some interesting insights in introducing a fully-connected graph structure in the last layer of GNN. There are still issues the authors need to address.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Fj6eaf58CP", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper analyzes the problem bottleneck in graph neural network message passing, points out that the over-squashing issue results in poor performance in prediction tasks that depend on long-range information on the graph, proposes a simple solution that removes the topology in the last layer, experiments on 3 different datasets, shows improvement over baselines and provides combinatorial analysis. \n\nStrength:\n1. The paper provides intuitive examples why long range information is needed in some tasks and why the message passing bottleneck is happening\n2. The proposed method (FA) is tested on 3 datasets with multiple bench marks. The results look promising.\n3. The combinatorial analysis provides insights on how the bottleneck is limiting GNN and the max depth that a GNN can perfectly fit.\n\nWeakness and suggestions:\n1. The paper brings up short vs long-range problems. However, there's no clear definition of what is a short vs. long-range problem. Can you provide a more formal definition of long range interaction on graph? How long is long range? Is there any quantitative measurement to decide that? Is this long range problem task-specific? data-specific? or a combination? \n2. In the experiments, the improvement for VarMisuse does not seem as impressive as the other two datasets. Can you provide some insights what is causing this difference in improvement?\n3. While the paper proposes a simple solution (FA) to the bottleneck problem, there's not much detail for readers to understand empirically or analytically the extent to which bottleneck issue is mitigated. The experiments do provide some justification and proof that the method would work, but maybe a way to directly measure that indeed more information is passed through is even better.\n4. I'm expecting to see more ablation studies or variations of the proposed method, e.g. how would the model perform if applying FA in layers other than the last? instead of a fully-adjacent layer, what about make 50%, or 75% of the nodes directly connected to the node beyond the original neighbor?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper identifies the phenomenon of oversquashing in GNNs and relate it to bottleneck. While this phenomenon has been previously observed, the analysis is new and insightful. The authors conclude that standard message passing may be inefficient in cases where the graphs exhibit an exponentially growing number of neighbors and long-range dependencies, and propose a solution in the form of a fully-adjacent layer. While the paper does not offer much methodologically, it is the observation of bottleneck that is of importance. 

We therefore believe that the criticism raised by some reviewers of the observation not being novel and the solution "too simple" rather unsubstantiated. The authors have well addressed these issues in their rebuttal. The AC recommends accepting the paper. 
Decision: Accept (Poster)