Analysis of Corrected Graph Convolutions

Authors: robert  wang
aseem  baranwal
kimon  fontoulakis
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 19:19:52

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.

Main paper: 
 introduction: 
 Graphs naturally represent complex relational information found in a plethora of applications such as social analysis [Backstrom and Leskovec, 2011] , recommendation systems [Ying et al., 2018 , Borisyuk et al., 2024] , computer vision [Monti et al., 2017] , materials science and chemistry [Reiser et al., 2022] , statistical physics [Battaglia et al., 2016 , Bapst et al., 2020] , financial forensics [Zhang et al., 2017 , Weber et al., 2019] and traffic prediction in Google Maps [Derrow-Pinion 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 on graphs is the graph convolution operation. It has been shown empirically [Defferrard et al., 2016 , Kipf and Welling, 2017 , Gasteiger et al., 2019 , Rossi et al., 2020] that using graph convolutions to 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 et al., 2020 , Keriven, 2022 , Wu et al., 2023] , an issue known as oversmoothing. Several solutions have been proposed for this problem, we refer the reader to the survey of Rusch et al. [2023] .In this paper we provide a rigorous spectral analysis, based on the contextual stochastic block model [Deshpande et al., 2018] , to show that the oversmoothing phenomenon can be 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 [2020] , Rusch et al. [2023] (PairNorm). However, our method explicitly uses the principal eigenvector. We provide below some intuition about why excluding the principal eigenvector helps to alleviate over-smoothing.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 D -1 A or D -1/2 AD -1/2 [Kipf and Welling, 2017] . Suppose our graph is d-regular, meaning that each node has exactly d neighbors. In this case, both graph convolutions reduce to 1 d A. The top eigenvector of A is 1 with eigenvalue d, where 1 is the vector of all ones. This means that lim k→∞ 1d k A k = 1n 11 ⊤ , 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, we should expect, as verified by most real-world and synthetic experiments, that many rounds of the convolution x → 1 d Ax will lead to a large learning error. However, if we instead perform convolution with the corrected matrix Ã :=1 d A -1 n 11 ⊤ ,then the convergent behavior of x → Ãk x would be equivalent to projecting x 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 a focus on linear, binary classification. Our results are stated in terms of the following corrected convolution matrices:EQUATIONwhere d := 2|E|/n 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 Ã is (up to a scalar multiple) its unnormalized counterpart. Briefly, we demonstrate that when the graph is 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 a similar analysis in [Wu et al., 2023] for vanilla graph convolutions (without correction), we show that classification accuracy does not become worse as the number of convolutions increases.In this work, we provide, to our knowledge, the first theoretical guarantees on partial and exact classification after k rounds of graph convolutions in the contextual stochastic block model. Our main result is to show that each graph convolution with the corrected matrix reduces the classification error by a 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 q be the intra-and inter-class edge probabilities with γ(p, q) = |p -q|/(p + 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 p + q ≥ Ω( log 2 n n ) and γ ≥ Ω( 1 √ d ), each convolution with Ã reduces classification error by a factor of about 1 γ 2 d until the fraction of errors is O( 1 γ 2 d )• If p + q ≥ Ω( log 2 n n ) and γ ≥ Ω( log n d ), each convolution with Â reduces classification error by a factor of about log n γ 2 d until the fraction of errors is O( log n γ 2 d )• If p + q ≥ Ω( log 3 n n ), γ ≥ Ω(k log n d ) and the input features has signal-to-noise ratio at least Ω( log n n ), the data is linearly separable after k rounds of convolutions with Ã.To obtain our partial classification results, we use spectral analysis to bound the mean-squared-error between the convolved features and the true signal. For exact classification, we prove a concentration inequality on the total amount of message received by a vertex through "incorrect paths" of length k after k rounds of convolution through a 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 is 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, Ã, reduces classification error by a constant fraction each round, until a point of saturation where no further improvement is made. 
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, Scarselli et al. [2009] , Cheng et al. [2011] , Gilbert et al. [2012] , Dang and Viennet [2012] , Günnemann et al. [2013] , Yang et al. [2013] , Hamilton et al. [2017] , Jin et al. [2019] , Mehta et al. [2019] , Chien et al. [2022] , Yan et al. [2021] . These studies have underscored the empirical advantages of incorporating graph structures when available.The literature also addresses the expressive capacity [Lu et al., 2017 , Balcilar et al., 2021 ] and generalization potential [Maskey et al., 2022] of Graph Neural Networks (GNNs), including challenges like oversmoothing [Keriven, 2022 , Xu et al., 2021 , Oono and Suzuki, 2020 , Li et al., 2018 , Rusch et al., 2023] . In our paper, we ground our work on the contextual stochastic block model [Deshpande 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, information-theoretic, 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 classifying a significant portion of nodes from this model, given linear sample complexity and large but bounded degree. Additionally, Hou et al. [2020] introduces graph smoothness metrics to quantify the utility of graphical information. Further developments in Chien et al. [2021 Chien et al. [ , 2022]] , Baranwal et al. [2021 Baranwal et al. [ , 2023a] ] extend the application of CSBM, establishing exact classification thresholds for graph convolutions in multi-layer networks, accompanied by generalization guarantees.A 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-passing 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 fraction of recoverable nodes is influenced by the signal-to-noise ratio in the node features and the 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 Zhao 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 it improves performance exponentially up to saturation, after which more convolutions do not improve nor degrade performance. On a technical level, the previous work only analyzes the distribution of a single node's feature values after convolution and does not take into account correlations between nodes. In our work, we use spectral analysis of higher powers of the convolution matrix, which takes into account correlations between nodes to 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] .In this section, we will prove our main technical lemma, Lemma D.5. By Corollary D.4, it suffices to control the term |e ⊤ u R k s| in order to control |e ⊤ u R ′k s|. 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 2t th moment of this random variable E[(e ⊤ u R k s) 2t ] for an appropriately chosen t. We now state our main result for this section as follows: Proposition D.6. Suppose R is an n × n symmetric random matrix where for each 1 ≤ i ≤ j, R i,j = 1 -p i,j with probability p i,j and -p i,j with probability 1 -p i,j and are independent. Let p = max i,j p i,j , and suppose p ≥ Ω( log 3 n n ). Then we havePr |e ⊤ u R k s| > 1 √ n (C np log n) k ≤ exp(-Ω(C log n))Proof. The term e ⊤ u R k s can be written as the sum over all walks of length k originating from u. Let W u,k denote the set of all walks of length k originating at u. For brevity, we will use W to denote W u,k . For each w ∈ W, let w(j) be the j th vertex in the walk. Note that w(0) = u always. Then we havee ⊤ u R k s = w∈W k j=1 R w(j-1),w(j) s(w(k)) Thus, we have E[(e ⊤ u R k s) 2t ] = w1,w2...w2t∈W E[ 2t i=1 k j=1 R wi(j-1),wi(j) s(w i (k))] ≤ w1,w2...w2t∈W |E[ 2t i=1 k j=1 R wi(j-1),wi(j) ]| • 2t i=1 |s(w i (k))| = 1 n t w1,w2...w2t∈W |E[ 2t i=1 k j=1 R wi(j-1),wi(j) ]|Where the last equality follows from the fact that |s(v)| = 1/ √ n for all v ∈ V . Now, for each ⃗ w = (w 1 , ...w 2t ) ∈ W 2t and edge h ∈ n × n, let # ⃗ w (h) be the number of times the edge h occurs in the graph w 1 ∪ w 2 ∪, ...w 2t . In other words, for h = {a, b}, # ⃗ w (h) is the number of times the variable R a,b occurs in the product 2t i=1 k j=1 R wi(j-1),wi(j) . We will also let | ⃗ w| denote the number of unique edges in the graph formed by the union of these 2t walks. For example, if ⃗ w consist of the walks (1, 2, 3), and (1, 2, 4 ), then we have# ⃗ w (1, 2) = 2, # ⃗ w (2, 3) = 1, # ⃗ w (2, 4) = 1, and | ⃗ w| = 3. Using this notation, we have w1,w2...w2t∈W |E[ 2t i=1 k j=1 R wi(j-1),wi(j) ]| = ⃗ w∈W 2t h∈[n]×[n] |E[R # ⃗ w (h) h ]| Now we note that each R h has E[R h ] = 0 and for all k ≥ 2, we have |E[R k h ]| ≤ E[|R k h |] = p h (1 -p h ) k + p k h (1 -p h ) = p h ((1 -p h ) k + p k-1 h (1 -p h )) ≤ p h ≤ p Thus, the term h∈[n]×[n] |E[R # ⃗ w (h) h]| is only nonzero if in the union of the edges in the walks w 1 , ...w 2t , each edge is counted at least twice, and if it is non-zero, then it is the product of at most | ⃗ w| terms of value at most p. We now let W 2t pair 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, 2, 3), (1, 2, 3)} would be valid but {(1, 2, 3), (1, 2, 4)} would not be valid. Now we have⃗ w∈W 2t h∈[n]×[n] |E[R # ⃗ w (h) h ]| ≤ w∈W 2t pair p | ⃗ w| = tk ℓ=1 p ℓ |{ ⃗ w ∈ W 2t pair , | ⃗ w| = ℓ}|Now, what we have left is a counting problem. We need to count the number of valid sets of walks whose union has exactly ℓ distinct edges. We note that ℓ can be at most tk 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 p ≥ log 3 n n and t ≤ log n 2k . Then we have:|{ ⃗ w ∈ W 2t pair , | ⃗ w| = ℓ}| ≤ 2tk 2ℓ (2ℓ -1)!! • ℓ 2kt-2ℓ (n) ℓThe notation of n!! denotes n • n -2 • n -4...1. Given this upper bound on the number of valid sets of walks, we are ready to give our final bound. We will let t = C1 log n 2k for large enough constant C 1 . Note that the only constraint on t is that it is a positive integer, and this is feasible as long as k = O(log n). Since p ≥ log 3 n n , we have np ≥ (tk/C 1 ) 3 . We will make the substitution b = tk -ℓ. Then we have tk ℓ=1p ℓ |{ ⃗ w ∈ W 2t pair , | ⃗ w| = ℓ}| ≤ tk-1 b=0 (np) tk-b (tk -b) 2b (2tk -2b -1)!! 2tk 2b ≤ tk-1 b=0 (np) tk-b (2tk) tk-b (2tk) 2b (2tk) 2b e 2b (2b) 2b ≤ (np) tk (2tk) tk tk-1 b=0 (2tk) 3b e 2b (2b)!(np) b ≤ (np) tk (2tk) tk b≥0 (C 1 e 2 ) b (2b)! ≤ O((np) tk (2tk) tk )In the second line, we used the fact that (2tk -2b -1)!! is the product of tk -b terms of value at most 2tk as well as the standard upper bound of 2tk 2b ≤ (2tk) 2b e 2b (2b) 2b , the second last bound follows Vertex Assignment Procedure• Pick an arbitrary partitioning of the edges into ℓ groups without singletons• For i = 1 to 2t:-For j = 1 to k * If the edge (w i (j -1), w i (j)) is not part of a group which contains an already assigned edge, then pick a new vertex for w i (j). * Else, let (w i ′ (j ′ -1), w i ′ (j ′ )) be an edge in the same group as (w i (j -1), w i (j)) such that both w i ′ (j ′ -1) and w i ′ (j ′ ) are already assigned. Then assign w i (j) such that {w i (j -1), w i (j)} = {w i ′ (j ′ -1), w i ′ (j ′ )}. If no such assignment is possible, then the procedure fails.To see that every possible valid set of walks can be outputted by this procedure, if we are given some ⃗ w = (w 1 , ...w 2t ) ∈ W 2t pair , 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 a new edge corresponds to 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 is 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, we see that in first case of the inner for-loop, there are at most n possible assignments for the vertex w i (j). In the second step, there is only one possible assignment if the procedure doesn't fail. Since we encounter the first case of the for-loop at most ℓ times, the total number of vertex assignments given a fixed partitioning of edges is at most n ℓ . Finally, this gives us the desired bound:|{ ⃗ w ∈ W 2t pair , | ⃗ w| = ℓ}| ≤ 2tk 2ℓ (2ℓ -1)!! • ℓ 2kt-2ℓ (n) ℓ 
preliminaries and model description: 
 Throughout this paper, we use 1 to denote the all-ones vector and e i to denote the i th standard basis vector in R n . Given a vector x ∈ R n , we use ∥x∥ to denote its Euclidean norm n i=1 x(i) 2 . We use ∥x∥ ∞ to denote its infinity norm, max n i=1 |x(i)|. For a matrix M ∈ R n , we use ∥M ∥ to denote its operator norm, max x̸ =0,∥x∥=1 ∥M x∥. We use ∥M ∥ F = i,j M 2 i,j to denote its Frobenius norm. We also make routine use of the spectral theorem, which says that if M is a n × n symmetric matrix, then it can be diagonalized with n orthogonal eigenvectors and real eigenvalues. In particular, there exist λ 1 , λ 2 , ...λ n ∈ R and orthonormal vectors w 1 , w 2 , ...w n ∈ R n such that M = n i=1 λ i w i w ⊤ i . Note that when M is symmetric, ∥M ∥ = max i |λ i | = max x:∥x∥=1 |x ⊤ M x|.Finally, we use the N (µ, Σ) to a Gaussian distribution with mean µ and covariance matrix Σ. For one-dimensional Gaussians, we use N (µ, σ 2 ). For X ∼ N (µ, σ 2 ), we will frequently use the Gaussian tail bound:Pr [|X -µ| > tσ] ≤ exp(-t 22 ).In this section, we formally describe the contextual stochastic block model introduced by [Deshpande et al., 2018] . Our model is defined by parameters n, m ∈ N, p, q ∈ [0, 1], µ, ν, ∈ R m and σ ∈ R + In the model, we are given a random undirected graph, G = (V, E), 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 i, j ∈ S and i, j ∈ T , the edge (i, j) is in E independently with probability p while for each pair i ∈ S and j ∈ T , the edge (i, j) is in E with probability q. In addition to the graph, we are also given a feature matrix X ∈ R n×m drawn from a Gaussian mixture model with two centers µ and ν.For each i ∈ V , we let g i ∼ N (0, σ 2 I m ) be an i.i.d. Gaussian noise vector. Now let (x i ) i∈n be the rows of X. For i ∈ S, we have x i = µ + g i and for each i ∈ T , we havex i = ν + g i .In the multi-class setting, our nodes are partitioned into L classes, C 1 , ...C L , of size n/L. The inter-class edge probability is p and intra-class edge probability is q. We assume the features are generated by a Gaussian mixture with L centers c 1 , ...c L ∈ R m . If node i is in class l, then we observe its feature vector as x j = c l + g i . In addition, we will let µ i := c l , for i ∈ C l , denote the center for vertex i.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes]• It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: We have read the NeurIPS Code of Ethics. Our work is theoretical and we don'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 we 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 the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
results and interpretation: 
 In our analysis, there are two types of objectives. In the exact classification objective, the aim is to exactly recover S and T with probability 1 -o(1). In the partial classification, or "detection" problem, the goal is to correctly classify 1 -o(1) fraction of vertices correctly with probability 1 -o(1). We begin by stating our results for the partial classification regime. For ease of notation, we will assume p > q from this point forward. We show in Appendix B.1 that this assumption is made without loss of generality. Theorem 4.1. Suppose we are given a 2-block m-dimensional CSBM with parameters n, p > q, µ, ν, σ satisfying γ(p, q) := p-q p+q ≥ Ω1 np and p ≥ Ω log 2 n n. There exists a linear classifier such that after k rounds of convolution with Ã, will, with probability at least1 -1 2 exp(-Ω n∥µ-ν∥ 2 σ 2), misclassify at mostO 1 γ 2 p + C γ √ np 2k σ 2 ∥µ -ν∥ 2 n log nvertices, where C is an absolute constant. Furthermore, if γ ≥ Ω( log n np ) then with probability at least 1 -1 2 exp(-Ω n∥µ-ν∥ 2 σ 2), the same linear classifier after k rounds of convolution with Â will misclassify at mostO log n γ 2 p + C log n γ √ np 2k σ 2 ∥µ -ν∥ 2 n log n vertices.Now we take a 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/(γ 2 np). This term is small if γ 2 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 a constant means that we need the signal from the graph to be sufficiently strong. Now, if we examine our misclassification error bound, and let ρ = C/(γ 2 np) where C is a sufficiently large constant, then we see that the fraction of misclassified vertices is at most ρ+ρ k σ 2 log n/ ∥µ -ν∥ 2 . Our assumption on the parameters ensures that ρ < 1. Note that only the second term depends on k, and the feature'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 = log 1/ρ σ 2 log n/(ρ ∥µ -ν∥2 ) 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. If σ/ ∥µ -ν∥ is constant, we will always reach our optimal error bound of O(ρ) when k = O(log log n). Moreover, if γ = Ω(1), as was assumed in Baranwal et al. [2021] , then we will have 1/ρ ≥ Ω(np). This means even when σ/ ∥µ -ν∥ ≈ n/ log n, we will reach optimality in constant number of convolutions with high probability if the graph is moderately dense. For example, if p = 1/ √ n, then we only need 3 convolutions and if p = Ω(1), then we only need 2. On the other hand, if γ is on the order of Θ(1/ √ np), then in the worst case, we may need log n convolutions to reach our optimal bound. Next, we state our results for exact classification. Theorem 4.2. Suppose we are given a 2-block m-dimensional CSBM with parameters n, p > q, µ, ν, σ satisfying γ(p, q) ≥ Ω k log n np and p ≥ log 3 n n . Then after k = O(log n) rounds of graph convolution with Ã, our data is linearly separable with probability 1 -n -Ω(1) if∥µ -ν∥ σ ≥ Ω max log n n , C γ √ np k log nwhere C is an absolute constant.Here, we bound the minimum signal-to-noise ratio required for exact classification as a function of p, q, n and k. Just like the partial classification result, our function has a term that decreases exponentially with k and a term independent of k. The rate of decrease for the dependent term is proportional to 1/(γ √ np), or √ ρ. We see once again that with more convolutions, the requirement on the feature signal-to-noise ratio for exact classification becomes exponentially weaker. Moreover, since we assumed that γ ≥ Ω(k log n/(np)), as long as ∥µ -ν∥ ≥ Ω(σ log n/n), the data becomes linearly separable after k = O(log n/log 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 γ = Ω(1) and p = Ω(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-normalized adjacency matrix, Ã. Similar bounds should hold for Â based on our simulation results, but we leave this for future work.Both Theorem 4.1 and Theorem 4.2 require a lower bound of γ ≥ ω(1/ √ np), and this is to ensure that the signal from the graph is strong enough so that a convolution does not destroy the signal from the data. Also, implicit in the probability bound of Theorem 4.1 and in Theorem 4.2, is the assumption that our signal-to-noise ratio, ∥µ -ν∥ /σ, is at least ω(1/ √ n) so the feature noise does not completely drown out the signal. Our lower-bound assumption on p 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 = O(log n). 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 k ≥ log n. Finally, we note that the case p > q corresponds to a homophilous graph, and the case p < q corresponds to a heterophilous graph (see Luan et al. [2021] , Ma et al. [2022] for more). For binary classification, it has been shown [Baranwal et al., 2023a ] that one can assume p > q without loss of generality and make corresponding adjustments in the classifier.As such, we assume that p > q. For more detail regarding this assumption, see Appendix B.1.5 One-Dimensional CSBMIn Baranwal et al. [2021] , the authors showed that analyzing the linear classifier for the m-dimensional CSBM reduces to analyzing the 1-dimensional model. We say that a CSBM is one-dimensional and centered with parameters n, p, q, σ if it has one-dimensional features and means 1/ √ n and -1/ √ n. That is, we have one feature vector x ∈ R n given by x = s + g, where g ∼ N (0, σ 2 I n ) and s(i) = 1/ √ n for i ∈ S and -1/ √ n for i ∈ T . We will refer to s as our signal vector and for ease of notation, we normalize it so that it 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 1-dimensional centered CSBM (proof in Appendix B.1). Thus, in the proofs of our main theorems, we will analyze the 1-dimensional case before applying Lemma 5.1. Lemma 5.1. Given an m-dimensional 2-block CSBM , there exist w ∈ R m and b ∈ R n such that Xw + b = s + g where for each vertex i, g i is i.i.d. N (0, σ ′2 ) with σ ′ = 4σ √ n∥µ-ν∥ .In the 1-dimensional model, it is clear how our signal s is present in our features. Our convolution matrix also captures the signal because it can be viewed as a perturbation of the matrix ss ⊤ . This is especially evident with the un-normalized convolution matrix Ã, which satisfies the followingEQUATIONwhere η := (p -q)n/(2d) is the signal strength, d ′ := ((p + q)n/2 -d)/(nd) is the average degree deviation, and R is the "edge-deviation" matrix, where R i,j = A i,j -E[A i,j ]. 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 γss ⊤ . In fact, if we show degree concentration for all vertices, then we can show that Â also behaves like Ã. We state these concentration results below.Proposition 5.2. Assume that p = Ω( log 2 n n ), and let γ = p-q p+q . With probability 1 -n -Ω(1) , we have the following concentration results1. |d ′ | ≤ O(1/n 1.5 ), which implies that η ∈ γ(1 ± o(1)). 2. ∥R∥ ≤ O( √ np) 3. Ã -γss ⊤ ≤ O( 1 √ np ) and Â -γss ⊤ ≤ O( log n np )These concentration properties are crucial for spectral analysis. Details are given in Appendix B.1. 
partial classification: 
 In this section, we give a sketch of the proof of our partial classification result, Theorem 4.1. The full proofs can be found in Appendix C. We will show that partial classification can be achieved if the 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 ∈ { Ã, Â}. Proposition 6.1. Given a centered 1-dimensional 2 block CSBM with parameters n, p > q, σ and γ(p, q) = p-q p+q , suppose our convolution matrix M satisfies M -γss ⊤ ≤ δ and γ ≥ Cδ for a large enough constant C. Let x k = M k x, be the result of applying k rounds of graph convolution to our input feature x. Then with probability at least 1 -1 2 exp(-1 4σ 2 ), there exists a scalar C k and an absolute constant C ′ such that∥C k x k -s∥ 2 ≤ O δ 2 γ 2 + C ′ δ γ 2k nσ 2 log nThe main idea of our analysis is to use the fact that the top eigenvector of M , denoted ŝ, is well correlated with our signal s. Since M -γss ⊤ ≤ δ and γ > Cδ by assumption, standard Matrix perturbation arguments imply that the spectrum of M will be in (γ ± δ, ±δ, ±δ, ...) with high probability. Given our assumption of γ > Cδ, there will be a large gap between the top eigenvalue of M and the rest of its eigenvalues. A well-known result Davis and Kahan implies that ∥s -ŝ∥ 2 ≤ O(δ 2 /γ 2 ), i.e. s is close to ŝ. Thus, we prove Proposition 6.1 by showing that the influence of the rest of the eigenvectors on our convolved vector, x k = M k x, decreases exponentially with k, which allows us to bound the squared norm distance between x k and s. In particular, we take our normalization constant to beC k ≈ 1/λ k 1 , where λ 1 is the maximum eigenvalue of M . Note that lim k→∞ (1/λ k 1 )M k = ŝŝ ⊤ .Roughly speaking, we decompose our convolution vector asC k x k ≈ (1/λ k 1 )M k s + (1/λ k 1 )M k g.To bound the distance of this vector from s, we analyze the contribution of each of the two terms to our error separately. That is, we show that with high probability∥(1/λ k 1 )M k s -s∥ 2 ≤ O(δ 2 /γ 2 ) and M k g 2 ≤ O((δ/γ) 2k nσ 2 log n).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, g, and thus decreases with our noise level σ and drops exponentially with each convolution.Finally, given Proposition 6.1, we can prove the partial classification result by noting that if we partition the convolved 1-dimensional data around 0, then each misclassified vertex contributes 1/n to the mean-squared error, which means the number of misclassified vertices is at most ∥C k x k -s∥ 2 n. This, combined with Lemma 5.1 to generalize to the m-dimensional case will prove Theorem 4.1 
exact classification: 
 In this section, we sketch the proof of Theorem 4.2 for exact classification using the un-normalized corrected convolution matrix Ã. Full proofs can be found in Appendix D. To show linear separability, we would like x k = Ãk x to have positive entries for all vertices in S and negative entries for all vertices in T . This means that we want to show ∥C k x k -s∥ ∞ < 1/ √ n for some appropriate scalar C k . In particular, we will take C k to be 1/η k , where η is our empirical estimate of γ(p, q). In partial classification, it sufficed to bound the mean squared error ∥C k x k -s∥ 2 2 , using spectral analysis but bounding ∥C k x k -s∥ ∞ 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 1-dimensional centered model: Proposition 7.1. Suppose we are given a 1-dimensional centered 2-block CSBM with parameters n, p, q, σ and k= O(log n) such that γ = p-q p+q ≥ Ω k log n np , p ≥ log 3 n n , and σ ≤ O 1 √ log n .Then with probability at least 1 -n -Ω(1) :1 η k Ãk x -s ∞ ≤ 1 2 √ n + O C γ √ np k σ log nGiven, Proposition 7.1, Theorem 4.2 follows immediately by applying Lemma 5.1. We now give a sketch of our proof for Proposition 7.1. To bound each entry ofC k x k -s, we must bound |e ⊤ u Ãk x/η k -e ⊤u s| for all u ∈ V . Similar to in partial classification, we will split our error into error from Ãk s and error from Ãk g. That is, for each u ∈ V , we separately upper bound|e ⊤ u (ηss ⊤ + R ′ ) k s -e ⊤ u s| and |e ⊤ u (ηss ⊤ + R ′ ) k g|, where R ′ = Ã -ηss ⊤ .The matrix (ηss ⊤ + R ′ ) k , when expanded out, can be written as η k ss ⊤ plus a sum of 2 k -1 terms, each of which is a noncommutative product of matrices of the form ηss ⊤ or R ′ . We group these error matrices into terms of order ℓ for ℓ ∈ [k], where the ℓ th order terms are comprised of products that contain ℓ copies of R ′ and k -ℓ copies of γss ⊤ .In our analysis, we first use degree concentration to show that instead of analyzing the error w.r.t. R ′ , it suffices to analyze the error w.r.t. 1 d R.To bound e ⊤ u (ηss ⊤ + 1 d R) k s, we expand it out and find that each term arising from an error matrix of order ℓ can be written as a multiple of e ⊤ u R a1 s•s ⊤ R a2 s•...s ⊤ R a L s where a 1 , ...a L are non-negative integers satisfying a 1 +a 2 +...a L = ℓ. The symmetric terms can be bounded by showing s ⊤ R a s ≲ ( √ np) a using simple spectral arguments.To control the asymmetric term, we show that with high probability, |e ⊤ u R a1 s| ≤ 1 √ n (Cnp log n) a1/2 for a constant C. This part is the most technical part and requires the slightly stronger graph density assumption: p ≥ Ω(log 3 n/n). Thus, we have |e⊤ u R a1 s • s ⊤ R a2 s • ...s ⊤ R a L s| ≤ 1 √ n (Cn log n) ℓ/2for some constant C. The analysis for bounding e u Ãk g is similar. Finally, by combining these bounds with our assumptions that γ is large enough, we obtain Proposition 7.1. 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 ⊤ u R ℓ s can be expressed as w R w(0),w(1) R w(1),w(2) , ...R w(ℓ-1),w(a) s(w(a)) where the sum is over all walks, w, of length a in the complete graph over n vertices starting at w(0) := u. From a message-passing perspective, one can interpret this as bounding the deviation between the amount of signal message u receives over paths of a certain length and the amount of message it expects to receive. To bound this term, we use a path counting argument to control its higher moments, and then apply Markov's inequality:Pr |e ⊤ u R a s| ≥ λ < 1 λ 2t E[|e ⊤ u R a s| 2t ].8 Multi-class Analysis on Gaussian Mixture ModelIn 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-normalized corrected convolution matrix, Ã. 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 L clusters (see Lemma E.1). Before formally stating our result, we will introduce some useful notation:• Graph Signal: λ := (p-q)n dL is the strength of the signal from the graph.• Graph Noise:δ := C( 1 d ( np(1 -p)/L + nq(1 -q))) for some constant C. δ is an upper bound on the graph noise.• Let U := E[X] be the matrix whose i th column is µ i . We also assume our features are centered on expectation so that U ⊤ 1 = 0. This is not restrictive since it can be satisfied by applying a linear shift to the features • Let ∆ = min i,j∈[n] ∥µ i -µ j ∥ be the minimum distance between the centers Theorem 8.1. Given the CSBM with parameters, p, q, L, n, m, suppose min(p, q) ≥ Ω(log 2 n n ) and |λ| > 4kδ. Let X (k) = 1 λ kÃk X be the feature matrix after k rounds of convolutions with scalaing factor 1/λ k . Let x (k) i be the i th row of the matrix X (k) . Then with probability 1 -n -Ω(1) , at leastn -n e nodes, i, satisfy x (k) i -µ i < ∆/2 where n e = O (kδ/|λ|) 2 ∥U ∥ 2 F ∆ 2 + (L + n(δ/|λ|) 2k ) σ 2 m log n ∆ 2 .In particular, the quadratic classifer x → softmax(∥x -c l ∥ 2 ) L l=1 will correctly classify at least n -n e points, and when n e = o(n), then we can correctly classify 1 -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 is 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, σ 2 , that is large at the beginning and decreases exponentially with each convolution. The classification accuracy at the point of saturation (k ≈ log n) depends on the squared product between graph's signal-to-noise ratio, δ/|λ|, and the "separation ratio" of the datasets: ∥U ∥ F /∆. As in the two-class setting, our theorem captures both the homophilic and heterophilic settings. However, for large L, our error parameter, δ, can be much larger if q > 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 4.2 for linear binary classification. For real data, we show that removing the principal component of the adjacency matrix exhibits positive effects on multi-class node classification problems as well.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 ( 1). We choose n = 2000 nodes with 20 features for each node, sampled from a Gaussian mixture. The intra-edge probability is fixed to p = O(log 3 n/n). We perform linear classification to demonstrate the results in Theorem 4.1 and Theorem 4.2, training a one-layer GCN network both with and without the corrected convolutions and perform an empirical comparison.We provide plots for two different settings: (1) Fix γ = |p -q|/(p + q) = 2/3 and vary signal-tonoise ratio of the node features, ∥µ -ν∥/σ, for different number of convolutions. We observe in Figure 1 that as the number of convolutions increases, the original GCN [Kipf and Welling, 2017] (in blue) starts performing poorly, while the corrected versions (in orange and green) retain the accuracy for lower signal-to-noise ratio; (2) Fix ∥µ -ν∥/σ = 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 2 . The vertical lines represent the threshold for exact classification from Theorem 4.2. Figure 1 : 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 = D 1/2 1 and the "GCN with vv ⊤ removed" refers to convolution with the corrected, normalized adjacency matrix. "GCN with 11 ⊤ removed" is the corrected, unnormalized matrix.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 of convolutions increases but the corrected convolutions converge to an accuracy much higher than that of the uncorrected convolution. This is attributed to 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.1, that for synthetic data with balanced classes, the classification accuracy only increases with more convolutions if they are corrected to remove the top eigenvector.  
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 to generalize our analysis to broader classes of multi-class models. For example, if the size of classes are unbalanced, the second eigenspace may not capture all the information about the clusters. In addition, the distribution of features may not follow a standard Gaussian mixture model, but more complicated distributions, possibly with multiple centers [Baranwal et 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.Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [No] Justification: As we mention above, our work is theoretical and we don'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 we 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.• 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper is theoretical. It poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • 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 is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was 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. 
crowdsourcing 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 as 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 in the supplemental material is fine, but if the main contribution 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. 
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?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. • Depending on 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.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: Before beginning our proofs, we will establish the following theorems from the literature and basic facts that we will use throughout the proofs.For matrix inequalities, we 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 λ 1 ≥ λ 2 ≥ ...λ n and B be a symmetric matrix µ 1 ≥ µ 2 ≥ ....µ n . Suppose ∥A -B∥ ≤ δ. Then,max i |λ i -µ i | ≤ δWe also use the following basic result to relate the matrix spectral norm to its maximum entry Lemma A.2. Let M be an n × n symmetric matrix such that each row of M has at most m non-zero entries and each entry of M has an absolute value at most ε. Then ∥M ∥ ≤ εmProof. We will use the fact that for any scalars a, b, we have2ab ≤ a 2 + b 2 since a 2 + b 2 -2ab = (a -b) 2 ≥ 0.We will also use supp(M ) to denote the set of non-zero entries in M . Let x be a unit vector. Then we have|x ⊤ M x| = | i n j=1 x(i)x(j)M i,j | ≤ ε i,j∈supp(M ) x(i)x(j) ≤ ε i,j∈supp(M ) 1 2 x(i) 2 + 1 2 x(j) 2 ≤ εm i x(i) 2 = εmWhere the last inequality follows from the fact for every i, there are at most m entries j such that M i,j ̸ = 0.Throughout our analysis, we will mainly use the following two concentration inequalities. The first is a bound on the the expected deviation of the sum of Bernoulli random variables Theorem A.3. Let X 1 , ...X n be Bernoulli random variables with mean at most p and S n = n i=1 X i . ThenEQUATION))The second concentration inequality we will upper-bounds the spectral norm of random matrices whose entries have zero mean and bounded variance. Theorem A.4. ( [Bandeira and van Handel, 2016] Remark 3.13) Let R be a random matrix whose entries R i,j are independent, zero mean, with variance σ 2 . Then with probability 1 -n -Ω(1) , we have∥R∥ ≤ O(σ √ n + log n) In particular, if σ 2 = Ω( log 2 n n ) then ∥R∥ ≤ O(σ √ n)We will also use the standard tail bound on the norm of a Gaussian vector Lemma A.5. Let g ∼ N (0, σ 2 I n ) be a random Gaussian vector. Then Pr [∥g∥ > t] ≤ 2 exp(-t 2 2nσ 2 )We will also be using the following basic fact about approximating the exponential function Lemma A.6. For all x, 1 + x ≤ e x . If x ≤ 1, then e x ≤ 1 + 2x.B.1 Proof of Lemma 5.1In the following section, we give the missing proofs of the basic properties of the CSBM. The first is the reduction from the m-dimensional model to the centered 1-dimensional model, which we will restate here:Lemma B.1. Given an m-dimensional 2-block CSBM , there exist w ∈ R m and b ∈ R n such that Xw + b = s + g where for each vertex i, g i is i.i.d. N (0, σ ′2 ) with σ ′ = 4σ √ n∥µ-ν∥ .Proof. Let X i,: be the i th row of X. For each i ∈ S, we have X i,: = µ + g i and for each j ∈ T we have X j,: = ν + g j , where g i ∼ N (0, σ 2 I m ) are i.i.d. random Gaussian noise vectors. Now we pick w= (µ -ν), b = -1 2 ⟨µ + ν, µ -ν⟩ ⃗ 1. Now x ′ = Xw + b. For i ∈ S, we let s ′ (i) := ⟨µ - 1 2 (µ + ν), µ -ν⟩ = 1 2 ∥µ -ν∥ 2and for i ∈ T , we lets ′ (i) := ⟨ν - 1 2 (µ + ν), µ -ν⟩ = - 1 2 ∥µ -ν∥ 2The s ′ part is our signal. On the other hand, the noise at each entry is given by x ′ (i) -s ′ (i) = ⟨g i , µ -ν⟩ which is Gaussian with standard deviation σ ∥µ -ν∥. Now, if we let x = 4 √ n∥µ-ν∥ 2 x ′ , then we have x = s + g, where s(i) ∈ ± 1 √ n and each entry of g is i.i.d. Gaussian with standard deviation σ ′ := 4σ √ n∥ν-µ∥ .In this section, we will provide some crucial properties of the graph convolution matrices in (1) and then use them to prove Proposition 5.2. The adjacency matrix A is a random matrix with expectationE[A] = pJ n/2 qJ n/2 qJ n/2 pJ n/2Where J m denotes the m × m all-ones matrix. It can be seen that E[A] is a rank-2 matrix, with eigenvectors 1√ n 1 and s because E[A]1 = 1 2 (p + q)n1 and E[A]s = 1 2 (p -q)ns, which means E[A] = 1 2 (p + q)11 ⊤ + 1 2 (p -q)nss ⊤Thus, in the centered one-dimensional CSBM, our true signal, s, is encoded in two ways: as the second eigenvector of the matrix E[A] and as E[x]. We can express our unnormalized corrected convolution matrix in terms of the signal, ss ⊤ , as follows:Ã = 1 d A - 1 n 11 ⊤ = (p -q)n 2d ss ⊤ + 1 2 (p + q)n -d nd 11 ⊤ + 1 d (A -E[A])Recall from main text that we defined η := (p-q)n 2d be the signal strength, d ′ := (p+q)n/2-d nd to be the degree deviation, and R = A -E[A] to be the error matrix. Thus, we haveÃ = ηss ⊤ + 1 d R + d ′ 11 ⊤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 R are small compared to our matrix signal strength η with high probability so that Ã behaves like ηss ⊤ ≈ γss ⊤ . To analyze convolution with the normalized Â, we use degree-concentration to show that Â is close to Ã, and so also behaves like γss ⊤ . Now we prove the main proposition in our section, Proposition 5.2, which we restate as follows:Proposition B.2. Assume that p = Ω( log n n ), and let γ = p-q p+q . With probability 1 -n -Ω(1) , we have the following concentration results1. |d ′ | = |d-1 2 (p+q)n| nd ≤ O(1/n 1.5 ), which implies that η ∈ p-q p+q (1 ± o(1)). 2. ∥R∥ ≤ O( √ np) 3. Ã -γss ⊤ ≤ O( 1 √ np ) and Â -γss ⊤ ≤ O( log n 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 1 4 (p + q)n 2 . Thus, we apply Theorem A.3 with t = Θ((p + q)n 1.5 ) to obtainPr ||E| - 1 4 (p + q)n 2 | > t ≤ exp(-Ω(pn)) = n -Ω(1)Since d = 2|E|/n, we have that with high probability, |d -1 2 (p + q)n| ≤ O((p + q)√ n) and .5 ). This gives us bound number 1. To get bound number 2, we apply Theorem A.4 on the error matrix R, noting that each entry of R has variance at most p. To get bound number 3, let|d ′ | = |d-1 2 (p+q)n| nd ≤ O( (p+q) √ n (p+q)n 2 (1-o(1))) ≤ O(1/n 1R ′ = 1 d R + d ′ 11 ⊤ = Ã -ηss ⊤ .Then with high probability, we have∥R ′ ∥ ≤ 1 d ∥R∥ + d ′ ∥J∥ ≤ 1 1 2 (p + q)n(1 -o(1)) ∥R∥ + d ′ 11 ⊤ ≤ O( 1 √ pn + 1 √ n ) since 11 ⊤ = n = O( 1 √ pn )Finally, we analyze the corrected normalized adjacency matrix Â. In this case, we want to show degree concentration for every node. Let d v be the degree of node v, and d = 1 2 (p + q)n be the expected degree. By applying Theorem A.3 and using our assumption p > q, we havePr |d v -d| > Cnp log n ≤ exp(-Ω(log n))Thus, with high probability, we have |d v -d| ≤ O( √ np log n) for all v ∈ V . Now, to analyze the normalized adjacency matrix, we haveÂ -γss ⊤ = Â -γss ⊤ + Ã -Ã ≤ Â -Ã + Ã -γss ⊤ ≤ D -1/2 AD -1/2 - 1 d A + 1 v d v D 1/2 11 ⊤ D 1/2 - 1 n 11 ⊤ + O( 1 √ np ) To bound D -1/2 AD -1/2 -1 d A , let ε = C log n npfor large enough C so that for all v, d v ∈ d(1 ± ε). We note that the adjacency matrix has at most d(1 + ε) non-zero entries for each row and for each u, v, we have| 1 √ d u d v - 1 d | ≤ 1 d(1 -ε) - 1 d(1 + ε) ≤ O( ε d )Thus, by applying Lemma A.2, we haveD -1/2 AD -1/2 -1 d A ≤ O(ε).Similarly, for all u, v, we have| √ d u d v i d i - 1 n | ≤ d(1 + ε) dn(1 -ε) - 1 n ≤ O( ε n ) Thus, Lemma A.2 implies that 1 v dv D 1/2 11 ⊤ D 1/2 -1 n 11 ⊤ ≤ O(ε). Finally, this implies that Â -γss ⊤ ≤ O( log n np )Note that the case p > q corresponds to a homophilous graph, and the case p < q corresponds to a heterophilous graph (see Luan et al. [2021] , 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 < q then we can take -Ã as our convolution matrix so that its maximum modulus eigenvalue is positive. Moreover, since our signal, s, is centered, taking a convolution with Ã is equivalent to taking a convolution with -Ã. Thus, we can assume without loss of generality that γ is always non-negative, i.e. p > q for the rest of our analysis.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-known in the literature (for example see Vershynin [2018] chapter 4.5).We will give the proof here for completeness. Lemma C.1. Suppose M satisfies M -γss ⊤ ≤ δ where γ > Cδ for large enough constant C. Let ŝ be the top eigenvector of M . Then ⟨s, ŝ⟩ 2 ≥ 1 -4 δ 2 γ 2 , and ∥s -ŝ∥ 2 = O(δ/γ).Proof. By assumption, we can express M as γss ⊤ + R ′ where ∥R ′ ∥ ≤ δ. Now let λ k be the k th largest eigenvalue of M . By Theorem A.1, we have |λ 1 -γ| ≤ δ and ∀i > 1, |λ i | ≤ δ. Now consider the matrix I -ss ⊤ , which is the projection matrix onto the orthogonal complement subspace of s.Since M = γss ⊤ + R ′ , we haveγ(I -ss ⊤ ) = γI -M + R ′and the matrix γI -M has the same eigenvectors as M . In particular, ŝ is an eigenvector with eigenvalues γ -λ 1 . Thus, we haveγ 1 -⟨s, ŝ⟩ 2 = γ ŝ⊤ (I -ss ⊤ )ŝ = γ(I -ss ⊤ )ŝ = ∥(γI -M )ŝ + R ′ ŝ∥ ≤ ∥(γI -M )ŝ∥ + ∥R ′ ŝ∥ ≤ |γ -λ 1 | + δ ≤ 2δThus, we have ⟨s, ŝ⟩ 2 ≥ 1 -4δ 2 /γ 2 . Since by our assumption, δ/γ is small, ŝ is very close to either s or -s. 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, we can assume WLOG that ⟨s, ŝ⟩ > 0. As a consequence, we have∥s -ŝ∥ 2 = 2 -2⟨s, ŝ⟩ = 2 -2 1 -2δ/γ = O(δ/γ)where the second inequality follows from applying the first order approximation √ 1 -x = 1 -x 2 -O(x 2 ) using the fact that δ/γ is small. Note that if ⟨s, ŝ⟩ was negative, we can do the same analysis in the following sections with -s instead of s. Now we will prove the main result about partial classification in the 1-dimensional model, Proposition 6.1, which we restate as follows: Proposition C.2. Given a centered 1-dimensional 2 block CSBM with parameters n, p > q, σ and γ(p, q) = p-q p+q , suppose our convolution matrix M satisfies M -γss ⊤ ≤ δ and γ ≥ Cδ for a large enough constant C. Let x k = M k x, be the result of applying k rounds of graph convolution to our input feature x. Then with probability at least 1 -1 2 exp(-1 4σ 2 ), there exists a scalar C k and an absolute constant C ′ such that∥C k x k -s∥ 2 ≤ O δ 2 γ 2 + C ′ δ γ 2k nσ 2 log nProof. Let λ 1 ≥ ...λ n be the eigenvalues of M and w 1 =: ŝ, w 2 ...w n be their corresponding eigenvectors. By Lemma C.1, the eigenvalues satisfy λ 1 ∈ γ ± δ and |λ i | ≤ δ for i > 1. The convolution vector after k rounds can be expressed as x k = M k g + M k s, and we will analyze each term individually.M k g = λ k 1 ⟨g, w 1 ⟩ŝ + i>1 λ k i ⟨g, w i ⟩w i = λ k 1 ⟨g, w 1 ⟩s + λ k 1 ⟨g, w 1 ⟩(ŝ -s) + i>1 λ k i ⟨g, w i ⟩w iand similarly,M k s = λ k 1 ⟨s, w 1 ⟩ŝ + i>1 λ k i ⟨s, w i ⟩w i = λ k 1 ⟨s, w 1 ⟩s + λ k 1 ⟨s, w 1 ⟩(ŝ -s) + i>1 λ k i ⟨s, w i ⟩w iNow we will let E g and E s be the error vectors, i.e. vectors that are not in the span of s, from each of the terms respectively. That isE g = λ k 1 ⟨g, w 1 ⟩(ŝ -s) + i>1 λ k i ⟨g, w i ⟩w i E s = λ k 1 ⟨s, w 1 ⟩(ŝ -s) + i>1 λ k i ⟨s, w i ⟩w iThus, we have x k = λ k 1 ⟨s + g, ŝ⟩s + E g + E s Thus, we will let C k = (λ k 1 ⟨s + g, ŝ⟩) -1 and bound the squared norm of the error terms C k (E g + E s ). We will also use the fact that for any vectors y, z, we have ∥y + z∥ 2 ≤ 2 ∥y∥ 2 + 2 ∥z∥ 2 . Using this, we have∥E g ∥ 2 ≤ 2λ 2k 1 |⟨ŝ, g⟩| 2 ∥s -ŝ∥ 2 + 2 i>1 λ k i ⟨g, w i ⟩w i 2 ≤ O(λ 2k 1 δ 2 /γ 2 )|⟨ŝ, g⟩| 2 + 2δ 2k i>1 ⟨g, w i ⟩w i 2 ≤ O(λ 2k 1 δ 2 /γ 2 )|⟨ŝ, g⟩| 2 + 2δ 2k ∥g∥ 2where in the second inequality, we used the fact that Lemma C.1 implies ∥s -ŝ∥ 2 ≤ O(δ 2 /γ 2 ). By Lemma A.5, we have ∥g∥ 2 = O(σ 2 n log n) with probability 1 -n -Ω(1) . Also, ⟨ŝ, g⟩ has distribution N (0, 1) because ŝ is a unit vector. Thus with probability exp(-1 4σ 2 ), |⟨ŝ, g⟩| ≤ 1/2. If both these events happen, then we have ∥E g ∥ 2 ≤ O(λ 2k 1 δ 2 /γ 2 + δ 2k σ 2 n log n). Now, to bound the other error term, we have∥E s ∥ 2 ≤ 2λ 2k 1 ∥s -ŝ∥ 2 ⟨ŝ, s⟩ 2 + 2 i>1 λ k 2 ⟨w i , s⟩w i 2 ≤ 2λ 2k 1 ∥s -ŝ∥ 2 ⟨ŝ, s⟩ 2 + 2δ 2k ∥s∥ 2 ≤ O(λ 2k 1 δ 2 /γ 2 ),where the last inequality follows from the fact that ∥s∥ = 1 and |λ 1 -γ| ≤ δ, which is a constant factor smaller than λ 1 , which means δ 2k = O(λ 2k 1 δ 2 /γ 2 ). Finally, we want to lower bound ⟨ŝ, s⟩ + ⟨s, g⟩ by a constant so C k = O(λ k 1 ). By Lemma C.1, we have ⟨ŝ, s⟩ > 1 -O(δ/γ). We can assume that our constant C is large enough so that γ/δ < 1/4, which means that ⟨ŝ, s⟩ ≥ 3/4. Then ⟨ŝ, s⟩ + ⟨s, g⟩ ≥ 1/4 as long as ⟨s, g⟩ ≥ 0 or |⟨s, g⟩| ≤ 1/2. This happens with probability at leastEQUATION2 ), and if this does occur, we have∥C k x k -s∥ 2 ≤ 2C 2 k ∥E g ∥ 2 + 2C 2 k ∥E s ∥ 2 ≤ O(λ 2k 1 (λ -2k 1 δ 2 /γ 2 + δ 2k nσ 2 log n)) O(δ 2 /γ 2 + (δ/λ 1 ) 2k nσ 2 log n) Moreover, since λ 1 ≥ γ -δ, we have δ/λ 1 ≤ δ/(γ -δ) = O(δ/γ) since γ is a 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 and σ ′ = O( σ √ n∥µ-ν∥ ). Now let x = Xw + b be our transformed onedimensional feature vector and let x k = M k x where M is either Ã or Â. To bound the mean-squared error of our convolved data, we will apply Proposition 6.1. By Proposition 5.2, we can takeδ = O( 1 √ np ) if M = Ã and δ = O( log n np ) if M = Â.Then, as long as γ ≥ Cδ for large enough constant C, we have a scalar C k and constant C ′ such thatEQUATIONNow, we take 0 to be the threshold, meaning we put vertex i in the first class if x k (i) < 0 and put it in the second class otherwise. Note that this partitioning scheme is indifferent to the scaling of the vector x k , so we can equivalently apply it to C k x k (note this does not necessitate computing C k directly). Since each i ∈ S has s(i) = 1/ √ n and each j ∈ T has s(j) = -1/ √ n, a vertex can only be misclassified if it contributes at least 1/n to the total squared distance ∥C k x k -s∥ 2 . Thus, the total number of misclassified vertices is at most ∥C k x k -s∥ 2 n, which gives us the main theorem after substituting the appropriate value of δ.In this section, we will formally prove Proposition 7.1. Before we begin, we will, as a warmup, analyze the behavior of 1 convolution for the centered 1-dimensional CSBM. The following proposition is essentially equivalent to theorem 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.1. Suppose we are given the 1-dimensional centered CSBM with parameters n, p, q, σsuch that p ≥ Ω( log 2 n n ), γ ≥ Ω( log n np ), and σ ≤ O( 1 √ log n ).Then with probability 1 -n -Ω(1) , we haves - 1 η x 1 ∞ ≤ O(σ 1 γ log n np + log n n ) + 1 2 √ nProof. By the definition of our convolution matrix, we have1 η x 1 = 1 η (ηss ⊤ + R ′ )(s + g) = s + 1 η R ′ s + (ss ⊤ + 1 η R ′ )gThus, we can bound the infinity norm error as:s - 1 η x 1 ∞ = 1 η R ′ s + (ss ⊤ + 1 η R ′ )g ∞ ≤ (ss ⊤ + 1 η R ′ )g ∞ + 1 η R ′ s ∞Since the infinity norm is the maximum absolute value of all entries, we need to bound terms |e ⊤ u R ′ s|/η and |e ⊤ u (ss ⊤ + R ′ /η)g| for all u ∈ V . We will start by bounding the Gaussian part of the error. Since e ⊤ u (ss ⊤ + R ′ /η)g ∼ N (0, σ 2 ∥R ′ e u /η + ⟨s, e u ⟩s∥ 2 ), we have that with high 1)). Thus, we haveprobability max i∈n |e ⊤ u (ss ⊤ + R ′ /η)g| ≤ O(σ √ log n • ∥R ′ e u /η|e ⊤ u (ss ⊤ + R ′ /η)g| ≤ O(σ 1 γ log n np + log n n ) Now, to bound the error term |e ⊤ u R ′ s|, we have e ⊤ u R ′ s = e ⊤ u ( 1 d R + d ′ 11 ⊤ )s = 1 d e ⊤ uRs since s is orthogonal to the all-ones vector. Now, WLOG, suppose u ∈ S. Notice thate ⊤ u Rs = 1 √ n ( i∈S R u,i -i∈T R u,i ), where both sums are sums over independent shifted Bernoulli random variables with variance at most p. Thus, by applying Theorem A.3, we have|e ⊤ u R ′ s| ≤ 1 √ n • O( √ np log n) = O( √ p log n). Now, using the fact that d ≥ 1 2 (p + q)n(1 -o(1)), we have | 1 d e ⊤ u Rs| ≤ O( 1 √ n • log n np ). By our assumption, γ ≥ C log n np ) for large enough constant C. Then, we can take C to be large enough so that| 1 η e ⊤ u R ′ s| = O 1 γ(1 -o(1)) log n np ≤ 1 2 √ n D.1 Proof of Main ResultIn this section, we prove Proposition 7.1, which we restate as follows: Proposition D.2. Suppose we are given a 1-dimensional centered 2-block CSBM with parameters n, p, q, σ and k = O(log n) such that γ = p-q p+q ≥ Ω(k log n np ), p ≥ log 3 n n , and σ ≤ O( 1 √ log n ). Then with probability at least 1 -n -Ω(1) :1 η k Ãk x -s ∞ ≤ 1 2 √ n + O(( C γ √ np ) k σ log n)Before proving the main proposition, we will use degree-concentration to reduce analyzing the error matrix R ′ = Ã -ηss ⊤ to analysing 1 d R instead. This is useful because our analysis crucially uses the fact that our error matrix R has zero-mean Radamacher entries. Proposition D.3. Let R ′ = Ã -ηss ⊤ and suppose k ≤ O(log n). Then with high probability, we have thatR ′k -1 d k R k ≤ O( C k k √ log n ( √ pn) k • √ n ) for a constant C.Proof. Before beginning the proof, we first need to give a tighter degree-concentration bound to show that with high probability,|d ′ | ≤ O( √ log n n 2 √ p ). By applying Theorem A.3 with t = Θ(n √ p log n). Pr ||E| - 1 4 (p + q)n 2 | > t ≤ exp(-Ω n 2 p log n (p + q)n 2 ) = n -Ω(1)Since d = 2|E|/n and with high probability at,|E| ≥ 1 4 (p + q)n 2 -t ≥ 1 4 (p + q)n 2 (1 -o(1)), we have d ≥ 1 2 (p + q)n(1 -o(1)) = Ω(np).Putting these together, we get the bound: |d ′ | = |d -1 2 (p + q)n| nd = 2 ||E| -1 4 (p + q)n 2 | n 2 d ≤ O( n √ p log n n 3 p ) ≤ O( √ log n n 2 √ p ) Now, recall from Equation (2) that R ′ = 1 d R + d ′ 11 ⊤ .1 δ R ′ ) k . We will let M 0 = 1 dδ R and M 1 = d ′ δ 11 ⊤ . Then, we have ∥M 0 ∥ ≤ 1,and∥M 1 ∥ ≤ d ′ n δ . Since |d ′ | ≤ √ log nn 2 √ p with high probability, we will assume this event occurs. Thus, we have∥M 1 ∥ ≤ O( n √ np log n n 2 √ p ) ≤ O( log n n ). Finally, we have ( 1 δ R ′ ) k = (M 0 + M 1 ) k .We are going to expand this out, and so let us introduce some notation. Let [k] ℓ = {i := (i 1 , i 2 , ...i k ) ∈ {0, 1} k : i 1 + i 2 + ...i k = ℓ}.That is, it's the set of length k binary sequences with exactly ℓ terms equaled to 1. Now, we have(M 0 + M 1 ) k -M k 0 = k ℓ=0 i∈( [k] ℓ ) k j=1 M ij -M k 0 = k ℓ=1 i∈( [k] ℓ ) k j=1 M ijFor any matrices M, N , their spectral norms satisfy ∥M N ∥ ≤ ∥M ∥ ∥N ∥. Thus, for each i∈ [k] ℓ , we have k j=1 M ij ≤ ∥M 1 ∥ ℓ since ∥M 0 ∥ ≤ 1.Thus, we have(M 0 + M 1 ) k -M k 0 ≤ k ℓ=1 k ℓ ∥M 1 ∥ ℓ = (1 + ∥M 1 ∥) k -1 ≤ e k∥M1∥ -1 ≤ 2k ∥M 1 ∥where the second last inequality follows from Lemma A.6 because k ∥M 1 ∥ ≤ k log n n ≤ 1 by our assumptions on k. Finally, we haveR ′k - 1 d k R k = δ k (M 0 + M 1 ) k -M 0 ≤ 2δ k k ∥M 1 ∥ ≤ O( kC k √ log n ( √ pn) k • √ n ) For a constant C.As a corollary, we can show the following:Corollary D.4. Let x and y be unit vectors. Then|x ⊤ R ′k y| ≤ |x ⊤ ( 1 d k R k )y| + O( C k k √ log n ( √ pn) k • √ n )) for some constant C.Proof. This follows from the basic properties of the spectral norm|x ⊤ R ′k y| = |x ⊤ ( 1 d k R k + R ′k - 1 d k R k )y| ≤ |x ⊤ ( 1 d k R k )y| + ∥x∥ ∥y∥ R ′k - 1 d k R k ≤ |x ⊤ ( 1 d k R k )y| + O( C k k √ log n ( √ pn) k • √ n )) by Proposition D.3Corollary D.4 is key to proving our main technical lemma, the proof of which we will defer to the next section.Lemma D.5. Given p ≥ log 3 n n , we have that with probability 1 -n -Ω( 1) , for all u ∈ V and allk ∈ {1, 2, ...O(log n)} |e ⊤ u R ′k s| ≤ 1 √ n C log n pn k for some constant CNow, we are ready to prove our main result, Proposition 7.1. The proof is similar to that of Proposition D.3 but requires the use of Lemma D.5 to obtain a sharper bound on the error terms than by simply applying the spectral norm bound as we did in the degree-concentration proof.Proof. (Proposition 7.1) Just like in the k = 1 case, we express Ã as ηss ⊤ + R ′ and decompose our convolution vector into the following terms:1 η k Ãk x = 1 η k Ãk (s + g) = s + ( 1 η k Ãk -ss ⊤ )s + 1 η k Ãk gIn order to bound s -1η k Ãk x ∞, we will bound, for all u ∈ V , the error terms |e ⊤ u ( 1η k Ãk -ss ⊤ )s| and |e ⊤ u 1 η kÃk g|. Similar to in the proof of Proposition D.3, we start by expanding out 1η k Ãk . Let Y 0 = ss ⊤ and Y 1 = R ′ . Then we have 1 η k Ãk = 1 η k (ηY 0 + Y 1 ) k = 1 η k k ℓ=0 η k-ℓ i∈( [k] ℓ ) k j=1 Y ij = k ℓ=0 η -ℓ i∈( [k] ℓ ) k j=1 Y ijNote that (ss ⊤ ) 2 = ss ⊤ , which means that the first term in our summation (i.e. the ℓ = 0 terms) is simply ss ⊤ . Now we start by bounding the error terms involving s.|e ⊤ u ( 1 η k Ãk -ss ⊤ )s| = | k ℓ=1 η -ℓ i∈( [k] ℓ ) e ⊤ u k j=1 Y ij s| ≤ k ℓ=1 η -ℓ i∈( [k] ℓ ) |e ⊤ u k j=1 Y ij s| For each i ∈ [k] ℓ , we have |e ⊤ u k j=1 Y ij s| = |e ⊤ u R ′a1 s • s ⊤ R ′a2 s • ...s ⊤ R ′a L s|where a 1 , ...a L are non-negative integers satisfying a 1 + ...a L = ℓ. This is because the product k j=1 Y ij has exactly ℓ terms of the form R ′ and ss ⊤ for the rest of the terms. By Proposition 5.2, the matrix R ′ has spectral norm at most C1 √ np for some constant C 1 with high probability. For each term of the form |s ⊤ R ′aj s| for j > 1, we bound it by|s ⊤ R ′aj s| ≤ ∥R ′ ∥ aj ≤ C1 √ np aj. For the first term |e ⊤ u R ′a1 s|, we apply Lemma D.5 and give |e⊤ u R ′a1 s| ≤ 1 √ n C 2 log n np a1for some constant C 2 . Thus, we have:|e ⊤ u k j=1 Y ij s| ≤ 1 √ n max(C 1 , C 2 ) √ np a1+...a L log n a1 ≤ 1 √ n C log n np ℓwhere C is a large enough constant such that C ≥ max(C 1 , C 2 ). Now, we let ρ := C η log n np . Assuming that γ ≥ 9Ck log n np and with high probability, η ∈ γ(1 ± o(1)), we have ρ ≤ 1 8k with high probability. Thus, we have|e ⊤ u ( 1 η k Ãk -ss ⊤ )s| ≤ k ℓ=1 η -ℓ i∈( [k] ℓ ) |e ⊤ u k j=1 Y ij s| ≤ 1 √ n k ℓ=1 k ℓ η -ℓ C log n np ℓ = 1 √ n k ℓ=1 k ℓ ρ ℓ = 1 √ n ((1 + ρ) k -1) ≤ 1 4 √ n by Lemma A.6 and ρ ≤ 1 8kNow, we bound the Gaussian part of the error:e ⊤ u Ãg = k-1 ℓ=0 η -ℓ i∈( [k] ℓ ) e ⊤ u k j=1 Y ij g + η -k e ⊤ u R ′k gFor each i ∈ [k] ℓ where ℓ < k, we have|e ⊤ u k j=1 Y ij g| = |e ⊤ u R ′a1 s • s ⊤ R ′a2 s • ...s ⊤ R ′a L g|where a 1 +a 2 +...a L = ℓ. This is because when ℓ < k, there is at least one Y ij term that is equalled to ss ⊤ , which means in the product, the leftmost term must be e ⊤ u R ′a1 s for some a 1 and the right most term must be s ⊤ R ′a L g for some a L . Once again, we use the fact that |s ⊤ R ′aj s| ≤ ∥R ′ ∥ aj ≤ ( C1 √ np ) aj for all j > 1, and by Lemma D.5, we have |e ⊤ u R ′a1 s| ≤ (C 2 log n np ) a1 where C 1 , C 2 are absolute constants. To bound the last term, we have that s ⊤ R ′a g ∼ N (0, σ 2 ∥R ′a s∥2 ) for all a > 0. Thus, with high probability, we have that|s ⊤ R ′a L g| ≤ O(σ ∥R ′a L s∥ √ log n) ≤ O(σ( C1 √ np ) a L √ log n). Thus, we can apply the same bounds as we did for the error term involving s but now with an extra σ √ log n factor:|e ⊤ u k j=1 Y ij g| = |e ⊤ u R ′a1 s • s ⊤ R ′a2 s • ...s ⊤ R ′a L g| ≤ O( σ √ log n √ n • k-1 ℓ=0 k ℓ ρ ℓ ) ≤ O( σ √ log n √ n • (1 + ρ) k ) ≤ O( σ √ log n √ n ) by Lemma A.6 ≤ O( 1 4 √ n )Where the last inequality follows assuming σ ≤ 1 C ′ √ log n for some large enough constant C ′ . Finally, to bound the k th order term, we have that with high probability,η -k |e ⊤ u R ′k g| ≤ ( C1 η √ np ) k σ √ log n.Putting everything together, and using the fact that η ≥ γ(1 -o(1)) with high probability, we have that for all u ∈ V ,|e ⊤ u s - 1 η k Ãk x| ≤ 1 η k (|e ⊤ u ( Ãk -ss ⊤ )s| + |e ⊤ u Ãk g|) ≤ 1 2 √ n + C γ √ np k σ log n)for some absolute constant C 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, we see that given m-dimensional features with feature matrix X, we can transform it to a centered 1-dimensional feature vector x = Xw + b = s + g where g ∼ N (0, σ ′2 I) and σ ′ = 4σ √ n∥ν-µ∥ . Thus, we have ∥ν -µ∥ = 4σ σ ′ √ n . By Proposition 7.1, our 1-dimensional features become linearly separable as long asC γ √ np k σ ′ √ log n < 1 2 √n for some absolute constant C. Given our expression of σ ′ in terms of the mean distance, this is equivalent to∥ν -µ∥ ≥ σ C γ √ np k log n In Proposition 7.1, we also needed to assumed that σ ′ ≤ O( 1 √ log n ), which implies that ∥ν -µ∥ ≥ Ω(σ log n n ) D.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, Ã, can be decomposed as Ã = M +R ′ where:• M has rank L -1, with L -1 eigenvalues equalled to (p-q)n dL = λ. Also, M U = λU• R ′ is a random matrix such that with probability at least 1 -n -Ω(1) ,∥R ′ ∥ ≤ C( 1 d ( np(1 -p)/L + nq(1 -q))) = δProof. The expected adjacency matrix in the multi-class setting can be written asE[A] =    pJ n/L qJ n/L . . . qJ n/L qJ n/L pJ n/L . . . qJ n/L qJ n/L . . . . . . qJ n/L qJ n/L qJ n/L . . . pJ n/L    = (qJ L + (p -q)I L ) ⊗ J n/L The top (normalized) eigenvector of E[A] is 1 √ n 1.The top eigenvalue is the expected degree d = pn/L + (L -1)qn/L. Moreover, E[A] has rank L and its eigenvectors are of the form L n v ⊗ 1 n/L where v is an eigenvector of the matrix (qJ L + (p -q)I L ). Since the top eigenvectoris 1 √ n 1 = 1 √ L 1 L ⊗ L n 1 n/L , the rest of the eigenvectors of E[A] must be of the form L n v 2 ⊗ 1 n/L , ... L n v L ⊗ 1 n/L, where v 2 , ...v L are an orthonormal basis of the subspace in R L orthogonal to 1 L . Thus, for l = 2, ..L, we haveE[A](v l ⊗ 1) = 1 L (p -q)n(v l ⊗ 1), which means the second toL th eigenvalues of E[A] are equalled to λd. Now let R = A -E[A]and . Then we haveÃ = 1 d A - 1 n 11 ⊤ = ( 1 d - 1 d )A + 1 d R + 1 d E[A] - 1 n 11 ⊤ Now, let M := 1 d E[A] -1n 11 ⊤ . Note that the non-zero eigenspace of M is equivalent to 2nd to L th eigenspace of E[A] and the corresponding eigenvalue is λ. To show that M U = U , let u be any column of U . By our assumption that each class has one center, the entries of u are constant on each class. If we define v ∈ R L such that v(l) = u(i) for i ∈ C l , then we can write u = v ⊗ 1 n/L . Since by our assumption, u ⊥ 1 n , we must have v ⊥ 1 L . Thus, we see that u is exactly in the subspace spanned by the non-zero eigenvectors of M , which means M u = λu.Now, we simply have to bound the spectral norm of the matrixR ′ := 1 d R + ( 1 d -1 d )A.We start with bounding ∥R∥. To do so, we can write R as R = R p + R q , where R p and R q contain the entries of R corresponding to intra-and inter-class edges respectively. Note that R p is block diagonal with L blocks of size n/L. Each block is size n/L × n/L and have i.i.d entries. By Theorem A.4, each block has spectral norm at most O( np(1 -p)/L) with probability at least 1 -n -Ω(1) . Similarly, we have ∥R q ∥ ≤ O( nq(1 -q)) with probability at least 1 -n -Ω(1) . This means ∥R∥ ≤ O( np(1 -p)/L + nq(1 -q)).n where |E| is the number of edges in G. By applying Theorem A.3 with t = np(1 -p)/L + nq(1 -q), we havePr | d -d| > t ≤ exp(-Ω( t 2 max(p, q) )) ≤ n -Ω(1)since min(p, q) ≥ log 2 n/n. Assuming that | d -d| ≤ t and noting that ∥A∥ ≤ d, we have( 1 d -1 d )A ≤ ∥R∥ ≤ t/d. Thus, we have Ã = M +R ′ , where ∥R ′ ∥ ≤ δ with high probability.We will also need to bound the operator norm distance between the k th convolution and M k Lemma E.2. Suppose |λ| > 2kδ. Then with high probability, we have1 λ k ( Ãk -M k ) ≤ 2kδ/|λ|.Proof. By Lemma E.1, we haveÃk = (M + R ′ ) k = M k + k l=1 b∈( [k] l ) k i=1 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 ∥M ∥ = |λ| and ∥R ′ ∥ ≤ δ with high probability. Using the fact that ∥AB∥ ≤ ∥A∥ ∥B∥ and triangle inequality, we have1 λ k ((M + R ′ ) k -M k ) ≤ 1 |λ| k k l=1 k l ∥M ∥ k-l ∥R ′ ∥ l ≤ k l=1 k l ( δ |λ| ) l = (1 + δ |λ| ) k -1Our assumption that |λ| > 4δk implies the RHS is at most 2kδ/|λ| by Lemma A.6. Now we are ready to prove Theorem 8.1.Proof. We can express the total squared error after k convolutions as:n i=1 x (k) i -µ i 2 = X (k) -U 2 FWe decompose our data as X (k) = U + G, where G is a Gaussian matrix with i.i.d N (0, σ 2 ) entries.Recall that we take our scaling factor to be 1/λ k . Thus, we haveX (k) -U 2 F = 1 λ k Ãk (U + G) -U 2 F ≤ 2 1 λ k Ãk U -U 2 F + 2 1 λ k Ãk G 2 F .By Lemma E.1, we have M U = λU . Let u 1 , ...u m be the columns of U . Then, we have1 λ k Ãk U -U 2 F = 1 λ k ( Ãk -M k )U 2 F = m i=1 1 λ k ( Ãk -M k )u i 2 ≤ m i=1 1 λ k ( Ãk -M k ) 2 ∥u i ∥ 2 = 1 λ k ( Ãk -M k ) 2 ∥U ∥ 2 F ≤ O(kδ/|λ|) 2 ∥U ∥ 2 Fwhere the last inequality follows from Lemma E.2. By Lemma A.5, we have, with high probability,1 λ k Ãk G 2 F ≤ 1 λ 2k T r( Ã2k )σ 2 m log nSince adding R ′ to M perturbs its eigenvalues by at most δ (Theorem A.1), we have1 λ 2k T r( Ã2k ) ≤ (1 + δ/|λ|) 2k (L -1) + n(δ/|λ|) 2k|λ| > 4δk implies (1 + δ/|λ|) 2k ≤ O(1). Now let n e be the number of points i such thatx (k) i -µ i ≥ ∆/2. Then we have n e ∆ 2 ≤ 4 X (k) -U 2 F ≤ O((kδ/|λ|) 2 ∥U ∥ 2 F + (L + n(δ/|λ|) 2k )mσ 2 log n)Dividing both sides by ∆ 2 gives us the desired bound.Finally, we recall that ∆ is the minimum distance between centers. Thus if x (k) i -µ i < ∆/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 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 at five 1-vs-all classifiers followed by a 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 do not deteriorate in performance as the number of convolutions increases. Note that while the performances are similar between linear and non-linear classification, non-linear classification is required in general when each individual class mean cannot be separated from all others via a linear hyperplane. 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 in 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 on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
 
