Analysis of Corrected Graph Convolutions
Authors: Robert Wang
Aseem Baranwal
Kimon Fountoulakis
Venue: NeurIPS 2024 poster (2024)
Keywords: Node classification
partial classification
exact classification
contextual stochastic block model
graph convolution
spectral analysis
Primary area: learning_theory
TL;DR: Analysis of the corrected graph convolution on the contextual stochastic block model for arbitrary number of convolutions.

Abstract: Machine learning for node classification on graphs is a prominent area driven by applications such as recommendation systems. State-of-the-art models often use multiple graph convolutions on the data, as empirical evidence suggests they can enhance performance. However, it has been shown empirically and theoretically, that too many graph convolutions can degrade performance significantly, a phenomenon known as oversmoothing. In this paper, we provide a rigorous theoretical analysis, based on the two-class contextual stochastic block model (CSBM), of the performance of vanilla graph convolution from which we remove the principal eigenvector to avoid oversmoothing. We perform a spectral analysis for $k$ rounds of corrected graph convolutions, and we provide results for partial and exact classification. For partial classification, we show that each round of convolution can reduce the misclassification error exponentially up to a saturation level, after which performance does not worsen. We also extend this analysis to the multi-class setting with features distributed according to a Gaussian mixture model. For exact classification, we show that the separability threshold can be improved exponentially up to $O({\log{n}}/{\log\log{n}})$ corrected convolutions.

Analysis of Corrected Graph Convolutions
Robert Wang"
Aseem Baranwal
Kimon Fontoulakis'
Abstract
Machine learning for node classification on graphs prominent area driven by applications such as recommendation systems. State-of-the-art models often use multiple graph convolutions on the data, as empirical evidence suggests they can enhance performance. However, it has been shown empirically and theoret- ically, that too many graph convolutions can degrade performance significantly, a phenomenon known as oversmoothing. In this paper, we provide a rigorous theoretical analysis, based on the two-class contextual stochastic block model (CSBM), of the performance of vanilla graph convolution from which we remove the principal eigenvector to avoid oversmoothing. We perform a spectral analysis for & rounds of corrected graph convolutions, and we provide results for partial and exact classification. For partial classification, we show that each round convolution can reduce the misclassification error exponentially up to saturation level, after which performance does not worsen. We also extend this analysis to the multi-class setting with features distributed according Gaussian mixture model. For exact classification, we show that the separability threshold can be improved exponentially up Ollog n /log log n) corrected convolutions.
Introduction
Graphs naturally represent complex relational information found in plethora of applications such
social analysis [Backstrom and Leskovec, 2011]. recommendation systems (Ying al.
2018
Borisyuk et al. [202]] computer vision [Monti et al. 2017]. materials science and chemistry Reiser
al. 2022
statistical physics [Battaglia al. 2016 Bapst et al. 2020), financial forensics Zhang
et al.
2017
Weber et al. 2019 and traffic prediction in Google Maps DerrowwPPinii et al. 2021
The abundance of relational information in combination with features of the corresponding entities has led to improved performance of machine learning models for classification and regression tasks. Central to the field of machine learning graphs is the graph convolution operation. It has been shown empirically [Defferrard et al., 2016 Kipf and Welling 2017 Gasteiger et al.) 2019 Rossi al. 2020 that using graph convolutions the feature data enhances the prediction performance of a model, but too many graph convolutions can have the opposite effect [Oono and Suzuki 2020 Chen
al. 2020 Keriven 2022 Wu al. 2023) issue known oversmoothing. Several solutions have been proposed for this problem. we refer the reader to the survey of Rusch et al. [2023].
In this paper provide rigorous spectral analysis, based the contextual stochastic block model [Deshpande et al. 2018], to show that the oversmoothing phenomenon can alleviated by excluding the principal eigenvector's component from the graph convolution matrix. This is similar to the state-of-the-art normalization approach used in Zhao and Akoglu 22000), Rusch et al. (2023) (PairNorm). However, method explicitly uses the principal eigenvector. We provide below some intuition about why excluding the principal eigenvector helps to alleviate over-smoothing.
Cheriton School Computer Science, University Waterloo Cheriton School of Computer Science, University of Waterloo 'Cheriton School Computer Science, University of Waterloo
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Let A be the adjacency matrix of the given graph, and D be the degree matrix. Vanilla graph convolutions are represented using matrices such as A or D-1/2 2017]. Suppose our graph is d-regular, meaning that each node has exactly d neighbors. In this case, both graph convolutions reduce to J.A. The top eigenvector of A is 1 with eigenvalue d, where I is the vector of all ones. This means that lima->x z A 11T, which implies that applying many convolutions is equivalent to projecting our data onto the all-ones vector. Thus, all feature values will converge to the same point. Therefore, should expect, verified by most real-world and synthetic experiments, that many rounds of the convolution 2 + Arr will lead to a large learning error. However, if we instead perform convolution with the corrected matrix Ā == A 111,
[Kipf and Welling
then the convergent behavior of x + A would be equivalent to projecting onto the second eigenvector of A. This eigenvector is known to capture information about sparse bipartitions in the graph G [Cheeger 1970, Alon and Milman 1985 Alon 1986]. and so for certain problems, like binary classification, we may expect this eigenvector to capture a larger amount of information about our signal. We note that another well-studied graph matrix is the Laplacian, D-A. In the regular case, this has the same eigenvectors as the adjacency matrix, but with reversed spectrum. The trivial eigenvector we remove is exactly the Nullspace of the Laplacian.
In our analysis, we study the classification problem in the contextual stochastic block model, with focus on linear, binary classification. Our results are stated in terms of the following corrected convolution matrices:
(I) where d := 2/E is the empirical average degree in A, where |E| is the number of edges in the graph. Note that Á is derived from the normalized adjacency matrix, while A is (up to a scalar multiple) its unnormalized counterpart. Briefly, we demonstrate that when the graph of reasonable quality, the corrected graph convolutions exponentially improve both partial and exact classification guarantees. Depending on the density and quality of the given graph, improvement becomes saturated after O (log n) convolutions in our partial and exact classification results. However, in comparison to similar analysis in [Wu et al.) 2203)) for vanilla graph convolutions (without correction). we show that classification accuracy does not become worse as the number of convolutions increases.
Å = D-1 1/2-1111/2 1/2
and À
11 71
1.1 Our Contributions
In this work, provide, to our knowledge, the first theoretical guarantees partial and exact classification after rounds of graph convolutions in the contextual stochastic block model. Our main result is show that each graph convolution with the corrected matrix reduces the classification error by multiplicative factor until a certain point of "saturation" and the number of convolutions required until saturation depends on the amount of input feature variance. We show that the accuracy of the linear classifier at the point of saturation only depends on the strength of the signal from the graph. This is in contrast to the uncorrected convolution matrix, which will always exhibit a decrease in classification accuracy after many convolutions. Finally, we show that given slightly stronger assumptions on graph density and signal strength, the convolved data at the point of saturation will be linearly separable with high probability. To quantify our results, we let p and be the intra- and inter-class edge probabilities with 7p, q) lp gl + q) being the "relative signal strength" in the graph. Let d be the expected degree of each vertex. Our results can be summarized as follows:
* If + 2 2 log" n
and 7 2 R (2))) ), each convolution with À reduces classification error by a factor of about I until the fraction of errors is 0 7
7Fa
p 22 loo
and y 2 22 V log each convolution with Á reduces classification
error by factor of about log ydd
until the fraction of errors is O logn 7d
Iff + q 22 log" (00m""), 2 2(k " and the input features has signal-to-noise ratio n
least 2( log"). ). the data is linearly separable after rounds of convolutions with A.
To obtain our partial classification results, we use spectral analysis to bound the mean-squared-erroo between the convolved features and the true signal. For exact classification, prove concentration

---

inequality on the total amount of message received by vertex through "incorrect paths" of length k after & rounds of convolution through combinatorial moment analysis. Using this, we establish entry-wise bounds on the deviation of the convolved feature vector from the true signal.
Finally, we extend our partial-recovery result to the multi-class setting. In this setting, we assume our features are distributed according to a Gaussian mixture model with L equal-sized clusters and our graph distributed according to a L-block stochastic block model. Our analysis for partial recovery generalizes easily to the multi-class setting with the use of basic non-linear classifiers. Just as before, we show that convolution with the corrected, un-normalized adjacency matrix, A, reduces classification error by a constant fraction each round, until point of saturation where no further improvement is made.
2 Literature review
Research on graph learning has increasingly focused on methods that integrate node features with relational information, particularly within the semi-supervised node classification framework, see, for example, /Scarselii et al. [2009]. Cheng et al. (2011). Gilbert et al. [2012). Dang and Viennet
20122, Günnemann et al. [2013] Yang al. [2013] Hamilton al. [011 Jin al. [2019]. Mehta
et al. 2019]. Chien et al. 20022] Yan et al. [002 These studies have underscored the empirical
advantages of incorporating graph structures when available.
The literature also addresses the expressive capacity [u et al. 2017 Balcilar ct al.
2021 and gener-
alization potential [Maskey et al.] 2022] of Graph Neural Networks (GNNs). including challenges
like oversmoothing [Kerivnn] [0022] Xu et al. 2021 Oono and Suzuki 2020 Li et al. 2018 Rusch
ett al.
2023 In our paper, ground our work the contextual stochastic block model [Desh-
pande et al. 2018), a widely used statistical framework for analyzing graph learning and inference
problems. Recent theoretical studies have extensively used the CSBM to illustrate several statistical, informatioontheeretiic. and combinatorial results on relational data accompanied by node features. In Deshpande et al. [2018]. Lu and Sen 2020). the authors investigate the classification thresholds for accurately blassifying sigmificant portion of nodes from this model, given linear sample complexity and large but bounded degree. Additionally, Hou al. (2020) introduces graph smoothness metrics to quantify the utility of graphical information. Further developments in Chien et al. [202] 2022).
Baranwal et al. [22TT] 2023a extend the application of CSBM, establishing exact classifiction thresholds for graph convolutions in multi-layer networks, accompanied by generalization guarantees. theoretical exploration of the graph attention mechanism (GAT) is provided by |Fountoulakis et al.] [2023] delineating conditions under which attention can improve node classification tasks. More recently, Baranwal et al. [2023b] provide the locally Bayes optimal message-passingg architecture for node classification for the general CSBM.
In this paper, we provide exact and partial classification guarantees for multiple graph convolution operations. Previous investigations have often been confined to a few convolution layers, limiting the understanding of their effects on variance reduction (see, for example, Baranwal et al. (2023a]). Our findings contribute a novel spectral perspective on graph convolutions, describing how the ratio in the node features and the
fraction of recoverable nodes is influenced by the signal-to-noie scaled difference between intra- and inter-class edge probabilities. We also demonstrate that the oversmoothing phenomenon can be alleviated by excluding the principal eigenvector's component from the adjacency matrix a strategy somewhat akin to the normalization approach used in /Zhoo and Akoglu [2020] (PairNorm), albeit our method explicitly uses the principal eigenvector and is grounded in rigorous spectral justifications.
In a relatively recent work (Wu et al. 2023] the authors rigorously analyze the phenomenon of oversmoothing in GNNs for the 2-block CSBM by identifying two competing effects of graph convolutions: the mixing effect, which homogenizes node representations across different classes, and the denoising effect, which homogenizes node representations within the same class. Their analysis shows that oversmoothing occurs when the mixing effect dominates the denoising effect, and they quantify the number of layers required for this transition. In contrast, we work with the corrected graph convolution in the 2-block CSBM and show that improves performance exponentially up to saturation, after which more convolutions do not improve nor degrade performance. On technical level, the previous work only analyzes the distribution of single node's 's feature values after convolution and does not take into account correlations between nodes. In our work, we use spectral
3

---

