Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper analyzes the redundancy problem in message passing in graph neural networks, and proposes a method to address this issue. Theoretical analysis and empirical verification are presented to justify the effectiveness of the proposed method.
The contributions can be summarized as follows:
1) Formulate and analyze the redundancy problem in message flows and suggest its impact on hindering the performance of GNNs.
2) Propose a redundancy-free GNN (RFGNN), and justify the superior expressive power of RFGNN in terms of addressing the over-squashing issue.
3) Show another advantage of RFGNN, i.e., capable of measuring the similarity between graphs in different granularity and detecting overlapping subgraphs.
4) Empirically verify the effectiveness of RFGNN through graph classification tasks on eight benchmark datasets by comparing with graph kernels and powerful GNNs.
strengths_and_weaknesses: Strengths:
1. This paper studies an important problem, i.e., the redundancy within the message passing flow, which is highly related to the performance of graph-level tasks where higher-order neighbors are important.

2. This paper is well organized, and the theoretical analysis is clearly presented. The redundancy problem is introduced and formulated strictly in the research context. 

3. This paper also analyzes the negative impact of message flow redundancies and connects it with the over-squashing phenomenon. The significance of this work is highlighted by showing its ability to address the over-squashing problem.

4. The expressive power of RFGNN is studied by 1) theoretical analysis and comparison with 1-WL, 2) empirical verification through experiments by comparing with graph kernels and power GNNs such as GIN, k-GNN, and CIN.

5. The proposed method shows other advantages in measuring graph similarity and detecting overlapping subgraphs.


Weakness:
1. It is said at the beginning of section 3 that “all proofs can be found in Appendix“, but there is no appendix attached.

2. The lack of illustrations/visualization during the analysis in Section 3 makes it difficult to catch the idea. For instance, on page 4, lines 133-139, this part can be illustrated with an example.

3. The results for baselines in Table 1 are reported from the original papers. However, the different configurations may result in different performance results of the baselines. In this paper, the experiment follows the configuration in the paper <How powerful are Graph Neural Networks>. The configurations between RFGNN and other baselines (e.g., Tree++) are not consistent.

4. The experiments are kind of simple. Only one graph classification experiment is presented. There are only five baseline methods, and around half of the baseline results are not available. And there are no explanations for the missing results.
questions: Questions:
1. As the paper described in section 6 (page 9: line 314),  the experiment is semi-supervised graph classification. But the experiment follows the configuration of <How powerful are Graph Neural Networks>, which conducts experiments with supervised graph classification tasks. Can you explain this inconsistency? And give more details of the semi-supervised learning in this experiment?

2. Why are most baseline results missing in Table 1?
limitations: 1. No appendix with proofs.

2. It is preferable to give instances during the theoretical analysis, so the readers can follow the idea easier.

3. The results in Table 1 are incomplete.

4. More experiments are needed to demonstrate the details of the learning of RFGNN.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work aims to eliminate the message flow redundancy in traditional message passing schemes so as to reduce the over-squashing issue. The authors first explain the redundancy in the computational graph of message passing and then theoretically quantify that the redundancy would cause the over-squashing issue. Based on these findings, the authors propose a message-passing GNN that is message flow redundancy-free and theoretically has better expressive power than 1-WL.

To empirically evaluate the performance of the proposed GNN (RFGNN), semisupervised graph classification tasks are done to compare RFGNN to several baselines. The results show that RFGNN in general exhibits better performance than the baselines.
strengths_and_weaknesses: Strengths:
1. The investigation of the message flow redundancy in message passing together with the over-squashing problem is novel. There are existing works related to the redundancy in message passing. However, they usually focus on reducing the computational complexity caused by redundant operations.
2. The authors conduct theoretical analysis when quantifying the effect of over-squashing and analyzing the expressive power of the proposed GNN. These analyses make the proposed method more solid.
3. The paper is generally easy to follow and well-written. The concepts and the proposed models are clearly explained.

