Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work studies the phenomenon of oversmoothing in graphical neural networks and asks the question: since message passing averages information and thus loses local information, why is it ever helpful in estimation.  The authors consider a linear model in which the data distribution is Gaussian and message passing and aggregation are linear, so the model can be exactly solved.  It is shown that k rounds of message passing takes a data covariance \Sigma to (Id + \Sigma^-1)^{-2k} \Sigma, a transformation which shrinks small eigenvalues.  If these are noise directions then this is beneficial.  
strengths_and_weaknesses: Strength: a simple, clear and instructive analysis bearing on a question of much current interest.

Weakness: more could be said about the simple model, for example about the question raised below.  
questions: I found the discussion in section 4.2 particularly interesting and it raises a question.  As the authors say, the result depends on parameters of the random graph model, in particular the covariance in equation 6.  It is taken to be 1 here and the general dependence is easy to put in.  But if one wants to apply the result to an empirical graph and observations, one needs to know how to estimate this parameter, as the authors comment in the conclusions.  Equivalently, what determines which are the "small" eigenvalues which get smoothed versus the "large" ones which do not ?

limitations: Technical results with no immediate societal impact.
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 paper studies the problem of beneficial smoothing and oversmoothing. The authors show that a finite number of mean aggregation steps improve the learning performance of linear GNNs before oversmoothing occurs in examples of regression and classification. Numerical experiments demonstrate their claims.
strengths_and_weaknesses: Strengths:
1. The paper provides the first theoretical study that models the benefits of finite smoothing (mean aggregation) before oversmoothing occurs.
2. The paper is well organized and easy to follow.


Weaknesses:
1. The authors may want to conduct experiments on some large-scale datasets, such as OGB [1].
2. The authors may want to analyze some non-linear GNNs, which are more useful and powerful for large-scale datasets than linear GNNs.
3. The authors may want to provide approaches to efficiently compute or estimate the optimal smoothing point, which is useful in practice.
[1] Hu, Weihua, et al. "Open graph benchmark: Datasets for machine learning on graphs." Advances in neural information processing systems 2020.

questions: See weaknesses.
limitations: Yes.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the smoothing and over-smoothing phenomena on graph representation learning via the mean aggregation, which is the most common aggregation function of the message-passing framework. The authors prove that both phenomena are co-existent with a latent space random graph model. Besides, two mechanisms for the benefits of mean aggregation are recognized. In addition, the theoretical expressions are well matched with simulation results. The theory in this work has a great impact on graph representation learning. It helps researchers deeply comprehend the smoothing and over-smoothing phenomena. More importantly, this paper may enlighten researchers on preventing, relieving, and solving the over-smoothing issue.
strengths_and_weaknesses: Strengths:

- The writing is neat and easy to follow.  
- The theoretical foundation is solid.

questions: 1. What are the boundary conditions between the smoothing and over-smoothing?
limitations: The authors have sufficiently addressed limitations of this work. In Section 6, the authors acknowledge that this work does not discuss the most common situation that how a non-linear GNN works for the node classification task with the cross entropy loss function.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper proposes a simplified theoretical framework -- linear MPNNs with mean aggregation, latent variables underlying the label, feature, and graph generation -- to show that while the problem of over-smoothing is indeed generally relevant in the context of graph neural networks, a finite number of aggregation steps (equivalently finite integration time from the point of view of GNNs as dynamical systems) could be desirable to reduce the noise of the node representations and consequently improve the classification.
strengths_and_weaknesses: Presentation: The paper is well written and the outline is clear. The problem at hand is precisely formalized along with main results and ingredients entering the proofs. I also appreciate the discussion on limitations of the current framework and/or techniques of the adopted proofs.

Novelty and originality: The paper is original -- at least in the GNN community -- for what concerns the proposed risk analysis as a function of the number of aggregation steps. In terms of "novelty", the judgement is slightly trickier. Per se, the paper does not really offer new "carry-with-you" insights and there is perhaps little new understanding beyond an elegant mathematical analysis that only applies to very ideal scenarios though -- as further commented below. The following specific sentence at line 74 is crucial: "(...) the relationship between node features and graph structure, and we hope that it proves an inspiration to help the design of GNNs in the future." It is not clear to me how and to what extent the paper provides an original insight to the community that could lead to better designed GNNs or more generally to a deeper understanding of their mechanism -- beyond better formalizing something that is arguably already known.

Strengths: 

- The paper is elegant and no clear improvements are needed on the presentation front.

