Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper analyzes oversquashing in GNN using geometric methods. The paper proposes a novel rewiring method based on negative curvature to construct graphs that are less susceptible to oversquashing. Though the theoretical contribution is strong the empirical evidence is not strong. Overall a good paper. 
main_review: Overall the paper is well written, however, the paper improve further to have better readability. It would be helpful to have more intuitive clarity on the use of hyperbolic spaces since many readers may not be familiar with the topic. Throughout the paper, homophilic and hetherophilic nature of graphs are mentioned, however, the exact definitions of them are not clearly defined. Further, in experiments “low-homophily” is mentioned, but there is not measure for low or high homophily. I suggest that the authors provide a proper definition for homophilic/heherophilic as [1,2] and provide numerical measures for datasets used in experiments as in [1]  

The main weak point of the paper is experiments. First of all, is it fully-supervised node classification of semi-supervised node classification? The experiments are not substantial in terms of dataset selections, comparisons with baseline methods and obtained accuracy. 

a) The selected baseline methods are limited, can the authors use further baselines methods? Can the proposed graph rewiring method be compared with the +FA method in  [1]?

b) To my knowledge Cora is not a homophilic dataset [1]. It would be helpful if more datasets from hetherophilic graphs (Citeseer, Pubmed) are also considered in experiments, which would allow us to  have a better understanding of the over-squashing phenomenon.

c) Cornell, Texas and Wisconsin are small scale datasets. I suggest to experiments with Chameleon or/and Squirrel dataset, which have large number of nodes and dense graphs. 

d) Why are accuracies of Cornell, Texas, and Wisconsin low? There are methods that have shown greater accuracy for these datasets [1]. I wonder whether the low accuracy is due to the use of GCN and if a different GNN method is used in with the proposed rewiring method the accuracy would increase. Do authors have any experience with other models?  



References
[1] Eli Chien and Jianhao Peng and Pan Li and Olgica Milenkovic, Adaptive Universal Generalized PageRank Graph Neural Network,
International Conference on Learning Representations (2021)

[2] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gcn: Geometric graph convolutional networks.  International Conference on Learning Representations (2019)
summary_of_the_review: A good paper with a novel ideas on oversquashing in GNN. The main limitation of the paper is the limited of empirical support.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose a new graph rewiring approach that utilizes a discrete notion of Ricci curvature to mitigate over-squashing. This is motivated by a link between negatively curved edges and graph bottlenecks. The paper has a theoretical focus, but also provides a set of validation experiments to demonstrate the proposed approach.
main_review: Detailed comments:
- A critical aspect of rewiring is its effect on the structure and topological properties of the underlying graph. This is not captured by just analyzing the number of added/ removed edges across the graph. I think that it would be more useful to analyze graph characteristics (such as the node degree distribution) or to measure the distance of the original and the rewired graph globally, e.g., with a transportation distance. 
- Can you comment on the cost of curvature-based rewiring vs. random walk-based rewiring? If curvature-based rewiring is less efficient than random walk-based rewiring, is this (in your experiments) mitigated by a reduced cost in the downstream task (due to the smaller number of edges).
- In section 4 you briefly remark that curvature-based rewiring may reduce over-smoothing. I think it could be interesting to expand on that.

summary_of_the_review: I found the paper very interesting in that it analyzes the over-squashing problems through a new, geometric lens. The theoretical motivation for using curvature-based tools as opposed to random-walk-based rewiring is well-done. My main concern is that the authors’ notion of graph structure preservation is not convincing to me. The experiments could be more comprehensive. Please see detailed comments.
review_title: null

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: summary_of_the_paper:  The paper provides an analytical explanation for the over-squashing and GNN bottleneck phenomena. While Alon & Yahav (2020) demonstrated the over-squashing phenomenon empirically and provided mainly intuitions as to why it happens, this paper performs a deeper analysis and connects over-squashing to combinatorial curvatures. The paper shows that negatively curved edges are responsible for over-squashing. This is important because it allows to measure over-squashing, and pinpoint specific edges that are responsible for it in a given graph. 
Further, the paper proposes a method (called SDRF) to re-wire the graph based on these insights and shows empirically how this method alleviates over-squashing.

main_review: ## Strengths
* The paper provides good intuitions to over-squashing. This intuition is visualized in Figure 1 that gives a good intuition of over-squashing and of the proposed SDRF solution.
* Further, the paper provides a good connection to graph curvatures that allows to measure and analyze over-squashing.
* The paper provides a thorough analysis using the proposed notations and connects it to further geometric theoretical and classical ideas.
* The paper provides a good conceptual comparison to random-walk-based rewiring and whether this can address the GNN bottleneck, and also an interesting discussion about the likelihood of GNN bottlenecks in homophilic and heterophilic datasets.
* The evaluation shows that the proposed SDRF method outperforms the DIGL baseline without a significant increase in the amount of computation compared to the original graph structure, while the DIGL baseline adds an order of magnitude more edges, which increases the computation cost.

