A Spectral Theory of Normalized Corrected GNN Propagation

Abstract We develop a spectral theory for normalized corrected GNN propagation. The object of study is the symmetric normalized adjacency with its degree-stationary component removed, matching the normalization used by standard GCN-style models while isolating the stationary direction most directly tied to oversmoothing. The central theoretical question is whether this corrected normalized operator preserves class-discriminative signal after many propagation layers. Our main result is a high-probability exact-recovery theorem for the binary Contextual Stochastic Block Model after k = O(log n) propagation steps in the dense polylogarithmic regime p ≥ C logB n/n, for any fixed B > 4, under explicit graph-signal and feature-SNR conditions. We also establish a multi-class partial recovery theorem showing contraction toward class centers for most nodes. Synthetic and real node-classification experiments are included as empirical checks of the theory’s predicted dependence on depth, graph signal, and feature noise.

Introduction

Deep GNNs repeatedly apply graph propagation operators to node features (Scarselli et al., 2009; Kipf & Welling, 2017; Hamilton et al., 2017; Wu et al., 2019; Gasteiger et al., 2019). For GCN-style architectures, the basic linear backbone is the symmetric normalized adjacency D−1/2 AD−1/2 (Kipf & Welling, 2017; Chen et al., 2020; Wu et al., 2019). This normalization is essential in practice, but it also creates a precise spectral mechanism for oversmoothing: repeated propagation amplifies the degree-stationary component while attenuating directions that separate classes (Li et al., 2018; Oono & Suzuki, 2020; Keriven, 2022; Rusch et al., 2023; Jin & Zhu, 2025). Thus a central theoretical question is not only whether oversmoothing occurs, but whether the normalized propagation operator can be corrected in a way that provably preserves class information at logarithmic depth. We study this question through the operator b = D−1/2 AD−1/2 − A

1⊤ D 1

D1/2 11⊤ D1/2 ,

which subtracts the degree-stationary rank-one component before propagation. This operator-level viewpoint follows the broader spectral and graph-signal processing perspective on graph filters (Shuman et al., 2013; ∗ Wei Li is the corresponding author ([email protected]).

Balcilar et al., 2021; Chien et al., 2021; Goksu, 2025). This is the normalized counterpart of the corrected convolution analyzed by (Wang et al., 2024) for unnormalized adjacency matrices. The normalized setting has three characteristic features: the stationary vector is degree-dependent and random, each entry contains nonlinear degree factors, and powers of the residual matrix are tracked entrywise in addition to their spectral-norm behavior. This paper develops a spectral theory of this normalized corrected GNN propagation operator under the Contextual Stochastic Block Model (CSBM) (Deshpande et al., 2018; Lu & Sen, 2020; Baranwal et al., 2021; 2023a; Dalle & Thiran, 2024). The main theorem gives exact recovery by a linear classifier after k = O(log n) propagation steps when p ≥ C logB n/n for any fixed B > 4, provided the graph signal and feature signal-tonoise ratio exceed explicit thresholds. The theorem characterizes when the stationary correction is sufficient to preserve separability through logarithmic depth. The proof reduces the normalized operator to a corrected rank-one signal plus a residual and then develops an entrywise Krylov bound for multi-layer residual powers. The key technical device is a degree-truncated atom expansion combined with decorated-walk counting, which separates true graph fluctuations from artifacts introduced by random normalization. The experiments conducted in this paper examine the predicted dependencies on depth, graph signal, and feature noise. They are consistent with reduced depth-dependent degradation on synthetic CSBM instances and standard node-classification benchmarks. The main contributions are as follows. • A normalized corrected propagation model. We formulate the corrected GCN backbone by subtracting the degree-stationary component of D−1/2 AD−1/2 , giving an explicit operator-level model of spectral correction in normalized GNNs. • Binary exact-recovery theorem. We prove binary CSBM exact recovery after k = O(log n) normalized corrected propagation steps in the dense polylogarithmic regime p ≥ C logB n/n, with explicit graph-signal and feature-SNR conditions. • Entrywise residual-power theory. We prove worst-node multi-layer bounds for powers of the normalized residual despite random degree normalization, using atom expansions and decorated-walk counting. • Multi-class recovery theorem and empirical checks. We prove partial recovery for fixed L-class CSBMs and include empirical checks of the predicted depth dependence on synthetic and real node-classification datasets. • Empirical validation. Experiments on synthetic CSBM data and standard node-classification benchmarks support the theory and show that normalized spectral correction remains effective in deep GNN regimes.

Related Work

Message passing and normalized propagation. GNNs combine graph structure and node features through repeated local aggregation (Scarselli et al., 2009; Kipf & Welling, 2017; Hamilton et al., 2017). Several influential models can be viewed, at least in their linear propagation backbone, as applying normalized graph filters before or between learned feature transformations (Kipf & Welling, 2017; Wu et al., 2019; Gasteiger et al., 2019; Chen et al., 2020). This paper focuses on that propagation backbone rather than on architectural components such as nonlinear activations, attention, or optimization. The specific object of study is the symmetric normalized operator after subtracting its degree-stationary component. Oversmoothing and its spectral mechanisms. Oversmoothing was identified as a depth-dependent loss of class information in message passing (Li et al., 2018); subsequent theory shows that repeated propagation can drive node representations toward low-dimensional or stationary subspaces (Oono & Suzuki, 2020; Cai & Wang, 2020; Hou et al., 2020; Keriven, 2022; Adam-Day et al., 2024; Rusch et al., 2023). Many methods attempt to mitigate this behavior through residual connections, normalization, edge dropping, diffusion design, or signed/high-frequency components (Xu et al., 2018; Zhao & Akoglu, 2020; Chen et al., 2020; Rong et al., 2020; Chamberlain et al., 2021; Scholkemper et al., 2025; WANG et al., 2026; He et al., 2025). Our 2

contribution is complementary: we do not introduce a new trained architecture, but analyze an explicit correction of the propagation operator and prove when it preserves separability. Graph spectral filters and correction. Graph signal processing interprets message passing as filtering over the graph spectrum (Shuman et al., 2013). Early spectral GNNs and localized polynomial filters established this operator viewpoint (Bruna et al., 2014; Defferrard et al., 2016; Balcilar et al., 2021). Learnable or adaptive filters, including generalized PageRank and polynomial constructions, have been proposed for heterophily or oversmoothing (Chien et al., 2021; Goksu, 2025). These works motivate the operator-level viewpoint, but most are algorithmic or empirical. Here the filter is fixed by a correction principle: remove the rank-one stationary component and analyze the resulting normalized residual through high-probability spectral and entrywise bounds. CSBM theory and the closest prior work. The CSBM provides a controlled model in which graph structure and noisy node features jointly determine classification performance (Deshpande et al., 2018; Lu & Sen, 2020; Mehta et al., 2019; Baranwal et al., 2021; Maskey et al., 2022; Baranwal et al., 2023a;b; Maskey et al., 2024; Duranthon & Zdeborová, 2025; Dalle & Thiran, 2024; Ma et al., 2025). The closest result to ours is the corrected convolution theory of (Wang et al., 2024), which proves recovery guarantees for an unnormalized corrected adjacency operator. Our setting differs in the normalization used by standard GCNs: D−1/2 AD−1/2 has a random degree-weighted stationary vector, and its entries contain nonlinear degree denominators. These features require the atom expansion and decorated-walk counting developed below; they are not consequences of the unnormalized analysis.

Preliminaries

We use the following notation throughout this paper. For n ∈ N, let [n] = {1, . . . , n}. The all-ones vector is denoted by 1, and ei denotes the i-th standard basis vector. For a vector x, let ∥x∥ and ∥x∥∞ denote its Euclidean and infinity norms. For a matrix M , let  1/2 X 2 ∥M ∥ = sup ∥M x∥, ∥M ∥F =  Mij ∥x∥=1

i,j

denote the operator and Frobenius norms. We also use the induced ℓ∞ → ℓ∞ matrix norm X ∥M ∥∞→∞ := sup ∥M x∥∞ = max |Mij |, i

∥x∥∞ =1

that is, the maximum absolute row-sum norm. Let G = (V, E) be an undirected unweighted graph with V = [n], adjacency matrix A, degrees di , degree matrix D = diag(d1 , . . . , dn ), and average degree 2|E| . n

d :=

We use the standard conventions (D−1/2 )ii = 0 when di = 0, and d = (1⊤ D1)/n, so d−1 = n/(1⊤ D1) when 1⊤ D1 > 0, and d−1 = 0 when d = 0. For GCN-style propagation, the symmetric normalized adjacency is D−1/2 AD−1/2 . The dominant stationary component of this operator is not the uniform vector but the degree-weighted vector D1/2 1. We therefore study the corrected normalized propagation matrix b = D−1/2 AD−1/2 − A

1⊤ D 1

D1/2 11⊤ D1/2 .

(1)

For comparison with the unnormalized theory of (Wang et al., 2024), we also write e = 1 A − 1 11⊤ . A d n Both operators remove the leading stationary direction before repeated propagation. The normalized operator b is the one used in our main results and experiments. A 3

Main Results