2. 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.
 
[1] Choi, Yoonhyuk, et al. "Improving Signed Propagation for Graph Neural Networks." arXiv preprint arXiv:2301.08918 (2023).
questions: questions: 1. (Refer to weakness # 2) Would it be possible to analyze GNNs employing various convolution methods with shallower layers?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: There are no critical weaknesses in the work. I have a few comments/questions which I list below.
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? 
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?
3. The analysis considers homophily structure of the graph $p>q$. Can it be extended to heterophily case as well?
4. In the definition of $\hat{A}$ in equation 1, shouldn't the last $D$ be $D^{-1/2}$? The negative sign is missing.
questions: questions: Please refer to the Weaknesses.
limitations: limitations: The analysis is in linear setting, and extending it to non-linear activations may be challenging.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: What is CSBM? I know SBM but what makes it C?

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?

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 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: limitations: no ethical issues
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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.
* 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.
* Theoretical statements and their implications are hard to understand. Clearly stating all symbols and providing additional details would help. 
* 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.
* 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.
questions: 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?
* What are potential practical implications that can now be developed?
* l. 332: Why is the O-notation used for $p=O(log^3 n/n)$?
limitations: limitations: Limitations are not explicitly presented.

Comments: title: Thank you for the response
Correction of typo in the response
comment: We are grateful. Thank you. We will make appropriate modifications to address your concerns in the revised version.
I want to thank the reviewers for their quick and detailed answers. I am now convinced of this work's benefits to the graph learning community and am open to accepting this paper. I have changed my score to 6.

I want to state my final opinions below, to which the authors do not need to reply:

>The dominant (first) eigenvector does not hold meaningful classification information, therefore removing it helps. [...] Fig 3 shows that removing the top eigenvector allows the model to have better performance as the number of convolutions increases.

The best-achieved performance of the original aggregation and corrected aggregation are quite similar (both for k=1). Stating that the corrected aggregation retains more task-related information would better describe the behavior. Identifying non-SBM tasks for which "removing the top eigenvector allows the model to have better performance as the number of convolutions increases" is actually true, and the max performance for the corrected aggregation is better compared to the standard aggregation, which is still open and interesting for future work.

> We come from a graph neural network background where this definition is ubiquitous and we didn't explicitly specify it as a definition.

In my graph neural network background, a graph convolution consists of a feature transformation and an aggregation part. As this work considers the aggregation part, I would personally find it more precise to call it $k$ rounds of aggregation instead of $k$ rounds of convolution. 

>We can offer to change the title to "Analysis of Eigen-Corrected Graph Convolutions" if the reviewer believes that this is more specific.

I don't mind if the authors keep the original title. To me personally, something like "Analysis of CSBM-Corrected Graph Aggregations" would seem clearer.
We thank the reviewer for their reply. However, we would like to point out that this post was made very close to the deadline and during the authors' nighttime. A proper reply to the reviewer takes several hours. We provide a reply to the best of our ability given the limited time.

We want to re-iterate the fact that the corrected convolution is not ours. We mention this in our first reply above and we point this out in lines 348 to 350. This idea is already implemented in widely cited practical papers [ref line 512 (ICLR 2020)]. We provide a rigorous analysis.

> In the referenced work [ref line 443, Keriven: Not Too Little, Not Too Much], ...  task. 

The result that the reviewer claims seems to be Theorem 2. We would like to clarify what is proved in the main theorem of this paper. The authors don't provide a non-asymptotic analysis as we do in our paper. They only provide an existential result. They prove that 1 convolution can be better, under specific assumptions, than 0 convolutions. They also prove that 1 convolution is better than infinite convolutions. This implies that there might exist a $k^* \ge 1$ which is optimal. However, they never rigorously analyze the performance of convolution for $k>1$ and $k<\infty$. In fact, the authors mention in their paper that "In the next section, we also derive an intuitive expression for $R(k)$ (although without rigorous proof), which we observe to match the numerics quite well."

We would like to point out that it is technically extremely challenging, and requires a whole different set of methodology, to achieve non-asymptotic analysis as we do in our paper, and we hope the review appreciates it. 

> Can this study be extended ...  in the limit becomes worse?

We will reply to this question by focusing on other tasks within node-classification, since node-classification is the focus of our paper. By dominating eigenvector we assume that the reviewer implies the second or higher eigenvectors. The dominant (first) eigenvector does not hold meaningful classification information, therefore removing it helps. We prove this in our Theorems 4.1 and 4.2. Also, Fig 3 shows that removing the top eigenvector allows the model to have better performance as the number of convolutions increases. 

We interpret the reviewer's comment as a question about why the performance decreases for $k$ larger than 1 or 2. The reason is not because we remove the dominant (first) eigenvector. As we point out this is beneficial, since the first eigenvector holds no information about the classes. The reason is that in the particular real data which we used there are eigenvectors with small eigenvalues which might contain meaningful information. Asymptotically, the corrected convolution, which we repeat is not our idea, see comments above, might miss the information from such eigenvectors. Intuitively, this could be the case in a graph where there are small communities within larger communities in the given graph structure. The top eigenvectors are likely to be correlated with the larger communities. To capture the information from small eigenvalues, a different convolution is needed which filters eigenvectors in an appropriate way. However, we would like to point out again, that the first eigenvector will be filtered out in this case too since it's not meaningful. 

To analyze such a scenario, we would have to change our random data model. That's because in the current data model the first few top eigenvectors (excluding the first one) are the most meaningful ones, and eigenvectors for small eigenvalues are just noise. Technically, a non-asymptotic spectral analysis could also work in this hypothetical new data model. The corrected convolution in our paper is likely to lose performance as $k$ increases. A different convolution would be needed to better capture the information of eigenvectors of small eigenvalues. This study is indeed interesting, however, we would like to mention that it is far from the goal of our present paper. 

We would be happy to mention the above in our paper.

> Convolution: ... in this work clearer.

We will make sure to clarify this in our paper. We come from a graph neural network background where this definition is ubiquitous and we didn't explicitly specify it as a definition. 

> Corrected convolution: ... can be more "correct".

We chose the word corrected since in the literature of statistical community detection (no node features), the word is often used for modified versions of the original SBM, for example: B. Karrer and M. E. J. Newman, Stochastic blockmodels and community structure in networks, Phys. Rev. E 83 (2011). In this case, the fact that one does degree "correction" does not necessarily mean that it is a universal correction for any possible problem. It's a name which makes sense within a specific context. We can offer to change the title to "Analysis of Eigen-Corrected Graph Convolutions" if the reviewer believes that this is more specific.
The above comment was apparently not visible to the authors. I apologize and hope my question still comes in time.
Thank you! We will incorporate the modifications in the revised version of the paper.
I thank the reviewers for their detailed feedback. I can now better understand why this work can be interesting from a mathematical and statistical point.

I would like to hear more details about the following:
* In the referenced work [ref line 443, Keriven: Not Too Little, Not Too Much], the author shows that some rounds of aggregation can be helpful while too many iterations are hurtful for their considered task. Here, it seems like more rounds of aggregation are always beneficial, but fewer rounds can be sufficient. Can this study be extended in the future to include cases where the task does not align so well with the dominating eigenvector? For Figure 3, performance seems to be monotonously decreasing, so (zero or one?) iterations seem to be optimal. What would tasks look like for which some iterations of your corrected convolutions are beneficial while the performance in the limit becomes worse?

Two additional comments on terms that I found irritating but not critical:
* Convolution: There is no definition of what convolution means. It seems like it's just the aggregation part $\mathbf{A}$ and powers of it. Referring to this as convolution is confusing to me, as no filter is considered. In the referenced work above, the author calls this $k$ rounds of aggregation, which would also make the statements in this work clearer.
* Corrected convolution: Was this term used previously in the literature? What makes this aggregation more "correct"? I agree that it seems more correct for the tasks considered in this work. However, I would argue that depending on the graph and task, various aggregation matrices can be more "correct".
Thanks, I am happy with all the responses. The new figures showing the bound vs performance are also very interesting, and a great improvement on the paper. I have no further questions.
We thank the reviewer for recommending acceptance of the paper. We will address all comments in the revised version of the paper.
We thank the reviewer for raising their score. We will add the additional result in the revised version of the paper and address all comments.
I thank the authors for their clarifications and for providing analysis for multi-class setting. I retain my score as I didn't have any major concerns in my initial review, and I recommend acceptance of the paper.
The authors' response has adequately addressed my main concerns on the multi-class scenario and the analysis on shallower networks. I have raised my rating.
Dear reviewer, we apologize for the typo in the response to Question 2: What makes it C in CSBM?
The C (context) here refers to the node features, since the data model consists of node features in addition to the graph.
This term has been used in the statistics community to describe such data with a combination of two components: the graph and the node attributes.
Please refer to Section 3.1 for a detailed description of the CSBM, and to [Deshpande, Y. and Sen S. and Montanari, A. and Mossel, E. Contextual stochastic block models. Advances in Neural Information Processing Systems, 2018.] where it was introduced.