Weaknesses:
1. The experiments are relatively weak compared to the theoretical part. The experiments need to be better designed to better demonstrate the performance of the proposed method. For example, the performance difference between the proposed RFGNN and the other baselines can be smaller than the stds as shown in Table 1, it would be necessary to confirm the statistical significance when comparing them. Besides, the results of GIN. k-order GNN, and CIN are not computed for Enzymes, BZR, Cox2 and DHFR in Table 1, thus the comparison is not comprehensive enough. 
2. There are existing works investigating the redundant computations in GNNs (e.g. Redundancy-Free Computation for Graph Neural Networks, KDD 2020). The authors should address these works in the Related Works section.
questions: I saw the height of the Truncated ePaths Forest (TPF) in RFGNN is 3 in experiments, how would the height affect the performance? Besides,  I'm not sure why the length of each epath should be larger than 2. Will the choice of 2 affect any analysis and the performance?
limitations: Since the proposed GNN is redundancy-free for the message flows, it would be interesting to investigate the computational complexity of the proposed model. If the model can reduce redundant computations and save memory/time, that can be also an advantage to be discussed.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: One challenge of conventional GNNs is the propagation of information between long-distance node / long-length paths. This paper argues the redundant aggregation of the same node/edge information attenuates the effect of features coming from long distance paths (Message Over-squashing). 
As a solution, Redundancy-Free Graph Neural Networks (RFGNN) are proposed. They are a variation of GNNs which is  redundancy-free.
This contribution also proposes a theoretical framework allowing to compare RFGNN with traditional WL-GNNs. In particular, it is shown that:
- The expressive powers of RFGNN can surpass the conventional GNNs (TPF Hashing is more powerful than WL-1).
- Over-squashing is reduced by de-redundancy.
Eventually, RFGNN is evaluated on graph classification tasks against several baselines (including GIN, k-GNN, and CIN) and on several bioinformatics datasets (NCI1, PTC, MUTAG, PROTEINS, ENZYMES) as well as 3 small molecules datasets (BZR, COX2, DHFR).
strengths_and_weaknesses: ## Strengths
 - I believe this work is very novel. It introduces a new type of Graph Neural Network as well as theoretical framework to analyze them.
 - The contribution is well written and of high quality. Given the space constraint, the contribution is relatively clear.
 - It seems that RFGNN achieves superior performance in graph discrimination than traditional GNNs and even k-order GNNs.

 ## Weaknesses
  - I believe that NeurIPS is not a good format for this contribution. 9 pages are just not enough to fit all the relevant information and the presentation of this paper suffers a bit from this. Therefore, if the paper is accepted, I would suggest to the authors to publish a longer version on arxiv that includes some of the appendices in the main text as well as spend a bit more time explaining the core idea of this contribution. This being said, I agree that such a contribution should be presented at NeurIPS.
  - The experimental evaluation feels a bit weak. It misses some scores (a lot of "-"). A longer discussion of the results would be welcome. According to me, not all baselines are equivalent and the main one should be the k-order GNN.
  - According to me, implementing the RFGNN is not trivial. Some explanation on how it is done would be welcome. Code is provided, though.

questions: - The TPF Hashing (TPFH) is compared to WL-1 test. Why not compare a TPFH with trees of height k with a WL-k test? Would they be the same?

- Shouldn’t k-Tree RFGNN be as powerful as a k-order GNN when learning is done appropriately?

- What is the blue color in the result Table? It is a bit misleading because RFGNN is the 3rd score and not the 2nd one.

limitations: Limitations are not discussed. No potential negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors aim to theoretically analyze the redundancy in GNNs and its practical implications, which is an interesting and important problem in the GNN community. To overcome the redundancy problem, the authors propose an expressive RFGNN based on the so-called Truncated ePath Tree. Experiments demonstrate that RFGNN outperforms existing models.
strengths_and_weaknesses: - Originality
  - The authors are the first to theoretically analyze the redundancy GNNs and its practical implications. Thus, the submission is certainly an original work.
  - The idea that using extended path to develop a redundancy-free message passing paradigm seems novel to me.
- Quality
  - This paper is well motivated. The authors did a good job in illustrating the redundancy problem in message passing and propose a reasonable solution to it.
  - This paper is technically solid. The authors rigorously analyze why redundancy causes message over-squashing. Besides, the authors provide theoretical analysis for the proposed method and show their method outperforms 1-WL test.
  - My major concern is the scalability of the proposed RFGNN. As shown in Table 1, in TPF, the average number of nodes/edges becomes at least ten times larger than that in the original graph. I am wondering if RFGNN is applicable to larger graphs such as ogbg-ppa and ogbg-code2.
- Clarity
  - The writing of this paper is overall clear. My only complaint is about Figure 1. It looks confusing to me and the authors may want to give a more clear illustration in either the main text or caption.
- Significance
  - Both the theoretical and empirical results are significant. 
questions: 1. Whether RFGNN is applicable to larger graphs such as ogbg-ppa and ogbg-code2?
2. Since one of the motivations to alleviate over-squashing is to better model long-distance interactions, I suggest the authors to conduct experiments to evaluate the effect of the number of GNN layers. The current number of GNN layers is always 3, which may not reflect“long-distance interactions”.
3. In Line 182, the authors claim that “the influence along a long path is always less than that of its sub-paths”. Is there any possibility that distant nodes should contribute less than closer nodes?
limitations: The authors have addressed the limitations of their work, but did not discuss the potential negative societal impact.
review_title: null

Meta-review: metareview: This work focuses on a well-known (inductive) bias of message-passing: the fact that information from far away neighbors is dilluted and taken less into account than those of nearby ones. The paper proposes an innovative and rational way to overcome the oversquashing bias. It also provides compelling theoretical evidence for the proposed approach's merit. The numerical results are promising, though not sufficiently thorough to establish this as being close to state-of-the-art. Nevertheless, the reviewers agree that the work is valuable to the community and should be published.
confidence: Certain
Decision: Accept