analysis of higher powers of the convolution matrix, which takes into account correlations between nodes obtain our partial classification results over the whole dataset. To handle the modified convolution in the exact classification setting, we analyze the error more directly through matrix perturbation analysis rather than trying to directly count the higher-order neighbors of each vertex as in previous works (Baranwal et al. 2023a
Wu et al. 2023
3 Preliminaries and Model Description
Throughout this paper, we use 1 to denote the all-ones vector and e, to denote the 8th standard basis vector in R". Given a vector x E R", we use ||æ]|| to denote its Euclidean norm Ex=
use ||æ loc to denote its infinity norm, max; [z) For matrix M E R", use M =1 x01)². We denote its
operator norm, maxx ||Mz||| We use || - MD, to denote its Frobenius norm.
We also make routine use of the spectral theorem, which says that if M is X symmetric matrix, then it can be diagonalized with n orthogonal eigenvectors and real eigenvalues. In particular, there exist d₁ ... E R and orthonormal vectors W1, WC, E R" such that M - >> n= X.w.w! Note that when M is symmetrie, |M] max; | = max ||]||| Mx].
Finally, we use the Mi,, Σ) to a Gaussian distribution with mean μ and covariance matrix E. For nne-dimensional Gaussians, use (u,, o²). For X ~ N(,, 02), we will frequently use the
Gaussian tail bound: Pr [[X - e > to] S e
3.1 Contextual Stochastic Block Model
In this section, we formally describe the contextual stochastic block model introduced by (eehpaadee al., 2018). Our model is defined by parameters n, m N. P. q E [0, 1], μ., 2/, R and E In the model, we are given random undirected graph, G (V, F)), where [V| n. drawn from the 2-block stochastic block model and features drawn from the Gaussian mixture model. Our vertices are partitioned into two classes, S and T, of size n/2, which we want to recover. For each pair of vertices j.j E S and i.j T, the edge (i. is in E independently with probability p while for each pair i E S and E T. the edge (i,j) is in E with probability q. In addition to the graph, we also given a feature matrix X Ruxm drawn from a Gaussian mixture model with two centers μ and v. For each i E V, we let 9i NN0, 0² Im) be an i.i.d. Gaussian noise vector. Now let (æi)ien be the rows of X. For E S, we have F; = μ + 9: and for each i E T, we have I; = 1/ + gt-
In the multi-class setting, our nodes are partitioned into L classes, CI...CL, of size n/L. The inter-class edge probability is p and intra-class edge probability q. We assume the features are generated by Gaussian mixture with I, centers cI,..CL RRm If node i is in class 1, then we observe its feature vector as Øy aa + 9:- In addition, we will let b4 = Ct for Ct, denote the center for vertex i.
4 Results and Interpretation
In our analysis, there are two types of objectives. the exact classification objective, the aim is to exactly recover S and I with probability 1 1-1( In the partial classification, "detection" problem, the goal to correctly classify begin by stating results for the partial classification regime. For ease of notation, will assume p > 9 from this point forward. We show in Appendix B. that this assumption is made without loss of generality.
o(1) fraction of vertices correctly with probability 1 - o(1). We
Theorem 4.1. Suppose we are given 2-block m-dimensional CSBM with parameters n.P > 4. [4, v, a satisfying 7(p, = a-a 2 2 (V(1)) np) and p 2 Ω log² There exists a lin- ear classifier such that after k rounds of convolution with A, will. with probability least 1 - exp( exp(-92(nlu-u11? (llu=ule)) ) misclassify at most
0 1 +
C
2k 0²
|| - v1 2 log
22p
(/pp

---

vertices, where C is an absolute constant. Furthermore, if 2 D [ogg) then with probability at
least 1 - exp( (
( the same linear classifier after rounds of convolution with Å will
a²
misclassify most
log n 72p Vrpp +
C log n2
0² ||I w1 log
0
vertices.
Now we take closer look at the error bound. For brevity, we will focus on our results regarding convolutions with Å. First, we see that an important ratio in our bound is the term 1/(7?np). This term is small if 72 is much larger than the inverse of the expected degree of each vertex, (p + q)n/2, which is at most np. Our assumption that this ratio is upper bounded by constant means that we need the signal from the graph be sufficiently strong, Now, if we examine our misclassification error bound, and let p= p C/(r"np)())))) where C' is sufficiently large constant, then we see that the fraction of misclassified vertices is at most p+ p²² log n/ || w1 Our assumption on the parameters ensures that p 1. Note that only the second term depends on k, and the feature's s noise-to-signal ratio. This term measures the amount of error introduced by the variance in the features and exponentially
decreases with k. Moreover, after about k = logi/p (o2 log n/(p || - convolutions, the
term, which only depends on graph parameters, will dominate over the variance term, indicating that more convolutions will not improve the quality of the convolved features beyond the quality of the signal from the graph. a || - wIIl constant, we will always reach our optimal error bound of O(p) when k = Ollg log n). Moreover, if y 22(1, was assumed in |Baranaal et al. [2021] J, then we will have 1/p 2 ((np). This means even when o/ ||| - w/ 2 /n/ log optimality in constant number of convolutions with high probability the graph is moderately dense. For example, if p 1/vn.. then only need 3 convolutions and if p [((1), then only need On the other hand, if y is on the order ((1 /rp), then in the worst case, we may need log n convolutions to reach our optimal bound. Next, we state results for exact classification.
will reach
Theorem 4.2. Suppose we are given 2-block m-dimensional CSBM with parameters p. > M4 V, satisfying 7(p q) 2 Ω
and p 2 log"n Then after k = Olog n) rounds of graph convolution with A, our data is linearly separable with probability 1 - n -2(1 if
log n up
|l wll
logn
k
2 Ω
max
v
log
where C' an absolute constant.
Here, we bound the minimum signal-to-noise ratio required for exact classification as a function of p. g, n and k. Just like the partial classification result, our function has a term that decreases exponentially with & and a term independent of k. The rate of decrease for the dependent term is proportional 1/(r-/rip) or vp. We see once again that with more convolutions, the requirement on the feature signal-to-nol
ratio for exact classification becomes exponentially weaker. More- over, since we assumed that 7 2 S2(k //ll////oog/// n (mp)). as long as || wll 2 M( /logn/n) the data becomes linearly separable after = O(log n n//lo log n) convolutions. Just as in the partial classification case, we observe that the larger is, the fewer convolutions we need to obtain the optimal bound. In particular, if 7 2(1) and p = (2(1) then one convolution already gives the optimal bound, and if p 1/,n, then two convolutions are enough. For technical reasons, we only analyze exact classification using convolution with the corrected un un-normalized adjacency matrix, Á. Similar bounds should hold for Á based our simulation results, but we leave this for future work.
4.1 Discussion on our Assumptions
Both Theorem 4.1 and Theorem 4.2 require a lower bound of 2 /np), and this to ensure that the signal Trom the graph is strong enough so that convolution does not destroy the signal from the data. Also, implicit in the probability bound of Theorem 4. and Theorem 4.2 is the assumption that our signal-to-noise ratio, || w|l /o, is at least w(1/ so the feature noise does
5

---

not completely drown out the signal. Our bound assumption on is to ensure concentration in the behavior of the degrees and the adjacency matrix towards their expectation. In Theorem 4.2
we also assume that k = (log r.). This is done mainly for technical reasons of our proof but we note that this assumption is made without loss of generality because as mentioned, the bound in Theorem 4.2 does not improve for & 2 log n. Finally, we note that the case >> corresponds to homophilous graph, and the case p < q corresponds to heterophilous graph (see Luan et al. [2021], Ma et al. [022) for more). For binary classification, it has been shown [Baranwal et al. 2023a that one can assume p > without loss of generality and make corresponding adjustments the classifier. As such, we assume that p q. For more detail regarding this assumption, Appendix B.1
5 One-Dimensional CSBM
In Baranwal et al. [2021] the authors showed that analyzing the linear classifier for the m- m--imennional
CSBM reduces analyzing the 1-dimensional model. We say that CSBM is one-dimensional and centered with parameters n., p, if it has one-dimensional features and means 1/ and -1/vn. That is, have one feature vector x E R given by x + g. where y (0, o² I,)) and s(i) 1//n for i E S and -1/vn for E T. We will refer to as our signal vector and for case of notation, we normalize so that always has unit norm. The following lemma allows us to reduce the analysis of the linear classifier for a general CSBM to the analysis of the I-dimensional centered CSBM (proof in Appendix [B.). Thus, in the proofs of our main theorems, we will analyze the I-dimensional case before applying Lemma 5.1
Lemma 5.1. Given an m-dimensional 2-block CSBM, there exist w E 1 and b E R such that Xw + b + 9 where for each vertex i, 9: is i...d. (0, o²2) with o' "
4o
In the 1-dimensional model, it is clear how our signal s is present our features. Our convolution matrix also captures the signal because it can be viewed as perturbation of the matrix 8s T. This is especially evident with the un-normalized convolution matrix Å, which satisfies the following
1 J R d'11
À = nss"
(2)
where 7 : (p - ()dd is the signal strength, d' == g)m22 ////2-d/(nndll (nd) is the average degree deviation, and R is the "odge-deviation" matrix. where Rı,j A..; [[A.,]] Since R has i.i.d. zero-mean entries with variance at most p. we can use standard matrix concentration inequalities to show it is not too big. Likewise, d' is small due to degree concentration, and together, these two concentration results imply that Á is close to yss In fact, if we show degree concentration for all vertices, then we can show that Å also behaves like Á. We state these concentration results below. p-q Proposition 5.2. Assume that p = 2 1o(l "), and let ? = pt4" have the following concentration results
With probability 1 - n -Q(1) we
1. d'| O(1/n25), which implies that 1) E 7(1 o
2. |R| I ((vnp)
3. Ā yas" T
and | 7Ss <0(v
log np
These concentration properties are crucial for spectral analysis. Details are given in Appendix B.
Partial Classification
In this section, give sketch of the proof of our partial classification result, Theorem The full proofs can be found in Appendix C convolved vector is well-correlated with our signal vector s as defined in the beginning of Section 5 in the centered-1 dimensional CSBM. We will analyze our result for convolutions using the matrix M E (Ā, Å).
We will show that partial classification can be achieved if the
Proposition 6.1. Given a centered I-dimensional 2 block CSBM with parameters n. > q, a and (p. g) p-g, suppose our convolution matrix M satisfies || -ys! T < å and y C6 for p+g'

---

large enough constant C. Let x be the result of applying k rounds of graph convolution to our input feature x. Then with probability least exp( Toz -opp-)az)) there exists a scalar C₁: and an absolute constant C' such that
- s = (
8 (C'6) 2k )
(5))))))
no² logn
The main idea of our analysis is to use the fact that the top eigenvector of M, denoted 8, is well correlated with our signal s. Since || - yss -
I á and > Cd by assumption, standard Matrix perturbation arguments imply that the spectrum of M will be in (7 + 5, =ō, =ō, with high probability. Given our assumption of y > Co, there will be large gap between the top eigenvalue of M and the rest of its eigenvalues. A well-known result Davis and Kahan implies that prove Proposition 6.1 by showing that the
||s a|| s O ((6) i.c. is close to 3. Thus, influence of the rest of the eigenvectors on our convolved vector, 25 = M2 decreases exponentially with k, which allows us to bound the squared norm distance between 2a and s. In particular, we take our normalization constant to be Cs RJ 1/2f. where λ is the maximum eigenvalue of M. Note that (1/x- (1/A() = $87 Roughly speaking, we decompose our convolution vector as CL R (1/2f) M + (1/Af) \/ To bound the distance of this vector from 8, we analyze the contribution of each of the two terms our error separately. That is, show that with high probability [I(1/A))M/ - s I 0(8²/7) and || gl| S (((8/))22 22=nn² logn). Note that the first error term is from taking the convolution of the noisy graph with the true signal, and thus does not decrease with k. The second error term, on the other hand, comes from variance in the features, and thus decreases with our noise level and drops exponentially with each convolution.
Finally, given Proposition 6. we can prove the partial classification result by noting that we partition the convolved I-dimensional data around 0, then each misclassified vertex contributes 1/n to the mean-squared error, which means the number of misclassified vertices is most ||Ck-7t s| This, combined with Lemma 5.1 to generalize to the m- dimensionnl case will prove Theorem 4.1
7 Exact Classification
In this section, we sketch the proof of Theorem for exact classification using the un-normalized corrected convolution matrix Á. Full proofs can be found in Appendix D To show linear separability, would like myg- 4 have positive entries for all vertices in S and negative entries for all vertices in T. This means that we want to show || - allao < /i for some appropriate scalar CR. In particular, we will take C2 to be 1/n², where 1) is our empirical estimate of (p, q). In partial classification, it sufficed to bound the mean squared error ||Cræ =11 using spectral analysis but bounding || |Caar - *||>0 requires more work because now we are bounding the entrywise instead of average error. In our approach, we bound the volume of messages passed through "incorrect paths" in our graph and show that the contribution from these messages is small. Then, we show the other source of error, the feature variance, is reduced exponentially with each round of convolution. As with the partial classification result, we first prove our result in the I-dimensional centered model: Proposition 7.1. Suppose we are given a I-dimensional centered 2-block CSBM with parameters n. p. g, a and l O(logn) n) such that 7 p-q p+g
2 1
log n ap
log² n and S O n
(Vogg
Then with probability at least n -S(1);
1 x
+0
(
C
&
A
S 2
V
(ypp
We now give a sketch of our proof for Proposition 7. To bound each entry of CL - s, we must bound leT A0 - e s for all u E V. Similar to in partial classification, we will split our error into error from A and error from Åtg. That is, for each u E V, we separately upper bound le,T (mss T + +*' - e s| and le__ (nss *R) where R' = À - mss"" The matrix (nss7 + & when expanded out, can be written as 17*ss" plus sum of 2* 1 terms, each of which a non- commutative product of matrices of the form n1ss" R'. We group these error matrices into terms
Given, Proposition 7.1 Theorem 4.2 follows immediately by applying Lemma 5.1
7

---

of order é for E [k], where the eth order terms are comprised of products that contain & copies of R and k: - l copies of ryss".
In our analysis, R. it suffices to analyze the error w.r.t R. To bound e, (7s5 T + /t))*s, we expand it out and find that each term arising from an error matrix of order & can be written e, s s.......s & where a1....0 are non-negative integers satisfying d1 + +az = &. The symmetric terms can be bounded by showing T R 8 S (Vup)* using simple spectral arguments. To control the asymmetric term, we show that with high probability, le, I S रा (Cnp log n)a1/2 for constant C. This part is the most technical part and requires the slightly stronger graph density assumption: p 2 12 n/n). Thus, we have |e, & R ...s............................ R I (C log n) n)//
first use degree concentration to show that instead of analyzing the error w.r.t.
multiple of
for some constant C. The analysis for bounding Ca A* is similar. Finally, by combining these bounds with our assumptions that is large enough, we obtain Proposition 77.
Now, we take a closer look at the step of bounding the asymmetric term. Recall that R is a random symmetric matrix with i.i.d. zero mean entries. The term e, Rt can be expressed as En (o) (ooo)) ( (t--) w))) ((())((((a)) where the sum is over all walks, of length in the complete graph over n vertices starting at w()) == u. From a message-passing perspective, one interpret this bounding the deviation between the amount of signal message receives over paths of a certain length and the amount of message it expects to receive. To bound this term, we use path counting argument control its higher moments, and then apply Markov's inequality: Pr le_ s Al < Biee {(]
8 Multi-class Analysis on Gaussian Mixture Model
In this section, we will formally state and sketch our results for the multi-class analysis. Full proofs are in Appendix E. For simplicity, we will only analyze convolution with the un- an-normalized corrected convolution matrix. A. The reason that the corrected convolution still gives good performance is that when class sizes are balanced, the second eigenspace of the expected adjacency matrix has multiplicity L, - 1 and exactly captures the T. clusters (see Lemma E. Before formally stating our result, we will introduce some useful notation:
Graph Signal: = (p-q)m
the strength of the signal from the graph. dL
p)/L+ Vnq(1 g))) for some constant C. 5 is an Graph Noise: 5 == C()
upper bound on the graph noise.
Let U := [[X] be the matrix whose ht column is μ.. We also assume our features are centered on expectation so that U O. This restrictive since it can be satisfied by applying a linear shift to the features
Let A = min,,je(m] ||p
Myll be the minimum distance between the centers
Theorem 8.1. Given the CSBM with parameters, p. 9, L, n, m. suppose min(p, q) 2 2 loog" and [|] > 4k6. Let (4) A X be the feature matrix after k rounds of convolutions with scalaing factor 1/2². Let x be the 8th row of the matrix (k), Then with probability 1 --n--nn -001), at least n The nodes, i, satisfy |0 us A/2 where
ne = =
1 A
+ (I. (1++2///)))
22m log
A
In particular, the quadratic classifer x + softmax[|Ix - all \ will correctly classify at least n The points, and when n. = o(1), then we can correctly classify - o(1) fraction of points.
Intuitively, our theorem states that each convolution will cause the points in each cluster to "contract" towards their means up until a certain saturation point reached. If after this contraction, many points are closer to their own centers than to any other centers, the softmax classifier will correctly classify them. Just as in Theorem 4.1 our error bound consists of one component depending on the variance, o that is large at the beginning and decreases exponentially with each convolution. The
8

---

classification accuracy at the point of saturation (k = log n) depends on the squared product between graph's 's sggal-to-noiss ratio, 8/ and the "separation ratio" of the datasets: | /A. As in the two-class setting, our theorem captures both the homophilic and heterophilic settings. However, for large L,, our error parameter, 5, can be much larger if > p. This observation of noisier graphs in the heterophilic setting, leading to less accurate performance, is consistent with observations from previous studies [Choi et al. 2023].
Experiments
In this section, we demonstrate our results empirically. For synthetic data, we show Theorems 4.1 and for linear binary classification. For real data, we show that removing the principal component of the adjacency matrix exhibits positive effects multi-class node classification problems as well.
9.1 Synthetic Data
For synthetic data from the CSBM, we demonstrate the benefits of removing the principal component of the adjacency matrix before performing convolutions for both variants of convolution described in Equation (T). We choose n 2000 nodes with 20 features for each node, sampled from a Gaussian mixture. The intra-edge probability is fixed to O(log" n/n). . We perform linear classification to demonstrate the results in Theorem 4.1 and Theorem 4.2] training one-layer GCN network both with and without the corrected convolutions and perform an empirical comparison.
We provide plots for different settings: (1) Fix = -p /l/(p + q) 2/3 and vary signal-to- noise ratio of the node features, || /il/a, for different number of convolutions. We observe in Figure T that the number of convolutions increases, the original GCN (Kipt and Welling, 2017] (in blue) starts performing poorly, while the corrected versions (in orange and green) retain the accuracy for lower signal-to coonall----oisee ratio; (2) Fix 1| v/l/or 1 and vary the graph relative signal strength, for different number of convolutions. We observe the same trends in this setting, as depicted in Figure The vertical lines represent the threshold for exact classification from Theorem 4.2
Accuracy
Accuracy
with
(a) 1 convolution.
(b) convolutions.
(c) 4 convolutions.
Accuracy
Accuracy
EEM vol Exet meovery
DC' wit secoery wahii
SoN uit panond bail uocensty valus
(d) convolutions.
(c) 12 convolutions.
(f) 16 convolutions.
Figure I:
Accuracy plot (average over 50 trials) against the signal-to-noise ratio of the features (ratio of the distance between the means to the standard deviation) for increasing number of convolutions. Here, v = 11/2 1 and the "GCN with ve removed" refers to convolution with the corrected, normalized adjacency matrix. "GCN with 11 removed" is the corrected, unnormalized matrix.
9.2 Real Data
Similar to synthetic data, we compare the results for corrected graph convolution to the original GCN on the following real graph benchmarks datasets: CORA, CiteSeer, and Pubmed citation networks [Sen et al. 2008 in the multi-class setting. In Figure 3 we see that overall the accuracy of every learning method decreases as the number convolutions increases but the corrected convolutions converge to accuracy much higher than that of the uncorreeted convolution. This is attributed to

---

Accuracy
Accuracy
DPt witt
DM's wit proend senood
Godlutth senored
with wenooed
13
25
15
00
022
64
00
8.2
00
0.2
30
(a) 1 convolution.
(b) 2 convolutions.
(c) 4 convolutions.
Accuracy
2.4
Accuracy
Dig 603
Accuracy
Deip
0.7
Bug DTW
GCM uit 61 wnoved
GGl uit senvidd
00
06
00
0.2
(d) 8 convolutions.
(c) 12 convolutions.
(I) 16 convolutions.
Figure 2: Accuracy plot (average over 50 trials) against graph relative signal strength (7 =
/l/ (p + q)) for various values of the number of convolutions.
the fact that for multi-class classification on general graphs, the important information about class memberships is typically captured by the top C eigenvectors (except the first one) where C is greater than the number of classes [Lee et al. 2014). In general, these eigenvectors could have different eigenvalues. Since the limiting behavior of many rounds of convolutions is akin to projecting the features onto the eigenvector(s) corresponding to the second eigenvalue, we only expect this to capture partial information about the multi-class structure. By contrast, we show, in Appendix [E.] that for synthetic data with balanced classes, the classification accuracy only increases with more convolutions if they are corrected remove the top eigenvector.
Accuracy
Accuracy 2.
Number of Layers
Number Layers
Number of Layers
(a) Cora.
(b) CiteSeer.
PubMed.
Figure 3: Accuracy plots (average over 50 trials) against the number of layers for real datasets.
10 Conclusion and Future Work
In this study, we utilized spectral methods to obtain partial and exact classification results for the linear classifier with corrected convolution matrices in the 2-block CSBM. Our spectral approach highlights, theoretically, how removing the top eigenvector can mitigate oversmoothing and improve classification accuracy. We prove that the removal of the top eigenvector results in reducing feature variance and correcting the asymptotic behavior of many rounds of convolution towards the second, rather than the top eigenvector of the adjacency matrix. Finally, we showed that our analysis can be generalized to the multi-class setting. We hope our analysis can lead to further developments in theoretical and practical studies of GNNs. A natural extension of this work would be generalize our analysis to broader classes of multi-class models. For example, if the size of classes are unbalanced, the second eigenspace may capture all the information about the clusters. In addition, the distribution of features may not follow standard Gaussian mixture model, but more complicated distributions, possibly with multiple centers [Baranwal al. 2023a]. Another natural setting to consider is when clusters in the feature distribution do not exactly match clusters in the graph. Extending our analysis to these settings will likely require more sophisticated network architectures and activation functions.
10

---

Acknowledgements
K. Fountoulakis would like to acknowledge the support of the Natural Sciences and Engincering Research Council of Canada (NSERC). Cette recherche a été financée par le Conseil de recherches en sciences naturelles en génie du Canada (CRSNG), IRGPIN-2019-04067; DGBCR-2019-001477
References
Noga Alon. Eigenvalues and Expanders. Combinatorica, 6:83-96, 1986.
Noga Alon and Vitali Milman. f--ssoperimetric Inequalities for Graphs, and Superconcentrators. Journal of Combinatorial Theory, Series B, 38(1):73-88, 1985.
Lars Backstrom and Jure Leskovec. Supervised random walks: predicting and recommending links in social networks. In Proceedings of the fourth ACM international conference on Web search and data mining, pages 635-644, 2011.
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the Expressive Power of Graph Neural Networks in a Spectral Perspective. In International Conference Learning Representations, 2021.
Afonso S. Bandeira and Ramon van Handel. Sharp Nonasymptotic Bounds the Norm of Random Matrices with Independent Entries. The Annals of Probability, 44(4):2479 2506, 2016.
Victor Bapst, Thomas Keck, A Terabska-Barwinee
Craig Donner, Ekin Dogus Cubuk, Samuel S Schoenholz, Annette Obika, Alexander WR Nelson, Trevor Back, Demis Hassabis, et al. Unveiling the Predictive Power of Static Structure in Glassy Systems. Nature Physics, 16(4):448-44,, 2020.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph Convolution for Semi- Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pages 684-693, 2021.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of Graph Convolutions in Multi-layer Networks. In The Eleventh International Conference Learning Representations, 2023a.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Optimality of message-passing architectures for sparse graphs. In Advances in Neural Information Processing Systems, volume 36, pages 40320-40341 2023b.
P. Battaglia, R. Pascanu, M. Lai, J. Rezende, and K. Kavukcuoglu. Interaction Networks for Learning about Objects, Relations and Physics. Advances Neural Information Processing Systems (NeurIPS), 2016.
Fedor Borisyuk, Shihai He, Yunbo Ouyang, Morteza Ramezani, Peng Du, Xiaochen Hou, Chengming Jiang, Nitin Pasumarthy, Priya Bannur, Birjodh Tiwana, Ping Liu, Siddharth Dangi Daqi Sun, Zhoutao Pei, Xiao Shi, Sirou Zhu, Qianqi Shen, Kuang-Hsuan Lee, David Stein, Baolei Li, Haichao Wei, Amol Ghoting, and Souvik Ghosh. LiGNN: Graph Neural Networks at LinkedIn, 2024.
Jeff Cheeger. A Lower Bound for the Smallest Eigenvalue of the Laplacian. Problems in Analysis, pages 195-199, 1970.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and Relieving the Over- Swor-Smoo Problem for Graph Neural Networks from the Topological View. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04)3448-3445 Apr. 2020.
Hong Cheng, Yang Zhou, and Jeffrey Xu Yu. Clustering Large Attributed Graphs: A Balance between Structural and Attribute Similarities. ACM Transactions on Knowledge Discovery from Data, 12, 2011.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. Adaptive Universal Generalized PageRank Graph Neural Network. In International Conference Learning Representations, 2021.

---

Eli Chien, Wei- Wei-Cheng Chang. Cho-Jui Hsieh, Hsiang-Fu Yu, Jiong Zhang, Olgica Milenkovic, and Inderjit S Dhillon. Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction. In International Conference on Learning Representations, 2022.
Yoonhyuk Choi, Jiho Choi, Taewook Ko, and Chong-Kwon Kim. Improving signed propagation for graph neural networks in multi-class environments. arXiv preprint (rXiv:2301.089// 2023.
A. Dang and E. Viennet. Community Detection based on Structural and Attribute Similarities, In The Sixth International Conference on Digital Society (ICDS), 2012.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
Austin Derrow-Pinions Jennifer She, David Wong, Oliver Lange, Todd Hester, Luis Perez, Marc Nunkesser, Seongjae Lee, Xueying Guo, Brett Wiltshire, Peter W. Battaglia, Vishal Gupta, Ang Li, Zhongwen Xu, Alvaro Gonzaez-G Yujia Li, and Petar Velickovic. ETA Prediction with Graph Neural Networks in Google Maps. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, CIKM '21, page 3767-3776, 2021.
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual Stochastic Block Models. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Kimon Fountoulakis, Amit Levi, Shenghao Yang, Aseem Baranwal, and Aukosh Jagannath. Graph attention retrospective. Journal of Machine Learning Research, 24(246):1 122 2023.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then Propagate: Graph Neural Networks meet Personalized PageRank. In International Conference on Learning Representations, 2019.
Jerome Gilbert, Ernest Valveny, and Horst Bunke. Graph Embedding in Vector Spaces by Node Attribute Statistics. Pattern Recognition, 45(9):3072-3083, 2012.
Stephan Günnemann, Ines Färber, Sebastian Raubach, and Thomas Seidl. Spectral Subspace Clus- tering for Graphs with Feature Vectors. In IEEE 13th International Conference on Data Mining, 2013.
William L. Hamilton, Rex Ying, and Jure Leskovee. Inductive Representation Learning on Large Graphs. NIPS 17: Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 1025-1035, 2017.
Yifan Hou, Jian Zhang, James Cheng, Kaili Ma, Richard T. B. Ma, Hongzhi Chen, and Ming- Chang Yang. Measuring and Improving the Use of Graph Information in Graph Neural Networks. In International Conference on Learning Representations, 2020.
Di Jin, Ziyang Liu, Weihao Li, Dongxiao He, and Weixiong Zhang. Graph Convolutional Networks Meet Markov Random Fields: Semi-Supervised Community Detection in Attribute Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 3(1):152-159, 2019.
Nicolas Keriven. Not Too Little, Not Too Much: A theoretical Analysis of Graph (Over)Smoothing. In Advances in Neural Information Processing Systems, 2022.
Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference Learning Representations (ICLR), 2017.
James R. Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher- order cheeger inequalities. J. ACM, 61(6), dec 2014. ISSN 0004-5411. doi: 10. 10.1145/2665063. URL https://doi org/10. 1145/2665063
Qimai Li. Zhichao Han, and Xiao-Ming Wu. Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning. In Thirty-Second AAAI conference on artificial intelligence, 2018.
Chen Lu and Subhabrata Sen. Contextual Stochastic Block Model: Sharp Thresholds and Contiguity. ArXiv, 2020. 1:Xiv:2011.09841.
12

---

Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The Expressive Power of Neural Networks: A View from the Width. In Advances in Neural Information Processing Systems, volume 30, 2017.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao- Wen Chang, and Doina Precup. Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification? arXiv preprint arXiv: 1ee.22009005544 05641, 2021.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is Homophily a Necessity for Graph Neural Networks? In International Conference on Learning Representations, 2022.
Sohir Maskey, Ron Levie, Yunseok Lee, and Gitta Kutyniok. Generalization analysis of message passing neural networks on large random graphs. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
Nikhil Mehta, Lawrence Carin Duke, and Piyush Rai. Stochastic Blockmodels meet Graph Neural Networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 4466-4474, 2019.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M. Bronstein. Geometric Deep Learning Graphs and Manifolds Using Mixture Model CNNs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
Kenta Oono and Taiji Suzuki. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. In International Conference on Learning Representations, 2020.
Philipp Reiser, Maximilian Neubert, Andreas Eberhard, Luca Torresi, Chen Zhou, Chen Shao, Houssam Metni, Clint van Hoesel, Henrik Schopmans, Timo Sommer, and Pascal Friederich. Graph Neural Networks for Materials Science and Chemistry. Communications Materials, 3:93, 2022.
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael M. Bronstein, and Federico Monti. SIGN: Scalable Inception Graph Neural Networks. CoRR, abs/2004. 2020.
T. Konstantin Rusch, Michael M. Bronstein, and Siddhartha Mishra. A Survey on Oversmoothing in Graph Neural Networks. arXiv preprint arXiv:2303. 10993, 2023.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The Graph Neural Network Model. IEEE Transactions on Neural Networks, 20(1), 2009.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93, 2008.
Roman Vershynin. DingensDimesion Probability: An Introduction with Applications in Data Science, volume 47, Cambridge University Press, 2018
Mark Weber, Giacomo Domeniconi, Jie Chen, Daniel Karl I Weidele, Claudio Bellei, Tom Robin- son, and Charles E Leiserson. Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics. arXiv preprint 1Xiv:1908.0259/ 2019.
Xinyi Wu, Zhengdao Chen, William Wei Wang, and Ali Jadbabaie. A Aon-Asymptotic Analysis of Oversmoothing in Graph Neural Networks. In The Eleventh International Conference on Learning Representations, 2023.
Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolei Du, Ken-Ichi Kawarabayashi, and Stefanie Jegelka. How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks. In International Conference Learning Representations, 2021.
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks, 2021.
Yang, McAuley, and Leskovec. Community Detection in Networks with Node Attributes. In 2013 IEEE 13th International Conference on Data Mining, pages 1151-1156, 2013.
13

---

Rex Ying. Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. KDD '18: Pro- ceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 974-983. 2018.
Si Zhang, Dawei Zhou, Mehmet Yigit Yildirim. Scott Alcom, Jingrui He, Hasan Davulcu, and Hanghang Tong. Hidden: Hierarchical Dense Subgraph Detection with Application to Financial Fraud Detection. In Proceedings of the 2017 SIAM International Conference on Data Mining, pages 570-578. SIAM, 2017.
Lingxiao Zhao and Leman Akoglu. PainNorm: Tackling Oversmoothing in GNNs, In International Conference on Learning Representations 2020.
14

---

A Linear Algebra and Probability Background
Before beginning our proofs, will establish the following theorems from the literature and basic facts that we will use throughout the proofs.
A.1 Linear Algebra
For matrix inequalities, use the following inequalities about matrix spectral norms.
Theorem A.1. ([Vershynin) 2018] theorem 4.5.3.) Let A be a symmetric matrix with eigenvalues
A 2 22 2 ...An and B be a symmetric matrix μt 2 P2 2 ...fha Suppose || 14-Bl 8. Then, max; A M4 5
We also use the following basic result to relate the matrix spectral norm to its maximum entry Lemma A.2. Let M be an symmetric matrix such that each row of M has at most non-zero entries and each entry of M has an absolute value al most è. Then [ || I em
Proof. We will use the fact that for any scalars a, b, have 2ab S a² b2 since a² 122 2ab (a - 6)2 2 O. We will also use supp(M) to denote the set of non-zero entries in M. Let be a unit vector. Then have
1oc T Mx
Σ
Σ
Ma)
x(t)x(ii
1,j E.jEspp((M)
Σ
2 x0)) + x1)² xx1)²
E
E.Exspp(MM
=m
Where the last inequality follows from the fact for every i, there are at most m entries j such that
Ma + O.
A.2
Concentration Inequalities
Throughout our analysis, we will mainly use the following two concentration inequalities. The first is bound on the the expected deviation of the sum of Bernoulli random variables
Theorem A.3. Let XI....X, be Bernoulli random variables with mean at most and S, = -im X, Then
Pr []S E[S,]]
1 exp( St
np
The second concentration inequality we will upper-bounds the spectral norm of random matrices whose entries have mean and bounded variance.
Theorem A.4. (/Bandeira and van Handel 2016] Remark 3.13) Let R be random matrix whose entries Rig are independent, zero mean, with variance o², Then with probability 1 n -9(1) we have
||||| S O
In particular, of 2 log then ||||| < <(ovm)
We will also use the standard tail bound on the norm of a Gaussian vector
Lemma A.S. Let ~ o2,), be a random Gaussian vector.
Then Pr [lle]| > t <
2 exp(p= -no=
15

---

A.3 Other Facts
We will also be using the following basic fact about approximating the exponential function Lemma A.6. For all 1+ e If S then ex - 2x.
B Proofs in Section
B.1 Proof of Lemma
In the following section, we give the missing proofs of the basic properties of the CSBM. The first is the reduction from the m dimimensionnal model the centered --dimensional model, which we will restate here:
Lemma B.1. Given an m-dimensional 2-block CSBM, there exist to E I and b E IR" such that Xw + where for each vertex 9: is i...d. (0, d²2) with o' / [lllv=
4a
Proof. Let Xi,: be the tth row of X. For each i E S, we have X.,. μ Di and for each j T we have X₁.: 9j, where 9: ~ ~N o² Im) are i..d. random Gaussian noise vectors. Now we pick (n v), - + v, p v. Now x' = Xw + b. For i S, we let
8' (1) = 4u 1 (1+ v) u) 2 |1 v11
and for i T. we let
( = 1 -
11 m11
The s' part is signal. On the other hand, the noise each entry is given by z'(i) (1)) (gt, μ 1 v) which is Gaussian with standard deviation a || - v/I. Now, we let -パ
then we have x = 8 + g. where s(i) E and each entry of g is i.i.d. Gaussian with standard Vn
deviation o' -
Proof of Proposition 5.2 and Characterizing the Convolution Matrix
In this section, we will provide some crucial properties of the graph convolution matrices in ① and then use them to prove Proposition 5.2 The adjacency matrix A is random matrix with expectation
[pJa/2 qJn/2] [Jnn/2
E[A|
pJa/2]
Where Jm denotes the all-ones matrix. It can be seen that E[A] is rank-2 matrix, with and s because E[A] 1 = 2 (p + 4)ll and E[A]s 1 (p q)ns, which means
eigenvectors /
1 E[A| = (p (p + + +5 9ssssss
Thus, in the centered one-dimensional CSBM, our true signal, s, is encoded in two ways: as the second eigenvector of the matrix [[A] and as E[z]. We can express our unnormalized corrected convolution matrix in terms of the signal, ss" Ts as follows:
(p (p-9)n
3p g)n d 11
1 + (A-RR((A)
Ā Recall from main text that defined n (p-g)n be the signal strength, d' (p+g)n/2-4 to be the degree deviation, and R A [[A] to be the error matrix. Thus, we have
11
88
72
2d
nd
1 + 1'11
À = nss"
Note that R has independent zero mean entries with bounded variance, and such random matrices have well-studied concentration properties. The main idea of our analysis is to show that d' and
16

---

R are small compared to our matrix signal strength with high probability so that A behaves like yss" T R yys" To analyze convolution with the normalized A, we use degree-concentration to show that Á is close to Å, and so also behaves like yas?.
Now we prove the main proposition in our section, Proposition 5.2 which we restate follows:
Proposition B.2. Assume that p S2( logn), ), and let P_9. the following concentration results
With probability 1 n-((1), we have
ptq
1. dd| dd- ((++))ml
< O(1/n2 which implies that oy E PTg (1 (1 o(1))
ad
2. [R]] I ((ppp)
3. Á yss" T
and | yss s
SO(v
logn np
Proof. To bound the deviation of the average degree is equivalent to bounding the total number of edges in the graph. Note that the expected number of edges in the graph is [p + q)n². Thus, apply Theorem
A.3 with @(pp + q)n 1.5) obtain
Pr
E
(p g) >1
S exp(- n -R(1)
Since d = El/n, n. we have that with high probability, Id [0 + g)ml S O(1 + v) and (p+g)y/
|d'| id- (p++-mml I O (ptg)nn(1 a(I) S O((1n'.5). This gives us bound number 1. To get
bound number 2, we apply Theorem A.44 on the error matrix R. noting that each entry of R has
variance most p. To get bound number 3, let It' j d'11 A- 7787. Then with high probability, we have
|2'|| S 7 [|] + d' I|
$ (p + q)n(1 - o(1))
||]|| d' |11"]
<0
+ vn
since
||11 T|
vp
0(
pp
Finally, analyze the corrected normalized adjacency matrix Å. In this case, want show degree concentration for every node. Let dy the degree of node v, and d = (p + q)n be the expected degree. By applying Thcorem[A.3] and using our assumption p > have
Pr [ide
d / Copllog exp((-2(log)
Thus, with high probability, we have ddg d s ((Vnpllgg)) for all u E V. Now, to analyze the normalized adjacency matrix, we have
|| A 788 T
| = Å 788
A
<
A
+
A - 7ss A-7
<
D- D-1/2 1D21/2
A
+ Σ. d
11/211 D2/2 -111T + +
Vap
To bound AD ///. let =
Clogn for large enough C' so that for all v, d, E
d( + e). We note that the adjacency matrix has at most d(1 + E) non-zero entries for each row and for each u, v, we have
Voncta al d(1 E) d(1 s 5o
17

---

Thus, by applying Lemma A.2
we have
|D-1//AA - 1/2 - //1l - O(e). Similarly, for all u, we
have
dd
1
dn(1 - 2 (
d(1 +))
E,d, di
7
n
Thus, Lemma
A.2
implies that
D212 11 11 - =11
- (s). Finally, this implies that
d.
738 [
T
$ 1
log np
Note that the case p > 9 corresponds to homophilous graph, and the case p q corresponds to heterophilous graph (see Luan et al. [202T]. Ma et al. [2022] for more), however, for binary classification, it has been shown [Baranwal et al., 2023a that once can assume p > q without loss of generality, and make corresponding adjustments in the classifier. Indeed in our case, if p then we can take - A as our convolution matrix so that its maximum modulus eigenvalue is positive. Moreover, since our signal, is centered, taking convolution with À is equivalent to taking convolution with -A. Thus, we can assume without loss of generality that y is always non-negative, i.e. p > q for the rest of our analysis.
C Proofs in Section 6
In this section, we will formally prove our first main theorem on partial classification, Theorem 4.1 To start, we will show the correlation between the top eigenvector of the convolution matrix M and s. Note that this result is well-knowd in the literature (for example see Vershynin (2018) chapter 4.5). We will give the proof here for completeness.
Lemma C.I. Suppose M satisfies || - 7888 S 6 where 7 > C6 for large enough constant C.
Let & be the top eigenvector of M. Then (s, 8)2 2 1 4 55 and ||s a|| = 0(8/7).
Proof. By assumption, can express M as 7ss Rt' where [|||| 5. Now let A be the k largest eigenvalue of M. By Theorem A.1 we have A ~1 s and vi > 1, |Ail < 8. Now consider the matrix ss which is the projection matrix onto the orthogonal complement subspace s. Since M 7s8 + R', we have
>( -s- -)= R
and the matrix 71 M has the same eigenvectors as M. In particular, is an eigenvector with eigenvalues 7 - A1. Thus, we have
7 (8, 8)2 = - ST (I ss T)
= 11 ss )&ll
= 11(71 AM) R'sll
S 11(>T M)&11 + ||
< 1 A1l 41I+0 6
< 25
Thus, we have (s, 8)2 18244827- Since by our assumption, 8/7 is small, 8 is very close to either or ss. For our analysis, it doesn't matter which of these is the case as both s and -s equally separate the points in our two classes. Thus, assume WLOG that (s, 8) > 0. As consequence, have
||s - 8|| = 2(s, 8) = - 2 2
=
where the second inequality follows from applying the first order approximation /1 (ax2) using the fact that y/y is small. Note that (s, 8) was negative, we can the same analysis in the following sections with -s instead of
z
2
18

---

Now we will prove the main result about partial classification in the 1-dimensional model, Proposi- tion [. which we restate as follows:
Proposition C.2. Given a centered I I-dimensional 2 block CSBM with parameters n. > 9, a and
((p.g) P-4,
p+q' suppose our convolution matrix M satisfies | - -Yss" || S ā and y z C6 for
large enough constant C. Let I = M be the result of applying rounds of graph convolution to our input feature x. Then with probability least - - expl T there exists a scalar Ck and an absolute constant C' such that
8 ||CL:t - S0 =010=000
(0(6
72 (
2h
no² logn 2
Proof. Let A1 2. ...An be the eigenvalues of M and w/ =: 8, u2..Wu, be their corresponding
eigenvectors. By Lemma C. the eigenvalues satisfy dι E 7 + d and [xl I 5 for >> 1. The convolution vector after k rounds can be expressed as I = M + M&s, s, and we will analyze each term individually.
M g = Xt (g, w188 +
Σ 121
x wi)ws
= (g, wils + X (g, wi (6 - -8) + Σ wi)
and similarly,
M X (s, w1)8 + Σ (s,
1>1
(f, wi>s
X (8, w 8) +
Σ X (s, ws)wr
i>1
Now we will let E, and Eg be the error vectors, i.c. vectors that are not in the span of s, from each of the terms respectively. That is
Eg (9, (g,(g,w)) w1)
8) +
Σ X (g. wi)wr
1>1
E, (s) - 5)+ + Σ A (s. w,)w
Thus, we have
2s = X 9. 8)s Eg + E, Thus, we will let Ck = (* g, 8)) and bound the squared norm of the error terms C Cx + E,). We will also use the fact that for any vectors y, we have |y + =1|² < 2 |1//1 + 2 || Using this, we have
|E < 2x I|s -31
31 +2
Σ
x (g. w.)
>> l
< <0((7189/))((380))))) + 28
(g wi)w:
s <0 g) 2822
|| 2
where in the second incquality, we used the fact that Lemma C.1 implics I|s - 311 < 0682/77). By
Lemma A.5 we have ||a|| 2 = Oo02 logn) n) with probability n (111) Also, (3. g) has distribution (0 1) because is a unit vector. Thus with probability exp( =f (8,g)) < 1/2. If both these
events happen, then we have || < O //2 + 82h on log Now, to bound the other error term, we have
|E.1 < 212* ||s 5| (3, s), +2
Σ
X (er, s)
1>1
< 2X2 ||s - 811 (8, 6), + 26 || 2
s 0(12288177))
19

---

where the last inequality follows from the fact that ||s||
1 and [^ -1- - 6, which is a constant factor smaller than \1. which means 62t = O 82 /22 Finally, we want to lower bound (8, 8) + (8, g) by constant so Ck = (Aa)) By Lemma C.1 we have (8. > 1 1- ((6/7)- We can assume that our constant C' is large enough so that 2/0
1/4, which means that ($. 2 3/4. Then
(8. + (s.g) 2 1/4 as long as (s.9) 2 or Ks. g)1 S 1/2. This happens with probability at least
2 exp( TØ=)) ))
2 exp( Toz); and if this does occur, we have
1| s11² - 20 || 20 ||
s 0 (A- /72 + 6 2022noo "nnnoooog log
0 + (6/ " n== log
Moreover, since A y 8, we have 8/A1 < 8/(7 6) = 0(6/7) since is least a constant factor larger than and this gives us our final bound.
With our main proposition established, we can prove our main theorem as follows:
Proof. (Theorem 4.1) First, we apply Lemma 5.1 to reduce to the one dimensional centered CSBM with parameters p.q 9 and o' = 0 Vn | [il Now let x Xw + b be our transformed one-
dimensional feature vector and let x M where M is either A or A. To bound the mean-squared error of our convolved data, we will apply Proposition 6.1] By Proposition 5.2 we can take
8 0 Hyp) if M À and 5 = O(v log
if M = Å. Then, as long as 7 2 C8 for large enough
constant C, we have scalar C2 and constant C' such that
( 82 (
C'5 26 0² Pog
||C - - 10
|| vl3
Now, we take 0 to be the threshold, meaning we put vertex é in the first class if I (1) < 0 and put it in the second class otherwise. Note that this partitioning scheme is indifferent to the scaling of the vector Tg. so we can equivalently apply it to Ca (note this does not necessitate computing C2 directly). Since each E S has s(i 1/ /ni and each j T has s(j) -n, vertex can only be misclassified if it contributes at least 1/n the total squared distance ||Cx.ra s|1 Thus, the total number of misclassified vertices is at most ||Cx. - =II? n, which gives us the main theorem after substituting the appropriate value of 8.
D Proofs in Section 7
In this section, we will formally prove Proposition 7.1 Before we begin, we will, as warm- up. analyze the behavior of convolution for the centered I-dimensional CSBM. The following proposition is essentially cquivalent to thcorem 1.2 in Baranwal et al. [2021). The proof here is not used later on, but gives some intuition about how to analyze exact classification using a matrix-focused framework.
Proposition D.I. Suppose we are given the I-dimensional centered CSBM with parameters n. 4, such that 2 20 log" n
Y 2
O(v
log n mp
and S <0( Vlogn
Then with probability 1 n -Q11,,
have
log n np
log n n
s 0
x
2
Proof. By the definition of our convolution matrix, we have
1
7 Σ1 = (nss* T + (s) + = s R's + (ss T + R')g
Thus, we can bound the infinity norm error as:
1
1
8
= - H's s + (ss T + R')
< (ss
+ 17
RR
+
- R's
11
17
17
20

---

Since the infinity norm is the maximum absolute value of all entries, we need to bound terms le, // and le (ss" + R /n)gg for all u V. We will start by bounding the Gaussian part of the error. Since ey (ss" + R /n)g ~ NNO, o² R / + (s, Cu)sll), we have that with high probability maxign ee (88" + R'/nng & O n [| e. n (s))))))) Now note that
(s, ea)l = 1/vn and by Theorem A.4 |Reell S | S Olo v np Finally, by Proposition 5.2
have - 7(1 (1)). Thus, we have
log np
log n
le (as T + R1/n)ol & s
VV
+
Now, to bound the error term c R'sl, we have R's = e C + = Rs since is orthogonal the all-ones vector. Now, WLOG, suppose u S. Notice that ey Rs = (ies Ru - Eier Ru,)), where both sums are sums over independent shifted Bernoulli random variables with variance at most p. Thus, by applying Theorem A.3 we have le R(s S - O(vnplogn) = =O(pplog)) Now, using the fact that Z { g) - (()),
de
we have I Ral S 0
Log
By our assumption, 7 2 CV
log n for large enough constant np
V
np
C. Then, we can take C' to be large enough that
1
ee
H'sl O (71-0(1)) V
1
log np
-
1
1
2/n
D.1 Proof of Main Result
In this section, we prove Proposition 7.1 which restate follows:
Proposition D.2. Suppose we are given I-dimensional centered 2-block CSBM with parumeters n. P: 9, a and l = O(log n) such that 7 ptq
P-g 2 2(ky
log n up
2 log n and σ S O Vilgnn
Then with probability at least 1 n -0(1)
1 Axx x 17k
S 2/7 7/m
- O(1,
) logn)
Before proving the main proposition, we will use degree-connentratioon to reduce analyzing the error matrix nas" to analysing R instead. This is useful because our analysis crucially uses the fact that
matrix R has zero-mean Radamacher entries.
Proposition D.3. Let R' Ā 1188" and suppose h: S O(log n). Then with high probability, have that RM dh R < O C'ko/oga for constant C. (ypp)*-<//
Proof. Before beginning the proof, first need to give tighter degree concentionninnnatioon bound to show that with high probability, |d'| S O
Vlggn
By applying Theorem A.3 with t O(n O(nyplogn) n).
R2 vp
Pr
7 (p + n) > .
>0] < exp(
n1 log
= -9(1)
(p 4)n²
Since d = =2|E//n and with high probability at, |E| > {p + g)n² - > [ 4)n²(1 o(1)), we
have d 2 (p + q)n(1 o(1) ((mp). Putting these together, get the bound:
ld' |d (p + g)nl
= [E| - {p + g)n?l
MVDplog
0 Vlgg n
< O n²p
nd.
ndd
n² vp
Now, recall from Equation probability, 1 |||]||| S V
2 that Rt - 2 d. By Proposition
5.2 we have that with high
C for some constant C. We will let d = v
C be this upper bound. Now
up
np
21

---

consider the matrix (g R² We will let Mo = 1 R and M1 d' 11 Then, we have ||olll S 1, do with high probability, we will assume this event occurs. Thus,
and | || I f Since |d'|
ylog n /p
Ol )) Finally, we have R1) = (Mo + Mi)* We are 22 (0, 1) in + ig + ...g = f). That is, it's the set of length binary sequences with exactly terms equaled to 1. Now, we have
we have |M & O nymploon n'v0
going to expand this out, and let us introduce some notation. Let (1))
(Mo M1)* MD
Σ
Σ
II
M.
MD
iE
(1
1=1
M
(1) j=1
For any matrices M, NN, their spectral norms satisfy || S |M [|]]] Thus, for each (11)
have | Me < |M]l since |M 1. Thus, we have
[| M1)* - Moll S
|M
< +IMM II
2k M|
where the second last inequality follows from Lemma A.6 because 1: &M $ kv assumptions on Finally, we have
log
by
R
RE.
8h [IMM M1)* Moll
dh
S 28 k ||
< 00 kC* Vockloon
(Vpn)t
For constant C.
As corollary, we can show the following:
Corollary D.4. Let and y be unit vectors. Then |x R S lx ( Rh)bl + 0 C"Aylogn )) for some constant C.
Proof. This follows from the basic properties of the spectral norm
1
1x: T 1t y) = 1
R² +
R()))l
dt
1
1x:
(
+ ||~||| ||
R
Rk
dh
1
C+ c*Kylogn
x T
Rh)y + o
))
by Proposition D.3
de
(ypr)* vn
Corollary D.4 key to proving our main technical lemma, the proof of which we will defer to the next section.
22

---

Lemma D.5. Given p 2 log"n we have that with probability 1 1-n -01)), for all V and all
E (1ogn...(loonn)
l T R s) S 1 V
(
(c
log n
pn
for some constant C
Now, ready to prove main result, Proposition 7.1 The proof is similar to that of Proposition D.3Jbur requires the use of Lemma(D.S to obtain a sharper bound on the error terms than by simply applying the spectral norm bound did in the degree-concentration proof.
Proof. (Proposition 7.1
Just like in the case, we express Ā as 1ss R'' and decompose our convolution vector into the following terms:
1 1
A o (*
1 s7t
+ A
sss
ss ss))s
In order bound + A+ will bound, for all V. the error terms |e_ ( A 88 )s|
and |e_ , A Similar to in the proof of Proposition D.3 we start by expanding out , A Let
Yo = 88 and Yi = It', Then we have
A
(n1o
+ Y2)
17
ryt
k Y
k-t
1
t=
(tl) j=1
Σ t=
Yi
(=)
Note that (ss )2== ss which means that the first term in our summation (i.e. the l = 0 terms) is simply ss" Now we start by bounding the error terms involving 8.
k
Ie ( At
17th
88 )sl
=
Yi
t=1
VE
(1)
1=1
k
eu
Y2,
1=1
iE
(k]]
j=1
For each i E (.). we have
le
II
Yr, le, Rm s. S R!o2s ...s R.as
where 01,...az are non-negative integers satisfying + ...aa = l. This is because the product II Yú, has exactly é terms of the form It' and ss for the rest of the terms. By Proposition 5.2 the matrix It' has spectral norm at most C₁ for some constant C₁ with high probability. For each Vap
term of the form Is T / for j > 1, we bound it by Is (R'as s| S || <
For the first
mmp
term le, Rd sl, we apply Lemma D.5 and give le,, Rios s| < C22
log 1o np
for some constant
Cz. Thus, we have:
si 5| Vn
max C2)
artm.or
v Vlogn"
< vn
1
(c
log np
/mp
23

---

where C' is a large enough constant such that C 2 max(C1, C2). Now, we let p ==
log
V
np
Assuming that 7 2 9Ckv log and with high probability, E r(1 + o(1)), we have p S 8k with
V
1
up
high probability. Thus, we have
k
|e 17t
1
88
-
11
Viy 8|
t=1
(kl]
j=1
k
(0v)
log n nap
nn
1=1
pt
((1 + p)* 1)
vn
$ 4
by Lemma A.6 and p ك 8k
Now, we bound the Gaussian part of the error:
--1
k
Ag
Y2,9 + 17 _e_ Rl
t=
EE
(+l)
j=1
For each i (1)) where < ki, we have
e
II j=1
Y2,gl
R s. TRoog. . ...sT R gl
where a1 +a2+t..0 = E. This is because when E < k, there is at least one Yi, term that is equalled to SsT, which means in the product, the lefimost term must be e R! s for some 01 and the right most term must be s Rt'01.g g for some ar., Once again, we use the fact that Is s/ S [| < Ch )ay
Vap
for all j > 1, and by Lemma D.5 we have |e], R sl (C2 v 'loa) yar where C1, C2 are absolute
ap
constants. To bound the last term, we have that T R g ~ N(0, o² |R'a>|" s||²) for all a > 0. Thus, with high probability, we have that |s IsT Rt* S O || | a|l Vlogn) S O(a( Cs jl Vlogn) n). vap
Thus, we can apply the same bounds as we did for the error term involving s but now with an extra / log n factor:
k
Yi,gl = le_ R s. sT R . ...sT Reas
Vlog
< 0
Vn
Vlogn
< (
(1 + k)
Vn
0 T Vog
by Lemma A.6
Vn
0
4
Where the last inequality follows assuming < C'vlogn for some large enough constant C². Finally, to bound the tth order term, we have that with high probability, 1) =e ne*ggl S ( C ) a Vogoo. n.
m/pp
24

---

Putting everything together, and using the fact that 2 7(1 o(1)) with high probability, we have that for all V.
le / 1 (Ie ss ss])s|+ 1e, gl) S 2/n" + for some absolute constant C'
1 opp
C
ov llog n)
Yrpp
Given Proposition 7.1
we can derive Theorem 4.2 by using the standard reduction in Lemma 5.1
Proof. (Theorem 4.2) By applying Lemma 5.1 see that given m-dimeensioaa features with feature matrix X, we can transform to a centered i-dimensional feature vector x = Xw + 8 where g (O, o²² and o' - Thus, we have || - u1|
By Proposition 7.J our
d'vn'
1 I-dimensional features become linearly separable as long as my Vlogn < 2/n for some absolute constant C. Given our expression of o' in terms of the mean distance, this is equivalent to
V ell 2
log
YVpp
In Proposition 7.1 we also needed to assumed that o' S 00 Vlogn which implies that
log
|| μ4|| 2 2(0
n
D.2 Message Passing Error Bound
In this section, we will prove our main technical lemma, Lemma D.5 By Corollary D.4 it suffices to control the term le [P in order control le, R2 1e Since this is the sum over many dependent random variables, we cannot easily compute its moment generating function. Instead, we will compute the moments directly. In particular, we will apply Markov's inequality using the 21 moment of this random variable [[[e, R 2)*1 for an appropriately chosen t. We now state our main result for this section follows:
Proposition D.6. Suppose is an n. X n symmetric random matrix where for each siis j. R 1 Pi, with probability Pt.j and -Ps,3 with probability 1 Pt.5 and are independent. Let p maxi, Pi.j. and suppose 2 Q log "). Then we have
Pr 10
R
S exp( (CVnplogn)*
Vn
Proof. The term e," R s can be written as the sum over all walks of length & originating from u. Let Wi.k denote the set of all walks of length & originating at u. For brevity, will use W to denote W.. For each E W, let w(j) be the jth vertex in the walk. Note that w(0) always. Then we have
e R
II wE
Σ
Rw s(w()))(()))
Thus, we have
2t
E[ T Rh s)2{
Σ
E
Ru, (1- ((xx))(
10g W
[=1 5=1
28
k
21
Σ
[E
Rw v.ll
II (s()(()))
3i Wi.W..... EW
i=
j=1
1
Σ
21
R ( ())l
n
W1 Ma EW
i=1j=1
25

---

Where the last equality follows from the fact that [s(u)] = 1/v2 for all v E V. Now, for each i = (w:))) E 2 and edge h E n, let # (h) ) be the number of times the edge h occurs in the graph ui UwepU, In other words, for h = {a, b). # (h) is the number of times the variable Ra,5 occurs in the product I I1 (1),
We will also let | denote the number of unique edges in the graph formed by the union of these 2/ walks. For example, if vr consist of the walks (1, 2, 3), and (1, 2, 4), then we have #1, = 2, #2(,,3) = 1, # a (2, 4) 1, and |aح|| 3. Using this notation, we have
26 E
Σ
Σ II
M1 W1. EW
==1j=1
WEW hefm
Now we note that each R2 has [[RA] = 0 and for all 2 2, we have
E B
I B[ = Pa ph) + ph - Ph.) = p1 - ph)) + Ph (1-11)
Thus, the term [h | is only nonzero if in the union of the edges in the walks Why.-. W2t, each edge counted least twice, and if it is non-zero, then it is the product of at most | terms of value at most p. We now let W paér be the set of such walks, which we will denote as "valid walks". As an example, when t = 2 and k = 2, the walks (,1,,,3), (1, 2, 3)} would be valid but {11,2, 3), (1, 4)3 would not be valid. Now we have
Σ NEW AE[1]]|]
II
E
R [ < h
Σ p |
WEW pair
Ep'K Σ
Mpairs
| = =
Now, what we have left is counting problem. We need to count the number of valid sets of walks whose union has exactly distinct edges. We note that l can be at most th because otherwise, there must be an edge that is counted at most once, making the walks invalid. Since it is difficult to count this quantity exactly, we will just upper-bound it as follows:
Proposition D.7. Suppose
log a and t < log a 2k
Then we have:
2tk
K {w E
2
W eH
<
(26- - 1)1! - 22k-22
pair:
28
The notation of n!! denotes n n 4. Given this upper bound the number of valid sets of walks, are ready to give our final bound. We will let t C. log for large enough constant
2h
C1. Note that the only constraint on is that it is positive integer, and this is feasible as long as
k Ologn)) n). Since p log" a
have np (tk/Ci)² We will make the substitution b = tk l.
Then we have
tk
ck
2tk
Σ 1=1
Mi E w poirs |:ج|| = =0 0 S
(np) th ( 22 2h 1)!!
2b
b=
tk
(np) th ( (2tk)26 (2
(26)26
(2p)) 0k
(2t 36 26
< (np) (2tk) th
(c)e2)6
I (2t)))(2t)) Lk
(26)!
620
S <(((p)) 2h (2
In the second line, we used the fact that (2tk 2h- 1)!! is the product of th b terms of value at most 21 as well as the standard upper bound of (2tk)
22 28
the second last bound follows
(26y25
26

---

from our assumption p. and the final bound follows from the fact that the sum converges. Putting all of this together, we have that for
C₁ log
and p z
log
26
n
El(e, 12 s) S 00 (2tkT))) th
nt
Now, we can apply Markov's inequality on the th moment with t = C₁ log
2h
Pr [] le_ R >
Anl (CVnploon)]]]
1
n'B((c, R)
vn
C (mp log n.)
0 (mp log n) Ork
(20k (mplog n
VC lug
S 00 Clogn
exp( exp(-S(logn)
for a sufficiently large constant
Now, we combine our results from degree-concentration and the message passing error bound to prove the main result of this section, Lemma D.5
-. Proof. (Lemma D.5) First, note that for 0, the bound clearly holds, as le sl = Vn.
Now for
general k, we start by applying Corollary D.4 to obtain
&C Vlog VTp"
Te R
S dh le R O
For some constant C₁. Now by Proposition D.6
we have that with high probability ey Rits S vn (C2v/mplogn) for some constant C2 and 2 Hp + q)n(1 o(1)). Thus, we have
Note that Vlg is bigger than k-log n for large enough n. take C' to be around max(C1, C2) to obtain our upper bound. Finally, by applying union bound, we can ensure that with high probability, bound holds for all V.
Te le Ras < 1
vn (C2v log
pn
Thus, the jh le R* term clearly dominates
D.2.1 Proof of proposition Proposition D.7
In this section, complete our proof of the main message passing error bound by proving the upper bound on the number of valid sets walks of length k.
L) to first count Proof. (Proposition D.7 The idea bound the quantity (( Wpair: [لا|
all the ways to partition the edges of the 2f walks into exactly groups of size at least 2. Then, for each partition, we count the number of ways to assign the vertices of the walks edges of the same group are assigned to the same pair of vertices. In the grouping stage, we first pick 28 walk edges and pair them with each other, assigning a new group to each pair. Then for the rest of the 2/k 2 edges, we assign each of them to one of the E groups. This ensures that each group has at least two edges. The number of ways to pick 28 edges is (2kl). The number of ways to pair these edges is (2f- 1)!! (2f () - 3)... 1. Finally, the number of way to assign the rest of the edges to one of the groups is f(2kt-20) 26) Thus, the total number of valid partitions of the edges is at most (2tk)
way such that all
2r (2e 1)!! 2 Note that this upper bound is tight when É = th but becomes less tight becomes smaller.
Given a partition of the edges, we now count the number of ways to assign the vertex variables w;()). We will give simple assignment algorithm such that every valid assignment is possible output of the algorithm. Note that not every output of the algorithm is necessarily valid, so we are actually over-counting.
27

---

Vertex Assignment Procedure
Pick an arbitrary partitioning the edges into & groups without singletons
For i 2t:
For to k
* the edge (wi(j - 1), w; (j)) not part of a group which contains an already assigned edge, then pick new vertex for w; (j).
* Else. let (j' - 1), wy (j)) be an edge in the same group as (wyy(
1), wx(i) such that both We 1) and wy (J") are already assigned. Then assign w;(5) such that {w;(j - 1). w;(i)} = (w, - 1), wy (i))) If no such assignment possible, then the procedure fails.
To that every possible valid walks can be outputted by this procedure, if we are given some w = (W.e). E W pairs we can take the partitioning of the edges in the first step to be to be the partition induced by the union of the edges of the 2t walks. Then, we can simply follow the vertices of the walks in the same order as in our assignment procedure and see that each time we encounter new edge corresponds the first case of the inner for-loop and each time we traverse an already traversed edge corresponds to the second case in the inner for-loop where the procedure does not fail. Thus, the number of valid sets of walks with distinct edges indeed upper bounded by the total number of possible outputs to our vertex assignment procedure.
To bound the number of possible outcomes in our procedure, for-loop, there are at most n possible assignments for the vertex w; (i). In the second step, there is only one possible assignment the procedure doesn't 't fail. Since encounter the first case of the for-loop at most times, the total number of vertex assignments given fixed partitioning of edges is most n.. Finally, this gives the desired bound:
that in first of the inner
2tk
2 pair!
(26 1)1! (2t-2((n))
28
28

---

E Proofs for Section g
In this section, we will prove our main results for multi-class analysis. Theorem 8.1 First, we will characterize the convolution matrix in terms of the expected adjacency matrix:
Lemma E.1. In the multi-class setting, the convolution matrix, A, can be decomposed as Ả == M+R where:
.M has rank L 1, with L eigenvalues equalled to (p-q)m = X. Also, MU = AU at.
R' is a random matrix such that with probability at least - n -Q(1, || S pp/)/ vnq(1 q))) =
Proof. The expected adjacency matrix in the multi-class setting can be written
ppJntt qJnft. ... -./r.. qJn/L pJnfL ... q.I/L (qJ1. + (p ()) @ Jayr. qJn/t. [qJn/L
E[A]
qJn/I.
qJn.L ... pJpnL.
The top (normalized) eigenvector of E[A] is I. The top eigenvalue is the expected degree d = pn/ L + (L 1)/n/L. Moreover, E[A] has rank L and its eigenvectors are of the form V L e & 1// where v is an eigenvector of the matrix (qJz + (p I)). Since the top eigenvector
11 1 J..1 V n/L, the rest of the eigenvectors of [[A] must be of the form / 4 122
is vn
1n/L. ... 4uz 1n/t, where U2,... Ur, are an orthonormal basis of the subspace in R orthogonal 1n. Thus, for L.. we have [[A y @ 1) = (p g)n(u @ 1). which means the second to th eigenvalues of [B[A] are equalled to Ad.
Now let R = A A] and. Then we have
1
1
d R B[A] = d -
1 11T n
A
A
-
11
d
d
71
Now, let M := ]E[A-] -111T Note that the non-zero eigenspace of M is equivalent to 2nd to show that MU = U, let any column of U. By our assumption that each class has one center, the entries of are constant on each class. If we define v E IR such that v() = u(i) for E C₁, then we can write u = v X 1,/L. Since by our assumption, 1 Ln, we must have 1 LZ. Thus, spanned by the non-zero eigenvectors of M, which means Mu Au.
t eigenspace of E[A] and the corresponding eigenvalue
that is exactly in the subspace
Now, we simply have to bound the spectral norm of the matrix R' : 2 1)A. We start with bounding [|]] To do so, we can write R as R = Rp + Rg. where R, and R. contain the entries of R corresponding to intra- and inter- class edges respectively. Note that Rp is block diagonal with I. blocks of size n/ T.. Each block is size n/I. n/ T, and have i.i.d entries. By Theorem A.4 each block has spectral norm at most O(y/n(() - p)/L) with probability at least 1 n 11) Similarly, we have R S O(vng(1 - q)) with probability least 2(1) This means || < (((pp((11ppppppppppp111
+ /ng(1- -))
Now, we bound the degree deviation. Recall that d 2 where |E| is the number of edges in G. By applying Theorem A.3 with
Vnp(1 p)/T. + Vng(1 q), we have
t² 5 2(1)
Pr [|] d| > |] S exp(p1p0 -2(
~2(1)
max(p,
since min(p. q) > log" n/n. Assuming that Id - d Σ and noting that |||||| S d, we have [(2 A < R|| < t/d. Thus, we have Ā = M + R', where || R'll < 8 with high prohability. I1
We will also need to bound the operator norm distance between the th convolution and M*
29

---

Lemma E.2. Suppose {| > 2k8. Then with high probability, we have
1 Mt)
(A*
$2k6 22k8/11
A
Proof. By Lemma E.1 we have
A
(M + R) = M + Σ
II 1=1 (T))
Σ
MM-
where the inner sum is over bit-strings b of length is with exactly L I's and k - 1 O's. Note that
||M]] |\| and [|] I 5 with high probability. Using the fact that ||AB|| S ||||| [B] and triangle
inequality, we have
L A ((M+ + (R)*
M*)
k
|M
IR''
Σ
8
8 ) j
A
Our assumption that [^] > 48k implies the RHS is at most 2k8/[A| by Lemma A.6
Now we are ready to prove Theorem
Proof. We can express the total squared error after convolutions as:
Σ
(k) 2
x
U
We decompose our data as X
U' + G. where G is a Gaussian matrix with i.i.d (1,, o²) entries.
Recall that we take our scaling factor to be 1/1*. Thus, we have
x u =
1 1 A
a + G) u
2 F
AA
+2
By Lemma we have MU = NU. Let U1 Um be the columns of U. Then, we have
1 A -U U
2
1
1
(A*
M
F
1
N CĀ*
M yus
x (āt Mw/ /| ||u:11
1
x (A* M²) || 110/12
s ((8//1)) ||UT|
where the last inequality follows from Lemma
E.2,
By Lemma A.S. have, with high probability,
* A
<
1 Tr(A22) )o²n m log
x2k
F
Since adding R' to M perturbs its eigenvalues by at most 8 (Theorem A.I we have
A Tr(A²*) < (1 + 21+ 1) + (6/111))
||| > 48k implies (1 + 2/ < 0(1). Now let ne be the number of points such that
1 (k) ps 2/2. Then we have
n. A ك (+) 11 < {0(66)12))) (L + m66/121)2* log
30

---

Dividing both sides by A gives us the desired bound.
A/2, then it is closer to its own center than any other center. Thus, the softmax classifier can correctly classify all such points.
Finally, we recall that A is the minimum distance between centers, Thus if |x(00 |4|
E.1 Additional Figures for Multi-class simulation
Finally, we conclude our section with some additional figures to illustrate the performance of the corrected convolution on synthetic data. We compare the corrected and uncorrected convolutions via both linear and non-linear models. Our means are class means are given by the standard basis vectors. For the linear model (figs 4a 4c), we look five 1-vs-all classifiers followed by softmax to predict the class label, while the non-linear method (figs 4d 4f) follows a typical two-layer MLP-based architecture. In both cases, we observe that the corrected convolutions in performance the number of convolutions increases. Note that while the performances are similar between linear and non-linear classification, non-linear classification required in general when each individual class mean cannot be separated from all others via linear hyperplane.
not deteriorate
Accuracy
Accuracy i.
Accuracy
GCV
GC1
GCI
Number Convolutions
Number Convolutions
Number of Convolutions
(a) Linear method, 4 = 0.02, a (b) Linear method, = 0.02, σ (c) Linear method, = 0.04,
1.
Accuracy
Accuracy
Accuracy
OCC GCX 12 ramoodd
Gcs Ai7 12' ramovst
GC1 wit 12" removes
Number of Layers
Number of Convolutions
Number of Convolutions
(d) Nonlinear method, q (c)2,(e) Nonlincar method, g 0.02, (f) Nonlinear method, 0.04,
Figure 4: Accuracy plot (averaged over 50 trials) CSBM data with 5 balanced classes, 500 nodes per class and orthogonal means, with fixed p = 0.1.
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims made match our theoretical contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: We mention that we work on the contextual stochastic block model. Also, throughout the paper we mention limitations of our analysis.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
32

---

Justification:
We do exactly what the question asks.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide information about the settings in our experiments. We also provide reproducible code.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
33

---

Answer: [Yes]
Justification: We provide code that reproduces the experiments by just executing simple Python notebooks.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
//nips. //nips.cc/ppl wwwppbblccguuiicuceccccccoe.oopp hetggudddeeeoeeubbinninn
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We do exactly what the question asks.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We do provide errors bars in our plots.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
34

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We do exactly what the question asks.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httph::t///// httttpp://eerrrpp...cpppll////// httppbliieetiiicccudeeeeeeeeeeee
Answer: [Yes]
Justification: We have read the NeurIPS Code of Ethics. Our work is theoretical and we don't believe it has direct path negative societal impact. On the contrary, we hope that our thorough theoretical analysis helps in interpreting performance of the models that we use, which could. potentially, have positive impact safety, security, discrimination. surveillance, deception and harassment, environment, human rights, bias and faireess.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: As mention above, work is theoretical and we don't 't believe it has a direct path to negative societal impact. On the contrary, we hope that our thorough theoretical analysis helps in interpreting performance of the models that use, which could, potentially, have positive impact in safety, security, discrimination, surveillance, deception and harassment, environment, human rights, bias and fairness.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
35

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper is theoretical. poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
36

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
37

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
38


Reviews:
[{"review_id": "QfEx0KtRDm", "reviewer": "Reviewer_xoAh", "summary": "In this paper, the authors present a comprehensive theoretical analysis using the contextual stochastic block model (CSBM) to evaluate the performance of vanilla graph convolution after removing the principal eigenvector to prevent over-smoothing. They conduct a spectral analysis for k rounds of corrected graph convolutions and provide findings for both partial and exact classification.", "questions": "1. (Refer to weakness # 2) Would it be possible to analyze GNNs employing various convolution methods with shallower layers?", "limitations": "The authors have addressed some of the limitations of their work (limited to the binary classification case). Their work does not present any potential negative societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper provides both detailed theoretical analysis and experiments on three datasets: CORA, CiteSeer, and Pubmed.\n\n2. The paper provides a novel insight on why corrected convolution can mitigate over-smoothing and improve classification accuracy.", "weaknesses": "1. The synthesized data by CSBM might be adequate to illustrate the binary classification case, but the multi-class case could be more complicated. For instance, it is illustrated in [1] that the effects of signed propagation under binary-class case and multi-class case could be quite different. It is mentioned that the authors would like to analyze the multi-class CSBM using more sophisticated architectures and I look forward to the further analysis.\n \n2. Instead of stacking more than 20 layers of GNNs, it is a common practice to limit the number of layers to 3 to 5. According to Figure 3, the accuracy of the three learning methods appears more complex when the number of layers is limited to 5 or fewer. Therefore, the conclusion may not be applicable to real-world data applications.\n \n[1] Choi, Yoonhyuk, et al. \"Improving Signed Propagation for Graph Neural Networks.\" arXiv preprint arXiv:2301.08918 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for the thorough feedback on our work. It certainly helped us improve our manuscript.\n\n> The multi-class case could be more complicated. It is mentioned that the authors would like to analyze the multi-class CSBM using more sophisticated architectures and I look forward to further analysis.\n\nWe have extended our partial recovery result (Theorem 4.1) to the multi-class setting. Statement and proof of our result are in the global response. In our analysis, we have $L$ classes, and features are generated by a Gaussian mixture model with one mean for each class. We show that the graph signal is measured by the quantity $\\lambda = \\frac{(p-q)n}{dL}$ where $d$ is the expected degree. The graph noise is bounded by $\\delta = O(\\frac{1}{d}(\\sqrt{np(1-p)/L} + \\sqrt{nq(1-q)}))$. We assume that $|\\lambda| \\gtrsim k\\delta$, and the cluster means are well separated. We show that after $k$ rounds of convolution of the data for sufficiently large $k$, $1-o(1)$ fraction of points will be closer to the means of their class than that of any other class. This means a classifier exists that correctly classifies $1-o(1)$ fraction of the data. Our bounds are similar to Theorem 4.1 in our paper. We refer the reveiwer to table 1 in the response pdf for detailed discussion of our theoretical guarantee in different regimes of parameters. We also provide experimental results on synthetic data for the multi-class CSBM that mirror our theoretical bounds (see the response pdf).\n\n\nFinally, we note that for multi-class CSBM, there is a wide range of assumptions one can make about the class sizes, edge probabilities, and distribution of features. One key assumption we made is that each class has one feature mean. Other models (ref line 385) have analyzed instances where one class can have multiple means. We believe we can extend our analysis to even broader multi-class settings in the future with additional techniques.\n    \n> It is illustrated in [1] that the effects of signed propagation under the binary-class case and the multi-class case could be quite different.\n    \nThis is a good comment. We will discuss this in our revision along with the reference you provided. Indeed, the heterophilic setting in the multi-class problem can be more difficult than the homophilic setting. Using our new theorem above, we formalize this observation below using CSBM. Just as in the case of 2-classes, there is no difference in our analysis between the homophilic $(p>q)$ and heterophilic $(q > p)$ cases.\n\nNote that in the homophilic case, $\\lambda>0$ and in the heterophilic case, $\\lambda<0$. Implicitly, we are applying signed propagation in the heterophilic in Theorem 1 because of our scaling factor of $1/\\lambda^k$. Thus, one can view it as applying the convolution $\\tilde{A}/\\lambda$ each time.\n\nWe show that as long as $|\\lambda| \\gtrsim k\\delta$, the data will become well-separated after $k$ convolutions. This is because $\\tilde{A}^k$ will tend towards its dominant eigenspaces, which correspond to the eigenvalues that are large in absolute value. However, the value of $\\delta$ itself can be much worse in the heterophilic case. In Lemma 2, our upper bound on the noise from the graph, $\\delta$, scales with $\\sqrt{np/L} + \\sqrt{nq}$ when $p,q < 1/2$. Assuming we fix $\\min(p,q)$ to be small, if $p >> q$, this quantity is much smaller than when $q >> p$. This suggests that while the signal strength from the graph is the same, the noise can become much worse if we have many classes in the heterophilic case.\n\n    \n> Comment 3 and Question: It is a common practice to limit the number of layers to 3 to 5. According to Figure 3, the accuracy of the three learning methods appears more complex when the number of layers is limited to 5 or fewer. Therefore, the conclusion may not apply to real-world data applications. Would it be possible to analyze GNNs employing various convolution methods with shallower layers? \n\nWe agree with the reviewer that for shallow networks, there might not be a performance difference between the three convolutions tested in our real experiments. Since the reviewer seems to ask for a theoretical comparison among the convolutions in our paper, we can compare our exact classification result (Theorem 4.2) with previous work in the same model but with uncorrected convolutions. We observe that even in the case of one convolution, under appropriate assumptions in CSBM, the uncorrected convolution achieves the same performance as the corrected convolution, thus verifying the reviewer's claim in synthetic data as well. In particular, in our Theorem 4.2, if $k = 1$ (one convolution) and $\\frac{p-q}{p+q} = \\Omega(1)$, then the exact classification threshold for the feature signal-to-noise ratio $\\frac{\\|\\mu-\\nu\\|}{\\sigma}$ is about $\\sqrt{\\frac{\\log{n}}{np}}$. Theorem 1.2 of the reference in line 381 shows the same separability threshold for uncorrected convolutions in the same setting up to a factor of $\\sqrt{\\log{n}}$, which can be removed by more careful analysis (see ref line 385).\n\nIn our paper, we quantify how many convolutions are necessary to attain optimal behavior in CSBM. In Section 4, we provide several examples of model parameter values for which only a constant number of convolutions is optimal. We provide more such examples in the multi-class model in our response pdf.\n\nConcerning a high number of convolutions, we note that oversmoothing is a well-studied problem in the GNN community, which we do not claim to have resolved. However, we believe our results offer new theoretical insights into the oversmoothing phenomenon that we hope could be useful in future studies constructing deeper GNNs that are more effective.\n\nFinal remarks\n\nIf the reviewer has more actionable suggestions to further improve our work, please kindly let us know. We would be happy to address any further questions. We hope the clarifications are sufficient for them to consider raising their score.", "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": "", "extra_scores": {}}, {"review_id": "yD0mtQ5Qfa", "reviewer": "Reviewer_eGdd", "summary": "This paper studies over-smoothing from $k$ rounds of graph convolutions in the Contextual Stochastic Block Model by considering vanilla graph convolutions and a corrected one where the principal eigenvector is removed. Using spectral analysis, the authors derive the partial and exact recovery for both cases and show that the corrected convolution avoids over-smoothing. They derive the classification error for different densities $p$, $q$ and separability $\\gamma$ of the underlying graph model.", "questions": "Please refer to the Weaknesses.", "limitations": "The analysis is in linear setting, and extending it to non-linear activations may be challenging.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The theoretical analysis is thorough and comprehensive. The studied setting is also of practical significance and the authors provide rigorous theoretical analysis. \n2. The presentation is clear. The discussions on the theoretical results and assumptions are very helpful in understanding the paper.\n3. Experiments also support the theoretical results.", "weaknesses": "There are no critical weaknesses in the work. I have a few comments/questions which I list below.\n1. One aspect of the result is the dependence on the density of the graph as well as good SNR ratio. Can the authors comment on the need for denser connectivity in the graph for recovery? \n2. The performance of the corrected convolution decreases with $k$ in the case of a multi-class setting. The authors reason it as the projection onto the second eigenvector cannot capture the full class information. However, in the balanced data setting, all the eigenvalues of the corrected convolution are the same, with eigenvectors having information about the classes. So, in expectation, shouldn't the performance be unaffected?\n3. The analysis considers homophily structure of the graph $p>q$. Can it be extended to heterophily case as well?\n4. In the definition of $\\hat{A}$ in equation 1, shouldn't the last $D$ be $D^{-1/2}$? The negative sign is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their thought-provoking questions and comments, and are grateful for the encouraging review. We answer the questions below.\n\n> Question 1: One aspect of the result is the dependence on the density of the graph as well as good SNR ratio. Can the authors comment on the need for denser connectivity in the graph for recovery?\n\nIn general, the lower bound on density ($p$ value) is required for degree and matrix concentration (see Proposition 5.3). In case the reviewer is asking why Theorem 4.2 requires a higher density than Theorem 4.1, this is just an artifact of the more technical analysis for Theorem 4.2. We believe with better analysis, we can probably remove the extra $\\log n$ requirement in Theorem 4.2. Specifically, the proof of Theorem 4.2 requires some combinatorial counting arguments to bound the moment of the entry-wise error in the convolved feature vector. In counting these combinatorial objects, we sometimes applied some crude upper bounds which are likely not tight.\n\n> Question 2: The performance of the corrected convolution decreases with $k$ in the case of a multi-class setting. The authors reason it as the projection onto the second eigenvector cannot capture the full class information. However, in the balanced data setting, all the eigenvalues of the corrected convolution are the same, with eigenvectors having information about the classes. So, in expectation, shouldn't the performance be unaffected?\n\nThat is a good observation. Indeed if the convolution matrix's top eigenvalue has multiplicity $L$, then after many convolutions, we are projecting onto the top $L$-eigenspaces. In response to these insights, we have produced new analysis on multi-class CSBM (see global response), in which we generalize Theorem 4.1 (partial recovery result) to the multi-class setting with balanced classes. If there are $L$ classes, the second eigenvalue of the expected adjacency matrix has multiplicity $L-1$ just as the reviewer pointed out. We show in our analysis that if the perturbation is small and $k$ is not too large, the corrected convolution will still behave like projecting onto the second to $L^{th}$ eigenspace of the expected adjacency matrix. \n\nIn the case of real data, it is still likely the case that projecting the features onto the top few eigenspaces is not sufficient to capture all the information of the class labels and could also destroy some relevant information within the feature distribution. However, we still demonstrate that simply removing the top eigenvector leads to improved performance in the oversmoothing regime. We thank the reviewer for this observation and will modify our write-up accordingly to include this discussion.\n    \n> Question 3: The analysis considers homophily structure of the graph $p>q$. Can it be extended to heterophily case as well?\n\nOur results hold for the case where $q>p$ as well. See lines $159$ to $161$ in our paper. \n    \n> Question 4: In the definition of $\\hat{A}$ in equation 1, shouldn't the last $D$ be $D^{-1/2}$? The negative sign is missing.\n\nThanks for catching the typo. The second term should be normalized by $\\mathbf{1}^\\top D\\mathbf{1}$. Here, $D^{1/2}\\mathbf{1}$ is the top eigenvector of the normalized adjacency matrix.\n\n> Limitation: The analysis is in linear setting, and extending it to non-linear activations may be challenging.\n\nIn our analysis on binary classification, the linear classifier was sufficient. However, for multi-class data, we could require non-linear classifiers. We have extended our partial recovery result (Theorem 4.1) to the multi-class setting which involve the use of a non-linear classifier (see global response). In our analysis, we have $L$ classes, and we assume features are generated by a Gaussian mixture model with one mean for each class. In our results, we show that the graph signal is measured by the quantity $\\lambda = \\frac{(p-q)n}{dL}$ where $d$ is the expected degree. The graph noise is bounded by $\\delta = O(\\frac{1}{d}(\\sqrt{np(1-p)/L} + \\sqrt{nq(1-q)}))$. We show that as long as $|\\lambda| \\gtrsim k\\delta$, and the cluster means are well separated, then after $k$ rounds of convolution of the data, $1-o(1)$ fraction of points will be closer to the mean of their class than of any other class. Given this guarantee, we can correctly classify $1-o(1)$ nodes using the non-linear classifier: $x\\mapsto \\text{softmax}(\\|x-c_l\\|^{2})_{l=1}^L$, where $c_l's$ are cluster means from each class. This is a quadratic classifier, where the means $c_l$ are the learnable parameters.\n     \nWe note that in our model, we assumed there is only one mean for each class. It is possible to add more complexity to the model by having multiple means in each class and considering different ways they can be distributed. See, for example, the reference in line 385 where the authors analyze an XOR based data model for binary classification, requiring a non-linear classifier. We hope to extend our analysis to capture these more general models and classifiers as well.\n\nFinal remarks\n\nOnce again, we would like to express our gratitude for the thorough examination and feedback of our work. We believe that it certainly helped us to improve our manuscript. If the reviewer has more actionable suggestions to further improve our work, please kindly let us know. We would be happy to address any further questions. We hope the clarifications and additional comments are sufficient for them to consider raising their score.", "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": "", "extra_scores": {}}, {"review_id": "RK165Mc1rs", "reviewer": "Reviewer_uSHp", "summary": "This paper studies the concept of oversmoothing via a CSBM modeling of a GNN structure, and views the behaviors of vectors after repeated multiplications of a graph. Importantly, they consider a scheme where a dominant eigenvector is \"left out\", so that it does not dominate the behavior of the evolution so much, and show enhanced performance over real world datasets.", "questions": "What is CSBM? I know SBM but what makes it C?\n\nHave you considered scenarios where the data has clear block structure, but it does not 100% overlap with the true labels? will it cause undesirable biases? can those be quantified?\n\nActually, one interpretation of this is that the adjacency spectrum somewhat mirrors the Laplacian spectrum, but in reverse order. So, the dominant eigenvector corresponds to the nullspace of L, and the second one is the one associated with the mixing parameter in L. So, in that sense, it makes sense why focusing on that eigenspace gives better performance. I would be interested in hearing the authors' view on this.", "limitations": "no ethical issues", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper explores an important problem from a simple enough framework that it is tractable. There are a ton of statistical results, which all look reasonable and tell a reasonable story about the balance between learning and oversmoothing. \n\nThe idea of discarding the dominant eigenvector is also interesting, and clearly does show improved results in the numerics.", "weaknesses": "It's not clear to me how informative / predictive the various statistical results are to oversmoothing in practice. Can there be some figures that show the theoretical bounds, compared with true performance over some simulated examples? For example, one of the theorems uses  Davis/Kahan, which is pretty pessimistic in practice. In general, perhaps the spectral gap alone is not informative enough to showcase the entirety of the oversmoothing behavior, and while that is certainly fine given the complexity of the problem, it still would be useful to see the theorems compared with in practice behavior.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the insightful questions and comments along with the encouraging review. We answer the questions below.\n\n> Comment/question 1: It's not clear to me how informative / predictive the various statistical results are to oversmoothing in practice. Can there be some figures that show the theoretical bounds, compared with true performance over some simulated examples? For example, one of the theorems uses Davis/Kahan, which is pretty pessimistic in practice. In general, perhaps the spectral gap alone is not informative enough to showcase the entirety of the oversmoothing behavior, and while that is certainly fine given the complexity of the problem, it still would be useful to see the theorems compared with in practice behavior.\n\nWe assume that the reviewer would like to see the theoretical classification accuracy bound for Theorems 4.1 and 4.2 in the same plot of our simulated synthetic experiments. Please, let us know if this is not the correct interpretation of your question. We would be happy to update our reply during the discussion period. In case, that's the correct interpretation of your question we provide updated plots with the theoretical bound for partial recovery, Theorem 4.1, in the response pdf. We would like to note that the exact classification thresholds from Theorem 4.2 are demonstrated with vertical lines in the current plots in Figures 1 and 2 of our paper.\n\n    \n> Question 2: What is CSBM? I know SBM but what makes it C?\n    \nContext is referred to in the literature as the features of the nodes. \\textcolor{red}{Are there any historical reasons that the features are called context here? Cite the original CSBM paper and point to Section 3.1}\n\n> Question 3: Have you considered scenarios where the data has clear block structure, but it does not 100\\% overlap with the true labels? will it cause undesirable biases? can those be quantified?\n\nThis is a very good question. We have thought about this a little bit. If there is a mismatch between the community structure in the graph and classes of the feature vectors of the nodes, then the mismatched vertices will probably be pulled to the opposite means by the convolutions. This means that there will be more misclassified nodes in the partial classification result, and the threshold of exact classification will be worse. We can probably still analyze this case by splitting the feature vector into the part corresponding to correctly matched vertices and the part corresponding to mismatched vertices and analyzing the error from each part separately. If the mismatch is small, we should be able to get reasonable partial classification results. This could be an interesting avenue for future work.\n\n> Question 4: Actually, one interpretation of this is that the adjacency spectrum somewhat mirrors the Laplacian spectrum, but in reverse order. So, the dominant eigenvector corresponds to the null space of L, and the second one is the one associated with the mixing parameter in L. So, in that sense, it makes sense why focusing on that eigenspace gives better performance. I would be interested in hearing the authors' views on this.\n\nWe agree with this interpretation, and that's exactly what happens in our analysis for CSBM. We will mention the relation to the Laplacian more explicitly in our revision.\n\nFinal remarks\n\nOnce again, we would like to express our gratitude for the thorough examination and feedback of our work. We believe that it certainly helped us to improve our manuscript. If the reviewer has more actionable suggestions to further improve our work, please kindly let us know. We would be happy to address any further questions. We hope the clarifications and additional comments are sufficient for them to consider raising their score.", "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": "", "extra_scores": {}}, {"review_id": "LgGljtTiJ2", "reviewer": "Reviewer_kcVu", "summary": "This paper studies the effects of removing the top eigenvector of the adjacency matrix used for aggregation in graph convolutions. For the contextual stochastic block model (CSBM), this is theoretically shown to be beneficial. The authors provide several theoretical statements describing misclassification ratios and chances and chances of achieving linear separation. Experiments confirm the superiority of removing the smooth eigenvector for the CSBM.", "questions": "* What are the benefits of this analysis against existing insights that the signal corresponding to the top eigenvector of a matrix gets amplified the most and dominates representations?\n* What are potential practical implications that can now be developed?\n* l. 332: Why is the O-notation used for $p=O(log^3 n/n)$?", "limitations": "Limitations are not explicitly presented.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "* The background, literature review, and preliminaries are nicely presented.\n* The ideas behind the proofs are interesting.\n* The conducted experiments confirm the claimed benefits of removing the top eigenvector for CSBM.", "weaknesses": "* The structure of the paper is confusing. In Section 4, two Theorems are provided without proofs. Proofs are also not provided in the Appendix. Then, there is a proof sketch for the Theorems in Section 6.\n* A clear focus would help the accessibility of this work. It would suffice to consider either $\\hat{A}$ or $\\tilde{A}$ and Theorem 4.1 or Theorem 4.2 while providing more details for the selected case.\n* Theoretical statements and their implications are hard to understand. Clearly stating all symbols and providing additional details would help. \n* The implications of this work are not clear to me. We know that $M^kx$ gets dominated by the top eigenvector of M with rate $\\lambda_2/\\lambda_1$. Setting the largest eigenvalue to zero, results in dominance of the second eigenvector. As pointed out in this work, this eigenvector corresponds to sparse and balanced bipartitions. This analysis seems like a complicated way to come to the same conclusion.\n* The practical usage of removing the top eigenvector seems very limited, as one dominating signal is exchanged for another. This is confirmed in Figure 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We answer the concerns below.\n\n> The structure of the paper is confusing. Two Theorems are provided without proofs. Proofs are also not in the Appendix.\n\nWe prove both our theorems rigorously in the appendix. For the proof of Theorem 4.1, we refer to Appendix C (Title: Proofs in Section 6). Please check line 611, where we start by proving the essential lemmas, followed by the proof of Theorem 4.1 in line 662. For Theorem 4.2, the sketch is in section 7 (line 277) and the full proof is in Appendix D titled `Proofs in Section 7 (line 676)`. The explicit proof of Theorem 4.2 is given in `line 760`. We will point to the proofs explicitly with hyperlinks in the main paper in our revision.\n\n> It would suffice to consider either $\\hat{A}$ or $\\tilde{A}$ and Theorem 4.1 or Theorem 4.2.\n\nThank you for the suggestion. We believe that both Theorem 4.1 and 4.2 are important. In community detection results for the SBM, it is customary to study both exact and partial recovery results (see \\[E. Abbe, Community Detection and Stochastic Block Models, JMLR 2018\\]). In our paper, we provide answers to such customary questions for node classification for the CSBM, where we also have node feature information in addition to the graph.\n\n> Theoretical statements and their implications are hard to understand. Clearly stating all symbols and providing additional details would help.\n\nWe provide an extensive discussion on the theorems and their meaning in terms of the number of convolutions and the SNR in the data (see lines 170 to 188 for Theorem 4.1, and lines 193 to 202 for Theorem 4.2). It would help if the reviewer could point us to the part that is hard to understand so we can explain it better and modify our paper accordingly. It would be helpful if the reviewer could tell us which symbols and additional details are required.\n    \n> The implications of this work are not clear to me. Setting the largest eigenvalue to zero results in dominance of the 2nd eigenvector, corresponding to sparse and balanced bipartitions. This analysis seems like a complicated way to come to the same conclusion.\n    \nWe respectfully disagree with the reviewer's perspective. There is a large body of literature in the GNN community where people care about precisely quantifying the classification results and non-asymptotic behavior of these models. For example, \\[ref line 443, Keriven: Not Too Little, Not Too Much\\] studied classification guarantees of graph convolution in simplified statistical models and showed improved classification guarantees compared to no convolutions. However, the analysis was limited to at most $2$ convolutions. In \\[ref line 494, Wu et al.\\] the authors studied the non-asymptotic behavior of graph convolutions in the CSBM and precisely characterized how many convolutions it takes before the oversmoothing effect overtakes the aggregating effect of graph convolution. However, the paper does not give classification guarantees of the model. In our paper, we analyze the corrected graph convolution in the CSBM, which, in this model, mitigates the oversmoothing effect. As a result, we can give partial and exact recovery guarantees for up to $O(\\log{n})$ convolutions, which has not been done in all the aforementioned works. We also precisely quantify the number of convolutions it takes to obtain our recovery results. We also note that the proof of our exact recovery result (Theorem 4.2) requires much more sophisticated techniques than simply analyzing the rate of convergence of the eigenvalues to $\\lambda_1$. This is because we have to bound the distance $\\|A^kx - s\\|_\\infty$ instead of $\\|A^kx - s\\|_2$, which means simple spectral analysis is insufficient. To overcome this, we used careful analysis of the moment of each entry of our convolved feature vector.\n\nFinally, we argue that the intuition behind our analysis being simple is a good thing because it makes it more accessible to the general audience. Our analysis formalizes this intuition that most people can interpret into concrete recovery guarantees whereas previous studies did not.\n    \n\n    \n> The practical usage of removing the top eigenvector seems very limited, as one dominating signal is exchanged for another. This is confirmed in Fig 3.\n\nThe eigenvector which we remove has no information about the class membership. The second eigenvector which dominates after removing the first has useful classification information. Therefore, simply stating that exchanging one signal for another is not useful, is not correct. We prove this in our Theorems 4.1 and 4.2. Fig 3 does not confirm the reviewer's statement. In fact, Fig 3 shows that removing the top eigenvector allows the model to have better performance as the number of convolutions increases. As we point out in lines 348 to 350, the idea of removing the top eigenvector is helpful in practice and has been implemented in widely cited studies (see \\[ref line 512, Zhao and Akoglu\\]).\n\n> What are the benefits of this analysis against existing insights that the signal corresponding to the top eigenvector of a matrix gets amplified the most?\n\nWe have answered this question in detail in our reply about Weakness 4 above.\n\n> What are potential practical implications?\n\nThis is similar to weakness 5 so see the response there. To re-iterate, based on our analysis, we could recommend removing the top eigenvector from the convolution matrix. As we point out in lines 348 to 350, this is helpful in practice and has been implemented in widely cited studies (see \\[ref line 512, Zhao and Akoglu\\]).\n    \n> l. 332: Why is the O-notation used?\n\nWe will update the precise value of $p$ in the experiments. We used $O$ notation to denote that there is a constant factor associated with the value.\n\nIf the reviewer has more actionable suggestions to further improve our work, please kindly let us know. We would be happy to address any further questions. We hope the clarifications are sufficient for them to consider raising their score.", "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": "", "extra_scores": {}}]

Author rebuttal:
$$
   \def\norm#1{{\|#1\|}}
   \def\E{{\mathbb{E}}}
$$

## Multi-class Analysis
We define the L-Block CSBM with parameters $p,q,L,n,m$. We have $n$ nodes and $L$ classes, $\mathcal{C}_1,...\mathcal{C}_L$, of size $n/L$. For each node $i$, we have a feature vector $x_i\in \mathbb{R}^m$ with distribution $N(\mu_i, \sigma^2 I_m)$. For each class $\mathcal{C}_l$, $l\in [L]$, we let $c_l \in \mathbb{R}^m$ be the class mean, and for $i\in \mathcal{C}_l$, $\mu_i = c_l$. We define

$$\tilde{A} = \frac{1}{d}A - \frac1n\mathbf{1}\mathbf{1}^\top,$$
where $d = \frac{np}{L} + \frac{nq(L-1)}{L}$ is the expected degree of each vertex. Note $d$ can be estimated accurately with high probability by degree concentration (see proposition 5.2). We introduce useful notation below.

- **Graph Signal:** $\lambda := \frac{(p-q)n}{dL}$ is the strength of the signal from the graph. 
- **Graph Noise:** $\delta := C(\frac{1}{d}(\sqrt{np(1-p)/L} +\sqrt{nq(1-q)}))$ for some constant $C$. $\delta$ is an upper bound on the graph noise.
- Let $U:=\E[X]$ be the matrix whose $i^{th}$ row is $\mu_i$. We will use $\norm{U}_F^2$ to denote its Frobenius norm. We also assume our features are centered on expectation so that $U^\top \mathbf{1} = 0$. This is not restrictive since it can be satisfied by applying a linear shift to the features.
- Let $\Delta = \min_{i,j\in [n]}\norm{\mu_i-\mu_j}$ be the minimum distance between the centers.

### Theorem 1

Given the CSBM with parameters, $p,q,L,n,m$, suppose $\min(p,q) \geq \Omega(\frac{\log^{2}n}{n})$ and $|\lambda| > 4k\delta$. Let $X^{(k)} = \frac{1}{\lambda^k}A^{(k)}X$ be the feature matrix after $k$ rounds of convolutions with scalaing factor $1/\lambda^k$. Let $x^{(k)}_i$ be the $i^{th}$ row of the matrix $X^{(k)}$. Then with probability $1-n^{-\Omega(1)}$, at least $n - n_e$ nodes, $i$, satisfy $\norm{x^{(k)}_i - \mu_i}< \Delta/2$ where 
$$n_e =  O\Big((k \delta/|\lambda|)^2\frac{\norm{U}_F^2}{\Delta^2} + (L + n(\delta/|\lambda|)^{2k})\frac{\sigma^2m\log{n}}{\Delta^2}\Big).$$

In particular, the quadratic classifer $x\mapsto \text{softmax}(\norm{x-c_l}^2)_{l=1}^L$ will correctly classify at least $n-n_e$ points.

---

See the attached PDF for examples of our bound in specific setting as well as experimental results. 

The following lemma explains how the expressions for graph signal and noise are derived.

### Lemma 2
The convolution matrix $\tilde{A}$ can be decomposed as $\tilde{A} = M + R'$ where:

- $M = \E[\tilde{A}]$ has rank $L-1$, with $L-1$ eigenvalues equalled to $\frac{(p-q)n}{dL} = \lambda$. Also, $MU = \lambda U$
- $R'$ is a random matrix such that with probability $\ge 1-n^{-\Omega(1)}$, $\norm{R'} \leq O(\frac{1}{d}(\sqrt{np(1-p)/L} + \sqrt{nq(1-q)})) = \delta$

---

The proof is standard, so we only give a sketch due to space limitations. We are happy to give the full proof in the discussion period. For item 1, we note $\E[A]$ is rank $L$ and has top eigenvector $\mathbf{1}$ with eigenvalue $d$. Its second eigenvalue is $\lambda$ with multiplicity $L-1$ and the eigenspace is characterized by the set vectors orthogonal to $\mathbf{1}$ and constant on each class. Since each class has one center and $U^\top \mathbf{1} = 0$, the columns of $U$ are in the second eigenspace. To obtain item 2, we decompose $A-E[A]$ into entries with probability $p$ and entries with probability $q$. Then we bound them separately using matrix concentration in theorem A.4 of the paper.

We will also need to bound the operator norm distance between the $k^{th}$ convolution and $M^k$
### Lemma 3

Suppose $|\lambda| > 4k\delta$. Then with high probability, we have
$$\norm{\frac{1}{\lambda^k}(\tilde{A}^k - M^k)} \leq 2k\delta/|\lambda|.$$

#### Proof
By Lemma 2, we have 
$$\tilde{A}^k = (M+R')^k = M^k + \sum_{l=1}^k\sum_{b\in {[k]\choose l}}\prod_{i=1}^k M^{1-b(i)}R'^{b(i)},$$
where the inner sum is over bit-strings $b$ of length $k$ with exactly $l$ $1$'s and $k-l$ $0$'s. Note that $\norm{M} = |\lambda|$ and $\norm{R'}\leq \delta$ with high probability. Using the fact that $\norm{AB}\leq \norm{A}\norm{B}$ and triangle inequality, we have
$$\norm{\frac{1}{\lambda^k}((M+R')^k - M^k)} \leq \frac{1}{|\lambda|^k}\sum_{l=1}^k{k\choose l}\norm{M}^{k-l}\norm{R'}^{l} \leq \sum_{l=1}^k{k\choose l}(\frac{\delta}{|\lambda|})^{l} = (1+\frac{\delta}{|\lambda|})^{k}-1$$
Our assumption that $|\lambda| > 4\delta k$ implies the RHS is at most $2k\delta/|\lambda|$.

---

Now we are ready to prove our main theorem.
#### Proof of Theorem 1
We decompose our data as $X = U + G$, where $G$ is a Gaussian matrix with i.i.d $N(0, \sigma^2)$ entries. We will decompose our error into error from the graph and error from the feature noise. Recall that we take our scaling factor to be $1/\lambda^k$. We have
$$\norm{X^{(k)}-U}_F^2 = \norm{\frac{1}{\lambda^k}\tilde{A}^k(U + G)-U}_F^2 \leq 2\norm{\frac{1}{\lambda^k}\tilde{A}^kU - U}_F^2 + 2\norm{\frac{1}{\lambda^k}\tilde{A}^k G}_F^2.$$

By Lemma 2, we have $MU = \lambda U$. Thus, we have
$$\norm{\frac{1}{\lambda^k}\tilde{A}^kU - U}_F^2 = \norm{\frac{1}{\lambda^k}(\tilde{A}^k - M^k)U}_F^2 \leq \norm{\frac{1}{\lambda^k}(\tilde{A}^k - M^k)}^2\norm{U}_F^2 \leq (k\delta/|\lambda|)^2\norm{U}_F^2,$$
where the inequality follows from Lemma 3. By standard Gaussian norm concentration for $G$ (see theorem A.1 of paper), we have high probability
$$\norm{\frac{1}{\lambda^k}\tilde{A}^k G}_F^2 \leq \frac{1}{\lambda^{2k}}Tr(\tilde{A}^{2k})\sigma^2m\log{n}$$
Since adding $R'$ to $M$ preturbs its eigenvalues by at most $\delta$ (see theorem A.1 in the paper), we have
$$\frac{1}{\lambda^{2k}}Tr(\tilde{A}^{2k}) \leq (1 + \delta/|\lambda|)^{2k}(L-1) + n(\delta/|\lambda|)^{2k}$$

Note that $|\lambda| > 4\delta k$ implies $(1 + \delta/|\lambda|)^{2k} \leq 1$. Now let $n_e$ be the number of points $i$ such that $\norm{x^{(k)}_i - \mu_i} \geq \Delta/2$. Then we have
$$n_e\Delta^2\leq  4\norm{X^{(k)}-U}_F^2 \leq O((k\delta/|\lambda|)^2\norm{U}_F^2 + (L + n(\delta/|\lambda|)^{2k})m\sigma^2\log{n}).$$

Meta-review: This paper provides a spectral analysis showing that, for data generated by stochastic block models, the oversmoothing phenomenon can be alleviated by subtracting the projection upon the leading eigenvector from the shift operator. The new leading eigenvector then becomes the second eigenvector, which contains more information about the structure of the graph than the original leading eigenvector, related to properties of connectedness of the graph, i.e. information about sparse bipartitions. This idea leads to a practical approach for correcting the shift operator in standard GNNs, and to theoretical guarantees on node classification on 2-class stochastic block models. The improvement in classification is demonstrated on synthetic data and on citation networks, where GCN with the corrected shift operator outperforms vanilla GCN. While the experimental results are limited, they are sufficient for a paper with a theoretical contribution. Overall, this is a solid theoretical work with sufficient novelty.

The authors are asked to incorporate the reviewer comments for the camera ready version.
Decision: Accept (poster)