- The technical statements seem correct to me -- you may need an extra factor of 1/2 in front of the regularization in eq (3) for the equality to be correct?

- The problem addressed is worth exploring -- namely a finer analysis of GNNs after a $finite$ number of steps (i.e. finite integration time) is still somewhat lacking and the now standard asymptotic analysis of the over-smoothing effect is indeed limiting and ideal.

- I appreciate the efforts to comment on the technical assumption 1 and to provide some intuition based on principal components. 

Weaknesses:

- The main weakness -- as partly mentioned above -- is that the message of the paper is known in the community and that the setting analysed does avoid investigating precisely those cases that are not fully understood. The upshot is the following: if the graph is homophilic (label distribution aligned with the topology) and the node-wise features are somewhat smooth (aware of the graph structure), then some (finite) smoothing is known and expected to be beneficial to denoise the node representations and leverage the information contained in the graph structure. This is for example implicit in all the references that argue how conventional graph convolutional models behave as low-pass filter operations in the graph-frequency domain (under some assumptions). While this may not have been formalized using the techniques of the paper, the end-message is not different. It is hard for me to grasp some novel understanding that the paper may bring in this scenario beyond some specific asymptotics that are though consequence of the very ideal setting analysed. 

- Connected to the first point, the paper does analyse the easier problem of MPNNs "in the case of homophily". In fact, the underlying 
assumption is that the graph generation procedure via the kernel is homophilic wrt the latent variables and hence $y = x^\top \beta^{\star}$. This is precisely the scenario where some steps of low-pass filters are beneficial and accordingly the same applies to MPNNs that act as average on the 1-hop. There is an implicit message throughout the paper that some smoothing is "always" beneficial. This may fail for heterophilic graphs when using MPNNs that simply average over the neighbours. This point should be better addressed. 

- The relation between the optimal k and the dimension (which would be new in the community) is quite interesting but this is not explored further. While I understand that would require more involved mathematical techniques,  the behaviour of the risk after k steps and explicit formulas in low-dimension are only available after further constraints (for example on the form of $M$) and the far more interesting question of the degradation of k even in the ideal scenario is mostly still open given that the main theorem amounts to showing that with high probability one step of aggregation is better than none.
  

questions: Questions and further feedback:

- Is Assumption 1 in some way optimal or a consequence of the techniques adopted (e.g. that we show that in probability $\mathcal{R}^{(1)} < \mathcal{R}^{(0)}$?

- It would be more interesting to explore what happens if we have a residual connection which is known to mitigate (prevent) over-smoothing. How would now the behaviour of the risk be affected? Any speculation?

- What of the analysis proposed here can be extended to less ideal scenarios? For example when the graph generation is less ideal than that encoded by a Gaussian kernel over the latent variables -- certainly the estimates are less quantitative but perhaps more interesting.

- Some more synthetic experiments could also potentially improve the story especially to complement qualitative analysis when stress-testing the ideal scenario. For example, what happens when we generate features (or graph) that fail to satisfy the assumptions? How would the degradation wrt k react?

Conclusions: 

It is hard to have a strong opinion on this paper. On one side, it is very well written and presented, with the proposed problem fully addressed in the specific mathematical setting introduced. While ideal scenarios are indeed useful for providing a better understanding of a given phenomenon, I can't help but feel that the insights deduced here are not that novel. In fact, I circle back to the sentence "(...) and we hope that it proves an inspiration to help the design of GNNs in the future", $\textbf{which has not been justified in my opinion}$. Nonetheless, I still think $\textit{this is a worthy paper}$ -- with potential interesting extensions in some of the less ideal cases I mentioned earlier -- $\textit{perhaps though more suitable for a more `statistics oriented/flavoured' conference rather than a general one}$. I am of course happy to engage in discussion and raise my score if the authors and/or other reviewers point to something I have missed in my analysis concerning impact and relevance in the community. 
limitations: Societal impact is not reported -- albeit the paper is theoretical in nature. Limitations are properly discussed.
review_title: null

Meta-review: metareview: The majority of reviewers are in favor of accepting * Not too little, not too much: a theoretical analysis of graph (over)smoothing* .  The reviewers were impressed in general by this theoretical analysis of finite-step mean aggregation smoothing in linear GNNs which is well-supported by their simulation results.  The paper's model gives evidence of both the value of smoothing but demonstrates that a threshold for over smoothing exists.  In general the novelty of the analysis of  a phenomena relevant to the community and the quality presentation leads me to recommend that this paper be accepted.
confidence: Certain
Decision: Accept