Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.

[Questionable motivation]
In 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. 
In 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.
The 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.

[Too simple solution]
It 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. 
This 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.

[Omitted discussion]
Finally, 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.
review_title: Interesting observation but questionable motivation and too simple solution

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: 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.

Strength:
- 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.
- 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.
- The paper provides a simple yet effective solution to mitigate the problem, supported by extensive empirical results on multiple datasets.

Minor comments:
- 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.
- 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).
review_title: An important observation for GNN limitation with detailed analysis and a simple solution with impressive results

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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:

First, 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.

Also, 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.

It 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.

For 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.

I 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.

In 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.

review_title: R3

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

Developing 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.

The 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.

This 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.


Overall, 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.

review_title: This paper introduces a new bottleneck of GNNs: the over squashing. It analyzes this problem in detail with supporting experiments and results. This bottleneck is quite worthy of thinking when designing deep GNNs.

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

Strength:
1. The paper provides intuitive examples why long range information is needed in some tasks and why the message passing bottleneck is happening
2. The proposed method (FA) is tested on 3 datasets with multiple bench marks. The results look promising.
3. The combinatorial analysis provides insights on how the bottleneck is limiting GNN and the max depth that a GNN can perfectly fit.

Weakness and suggestions:
1. 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? 
2. 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?
3. 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.
4. 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?

review_title: simple solution to the bottleneck problem but more ablation studies or model variation could be added

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)