Not too little, not too much: a theoretical analysis of graph (over)smoothing
Authors: Nicolas Keriven
Venue: NeurIPS 2022 Accept (2022)
Keywords: graph neural network
theory
oversmoothing
aggregation

Abstract: We analyze graph smoothing with mean aggregation, where each node successively receives the average of the features of its neighbors. Indeed, it has quickly been observed that Graph Neural Networks (GNNs), which generally follow some variant of Message-Passing (MP) with repeated aggregation, may be subject to the oversmoothing phenomenon: by performing too many rounds of MP, the node features tend to converge to a non-informative limit. In the case of mean aggregation, for connected graphs, the node features become constant across the whole graph. At the other end of the spectrum, it is intuitively obvious that some MP rounds are necessary, but existing analyses do not exhibit both phenomena at once: beneficial ``finite'' smoothing and oversmoothing in the limit. In this paper, we consider simplified linear GNNs, and rigorously analyze two examples for which a finite number of mean aggregation steps provably improves the learning performance, before oversmoothing kicks in. We consider a latent space random graph model, where node features are partial observations of the latent variables and the graph contains pairwise relationships between them. We show that graph smoothing restores some of the lost information, up to a certain point, by two phenomena: graph smoothing shrinks non-principal directions in the data faster than principal ones, which is useful for regression, and shrinks nodes within communities faster than they collapse together, which improves classification.

Not too little, not too much: a theoretical analysis of graph (over)smoothing
Nicolas Keriven
CNRS, GIPSA-lab, Grenoble, France nicolas. ker.ken@errss....
Abstract
We analyze graph smoothing with mean aggregation, where each node successively receives the average of the features of its neighbors. Indeed, it has quickly been observed that Graph Neural Networks (GNNs), which generally follow some variant of Message-Passing (MP) with repeated aggregation, may be subject the oversmoothing phenomenon: by performing too many rounds of MP, the node features tend converge to non-informative limit. In the case of mean aggregation, for connected graphs, the node features become constant across the whole graph. At the other end of the spectrum, is intuitively obvious that some MP rounds are necessary, but existing analyses do not exhibit both phenomena at once: beneficial "finite" smoothing and oversmoothing the limit. In this paper, we consider simplified linear GNNs, and rigorously analyze two examples for which finite number of mean aggregation steps provably improves the learning performance, before oversmoothing kicks in. We consider latent space random graph model, where node features are partial observations of the latent variables and the graph contains pairwise relationships between them. We show that graph smoothing restores some of the lost information, up to a certain point, by two phenomena: graph smoothing shrinks non- non-principal directions in the data faster than principal ones, which useful for regression, and shrinks nodes within communities faster than they collapse together, which improves classification.
Introduction
In recent years, deep architectures such Graph Neural Networks (GNNs), along with the availability of large sets of graph data, have significantly broadened the field of machine learning on graphs and
structured data, with a myyiad of applications ranging from community detection [II] molecule classification (20), drug discovery [19). quantum chemistry [15), recommender systems [44), semi- supervised learning, and so on. See 7 16
6 46
for reviews. Most GNNs rely on the Message-
Passing (MP) framework [15 23 with plethora of variants. At each layer k for each node i, representation z; previous layer:
(k) is computed using the representations of the neighbors Nr of i in the graph the
AGG ((2)--"))
(I)
where AGG is an aggregation function that, crucially, treats {z) (k))))) DeN, Hew, as an unordered set, to respect the absence of node ordering in the graph. There many variants of aggregation functions, based on sum, mean, max, min, degreeenormaaiized (23), attention-based [39], and so on. In this work, consider one of the most classical, mean aggregation:
(k)
E, ag 2 (k-1))
(2)
Σ
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