We now state the main spectral consequences of normalized corrected propagation. The CSBM (Duranthon & Zdeborová, 2025) adds Gaussian node features to a planted block model, making it possible to track three quantities in the same theorem: graph signal, feature noise, and propagation depth. Our results show that, after removing the degree-stationary component, the normalized operator behaves like a low-rank class-signal operator plus a residual whose multi-layer action remains controlled. Definition 4.1. The CSBM, denoted CSBM(n, m, p, q, µ, ν, σ), is defined as follows. Let V = [n] be the set of vertices (with n even), partitioned into two disjoint communities S and T of equal size |S| = |T | = n/2. Let y ∈ {−1, 1}n be the community indicator vector by setting yi = 1 if i ∈ S and yi = −1 if i ∈ T . The model generates a random graph G = (V, E) and a feature matrix X ∈ Rn×m according to the following processes: 1. Graph Generation: For every pair of distinct vertices i, j ∈ V , the edge (i, j) is included in E independently with probability: ( p if yi = yj (intra-class), P((i, j) ∈ E) = q if yi ̸= yj (inter-class). 2. Feature Generation: For each vertex i ∈ V , the feature vector xi ∈ Rm (the i-th row of X) is drawn independently from a Gaussian mixture: ( N (µ, σ 2 Im ) if i ∈ S, xi ∼ N (ν, σ 2 Im ) if i ∈ T. For p > q > 0, set γ(p, q) := p−q p+q . In (Wang et al., 2024), proved that e (Wang et al., 2024)). Suppose we are given a 2-block m-dimensional Theorem 4.2 (Exact Recovery for A q

CSBM with parameters n, p > q, µ, ν, σ satisfying γ(p, q) ≥ Ω k

log n np

and p ≥ logn n . Then after k =

O(log n) rounds of graph convolution with Ã, our data is linearly separable with probability 1 − n−Ω(1) if !! r log n C k p ∥µ − ν∥ log n ≥ Ω max , √ σ n γ np where C is an absolute constant. The first main theoretical result is the normalized analogue. It has the same structure, but the random degree normalization requires a dense polylogarithmic density assumption and a slightly stronger residual-control term. b Fix any constant B > 4. Theorem 4.3 (Exact Recovery for A). There exist constants Cd , Cγ , C0 , C∗ , Csnr , c0 > 0, depending only on B, such that the following holds. Consider a balanced q

two-block CSBM(n, m, p, q, µ, ν, σ) with p > q > 0, centered feature means µ + ν = 0. Let θ := C

log n np

and ρ := γθ , where C > 0 is a sufficiently large absolute constant. Assume p ≥ Cd logn n and suppose q n 1 ≤ k ≤ C0 log n and γ ≥ Cγ k log np (where C0 is chosen no larger than the constant c in Lemma B.9), which equivalently implies kρ ≤ c0 . Then, after k rounds of normalized corrected graph convolution, the rows bk X are linearly separable with probability at least 1 − n−Ω(1) , provided of X (k) = A r  s !k   log n p ∥µ − ν∥ C∗ log n log n . ≥ Csnr max ,   σ n γ np Remark 4.4. Theorem 4.3 gives a normalized exact-recovery guarantee under the dense polylogarithmic condition np ≥ C logB n with fixed B > 4. This is a slightly stronger density assumption than the sharp np ≥ C log3 n target, but it makes Taylor remainders in the normalized degree expansion controllable by deterministic row-sum bounds. 4

Proof roadmap and key technical estimate. We include the proof roadmap here, and the main technical contribution of the theorem lies in the normalized residual-power analysis. First, the feature model is reduced to the one-dimensional centered form Xw = s + g, where g ∼ N (0, σ ′2 In ), by Lemma B.2. Second, degree concentration gives the signal-plus-residual decomposition s (p − q)n log n ⊤ ′ ′ b = ηss + R , A η= , ∥R ∥ ≲ . 2d np However, this spectral-norm control is not enough for exact recovery. We need worst-node control after k = O(log n) layers. The key technical estimate is the following short form of Lemma B.9: with high probability, uniformly over all vertices u and all 1 ≤ a ≤ k, s !a 1 log n ′ a K e⊤ . (Key) u (R ) s ≤ √ np n This bound says that residual powers remain delocalized in the planted signal direction; the extra n−1/2 factor is what allows a sign-based classifier to control every node rather than only an average error. The proof of (Key) is the normalized part of the argument. Unlike the unnormalized case, each entry of R′ contains random nonlinear degree denominators and a random stationary correction. We handle these terms by expanding normalized entries into positive-level atoms (Lemma B.5) and then bounding the surviving high-moment terms by decorated-walk counting (Lemma B.6). This yields the decoupled decorated-walk expansion and moment bound in Appendix B. Finally, Lemma B.10 combines (Key), the spectral norm bk (s + g) stays within o(n−1/2 ) of s in ℓ∞ , which gives bound, and Gaussian concentration to show that η −k A linear separability. The second theoretical result extends the analysis to L classes, with equal-sized graph blocks and Gaussian class-conditional features. The result is weaker than exact recovery, but it retains the same spectral conclusion: after normalization correction, most propagated representations contract toward their class centers when the graph signal dominates perturbation and feature noise. Definition 4.5 (Multi-Class CSBM). A multi-class Contextual Stochastic Block Model (multi-class CSBM) with L equal-sized classes, denoted as CSBM(n, m, p, q, L, µ, σ), is generated as follows: 1. Node Labels: The n nodes are partitioned into L disjoint classes C1 , . . . , CL , each of size n/L. 2. Graph Topology: An undirected graph G = (V, E) is generated where edges between nodes i and j are drawn independently. The probability of an edge is p if i and j belong to the same class, and q if they belong to different classes. 3. Node Features: For a node i ∈ Cl , its m-dimensional feature vector is generated as xi ∼ N (µl , σ 2 Im ), where µl ∈ Rm is the specific center for class l. The parameter µ = {µ1 , . . . , µL } denotes the set of PL all class centers. We assume the centers are zero-mean, i.e., l=1 µl = 0. The expected average degree is

pn (L − 1)qn d¯ := + . L L

¯ be the graph signal strength and Let λ := (p − q)n/(dL) ! r np(1 − p) p −1 ¯ δ := C d + nq(1 − q) L be the graph-noise scale. Let U = E[X], assume U ⊤ 1 = 0, and set ∆ := minℓ̸=h ∥µℓ − µh ∥. We first recall the corresponding unnormalized result of (Wang et al., 2024); the normalized analogue follows as the next theorem. 5

e (Wang et al., 2024)). Given the CSBM with parameters, Theorem 4.6 (Multi-class Partial Recovery for A log2 n p, q, L, n, m, σ, suppose min(p, q) ≥ Ω( n ) and |λ| > 4kδ. Let X (k) = λ1k Ãk X be the feature matrix after (k)

k rounds of convolutions with scalaing factor 1/λk . Let xi probability 1 − n−Ω(1) , at least n − ne nodes, i, satisfy

be the ith row of the matrix X (k) . Then with

(k) xi − µ i

< ∆/2 where

2 2 ∥U ∥F 2k σ m log n + (L + n(δ/|λ|) . ne = O (kδ/|λ|)2 ) ∆2 ∆2 2

In particular, the quadratic classifer x 7→ softmax(∥x − cl ∥ )L l=1 will correctly classify at least n − ne points, and when ne = o(n), then we can correctly classify 1 − o(1) fraction of points. The following theorem gives the corresponding partial-recovery guarantee for the normalized corrected b operator A. b Given the multi-class CSBM with parameters Theorem 4.7 (Multi-class Partial Recovery for A). p, q, L, n, m, σ, assume that L is fixed, L | n, and all constants below may depend on L. Suppose the graph is sufficiently dense with d¯ ≥ C log n, the feature dimension satisfies m ≤ nCm for a fixed constant Cm > 0, and the signal q dominates the noise such that |λ| ≥ C0 k(δ + ϵ) for a sufficiently large absolute constant ¯ Let X (k) = λ−k A bk X be the scaled feature matrix after k rounds of propagation. C0 , where ϵ := Cϵ log n/d. (k)

Let xi be the i-th row of X (k) , and let ℓ(i) denote the class of node i. Then with high probability 1 − n−Ω(1) , (k) at least n − ne nodes satisfy ∥xi − µℓ(i) ∥ < ∆/2, where ne is bounded by 



2 h i h ϵ 2k δ + ϵ 2k δ + ϵ 2k i σ 2 m log n  2 δ + ϵ 2 ∥U ∥F . ne = O  ) + 4k ( ) + (1 + ) (L − 1) + n( ) (   |λ| |λ| ∆2 |λ| |λ| ∆2 | {z } | {z } Structural & Normalization Error

Initial Variance Error

In particular, the nearest-center classifier arg minℓ∈[L] ∥x − µℓ ∥ correctly classifies all nodes outside this exceptional set. Theorem 4.7 gives an explicit partial-recovery bound for normalized corrected propagation. When graph perturbation, normalization error, and feature noise are small relative to ∆, the bound on nnorm is sublinear. e The two error terms separate structural error from propagated feature variance: • Structural error. The first term accumulates graph perturbation and degree-normalization error relative to class separation. • Feature-noise error. The second term tracks propagated Gaussian noise and its dependence on m, σ, and ∆. Compared with Theorem 4.6, the normalized result replaces the graph perturbation scale δ by δ + ϵ and adds the purely normalization-driven term (ϵ/|λ|)2k ∥U ∥2F /∆2 . The proof is deferred to Appendices B and C.2.

Experiments

The experiments are secondary to the theoretical results and are designed as empirical checks of the spectral predictions rather than as a full architecture benchmark. On synthetic CSBM graphs, we vary feature SNR, graph signal strength, and propagation depth to test the theorem’s predicted dependencies. On standard node-classification benchmarks, we test whether the same normalized correction is associated with smaller depth-dependent degradation outside the idealized model. We compare against standard normalized propagation and three recent oversmoothing baselines: 6

• DropEdge (Rong et al., 2020), which randomly removes edges during training. • GraphMamba (He et al., 2025), which uses state-space modules for long-range propagation. • RevGNN (Park et al., 2024), which uses reverse diffusion to recover high-frequency information. 5.1

Synthetic Data

We generate two-block CSBM graphs with n = 2000 and feature dimension m = 20. After k propagation steps, a linear classifier is trained on the resulting embeddings; all curves report average accuracy over 50 trials. We test two regimes: 1. Feature SNR. We fix γ = (p − q)/(p + q) = 2/3 and vary ∥µ − ν∥/σ. Consistent with the theorem, corrected propagation remains more stable at large k when feature SNR is sufficient (Figure 1).

1.0

0.9

0.8

0.7

0.8

0.7

0.6

0.5

0.5 10−1

100 ‖μ − ν‖ σ

Standard GCN GCN with Â (Ours)

GCN with Ã GCN with Ã threshold

Accuracy

1.0

Accuracy

2. Graph signal. We fix ∥µ − ν∥/σ = 1 and vary γ. Corrected propagation retains higher accuracy as graph signal decreases, and the empirical transition follows the theoretical threshold trend (Figure 2).

101

0.5 100 ‖μ − ν‖ σ

Standard GCN GCN with Â (Ours)

(a) k = 1.

GCN with Ã GCN with Ã threshold

101

10−1

Standard GCN GCN with Â (Ours)

(b) k = 2.

0.9

0.8

0.7

0.6

0.5

0.5 10−1

100 ‖μ − ν‖ σ

Standard GCN GCN with Â (Ours)

GCN with Ã GCN with Ã threshold

(d) k = 8.

101

GCN with Â threshold

Accuracy

1.0

0.7

GCN with Ã GCN with Ã threshold

GCN with Â threshold

1.0

0.8

101

100 ‖μ − ν‖ σ

GCN with Â threshold

1.0

Accuracy

0.7

0.6

10−1

GCN with Â threshold

0.8

0.7

0.6

0.5 10−1

100 ‖μ − ν‖ σ

Standard GCN GCN with Â (Ours)

GCN with Ã GCN with Ã threshold

(e) k = 12.

101

GCN with Â threshold

10−1

101

100 ‖μ − ν‖ σ

Standard GCN GCN with Â (Ours)

GCN with Ã GCN with Ã threshold

GCN with Â threshold

(f) k = 16.

Figure 1: Synthetic CSBM accuracy versus feature SNR for increasing propagation depth. Baseline comparison. Against recent oversmoothing baselines, corrected propagation shows comparable accuracy trends while preserving the same stability pattern across both feature-SNR and graph-signal sweeps (Figures 3 and 4). 5.2

Real Data

We evaluate on Cora, CiteSeer, PubMed, Reddit, ogbn-arxiv, and ogbn-products. Table 1 reports dataset statistics. These experiments assess whether the correction is associated with reduced depth-dependent degradation on heterogeneous multi-class graphs. Balanced two-cluster subsets. To align with the balanced CSBM theory, we select the two largest classes in each dataset and downsample the majority class to obtain a 1:1 class ratio. In these balanced subsets, corrected propagation maintains more stable accuracy as depth increases (Figure 5), consistent with the predicted effect of removing the stationary component. 7

1.0

0.9

0.8

0.7

0.8

0.7

0.6

0.5

0.5 0.0

0.2

0.4

0.6

0.8

Accuracy

1.0

0.9

Accuracy

1.0

0.5 0.0

0.2

0.4

0.6

0.8

1.0

0.0

GCN with Ã GCN with Ã threshold

GCN with Â threshold

(b) k = 2. 0.9

0.8

0.7

0.6

0.5

0.5 0.4

0.6

0.8

Accuracy

0.9

Accuracy

0.9

0.7

1.0

0.8

0.7

0.5 0.0

0.2

0.4

0.6

0.8

1.0

0.0

0.2

0.4

GCN with Ã GCN with Ã threshold

GCN with Â threshold

1.0

GCN with Â threshold

0.6

γ Standard GCN GCN with Â (Ours)

0.8

0.6

GCN with Ã GCN with Ã threshold

Standard GCN GCN with Â (Ours)

1.0

0.2

0.4

GCN with Ã GCN with Ã threshold

Standard GCN GCN with Â (Ours)

1.0

0.0

0.2

(a) k = 1.

Accuracy

0.7

0.6

γ Standard GCN GCN with Â (Ours)

0.8

(d) k = 4.

0.6

0.8

1.0

GCN with Ã GCN with Ã threshold

Standard GCN GCN with Â (Ours)

GCN with Â threshold

GCN with Ã GCN with Ã threshold

Standard GCN GCN with Â (Ours)

(e) k = 5.

GCN with Â threshold

(f) k = 6.

1.0

0.9

0.8

0.7

0.8

0.7

0.6

0.5

0.5 10−1

101

100

Accuracy

1.0

Accuracy

Figure 2: Synthetic CSBM accuracy versus graph signal strength.

0.5 10−1

101

100

10−1

MbaGCN Reverse-GNN

Ours threshold

Ours DropEdge

‖μ − ν‖ σ

MbaGCN Reverse-GNN

Ours threshold

Ours DropEdge

(b) k = 2.

0.9

0.8

0.7

0.6

0.5

0.5 10−1

101

100

Accuracy

1.0

Accuracy

1.0

0.7

MbaGCN Reverse-GNN

0.8

0.7

0.5 10−1

101

100

10−1

(d) k = 8.

Ours DropEdge

MbaGCN Reverse-GNN

(e) k = 12.

101

100

‖μ − ν‖ σ

Ours threshold

0.6

‖μ − ν‖ σ

Ours DropEdge

MbaGCN Reverse-GNN

1.0

0.8

101

100

‖μ − ν‖ σ

(a) k = 1.

Accuracy

0.7

0.6

‖μ − ν‖ σ

Ours DropEdge

0.8

‖μ − ν‖ σ

Ours threshold

Ours DropEdge

MbaGCN Reverse-GNN

Ours threshold

(f) k = 16.

Figure 3: Synthetic CSBM comparison with recent oversmoothing baselines under varying feature SNR. Full Dataset Evaluation. On the full datasets, we observe a smaller depth-dependent accuracy drop for corrected propagation than for standard GCN propagation (Figure 6). The effect is smaller than on balanced subsets but remains consistent with the spectral-collapse mechanism. Baseline comparison. Corrected propagation has comparable accuracy to recent baselines on both balanced subsets and full datasets (Figures 7 and 8), while using a training-free operator-level correction.

Discussion and Limitations

The theoretical contribution is threefold. First, normalized corrected propagation is identified as a spectral object in its own right: subtracting the degree-stationary direction of D−1/2 AD−1/2 yields an operator 8

1.0

0.9

0.8

0.7

0.8

0.7

0.6

0.5

0.5 0.0

0.2

0.4

0.6

0.8

Accuracy

1.0

0.9

Accuracy

1.0

0.5 0.0

0.2

0.4

0.6

0.8

1.0

0.0

MbaGCN Reverse-GNN

Ours threshold

Ours DropEdge

Ours threshold

Ours DropEdge

(b) k = 2. 0.9

0.9

0.7

0.8

0.7

0.6

0.5

0.5 0.4

0.6

0.8

1.0

Accuracy

0.9

Accuracy

1.0

0.8

Ours threshold

1.0

0.8

0.7

0.5 0.0

0.2

0.4

0.6

0.8

1.0

0.0

0.2

0.4

MbaGCN Reverse-GNN

0.8

Ours threshold

0.6

γ Ours DropEdge

0.6

MbaGCN Reverse-GNN

1.0

0.2

0.4

MbaGCN Reverse-GNN

1.0

0.0

0.2

(a) k = 1.

Accuracy

0.7

0.6

γ Ours DropEdge

0.8

Ours DropEdge

(d) k = 4.

0.6

0.8

1.0

MbaGCN Reverse-GNN

Ours threshold

Ours DropEdge

(e) k = 5.

MbaGCN Reverse-GNN

Ours threshold

(f) k = 6.

Figure 4: Synthetic CSBM comparison with recent oversmoothing baselines under varying graph signal.

Table 1: Statistics of real-world datasets used in our experiments.

Dataset

Nodes

Edges

Features

Classes

Class Imbalance

Cora CiteSeer PubMed Reddit ogbn-arxiv ogbn-products

2,708 3,327 19,717 232,965 169,343 2,449,029

10,556 9,104 88,648 114,615,892 1,166,243 61,859,140

1,433 3,703 500 602 128 100

7 6 3 41 40 47

Mild Mild Moderate High High High

whose signal direction can remain separated for logarithmically many layers under explicit CSBM conditions. Second, the exact-recovery and partial-recovery theorems connect this spectral correction to node classification guarantees. Third, the proof develops normalized residual-power bounds that are entrywise rather than only spectral-norm bounds, which is the level needed for exact recovery. The main technical message is that normalized correction requires tools beyond the unnormalized analysis. Random degrees enter through nonlinear factors and also appear inside the correction term. Our proof handles these effects by expanding each normalized residual entry into positive-level atoms and then counting the decorated walk patterns that survive in high moments. This is the main normalized-specific component of the theory. Several limitations remain. First, the CSBM does not capture all degree heterogeneity, heterophily, or label semantics in real graphs. Second, the guarantees analyze the linear propagation backbone rather than nonlinear activations, attention, optimization, or learned feature transformations. Third, the binary theorem is proved in the dense polylogarithmic regime np ≥ C logB n for fixed B > 4, leaving the sharper np ≥ C log3 n normalized threshold open. Finally, very large graphs require scalable approximations of the stationary-component correction. 9

Balanced Two-Cluster Sampling on Cora

Balanced Two-Cluster Sampling on PubMed

Balanced Two-Cluster Sampling on CiteSeer

0.925

0.90

0.875 0.900 0.850

0.850 0.825 0.800

Test Accuracy

0.875 0.825 0.800 0.775 0.750 0.775 0.750

0.725

Standard GCN GCN with Â (Ours)

GCN with Ã

0.700

GCN with Ã

0.80

0.75

Standard GCN GCN with Â (Ours)

0.85

Standard GCN GCN with Â (Ours) 0.70

Number of Layers

GCN with Ã 5

(a) Cora.

(b) CiteSeer.

Balanced Two-Cluster Sampling on ogbn-arxiv

Balanced Two-Cluster Sampling on Reddit

Number of Layers

0.99

1.000

0.9

0.975

0.900 0.875

0.825

Standard GCN GCN with Â (Ours)

Test Accuracy

0.925

0.850

0.98

0.8

0.950

0.7

0.6

0.5

Standard GCN GCN with Â (Ours)

0.96

0.95

GCN with Ã

GCN with Ã 0.800

0.97

Standard GCN GCN with Â (Ours) GCN with Ã

0.4 5

(d) Reddit.

Number of Layers

(e) ogbn-arxiv.

(f) ogbn-products.

Figure 5: Accuracy versus propagation depth on balanced two-cluster sampled subsets. Performance Comparison on Cora

Performance Comparison on CiteSeer

Standard GCN GCN with Â (Ours)

0.7

0.55

GCN with Ã

0.70

Test Accuracy

0.5

0.4

Test Accuracy

0.50

0.6

Test Accuracy

Performance Comparison on PubMed 0.75

Standard GCN GCN with Â (Ours)

0.60

0.45 0.40 0.35 0.30

0.65

0.60

0.55

0.3

Standard GCN GCN with Â (Ours)

0.25

0.2

0.50

0.20

Number of Layers

GCN with Ã 5

Number of Layers

(a) Cora.

(b) CiteSeer.

Performance Comparison on Reddit

Number of Layers

Performance Comparison on ogbn-arxiv

Performance Comparison on ogbn-products

Standard GCN GCN with Â (Ours)

0.7

0.9

Standard GCN GCN with Â (Ours)

0.8

GCN with Ã

0.6

GCN with Ã

Standard GCN GCN with Â (Ours)

0.7

GCN with Ã

0.6 0.5 0.4 0.3

Test Accuracy

0.6 0.7

0.5

0.4

0.3

0.2

0.5

0.4

0.3

0.2 5

Number of Layers

(d) Reddit.

Number of Layers

(e) ogbn-arxiv.

Number of Layers

(f) ogbn-products.

Figure 6: Accuracy versus propagation depth on full real-world datasets.

Conclusion and Future Work

We developed a spectral theory of normalized corrected GNN propagation. The main result proves exact recovery in the binary CSBM after k = O(log n) layers under dense polylogarithmic graph density and explicit signal-to-noise assumptions. A multi-class theorem gives partial recovery for most nodes under analogous signal-dominance conditions. The central technical ingredient is entrywise control of normalized residual powers, obtained by atom expansion and decorated-walk counting. Future work includes sharpening the density threshold, extending the theory to heterophilous and degree-heterogeneous models, incorporating nonlinear trained GNN layers, and developing scalable approximations to the stationary correction. 10

Balanced Two-Cluster Sampling on Cora

Balanced Two-Cluster Sampling on CiteSeer

Balanced Two-Cluster Sampling on PubMed 0.925

0.90

0.900

0.80 0.75 0.70

0.875

0.85

Test Accuracy

0.85

0.80

0.75

0.65

0.850 0.825 0.800 0.775 0.750

0.70

0.725

0.60 5

Number of Layers Ours

DropEdge

Number of Layers

MbaGCN

Reverse-GNN

Ours

(a) Cora.

DropEdge

Reverse-GNN

Ours

(b) CiteSeer.

Balanced Two-Cluster Sampling on Reddit

DropEdge

MbaGCN

Reverse-GNN

Balanced Two-Cluster Sampling on ogbn-arxiv

1.00

Number of Layers

MbaGCN

0.90

0.98

0.90

0.85

0.80

Test Accuracy

0.85

Test Accuracy

0.95

0.80 0.75 0.70

0.60

0.70 5

0.90 5

Number of Layers Ours

DropEdge

0.94

0.92

0.65

0.75

0.96

MbaGCN

Reverse-GNN

Ours

(d) Reddit.

DropEdge

Number of Layers

Number of Layers MbaGCN

Ours

Reverse-GNN

(e) ogbn-arxiv.

DropEdge

MbaGCN

Reverse-GNN

(f) ogbn-products.

Figure 7: Balanced-subset comparison with recent oversmoothing baselines. Performance Comparison on Cora

Performance Comparison on CiteSeer

Performance Comparison on PubMed

0.8

0.5 0.4 0.3

Test Accuracy

0.6

Test Accuracy

0.7

0.6

0.7

0.5

0.4

0.3

0.6

0.5

0.4

0.3

0.2 0.2

0.2 5

Number of Layers Ours

DropEdge

Number of Layers

MbaGCN

Reverse-GNN

Ours

(a) Cora.

DropEdge

Reverse-GNN

Ours

(b) CiteSeer.

Performance Comparison on Reddit

Number of Layers

MbaGCN

DropEdge

MbaGCN

Reverse-GNN

Performance Comparison on ogbn-arxiv

Performance Comparison on ogbn-products

0.7 0.70

0.6

0.4

0.2

0.65

Test Accuracy

0.8

0.5

0.4

0.3

0.60 0.55 0.50 0.45 0.40

0.2

0.35

0.1 5

Number of Layers Ours

DropEdge

MbaGCN

(d) Reddit.

Number of Layers Reverse-GNN

Ours

DropEdge

MbaGCN

(e) ogbn-arxiv.

Number of Layers Reverse-GNN

Ours

DropEdge

MbaGCN

Reverse-GNN

(f) ogbn-products.

Figure 8: Full-dataset comparison with recent oversmoothing baselines.

Acknowledgments

This work was supported by the National Key RD Program of China (Grant No. 2023YFA1010202), the Central Guidance on Local Science and Technology Development Fund of Fujian Province (Grant No. 2023L3003), the National Natural Science Foundation of China (Grant No.11901094), the Interdisciplinary Frontier Research Project of PCL (Grant No. 2025QYB015). AI Assistant Declaration: During the preparation of this work, the authors used Gemini and ChatGPT to improve the readability and language of the manuscript, and to assist with LaTeX formatting. After using these tools, the authors reviewed and edited the content as needed and take full responsibility for the content of the publication. 11

References Sam Adam-Day, Michael Benedikt, İsmail İlkan Ceylan, and Ben Finkelshtein. Almost surely asymptotically constant graph neural networks. In Advances in Neural Information Processing Systems, 2024. Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the Expressive Power of Graph Neural Networks in a Spectral Perspective. In International Conference on Learning Representations, 2021. Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi-supervised classification: Improved linear separability and out-of-distribution generalization. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 684–693, 2021. Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of graph convolutions in multi-layer networks. In The Eleventh International Conference on Learning Representations, 2023a. Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Optimality of message-passing architectures for sparse graphs. In Advances in Neural Information Processing Systems, volume 36, pp. 40320–40341, 2023b. Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In International Conference on Learning Representations, 2014. Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. In ICML 2020 Workshop on Graph Representation Learning and Beyond, 2020. Benjamin Paul Chamberlain, James Rowbottom, Maria I Gorinova, Stefan Webb, Emanuele Rossi, and Michael M Bronstein. Grand: Graph neural diffusion. In International Conference on Machine Learning, pp. 1407–1418. PMLR, 2021. Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and Deep Graph Convolutional Networks. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 1725–1735. PMLR, 13–18 Jul 2020. Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive Universal Generalized PageRank Graph Neural Network. In International Conference on Learning Representations, 2021. Guillaume Dalle and Patrick Thiran. Optimal performance of graph convolutional networks on the contextual stochastic block model. In The Third Learning on Graphs Conference, 2024. Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, volume 29, 2016. Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. In Advances in Neural Information Processing Systems (NeurIPS), 2018. O Duranthon and Lenka Zdeborová. Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block model. Physical Review X, 15(4):041026, 2025. Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations (ICLR), 2019. Huseyin Goksu. Krawtchouknet: A unified gnn solution for heterophily and over-smoothing with adaptive bounded polynomials. arXiv preprint arXiv:2511.15327, 2025. William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive Representation Learning on Large Graphs. NIPS’17: Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025–1035, 2017. 12

Xin He, Yili Wang, Wenqi Fan, Xu Shen, Xin Juan, Rui Miao, and Xin Wang. Mamba-based graph convolutional networks: Tackling over-smoothing with selective state space. In Proceedings of the ThirtyFourth International Joint Conference on Artificial Intelligence (IJCAI), pp. 5345–5353, 2025. Yifan Hou, Jian Zhang, James Cheng, Kaili Ma, Richard T. B. Ma, Hongzhi Chen, and Ming-Chang Yang. Measuring and Improving the Use of Graph Information in Graph Neural Networks. In International Conference on Learning Representations, 2020. Yufei Jin and Xingquan Zhu. Oversmoothing alleviation in graph neural networks: A survey and unified view. Knowledge and Information Systems Journal, 2025. Nicolas Keriven. Not Too Little, Not Too Much: A theoretical Analysis of Graph (Over)Smoothing. In Advances in Neural Information Processing Systems, 2022. Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017. Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semisupervised learning. In Thirty-Second AAAI conference on artificial intelligence, 2018. Chen Lu and Subhabrata Sen. Contextual stochastic block model: Sharp thresholds and contiguity. ArXiv, 2020. Zhongtian Ma, Qiaosheng Zhang, Bocheng Zhou, Yexin Zhang, Shuyue Hu, and Zhen Wang. Graph attention is not always beneficial: A theoretical analysis of graph attention mechanisms via contextual stochastic block models. In International Conference on Learning Representations (ICLR), 2025. Sohir Maskey, Ron Levie, Yunseok Lee, and Gitta Kutyniok. Generalization analysis of message passing neural networks on large random graphs. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. Sohir Maskey, Ron Levie, and Gitta Kutyniok. Generalization bounds for message passing networks on mixture of graphons. SIAM Journal on Mathematics of Data Science, 2024. Nikhil Mehta, Lawrence Carin Duke, and Piyush Rai. Stochastic Blockmodels meet Graph Neural Networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 4466–4474, 2019. Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020. MoonJeong Park, Jaeseung Heo, and Dongwoo Kim. Mitigating oversmoothing through reverse process of gnns for heterophilic graphs. In Forty-first International Conference on Machine Learning (ICML), 2024. Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. DropEdge: Towards Deep Graph Convolutional Networks on Node Classification. In International Conference on Learning Representations, 2020. T. Konstantin Rusch, Michael M. Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303.10993, 2023. Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The Graph Neural Network Model. IEEE Transactions on Neural Networks, 20(1), 2009. Michael Scholkemper, Xinyi Wu, Ali Jadbabaie, and Michael T Schaub. Residual connections and normalization can provably prevent oversmoothing in GNNs. In The Thirteenth International Conference on Learning Representations, 2025. David I. Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine, 30(3):83–98, 2013. 13

Jiaqi WANG, Xinyi Wu, James Cheng, and Yifei Wang. A signed graph approach to understanding and mitigating oversmoothing. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2026. Robert Wang, Aseem Baranwal, and Kimon Fountoulakis. Analysis of corrected graph convolutions. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6861–6871, 2019. Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453–5462. PMLR, 2018. Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In International Conference on Learning Representations, 2020.

Mathematical Tools

To rigorously analyze the spectral properties of the corrected graph convolution and its effect on node features, we require a set of fundamental probabilistic and algebraic tools. These tools allow us to bound the spectral norms of random matrices, control eigenvalue perturbations, and manage the concentration of scalar sums that arise from the CSBM’s stochastic generation process. We begin with a foundational result from matrix perturbation theory, which guarantees that small changes to a symmetric matrix result in bounded shifts in its eigenvalues. Theorem A.1. Let A and B be n × n symmetric matrices. Let λ1 ≥ λ2 ≥ · · · ≥ λn and µ1 ≥ µ2 ≥ · · · ≥ µn be the eigenvalues of A and B, respectively. If ∥A − B∥ ≤ δ, then maxi |λi − µi | ≤ δ. Furthermore, we often need to bound the spectral norm of specific sparse symmetric matrices encountered in our graph constructions. The following theorem provides a general upper bound based on row sparsity and entry magnitude. Theorem 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 ∥ ≤ ϵm. While spectral bounds control the global operator behavior, local graph properties, such as node degrees and edge counts, are sums of independent Bernoulli random variables. To establish high-probability bounds on these quantities, we employ the standard Chernoff concentration inequality. Theorem Pn A.3. Let X1 , ...Xn be independent Bernoulli random variables with mean at most p, and let Sn = i=1 Xi . Then for any t > 0, 2 t Pr [|Sn − E[Sn ]| > t] ≤ exp −Ω . E[Sn ] In the analysis of multi-layer graph convolutions, terms involving products and powers of (1 + x) frequently emerge. To simplify these expressions while maintaining tight bounds, we utilize the following standard exponential inequalities. Theorem A.4. For all x ∈ R, 1 + x ≤ ex . Furthermore, if x ≤ 1, then ex ≤ 1 + 2x. Finally, since the initial node features in our CSBM framework are drawn from Gaussian mixture models, we rely on the concentration of Gaussian random vectors to bound the noise propagation. Theorem A.5. Let g ∼ N (0, σ 2 In ) be a random Gaussian vector. Then for any t > 0, t2 Pr [∥g∥ > t] ≤ 2 exp − . 2nσ 2

Additional Preliminaries and Lemmas

We recall the spectral theorem for real symmetric matrices. If M ∈ Rn×n is symmetric, it admits an Pn eigendecomposition M = i=1 λi wi wi⊤ , where λ1 , . . . , λn ∈ R are the eigenvalues and w1 , . . . , wn ∈ Rn form an orthonormal basis of eigenvectors. In this case, the operator norm satisfies ∥M ∥ = maxi |λi |. Additionally, we denote the multivariate Gaussian distribution with mean vector µ and covariance matrix Σ by N (µ, Σ). For a scalar random variable X ∼ N (µ, σ 2 ), we utilize the standard tail bound: 2 t Pr [|X − µ| > tσ] ≤ exp − . 2 A key insight from Baranwal et al. (2021) establishes that the analysis of linear classifiers on general mdimensional CSBMs can be effectively mapped to a simpler one-dimensional setting. To formalize this, we introduce the following definition: 15

Definition B.1 (One-Dimensional Centered CSBM). A CSBM is said to be one-dimensional and centered with parameters n, p, q, σ, if the feature dimensionality is m = 1. In this model, the single feature vector x ∈ Rn is decomposed as x = s + g, where: • g ∼ N (0, σ 2 In ) represents the Gaussian noise vector. • s ∈ Rn is the signal vector defined by class membership: ( √1 if i ∈ S, si = −1n √ if i ∈ T. n This construction ensures that the signal vector s has a unit norm (∥s∥ = 1), simplifying subsequent notation. The lemma presented below enables the reduction of linear classifier analysis from the general CSBM to the centered 1-dimensional model. Accordingly, our proof strategy for the main theorems begins with the 1-dimensional case, subsequently applying Lemma B.2 to extend the results. Lemma B.2. Consider an m-dimensional balanced two-block CSBM(n, m, p, q, µ, ν, σ) with p > q > 0 with centered feature means µ + ν = 0 and µ = ̸ ν. Let si = n−1/2 on S and si = −n−1/2 on T . Then the projection w= √

2(µ − ν) n ∥µ − ν∥2

satisfies Xw = s + g, Consequently, for every k ≥ 1,

g ∼ N (0, σ ′2 In ),

σ′ = √

2σ . n ∥µ − ν∥

bk Xw = A bk (s + g). A

Thus any sign-separation result for the one-dimensional centered model transfers to the original CSBM through the linear classifier with normal vector w. Proof. It follows from µ + ν = 0 that ν = −µ,

µ − ν = 2µ.

For each vertex i, the feature vector can be written as ( µ + ξi , xi = ν + ξi ,

i ∈ S, i ∈ T,

where ξi ∼ N (0, σ 2 Im ) are independent. Recall that w= √ Then, if i ∈ S, µ⊤ w = µ⊤ √

2(µ − ν) . n ∥µ − ν∥2

2(µ − ν) 2µ⊤ (2µ) 1 √ = =√ . n ∥µ − ν∥2 n ∥2µ∥2 n

Similarly, if i ∈ T , since ν = −µ, we also have 1 ν⊤w = − √ . n Therefore

⊤ x⊤ i w = si + ξi w.

Define

gi := ξi⊤ w.

Since the vectors ξi are independent Gaussian vectors with distribution N (0, σ 2 Im ), the variables gi are independent centered Gaussian random variables. Moreover, Var(gi ) = σ 2 ∥w∥2 . By the definition of w, ∥w∥2 = which implies that

4 4∥µ − ν∥2 = , n∥µ − ν∥4 n∥µ − ν∥2

gi ∼ N 0,

4σ 2 n∥µ − ν∥2

Equivalently, gi ∼ N (0, σ ′2 ), Thus, in vector form, where g = (g1 , . . . , gn )

σ′ = √

2σ . n ∥µ − ν∥

Xw = s + g, ⊤

has independent coordinates distributed as N (0, σ ′2 ).

b acts on the vertex coordinate and w is fixed in the feature coordinate, we have, for every integer Since A k ≥ 1, bk Xw = A bk (Xw) = A bk (s + g). A bk (s + g) have signs agreeing with the true community labels, then If the coordinates of A bk X)i w = sign (A bk (s + g))i sign (A bk X are linearly separable by the hyperplane with correctly classifies every vertex i. Hence the rows of A normal vector w and threshold 0. In the 1-dimensional model, the presence of the signal s in the feature space is immediate. Furthermore, the convolution matrix effectively captures this signal, as it can be modeled as a perturbation of the signal matrix ss⊤ . Following the framework of (Wang et al., 2024), the un-normalized convolution matrix Ã admits the decomposition 1 Ã = ηss⊤ + R + d′ 11⊤ d

(2)

where η := (p−q)n represents the signal strength, d′ := (p+q)n−2d denotes the average degree deviation, and R 2d 2nd is the “edge-deviation" matrix defined by Ri,j = Ai,j − E[Ai,j ]. The expected signal strength ratio is defined as γ = |p−q| p+q . As established in (Wang et al., 2024), since R consists of i.i.d. zero-mean entries with bounded variance, and d′ is controlled by degree concentration, the matrix Ã concentrates around γss⊤ . This behavior b as well. The relevant concentration bounds from (Wang extends to the normalized convolution matrix A et al., 2024) are summarized in the following proposition. Our analysis commences with a spectral norm bound for the corrected graph convolution matrix. Lemma B.3 b and Ã. Control over this spectral norm is fundamental bounds the spectral norm of the deviation between A to limiting error propagation across network layers. Lemma B.3. Suppose that p = Ω(log n/n) and p > q > 0. Then, there exists a constant C > 0 such that with probability at least 1 − n−Ω(1) , s b − A∥ e ≤C ∥A 17

log n . np

Proof. Let

(p + q)n d¯ := , 2

ε := K

log n , np

where K > 0 is a sufficiently large absolute constant. Since q ≤ p, we have d¯ = Θ(np). For each vertex v, its degree dv is a sum of independent Bernoulli random variables and Edv = d¯ + O(p). The O(p) term comes from excluding the vertex v itself from its own community and is negligible compared with d¯ = Θ(np). By Theorem A.3, ¯ P |dv − Edv | > εd/2 ≤ 2 exp −cε2 d¯ ≤ 2 exp(−c′ K 2 log n). Taking K large enough and applying a union bound over all v ∈ [n], we obtain, with probability at least 1 − n−Ω(1) , ¯ − ε), d(1 ¯ + ε)] dv ∈ [d(1

for every v ∈ [n].

(3)

On this event, n

1X ¯ − ε), d(1 ¯ + ε)]. dv ∈ [d(1 n v=1

(4)

b − A∥. e Recall that Now we bound ∥A 1 1 ⊤ 1/2 ⊤ 1/2 b−A e = D−1/2 AD−1/2 − 1 A − A D 11 D − 11 . d 1⊤ D1 n It is enough to bound the two terms separately. Let 1 M1 := D−1/2 AD−1/2 − A. d Then M1 is symmetric, and for every u, v, (M1 )uv = Auv By (3) and (4), we have √ Moreover,

√

1 1 − d du dv

1 1 Cε − ≤ . d du dv d¯

∆(G) := max dv ≤ 2d¯ v

for all sufficiently large n. Therefore every row of M1 has absolute row sum at most X

|(M1 )uv | ≤ du ·

Cε ≤ C ′ ε. d¯

Applying Theorem A.2 gives that ∥M1 ∥ ≤ C ′ ε. Next let M2 :=

1 1 D1/2 11⊤ D1/2 − 11⊤ . 1⊤ D1 n 18

(5)

Then M2 is symmetric and its entries are

√ du dv 1 P (M2 )uv = n − . n d w=1 w

Again (3) and the fact

n X

¯ − ε), nd(1 ¯ + ε)], dw ∈ [nd(1

w=1

we obtain

√ Cε 1 d d Pu v − ≤ . d n n w w Thus every row of M2 has absolute row sum at most X Cε |(M2 )uv | ≤ n · = Cε. n v

Applying Theorem A.2 again gives that (6)

∥M2 ∥ ≤ Cε. Combining (5) and (6) gives s b − A∥ e ≤ ∥M1 ∥ + ∥M2 ∥ ≤ Cε = CK ∥A

log n . np

Absorbing K into the constant C, we conclude s b − A∥ e ≤C ∥A

log n . np

This completes the proof. Lemma B.4. Assume that p ≥ C logn n and p > q > 0. Let γ :=

p−q , p+q

(p + q)n d¯ := , 2

η :=

(p − q)n , 2d

d′ :=

d¯ − d . nd

Then, with probability at least 1 − n−Ω(1) , the empirical average degree d satisfies s !! log n d = d¯ 1 + O . n2 p Consequently, the deviations of η and d′ are bounded by √ log n |η − γ| ≤ C √ , n p

√ ′

|d | ≤ C

log n √ . n2 p

Moreover, let R := A − EA denote the centered adjacency fluctuation. Then the spectral norms are bounded as follows: √ e − γss⊤ ≤ √C . ∥R∥ ≤ C np, A np Finally, combined with Lemma B.3, we have s log n ⊤ b − γss A ≤C . np Consequently, s b − ηss A

⊤

≤C

log n . np

Proof. Note that d = 2|E|/n is the average degree and |E| is a sum of independent Bernoulli random variables with n2 E|E| = (p + q) + O(np). 4 We have Ed = d¯ + O(p). Note that the variance of |E| is at most Cn2 p. By Theorem A.3, with probability at least 1 − n−Ω(1) , p ||E| − E|E|| ≤ Cn p log n. Therefore

¯ ≤C |d − d|

p log n.

Since d¯ = Θ(np), this implies

d = d¯ 1 + O

√

p log n np

= d¯ 1 + O

log n n2 p

!! .

We now estimate η − γ. By definition, η=

(p − q)n , 2d

Hence |η − γ| =

γ=

p−q (p − q)n = . p+q 2d¯

¯ (p − q)n 1 1 (p − q)n |d − d| . − = 2 d d¯ 2 dd¯

Using d, d¯ = Θ(np), p − q ≤ p + q = O(p), and ¯ ≤C |d − d|

p log n,

we obtain √ √ np p log n log n |η − γ| ≤ C =C √ . n2 p2 n p

(7)

√ √ |d¯ − d| C p log n log n ≤ = C 2√ . |d | = nd n · np n p

(8)

Similarly, ′

Next we control the centered adjacency matrix R = A − EA. The entries of R are independent above the diagonal, centered, and bounded by 1, with variances at most p. By a standard spectral norm bound for sparse centered adjacency matrices, since p ≥ C log n/n, with probability at least 1 − n−Ω(1) , √ ∥R∥ ≤ C np.

(9)

e Up to the harmless diagonal correction, which has operator norm O(1/d) = O(1/(np)), We now decompose A. the expectation of A can be written as EA =

p+q ⊤ p−q ⊤ 11 + yy , 2 2 20

√ where yi = 1 on S and yi = −1 on T . It follows from s = y/ n that yy ⊤ = nss⊤ . Thus

1 1 EA − 11⊤ = ηss⊤ + d′ 11⊤ + Ediag , d n

where ∥Ediag ∥ ≤ Therefore

C C ≤ . d np

(10)

e = 1 A − 1 11⊤ = ηss⊤ + 1 R + d′ 11⊤ + Ediag . A d n d

Consequently,

e − γss⊤ = (η − γ)ss⊤ + 1 R + d′ 11⊤ + Ediag . A d

Taking operator norms gives e − γss⊤ ≤ |η − γ| + 1 ∥R∥ + |d′ |∥11⊤ ∥ + ∥Ediag ∥. A d It follows from the fact p ≥ C log n/n that √

log n C √ ≤√ . n p np

This together with (7), (8), (9) and (10) yields that e − γss⊤ ≤ √C . A np By Lemma B.3, we have that

s b−A e ≤C A

log n . np

Therefore,

s e − γss⊤ ≤ C b−A e + A b − γss⊤ ≤ A A

log n , np

and then together with (7), this implies s b − ηss⊤ ≤ A b − γss⊤ + |γ − η| ≤ C A

log n . np

This completes the proof. √ For the next lemma, let yi = n si ∈ {±1}. For an unordered edge e = {r, t}, write ξe = Art − EArt . An atom is one monomial term produced by the finite Taylor expansion of a single normalized-residual entry and has the form ma X Y a(i, j) = ca χa (i, j) n−ba d¯−qa ξe (ϕ) , h

ϕ∈Φa (i,j) h=1

where d¯ = (p + q)n/2, χa (i, j) ∈ {1, yi , yj , yi yj }, and Φa (i, j) is the finite set of auxiliary vertex choices generated by local and global degree sums. For ϕ ∈ Φa (i, j), eh (ϕ) is the h-th centered edge variable selected by that auxiliary choice. The integer ma counts centered edge variables, qa is the power of d¯−1 , and ba records powers of n−1 from global degree averages. The atom level is λa := 2qa − ma . 21

b − ηss⊤ , where η = (p − q)n/(2d), and fix B > 4. Assume p ≥ Cd logB n/n. Fix Lemma B.5. Let R′ = A A0 > 0, let M ≤ A0 log n, and set L +1 log n ∗ L∗ := K0 M, τ := C √ , np where K0 is sufficiently large depending only on A0 . There is an event G with P(G c ) ≤ exp(−c log2 n), a clipped residual Rcl , and a decomposition Rcl = Rpol + Rrem ,

Rcl = R′

on G,

such that, with the atom notation above, (Rpol )ij =

(i, j ∈ [n]),

a(i, j)

a∈A

for a finite deterministic atom family A satisfying λa ≥ 1,

#{a ∈ A : λa = λ} ≤ C λ .

ma ≤ Cλa ,

Deterministic diagonal/no-self atoms have q = 1, m = 0 and are contracted before the centered-edge skeleton is counted. On G, ∥Rrem ∥∞→∞ ≤ Cτ, ∥Rcl ∥∞→∞ + ∥Rpol ∥∞→∞ ≤ C. Proof. Off-diagonal decomposition. We first isolate the degree-normalization factors in one off-diagonal entry. Write d − d¯ di − d¯ , β := . βi := d¯ d¯ ¯ + βi ) and d = d(1 ¯ + β). For i ̸= j, define Then di = d(1 Fij := (1 + βi )−1/2 (1 + βj )−1/2 = p and Gij := (1 + βi )

1/2

(1 + βj )

1/2

(1 + β)

It is easy to see that (D

−1/2

Aij )ij = Fij , d¯

and

−1

d¯ , di dj

p di dj = . ¯ + β) d(1

p di dj 1 = G . 1⊤ D1 n ij

For i ̸= j,

yi yj d¯ (1 + γyi yj ), η = γ(1 + β)−1 , si sj = . n n b − ηss⊤ gives the off-diagonal decomposition Substituting Aij = EAij + ξij into R′ = A EAij =

′ Rij =

γyi yj ξij 1 Fij + Fij − Gij + Fij − (1 + β)−1 . ¯ n n d

(11)

The right-hand side vanishes at the idealized deterministic point ξ = 0, βi = βj = β = 0. The actual no-self offset Edi − d¯ = O(p) is deterministic of size O(1/n) after normalization and is charged as a deterministic atom with q = 1, m = 0. We next expand the degree-normalization factors. This is where clipping is used: it makes the Taylor expansion globally defined while leaving the matrix unchanged on the high-probability event below. Define the event G by X √ √ max |di − Edi | ≤ C np log n, dv − nd¯ ≤ Cn p log n. i

Chernoff bounds and a union bound give P(G c ) ≤ exp(−c log2 n), and on G all degree fluctuations in (11) √ have absolute value O(log n/ np) < c∗ after increasing Cd . In particular, 1 + βi , 1 + βj , and 1 + β are bounded away from zero on G, so the factors Fij and Gij are well-defined and uniformly bounded there. Replace x−1/2 , x1/2 , and x−1 by smooth clipped functions agreeing with them on [1 − c∗ , 1 + c∗ ]. Taylor (−j) (−i) expand each clipped function to depth L∗ around leave-one-out degrees di , dj , and the global average d. ¯ each Atom expansion. The polynomial Taylor terms give P Rpol . Each exposed edge contributes ξij /d, P −1 −1 ¯ ¯ local degree decoration contributes d ℓ̸=i,j ξiℓ or d ℓ̸=i,j ξjℓ , and each global decoration contributes P n−1 d¯−1 r<s ξrs . In the atom notation, the auxiliary map ϕ records the choices of vertices in these sums. Thus an atom with ma centered edge variables and qa powers of d¯−1 has level 2qa − ma . The cancellation in (A) removes all level-zero deterministic terms. Exposed-edge and local/global degree atoms have level at least one, deterministic no-self atoms have level two, and the number of Taylor multi-indices of level λ is at most C λ . This proves the atom bounds. Remainder bound. The Taylor remainders form Rrem . On G, every normalized degree fluctuation W appearing in a remainder, such as a local leave-one-out degree fluctuation, a global average-degree fluctuation, ¯ satisfies |W | ≤ C log n/√np, so or the exposed-edge term Aij /d, |ρα,L∗ (W )| ≤

L +1 log n ∗ C√ = τ. np

Remainder terms in the adjacency part have row sums at most Cτ , and remainder terms in the stationary correction have entries at most Cτ /n. The displayed ℓ∞ → ℓ∞ bounds follow from the degree concentration on G. Lemma B.6. Consider a product of 2r path monomials obtained from the atoms in Lemma B.5. Suppose the product has 2M residual positions and total level Λ = 2M + h. After summing over all canonical decorated patterns of this level and over all vertex assignments, the total contribution to the 2r-th moment is at most n−r (CM )M (np)−M

CM √ np

h .

Proof. For a fixed product, let m be the total number of centered edge variables before identification, let ℓ be the number of distinct centered edges after identification, and let Q be the total d¯−1 -charge. By the definition of level, Λ m Q− = . 2 2 The expectation is zero unless every centered edge appears at least twice; hence ℓ ≤ m/2. For a nonzero pattern, Y E ξeνe ≤ C m pℓ , νe ≥ 2. e

P Global decorations have factors n−1 d¯−1 r<s ξrs . If a global-only edge is not identified with the local path skeleton, its two free endpoints give at most n2 choices and the two corresponding global normalizations give n−2 . Hence global-only decorations do not create a positive power of n. After these cancellations, reveal the remaining canonical skeleton from the fixed root u. If F is the number of new free vertices, each first appears through a centered edge that is paired later, so F ≤ ℓ. The 2r terminal factors sva contribute n−r , and the total vertex factor is at most nℓ−r . For one fixed canonical pattern, the contribution is therefore bounded by nℓ−r pℓ (np)−Q = n−r (np)ℓ−Q ≤ n−r (np)−Λ/2 . It remains to count canonical patterns. The 2M residual positions, their paired first occurrences, and the choices of atom sources give at most (CM )M possibilities at base level 2M . The extra level h, coming 23

from additional Taylor decorations or deterministic charges, contributes at most (CM )h choices. Thus the contribution of all patterns of level Λ = 2M + h is at most n

−r

(CM ) (np) M

−M

CM √ np

h ,

as claimed. b − ηss⊤ , where η = (p − q)n/(2d). Fix B > 4, and assume p ≥ Cd logB n/n. Fix Lemma B.7. Let R′ = A A0 > 0. For every M ≤ A0 log n, every pair (a, r) with ar = M , and every u ∈ [n], there is a decomposition ′a (M ) (M ) e⊤ u R s = Zu,a + Eu,a

such that (M ) 2r E|Eu,a | ≤ n−r (CM )M (np)−M ,

(M ) 2r E|Zu,a | ≤ n−r (CM )M (np)−M .

The constant C depends only on A0 and B. Proof. Apply Lemma B.5 with this value of M . On the event G, we have R′ = Rcl = Rpol + Rrem ,

∥Rpol ∥∞→∞ + ∥Rcl ∥∞→∞ ≤ C,

∥Rrem ∥∞→∞ ≤ Cτ,

where τ= Expand a e⊤ u Rpol s =

log n C√ np

a X Y

K0 M +1 .

(Rpol )vt−1 vt sva ,

v0 = u.

v1 ,...,va t=1

The level of a path monomial is the sum of the levels of its a atoms. Since all atoms have level at least one, (M ) every path monomial has level at least a. Let Zu,a be the sum of all level-a path monomials and define (M ) ′a (M ) Eu,a := e⊤ u R s − Zu,a . (M )

(M )

We first bound Zu,a . Every monomial appearing in |Zu,a |2r has 2M = 2ar residual positions and total level 2M . Applying Lemma B.6 with h = 0 gives (M ) 2r E|Zu,a | ≤ n−r (CM )M (np)−M .

On G, decompose

(M ) Eu,a = Epol + ETay ,

where Epol is the sum of polynomial path monomials of level at least a + 1, and ETay contains all paths with at least one Rrem factor. In |Epol |2r , terms of total level 2M + h with h ≥ 1 contribute at most n−r (CM )M (np)−M

CM √ np

by Lemma B.6. Since M ≤ A0 log n and np ≥ Cd logB n with B > 4, increasing Cd gives CM 1 ≤ . √ np 2 Summing the geometric series over h ≥ 1 yields E|Epol |2r 1G ≤ n−r (CM )M (np)−M . 24

For the Taylor-remainder part, the row-sum bounds from Lemma B.5 imply a a ETay = e⊤ u (Rcl − Rpol )s =

a−1 X

a−1−t t e⊤ s, u Rcl Rrem Rpol

t=0

and therefore, using ∥s∥∞ = n−1/2 ,

aC a τ |ETay |1G ≤ √ . n

Hence

E |ETay |2r 1G ≤ n−r (Ca)2r τ 2r .

Because M = ar, (Ca)2r ≤ (CM )M . Choosing K0 large and then Cd large gives τ 2 ≤ (np)−M , so

E |ETay |2r 1G ≤ n−r (CM )M (np)−M .

It remains to handle G c . Under the conventions before (1), the true and clipped residual matrices have absolute row sums at most nC . Thus, after taking the 2r-th power, ′a e⊤ uR s

a + e⊤ u Rcl s

≤ exp(Car log n) = exp(CM log n).

Since M ≤ A0 log n, r ≤ M , and np ≤ n, the target scale is at least exp(−CA0 log2 n). Taking the constant in the definition of G sufficiently large gives exp(CM log n)P(G c ) ≤ n−r (CM )M (np)−M . Combining the Z, polynomial-error, Taylor-error, and bad-event bounds, and absorbing fixed factors from |x + y + z|2r into (CM )M , proves (M ) 2r E|Eu,a | ≤ n−r (CM )M (np)−M . (M )

Together with the bound for Zu,a , this proves the lemma. Lemma B.8. Let ( b − ηss⊤ , R := A ′

si =

n−1/2 , −n−1/2 ,

i ∈ S, i ∈ T,

η :=

(p − q)n . 2d

Assume

logB n n for a fixed B > 4 and sufficiently large Cd = Cd (B). Let A0 > 0 be fixed. Then there exists a constant C = C(A0 , B) > 0 such that, for every u ∈ [n] and every pair of integers a, r ≥ 1 satisfying ar ≤ A0 log n, ar Car ′a 2r −r E e⊤ R s ≤ n . u np p ≥ Cd

Proof. Set M := ar. By Lemma B.7, with

′a (M ) (M ) e⊤ u R s = Zu,a + Eu,a ,

(M ) 2r E|Eu,a | ≤ n−r (CM )M (np)−M ,

(M ) 2r E|Zu,a | ≤ n−r (CM )M (np)−M .

After increasing C, n−r (CM )M (np)−M ≤ n−r

Car np

ar .

The elementary inequality |x + y|2r ≤ 22r−1 (|x|2r + |y|2r ) and the fact that r ≤ M ≤ A0 log n allow the factor 22r to be absorbed into the constant C. This gives the claimed bound. 25

Lemma B.9. Let b − ηss⊤ , R′ := A Assume p ≥ Cd

η :=

logB n , n

(p − q)n . 2d

1 ≤ k ≤ c log n,

where B > 4 is fixed, Cd = Cd (B) is sufficiently large, and c > 0 is sufficiently small. Then there exists a constant K > 0 such that, with probability at least 1 − n−Ω(1) , p (K log n/(np))a ⊤ ′a √ ∀u ∈ [n], ∀1 ≤ a ≤ k : eu R s ≤ . n Proof. Fix u ∈ [n] and 1 ≤ a ≤ k. Choose A1 log n ra := , a

where A1 is a sufficiently large absolute constant. Since a ≤ k ≤ c log n, by taking c ≤ A1 we have A1 log n ≤ ara ≤ (A1 + c) log n ≤ 2A1 log n. Applying Lemma B.8 with its fixed parameter A0 = 2A1 and with r = ra gives ara Cara ′a 2ra −ra E|e⊤ R s| ≤ n . u np Let Ta :=

log n/(np))a √ . n

By Markov’s inequality, ′a P(|e⊤ u R s| > Ta ) ≤

Cara K 2 log n

ara .

Since ara ≍ A1 log n, choosing A1 fixed and then K sufficiently large in terms of A1 yields ′a −30 P(|e⊤ . u R s| > Ta ) ≤ n

A union bound over all u ∈ [n] and all 1 ≤ a ≤ k ≤ c log n gives failure probability at most n log n·n−30 ≤ n−28 . This proves the claimed uniform bound. q n Lemma B.10. Let η > 0 and θ := C log np . Assume the decomposition b = ηss⊤ + R′ , A satisfies the spectral norm bound ∥R′ ∥ ≤ θ and the entrywise Krylov bound θa ′a |e⊤ u R s| ≤ √ n for all u ∈ [n] and 1 ≤ a ≤ k. Let g ∼ N (0, σ ′2 In ) be independent of the graph. If 1 ≤ k ≤ C0 log n and kθ/η ≤ c for a sufficiently small constant c > 0, then, with probability at least 1 − n−Ω(1) conditional on the graph event above, ! √ k p kθ/η σ ′ log n θ ′ −k bk √ η A (s + g) − s ≤C √ + + σ log n . η n n ∞ 26

b = ηP + R′ . We first control the signal part. Expand Proof. Write P := ss⊤ , so that P 2 = P , P s = s, and A (ηP + R′ )k s into words in the two letters ηP and R′ . The all-projector word equals η k s. We claim that every other word with exactly j ≥ 1 copies of R′ contributes, after division by η k , at most 1 √ n

j θ η

in ℓ∞ -norm. If the word has no P , then it is R′k s, and the claim is exactly the assumed Krylov bound. Now suppose the word contains at least one P . After deleting consecutive projectors and using P s = s, the action of the word on s is a product of blocks of the form R′a separated by projectors P . Each interior projector turns the vector to a multiple of s: P R′a s = s(s⊤ R′a s). The scalar is bounded by

|s⊤ R′a s| ≤ ∥R′a s∥2 ≤ θa ,

and the last block, if it is not followed by a projector on the left, is controlled coordinatewise by θa ∥R′a s∥∞ ≤ √ n √ from the Krylov assumption. Thus a word with j total R′ -factors has coordinate size at most η k−j θj / n. Dividing by η k proves the claim. Summing over the at most kj choices of the R′ -positions gives η

k j θ Ckθ/η C X k A s−s ≤√ ≤ √ . η n j=1 j n ∞

−k bk

Next we control the Gaussian part. Conditional on the graph, the pure projector word gives η −k (ηP )k g = P g = s(s⊤ g). Since s⊤ g ∼ N (0, σ ′2 ), a standard Gaussian tail bound gives √ σ ′ log n ∥P g∥∞ ≤ C √ n with probability at least 1 − n−Ω(1) . For the pure R′ -word, for every u, ′k ′2 ⊤ ′k 2 e⊤ , u R g ∼ N 0, σ ∥eu R ∥

′k ′ k k ∥e⊤ u R ∥ ≤ ∥R ∥ ≤ θ .

A union bound over u ∈ [n] yields ′k ′ k max |e⊤ u R g| ≤ Cσ θ

log n

with probability at least 1 − n−Ω(1) . Hence the pure R′ -word contributes at most k p θ C σ ′ log n. η It remains to check the mixed words, namely those containing at least one projector and at least one R′ . Fix such a word W with j copies of R′ . Let ηP be the rightmost projector letter in W . Then W g = U (ηP )R′a g = η U s (s⊤ R′a g), 27

where 0 ≤ a ≤ j is the number of consecutive R′ -letters to the right of this projector, and U is the prefix to its left. The prefix U contains exactly j − a copies of R′ and k − j − 1 copies of ηP . For the scalar, s⊤ R′a g ∼ N 0, σ ′2 ∥s⊤ R′a ∥2 , ∥s⊤ R′a ∥ ≤ θa with the convention θ0 = 1. Hence, by a union bound over 0 ≤ a ≤ k, p |s⊤ R′a g| ≤ Cσ ′ θa log n with probability at least 1 − n−Ω(1) . Applying the signal-word bound proved above, with k replaced by the length of the prefix, gives η k−j−1 θj−a √ ∥U s∥∞ ≤ , n because U has j − a residual letters and k − j − 1 projector letters. Therefore, after division by η k , the word contributes at most √ j σ ′ log n θ . C √ η n There are at most kj such words with j copies of R′ . Consequently the total mixed contribution is bounded by √ √ k−1 j θ σ ′ log n σ ′ log n X k ≤C √ , C √ j η n n j=1 where the last inequality follows from (1 + θ/η)k − 1 ≤ 2kθ/η ≤ C under kθ/η ≤ c. Combining the signal estimate, the pure projector noise estimate, the mixed Gaussian estimate, and the pure R′k g estimate proves the lemma. To prove our multi-class results (Theorem 4.7), we first characterize the unnormalized convolution matrix Ã in terms of its expected behavior and a bounded random perturbation. These fundamental characterizations for the unnormalized setting were established by (Wang et al., 2024). Lemma B.11 (Multi-class Characterization for Ã (Wang et al., 2024)). In the multi-class setting, the unnormalized convolution matrix, Ã, can be decomposed as Ã = M + R′ where: • M is symmetric and has rank L − 1: its nonzero eigenvalues are all equal to λ = (p−q)n , and the ¯ dL remaining eigenvalues are zero. Also, M U = λU . • R′ isqa random matrix such that with probability at least 1 − n−Ω(1) , ∥R′ ∥ ≤ δ where δ = p C( d1¯( np(1−p) + nq(1 − q))). L We also need to bound the operator norm distance between the k th convolution and M k , which directly follows from the properties of Ã. Lemma B.12 (Operator Norm Bound for Ãk (Wang et al., 2024)). Suppose |λ| > 4kδ. Then with high probability, we have 1 2kδ (Ãk − M k ) ≤ . k λ |λ| Lemma B.13 (Normalization perturbation for multi-class CSBM). In the multi-class CSBM, let pn (L − 1)qn d¯ = + L L and assume d¯ ≥ C log n. Then, with probability at least 1 − n−Ω(1) , r b − A∥ e ≤ C log n . ∥A d¯ 28

Proof. Let ϵ = C0 For every vertex v,

log n . d¯

Edv = (n/L − 1)p + (n − n/L)q = d¯ − p,

so Edv = d¯ + O(p). Since d¯ ≥ C log n, Chernoff’s inequality and a union bound give, with probability 1 − n−Ω(1) , 1X ¯ − ϵ), d(1 ¯ + ϵ)] for all v, ¯ − ϵ), d(1 ¯ + ϵ)] dv ∈ [d(1 d= dv ∈ [d(1 n v after increasing C0 . On this event, b−A e= A

1/2 ⊤ 1/2 D 11 D 1 ⊤ 1 − 11 . D−1/2 AD−1/2 − A − d 1⊤ D 1 n

For the first term, √

1 Cϵ 1 ≤ − . d du dv d¯

¯ every row has absolute row sum at most Cϵ. The matrix is symmetric, hence its operator Since du ≤ 2d, norm is at most Cϵ. For the second term, √ d d Cϵ 1 Pu v − ≤ , d n n w w so every row has absolute row sum at most Cϵ, and again the operator norm is at most Cϵ. Combining the two estimates proves the lemma.

Proofs of Main Theorems

C.1

Proof of Theorem 4.3

Proof. Let ( si =

n−1/2 , −n−1/2 ,

i ∈ S, i ∈ T,

η=

(p − q)n , 2d

b − ηss⊤ . R′ = A

b = ηss⊤ + R′ . By Lemma B.4, and by choosing the constant hidden in p ≥ ΩB (logB n/n) sufficiently Then A large, with probability 1 − n−Ω(1) , s √ log n log n |η − γ| ≤ C √ , ∥R′ ∥ ≤ C =: θ. n p np By the graph-signal assumption, with the constant hidden in ΩB (·) chosen sufficiently large, kθ/γ is smaller than the absolute constant required below. Increasing constants if necessary gives η ≍ γ and θ/η ≤ 2θ/γ. By Lemma B.2, there exists w ∈ Rm such that Xw = s + g,

g ∼ N (0, σ ′2 In ),

σ′ = √

2σ . n ∥µ − ν∥

bk Xw = A bk (s + g). Lemma B.9 gives, on the same high-probability graph event, Hence A θa ′a √ |e⊤ R s| ≤ , u n

∀u ∈ [n], 1 ≤ a ≤ k, 29

after increasing θ by an absolute factor. The use of Lemma B.9 is legitimate because the constant hidden in k = OB (log n) is chosen no larger than the constant c in that lemma. Applying Lemma B.10 therefore yields ! √ k p kθ/η σ ′ log n θ −k bk ′ √ η A (s + g) − s ≤C √ + σ log n . + η n n ∞ √ The first term is at most 1/(10 n) by the graph-signal assumption. Since η ≍ γ, the constant CB in the SNR condition is chosen √ larger than the absolute constants hidden in θ/η. The two remaining terms are therefore at most 1/(10 n) each by the assumed lower bound on ∥µ − ν∥/σ, together with σ′ = √

2σ . n ∥µ − ν∥

Thus bk (s + g) − s η −k A

∞

1 < √ . 2 n

bk (s + g), and hence of A bk (s + g), agree with the Every coordinate of s equals ±n−1/2 , so the signs of η −k A k k b b true labels. Since A Xw = A (s + g), the hyperplane with normal vector w and threshold zero separates the bk X. A union bound over the graph and Gaussian events gives failure probability n−Ω(1) . rows of A C.2

Proof of Theorem 4.7

Proof. We work on the high-probability graph event on which e = M + R, A

∥R∥ ≤ δ,

from Lemma B.11. Because L is fixed, the probability losses and constants in the multi-class spectral estimates are absorbed into n−Ω(1) and the displayed absolute constants. By Lemma B.13, on the same event after a union bound, the degree-normalization perturbation satisfies b − A, e Enorm := A Hence

b = M + H, A

∥Enorm ∥ ≤ ϵ.

H := R + Enorm ,

∥H∥ ≤ δ + ϵ.

Since M has rank L − 1 and satisfies M U = λU , we also have M U = λk U . k

Let X = U + G, where G has independent N (0, σ 2 ) entries. Then bk U − U + λ−k A bk G. X (k) − U = λ−k A Using ∥A + B∥2F ≤ 2∥A∥2F + 2∥B∥2F , it is enough to control the signal term and the Gaussian term separately. Signal term. For the signal part, bk U − U = λ−k (A bk − M k )U. λ−k A We decompose

bk − M k = (A bk − A ek ) + (A ek − M k ). A

Lemma B.12 gives ek − M k ) ≤ λ−k (A

2kδ . |λ|

For the normalization part, use the telescoping identity bk − A ek = A

k−1 X

bt (A b − A) eA ek−1−t . A

t=0

Moreover,

b ≤ |λ| + δ + ϵ, ∥A∥

Therefore −k

e ≤ |λ| + δ. ∥A∥

k−1 kϵ δ+ϵ ≤C , 1+ |λ| |λ|

bk − A ek ) ≤ kϵ (A |λ|

where the last inequality uses k(δ + ϵ)/|λ| ≤ C0−1 . Consequently, bk − M k ) ≤ C λ−k (A

k(δ + ϵ) . |λ|

This bound is dominated by " C

so −k bk

A U −U

≤C F

# δ+ϵ + 2k , |λ|

ϵ |λ|

+ 4k

δ+ϵ |λ|

2 #

∥U ∥2F .

bk . Since G has independent Gaussian columns Gaussian term. Conditional on the graph, set B := λ−k A g1 , . . . , gm , m X ∥BG∥2F = gr⊤ B ⊤ Bgr . r=1

A standard Gaussian quadratic-form concentration bound gives, with probability at least 1 − n−Ω(1) , ∥BG∥2F ≤ Cσ 2 m log n Tr(B ⊤ B). Here the assumption m ≤ nCm allows the Gaussian tail probability to be union bounded over the m feature b is symmetric, coordinates while keeping a log n factor. Because A 1 b2k ). Tr(A |λ|2k

Tr(B ⊤ B) =

Since M is symmetric with rank L − 1 and ∥M ∥ = |λ|, Weyl’s inequality for singular values gives b ≤ sj (M ) + ∥H∥. sj (A) More explicitly, for 1 ≤ j ≤ L − 1, b ≤ |λ| + ∥H∥ ≤ |λ| + δ + ϵ, sj (A) while the rank inequality

sj+L−1 (M + H) ≤ sj (H)

b ≤ δ + ϵ for every j ≥ L. Thus at most L − 1 singular values are bounded by |λ| + δ + ϵ, and all implies sj (A) b is symmetric, Tr(A b2k ) = Pn sj (A) b 2k . Hence remaining singular values are bounded by δ + ϵ. Because A j=1 1 b2k ) ≤ Tr(A |λ|2k Thus −k bk

≤C

A G F

δ+ϵ |λ|

δ+ϵ 1+ |λ|

(L − 1) + n

δ+ϵ |λ|

2k #

σ 2 m log n.

(k)

Counting bad vertices. Let ne be the number of vertices satisfying ∥xi ne

− µℓ(i) ∥ ≥ ∆/2. Then

∆2 ≤ ∥X (k) − U ∥2F . 4

Combining the two bounds above and absorbing absolute constants gives " 2 # 2k ∥U ∥2F ϵ δ + ϵ ne ≤ O + 4k 2 |λ| |λ| ∆2 ! " 2k 2k # 2 δ+ϵ δ+ϵ σ m log n (L − 1) + n . + 1+ |λ| |λ| ∆2 Every vertex outside this exceptional set is within distance ∆/2 of its true class center, and hence is closer to its own center than to any other class center. This proves the claimed partial recovery bound.

Record · ID 299939 · SHA-256 e7b062a801b3531e
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.