## Weaknesses

* Generality - I am not sure how do these results generalize beyond Graph Convolutional Networks (GCN). The use of GCN's augmented normalized adjacency matrix is assumed at the beginning of the paper, and this assumption is never questioned.
Are Lemma 1 and Corollary 2 correct only for GCN, where it is common to use the augmented normalized adjacency matrix? Specifically, this matrix has $D^{-1}$ which decays messages over paths. What happens if nodes are summed (as in GIN)? How does the signal then decay with the number of layers? Intuitively, I can understand that summing an exponentially growing number of nodes in a single vector cannot compress all the information after some compression steps (that is, GNN layers). But how is this expressed in the curvature theory? If the analysis in the paper refers only to GCN and GNNs which perform averaging, please mention this explicitly.

* Writing - as is, the paper can be perfectly understood only by audiences that are very familiar with all related work. The paper can be significantly improved by giving more background, explaining equations more intuitively, and avoiding unneeded citations which confuse the reader. For example, the paper uses the names such as "Ricci", "Poincare", "Ollivier", and "Forman" frequently. These references can confuse audiences who are not familiar with all terms and papers. Specifically, calling the main method "Balanced Forman", gives the reader the feeling that they would not really understand the proposed method without understanding the original Forman first. I believe that this is not the case, and that the paper *could* be standalone.
While the authors show an impressive understanding and familiarity with the related and classical work, I advise the authors to avoid this "name-dropping", in favor of better readability and accessibility to a broader audience.
I even think that some parts of the paper can be moved to the appendix, in favor of the readability of the remaining parts. For example, I am not sure that Corollary 2 is new (see below), and I'm not sure whether this is directly related to the point the paper tries to make, or whether is it a side-result.
See more specific details below.

* The Evaluation could also be strengthened by addressing more datasets and more GNN types.
See more details below.

* Reproducibility - please provide more training details, hyperparameters tuned and ranges, and the final selected hyperparameter values for the experiments in Section 5. A table of dataset statistics (in the appendix) can also help, before and after applying every type of preprocessing method (similarly to Table 3, possibly with absolute numbers as well).


## Writing

* Section 2.1: what is "$(i,j) \in E$ if $i \sim j$"? What does $i\sim j$ mean? Does it simply mean that there is an edge between them? If it only means that there is an edge between them, why is this a different notation than $(i,j) \in E$?

* What is $\hat{a}$ in Equation (1)? I cannot find its definition. Is it $\hat{A}$? It is unclear from the text.

* Section 2.1:
>"$d_{G}$ is the standard minimum-walk (geodesic) distance on the graph"

Is it simply the **shortest-path**? If so, I suggest using this term which is much more common to the broader audience. If not, the term "minimum-walk (geodesic) distance" should be better explained. 

* Section 2.1: 
> "the node features and representations are assumed to be scalar from now on"

that is, $p_0 = 1$ and all $p_l$ equal to 1?

* Corollary 2 - I think that the "Jumping Knowledge" paper (Xu et al., 2018) had already recognized this role of self-loops. What is the difference between this corollary and Theorem 1 in Xu et al. (2018)? Also, as the role of self-loops is not directly connected to the main contributions of this paper, I suggest considering moving it to the appendix, or removing it if it was already recognized by Xu et al, in favor of more space for explanations of other parts.

* Section 3, definition of $\lambda_{max}$ - what does "traversing the same node" mean? the same $k$ node from the previous definition of 4-cycles? A formal definition of $\lambda_{max}$ will be helpful.

* Section 3, the example describing Figure 3: I cannot understand the examples because in (ii), $\sharp_{\square}^{i}$ is defined for a specific edge $\sharp_{\square}^{i}(i,j)$, and here it appears as $\sharp_{\square}^{0}$ and $\sharp_{\square}^{1}$

Also, why is $\sharp_{\square}^{1}={5}$, and not also the node 0 is included, as it also creates a 4-cycle (1-0-3-5)?

* Corollary 4: what is "the volume of the geodesic balls", and what does growing "polynomially" exactly mean? How is the volume measured, and what does it grow over? (what is the "x axis"?)

* Theorem 5 - it would help if the authors could clarify this theorem, explain its meaning in words and intuitively. I am not sure I understand why every detail there is necessary, and what are its implications. 

* Cheeger constant (Equations (5)+(6)) - I did not really understand the notations in Eq. (5), what is the meaning of Equation (6), what is its significance?