onder srauthing
sreothing
Illustration of both beneficial smoothing and oversmoothing on Cora [32 (top) and Citescer [4] (bottom). From left to right: node features after performing respectively = O, 10, and 500 steps of mean aggregation, along the first two prineipal-componnts (of the original unsmoothed features), for three classes of nodes for better visibility. Figure on the right: Mean Square Error of Linear Ridge Regression (LRR) the smoothed features with respect to order of smoothing k. We observe that smoothing first gather same-labed nodes and improves learning. before they eventually collapses to single point (note that here we show LRR for consistency with the analysis presented in this paper, even though these are node classification tasks).
Figure 1:
where the dij E R_ are the entries of the adjacency matrix of the graph: either positive edge weights or 0, for unweighted edges, and is some function (usually Multi-Layer Perceptron). In other words, the aggregation process is weighted average over the neighbors. As we will see, it corresponds to a multiplication by (identity minus) the random walk Laplacian of the graph.
While MP is a natural and rather general framework, its limitations were quickly observed by researchers and practitioners. Foremost among them is the so-called oversmoothing phenomenon [27] as the GNN gets deeper and many rounds of MP are performed, the node features 2; tend to become similar across the graph, especially for small-world graphs with small diameter. Oversmoothing prevents GNN from being too deep unless one is particularly careful. A non-negligible part of the literature is dedicated fighting oversmoothing with various strategies (see below).
On the theoretical side, oversmoothing has mostly been analyzed in the infinite-layer limit A + oo. In this case, classical spectral analysis of graph operators such as the Laplacian can be leveraged to indeed show that node features will always converge to some limit that carries a limited amount of information (34]. This is particularly true for mean aggregation (2), with constant limit across all nodes for a connected graph, see Sec. 3 Unlike some other graph operators such as the symmetric normalized Laplacian, where the limit still carries a small amount of information such the degrees, with the random walk Laplacian all information is lost in the limit (beyond a single constant).
However, there has been little research at the other end of the spectrum, showing that some smooth- ing is useful for learning, despite this fact being intuitively and empirically obvious. Generally, researchers show the power of GNNs for sufficient (unbounded) number of layers, such as the now-famous ability to distinguish graph isomorphism as well as the Weisfeiler-Lehman test and all its variants [47 30), the ability to compute some graph functions (28). and on. Since these results are valid for an unbounded number of layers, the settings adopted in these works are, by definition, incompatible with non-in con-informative oversmoothing. To our knowledge, there is work that formally models both phenomena at once: some smoothing is provably useful for learning, while too much smoothing inevitably leads to oversmoothing.
This work aims to fill this gap. We showcase two representative exemples, of regression and classification, on which linear GNNs (aka, here, simply Linear Ridge Regression (LRR) on smoothed features) are subject to this double phenomenon. Note that restricting ourselves to mean aggregation makes this claim quite non-trivial. in the absence of any "informative" node features, no information can be recovered by mean aggregation alone. For instance, leaves constant node features unchanged, and the limit & + do is always constant. So the challenge is the following: node features must carry some information, such that a finite number of steps of mean aggregation provably increases the amount of useful information, before it loses it in the limit. See Fig. for illustration.
To show this we adopt on a model of latent space random graphs, with node features. The latter contain partial information about the unobserved latent variables which both the labels and the graph structure depend. On our examples, we prove that with high probability, graph smoothing improves performance before oversmoothing occurs. We identify two key phenomena for this:

---

smoothing shrinks non paiinciiaaa directions in the data faster than principal ones (Sec. 4. and shrinks communities faster than they collapse together (Sec. [5 Although our theoretical settings are obviously simplified, we believe it is step towards a better comprehension of graph aggregation and of the relationship between node features and graph structure, at the heart of many phenomena in graph machine learning.
Related Work Oversmoothing [27 is very active area of research in geometric deep learning, and an exhaustive list of works would be out of scope here. The research has been mainly focused on novel architectures to relieve it, such as residual mechanisms 26
10. randomly dropping connections
[18], introducing local jumps [48], clever normalizations [50, 17 5 37 or regularizations [9], among others. Some works have acknowledged the important role of the aggregation function, and proposed new exotic diffusion strategies [S] or to optimize it [24]. On the theoretical side, it has been mainly shown that repeatedly applying graph smoothing operators indeed induces convergence of the node features [34. In this work, we analyze model that present both the benefits of finite smoothing despite oversmoothing in the limit.
Our theoretical framework is based on simplified linear GNNs and random graphs that explicitely model the dependence between labels, node features, and graph structure. Despite their simplicity, linear GNNs, sometimes called Simplified Graph Convolutional networks (SGC), have been observed
to exhibits relatively good performance 45 33 and are routinely used in theoretical analyses (51)
Random graphs have been used extensively to analyze graph machine learning algorithms [43] 33 and
the theoretical properties of GNNs such stability [2] 36). transferability (25] or universality 22
Our model crucially includes observed node features, an essential part in analyzing the smoothing process. They have been shown to be correlated sought-for labels in real graphs [33, and that this fact is key in the success of GNNs. Our proof is in fact more akin to analyzing graph diffusion process [3 given appropriate initial conditions (observed node features), at initial time the diffusion produces a better signal for learning, before it eventually collapses to a single point. To the best of our knowledge, this is the first proof of this kind machine learning context.
Outline We describe our framework in Sec. 2 In Sec. 3 we briefly prove the oversmoothing phenomenon when k + co, which is just the Markov chains ergodic theorem in our settings. In Sec. we study a regression problem. We derive an expression that predicts with good accuracy the optimal smoothing order k* in some cases. Sec. 5 we study a classification problem between two Gaussians. Although we formally prove the existence of k* > 0, deriving an explicit expression for the risk still open in this case. Code to reproduce the figures is available at pestps://gitaan com/ hom/nkerriven. ccom///errreeeegggaaaamntttttt graphsmoothing
2 Preliminaries
Notations.
The norm ||-|| is the Euclidean norm for vectors and spectral norm for (rectangular)
matrices. For a psd matrix Σ, the Mahalanobis norm is || r Ex. The determinant of a matrix [S], and its smallest eigenvalue is Amin (S). The multivariate Gaussian distribution with mean μ and covariance Σ is denoted by (1) = det(2x2))-4 Le = We will use the shortened notations N₁, NNa.ia and N Noo Our bounds will involve various multiplicative constants poly( (-) which are polynomials in their input.
on an undirected graph R as well as node features Z1,... Zn RP each node of the graph. We also observe some labels yı...., Un, E R at training time and aim to predict the remaining labels +1, yn- In a classification framework, y E 11, For simplicity, Z E R2 the matrix whose rows contain the node features, Zu. Zre respectively its first Aur and last The rows, and similarly Yr. Ye the vectors containing the observed and non-observed labels.
SSL. In this paper, we consider Semi SuperSiupe Learning (SSL) 8 23 of size n. We observe a weighted adjacency matrix A = la,]l'
assume that f4r and The
fhr are both in O (n ! We denote by
Graph smoothing with mean aggregation. Here we consider a simplified situation of linear GNN with mean aggregation, that is, equation (2) with linear V. Since all linear weights collapses into
while this is an important topic in SSL 4 here we do not focus on the number of needed labels and perform an asymptotic analysis instead.
3

---

single matrix, a linear GNN with & layers just corresponds to performing k rounds of mean aggregation on the node features, then learning on the smoothed features. We denote by d, = مΣ, رااlة E RT the vector containing the degrees of the graph and D = diag(dA). Assuming that all degrees are non-zero, performing one round of mean aggregation corresponds to multiplying Z by T. = D A. Note that Id L is then the random walk Laplacian of the graph. The smoothed node features after rounds of mean aggregation are:
z(k) L.
Each row, denoted by 2 E RP, contains the smoothed features of an individual node. Similar to the non-smoothed features, its first Por and last The rows are denoted (k) (x)
Learning. In this paper, we consider learning with a Mean Square Error (MSE) loss and Ridge regularization. For À > 0, the regression coefficients vector the smoothed features is
3(k) def argming 2nd
||r
8
+ +1118122 = (Z z((
+ Ald
(z(()) Y
(3)
Then, the test risk is defined as
R
del. Rie
Yiu
Y 1 where Lic (A)
(()) g(w)
(4)
It is well known that when k co, the matrix L will converge to matrix with constant rows, and
(o00) def 1im R(k) will just be close to the variance of Y, see Sec. 3..33 for a precise statement. Very often, this degrades the results with respect to doing a simple linear regression: R,(0) (o0),
Our goal is to illustrate some situations where finite amount of smoothing provably improves the
test risk, that is, there is an optimal k* > 0 such that R(*)) < min (R)) ((x)).
Random graph model. To perform fine-grained analysis of our problem, we need statistical model linking the graph, the node features, and the labels. We adopt popular latent space random graph models akin to graphons [29]. Although such models are obviously idealized, we believe that they faithfully convey the main insights. In these models, to each node is associated an unobserved latent variable x; E Rdd with d > p (often d > p). and edge weights are assumed to be equal to ag = (J,,T, where W T2d x Te + R is connectivity kernel. Note that edges may also be taken random Bernoulli variables, but we do not consider this here for simplicity. Moreover, consider that the (I,, y/) are drawn iid from some joint distribution, and the node features are a linear projection of the latent variables lower dimension: 2 M T x; for some unknown M E Rd that satisfies M M Idp. At the end of the day:
Vi, (Ii, sid P.
2: = M Fz.
0ij = ((x,
(5)
For this model, note that
z = -
(R) M where (() L
In other words, the smoothed node features (R) also correspond to a linear projection of the (unknown) smoothed latent variables (k), To summarize, compared to "classical" machine learning on the (z,, y.), we do not observe directly the v,, but only projection of them = M TT.. Although we assume that M is orthogonal, we do not assume that is cefffrmmttion-peservinn lemma), but rather that information is lost between the æ and the z. However, we also observe the graph W (xx, 2y). Our goal is illustrate how mean aggregation may restore some of the lost information.
(c.g. it does
not satisfy the
In the rest of the paper, we use the Gaussian kernel with a small additive term E 0:
W(, = (2(x,)) where W y) -11==~11
(6)
The coefficient& is added to lower-bound the degrees of the graph and avoid degenerate situations. While this seems to needed for our current proof technique, we use e Gaussian kernel is classical model in theoretical graph machine learning [38]
Fig. 2 and The

---

Oversmoothing
In this section, we briefly examine the oversmoothing case, when oo while all other parameters are fixed. In this case, it is well-known that all node features converge even for general GNNs (34). For completeness,
state below this result in our settings. We have the following well-known ergodic theorem for stochastic matrices such as L.
Theorem 1 (Ergodic theorem for stochastic matrices, e.g. 12 Thm. 4.2].). Recall that da is the vector of degrees, let d da/dxIn We have
L
Ind
This easily allows us to prove the next result. Corollary 1. We have the following
Y (k)
(+llol (x11/lTp Bu)
[|ell2
Imn
(8)
k-000
where v = ZT and Dhr = Phr Eim1 Yi.
Proof. We use Thm. get L*M + Lxv and (Ald + - = X+1
Hence, in the limit k - oc, the predicted labels become all equal. When À z 0, this value is, as expected, the average of the labels in the training set Thr Using simple concentration inequalities, generally easy show that (())) Var(y) O (1/vn). In most cases, this leads situations where (()) R(s)), that is, is better to perform regression directly on the node features. In the next sections, we analyze some examples where smoothing provably helps.
4 Finite smoothing: Linear Regression
In this section, we consider a problem of linear regression on Gaussian data, We consider No. for some positive definite covariance matrix Σ, and y = T 3*, without noise for simplicity (noise would just add an additional variance terms to all our bounds). We will first describe our main result that holds under certain condition that is not necessarily easy to interpret, then give sketch of proof in Sec. 4.1 and an example in dimension d = 2 where this assumption is satisfied in Sec. 4.2
For symmetric positive semi-definite matrix S Rdxd define the following function
[Id 5 M (AId T SMT 2 ( (*) E R,
Reeg.
(S) def. ( (T)
where we recall that M is the projection matrix to obtain the node features Z = M TTa x. Note that satisfies < R(S)= < || Our result will be valid under the following assumption:
Assumption 1. We have Reeg (E) > Breg. ((Id+ -
Note that (Id + Σー1)-2ミ is indeed symmetric since (Id Σー and permute. Our main result can be stated informally follows, is detailed in the next section along with sketch of proof. Recall that the kernel is taken as (6).
Theorem 2 (Existence of optimal smoothing for regression.). Take any p > and suppose that Assumption 7 holds. I is sufficiently small and n is sufficiently large, then with probability there is k* > 0 such that R(k)) < min(R()) R(oo)).
4.1 Sketch of proof
As we will see, it is easy to show that ())) < (<)) with high probability. Our main goal will therefore be to show that (!)) < R (0) with high probability under Assumption which is sufficient show the existence of an optimal k*
Using concentration inequalities, will prove rigorous non-asymptotic bound for (1), In the next section, also derive intuitive expression for (k) (although without rigorous proof), which observe to match the numerics quite well.
5

---

The first step is to derive closed form expression for R which is fairly easy using standard concentration techniques for subgaussian variables. The next result is proved App. A.1. Theorem (Regression risk without smoothing.). With probability least 1 P.
|| d dv/og(1/p)
R (0) Rreg (E) + +
(10)
(A + Amin) V
where Amin Amiu EM).
As expected, when p p= d, M Id and À - O, we have Reg. [Σ] + 0 and the risk is exactly 0 in the infinite sample limit (recall that have assumed zero noise on the labels). When p d however, the limit risk is generally non-zero. The worst case is obtained when Σ orthogonal to M
where the risk reaches its maximum at || E| E lyl". Since this is the variance of this is also
lim R R(0)), hence we always have (()) & R (0c) with high probability for n large enough.
Let us now turn to computing the risk after one step smoothing k We define (
(Id + Σ-1 - (-1))-22k y. The main result of this section is the following.
Theorem 4 (Regression risk with one step of smoothing.). With probability at least 1
C' /
R()) = Reeg (20)) + (CEV)) +0
(11)
(A + Amin) Vn
where C' - poly( ea, + EI), C' = poly(E-), |||]| ||8*
and Amin = Amin E(T
This theorem gives limiting expression or (()) with two additional error terms. The first goes to 0 with and is due the deviation from the kemnel (6) to the exact Gaussian kernel Wg. The second term goes to when n + oc and is controlled via concentration inequalities. The limit risk when E + 0, + oc is (1)) se Rreg. (21)),, which is strictly lower than Rreg (Σ) by Assumption | and proves Theorem Note that, to get R()) < R(),, we generally need E S e em and therefore ea.
which seems to an unavoidable artifact in our current proof technique.
Let us try to better understand Assumption by sketching the proof of Thm.
4 The proof relies on an
approximate description of the distribution of the smoothed node features 2, -M where
recall that the zi (1) the rows of X L We define d(x:) IId Σ Illll and
d(x) (M
Preg (x)
Id) 1d)-
(12)
d(x)) +
Then, using some chaining concentration incqualities for subgaussian variables (Lemmaa 7 in the appendix) and properties of Gaussian distributions (Lemma 5), we can prove the following. Lemma 1.
With probability at least p. for all i = 1,...,
2 (1)
Greg (1:)
C Clogn( / log(1/))
(13)
Σ
1/2
2
(x( Preg. (1: (xe)) (1:1) T) Σ
Vn
where = poly(s ΣН|
ITd Σ)).
Hence the smoothed latent variables behaves almost like (Id + - up to a deviation that is handled in Lemma 3 in the appendix. The covariance of these data is (0) (Id + ---1 ---)),²;,, hence we can adapt the proof of Thm. 3 to obtain Thm. All details are given in App. A.2.
4.2 Intuition and exact computation in dimension d 2
We proved above that (!)) behaves almost like (Id + --=->>>-- --1)-'z, whose covariance is E(), Similarly, by applying repeated smoothing we can extrapolate that (())) behaves like (Id + -ー-))ー such that (A) 2 Reeg (*()). The rigorous proof of this fact becomes increasingly complicated and is skipped here. The matrix (k) has the same cigendecomposition as Σ, but where every cigenvalue A;

---

Empirical
Theary
12"
Order of smoothing
(a)
0.505
Empinical
3454
2-455
0315
0354
1.5
Onder smoothiigg
(b)
Figure 2: Illustration of mean aggregation smoothing the regression example described in Sec. 4.2 For both subfigures: First three figures on the left, top: unobserved latent variables (*) in dimension d = 2 where the colors are
bottom: observed node features (kk) xx) M in dimension p 1 on the x-axis, labels on the y-axis. From left to right, three order of smoothing = 0, 1 and are represented. Figure on the right: comparison of empirical and theoretical MSE given by [14 with respect to order of smoothing k. Subfig,
A1 = 2, A2 1/2 (smoothing docs help), Subfig. b A 1/2, A2 = (smoothing does not help).
replaced by ( = (1 A; This can be interpreted as follows: when X; > large, x(2) >ı while if X; 1 is small, x x²k+1 (note that the constant "1" here is due kernel (6). it is not inherently significant). Hence smoothing shrinks the directions of the small eigenvalues faster than that of the large ones. Thus, if 3* is mostly aligned with the eigenvectors of large cigenvalues, shrinking the small cigenvalues may reduce unwanted noise that emerges when projecting the node features z M x. On the other hand, if all eigenvalues of I are equal, then ()) Σ, and smoothing does not help, since in the limit À 0, the risk is invariant to scaling Reeg (aS) = Ree (S). Worse, we will see on an example below that smoothing can actually degrade the performance when 3 is unpropery aligned.
We illustrate this in dimension = 2. Consider the following settings: = 2,p = 1, Σ has two cigenvalues A > 1 and X2 < 1, with respective eigenvectors ui = [l, 11/ and U2 = [-1, 12/ and 8* is fully correlated with the first eigenvector: 3 bug. Finally, M 11, 0] is the projection on the first coordinate. This situation is represented in Fig. In this case, we can compute explicitely:
(h) Recg (2)()) 0, (2A 1 (2) / (5) (8)
11
(14)
(2X+ X + + 32
So, if (1th) decreases faster than (k)) this function will first decrease minimum of approximately
2
A
22 (when > z 0), before increasing again to b₂ = || 2 lim R R(o)
2x+x(=)))
This is illustrated Fig. 2 for
and A2 = -1/2, where we empirically observes minimum k**
that matches rather well the one predicted by (14)
Homophily vs. Heterophily and failure case graph theory, homophily refers the concept that linked nodes tend to display similar properties: for instance, friends on social networks have similar preferences, and so on. In graph machine learning, it generally means that linked nodes tend to have similar node features and labels. This concept is at the core of many graph signal processing and graph machine learning methods: for instance, spectral clustering akin low-pass filter on the graph structure. However, it has been observed that real graphs may sometimes exhibit a low
7

---

level of homophily [1 They are rather said to be heterophilic, somewhat less "well-defined concept: in heterophilic graphs, linked nodes can be similar or dissimilar, some attributes can be homophilic and others heterophilic, and so on.
In settings, at first glance it seems that our very regular random graph model always results in homophilic graphs, as the Gaussian kernel decreases with the distance between latent variables, and the latter are strongly linked with the node features. This partly true, however is it also possible that nodes linked by a "strong" edge (with a high weight) have very different labels, which can be said be a (toy) example of heterophily. For instance, consider the 2D linear regression example above given by (14). We have seen that when the regression vector is in the direction of the eigenvector corresponding a high eigenvalue, then beneficial smoothing appears, as it reduces the noise in the observed node features (Fig. 2ap. However, when the regression vector is instead in the low-eigenvalue direction, then close-by latent variables have very different labels, and the graph is more heterophilic. In this case, beneficial smoothing does not appear, and any smoothing strictly degrades the MSE! (Fig. 2 This due to the fact that in this case the "information" node features vanishes faster than the noise. Of course, this is exceedingly simple model of heterophily, and better understanding and modelization of this phenomenon remains an outstanding open question.
Discussion Recent literature on GNNs have adressed both oversmoothing and heterophily by clever normalization techniques [50, 17 5 37, combined with quantitative metrics of these phenomena 49 51. However, these tend to indiscriminately combat oversmoothing, without taking into account potential beneficial smoothing. In future work, our analysis could help designing more detailed normalization methods, e.g. after some estimation step that would identify which directions in the data are squeezed by smoothing, and which of them are relevant or not for learning.
5 Finite smoothing: classification
In this section, we examine a simple classification problem for two balanced classes with Gaussian distribution with identity covariance. The distribution of the labels and latent variables is:
(x, ~ (L, @ (1} + + (-1})
(15)
That is, with equal probability x is drawn from N₁. and y = 1, or ~ N_p. and = -1. As |P| increases, the problem become simpler, there an extensive literature on this problem [12 40
Note that in this case are also Gaussian, with mean v def M rl -v and identity covariance.
We note that this not the method of choice to solve it: there are plethora of losses better adapted to binary classification such the binary cross-entropy (left for future investigations), Spectral Clustering algorithm on the graph alone would be able to perform the classification task under some mild hypotheses [40] [ (without using the node features!). Nevertheless, let us recall that our main goal is to illustrate the smoothing phenomenon, and as we will see, the interpretation here will be quite different from the previous section. Our main result is the following.
a difficull problem per se, and that linear regression with the MSE is certainly
even other dedicated methods:
Theorem 5 (Existence of optimal smoothing for classification.). Take any p > 0. If is sufficiently small, and ||д|| n are sufficiently large, and || r|| > 0, then with probability 1 - p. there is k* > 0 such that R ()) (o))).
Note that we have assumed ||x|| to be sufficiently large here. However, we do not assume that [ T اlll is large (just non-zero), and the classification problem on the 2; alone may be very difficult. The rest of this section presents sketch of proof and intuitions behind this theorem.
5.1 Sketch of proof and intuition
As in the previous section, it will be easy to show that R,0)) < (00) with high probability, and we will prove that R(1) < (0)) with high probability, Again, we start by providing an expression for R()) For E R4, we define the following function
(s + 2)2 + ||211
(s(
(16)
(s + À + ||011
8

---

to each other, the smoothed features in each community have the same mean but a reduced variance Id/4, thus the limit risk Ra(1/4 in our limit expression for R(!) In other words, the communities shrink faster than they collapses together, and this reflects on the projected node The next result is proved in App. B.1. Recall that v/ = M¹ Theorem (Classification risk without smoothing.). With probability at least - P.
||||| P>/oo(oo log(1/p)
R (1) +0
(17)
vn
When ||^|||
oc, the risk goes 0, expected, since the Gaussians get further and further away. However, when |/|l - 0, which can happen either when ||||| is small or when M becomes orthogonal μu, the risk goes 1, its worst value, for random guesses. Since it is also the variance of y. we have indeed R()) < 1 = (())) with high probability for n large enough.
Let us now turn computing the risk after one step of smoothing 1. The main result this section is the following.
Theorem (Classification risk with one step of smoothing.). With probability at least 1 - p.
1 R()) (a.(114)+ ed EJ _
)) + +0
C'(logn) log(( log(1/p) vn
(18)
where C - poly([]]]]] e and C' -
This theorem show that R(4) 2 Ra. (1/4) with two additional error terms. First of all, a quick function study shows that Ra. (1/4) are small enough. The last eπrоr term goes to 0 when - co and is controlled via concentration inequalities. The first one is small when is small and ||æ||| large enough. We remark that, unlike the previous section where the error terms vanished in the limit & + 0, + oc, here there is non-zero error term due to || whose explicit expression still open. Hence, for instance, the discrepancy between the empirical observations and the theory in Fig, 3 compared to Fig. 2 Note that, as in the previous section, we need least E S ed and Z e However, here also need
(1) when |||||| > 0, which shows Thm. when the errors
||||| 2 vd. This rate similar to early analyses of Gaussian Mixture learning 12 although they
have been greatly improved since 3
As previously, we define here d, (x) 2- d/2 1|=-112 and
(a(x)) dx(x) 2tH + d +d=(())( (3)
(19)
23 + du(x) + d_
The following result is similar to Lemma 1 and is shown in App. B.2. Lemma 2. With probability at least P.
sup (:12) - Pol (1;)
poly(s-!) n(vd /log(1/P)
i=1....,
(20)
(1) (T) pa (ara (ca))
nn
sup 1=1,...
Let us examine Pa. closer. In the limit 0, (x. (1) is convex combination of (a: + n)/2 and (r - 22/2. Hence, when x ~ Nr. with high probability æ is close to μ and dx > (z) and in this case, (2l(z) = 2
st4 whose distribution is Ny,,a/44 The same reasoning applies to the
due to the communities getting closer other community. Hence, up to some error O (1lal=))/)) (
features. An illustration of this phenomenon is given in Fig. 3 All proof details
App. B.2.
5.2 Numerical illustration
In light of the proof of the theorem above, when x; belongs to the first community and x Rs (zx) se z4th applying second smoothing would transform it to (a,) 2.+3g
4 that

---

Empitial
Theory
smoodhing
Figure Illustration of mean aggregation smoothing on a classification task with two Gaussians with dimensions d 2. = 1, where M projects on the first coordinate. First three figures on the left, top: density of unobserved latent variables (*)) in dimension d bottom: density of observed node features Z(%)
x M in dimension = 1. From left to right, three order of smoothing = 0, 1 and 2 are represented (recall that the smoothing agnostic the labels, cannot perform in in-community smoothing). Figure the right: comparison of empirical and theoretical MSE given by (2T) with respect order smoothing k. For low k the node features communities are indeed more and more separated, and learning improves.
is, it keeps the same mean but now has variance ld/16. If we look at the proof, the error term O |1el1//4 would become in this case e 2,11/45 While this expression is far from being exact and we do not rigorous proof here (which seems far more complex than the case k 1), we can infer some approximate expression:
1u 2(14-1
(()) =u (1 +0
(21)
t=0
Unlike the expression [4), the term Ra.(4 (4-xk is strictly decreasing when k increases. Oversmoothing is modelled by the error term, for which we do not have exact expression, and for which we suspect that the quality of approximation degrades
increases. Nevertheless, we evaluate this expression on an example in Fig. 3 (with an adjusted multiplicative constant for the error term in (21) and find that is a reasonably good approximation, at least for small k.
Conclusion and outlooks
While the oversmoothing phenomenon k: has been well characterized, until there has been no theoretical studies that rigorously modelled both the benefits of finite smoothing before oversmoothing kicks in. In this paper, we adopted simplified context of linear GNNs with mean aggregation and random graphs with partially observed latent variables, and proved on two rep- resentative examples the co-existence of both phenomena. We identified two mechanisms for the benefits of mean aggregation: it tends to shrink noisy principal components faster than meaningful ones, and it tends gather nodes of the same community faster than they collapses together. We obtained theoretical expressions to some eтror terms that matched the numerics quite well on simple synthetic data.
There are many outlooks to this work. First and foremost, deriving inspiration from our theoretical observations to design better methods of setting the order of smoothing in practical application is major challenge. As seen in Fig. in the introduction, both mechanisms that we identified seem to come into play real data. However, many quantities appearing in the risks (14) and (2I) need be estimated. Second, extending our theory to more complex loss functions (especially for classification) and non-linear GNNs is crucial. Finally, our work is step towards better understanding of the relationship between node features and graph structure, which is at the heart of (over) sovor)smoo heterophily, and all graph machine learning methods. A more general theory, and more realistic models of random graphs to analyze it, is still an open question.
Acknowledgment
This work was supported by ANR JCJC GRandMa (ANR-21-CE23-0066) NK thanks S. Vaiter for inspiring discussions.
10

---

References
[1] Dimitris Achlioptas and Frank Mcsherry. On spectral learning of mixtures of distributions. Learning Theory, pages 458 469, 2005.
[2] Soren Asmussen. Applied Probability and Quene. Springer-Vere New York. 2003.
[3] Mikhail Belkin and Kaushik Sinha. Polynomial learning of distribution families. In IEEE 51st Annual Symposium Foundations of Computer Science. lece, 2010.
[4] Shai Ben- David, Tyler Lu, and Dávid Pál. Does unlabeled data provably help? Worst-case analysis of the sample complexity of semi-supervised learning. In 2 Annual Conference on Learning Theory, COLT 2008, pages 33-44, 2008
[5] Cristian Bodnar, Francesco Di Giovanni, Benjamin Paul Chamberlain, Pietro Liò, and Michael M. Bronstein. Neural Sheaf Diffusion: A Topological Perspective Heterophily and Oversmoothing in GNNs. 2022.
[6] Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric Deep Learning: Grids, Groups, Graphs, Geodesies, and Gauges. 2021.
[7] Michael M. Bronstein, Joan Bruna, Yann Lecun, Arthur Szlam, and Pierre Vandergheynst. Geometric Deep Learning: Going beyond Euclidean data. IEEE Signal Processing Magazine, 34(4):18-42, 2017.
[8] Olivier Chapelle, Berharrd Schölkopf, and Alexander Zien. Semi-Supervised Learning. 2010.
[9] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. AAAI 2020- 34th AAAI Conference on Artificial Intelligence, pages 3438-3445, 2019.
[10] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. 37th International Conference Machine Learning. ICML 2020. PartF16814:1703-1111
2020.
[11] Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community detection with line graph neural networks. In International Conference on Learning Representations (ICLR). 2019.
[12] Sanjoy Dasgupta. Learning mixtures Gaussians. In IEEE 51st Annual Symposium on Foundations of Computer Science, number May. 1999.
[13] Chi Thang Duong, Thanh Dat Hoang, Ha The Hien Dang, Quoc Viet Hung Nguyen, and Karl Aberer. On Node Features for Graph Neural Networks. 1nXiv:1911.08995 2019.
[14] C. L. Giles, K. D. Bollacker, and S. Lawrence. CiteSeer: automatic citation indexing system. Proceedings of the ACM International Conference on Digital Libraries, pages 89-98, 1998.
[15] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural Message Passing for Quantum Chemistry. International Conference on Machine Learning (ICML), pages 1-14, 2017.
[16] William L. Hamilton. Graph Representation Learning. 2020.
[17] Ningyuan Huang, Soledad Villar, Carey Priebe, Da Zheng, Chengyue Huang. Lin Yang, and Vladimir Braverman. From Local to Global: Spectral- Graph Neural Networks. pages
1-19, 2022.
[18) Wenbing Huang, Yu Rong, Tingyang Xu, Fuchun Sun, and Junzhou Huang. Tackling Over- Smoothing for General Graph Convolutional Networks. 14(8):1-14 2020.
[19] Dejun Jiang, Zhenxing Wu, Chang Yu Hsieh, Guangyong Chen, Ben Liao, Zhe Wang, Chao Shen, Dongsheng Cao, Jian Wu, and Tingiun Hou. Could graph neural networks learn better molecular representation for drug discovery? comparison study of descriptor-basee and graph-based models. Journal of Cheminformatics, 13(1):1-23, 2021.
11

---

[20] Steven Kearnes, Kevin McCloskey, Mare Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of Computer--ided Molecular Design, 30(8):595-600 608, 2016.
[21] Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. Convergence and Stability of Graph Convolutional Networks on Large Random Graphs. In Advances in Neural Information and Processing Systems (NeurlPS) Spotlight, pages 1-26, 2020.
[22] Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. On the Universality of Graph Neural Networks on Large Random Graphs. In Advances Neural Information and Processing Systems (NeurIPS), 2021.
[23] Thomas N Kipf and Max Welling. Semi-Supervised Learning with Graph Convolutional Networks. In International Conference on Learning Representations (ICLR), 2017.
[24] Kwei Herng Lai, Daochen Zha, Kaixiong Zhou, and Xia Hu. Policy-GNN: Aggregation Optimization for Graph Neural Networks. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 461-471, 2020.
[25] Ron Levie, Wei Huang, Lorenzo Bucci, Michael Bronstein, and Gitta Kutyniok. Transferability of spectral graph convolutional neural networks. Journal of Machine Learning Research, 22:1 22:1-41, 2021.
[26] Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. DeepGCNs: Can GCNs go as deep CNNs? Proceedings of the IEEE International Conference on Computer Vision, 2019-0ctob:9266-9277. 2019.
[27] Qimai Li, Zhichao Han, and Xiao Ming Wu. Deeper insights into graph convolutional networks for semi- sepi-supervised learning, 32nd AAAI Conference on Artificial Intelligence, AAAI 2018, pages -3355, 2018.
[28] Andreas Loukas. What graph neural networks cannot learn: depth vs width. In ICIRR, 2020.
[29] László Lovász. Large networks and graph limits. Colloquium Publications, 60:487, 2012.
[30] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably Powerful Graph Networks. In Advances in Neural Information Processing Systems (NeurIPS), pages
1-12, 2019.
[31] Naoki Masuda, Mason A. Porter, and Renaud Lambiotte. Random walks and diffusion on networks. Physics Reports, 716-717:1-58, 2017.
[32] Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127- 2000.
[33] Nicolo Navarin, Wolfgang Erb, Luca Pasa, and Alessandro Sperduti. Linear graph convolutional networks. ESANN 2020 Proceedings, 28th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, (October): 151-156, 2020.
[34] Kenta Oono and Taiji Suzuki. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. In International Conference on Learning Representation (ICLR), 2020.
[35] Lorenzo Rosasco, Mikhail Belkin, and Ernesto De Vito. On learning with integral operators. Journal of Machine Learning Research, 11:905-934, 2010.
[36] Luana Ruiz, Zhiyang Wang, and Alejandro Ribeiro. Graph and graphon neural network stability. (1):1-5, 2020.
[37] Konstantin Rusch, Benjamin P. Chamberlain, Michael W. Mahoney, Michael M. Bronstein, and Siddhartha Mishra. Gradient Gating for Deep Multi-Rate Learning on Graphs. pages 1-20, 2022.
[38] Minh Tang, Daniel I. Sussman, and Carey Priebe. Universally consistent vertex classification for latent positions graphs. The Annals of Statistics, 4163):14061140,, 2013,
12

---

[39] Petar Veličković, Arantxa Casanova, Pietro Liö, Guillem Cucurull, Adriana Romero, and Yoshua Bengio. Graph attention networks. 6th International Conference on Learning Representations, ICLR 2018 Conference Track Proceedings, pages 1-12, 2018.
[40] Santosh Vempala and Grant Wang. spectral algorithm for learning mixture models. Journal of Computer and System Sciences, 68(4))841-860, 2004.
[41] Roman Vershynin. Introduction to the non-asympiotic analysis of random matrices. Compressed Sensing: Theory and Applications, pages 210-268, 2009.
[42] Roman Vershynin. High-dimensional probabbbali An introduction with applications in data science. 2018.
[43] Ulrike Von Luxburg, Mikhail Belkin, and Olivier Bousquet. Consistency of spectral clustering. Annals of Statistics, 36(2):555-586 2008.
[44] Hongwei Wang, Jure Leskovee, Fuzheng Zhang, Miao Zhao, Wenjie Li, Mengdi Zhang, and Zhongyuan Wang. Knowledge-aware Graph Neural Networks with Label Smoothness Regular- ization for Recommender Systems. Proceedings the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2):968-977) 2019.
[45] Felix Wu, Tianyi Zhang, Amauri Holanda de Souza, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. 36th International Conference on Machine Learning, ICML 2019, 2019-June:1 1884:11884--11 1894, 2019.
[46] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chenggi Zhang, and Philip Yu. Comprehensive Survey on Graph Neural Networks. IEEE Transactions on Neural Networks and Learning Systems, pages 1-21, 2020.
[47] Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In ICLR, pages 1-15, 2019.
[48] Keyulu Xu. Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken Ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. 35th International Conference on Machine Learning, ICMI. 2018, 12:8676-8685, 2018.
[49] Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang. and Danai Koutra. Two Sides the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks. 2021.
[50] Lingxiao Zhao and Leman Akoglu. PairNorm: Tackling Oversmoothing GNNs. pages 1-17, 2019.
[51] Jiong Zhu, Ryan A. Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K. Ahmed, and Danai Koutra. Graph Neural Networks with Heterophily. 35th AAAI Conference on Artificial Intelligence, AAAI 2021, 12B: 168-11176, 2021.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] In the Appendix.
3. If you experiments...
13

---

(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [No] We consider toy experiments, on which variance is insignificantly low.
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasnng new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "L7zE4PKaXtW", "reviewer": "Reviewer_seXB", "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.", "questions": "See weaknesses.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper provides the first theoretical study that models the benefits of finite smoothing (mean aggregation) before oversmoothing occurs.\n2. The paper is well organized and easy to follow.\n\n\nWeaknesses:\n1. The authors may want to conduct experiments on some large-scale datasets, such as OGB [1].\n2. The authors may want to analyze some non-linear GNNs, which are more useful and powerful for large-scale datasets than linear GNNs.\n3. The authors may want to provide approaches to efficiently compute or estimate the optimal smoothing point, which is useful in practice.\n[1] Hu, Weihua, et al. \"Open graph benchmark: Datasets for machine learning on graphs.\" Advances in neural information processing systems 2020.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "J5oSff7kvAa", "reviewer": "Reviewer_hUnE", "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.", "questions": "Questions and further feedback:\n\n- 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)}$?\n\n- 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?\n\n- 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.\n\n- 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?\n\nConclusions: \n\nIt 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.", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nNovelty 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.\n\nStrengths: \n\n- The paper is elegant and no clear improvements are needed on the presentation front.\n\n- 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?\n\n- 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.\n\n- I appreciate the efforts to comment on the technical assumption 1 and to provide some intuition based on principal components. \n\nWeaknesses:\n\n- 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. \n\n- Connected to the first point, the paper does analyse the easier problem of MPNNs \"in the case of homophily\". In fact, the underlying \nassumption 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. \n\n- 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.\n  \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8NjjITjAdf7", "reviewer": "Reviewer_Xj6j", "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.", "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.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The writing is neat and easy to follow.  \n- The theoretical foundation is solid.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3-nwCJ1EuGg", "reviewer": "Reviewer_k824", "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.  ", "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 ?\n", "limitations": "Technical results with no immediate societal impact.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: a simple, clear and instructive analysis bearing on a question of much current interest.\n\nWeakness: more could be said about the simple model, for example about the question raised below.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept