A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks
Authors: Xinyi Wu
Zhengdao Chen
William Wei Wang
Ali Jadbabaie
Venue: ICLR 2023 poster (2023)
Keywords: graph neural networks
oversmoothing
representational power
theory
deep learning

Abstract: Oversmoothing is a central challenge of building more powerful Graph Neural Networks (GNNs). While previous works have only demonstrated that oversmoothing is inevitable when the number of graph convolutions tends to infinity, in this paper, we precisely characterize the mechanism behind the phenomenon via a non-asymptotic analysis. Specifically, we distinguish between two different effects when applying graph convolutions—an undesirable mixing effect that homogenizes node representations in different classes, and a desirable denoising effect that homogenizes node representations in the same class. By quantifying these two effects on random graphs sampled from the Contextual Stochastic Block Model (CSBM), we show that oversmoothing happens once the mixing effect starts to dominate the denoising effect, and the number of layers required for this transition is $O(\log N/\log (\log N))$ for sufficiently dense graphs with $N$ nodes. We also extend our analysis to study the effects of Personalized PageRank (PPR), or equivalently, the effects of initial residual connections on oversmoothing. Our results suggest that while PPR mitigates oversmoothing at deeper layers, PPR-based architectures still achieve their best performance at a shallow depth and are outperformed by the graph convolution approach on certain graphs. Finally, we support our theoretical results with numerical experiments, which further suggest that the oversmoothing phenomenon observed in practice can be magnified by the difficulty of optimizing deep GNN models.

Published as a conference paper at ICLR 2023
A NON-ASYMPTOTH ANALYSIS OF OVERSMOOTHING IN GRAPH NEURAL NETWORKS
Xinyi Wu', Zhengdao Chen?: William Wang', Ali Jadbabaie' 'Laboratory for Information and Decision Systems (LIDS), MIT Courant Institute of Mathematical Sciences, New York University (xinyiwu, wwang314 4, jadbabai j@mit. edu, zc121 6dn
ABSTRACT
Oversmoothing is a central challenge of building more powerful Graph Neural Networks (GNNs). While previous works have only demonstrated that over- smoothing is inevitable when the number of graph convolutions tends to infinity, in this paper, precisely characterize the mechanism behind the phenomenon via a non-asymptotic analysis. Specifically, we distinguish between two differ- ent effects when applying graph convolutions-an undesirable mixing effect that homogenizes node representations in different classes, and desirable denois- ing effect that homogenizes node representations the same class. By quantify- ing these two effects on random graphs sampled from the Contextual Stochastic Block Model (CSBM), we show that oversmoothing happens once the mixing ef- fect starts to dominate the denoising effect, and the number of layers required for this transition is Olog // log(log N)) for sufficiently dense graphs with N nodes. We also extend our analysis to study the effects of Personalized PageRank (PPR), or equivalently, the effects of initial residual connections on oversmooth- ing. Our results suggest that while PPR mitigates oversmoothing at deeper layers, PPR-based architectures still achieve their best performance at shallow depth and are outperformed by the graph convolution approach certain graphs. Finally, we support our theoretical results with numerical experiments, which further sug- gest that the oversmoothing phenomenon observed in practice be magnified by the difficulty of optimizing deep GNN models.
INTRODUCTION
Graph Neural Networks (GNNs) are a powerful framework for learning with graph-structured
data (Gori al. 2005; Scarselli al. 2009 Bruna al. 2014 Duvenaud et al.) 2015| Deffer- Battaglia et al. 2016 et al. 2016). Most GNN models are built by stacking layers Giimer et al. (017), where the representation of
rard et al. 2016
graph convolutions or message-passnn
each node is computed by recursively aggregating and transforming the representations of its neigh- boring nodes. The most representative and popular example is the Graph Convolutional Network (GCN) (Kipf & Welling (017). which has demonstrated success in node classification. primary graph task which asks for node labels and identifies community structures in real graphs.
Despite these achievements, the choice of depth for these GNN models remains an intriguing ques- tion. GNNs often achieve optimal classification performance when networks are shallow. Many widely used GNNs such as the GCN are no deeper than 4 layers (Kipf & Welling 2017: Wu et al.) 2019) and it has been observed that for deeper GNNs repeated message-passingg makes node repre- sentations in different classes indistinguishable and leads to lower node classification accuracy
phenomenon known as oversmoothing Kiipf & Welling 2017 Li et al. 2018
Klicpera et al.) 2019
Wu et al.) 2019 Oono & Suzuki 2020 Chen et al. 2020a
Through the insight that graph convolutions can be regarded as low-pass filters on graph signals, prior studies have estab- lished that oversmoothing inevitable when the number of layers in GNN increases infinity (Li et al. 20188 Oono & Suzuki 2020). However, these asymptotic analyses do not fully explain the rapid occurrence of oversmoothing when we increase the network depth, let alone the fact that for some datasets, having no graph convolution is even optimal (Liu et al,, 202T). These observations motivate the following key questions about oversmoothing in GNNs:
Keriven 2022
NNow at Google.

---

Published as a conference paper at ICLR 2023
ellest dlamriiing offectt
Figure 1: Stacking GNN layers increases both the mixing and denoising effects counteracting each other. Depending on the graph properties, either the denoising effect dominates the mixing effect, resulting less difficulty classifying nodes (A), or the mixing effect dominates the denoising effect, resulting in more difficulty classifying nodes (B)-this is when oversmoothing starts to happen.
Why does oversmoothing happen at relatively shallow depth?
Can we quantitatively model the effect of applying a finite number of graph convolutions and theoretically predict the "sweet spot" for the choice of depth?
In this paper, we propose non-asymptotic analysis framework to study the effects of graph convo- lutions and oversmoothing using the Contextual Stochastic Block Model (CSBM) (Deshpande et al.j 2018). The CSBM mimics the community structure of real graphs and enables us evaluate the performance of linear GNNs through the probabilistic model with ground truth community labels. More importantly,
generative model, the CSBM gives full control over the graph structure and allows us to analyze the effect of graph convolutions non-asymptotically, In particular, we distinguish between counteracting effects of graph convolutions:
mixing effect (undesirable): homogenizing node representations in different classes; denoising effect (desirable): homogenizing node representations in the same class.
Adding graph convolutions will increase both the mixing and denoising effects. As a result, over- smoothing happens not just because the mixing effect keeps accumulating as the depth increases, on which the asymptotic analyses are based (Li et al. [018 Oono Suzuki, 2020), but rather because the mixing effect starts to dominate the denoising effect (see Figure for a schematic illustration). By quantifying both effects as a function of the model depth, we show that the turning point of the tradeoff between the two effects is Oloog N/ log(log N)) for graphs with N nodes sampled from the CSBM in sufficiently dense regimes. Besides new theory, this paper also presents numerical results directly comparing theoretical predictions and empirical results. This comparison leads to new insights highlighting the fact that the oversmoothing phenomenon observed in practice is often mixture of pure oversmoothing and difficulty of optimizing weights in deep GNN models.
In addition, we apply our framework to analyze the effects of Personalized PageRank (PPR) on oversmoothing. Personalized propagation of neural predictions (PPNP) and its approximate vari- ant (APPNP) make use of PPR and its approximate variant, respectively, and were proposed as a solution to mitigate oversmoothing while retaining the ability aggregate information from larger neighborhoods in the graph (Klicpera et al., 2019). We show mathematically that PPR makes the model performance more robust increasing number of layers by reducing the mixing effect each layer, while it nonetheless reduces the desirable denoising effect at the same time. For graphs with large size or strong community structure, the reduction of the denoising effect would be greater than the reduction of the mixing effect and thus PPNP and APPNP would perform worse than the vanilla GNN on those graphs.
Our contributions are summarized follows:
We show that adding graph convolutions strengthens the denoising effect while exacerbates the mixing effect. Oversmoothing happens because the mixing effect dominates the denoising effect beyond certain depth. For sufficiently dense CSBM graphs with N nodes, the required number of layers for this to happen is Ollog N/ log(log N)).
We apply our framework to rigorously characterize the effects of PPR on oversmoothing. We show that PPR reduces both the mixing effect and the denoising effect of message-passing and thus does not necessarily improve node classification performance.
We verify our theoretical results in experiments. Through comparison between theory and ex- periments, we find that the difficulty of optimizing weights in deep GNN architectures often aggravates oversmoothing.
2

---

Published as a conference paper at ICLR 2023
2 ADDITIONAL RELATED WORK
Oversmoothing well-known issue in deep GNNs, and many techniques have been proposed to relieve it practically (Xu et al. 2018 Li et al. 2019 Chen ct al., 2020b; Huang et al. 2020; Zhao & Akoglu 2020p. On the theory side, prior works have shown that the model depth goes to infinity, the node representations within each connected component of the graph will converge to the same values (Li et al.] 2018: Oono & Suzuki 2020). However, The early onset of oversmoothing renders it important concern in practice, and it has not been satisfyingly explained by the previous asymptotic studies. Our work addresses this gap by quantifying the effects of graph convolutions as function of model depth and justifying why oversmoothing happens in shallow GNNs. A recent study shared a similar insight of distinguishing between two competing effects of message-passing and showed the existence of an optimal number of layers for node prediction tasks on a latent space random graph model. But the result had no further quantification on the optimal depth and hence the oversmoothing phenomenon was still only characterized asymptotically (Keriven 2022).
Oversmoothing problem in GNNs
Analysis of GNNs on CSBMs Stochastic block models (SBMs) and their contextual counterparts have been widely used to study node classification problems (Abbel 2018 Chen et al., 2019). Re- cently there have been several works proposing to use CSBMs to theoretically analyze GNNs for the node classification task. [Wei et al. (2022) used CSBMs to study the function of nonlinearity on the node classification performance, while Fountoulakis et al. (2022) used CSBMs to study the attention-based GNNs. More relevantly, |Barawwal et al. [222 2022) showed the advantage of ap- plying graph convolutions up to three times for node classification on CSBM graphs. Nonetheless, they only focused on the desirable denoising effect of graph convolution instead of its tradeoff with the undesirable mixing effect, and therefore did not explain the occurrence of oversmoothing.
PROBLEM SETTING AND MAIN RESULTS
We first introduce our theoretical analysis setup using the Contextual Stochastic Block Model (CSBM), a random graph model with planted community structure (Deshpande et al. 2018 Baran- wal et al. 2021 2022] Ma et al.) [022]] Wei et al.) [2022] Fountoulakis et al.] 2022). We then present a set of theoretical results establishing bounds for the representation power of GNNs in terms of the best-case node classification accuracy. The proofs of all the theorems and additional claims will be provided in the Appendix.
3.1 NOTATIONS
We represent an undirected graph with N nodes by G = X), where A E (0. 1NNN is the adjacency matrix and X R- is the node feature vector. For nodes u, v E [N], Aue 1 if and only if u and v are connected with an edge in G. and X,, E RR represents the node feature of u. We let n denote the all-one vector of length N and D diag(AI v) be the degree matrix of G.
3.2 THEORETICAL ANALYSIS FRAMEWORK
Contextual Stochastic Block Models We will focus on the case where the CSBM consists of two classes C₁ and C2 of nodes of equal size, in total with N nodes. For any two nodes in the graph, if they are from the same class, they are connected by an edge independently with probability p. or if they are from different classes, the probability is q. For each node v E C,, {1, 2). the initial feature X, is sampled independently from Gaussian distribution M(4, o²), where 14; E RR a E (0, oo). Without loss of generality, we assume that μ1 < #2. We denote a graph generated from such a CSBM as (AA, X) CSBM(N, p. M1, M2, d²). We further impose the following assumption the CSBM used in our analysis.
Assumption 1. p.q wlog N/N) and p > q 0.
The choice p. 4 = (log N/N) ensures that the generated graph 9 is connected almost surely (Abbel 2018 while being slightly more general than the p.q (log N/N) regime considered in some concurrent works (Baranwal et al. 2021 Wei et al. 2022). In addition, this regime also guarantees that G has a small diameter. Real-world graphs are known to exhibit the "small- world" phenomenon even if the number of nodes N is very large, the diameter of graph remains small (Girvan& & Newman 2002 Chung 2010).. We will see in the theoretical analysis (Section 333) how this -ialled characteristic contributes to the occurrence of oversmoothing in shallow
3

---

Published as a conference paper at ICLR 2023
GNNs. We remark that our results in fact hold for the more general choice of p.g 2(log N/N), for which only the concentration bound in Theorem needs to be modified in the threshold log N/N case where all the constants need more careful treatment.
q ensures that the graph structure has homophily, meaning that nodes from the same class are more likely to be connected than nodes from different classes. This characteristic observed in a wide range of real-world graphs (Easley & Kleinberg 2010 Ma al.) 2022). We note that this homophily assumption (p > q) is not essential to our analysis, though we add it for simplicity since the discussion of homophily versus heterophily (p < q) not the focus of our paper.
Further, the choice
Graph convolution and linear GNN In this paper, our theoretical analysis focuses on the sim- plified linear GNN model defined as follows: a graph convolution using the (left- seftt)noommlized ad- jacency matrix takes the operation h' (D-1 (D-lA)h, where and h' are the input and output node representations, respectively. A linear GNN layer can then be defined as h' = (D "A)hW, where W is a learnable weight matrix. As a result, the output of n linear GNN layers can be written as h(*) II W((), where (mm) (D= X is the output of n graph convolutions, and (*)) the weight matrix of the 4thh layer. Since this is linear (, it follows that r--aaer linear GNNs have the equivalent representation power as linear classifiers applied to h(m)
In practice, when building GNN models, nonlinear activation functions can be added between con- secutive linear GNN layers. For additional results showing that adding certain nonlinearity would not improve the classification performance, see Appendix K.1
Bayes error rate and z-score Thanks to the linearity of the model, we see that the representation of node C, after n graph convolutions is distributed as M((xg") (n) (o())))), where the variance (aim))2 is shared between classes. The optimal node-wise classifier in this case the Bayes optimal classifier, given by the following lemma.
Lemma 1. Suppose the label y is drawn uniformly from {1, 2). and given y. x ~ N( (1)))))). Then the Bayes optimal classifier, which minimizes the probability of misclassification among all
classifiers, has decision boundary D (11 (22)/2, and predicts y = 1, S D ory 2, if D. The associated Bayes error rate is 1 1 (22 where & denotes the cumulative distribution
function of the standard Gaussian distribution and =(n) = [ (m) (1))) ) is the z-score of 'D with respect to N (1 (o(n)))).
Lemma D states that we can estimate the optimal performance of an n-layer linear GNN through the z-score (m) ((1) - p. (((m), A higher z-score indicates a smaller Bayes error rate, and hence better expected performance of node classification. The z-score serves as basis for our quantitative analysis of oversmoothing. In the following section, by estimating μr2 pi (n) and (o(") we quantify the two counteracting effects of graph convolutions and obtain bounds on the z-score 2(n) as a function of n, which allows us to characterize oversmoothing quantita- tively. Specifically, there are two potential interpretations of oversmoothing based on the z-score:
(1) ((n) < 2(("), where n² = arg max,'' 2(m'); and (2) (nn)) < 20 They correspond to the cases (1) > n²: and (2) n > no. where no 2 0 denotes the number of layers that yield z-score on par with 20)) The bounds on the z-score 2""), 2lower and Zupper. enable us to estimate n² and no under
(n)
(n)
different scenarios and provide insights into the optimal choice of depth.
3.3 MAIN RESULTS
We first estimate the gap between the means Mi 21 - 1 measures how much node representations in different classes have homogenized after n GNN layers, which is the undesirable mixing effect.
(x)
Mi (n)
with respect to the number of layers n.
Lemma 2. For n E NU (0), assuming D A R E
[
-1]
1 - 11 = p P-4
- (12-
pp4
Lemma states that the means μi (a) and p2 (n) (n) will converge the same value (in this case (n(")) + 112 )/2)) The rate of change
get closer exponentially fast and as n - co, both
(n) and p2
4

---

Published as a conference paper at ICLR 2023
g)/p) q) is determined by the intra-community edge density p and the inter-community edge density q. Lemma 2 suggests that graphs with higher communityy density (q) or lower intra-community density (p) expected to suffer from higher mixing effect when we perform message-passing. We provide the following concentration bound for our estimate of μ P1 Mi., which states that the estimate concentrates at a rate of (p QQ)-
(n)
Theorem 1. Fix K E N and r > O. There exists a constant C(r, K) such that with probability at least 1 - O(1/N*) it holds for all 1 I k v K that
4-4 142 (K) 11 ( 7
- (22-Ni)1
C
VN(++9)
We then study the variance (2) with respect to the number of layers n. The variance (n))) measures how much the node representations in the same class have homogenized, which is the desirable denoising effect. We first state that no matter how many layers are applied, there is nontrivial fixed lower bound for (a(*))² 2 for graph with N nodes.
Lemma 3. For all n E N (0), OO² S ( s
Lemma 3 iiplies that for given graph, even as the number of layers goes to infinity, the variance (n(m) does not converge to zero, meaning that there is a fixed lower bound for the denoising effect. See Appendix K.2 for the exact theoretical limit for the variance (or(m)² as n goes to infinity. We now establish set of more precise upper and lower bounds for the variance (a(")) with respect to the number of layers in the following technical lemma.
Lemma 4. Let a = Np/ log N. With probability at least 1 - O(1/N) it holds for all 1 S n S
that
minfa, 2}
11
0² (a/ (Np) N
10
( S min
Σ k
9
(n 2h + (Np)
2
2n-2h 2k
min(a, 2]
+
Lemma hoold for all 1 < S N and directly leads to the following theorem with clarified upper bound where n is bounded by a constant K.
Theorem 2. Let >Np/ log N. Fix K E N. There exists a constant C(K) such that with probability least O(1/N holds for all 1 S S K that
mi
1
11 N 0 (a < min
min 2} (N 9)) J
C
max
10
(Np)"
Theorem states that the variance (n)) for each Gaussian distribution decreases more for larger graphs or denser graphs. Moreover, the upper bound implies that the variance (a("))² will initially go down at least at rate exponential in ( log N) before reaching the fixed lower bound o² / suggested by Lemma 3 This means that after (log N/ log(log N)) layers, the desirable denoising effect homogenizing node representations in the same class will saturate and the undesirable mixing effect will start to dominate.
Why does oversmoothing happen a shallow depth? For each node, message-passing with different-class nodes homogenizes their representations exponentially. The exponential rate depends on the fraction of different-class neighbors among all neighbors (Lemma 2 mixing effect). Mean- while, message-passingg passiig with nodes that have not been encountered before causes the denoising effect, and the magnitude depends on the absolute number of newly encountered neighbors. The diameter of the graph is approximately log N/ (og(Np) in the p. q = ?(log N/N) regime (Grabam & Lu 2001), and thus is at most log N/ log(log N) in our case. After the number of layers sur- passes the diameter, for each node, there will be no nodes that have not been encountered before in denoising effect).
message-passing and hence the denoising effect will almost vanish (Theorem 2 log N/ log(log N) grows very slowly with N: for example, when N 10 log N log(log N) as 8. This is why even in a large graph, the mixing effect will quickly dominate the denoising effect when increase the number of layers, and oversmoothing is expected to happen shallow depth.
Our theory suggests that the optimal number of layers, n²", is at most Ollog N/ log(log N)). For quantitative estimate, we can Lemma and Lemma compute bounds 2lower and
[In)
5

---

Published as a conference paper at ICLR 2023
(n) Aupper for (12 (m) - Appendix H for detailed discussion.
Mi //(()) and use them to infer nz" and no. defined in Section 3.2 See
Next, investigate the effect of increasing the dimension of the node features X. So far, have only considered the case with one-dimensional node features. The following proposition states that if features in each dimension are independent, increasing input feature dimension decreases the Bayes error rate for fixed n. The intuition is that when node features provide more evidence for classification, it easier to classify nodes correctly.
Proposition 1. Let the input feature dimension be d, X E RN Without loss of generality, suppose for node u in Cs, initial node feature X, ~ [[luu]",o²1, independently. Then the Bayes error rate
Vd (16
(1))
(/d (12 /lm)))) where denotes the cumulative distribution function = 11-1-
1 1--1- 1
of the standard Gaussian distribution. Hence the Bayes error rate is decreasing in d, and as d -+ cc, converges to O.
4 THE EFFECTS OF PERSONALIZED PAGERANK ON OVERSMOOTHING
Our analysis framework in Section 3.3 can also be applied GNNs with other mnessage-passing schemes. Specifically, we can analyze the performance of Personalized Propagation of Neural Predictions (PPNP) and its approximate variant, Approximate PPNP (APPNP), which were pro- posed for alleviating oversmoothing while still making use of multi-hop information in the graph. Personalized PageRank (PPR) or the approximate Personalized PageR-
The main idea is ank (APPR) in place of graph convolutions (Klicpera et al. 2019). Mathematically, the output of PPNP can be written 1 PPNP a(TN APPPN((++1)
()( 1)), while APPNP computes (1 (D- APAAPP))()) -))AAA))AAPP + ax iteratively in n, where IN is the identity ma- trix of size N and in both cases a is the teleportation probability. Then for nodes in C,, i E {1,2),
the node representations follow a Gaussian distribution /V (1EPSP (GPPN)))) after applying PPNP, or a Gaussian distribution N/ (1, APPNP(R) (PPPPN(())) after applying n APPNP layers.
We quantify the effects on the means and variances for PPNP and APPNP in the CSBM case. We can similarly use them calculate the z-score of (μ + M2) 2 and compare it to the one derived for the baseline GNN in Section 3] The key idea is that the PPR propagation can be written as
weighted average of the standard message-passing, i.e. a(Ix - (1 a)(D-IA)) A)) = Ek=o(1
()* A)* (Andersen et al. 2006). We first state the resulting mixing effect measured by the difference between the two means.
Proposition 2. Fix O, K E N. For PPNP, with probability at least 1 O(1/N"), there exists constant C(a, r, K) such that
PPNP
PUNP
p +
(122 1L) te.
+
2-0
where the error term |c| S C/CNC//N + (1 a) K+1
Proposition 3. Let > O. For APPNP, with probability at least 1- O11NN"") APPNP())
APPNP(n)
( p+g 1
(2 2x)g (1 a)"
2 ( ( (#2 m1) te.
P1 -P
up + a)y
where the error term is the same as the one defined in Theorem for the case of K = n.
Both
p+ 2=ng and (2-2a)g
12-(2-004 (1-a)
are monotone increasing in a. Hence from Proposition
p+4
3 3. we see that with larger a, meaning higher probability of celepotatiion back to the root node at each step of message-pan paassing, PPNP and APPNP will indeed make the difference between the means of the two classes larger: while the difference in means for the baseline GNN decays as (P-g) " the p++/ difference for PPNP/APPNP is lower bounded by a constant. This validates the original intuition behind PPNP and APPNP that compared to the baseline GNN, they reduce the mixing effect of message-passinng as staying closer to the root node means aggregating less information from nodes of different classes. This advantage becomes more prominent when is larger, where the model performance is dominated by the mixing effect: as n tends to infinity, while the means converge to the same value for the baseline GNN, their separation is lower-bounded for PPNP/APPNP.

---

Published as a conference paper at ICLR 2023
However, the problem with the previous intuition is that PPNP and APPNP will also reduce the denoising effect at each layer, as staying closer to the root node also means aggregating less infor- mation from new nodes that have not been encountered before. Hence, for arbitrary graph, the result of the tradeoff after the reduction of both effects is not trivial to analyze. Here, we quantify the resulting denoising effect for CSBM graphs measured by the variances. We denote (a(*)) upper as the variance upper bound for depth n in Lemma
Proposition 4. For PPNP, with probability at least
O(1/N), it holds for all S K S N that > (1 a)* Viown Yupper
a min(a, 2}
1 1) o² s (0 < max a²
a) K+1
max
10
N
Proposition 5. For APPNP, with probability at least 1 O(1/N), it holds for all n N that
min((,2) 2}
(a² (1-a)* a)
N o² s (AAPeNP(n)))
max
10
(Np)
{(
Σ (1 {a{
n-1
(o APPNNRCN)
I min
a)*
V (o((1)) Roper
+ - a)" "ii"VV(oooii" ((r
By comparing the lower bounds in Proposition 4 and with that in Theorem 2 we that PPR reduces the beneficial denoising effect of message-passingg for large or dense graphs, while the vari- ances for the baseline GNN decay as 1/(Np)", the variances for PPNP/APPNP by the constant a minfa, 20/10. 10. In total, the mixing effect is reduced by factor of (p=9)², while the denoising effect is reduced by a factor of 1/(Np)" Hence PPR would cause greater reduction in the denoising effect than the improvement in the mixing effect for graphs where NN and are large. This drawback would be especially notable at a shallow depth, where the denoising effect is supposed to dominate the mixing effect. APPNP would perform worse than the baseline GNN on these graphs in terms of the optimal classification performance.
lower bounded
We remark that in each APPNP layer, another way to interpret the term a.X is to regard it as resid- ual connection to the initial representation X (Chen et al., 2020b). Thus, our theory also validates the empirical observation that adding initial residual connections allows to build very deep models without catastrophic oversmoothing. However, our results suggest that initial residual connections do not guarantec an improvement in model performance by themselves.
5 EXPERIMENTS
In this section, we first demonstrate our theoretical results in previous sections on synthetic CSBM data. Then we discuss the role of optimizing weights ((k) in GNN layers in the occurrence of oversmoothing through both synthetic data and the three widely used benchmarks: Cora, CiteSeer and PubMed (Yang al. 2016). Our results highlight the fact that the oversmoothing phenomenon observed in practice can be exacerbated by the difficulty of optimizing weights in deep GNN models. More details about the experiments are provided in Appendix 0
5.1 THE EFFECT OF GRAPH TOPOLOGY ON OVERSMOOTHING
We first show how graph topology affects the occurrence of oversmoothing and the effects of PPR.
We randomly generated synthetic graph data from CSBM(N 2000, p. q 0.0038, μl 1, #22 = 1.3, o² = 1). We used 60%/20% /20% random splits and ran GNN and APPNP with a = 0.1. we report
For results in Figure 2 we report averages over graphs and for results in Figure B.
averages over 5 runs.
In Figure 2 we study how the strength of community structure affects oversmoothing. We can see that when graphs have stronger community structure in terms of a higher intra-community edge density p. they would benefit more from repeated message- message-passing. As result, given the same set of node features, oversmoothing would happen later and a classifier could achieve better classification performance. A similar trend can also be observed in Figure 4A. Our theory predicts n and r2p, as defined in Section 3.2 with high accuracy.
In Figure 3 we compare APPNP and GNN under different graph topologies. In all three cases, APPNP manifests its advantage of reducing the mixing effect compared to GNN when the number
7

---

Published as a conference paper at ICLR 2023
of layers is large, i.e. when the undesirable mixing effect is dominant. However, Figure BB,C show, when we have large graphs or graphs with strong community structure, APPNP's disadvan- tage of concurrently reducing the denoising effect is more severe, particularly when the number of layers is small. As a result, APPNP's optimal performance is worse than the baseline GNN. These observations accord well with our theoretical discussions in Section 4
B
best accuracy
bostt bostt accuracy
15
255
35
- Mp/logg
--lplog
2 Npllogg
Figure 2: How the strength of community structure affects oversmoothing. When graphs have stronger community structure (i.e. higher a), oversmoothing would happen later. Our theory (gray bar) predicts the optimal number of layers n² in practice (blue) with high accuracy (A). Given the same set of features, a classifier has significantly better performance on graphs with higher (B,C).
A (base case) N-2000, p-7.66 pio-2:1
B (larger graph)
C (stronger community)
N 10000, p-7.60 3, p:q-2:1
N-2000, p-2 p-2 piq 6:
1.0
1.0
test accuracy
GAN
GAN
0.9
0.8
0.8
0.8
0.6-
0.6
0.6
0.1
20 0.1
15 0.4
10 15
10
10
number of layers
Figure 3: Comparison of node classification performance between the baseline GNN and APPNP. The performance of APPNP is more robust when we increase the model depth. However, compared to the base case (A), APPNP tends to have worse optimal performance than GNN graphs with larger size (B) or stronger community structure (C), as predicted by the theory.
5.2 THE EFFECT OPTIMIZING WEIGHTS ON OVERSMOOTHING
We investigate how adding learnable weights (kk) in each GNN layers affects the node classifi- cation performance in practice. Consider the case when all the GNN layers used have width one, meaning that the learnable weight matrix ((k) in each layer is a scalar. In theory, the effects of adding such weights on the means and the variances would cancel each other and therefore they would not affect the z-score of our interest and the classification performance. Figure A shows the the value of no predicted by the z-score, the actual no without learnable weights according to the test accuracy and the actual no with learnable weights according the test accuracy. The results are averages over 5 graphs for each case. We empirically observe that GNNs with weights are much harder to train, and the difficulty increases as increase the number of layers. As result, no is smaller for the model with weights and the gap is larger when no is supposed to be larger, possibly due to greater difficulty in optimizing deeper architectures (Shamir 2019).
To relieve this potential optimization problem, we increase the width of each GNN layer (Du & Hu 2019). Figure CB.C presents the training and testing accuracies of GNNs with increasing width with respect the number of layers on a specific synthetic example. The results are averages over 5 runs. We observe that increasing the width of the network mitigates the difficulty of optimiz- ing weights, and the performance after adding weights able to gradually match the performance without weights. This empirically validates our claim in Section 3.2 that adding learnable weights should not affect the representation power of GNN in terms of node classification accuracy on CSBM graphs, besides empirical optimization issues.
In practice as we build deeper GNNs for more complicated tasks on real graph data, the difficulty of optimizing weights in deep GNN models persists. We revisit the multi-class node classification task on the three widely used benchmark datasets: Cora, CiteSeer and PubMed (Yang et al. 2016). We compare the performance of GNN without weights against the performance of GNN with weights
8

---

Published as a conference paper at ICLR 2023
A
B
P:Q=6:1
P:q-6:2
1.0
STRROFA vieees 202-130
Fammnn sccung
number of layers
number of layers
Figure 4: The effect of optimizing weights on oversmoothing using synthetic CSBM data. Compared to the GNN without weights, oversmoothing happens much sooner after adding learnable weights in each GNN layer, although these two models have the same representation power (A), As we increase the width of each GNN layer, the performance of GNN with weights able to gradually match that of GNN without weights (B,C).
Cora
CiteSeer
PubMed
test accuracy
Newegta vi
16 15
28
25
number of layons
number of layers
number layers
Figure 5: The effect of optimizing weights on oversmoothing using real-world benchmark datasets. Adding learnable weights each GNN layer does not improve node classification performance but rather leads to optimization difficulty.
in terms of test accuracy. We used 60% 20% 2000 /0% random splits, as in Wang & Leskovec (2020) and Huang al. (222I) and report averages over 5 runs. Figure shows the same kind of difficulty in optimizing deeper models with learnable weights in each GNN layer as we have seen for the synthetic data. Increasing the width of each GNN layer still mitigates the problem for shallower models, but it becomes much more difficult to tackle beyond 10 layers to the point that simply increasing the width could not solve it. As a result, although GNNs with and without weights are on par with each other when both are shallow, the former has much worse performance when the number of layers goes beyond 10. These results suggest that the oversmoothing phenomenon observed in practice is aggravated by the difficulty of optimizing deep GNN models.
DISCUSSION
Designing more powerful GNNs requires deeper understanding of current GNNs how they work and why they fail. In this paper, precisely characterize the mechanism of overmoothing via non-asymptotic analysis and justify why oversmoothing happens at a shallow depth. Our analysis suggests that oversmoothing happens once the undesirable mixing effect homogenizing node repre- sentations in different classes starts to dominate the desirable denoising effect homogenizing node representations in the same class. Due to the small diameter characteristic of real graphs, the turning point of the tradcoff will occur after only a few rounds of mnessage-passing resulting in oversmooth- ing in shallow GNNs.
It is worth noting that oversmoothing becomes important problem in the literature partly because typical Convolutional Neural Networks (CNNs) used for image processing are much deeper than GNNs (He et al. 2016). As such, researchers have been trying to use methods that have previously worked for CNNs to make current GNNs deeper (Li et al.) 2019 Chen et al. 20206). However, images can be regarded as giant grids with high diameter. This contrasts with with real-world graphs, which often have much smaller diameters. Hence we believe that building more powerful GNNs will require to think beyond CNNs and images and take advantage of the structure in real graphs.
There are many outlooks to our work and possible directions for further research. First, while our of the CSBM provided important insights into GNNs, it will be helpful to incorporate other real graph properties such as degree heterogeneity in the analysis. Additionally, further research can focus on the learning perspective of the problem.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This research has been supported by a Vannevar Bush Fellowship from the Office of the Secretary of Defense. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted necessarily representing the official policies or endorsements, either expressed or implied, the Department of Defense or the U.S. Government.
REFERENCES
Emmanuel Abbe. Community detection and stochastic block models. Foundations and Trends in Communications and Information Theory, 14:1-162, 2018.
Reid Andersen, Fan Chung Graham, and Kevin Lang. Local graph partitioning using pagerank vectors. In FOCS, 2006.
Afonso S Bandeira and Ramon Van Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. The Annals of Probability, 44(4):2479-25 2506, 2016.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi- supervised classification: Improved linear separability and out-of-distribution generalization. In ICML, 2021.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of graph convolutions in deep networks. ArXiv, http//244.09297,, 2022.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, and koray kavukcuoglu. Interaction networks for learning about objects, relations and physics. In NeurIPS, 2016.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: nonasymp- lotic theory of independence. Oxford university press, 2013.
Joan Bruna, Wojciech Zaremba, Arthur D. Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. In ICLR, 2014.
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. In AAAI, 2020a.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks, In JCML, 2020b.
Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community detection with line graph neural networks. In ICLR, 2019.
Fan Chung and Linyuan Lu. Concentration inequalities and martingale inequalities: survey. Inter- net mathematics, 3(1):79-127, 2006.
Fan R. K. Chung. Graph theory in the information age. volume 57, pp. 726-732. 2010.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NeurlPS, 2016.
Yash Deshpande, Andrea Montanari, Elchanan Mossel, and Subhabrata Sen. Contextual stochastic block models. In NeurIPS, 2018.
Luc Devroye, László Györfi, and Gábor Lugosi. A probabilistic theory of pattern recognition. In Stochastic Modelling and Applied Probability, 1996.
Simon Shaolei Du and Wei Hu. Width provably matters in optimization for deep linear neural networks. In ICML, 2019.
10

---

Published as a conference paper at ICLR 2023
David Kristjanson Duvenaud, Dougal Maclaurin, Jorge eguilera-Iparragune Rafael Gómez- Bombarelli, Timothy D. Hirzel, Alán Aspuru-Guzik, and Ryan P. Adams. Convolutional networks graphs for learning molecular fingerprints. In NeurlPS, 2015.
David A. Easley and Jon M. Kleinberg. Networks, Crowds, and Markets: Reasoning about a Highly
Connected World. 2010.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Kimon Fountoulakis, Amit Levi, Shenghao Yang, Aseem Baranwal, and Aukosh Jagannath. Graph attention retrospective. ArXiv, abs/2202.13066 2022.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
Michelle Girvan and Mark Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99:7821 7826, 2002.
M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In IJCNN, 2005.
Fan Chung Graham and Linyuan Lu. The diameter of sparse random graphs. Advances in Applied Mathematics, 26:257-279, 2001.
Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R. Benson. Combining label propagation and simple models out-performs graph neural networks. In ICLR, 2021.
Wenbing Huang, Yu Rong, Tingyang Xu, Fuchun Sun, and Junzhou Huang. Tackling over-
smoothing for general graph convolutional networks. arXiv preprint arXiv:2008.09864 2020.
Nicolas Keriven. Not too little, not too much: theoretical analysis of graph (over)smoothing. In NewrlPS, 2022.
Thomas Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019.
Guohao Li, Mathias Müller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? ICCV, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In ICLR, 2016.
Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. IEEE transactions on pattern analysis and machine intelligence, 2021.
Linyuan Lu and Xing Peng. Spectra of edge-independent random graphs. The Electronic Journal of Combinatorics, 20:27, 2013.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? In ICLR, 2022.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In ICLR, 2020.
11

---

Published as a conference paper at ICLR 2023
Adam Paszke, Sam Gross, Francisco Massa, Adam Lever, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Ed- ward Yang, Zach Vito. Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In NeurIPS, 2019.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20:61-80, 2009.
Ohad Shamir. Exponential convergence time of gradient descent for one-dimensional deep linear neural networks. COLT, 2019.
Hongwei Wang and Jure Leskovee. Unifying graph convolutional neural networks and label propa- gation. ArXiv, abs/2002.06755, 2020.
Rongzhe Wei, Haoteng Yin, J. Jia, Austin R. Benson, and Pan Li. Understanding non-linearity in graph neural networks from the bayesian-inference perspective. ArXiv, abs/2207.11311. 2022.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 32:4-24, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, 2018.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In ICML, 2016.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In ICLR, 2020.
A PROOF OF LEMMA
Following the definition of the Bayes optimal classifier (Devroye et al. 1996).
((x) arg Ply i|z],
1,122
we get that the Bayes optimal classifier has a linear decision boundary (#1 + p2)/2 such that the decision rule is
1y=1
if D D
1y=2
Probability of misclassification could be written
Fly = 1, > D) + Ply = S = P(z D = 1|Ply 1] + P|z < Dly = 2|P 2]
2 (P|r > Dly 1| + Pfr < y 2))
= (w1 + p2)/2, the expression is called the Bayes error rate, which is the minimal prob- ability of misclassification among all classifiers. Geometrically, it is easy to see that the Bayes error rate equals J.,, where S is the overlapping area between the two Gaussian distributions N (M("), (a())) and N (m) Hence one can use the z-score of (μ1 + p2)/2 with respect either of the Gaussian distributions directly calculate the Bayes error rate.
When D=
B PROOF LEMMA
Under the heuristic assumption D-1A RJ ((AA), we can write
(1) Pf1 + q12
(1)
PH2 + qp1
"1
11
p 9
12

---

Published as a conference paper at ICLR 2023
(k-11 1)
(R-1)
(k-1)
(R-1)
(k)
9112
(k)
q11
M1
112
for all & E
p +
Writing recursively, we get that
(r) (p + 9)th + (p 9)ah
(p+ + 9) n. (p 9)
11
P2
2(p 9)"
2(p 9)"
(n) (p + 4)"h (p 9)th
(p + 9)"
(p 9)"
P2 2(p + q)"
112
141
2(p + q)"
C PROOF OF THEOREM
We use || ||2 to denote the spectral norm, || maxx:||=||== ||Ar||2 We denote Ā E[A],
D E RDD) AT n and d R[d],. We further define the following relevant vectors:
1N/2
H1 1N/2
11 == IN.
u2 = - (1
142 N/22
The quantity of interest is p12 11
(R)
(R)
N72 W2 (D (D=1A)*..
C.I AUXILIARY RESULTS
We record some properties of the adjaceney matrices:
1. D-1AA and D-1 À have an eigenvalue of 1, corresponding to the (right) eigenvector w1
If Jn I, T. where 1, is all-one vector of length n, then
(pJN/2 qJN/2 (JN/2 pJN(2)
A =
3. D 2% (p IN...
= 0:6 + B32, where a 11 and 111112
2
To control the degree matrix D-1, will the following standard Chernoff bound Chung & Lu (006):
Lemma (Chernoff Bound). Let XI,..., Xa be independent, S := En. X,, and $ -E[S]. Then for all e >> 0,
P(S < $ =) e (25)) F(S 2 $ - é ((2(S+
We thus derive uniform lower bound the degree of every vertex: Corollary 1. For every r > 0, there is a constant C(r) such that whenever d 2 Cloog N, with probability at least N-",
3 dd. for all aall55 ISiSN. 2 d S
Consequently, with probability at least 1 N
S C/d some C.
Proof. By applying Lemma and a union bound, all degrees are within 1 1/2d of their expectations, with probability at least 1 - e d//8+oogg Taking C' = 8r + 8 yields the desired lower bound. An analogous proof works for the upper bound.
To show the latter part, write
d, d d,d
D 10-1_ D D-1122 max 18
Using the above bounds, the numerator for each is at most 1/2d and the denominator for each i is least 1/2d² with probability least 1 N-r. Combining the bounds yields the claim. [
13

---

Published as a conference paper at ICLR 2023
We will also need result concentration of random adjacency matrices, which is corollary of the sharp bounds derived in Bandeira & Van Handel (2016) Lemma 6 (Concentration of Adjacency Matrix). For every r 0, there is a constant C(r) such that whenever d 2 log N, with probability at least N=",
A All2 < CVd.
Proof. By corollary 3.12 from Bandeira & Van Handel (016)) there is constant such that P[ A - Alla 2 3vd - +t S e /x+logg
Setting& & VI 3 v r)x suffices achieve the desired bound.
C.2 SHARP CONCENTRATION OF THE RANDOM WALK OPERATOR D-1A
In this section, we aim to show the following concentration result for the random walk operator D D-'A:
Theorem 3. Suppose the edge probabilities are w log N
and let be the average degree. For any
r, there exists constant C such that for sufficiently large N, with probability at least O(N-))
C
Vd
Proof. We decompose the error
= D- - (D
+ +T2.
where
D= A), T- = - D-
We bound the two terms separately.
Bounding Ti: By Corollary 1
||D~ max; 1/d; S 2/d with probability 1 1- N- Combin-
ing this with Lemma 6 we see that with probability at least - -N
C
(D- A)ll2 D |2
Ale S Vd
for some C depending only
Bounding T2: Similar to Lu Peng (203).. we bound T2 by exploiting the low-rank structure of the expected adjacency matrix, A. Recall that A has a special block form. The cigendecomposition of Á is thus
À Σ Cy
==1
where (1(1) = VN
1 1 A N(ptg)
te(2) (2) = VN
1N/2
A2
N(p 2)
N/2
2
Using the definition of the spectral norm, we can bound
||22||2 as
||2l|2 max
|ID__ D Azrl2
||]||
|I - -- A(ar + (22
max ||||=|
Note that when ||a||2 1,
N
1
2
2
[I(D-1 -
(ID-\-D-')A D-1)A(a('' o2
d
d
1=1
N
2 d
2
Σ
X3
(10
(2)
dj
i=1
j=1
14

---

Published as a conference paper at ICLR 2023
using Canchy-Schwarz. Since |wo
VN for all i, the second summation can be bounded by
N و== Aj. Overall, the upper bound now
1
d 2)²
Σ x3
N
(d,d)2
Under the event of Corollary 1
de 2 Cd for some C < 1. Under our setup, we also have X = d?, X I d² This means that the upper bound is
CA ld di N
where d is the vector of node degrees. It remains to show that x --d-dl x Od). To this, we use a form of Talagrand's concentration inequality, given in Boucheron et al. (2013) Since the (( - dIx) 2|2 is a convex, I-Lipschitz function of A, Theorem 6.10 from Boucheron et al. 2013) guarantees that for any t > 0,
function 1 Jy ld x
ld d1 N112 E
ld N111 +1) S 1212
Using Jensen's 's inequality,
Bllld diN/12l S
BBlld diN 13
Var(d:)= / NVr((d) S v Nd.
If d = w(lo N), we can guarantee that
d dlNl12 & cVa
with probability at least (C- 1)2 O(N-)) for an appropriate constant C. Thus we have shown that with high probability. = = O(1/Vo), which proves the claim.
C.3 PROOF OF THEOREM I
Fix and K. We desire to bound
N/2 W2 ((D-1A)* -D--1A))
By the first property of adjacency matrices in auxiliary results, suffices to bound
N/2 w ((D-) A)* (D J22)
where 3 #12 We will show inductively that there is a such that for every & = 1,.., K,
|((D-AA)* - 1 C/Va.
this is true, then Cauchy-Schwarz -Shwwaz gives
8 Ih (D=*A)* (D- (0-'A))' < 1w2 w22la|1(D--1A)) A)*
-D- 'A)* la)
N/2
N/2
<C/Vd.
By Theorem have that with probability at least O(N-*)
C
10-IA-D-AAI, - Vā
15

---

Published as a conference paper at ICLR 2023
So
where || - C/Vd. Iterating, we have
|I(D-1 A)D A) A(D-1A)*-1D" A- (D-1A)"
Inductively, (D- (D-1A) H where | S C/vd. Plugging this in
1 have
I(D D 1 - = II((D- H) - l2
Of these terms, (D-I has norm at most || H(D-1A) A) has norm at most || and HJ has norm at most C/d Hence the induction step is complete.
We have thus shown that there is a constant Crr, K) such that with probability at least 1 - N-",
N/2 22 ((D- (D-1A)*mls C
d
which proves the claim.
By simulation one can verify that indeed 1
N/2 w2
(pTR) (12-~1). Figure S presents
(n) (() calculated from simulation against predicted values from our theoretical results. The sim- Hi u22
ulation results averaged over 20 instances generated from CSBM(N 2000, 0.0114, 0.0038, #1 12 = 1.5, o² 1).
number of layers
predicted uf"
predicted ul
actual 44th
actual pl
15
Figure 6: Comparison of the mean estimation in Lemma against simulation results.
D PROOF OF LEMMA 3
Fix and let the element in the tth row and jth column of (D-1A)" be Pij Consider fixed node
The variance of the feature for node after n layers of convolutions is (E,(1)) (n) )) by the
basic property of variance of sum. Since E, [pj second inequality.
(n) 1, it follows that (vg (n))a y2 1, which the
To show the first inequality, consider the following optimization problem:
min
Pij I s.t.
(n)
Σrh (n) Pij 1,
(n) 0, I5iSN
Pij
This part of proof goes by contradiction. Suppose 3k, such that Pi # (m) Fixing all other
Pi (n). . k. 1, if we average (() and pa (n) their sum of squares will strictly decrease while not
Moor precisely, the C' becomes O* which why restrict the approximation guarantce constant K.
16

---

Published as a conference paper at ICLR 2023
breaking the constraints:
(n) (n)
2
Pik Pa ((Pik (2 + (2)))))) = --22-11 (Pit (n))
Pii ) <0.
Thus to minimize En(Di (n) N.1 $ S N and the
So obtain contradiction. mimimum is 1/N.
E PROOF OF LEMMA 4
The proof relies on the following definition of neighborhood size: graph 9, we denote by (x) the set of vertices in G at distance k from vertex
[x(x) {y E 9 d(x, y) k}
we define (ar) to be the set of vertices within distance is of x:
(x(2) = Un(
1=0
To prove the lower bound, we first show intermediate step that
NN.. 0 S (n)2))
The proof is the same as the one for the first inequality Lemma 3 except we add in another con- straint that for a fixed i, the row is
This implies that the minimum of Σ, (ply (n)y2 becomes (f) The we apply the result on upper bound of neighborhood sizes in Erdös- Rényi graph ((N,2) p) (Lemma Graham & Lu (00T)), as also serves as upper bound neighborhood sizes in SBM(N, p. q). The result implies that with probability at least O1//N), we have
10
| S
min 2] (Np)". VI SnnSN.
We ignore for N,, because of all nodes are identical CSBM, so the bound applies for every nodes in the graph
The proof of upper bound is combinatorial. Corollary states that when is large, the degree of .N node i is approximately the expected degree in G, namely, E[degree] 2 (p q). Since
Pij
Σ
(3)
deg(i) deg(v1) 'eg( (v
path P= (i. 5
using the approximation of degrees, we get that
(x) Pij = (ND+t) ) (#
2
paths of length n between and j).
Then we use tree approximation to calculate the number of paths P of length between i and by regarding as the root. Note that
ΣV Σ
(p
(4)
k=
and for j E Tr.22, deterministic path P of length n 2k is needed in order reach j from
i. This implies that there are only k steps deviating from Pr There are (n - 2k + 1) ways of choosing when deviate. For each specific way of when deviate, there are approximately E Ejdegree]* ways of choosing the destinations for deviation. Hence in total, for = Tn-2k. there are (n 2k + E path of length n between and Thus
(n) Pij (n 2k + 1)a²
(5)
N(p +
17

---

Published as a conference paper at ICLR 2023
Plug in 5 into 4
we get that
L
2n-2k
2
2
T
24 21
2hc + 1)26
(6)
NN + q)
k=0
#
2
2n-2k
(n 2k (Np)
min
{a, 2]
N + q)
k=
Again, 7 follows from using the upper bound on n- Graham & Lu probability at least 1 O(1/N),
2001 such that with
22-21
9
(Np)
v1
S k
S
n 2
minfa, 2)
Combining with Lemma 3 we obtain the final result.
Figure 7 presents variance calculated from simulation against predicted upper and lower bounds from our theoretical results. The simulation results are averaged over 1000 instances generated from CSBM(N 2000, p- 0.0114, q 0.0038, μui 1, 1.5, o² 1).
1.0
real variance
upper bound lower bound
variance
0.6
6.2
number layers
Figure 7: Comparison of the bounds variance in Theorem 2
Jggaistt simulation results.
F PROOF OF THEOREM 2
When we fix K E N. only the upper bound in Theorem 2 will change. Note that the upper bound in (7 can be written as
1
(n 2k + 1)26
+
2h
2p
2
min 2}
2p
p +
N N(p
q)
C
p
2h
2
n
min 2]
2p
N(p 4)
2
min(a,2) 2}
N(p + q)
G PROOF OF PROPOSITION
Let the node representation vector of node u after graph convolutions be h (n) The Bayes error rate could be written as (IP())") (n) symmetry of our setup, one can easily see that the optimal linear decision boundary is the hyperplane Σj Jj (m u2). Then for E Ci, Σ (I(")), (ddu(") d()(m))2) and for E C2.
D/e E Ci] P[(! < Dlu E C2)). For N. due the
18

---

Published as a conference paper at ICLR 2023
Σz=1 )bb²)) -N(dpz (in) d(((())))) Thus the Bayes error can be written as
( > D/u EGG +
(
S 2/v E C2l)
j=1
5=1
[11 + (2) dup
(1))
á [ + (22 - dui ))
1 क
+
2
(d)
vdo(")
d
[1 + u22 - dji1
= -1- - Φ
2
(d)
The last equality follows from the fact that 1 (11 + (22) dpl") - (2 p2) - dip
H How TO USE THE Z-SCORE TO CHOOSE THE NUMBER OF LAYERS
(n) The bounds of the 7-score with respect to the number of layers, Floer and supper allow to calculate bounds for n²' and no under different scenarios. Specifically,
(n)
1. Vn N, Supper z0) (12 m1)/o, then n no 0. meaning that graph convolution should be applied.
(n)
2. Kn N::: Zupper
(n)
2 (0) 0, and
(a) Vn E N, Flower < (0), then 0 S no S. min EN:: Zupper S 20) which means that the number of graph convolutions should exceed the upper bound of ny. otherwise one gets worse performance than having no graph convolution. Note that in this case, since n² S rig, we can only conclude that
(m)
0 5 n* min(n N:
(n) Zupper S (0)
(b) (n E N (n) Powwrr 2 2011 > 0, then 0 S no m E N Zupper I 20)),, and let
arg max = nioor
max n S. ni
(n) Zupper
Power
S n
< min
n
nover
(n) Zupper
2lower
(11
meaning that the number of layers one should apply for optimal node classification perfor- mance more than the lower bound of n²" and less than the upper bound of n*.
I PROOFS OF PROPOSITION 2
I.1 PROOF OF PROPOSITION
Since the spectral radius of D-1 1,
α Σ
a(d - (1 (1--a) (D- (D--1))))
-1- (D-
k=0
Apply Lemma 2
we get that μb
PPNP
PPNP
pig -
(122 10-m)) v1).
To bound the approximation error, similar to the proof of the concentration bound in Theorem 1 suffices to bound
11
U1 N
((1-a))((D-)))) -))-((()()))) MI 112 -
W2
(Tx + +Tx+1,00)
N
k=0
where Tk
Σk
k=z a(1 ((1-))((D'')>)--))) (D))))))) Tr,,, = - a(1 (D--A)
(D-1 A))),, and K N up choice.
19

---

Published as a conference paper at ICLR 2023
Bounding Tx: Apply Theorem fix
0. there exists constant C(r, a,) such that with
probability 1- 1-00--0 O(N
|xxll2 S Vd
Bounding 1.o We will show upper bound for (D-1A)* (D-1 that applies for all k: E N. Note that for every k E N,
(D-
where D D-1/2AD-1/2 VAVT is the eigenvalue decomposition. Then
[1(D-1A)* ()* 2| - |I |[0= = (I(D-1A)* 122 +
1/21/2 + 1.
Since IKD-1//ADD1133)) 1 and by Corollary with probability at least 1 N
| S / /d//2, || 1 2//d.
the previous inequality becomes |I(D-1A)* - (D-1A)*>le S v3 + 1. Hence
|Tx+1,00||> (1 a) k+1
Combining the two results, we prove the claim.
1.2 PROOF OF PROPOSITION
The claim a direct corollary of Theorem
1.3
PROOF OF PROPOSITION
The covariance matrix PPNP of h PPNP could be written
oc a1-)00011)
PPNP 2
1=0
Note that the variance of node equals a Ee row i of matrix. Then by Cauchy-Schwarz Theorem,
(D) where i refers
(D (D A = || (XI(D
((00))(00033/000 all < N.
Moreover, by Lemma 3 (k))2 < d², bility 1 1 OL/N), for all K N.
Due to the identity of each node i, we get that with proba-
K
PPNP2 < a²
Σ (1 a)²²y ( +
Σ
(1
upper
1=
Á K+1
(1 - k
$ a
Σ (1 a)a aa)v/V(V' (or(4)) km
yupper
a
For the lower bound, note that with probability 1 O1/N),
N Σ
26 1
PPNPP 2 a
(1- 2
+ Σ
N
N
N=
20

---

Published as a conference paper at ICLR 2023
where N₂ is the size of h-hop neighborhood. Then
-1-aa a)2 minfa, 2}
(o a²
0²
10
(Np)*
min 2} (Np) (1-a) 2N
10
(Np) (Np (1 a)2)
min(a. 2]
10
is easy to see that Lemma applies to any message-passing scheme which could be regarded as random walk on the graph. Combining with Lemma we get the final result.
1.4
PROOF OF PROPOSITION
Since
(a Σa-a)( + +1-
APPPN(())
X
k=0
Through the same calculation as for the upper bound the proof of Proposition probability 1 - O(1/N).
we get that with
(PPPNR(N) < a - a² (ool + a1" /
(o(1))
uuppe
For the lower bound, through the same calculation as for the upper bound in the proof of Proposi- tion 2
we get that with probability 1 O(1NN)
n-1
APPNP(N))
a) 2 (0)0) + (1 - 2))
k=0
2 min
2}
(1- a)2t
1
o² +
min 2]
(1 -x)=)
a)2n
1
o²
10
(Np)*
10
(Np)n
k=
minfa,2]
(1-a) a)2n
a² +
0²
10
(Np)
Combining with Lemma
we get the final result.
J EXPERIMENTS
Here provide more details on the models that use in Section 5 optimizer and tune some hyperparameters for better performance. The hyperparameters used are summarized follows.
In all cases use the Adam
Data
final linear classifier
weights in GNN layer
learning rate (width)
iterations (width)
synihetic
layer
yes
(.000-AA66Y0.001666.5566)
0.01
8000
0.001
150
layer with hidden channels
yos
0.001
200
CiteSeer
3 layer with 16 hidden channels
0.001
100
PubMed
3 layer with 32 hidden channels
300
0.001
500
yes
0.001
500
We empirically find that after adding in weights each GNN layer, it takes much longer to train the model for one iteration, and the time increases when the depth or the width increases (Figure g Since for some combinations, takes more than 200,000 iterations for the validation accuracy to finally increase, for each case, we only train for reasonable amount of iterations.
All models were implemented with PyTorch (Paszke et al. 2019) and PyTorch Geometric (Fey & Lenssen 2019).
21

---

Published as a conference paper at ICLR 2023
iterations per second
600
500
400
6th olliwab we gitss or oth--2 we gitss oth-256
300
200
100
5
10
15
20
number layers
Figure 8: Iterations per second for each model.
K ADDITIONAL RESULTS
K.1 EFFECT OF NONLINEARITY CLASSIFICATION PERFORMANCE
In section 3. consider the of simplified linear GNN. What would happen if we add nonlin- earity after linear graph convolutions? Here, we consider the case of a GNN with a ReLU activation function added after n linear graph convolutions, i.c. (") ReLU((D- (A"))())))))).. that adding such nonlinearity does not improve the classification performance.
We show
Proposition 6. Applying ReLU activation function after n linear graph convolutions does not decrease the Bayes error rate, i.e. Bayes error rate based on h (n)RelU > Bayes ervor rate based on mm) and equality holds if p1 2 -22
Proof. is known that if x follows Gaussian distribution, then ReLU((:) follows Rectified Gaus- sian distribution. Following the definition of the Bayes optimal classifier, we present a geometric proof Figure (see next page, top), where the dark blue bar denotes the location of and the red bar denotes the decision boundary D of the Bayes optimal classifier, and the light blue area denotes the overlapping area S, which is twice the Bayes error rate.
#1 2 -2, D P1td2 + D
Pite2
the Bayes error rate stays the same.
ReLU
(n) 11ナ12 (n)
(n)
tit (n)
2 H12
M1
M2
2. 111 < 12, D t1 + D O, the Bayes error rate increases.
ReLU
(n)) pI #Ma (n) f1 2
(m)
(n)
H1z
Figure 9: A geometric proof of Proposition 6
22

---

Published as a conference paper at ICLR 2023
K.2 EXACT LIMIT OF VARIANCE (alm))2 AS +
Proposition 7. Given graph with adjacency matrix A, let its degree vector be d A N, where IN is the all-one vector of length N. IfG is connected and non-bipartite, the variance of each node i, denoted as (o.!m))? converges asymptoticully
|
Le.
[
d
(o, (m)) 2-000
Then [d]] [d]l 2 N. and the equality holds if and only if is regular.
Proof. Let e, denotes the standard basis unit vector with the 7t entry equals 1, and all other entries equal O. Since G is connected and non-bipartite, the random walk represented by P D ergodic, meaning that
p(n) n
where is the stationary distribution of this random walk with क. continuous functions, we conclude that
Then since norms are
I|d
|d| |d]]
(o, (2)) Σ ( ||e] 1 n- ||
By Lemma 3 it follows that
|d] |
2 N The unique minimizer of ||=1| subject to ||]||
π N 11N- N. This means that 9 must regular to achieve the lower bound asymptotically.
Under Assumption the graph generated by CSBM is almost surely connected. Here, remain to show that with high probability, the graph will also be non-bipartite.
Proposition 8. With probability at least 1- ((1(((())))))))))) a graph generated CSBM(N, p. 9. Pr, P2, 2²) contains triangle, which implies that it is non-bipartite.
(3)
Proof. The proof goes by the classic probabilistic method. Let Ta
Σ 1,, denotes the number
of triangles in G, where 1,, equals if potential triangle exists and 0 otherwise. Then by second moment method,
P 0] < Var(Ta)
Eijs E T. 11,, (E[Ta))²
(B
= E(Ta])
(E[TA])2
Since E.Ta] O(Np) Enj B 1,,1 (1 O(I/N))(([TA) get that
P 0] < |
+ 1110OONN/O//(((
Hence P is non-bipartite)
> PPZ > 2 O(1((N))))
K.3 SYMMETRIC GRAPH CONVOLUTION A122
Proposition 9. When using symmetric message-passing convolution A instead, the variance (ni12 is non-increusing with respect to the number of convolutional layers n. i.e.
(n+11)) < (o(")) (N)
Proof. We want to calculate the diagonal entries of the covariance matrix (n) of 1/2 10-1/2ADD AD AD-AADD-/ 10pp11//xX X, where the covariance matrix of X is o² IN. Hence
(()) = (D-11AA0-111
Since -1112/D-1/2 is symmetric, let its eigendeccomposition be VAVT and we could rewrite ((n) =VV"""")VV''"=>>>>>>>>>>>> VA
23

---

Published as a conference paper at ICLR 2023
Notice that the closed form of the diagonal entries is
diag
((m) Σ 1of2
Since for all <i [ 1, we obtain monotonicity of each entry of diag(I(m)) i.e. variance of each node.
Although the proposition does not always hold for random walk message-passinng convolution D-'A as one can construct specific counterexamples (Appendix K.4 in practice, variances are ob- served to be decreasing with respect with the number of layers. Moreover, we empirically observe that variance goes down more than the variance using symmetric message-passing convolutions. Figure [0] presents visualization of node representations comparing the change of variance with respect to the number of layers using random walk convolution and symmetric message-passing convolution. The data generated from CSBM(N 2000, p 0.0114, 0.0038, μl 1, 11 1.5, 0² 1).
random walk convolution D
symmetric convolution 0-2ADD-25
number of layers
number layers
class 1
class
class 2
class 2
-1
Figure 10: The change of variance with respect to the number of layers using random walk convo- lution D 'A and symmetric message-passingg convolution D-1/2ADD -
K.4 COUNTEREXAMPLES
Here, we construct a specific example where the variance (x))) 2 is not non-increasing with respect to the number of layers (Figure ITA). We remark that such non-monotone nature of change in variance is not caused by the bipartiteness of the graph, as cycle graph with even number of nodes also bipartite, but does exhibit such phenomenon (Figure II We conjecture the increase in variance is rather caused by the pree-like structure.
B
1.-
1.2
03-
6.9
0.5-
0.7-
variance
0.5-
0.5
94-
0.1
6.3
02
10
35
20
20
number of layers
number layers
Figure 11: Counterexamples.
K.S THE MIXING AND DENOISING EFFECTS IN PRACTICE
In this section, we measure the mixing and denoising effects of graph convolutions identified by our theoretical results in practice, and show that the same tradeoff between the two counteracting effects exists for real-wor woaldworld graphs. For the mixing effect, measure the pairwise L2 distances between the means of different classes, and for the denoising effect, we measure the cithin-class variances, both respect to the number of layers. Figure 12 gives visualization of both metrics for
24

---

Published as a conference paper at ICLR 2023
all classes Cora, CiteSeer and PubMed. We observe that similar to the synthetic CSBM data, adding graph convolutions increases both the mixing effect (homogenizing node representations in different classes, measured by the inter-class distances) and the denoising effect (homogenizing node representations the same class, measured by the within-class distances). addition, the beneficial denoising effect clearly reaches saturation just after small number of layers, predicted by our theory.
Cora
CiteSeer
PubMed
pairaise disterce belwwenn menes
0.1-
0.12
0.8
0.
6.7
number of layers
number of layers
number layers
Cora
CiteSeer
PubMed
3219
1123
1153+
109
number layers
number of layers
number of layers
Figure 12: The existence of the mixing (top row) and denoising effects (bottom row) of graph con- volutions in practice. Adding graph convolutions increases both effects and the beneficial denoising effect clearly reaches saturation just after a small number of layers, as predicted by our theory in Section 3
25


Reviews:
[{"review_id": "lQSWlQIZCz", "reviewer": "Reviewer_KQXD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper characterizes the mechanism of oversmoothing by a non-asymptotic analysis. It distinguishes undesirable mixing effect and the desirable denoising effect on graph convolutions and gives an estimation of when the mixing effect dominates the denoising effect, by quantifying both the effects on random graphs sampled from Contextual Stochastic Block Model (CSBM). On the basis of this analysis, it explains the oversmoothing phenomenon at a relatively shallow depth. To show that the framework can be applied to other message-passing schemes, specifically, the authors analyze the performance of Personalized Propagation of Neural Predictions (PPNP) and Approximate PPNP (APPNP). Their results suggest that PPR-based architectures mitigate oversmoothing at deep layers. Additionally, some numerical experiments support the theoretical results and indicate that the difficulty of optimizing parameters exacerbates oversmoothing.", "summary_of_the_review": "This paper provides a novel perspective to understand oversmoothing and a non-asymptotic framework to analyze it. It gives a series of theoretical results in both the main body and the appendix with detailed proofs. Their experiments support their main results and imply the detriment of the difficulty of optimizing deep GNN models. ", "strength_and_weaknesses": "\n1. This work provides a non-asymptotic analysis formulation of oversmoothing, closing the gap between finite-depth GNNs and the previous asymptotic analyses. The authors provide an explanation theoretically for why the optimal number of GNN layers for node classification is relatively small and gives a sweet spot for the required number of layers.\n2. The distinguishment of the mixing effect and denoising effect is helpful to understand counteracting effects in neural message passing. \n3. Experimentally, they observe that the difficulty of optimizing weight in deep GNNs aggravates oversmoothing. It makes sense and might be inspiring in further message passing designs.\n4. It seems that all the analysis relies on the assumption that the graph is generated as $\\mathcal(A,X)\\sim\\mathrm{CSBM}(N, p, q, \\mu_1, \\mu_2, \\sigma^2.)$ The authors point that their analysis cannot capture graph characteristics like degree heterogeneity. But except it, whether the analysis formulation can be applied to general feature distributions? \n\n**Questions**\n\n1. Could you please state more about the advantages of non-asymptotic analysis? To my knowledge, oversmoothing is associated with the Dirichlet energy decay rate in the previous works. In this work, the domination of the mixing effect is considered as the reason of it. Is there any connection between the two demonstrations (decay rate and domination)?\n2. The `sweet spot’ given in the paper is indeed a lovely choice for avoiding oversmoothing. I am curious about whether it is a sweet spot for the whole learning process. For example, is it possible that the sweet spot can be too short for some long-range problems?\n3. Could you give a notation instruction for $\\omega(logN/N)$ in Page 3 and $\\Omega(logN/N)$ in Page 4? And could you explain more about Figure 2? There are few illustrations, especially on graphs B and C.\n4. In the abstract, it says ‘PPR-based architectures still achieve their best performance at a shallow depth and are outperformed by the graph convolution approach on certain graphs.’ And Section 4, says ‘This drawback would be especially notable at a shallow depth, where the denoising effect is supposed to dominate the mixing effect. PPNP/APPNP would perform worse than the baseline GNN on these graphs in terms of the optimal classification performance.’ How does PPNP perform at a shallow depth after all?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "L9eU3dOsV4", "reviewer": "Reviewer_K5CA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper provides a theoretical analysis of oversmoothing in linear GCNs in an SBM setting where the features and labels are assumed to be Gaussian. It provides bounds for shallow GNNs rather than convergence rates in the infinite-layer limit. The theoretical results are supported with empirical data showing the effect of oversmoothing for synthetic and real-world datasets as the number of layers increases.", "summary_of_the_review": "The paper answers questions about the extent of oversmoothing in GNNs, and for a specific model exhibiting community structure, shows that oversmoothing occurs after a relatively small number of layers which can be explicitly predicted. While several simplifying assumptions are made, enough structure is imposed on the synthetic graphs for the results to be meaningful.", "strength_and_weaknesses": "General comments\n-\n\n- In the experiments section, your test accuracies for Cora, Citeseer, and Pubmed with weights appear much lower than in other papers. Is there a reason for this based on your experimental setup?\n\nStrengths\n-\n\n- The paper improves upon theoretical results on oversmoothing from past work, which proved crude bounds using Laplacian eigenvalues. In contrast, this paper finds bounds for shallow networks which are a more realistic regime for node classification.\n- Contextual SBMs are a good choice of framework for the theory that capture causes of oversmoothing in real-world graphs.\n\nWeaknesses:\n-\n\n- The node feature vectors are assumed to be 1-dimensional; is this strictly necessary to prove the results of the paper?\n- The Bayes optimal classifier is a simplification (as noted by the authors) and may not be applicable to the training of GNNs.\n- Performance does not seem to degrade much for Cora, Citeseer, and Pubmed in the case without weights even for very deep networks. This is in sharp contrast to the CSBM data, indicating that there are different factors contributing to the synthetic data.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "6xgTdC9m9R", "reviewer": "Reviewer_2Zpy", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "In this work, the authors focus on the over smoothing issue prevalent in GNN and demonstrate the presence of two underlying mechanisms which dictate when and how over smoothing issue crops up i.e., an undesirable mixing effect and a desirable de-noising effect. The authors demonstrate the efficacy of their approach via empirical results.", "summary_of_the_review": "The authors focus on an important problem for the GNN research community and try to decipher it via breaking it down to two counteracting effects of applying graph convolutions. However the analysis is very focussed on a specific set-up and is not generic in nature. Additionally it makes strong assumptions and due to this and prior issues, the usefulness of the current work is pretty limited. ", "strength_and_weaknesses": "Here below are some strengths of the current work :\n\n1) The authors focus on an important problem in the GNN research community and make an effort to decipher it in this current work. Specifically the authors try to explain why over smoothing happen at a relatively shallow depth which is very important to understand.\n\n2) The authors demonstrate the presence of counteracting effects of applying graph convolutions i.e., a mixing effect which homogenizes node representations and a de-noising effect which homogenizes node representations belonging to the same class. The authors also provide an estimate as to when one effect dominates the other.\n\nHere below are some weakness of the current work :\n\n1) The current work focusses on a simplified setup of two classes and uses Contextual Stochastic Block Model as the generative model which does not provide an accurate representation of real-world graphs. \n\n2) The authors do not demonstrate how to measure over-smoothing as well as the two effects in practice. Without being able to 1) adequately measure and quantify the two effects and 2) demonstrate the authors can adequately explain over-smoothing in a general setting, the presented approach seems hypothetical. \n\n3) The authors do not demonstrate the practicality of the current approach to the research community. Theoretical analysis is great however without being able to provide utility, the scope of the work is significantly reduced. \n\n4) As the authors themselves point out, the current work's analysis is based on oracle classifier, however in practice, we work in a semi-supervised setting. Thus the utility associated with the current work is pretty limited.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster