Venue: NeurIPS 2022 Workshop NeurReps

Reviews:

final_score: rating: 9: Technically flawless paper with excellent impact.
review_content: summary: The paper proposes a way so that the bottlenecks and over-squashing in the existing GNNs can be avoided. This is done by the addition of an extra GNN layer over the Cayley graph after a GNN layer on the input graph.
strengths_and_weaknesses: The work is novel and interesting. A thorough theoretical analysis is done that supports the claims made. The submission is clearly written and well organized. The results look interesting and can be used to overcome the problems of bottlenecks and over squashing in GNNs architectures.
questions: 1. While the paper gives a very detailed theoretical background, it would also be useful if it could provide an overview of more experimental results. 
2. For which other tasks than graph classification can the method be used? Are the experimental evidence available for those tasks as well?
limitations: Experimental results for other tasks could be shown. However it is a very well written paper.
recommended_decision: 3: Accept
review_title: Theoretical work on Expander Graph Propagation

final_score: rating: 8: Technically strong paper with novel ideas and high-to-excellent impact, and excellent evaluation and reproducibility.
review_content: summary: This paper studies the use of expander graphs in Graph Neural Networks (GNN). One would ideally seek methods that are capable of propagating information globally in a graph, that are protected from oversquashing, that are computationally efficient (subquadratic) in time and space, and that do not require dedicated processing of the input. The paper gives a thorough and well-explained introduction to expander graphs, to the eigenvalues of their Laplacians, to the Cheeger constant of a graph, to the diameter of a graph, and to the relationship between these concepts. The authors then propose expander graphs for use in GNNs in order to make steps towards the four ideal method properties mentioned above.
strengths_and_weaknesses: This paper is a well-explained introduction to the use of expander graphs in graphical neural networks (GNNs). The paper is clear and presented in an engaging manner. The results are precise and well-motivated. However, a downside is that the paper is mostly theoretical, and does not test the use of expander graphs in the application of GNNs to practical problems.
questions: Is there space in the paper, or in the appendix, to explain the over-squashing property more?

In the abstract you write "we theoretically demonstrate that ... are likely", and on the last sentence of the first page you write "We ... prove that the existence of negatively curved edges ... might in fact be required." I was surprised to see the soft words "are likely" or "might" in the description of a theoretical result or a proof. Why is this?
limitations: This is a theoretical paper without experimental tests on applied problems.
recommended_decision: 3: Accept
review_title: Review of Expander Graph Propogation

final_score: rating: 7: Technically solid paper, with moderate-to-high impact, and good-to-excellent evaluation and reproducibility.
review_content: summary: The paper proposes an efficient method for alleviating the over-squashing effects in GNNs by interleaving a GNN layer on the given graph input topology with a GNN layer over a Cayley graph of suitable dimension.
strengths_and_weaknesses: The main idea is interesting given the many desirable properties of expander graphs and will indeed avoid pre-computations (rewiring operations), be efficient and alleviate the over-squashing effect by `improving' the Cheeger constant. Empirical evaluation -- albeit not the most extensive one -- is also encouraging.

Weaknesses: It is not entirely clear what we lose by using a graph independent from topology and data to propagate messages and whether this is the most efficient way of alleviating the over-squashing. Indeed, the comparison with curvature only makes sense on a global scale but in general it is possible to have sparsity and positive curvature in "some" regions of the graph.
questions: It would be relevant to analyse a little the stability of this process. How sensitive we are to the depth (number of layers on the Cayley graph)? This question would also be important into addressing the issue of whether the improvement over baselines is truly deriving from long-range dependencies propagating better on the Cayley graph.
limitations: Yes.
recommended_decision: 3: Accept
review_title: Review of Expander Graph Propagation

Decision: Accept (Oral)