##  Evaluation:
1. It would really improve the evaluation if the authors could experiment with more GNN types and more benchmarks. Specifically, if the authors could take the datasets and exact settings used in Alon & Yahav (2020) and show how the proposed SDRF method improves the results there. The reason that this would be helpful is that Alon & Yahav showed that these datasets already suffer from over-squashing, by taking existing source code of other papers and improving their results. It would be interesting to compare SDRF and the (computationally expensive) solution of Alon & Yahav in terms of the tradeoff between accuracy and computation cost (the overall number of added edges).

2. DIGL is compared to SDRF as the main baseline. However, I couldn't find what exactly does DIGL do. The paragraph about random-walk-based rewiring on page 7 does explain the general idea, but it is unclear whether this is explaining directly about DIGL, or in general about PageRank-style approaches?

## Additional questions to authors
* According to this analysis, in the authors' opinion, are over-squashing and over-smoothing the same thing or not? What is the difference between them? (The answer to this question will **not** affect the rating negatively, as it is obviously out of the scope of this paper)
If the authors have an insightful explanation, I recommend including it in the body of the paper.



### Other minor comments:
* The paragraph about Discrete curvatures on graphs on page 4 is completely unclear for the audience who are unfamiliar with the described curvatures. I suggest delaying this to later or even moving to an appendix in favor of more text that will help clarify the rest of the paper.

* Theorem 5(i) writes $\ell \in [0, L-1]$. For clarity, I suggest being consistent which previous notations, for example as Lemma 1 which denotes $0 \leq \ell \leq ...$.

summary_of_the_review: Despite my many comments, I think that this is an important paper, which deepens our understanding of the over-squashing phenomenon from a geometric perspective.
While many recent GNN papers introduce new application domains, new features, and new GNN architectures, this paper improves our understanding of the foundations of existing GNNs and their limitations, which is even more important.

I will increase my rating if the authors would answer all questions in the "Writing" section above, in the "Additional Questions" section above, and provide more evaluation datasets (as detailed in the "Evaluation" section above).

===== Update =====

I have increased my rating to 10, good work.

Note that Table 2 is now too wide and goes beyond the page's borders.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper, the authors work on the over-squashing effect that has been recently observed in the GCN literature, namely the effect that, in a message-passing paradigm and for a learning problem that necessitates long-range interaction between distant nodes, the existence of bottlenecks in the graph (for instance an edge e with very large betweenness centrality) will intuitively distort the information that needs to travel from distant nodes and thus hinder the GCN's performance.

One natural direction of research is to add edges (and sometimes remove others in order to keep the complexity under control) to alleviate the bottlenecks. This rewiring process may be done in different ways and the authors suggest one particular algorithm that they compare with state-of-the-art.

In particular, the contributions are:
- a precise (even if somewhat arbitrary) definition of an over-squashing measure between two nodes $i$ and $s$ that is simply the Jacobian of the node representation at $i$ with respect to the entry $x_s$. The smaller this measure, the less $i$ "feels" $s$, the larger the over-squashing effect. The goal of the paper is to find a way to understand how to alleviate the bottlenecks responsible for this effect

- to this end, the authors suggest a new definition of Ricci-like curvature defined over the edges of the graphs. This new definition has one main property which is theorem 3: it lower bounds the Ollivier curvature. This then enables to obtain Cor. 4, and finally the main result Thm 5, that states, in a nutshell, that negatively curved edges are the ones causing bottlenecks.

- a concrete rewiring algorithm is suggested, in which two steps are repeated until convergence or max iteration is reached: a first stochastic step is performed where an edge is added to alleviate the edge that has minimal curvature, before a deterministic step where the edge with maximal curvature (typically those in cliques) is removed if it is larger than a threshold

- a tentative analysis, in the form of Thm 8, as well as experiments show the authors' method performs as well or outperforms other rewiring methods (they mainly compare with DIGL) while keeping the number of total edges after rewiring under control
main_review: The paper is well-written and well-organized. Formalizing the concept of over-squashing is interesting and timely, and is of interest to the field. This paper, as is often the case when one delves into novel grounds, makes somewhat arbitrary choices in order to move forward: the definition of over-squashing is somewhat arbitrary, the choice of working with that particular definition of Ricci curvature could be more motivated. Efforts are however made in an interesting direction, and the several discussions around the Cheeger constant gives depth to the paper, and its main messages.

- minor: Appendices F and G are announced at the beginnning of the Appendix section but I did not have them in my pdf document

summary_of_the_review: This is novel work on a seemingly important effect hindering GCN performance in general. Giving a formal definition of over-squashing and providing an analysis based on curvature is novel work, and potentially very useful to the field.
review_title: null

Meta-review: The paper proposes a new technique to handle oversquashing in GNNs by introducing a novel rewiring technique. The reviewers are quite positive about the paper and the rebuttal phase greatly helped clarify the method and it's impact.
Decision: Accept (Oral)