A CLT for Polynomial GNNs on Community-Based Graphs
Authors: Luciano Vinas
Arash A. Amini
Venue: NeurIPS 2025 poster ()
Keywords: Graph Neural Networks
Neighbor Aggregation
Convergence of Measures
Central Limit Theorem
GNN Oversmoothing
Stochastic Block Model
Primary area: theory
TL;DR: Graph convolutions on node features admit a natural central limit theorem which has consequences to multi-class node classification.

Abstract: We consider the empirical distribution of the embeddings of a $k$-layer polynomial GNN on a semi-supervised node classification task and prove a central limit theorem for them. Assuming a community based model for the underlying graph, with growing average degree $\nu_n\to\infty$, we show that the empirical distribution of the centered features, when scaled by $\nu_{n}^{k-1/2}$  converge in 1-Wasserstein distance to a centered stable mixture of multivariate normal distributions. In addition, the joint empirical distribution of uncentered features and labels when normalized by $\nu_n^k$ approach that of mixture of multivariate normal distributions, with stable means and covariance matrices vanishing as $\nu_n^{-1}$. We explicitly identify the asymptotic means and covariances, showing that the mixture collapses towards a 1-D version as $k$ is increased. Our results provides a precise and nuanced lens on how oversmoothing presents itself in the large graph limit, in the sparse regime. In particular, we show that training with cross-entropy on these embeddings is asymptotically equivalent to training on these nearly collapsed Gaussian mixtures.

A CLT for Polynomial GNNs on Community- -Based Graphs
Luciano Vinas
Arash A. Amini
University of California, Los Angeles lucianovinas@g. ucla.edi
University of California, Los Angeles aaamini0g ucla. edu
Abstract
We consider the empirical distribution of the embeddings of k-layer polynomial GNN on a semi-supervised node classification task and prove a central limit theorem for them. Assuming community based model for the underlying graph, with growing average degree Vn - oc, we show that the empirical distribution
the centered features, when scaled by in k-1/2 converge in I-Wasserstein distance to centered stable mixture of multivariate normal distributions. In addition, the joint empirical distribution of uncentered features and labels when normalized by vf approach that of mixture of multivariate normal distributions, with stable means and covariance matrices vanishing as Vn We explicitly identify the asymptotic means and covariances, showing that the mixture collapses towards a I-D version as & is increased. Our results provide precise and nuanced lens how oversmoothing presents itself in the large graph limit, in the sparse regime. In particular, we show that training with cross-entropy these embeddings is asymptotically equivalent to training on these nearly collapsed Gaussian mixtures.
Introduction
Graph Neural Networks (GNNs) are now a key tool for machine learning on graphs. Their success is largely due to the graph convolution operation-alss known message passing neighbor Eegregation-whie where node features are updated by gathering information from their graph neighbors [5 23). This process helps GNNs learn powerful embeddings for tasks like node classification and regression. For graphs with community structure, theory shows that even one aggregation step can improve feature separation between classes by factor of VVn, where Vn is the average node degree
3
Analyzing deep GNNs with multiple aggregation layers (A: > 1) is important but theoretically difficult. Unlike single aggregations, the resulting features, (**), lose desirable properties such entry-wise independence. To study these aglli-aaggeeated features, researchers have used techniques like walk-based decompositions, which classify feature contributions by underlying graph walk patterns 18). For community-basee graphs, these methods suggest that while feature cluster centers can separate at rate of v their standard deviation often grows as k-1/2
This paper focuses on Polynomial GNNs (Poly-GNNs). In these models, features ((()) = A X are created by applying the adjacency matrix A, times to initial node features X Rnxd without any non-linear functions in between. These features (83,, when passed through final linear layer W, produce classification scores. Poly-GNNs, despite their simplicity, are not just theoretical ideas. They form the basis of several practical and effective GNNs like APPNP [6). GPR-GNN [7]. and models using Chebyshev, Bernstein, and Jacobi polynomials 9 13 20 Such models have achieved strong results, sometimes sate-of-thee-an art, standard benchmarks demonstrate that simplified aggregators and polynomial baselines remain highly competitive with
20 indeed, recent rigorous evaluations
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

complex architectures [19]. Therefore. understanding Poly-GNN features offers valuable insights into multi-hop aggregation and the behavior of these common GNN types.
1.1 Overview of Our Contributions
In this paper, we undertake detailed asymptotic analysis of the embeddings generated by k-layer Poly-GNNs on community-basee graphs as the number of nodes n grows. To stabilize these features, we consider two types of normalized embeddings: the degree-normalized features o, =(k) := o
(k) /v/-
and the centered and scaled features <!*) vvn(@, (A) Elo;" D. Here, Vn is the average degree parameter which we assume tends to infinity. One of our main results is Central Limit Theorem
(CLT) demonstrating that the empirical distribution of c!ah) converges in 1-Wasserstein distance to centered mixture of multivariate Gaussian distributions.
Building upon this, we further demonstrate that the joint empirical distribution of the uncentered, degrec-normalized features (h) (which are directly used in downstream classifiers) and their cor- responding true labels 2; also converges in the 1-Wasserstein distance. Specifically, as n + oo and Vn, + oo, this distribution approaches that of a random pair (Z, Yn) where Z ~ т (the limit- ing class proportions) and Y, conditioned on Z = i follows a multivariate Gaussian distribution N [(e, Σg/vn) A core contribution of our work is the precise analytical characterization of these limiting class means jig and class-conditional covariance matrices Σt, expressed in terms of the graph's ss community structure and initial feature means.
This characterization has profound implications for understanding the training dynamics of GNNs.
(k)
We prove that training linear classifier these Poly-GNN features @g using the standard cross- entropy (CE) loss converges to the equivalent optimization problem on this limiting Gaussian mixture. This convergence holds uniformly for the loss function, the gradient path during optimization, and the final learned classifier weights (under mild conditions on weight norms), due to the Lipschitz nature of the CE loss and its gradients with respect to the features. This result provides strong theoretical basis for the behavior observed when training linear classifiers on GNN embeddings.
Furthermore, our explicit forms for jr and Σ, reveal a clear and precise mechanism behind the well-known phenomenon of GNN oversmoothing. The mean vectors μ involve terms of the form (J*M)?, while the covariance matrices Σg involve (J*-IM) where J is matrix derived from the graph's 's inter-community edge probabilities and class proportions, and M represents the initial class feature means. As the GNN depth l increases, the repeated matrix exponentiation j (and Jk=1) acts like a power iteration. This causes both the class means and the dominant sigen-directinn class covariances to align with oow-dimeniional (often I-D) subspace determined by the leading eigenvector(s) of J. Consequently, the feature distributions for different classes, initially potentially well-separated in d dimensions, collapse onto this common, typically 1-D, subspace. This results in a degenerate, poorly separated Gaussian mixture, thereby degrading classification performance. Our analysis, thus, provides nuanced, quantitative view of oversmoothing in the sparse, large-graph limit.
of the
The related literature for multi-hop aggregation can be broken into three cate- gories: distributional characterizations, oversmoothing phenomenon, and performance improvements on select learning tasks, such as classification or regression.
Previous Literature
For distributional characterizations, setting that ((()) is exactly component-wise Gaussian for all n. We note this cannot be the case for of = Σj Aij X, with Bernoulli Aij and normal Xj. Øf is a (scaled) mixture distribution.
22 is closest to our work. In their paper, the author's rely on the
In the vein of oversmoothing, works 17 21 show how properly normalized aggregations can still oversmooth in the presence of non- non-linearities. Oversmoothing in this case can be seen as consequence of the power iteration collapsing the range onto the Perron eigenvectors of A. The works [7] show that non-linearities like ReLU do not help oversmoothing since the ReLU operator is also contractive under the operator norm [.. In (1 the authors extend these results to also include attention-based non-linearities. Outside of [7 which considers the effects of oversmoothing on
a T. community graph, all other works assume is a deterministic graph. Our work differs fundamentally by analyzing stochastic graph model in the lurge-graph limit. While prior work

---

often explains oversmoothing via power iteration on fixed adjacency matrix, showing that feature means collapse, our CLT reveals a more powerful mechanism. Building upon our previous work of matrix moment analysis for community-basee graphs [8], we prove that the feature covariance also collapses onto the same unfavorable, (ow-dimensional subspace as the means. This provides a much stronger characterization of feature degeneracy.
With respect to improving task performance, works [4 show how multi-hop features can improve downstream learning tasks. Between the two works the generative formulation differs, 4 assumes (p. 9)SM with mixed mean feature representations while [4] assumes low rank, latent variable model which yields dense observed graphs. The losses considered by [4] [4] are Lipschitz, high- lighting the importance of understanding behavior of multi-hop features under the I-Wasserstein metric.
2 Preliminaries and Model Setup
In this section, we formally define the Polynomial GNN (Poly-GNN) architecture, introduce the normalized features central to our analysis, describe the community- based graph model, state our key assumptions, and briefly define the Wasserstein distance used to quantify distributional convergence.
2.1 Poly-GNNs and Feature Definitions
We consider a simple yet powerful class of Graph Neural Networks known as Polynomial GNNs (Poly- GNNs). Given an undirected graph with nodes, represented by its adjacency matrix A E {0, 1 and initial node features X Rn k--ayye Poly-GNN computes node embeddings, features, (b()) E R Raxd through l successive aggregations:
( A
The i-th row of ((),, denoted $ (k) E Rd represents the embedding for node i after is layers of aggregation.
For our asymptotic analysis, we work with normalized versions of these features. Let V, be the average degree parameter of the graph, which we assume grows with (see Assumption I We define the degree-normalized features as:
(k) uk
(k)
These features g(A)) are often the direct input to a downstream classifier. In practice, the unknown parameter Vn not required, as it can be reliably replaced by the observed average degree.
To establish a stable limiting distribution under a Central Limit Theorem, we further define the centered and scaled features:
(k) Vin
(k) 16 (
i == I,...,n.
(3)
The empirical distribution of these features, P,, := be a primary object of study.
1 n E 6e(0, where o, is a point mass at x, will
2.2 Community-Based Graph Model
We assume the graph and its node features are generated from community-ben based model. Let (z:) E [Z]" be vector of latent node labels, assigning each node to one of I, communities or classes. The graph structure and initial feature distributions are conditional on these labels.
Specifically, we adopt the Contextual Stochastic Block Model (CSBM) [10]. The adjacency matrix A generated such that edges are conditionally independent given z, with probabilities:
Ag Bern(y,, B,,,//n) for i + j, and A 0,
(4)
where B [0, 1| is a symmetric matrix of inter-community edge probability scalings. The parameter vn/n represents the average edge density scale.

---

The initial node features X, E R are assumed to be conditionally independent given 2,. Their expectations are determined by their class membership:
E[X; 2, = E MM,-,
(5)
where M E R2xd is matrix whose é-th row, MM... is the mean feature vector for class t. This can be written compactly as [[[] ZM, where Z E {0, 1 is the one-hot encoding matrix of the labels 2, i.e., Zie 2 f}.
We define π = (T1...... 'T)" as the vector limiting class proportions (see Assumption 3). Let II diag T....., ) be the diagonal matrix of these proportions. A key matrix in our analysis is E RIX/ defined as:
BTI
(6)
This matrix captures the interplay between inter-community connectivity and class sizes II.
2.3 Assumptions
Our theoretical results rely on the following assumptions:
Assumption 1 (Degree Growth). The average degree parameter Vn, 00 - 0o, and Bie SC for some constant C, implying that the expected degree of any node i, Ljzi Un Va,2,,/11 n, is (vn)).
Assumption 2 (Sparse Graph). The graph is sparse, meaning Assumption 3 (Cluster Convergence). For each class E E [L], let C. {i [m] be the set of nodes in class l. We assume there exist Te > such that me - [Cel/n = o()), and Ei= Te 1. Assumption 4 (Feature Bounds). The initial node features X4 are sub- sub-gaussian. Specifically, for any unit vector u E R., (X; [[ ~ (GG( for some o² > uniformly for all i,n. Furthermore, their expected norms uniformly bounded: lim limsup, sup supre[n] [1|X, 1|2 I z. for some I. 0.
o(n).
Of the listed assumptions, Assumptions 1 and are necessary as, without these, a limiting Gaussian distribution cannot be obtained. See Figure for mild and subsumes a large class of feature distributions. Assumption 2 is simplifying one. Our CLT framework extends to the dense regime (v,, ((n)), but the limiting covariance structure becomes more complex. As detailed in Appendix [.I]] the variance of the aggregated features decomposes into terms driven by graph randomness (A) and initial feature randomness (X). In the sparse setting, graph randomness dominates, causing the initial feature covariance to be negligible in the limit (Appendix A..)). In the dense case, this ceature-related noise term persists, leading different limiting covariance. We focus on the sparse case as it is representative of many large-scale networks.
details on the case of I. 1. Assumption 4 is
2.4 Wasserstein Distance
To measure the distance between probability distributions, we the 1- I-Wasserstein distance, denoted (P,, Q) For two probability measures and Q on Rd the Kantorovich- mnntorovich-Rubinsteen duality provides convenient definition:
/SaP fa
(IP = sup
fdD
feLip(1)
where Lip(1) is the class of all I-Lipschitz functions IRd - R. i.e., functions satisfying [f(x) - [w)] < || - v/l2 for all x, E Rd. We also write P/ sdP for the expectation of /under P. Convergence in W, implies weak convergence and convergence of first moments. Its connection to Lipschitz functions makes it particularly relevant for analyzing learning algorithms with Lipschitz loss functions.
3 Asymptotic Distribution of Poly-GNN Embeddings
In this section, we present our main theoretical results concerning the asymptotic distribution of Poly-GNN embeddings. We establish Central Limit Theorems (CLTs) for both the degree-normalized (k) features कh (jointly with their labels) and the centered-and-scaled features (k)) We then outline the key steps involved in proving these theorems, highlighting the key intermediate lemmas and propositions.

---

n1 300
n 3000
30000
0.15
3.75
0.75
Density
0.3
0.5
0.15
0.25
Donsity
0.2
0.2
0.2
0.0
0.0
Density
0.4
16
0.4
0.4
0.2
0.2
0.0
-1.5
1.5
Figure 1: Comparison of the (*t) distribution for At = across different expected degree Erdös-Réyni As graph size increases, the overall histogram resolution improved but this does not qualitatively change the shape of the histogram. That is, growing degree Di, + oc, is a neccesary condition for g e( to be Gaussian.
Réyni graphs
3.1 Main Central Limit Theorems
Our first main result characterizes the joint limiting distribution of the true node labels z; and the
degree-normalized Poly-GNN features (k) These features are typically used for downstream classification tasks.
Theorem (CLT for Degree-Normalized Features and Labels). Let (A, be community-basee Let (/4h
k-layer Poly- GNN features. Define the limiting class means μe Rd and class-conditions covariance matrices Σg E Raxd as:
graph satisfying Assumptions
0/ /utt be the
#e (J"M)"
(8)
Σg Σ; = (J=- diagle? J){k-
(9)
where eę is the l-th canonical unit vector in R J BII, and M contains the initial class feature (1b) Pjoint = (()) Let
means. Let Pjoint be the empirical distribution of pairs (2z, 0z
Gjoint be the probability distribution of a random pair (7, Yn) where 2. ~ Categorical L1)
and, conditioned on 7. Yn Nuu, Ee/va). Then, as > oC:
Wi
ppjoint Gjoint
O.
(10)
Furthermore, this convergence holds in the stronger class-conditional sense: for any R R>0 0,
lim E sup fi....ff fu (lip(R)
ΣΣ E=1 IEC,
selo Σ Te TYEY -0. (11)
Theorem 1 shows that for large and Un, the features o. behave as if drawn from Gaussian mixture where each component is centered μe and has a covariance Ee/vn that vanishes as Vn xc.
Our second main result provides a CLT for the centered and scaled features c! showing they converge to a stable (non-degenerate variance) Gaussian mixture.
Theorem (CLT for Centered and Scaled Features). Under the same conditions Theorem 7 let
(k) - 1) be the centered and scaled features. Let = Σi= 6:00 be their (k) = (o
empirical distribution. Let G be the centered Gaussian mixture distribution:
Te N(0, Ex),
(12)
5

---

where De is defined in Eq. 9 Then, as n + 0o:
E [Wi G)]
(13)
Furthermore, this convergence also holds in the stronger class-conditional sense: for any R 3 0.
lim E +-+00
fe(E!
E=.BY-NOX,,11MM 0. (14)
(LLp(R)
8=1 RCC
t=1
Theorem establishes that after appropriate centering and scaling, the Poly-GNN features converge mixture of Gaussians, each component having a non-vanishing covariance E..
more interest in practical scenarios, since the uncentered features do require estimation of the feature mean El ]. Furthermore, in settings where Assumption and hold, the average degree d becomes reliable estimate of normalization scale since d x Vn-
note that Theorem T may
3.2 Proof Outline and Key Steps
The proofs of Theorems [ and share a common foundation and proceed in several steps. We outline the general strategy here, focusing the convergence of P,, to G (Theorem 2]. The argument for Theorem builds on Theorem 2 with adjustments for the non-zero means and the v, scaling in the covariance. The full proofs are provided in Appendix
The overall strategy involves two main parts for establishing B[W1 (Pr,, G)] +:
Show that the empirical measure P, concentrates around its expectation P, = [F[[P i.e., 0.
(I,,
2. Show that the expected empirical measure P, converges to the target Gaussian mixture G in
W1 distance, ie., W1 (T G) +
The argument for consicoondiiinall convergence (e.g., Eq. (11) builds upon this by considering per-class empirical measures and leveraging the convergence of class proportions [Cel/n + Te.
The key technical steps involve analyzing the moments of the features:
Step 1: Moment Analysis for General Graphs This step characterizes the behavior of feature moments without yet imposing the full community structure, relying mainly on Assumptions | and 4
The centered, un-normalized features of
El (k) are decomposed into two terms: Å; (due to graph randomness) and Å; (due to initial feature randomness):
E (K) ò + A.
(15)
Normalizing appropriately, (k) (A: + A. 1/2
The term A, == A 1-1/2 is shown to be asymptotically negligible under our sparsity assumption
(see Proposition in Appendix A.3). Thus, <² is asymptotically equivalent to A; := Á,/// 1/2
in terms of its contribution to moments (see Lemma in Appendix A.3
The moments of á, := (A,, 0) for any unit vector E Rd are analyzed.
Odd moments: [[ [ + for odd (this follows from the moment bounds in Proposition 3
specifically the term // 2 [n/2] which is vn -1/2 for odd p = r).
Even moments: E + (r- 1) for even r, where o² : ||VE|A/V, 1-
(see Lemma Appendix A.3).
The expected normalized mean (see Lemma 3 in Appendix A.2
shown to converge a limit 7; (B{A\\(())
Step Specialization Community- Graphs Here, the community structure (Assumptions and the CSBM formulation) is used to refine the limiting moments.

---

The limiting mean for a node i C₁ converges to (JM eg (as detailed in the proof of Proposition Ii Appendix[A.4 building on Lemma
The average of the per-node variances o7 over class converges to 8 EgE,, where Σg is defined in Eq. D (this is part of the derivation in the proof of Proposition
Consequently, the r-th moment of the 8-projection of P... m, (. 1 E, E (R) 0)", converges to my (Ga) = Σ m [Y*) (see Proposition 4 Appendix A.4
Since the Gaussian mixture Gg determined by its moments, this establishes that I- Fn. ~ Gg. Uni-
form integrability of moments (derived from the v norm bounds in appendix specifically Lemma 9
applied to A via Proposition 3) then promotes this weak convergence to Wi (P Go - 0. A
discretization argument (Proposition from Appendix B and Proposition S (from Appendix D
extend this W1(P., G) +
Step 3: Concentration and Convergence of Empirical Measure. To show [[W, 0. we rely on:
Control over the variance of empirical moments: Var(n 11 Ei= S n (see Lemma
in Appendix A.3 which implies similar behavior for (k) via Lemma condition (b) of Proposition 8 Appendix [
This corresponds to
Tail control for (E("*),0 0): The features (5/4), 0) are shown to be uniformly L sub-Gaussiaa for
a growing r, (see Lemma] Tin Appendix A.I.. This corresponds to condition (a) of Proposition
Uniform integrability of moments of P, (the convergence shown in Proposition implies that for any fixed r, sup,, (F, finite, which by Proposition 7 implies sup, M, (P,) is finite, e.g. Mi (P,,) needed for condition (c) of Proposition g).
These conditions allow the application of Proposition (from Appendix D). which establishes the desired concentration E[ main parts to yield the final convergence result.
(IP,(IP..) (IP F.)]] + 0. The triangle inequality for W1 then combines these two
Implications for Classification and GNN Oversmoothing
The Central Limit Theorems presented in Section 3 not only provide a fundamental understanding of the distributional properties of Poly-GNN embeddings but also have significant practical implications. In this section, we explore two key consequences: first, how our results explain the convergence of linear classifiers trained on these embeddings, and second, how they offer a precise, quantitative mechanism for the GNN oversmoothing phenomenon 5 17
4.1 Convergence of Linear Classification on Poly-GNN Features
In many node classification tasks, GNN embeddings are fed into a final linear layer (often followed by a softmax activation) that trained using a cross-entropy (CE) loss. Our results provide a theoretical basis for understanding this training process in the asymptotic limit. We focus the
(k) degree-normalized features o; as these are the quantities typically used by the classifier.
(k)
Recall from Theorem that the joint empirical distribution of labels 2, and features ø converges to that of (Z, Yn), where Z ~ Categorical(()) (T) and Y, Z f ~ N(p,, Ee/un). The class means fr and covariances Σg are given by Eqs. (8) and ( respectively.
Consider a linear classifier with weights W = (w)...., w E Rixd and biases b = (b,,..., br.)² E LR-. The empirical cross-entropy loss for a dataset of n nodes is:
exp(w? 0; be) Ele wxxpxxxpppp o (k) + b..)
Eemp (W,
-== -3 log
(16)
It
The limiting loss, based on the Gaussian mixture (GM) characterization from Theorem I is:
LcM(W. := E TyeBY~NNu..d log exp(wi) be)
(17)
Σ4 exp(w TY + bw.)
7

---

Limiting Mixture Distribution
Gradient W]
Path for W2
Gradient Poth W3
0.4
-0.5
2
2.0
-25
-07
-30
-0.8
-0.2
-0.1
0.0
-2.0
-15
-1.0
-0.5
0.0
0.5
1.0
-0.8
-0.6
-0.4
-0.2
0.0
Figure 2: Ten gradient steps of cross-entropy optimization problem for (A, drawn from 3-class CSBM.
Shown on the right are gradient paths for samples drawn from empirical and theoretical distributions for "(
For any fixed set of weights (W,b) (e.g., within ball I(W, S R. for some radius R); the Lipschitz with respect the feature x. This Lipschitz property, combined with the 1- Wassersstein convergence established in Theorem (specifically, the clas--coniitioall form Eq. (IT), leads to the following key result:
individual loss term for class f, CR2(:; W,b) = - log Et exp("TIz+b..
exp(w, 2=bb)
Proposition (Convergence of CE Loss and Gradients). Under the conditions of Theorem 7 for any fixed radius R > 0:
(a) The empirical CE loss converges uniformly to the limiting GM CE loss:
lim E sup 22-00
SSmpp SWmp(WW)) b) -GGM(W, b)]
0.
(18)
[I(W&)]]
(b) The gradients of the empirical CE loss converge uniformly to the gradients of the limiting GM CE loss:
lim E sup [I(W&BIlESR
| (W.,) (W, -V V(w,o) CaM
0. (19)
Consequently, the sequence of parameters (W (Wmpp kemp) minimizing Lemp (W, b) within the ball con- verges in probability to the parameters (W ((M)) minimizing LGM(W, b) within the same ball, assuming uniqueness of the minimizer for the limiting problem.
The proof of (b) relies on the fact that the gradients C=CE,(x; W,b) are also Lipschitz in for bounded (W, b). Proposition I formalizes the intuition that training Poly-GNN with CE loss is asymptotically equivalent to performing CE optimization directly on the identified Gaussian mixture. This explains why gradient descent paths on the empirical loss track those the limiting GM loss, as illustrated in Figure
The stationarity conditions for optimization problem LCM (W, reveal moment-matching structure:
TEEe
By Ty.BYNN (H.... pel, and
By NNpp Sn/ve. pe).
(20)
for all é E [L], where P. = PY:Y: = cxpp bb)
exp(w + bj). It is important to note that while the GNN training process converges to this CE solution on the GM, this solution is not necessarily the Bayes optimal classifier for the Gaussian mixture itself (which would be Quadratic Discriminant Analysis. QDA, classifier). Figure illlssraates this, showing that even for large n where
(k)
closely follows the GM, the linear CE boundary can differ from the optimal QDA boundary.
4.2 A Precise Mechanism for GNN Oversmoothing
The oversmoothing phenomenon, where GNN performance degrades with depth k. is a well- documented empirical observation 55] 17 Existing explanations often invoke power iteration
argument fixed graph matrix, demonstrating that class means collapse towards common

---

Mixture Density (Theory)
QDA Log-Llkelihood
Log-Likellhood Rotio
(Estimated)
(Estimated)
10
-0.1
-0.1
-02
0.2
-0.2
-03
0.3
-03-
-044
Semples
Samples
-10
Class Means
Class Means
-0.1
0.0
0.1
0.2
0.3
0.4
-0.1
0.0
0.1
0.2
0.3
0.4
-0.1
0.0
0.1
0.2
0.3
0.4
Component
Component
Component
Figure 3: Classifier comparison for data which is 2 2-dimensional CSBM. On the left is the theoretical density of the 2-class CSBM. The two right plots the estimated oigllikeddood ratios for the QDA and CE estimator respectively, The slight bend the data is correctly captured by the QDA estimator.
subspace. Our analysis, grounded in a stochastic graph model, provides a fundamentally deeper mechanism.
More precisely, we show that in the sparse, large-graph limit, is not just the means that collapse. The initial, potentially class-separating covariance of the features vanishes, and is replaced by purely graph-induced covariance Mg that itself collapses. As our analytical forms show, this new covariance aligns its principal directions with the very same 1-D subspace occupied by the class means. This alignment of signal and noise is a much stronger form of oversmoothing, as it guarantees that the variance concentrates in the same direction the means, maximally hindering their separability.
To see this, recall the expressions from Eqs. and (9:
Pe (J*M) E6 Σg = (Jk- M) diagle J)(Jk-lM)
Consider the symmetric matrix Jaym = 1/1 which is similar to J (since = BII = 1/2 Jaym 122). Let Jaym QAQ be its eigendecomposition, with Q orthogonal and A diag(Au (A1, ............ Xr.) containing the eigenvalues, ordered by magnitude [Aı] [^2] Z .... Then jk (T-1/2QA*QTTTUZ If there is dominant eigenvalue Aι (i.e. [A > [22)). then for large k, the matrix A diag(Af, 0, .......)). This implies Jk = (II-I//2q II where qi the leading eigenvector of Jaym Let #1 11-1/2m (a right eigenvector J) and of = of 1/ (a left eigenvector of J). Then J = Xfuoo..
Substituting this into the expressions for and Σ;:
Class Means: R (f - vi)
This shows that for large k, all mean
vectors μ4 become approximately proportional to the fixed vector M of = "T The specific proportionality constant (uf ex) depends on the class but the direction is shared.
Similarly, J 2e X uuo Then Eg Rs 12(k-2)(M3 un (scalar,) (uf M), where scalar, = of diag(e? Ji) This indicates that Σ, (and thus Σz/u,) becomes approxi- mately rank-one, with dominant direction also aligned with Mf
Class Covariances:
This power iteration effect driven by J and J is the core of oversmoothing mechanism:
Mean Collapse: The mean vectors be for different classes tend to align along common direction M 11'11'//2 While their magnitudes might differ (scaled by (f ex)), their angular separation diminishes. If the initial feature means M projected onto U1 do not maintain sufficient separation, or if uf e values are too similar across classes, the means become indistinguishabl..
2. Covariance Collapse and Alignment: The covariance matrices Eg also become rank- deficient and align their principal direction with the same direction as the means.

---

Mixture Density for Different Number of Aggregations
-0.02
0004
0.06
-0.1
-0.04
-0.05
-02-
-0.10
-033
-012
-0.00
-0.44
-05
Mean Vectors
Moan Victors
Maan Vectors
-0.66
-0.08
0.1
0.06
0.04
0.07
Componett
Component
Component
Figure 4: Estimated kernel density plots of the aggregated features क of 2-class CSBM at different features
depths k. A feature collapse in mean vectors and the class covariances is visible by 4 = 6.
The net effect is that the L Gaussian components N(p. Ee/v)) of the feature distribution ~ effectively collapse onto 1-dimensional subspace. Within this subspace, they become mixture of 1-D Gaussians. If the projected means are not well-separated relative to the projected variances along this single dimension, classification becomes extremely difficult, regardless of the original dimensionality d or the initial separability of M. This phenomenon illustrated empirically in Figure where increasing & leads feature distributions that are elongated along common axis and overlap significantly. The parameter Vn helps shrink the variances overall, but does not prevent this directional collapse induced by k.
5 Conclusion
We conducted a rigorous asymptotic analysis k-layer Polynomial GNN (Poly-GNN) embeddings on large, sparse, community-based graphs, establishing Central Limit Theorems that precisely
characterize their limiting distributions. We showed that degree- normalized features ((k) jjointly with labels 24, converge in W -distance to Gaussian mixture N (ug, Σş/Un) per class l. We provided exact forms for μr (J TM and Dg (JK-1 "Y"" diag(e) J)(Jk-1M MM, determined by initial
means M, layers k. and community interaction matrix Centered-amm and-scaled features (Ab) similarly converge to Σ (0,
(K)
These findings have key implications. First, training linear classifiers on 0 with cross-entropy loss is asymptotically equivalent optimizing on this limiting Gaussian mixture, with uniform convergence of the loss, gradient path, and optimal weights. This theoretically grounds the training behavior of GNN-based classifiers. Second, our explicit characterization of μu and E, offers clear and nuanced understanding of the GNN oversmoothing phenomenon. The repeated multiplication by the matrix J (to powers h and k 1) acts as a power iteration, causing both the mean vectors and the principal directions of the covariance matrices align with a low-dimensional (often 1-D) subspace dictated by the leading eigenvectors of This results a degenerate, poorly separated Gaussian mixture, thereby diminishing the discriminative power of the GNN embeddings, irrespective of the initial feature dimensionality.
For future work, our framework suggests several avenues. A direct extension would be to extend degree-corrected stochastic block models (DCSBMs), where we expect similar CLT hold provided the normalized degree distribution is stable. Extending the analysis to polynomial filters of the form Σn C& (A/v,,) " appears feasible, though would require careful book-keeping of the correloorss between different powers of A. A more significant challenge, likely requiring new tools beyond our walk-based moment analysis, the extension to GNNs with non-linear activations or attention mechanisms. As a potential starting point, one could take inspiration from the loss landscape analysis of g which applies walk decomposition to the feed-forwant architecture of fully-connected ReLU network.
10

---

Acknowledgments
This material is based upon work supported by the National Science Foundation under Award No. 1945667.
References
[1] Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient Flows: In Metric Spaces and in the Space of Probability Measures. Lectures in Mathematics ETH Zürich. Birkhäuser, 2nd edition, 2008. ISBN 978 978-3-7643-8722-88
[2] Arash A. Amini and Luciano Vinas. Wasserstein concentration of empirical measures for dependent data via the method of moments, 2026. URL https://aaxxvvorr/abb/..
07228
[3] Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi- supervised classification: Improved linear separability and out-of-distribution generalization. In International Conference on Machine Learning, 2021.
[4] Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of graph convolutions in multi-layer networks. In The Eleventh International Conference on Learning Representations, 2023. URL U https: /tttts/s:///peenett eview http::///peeevvieeeeeee
[5] Chen Cai and Yusu Wang. A note over-smoothing for graph neural networks. In ICML Workshop on Graph Representation Learning and Beyond (GRL+), 2020. URL http:::tttssttt cc/virtual/2020/755
[6] Juntong Chen, Johannes Schmidt-Hieber Claire Donnat, and Olga Klopp. Understanding the effect of gen convolutions regression tasks, 2024. URL https::/arxiv.org//aaeee arg/ 20068
[7] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021.
[8] Anna Choromanska, Mikael Henaff, Michael Mathieu, Gerard Ben Arous, and Yann LeCun. The Loss Surfaces of Multilayer Networks. In Guy Lebanon and S. V. N. Vishwanathan, editors, Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Research, pages 192-204, San Diego, California, USA, 09-12 May 2015. PMLR.
[9] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in Neural Information Processing Systems 29 (NIPS 2016), pages 3844-3852 2016. URL URL https:://ppe::rre www.niis....aaaae 2016/hasha hts//aahh/444 0fdff 464344411c5bb72beell
1e665 Aet.0ssAssttact... html
[10] Yash Deshpande, Andrea Montanari, Elchanan Mossel, and Subhabrata Sen. Contextual stochastic block models. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL httpp::/pproceedinggs neurips........r..o............. wwtpssscccpspppccppprrrr.rem httpppppr_ffleeee
pdf
[11] Sören Dittmer, Emily King, and Peter Maass. Singular values for relu layers. IEEE Transac- tions on Neural Networks and Learning Systems, 31 310)):394433055 2020.
[12] Justin Gilmer, Samuel S. Schoenholz, Patrick Riley, Oriol Vinyals, and George F. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning. ICMI. 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1263-1272, 2017. URL http://procceedings mlr. wwwpss/e/esseeeeeeeepeepppp http/////gmmmmlr/.mmm/ html
[13] Mingguo He, Zhewei Wei, Zengfeng Huang, and Hongteng Xu. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 14239-14251 2021. URL https::///// htttp:://operrviiie net/
forum?id= Forum?id-WigDDV-..

---

[14] Nicolas Keriven. Not too little, not too much: a theoretical analysis of graph (over)smoothing,
In Advances in Neural Information Processing Systems, volume 35. Curran Associates. Inc., 2022. URL htttp:::/prroceeedngs..nnni
or55aarffrr6ooo/77777766644444er .html
[15] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017.
[16] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In Proceedings of the 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, wtt.:/wwww..ee..ooomm//tt.......
2019. URL
[17] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. International Conference on Learning Representations, 2020.
[18] Luciano Vinas and Arash A. Amini. Sharp bounds for poly-gnns and the effect of graph noise,
2024. URL /ttttps://ariivt hrrg/bbs24077. 19567
[19] Luciano Vinas and Arash A. Amini. Simple GNNs with low rank non-parametric aggregators. In Proceedings of the Third Learning on Graphs Conference, volume 269 Proceedings of Machine Learning Research, pages 10:1-10:11. PMLR, 2025. URL.httss://rrocedding
mlr. A.r.presssv26/ valess//26//vinas25a. wiwassaa.aaa..a html
[20] Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks? In International Conference on Machine Learning (ICML), volume 162 of Proceedings of Machine Learning Research, pages 23341-23362. PMLR, 2022. URL htttp:://ppoceeednnggge/ mlr
Dress/v166/wann22aan
[21] Xinyi Wu, Amir Ajorlou, Zihui Wu, and Ali Jadbabaie. Demystifying oversmoothing in attention-based graph neural networks. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URK.httts://ppenrevvee.
[22] Xinyi Wu, Zhengdao Chen, William Wei Wang, and Ali Jadbabaie. A non- con-asymptotic anal- ysis of oversmoothing in graph neural networks. In International Conference Learning Representations, 2023.
[23] Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning, 2016.
12

---

A Detailed Proofs of Main Theorems
This appendix provides the detailed proofs for Theorem and Theorem 2 presented in Section 3.1 The general proof strategy follows the outline given in Section 3.2
Before proceeding with the proofs, establish some notation used throughout the appendices. For probability measure ja on I' and a vector E IR we denote by μ4 the 8-projection (or 0-section) of μ. This the pushforward measure of j under the map I (xr, 0) x² 0. If X 14, then 1s0 is the distribution of the real-valued random variable (X, 0)- For a measure on IR, its r-th moment is denoted by mv) = ff dz(z). For a measure μ on Id, its r-th absolute moment is M,(u) = f [==]]d(()))) The empirical measure of a set of N points (Y:) is Σi=1 Sy; We denote the expectation of random empirical measure I2,, IP,, defined by its action on test functions f: Pr. [ EIP, n [/]]- We use Lip( R)) to denote the class of R-Lipschitz functions f R. R. Other notation, if not standard, will be defined as it appears.
A.1 Proof of Theorem (CLT for Centered and Scaled Features)
The proof of Theorem largely follows the structure laid out in Section First, we define the key components of the features. Recall the definition of the centered and scaled features from Eq. (3):
(k)
(k)
(k)
E (k)
<
E
R- 1/2
Vn
ElØ, represents the deviation of the i-th node's k-layer feature from its expectation. This deviation can be decomposed as follows. Let ((()) be the n d matrix all features.
The term 0
(k)
(R) [ = x - E[A*x]
A - E[A (since A and X are independent given 2)
(A* E[A+))X + E[A
E[X])
Á A...
(21)
Here, À = (A*-E[A*)) captures the randomness from the graph structure A, and A [[ E(X]) captures the randomness from the initial node features X (around their means). Both Á and Á are matrices. Let Å, and ÂŞ denote their i-th rows (viewed as d column vectors for consistency with )
We define the normalized versions:
A = Á A-1/2 1-1
A; 8//2
With this notation, the centered and scaled feature for node is:
A; + A,.
For any projection vector gd-1 we denote Ai, = (Ai, 0) = AT' and Ais = (),,0) AÇ
Now, we aim show [ G) + where P.
1 n En 6,00- This is achieved by showing:
(P,,, P.)) + 0, where P., = E[Pr)
2. W1 (T G) + 0.
Part 1: Concentration of P., around P... This part relies on Proposition (from Appendix D) To (k).
apply Proposition
8 we need to verify its conditions for Y =
(a) Uniform T,,, sub-Gaussianity of projections: For any 0 E 5d-1, ((E!") )0); are uni- formly V sub-Gaussian (see Appendix C [for the definition):
"
Lemma 1. sup [l(e(") (((((M))))) ,6)1| S C' xx) for all O E Sd-1 iE(n)
13

---

Proof. Combining Propositions 2 and (from Appendix A.3 we have
[(E I.. S ll. + [|A S KD + oB
where Ko is a constant only dependent on o and I., and Bk,n o(1). The result follows.
(b) Variance of empirical moments: We have the following result:
Lemma nim Var (n Es! 03)
for all E N and 5d-1
Proof: By Lemma 5 teo (c) 0y 1, Ei= Aflle Lemma 6 gives
Var(n Σ ( n The result follows from the inequality var((A) I 6|| B B12 3 var(B) ()) for any random variables A and B in L.2.
(c) Uniformly bounded first moment of P.: suPx21 Mi < This follows since by Proposition mi (Fn,0) converge to mi (Go), which is finite, for all sd-1, The claims then follows from Proposition
With these conditions met, Proposition 8 (from Appendix D implies E P.)] +
Part 2: Convergence of Pn, to G. Proposition (from Appendix A.4) shows my ( (P,.0) + m, (Go) for all 0 and Since Go is mixture of Gausstans, it is determined by its moments. This implies weak convergence 10 Gg. The convergence of moments also implies uniform integrability of all moments for (TP,.0) n221. This, combined with weak convergence, yields Wi (Pn,,, Go) 0 for all 0 E 1 (e.g., by [1] Proposition 7.1.5)). Proposition & (from Appendix) outlines the conditions necessary to lift this claim to Wi (Pw, G) - 0. Here, we note that condition (c), supn21 (Mi (IP.) <
0o, satisfied because M1 (P,)) is uniformly bounded (as argued in Part Ic).
The class-conditional convergence statement Theorem@folloove from a similar argument by consid- ering per-class empirical measures Fn, and their expectations Fn,e, and showing their convergence to N (0, Σe). See the proof of Proposition 5 (a restatement of the class-conditional convergence) for details.
A.2 Proof of Theorem (CLT for Degree-Normalized Features and Labels)
The proof of Theorem I closely mirrors that of Theorem 2 with adjustments for the non nero means and the 1/51 scaling in the covariance. Let ppjoint be the empirical measure of (zi, Ø; and Gjooint
=(k),
be its target limit. The convergence in W1 can be established by showing convergence of expectations of Lipschitz functions x() The argument involves showing that for i Ct, ø behaves like a draw from N Nuu, En/vx).
=(k)
1. Mean Convergence: Lemma establishes that Eldb (k), converges to general limit 76.
Lemma 3. Define limiting mean 7i4 of (E[A//,)) [ Assume Assumption 4 fand suppose
Pa 2 1. Then,
max E VE 34
1/1112 S 2(k)
Under the specific community based graph model, this general limit % further simplifies for nodes within a class C, to the class-specific mean Pe, as stated in the following lemma.
Lemma 4. Under the conditions of Theorem [ (which include the CSBM structure and Assump-
tions 4 let oe cf (B(A/v,])* " be the x d row vector defined in Lemma 3 For any
node E Cg, its limiting mean of converges to 5 o7 JRM. More precisely.
11 1 o(1)
max sup
(E[T] ieC.
Proof. The expected adjacency matrix of undirected, loop-less SBM E[A] (un/n)(P- diag(P)), where P ZBZT and diag P) contains the diagonal entries of P. Thus, E[A/vn]
14

---

(P/n) (diag(())m) The difference between (E[A/v,])* and (P/n)* can be bounded. Since matrix exponentiation H + H locally Lipschitz for matrices with bounded operator norm (which (P/n) and B[A/v/ [n] are, as their entries are ((1/n) and norms are (())) and
[[[[A/u]] P/ullop ||diag( P)
/m/ppp/ []diag(P)/nl))
max n n1 Bee = O( (n) #E[M]
(22)
it follows that ||( [//VA//A un )* (P/n)* lop = O(. Given [[X] ZM has bounded row norms (from Assumption
4p. we can write:
Tfe =
+ ((EAA//))))))) - (P/N)
= (P/ 2M +(n=)) ||e [1pp11B(
Since ||e] llop = and ||[[]]lop bounded (c.g., by maxe ||Me, I VLL.), the error term O(n So,
of
Now consider the main term (P(nn))5 For a node Ce, we have et' = = (where Re,
e, ee E RR.)
(P/n) eZ /n)
(B(((((( -eT(Bi) M (since z Z/n diag diag((C.l/n) II) = =e.
where J Bil and îI diag(F1,, ... . #1) with म. |Col/n. We are given μr e.. J where BII. The difference is e? (J J.M
From the Assumption 3 -. T. + (1). which implies īi = + En where E. is diagonal matrix with entries o(1). Thus, |TT M1 op = o(1). Then, J - J = B(T [T] BF
So, ||J J Jllop < [B]]m En lopp 0(1) o(1) o(1). Using the identity A B
--1 (AAA B)B+-1-3, and since || lup and || op are O(1) (as | lop and | are
Ej= (()).
| 1* llo I k max([]J]lopp [illop)* || llop = 0(1) o(1) = o(1)
Therefore,
I 11e7 Ilap1IJ
1k 11 Mloo = 1 -1-(t)))0000000 = o(1).
Combining the error terms:
c J o(1) + O((
Since vn o(n) (Assumption 2 n o(u which is also o11) Thus, the dominant error
term is o1). The bounds are unitorm over i E C2 and { [L] because the operator norm bounds B, 11, M and the rate of convergence Assumption are uniform.
2. Covariance Characterization: The deviation Φ; [(k)
E. Φ (k) -((0 /Vn The analysis for (k)
(specifically, the characterization of its moments leading to Proposition Fin Appendix(A.4) shows
-(k)
(1)
its asymptotic covariance, conditional on 2, = f, Eg. Thus, the covariance of Ø E ()
(and asymptotically, of -(k) - bl for E C₂) is Ee/Un.
3. Moment Matching and Concentration: Similar Theorem 2 one shows that the moments of
(Ø) m4) (for i Cz), when appropriately scaled, match those of N Ex/pn). Concentration arguments analogous to Part I of Theorem 2 proof apply.
Steps 2 and above are rigorously formalized during the proof of the class-conditional version the
statement (Eq. (II) which is stated and proved Proposition X in Appendix A.4).
15

---

A.3 Supporting Lemmas for Moment Analysis
We borrow the following two key results from 18
Proposition 2. Suppose X; [E[x]] SG( and Un 1. Then, for A1,0 ( 00:
1/2
| S BB where BRn (v / 1[k is even] + (un/n))122
Proof. A component-wise version of the above (i.e. with 0 a coordinate basis vector) is proven in [8
Section 4.1]. The general case follows by a similar argument. Broadly, this follows from the fact
that A, [X [(X])/u2 Un k-1/2 is linear transformation of sub-Gaussian random vectors
{X [[ The rate Bk,n is obtained through path counting on B[A4]s for each E [n]. M
Proposition 3. Let t, = rk- - [r/2] and No = 4 max |max(C1o, C1a, 110,00 v. for distribution-dependee constant C1. Assume Assumption 4 and suppose vn, 2 For [0, 11. let
(e(E) == max(r E 2N: 3(orkee s 1/ 1-
(23)
Then, for م = ((A* 1( 8) and all S (0):
E| S (((FHo)) u/=
(24)
As a consequence, for A.. = D 1/2 we have || vr. S Kg-
Proof. This result is proven in [8] The power v/ arises from counting dominant walk structures contributing to the r-th moment.
With these propositions place, we show that, in the sparse setting, the sliced moments of (E(*A) 0) are determined by the moments of graph noise Ai... That to say, as n grows large and the graph grows sparse, the contribution of feature noise Ai,0 to our normalized features (c!*), O) is negligible. This has important downstream consequences to our limiting aggregated features, as it implies the feature noise covariance will appear in the final limiting form of the aggregated feature covariance.
Lemma 5. Assume Assumptions
and For any N:
lim max n n000 vE(n) [<c(')
((cc(*))e0) ,0 Ai. L2
O.
Proof. Using the decomposition
(<(,,,0 -i, 00 + Nioo we have
(5) (k)
0- N Σ
A Ai.0
By Minkowski inequality (for Lg norm of sums):
Σ A A
5 Σ9
A A 12
12
By Hölder inequality, with 1/p = (r 8)/T r and 1/9 = 8/T,
A Ai 1 = E|A 2(r-s) A?o0l < (EA?:)) - 8/r (EA)
This is ||Ar, 2 2(r-a) s) ||Ai, 1... For n large enough so 2r rn. Proposition (via Lemma gives || S /r. Proposition 2 (via Lemma 9 gives ||A,,llza> S o 2r. Take n large enough so that Sk,. < 1. Then, for 1, we have g2s S BR hence o| S 020 Bk,, (2r)*. Since 3r.n -+ 0 from Proposition (as Vn -> 00, Un ((n)), and other terms are bounded, the sum tends to O. The convergence uniform over as the bounds are uniform.
16

---

Lemma 6. Under Assumption and For every i, E [n], r N and 8 E sa-1,
Cov 4..) In-
In particular, Var(n Ei=1 41,0) - in-' for N and 0 E S
The proof of Lemma 6 is quite involved, using combinatories of walk sequences, and appears in Appendix E
Lemma 7. Letr E 2N and 0 < E < 1. Assume Assumption 4 and suppose Vn 2 L. Ifr S (t),), then
E
A 1,0
(r 1) Hgal S C(r) un
where 1,0 = [VE
and Vú- = [diag (pri -1-pa), Pia (1 Pin)) )) /Un 1/2
The proof of Lemma 7 appears in Appendix and involves walk-based proxy term Tha (r) and careful counting of dominant non-dominant walk structures.
Lemma (Odd Moment Control for (i,)). Under Assumptions 74 for any odd integer 2 1 and any unit vector E R
lim max [E = 0.
More specifically, E[ Ow 1/2).
Proof. This follows from Proposition vz (VTRo)) Vn
For odd r, the moment bound for A.e is o S
1/2
A.4
Supporting Results for Specialization to Community-Basee Graphs
Proposition 4. Under Assumptions 74
BEee") 00" = - Σ Te ((Jk- (O) diaaae ( 1fr even).
R-000
Stated differently, m, (P.(.o)))) - m, where Go = Et T2 N,,
Proof. We proceed in steps:
Step 1: Approximate with moments of Aio By Lemma (specifically, ||(g!*), 0) -ooole: 0
since T.2 convergence implies L1), we have B(g!a)) 00 B[A + o(1), where the o(1) term is uniform over i. Thus,
1 n B (k) 0)
Σ E + o())
Step 2: Handle odd moments. If r an odd integer, by Lemma 8 E = o(1) uniformly in i. Therefore.
lim 7-000
Σ E ol = 0.
72
2=1
This matches the proposition statement, as 1[r is even] 0 for odd r.
Step 3: Handle even moments using Te.e- an even integer, by Lemma 7
E| = (r 1)!! 3he + o())
uniformly in é. Here, T.o = IVE[A/P, -- E So we need to analyze the limit of Σn 1i=1( (r 1)!! o.

---

Step 4: Analyze 0g under the CSBM structure. We have
T (E 1 " (EX(0).
- where V?2 = Vn (Pig - Pij )- = 1/= diag (4, - diag(e [[A))). Since by
assumption o(n), we have e/ [[A] = (vv,/)) = (1) uniformly in i. It follows that
V,² U diag(e c [[A]] + o(1)
Moreover, as shown in the proof of Lemma (specifically Eq. (22 B[A/v]] P/n O( where P = ZBZ". Substituting we get
L. = -(X])) diagle P/o((// + o())
Under the CSBM structure, we have [ ZMO. Similar to the derivation in Lemma s proof:
(P/n)* -1 ZMP = = k-1 M0 = -Z.% M0.
node i E Ce, then e, P/n e/ (BZT) /n). The term Z" <''daag(e? P/n) becomes diagonal L matrix. For E Cy:
(z" diag(e; P/n)))) = Σ Zjole 2/s)
(Pij/n) Σ (B2iz//)
JEC,,
jEC.,
1/s = f (BeolC.1/n) 1ls = 5f} Bes
So, z diaag(e? P/n)Z = diag diag( diag(e? Jn). Therefore, for i Cy:
7O Th M diag(e? { Jn, (J: + o(1)
Let (J) = (Jh- diag(e? -J emrors.
- MO). This term is the same for all i E C. up o1)
Step 5: Averaging over and taking limits. For even r:
B (r- 1)!!
000 + o(1)
|Cel
1
(r 1)!!
Σ %
+
n
CCol
(r- - 1j!!
Σ
मो (0 (2
As n + 0o. by Assumption गee + Te. Also, J| Jloop + 0 (due to ñî - II). Since ( is a continuous function of its matrix argument (in terms of matrix entries or operator norm for fixed M,O, B, ee, k), we have (J.) + (J) Let o = (J=-1 M0) (J) diag(e? J)(Jk-I The limit becomes:
(r- 1)!! Σ Te(a
t=1
This is precisely the r-th moment of G, Et=
N,0,
(1))) Note that o = 00EE0 where
Σg = (JR-1 M)Tdiagtt J) M). The proof is complete.
O
Proposition 5 (Part of Theorem Consider the setting of Proposition i E [L). Then for any R > 0:
Let Gy = N(, Ex) for
E
sup (h..pp
ΣΣ (e(
Σ M ~G, (F((1)
+
+0.
ELip(R) n
E=liECe
18

---

Proof. Let Pn,e = 1 Eiec, 8 0000) be the class flass-conditional empirical measure for class t. Let ft E Li)(R). We can assume fe(0) = 0 without loss of generality by considering fe(z) fe(0), as this does not change the difference of expectations for centered measures and preserves the Lipschitz constant. The term we want to show goes to zero is:
Kdl
Ce Pn.elfel
A
sup Su Eipp((
Σ GeGelffl
n
Using the triangle inequality:
Ce P. e.ee Tell Tellnn elee
A S
sup f El.ppp sm1
+
sup
mrefP,,elffd TeGeffell
/1../ (Lip(R)
CC
sup (eLip((
Pn,eLfell
t=1
We
sup ((Elip(R
PP [ Ge[fe]l-
{=1
The second term is El=1 ue W1 (F Ge) by definition of W1 (scaled by R). Let Ti, and T2,1 be the two terms.
For Tin Since fe(0) and ft E Lip(R), [f.e I Pn,elff(())] I R Pn. So, Elsupyetiip (eeellelll I R E[P,, [|==||]]] = R Pn,e[|=[[]]] The term Fnl
Ce Eiec, || (8) []] From the proof of Theorem 2
(specifically Part Ic, relying on uniform integra- (k) is bounded for all i. Thus, sup, Fn,,[]|=[]] is bounded (as + O. Therefore, [n] - 0.
bility of moments of P.),, sup,,
Bills
|ca] + co). By Assumption 3
Ce
For T2.:: We need to show EF Ge) + 0 for each l. By the triangle inequality, Wi WP,,n,e Ge) & (P,nn, Pw.e) + (P n.,, Ge). For the two terms on we have:
(a) (P Pn.e) + 0: Pr,e is empirical measure of N₂ Cel variables (c!x) i e C.). Since No + oo (as me > 0), we can apply Proposition to this specific subset of variables. The conditions for Proposition g are: (i) Uniform V
rx, sub-Gaussianity of
(s!")) 0) for i Cs: This holds from Lemma (ii) Variance of their empirical moments Var(N, Eiec, (k) .00)) - 0 holds from the more general formulation of Lemma where Cov(A (g.)) S (((4)), (iii) sup, M1 (In,e) oc: This holds as shown for Ti.. Thus, ([ n.e: Pn.e)] + 0.
(b) Wi Gt) 0: We analyze the moments of P,,, n, for a given 0 E Sd-11 m, (P. n,,,0)
ला Eiec. (R) "((,(")0)') 00"]. From Steps 1, 2, 3 of the proof of Proposition
know that E| (k) 0y] = B ol + (1). If odd, E o(1) by Lemma 8 my (Pr,,,,) -
0 = m, m,(n,,N (N(0, 0t E,()) If r even, E[A,, = (r - 1)!! ~. + o(1), where the o(1) is uniform in i. From Step 4 in the proof of Proposition 4 for any E Cc, 0i + o
8 E,e. Thus for i Ce, E((s!*) _001 (r - 1)! 1fr is even). This limit is uniform for all i E C.. Therefore,
(k)
my (Pn,e.)=
(r-1)!!( 1 1r is even] + o(1))
Cel
sEC2
+ (r - 1)!! 1/2 1fr is even].
19

---

This is (N, E,0)). Since GG (0, E2 is determined by its moments, and its moments are finite, Fn,, Gg The uniform integrability of moments for ne,c. is inherited from the global case (as seen in Ii argument, (P(,en.)) is bounded for any p). This promotes weak convergence Wi n,,,, Go,0) Then, by Proposition g Wi WI(P n.e, Ge) 0.
Since [ (P n.e: Ge) - for each l, and my are constants, [T + O. Combining E[[i.n] + and E[T2,n] + 0 completes the proof.
Proposition (Part of Theorem Then for any R > 0:
Consider the settings of Proposition 4 Les Ler = N Ee/voo
L
L
E
sup fL
Se(Øz
(k)
Σ
Te Te BBn,
n 8=1 iEC,
Proof. Let Pn,e e be the class-conditional empirical measure for of (k)
for class e:
PR,
Σ )(
Cel
iEC,
Let A, be the term inside the overall expectation:
Crlp [Rc] Σ Ge
A =
sup fu (R)
f
n
t=1
Similar to the proof of Proposition using the triangle inequality:
L
A
sup feELip(R)
jPP.
(:= Tin))
t=1
Pn.efee -Cmelil (:= TV
sup feELip(R)
1m1
The second term is Et R.R W1 (Pn,,, Gn.)). We can assume fe(0) 0 by replacing fe(x) with fe(x)) (0) and noting that [Pn,elf((O)] -o..f((())GG.(.(())) G,,(f((O)) Before bounding the two terms, we first show that
(fe(0)) - f( =
E p Mell2 0 uniformly for Cg.
(25)
By Lemma 3 and Lemma 4 B[o (h) + th for i C.. Next,
Var(ø: (k) Var(s! /Vvn) Σe/vn + o(
uniformly over i E C,, by noting that the convergence in the proof of Proposition
4 is, in fact, uniform
over E C2 and 0 E Sd-1, Since To - Hell2 & El[ (k) E (k)
lll +
T pe pell2, and the
first term is bounded by (tr(Var (k) 1)) 3/2 Ovn Opp=1122 = o(1), and the second terms is o(1) for
i C₁, the claim follows.
(k) [I]. By eq. (55) E o |I] converges to ||me|l which is bounded. Thus, sup, Elsup,, [e,eefell]] is bounded. Since
For Th. E(sup, [Pe]e[ee]]] s I [||+|||]
R Cc Eiec Elll
Cel de + 10by by Assumption 3 B[TY,,. + 0.
For T We need to show E[W, (P. n.e. Gn.e)] + 0 for each l. Let f E Lip(R) with f(0) 0. Let
P F, .......). We first analyze
[Pn.ll] G.lllfll [cpl
Σ El((
- -Gnelfll.
scc.
20

---

where P pn,
1 Eiec. [i
(k)
Using the decomposition for a single E Cy:
C2
[ Gr,lffl s Bl(
Blf(ue)))))))))))))))) - -a.
Let these two terms be A, Br (Note B, is actually independent of i for i Cj). Since f E Lip(Rt):
A4 S R- o (k) - Hell2 = Olv 1/3 uniformly for i E C₁. by eq. 25
For Bi, we have
Y)] 3 R. (EY.NNO..,..... B. = BY - f(ue +
-
and No. [1V||2] S Vtr(E//u)) O(u 1/3) So B: -0 1/3).
Thus, uniformly over i E Ce and f E Lip(R), we have " Gneeffll Ovvil/3) establishes Wi (P n.es G..,) + O.
This
Now, for the concentration part E(Wi (Pn,t, + 0: We will verify the conditions of Proposition for the variables Xi, 04 for i Cs:
(k)
(k) ii Uniform V,, sub-Gaussianity of (0, 0): Since ght² 1 =E(b, + ((()) /Vun, we have
(k) 00,l.... S (1 [ Φ. (k) llo.. + [I(5(() /VTn 0) 0)11u..
<E 1 031 1111|v.. + 11/5(t) // (Paa8yllu 8/11v.m
the first term bounded in the limit by Clus, 0) where C lim sumsu || ll, is universal constant, and the second term is O 1/2) by Lemma 1 both uniformly over E C2 and 0 e gd-1
and Me is bounded, and -/0// /vP has vanishing v norm (as (k)) has bounded Vi norm),
o (k) 0) will have bounded 4f r,,, norm (dominated by (pe, 0) plus small term).
(ii) Variance of empirical moments: Var(N, Eiec, (Ø) (k)
=(k)
0y)) Again, we use o;
E (k) (*) /vn. By argument similar to Lemma
obtain
||
(k) 8)" -E
(EΦ, 10)"1le= 1 Σ ( EE, 0))| II(E!*) /V li (26)
(k)
r- since the quantity is deterministic. This is uniformly bounded over i E C2 and 0 E gd-1, by eq. (25). Similarly, (ICE(*),))) 00]| is uni- formly bounded over i E C, and 0 gd-1, by the argument in the proof of Proposition 4 (the convergence of the moments is uniform over E Ct). follows that (!(=(*) /yPn 8) Iiia.
We have |KE (k)
0) ((Bo 0) 1--
(k)
(v x/2 O(ym 1/2) for 1, uniformly over i and 0. The same then applies to LHS (k)
of eq. 26). This in turn implies ||N;" Eiec, (0; ,,)" N Eiec, (RØ, 00)||
o11.. Now, Var(N.- EiEC, (Eø, (k) , 0 since this quantity deterministic. This
implies (see the inequality in the proof of Lemma Var(N ",Ee,,, (0, (k) .0)) = o(1)
which the desired result.
(iii) sup,, M₁ (P.)n.)) <
cc: This was shown for Ti,
Thus, by Proposition 8 W P. + 0.
Since B[W, (IP..,, Gn,+)) - 0 for each E, it follows that E[T - 0. Combining E[TY,,. - 0 and ETT + 0 completes the proof.
21

---

B Moment Characterization in W
In the following (lin))21 and HI are all (Borel) probability measures on R Proposition 7. Assume that (1m))21 is sequence of (Borel) measures IR such that
10'a'"dH,, (x) < co, for all A Rd
sup n21.
Then, supn21 I ||=||] (x) < oc.
Proof. Let {0I,..., 0m be --tt of the unit sphere S 10 E R ||0|| 1}. We have ||>||| su 10txl 21 maxxemmm 10 x/.
follows that |||||" s 2" maxie(m] 10 x|" s
D 10 , hence
sup / [H)) #21
m
S 2"
2 sup
10 xf' (H) < xo
proving the result.
C V sub-Gaussians
Definition (v, sub-Gaussian). Let 2 2 be real number, and vr [0, oo) [0, oc) be defined
by
V (x)
(27)
The corresponding Orlicz (or Luxembourg) norm for a random variable X is:
|| inf K 0: E (IXI/K) < 1}. Lemma 9 (Norm equivalence). Let X be random variable and 2 2. The following holds:
(28)
(a) Norm implies moments: || S K for some > 0, then
(/ s SCKV for all 2
where C1 > 0 is a universal constant.
(b) Moments imply norm: If (E)XP) < for some C > 0 and all E [2, r). then
|X|,, I C2C
where C2 2
Proof. Part (a) Assume |X|l,
K. By definition,
EVV,((X//K) 1.
lr/2
(XX/K)22
E
j!
For any integer ju (1, [r/2]], let p
2jo-
Since all terms in the non-negative:
X P
E
EE <
SE
KP jo!
Taking the p-th root: (E < ((p/2)))) Using the inequality m! I [e/m(mm/e)" for m pp22 1:
So. E| <
(//22)) < (e (2 (eVD/2) = (ev //2
P
2c
22

---

The term pe 1/2 is bounded by universal constant c' for p 2 2. (It tends to a + o0). Thus, (B I Kd' (2e) yp for even integers p E ( Now, let E [ be any real number. Let 2 2[p/2]- Then q is an even integer, p S S ++ < p + 2, and q S 2 (2 2[r/2J. By Lyapunov's inequality:
(E| I (B|x1") - Kéd /1/(2c)
Since q 1 p and p 2 2. we have q S p p 2p. So v S v2p vV==v Therefore. (E] < Ké', (TdevI/((2222/))
(c' 1/ee) K vp. Setting C₁ = VT/e (a universal constant)
proves the first part.
Part (b) Assume (B|X))) < Cvp for p E r2. We want to find & such that E[V, s 1.
1r/21 1
k
Let p = 2j. Since j [r,]]]] p [ the moment bound: B| S (C-D)² = CPpP/2
This range is contained in [2, rl. So we can use
//
C (2
E/ ((X/(/I S
Σ
k2
Using the bound (2/) S (2e)::
|r/2|
(2)())))
[r/2]
2e02
E|V,((X//E) & Σ 1=1
Σ 3=1
k2j
h2
This is geometric series with ratio R = 2c02/k2 If we choose k such that R S 1/2, the sum is bounded by //=((1/)² 1. We need 2cC2/k2 S 1/2, which means 122 > 4eC2, Let
k V4cC /eC. With this choice of k. have ((X/A(X)) I 1. By the definition of the norm, | S k 2/eC. Setting C2 = 2/e proves the second part.
Lemma 10 (Tail bound). Let Y be random variable and r 2 2. Suppose ||||,, S K for some K > 0. Then there exists universal constant co > 0 such that for all t 2 coK:
P(Y| 2 t) S exp min 12
(r2111)
where Cj 1/(44fe) and C1 is the universal constant from Lemma 9 a). The threshold constant is co 20ive.
Proof. The assumption |Y|| w- < K implics (E|Y < C,K p for all p E [2,2[r/2]] by Lemma aa). Let r/ 22r/2]. This matches the condition (56) of [18 Lemma 25] with A = Y.
= 2, Kiem = K, Ctem = 2C7, and ro replaced by r6- Lemma 25 applies for x 2 4Ciem = ((2CT)(1/2) = 4Cfe. It gives the tail bound:
POY| 2 13) < exp
min
2Cieme mó )) exp (- min {
1acfe' Lr/21})
I
Let t 1/2 so (1/K)². Substituting x in the bound yields:
The condition becomes t > K KAfcee= 20 Vek.
min {
(1/K)² 4Cfe Lr/21
P(YY 2 1) < exp
Setting C1 1/(ACfe) and co =CCi V gives the desired result.
23

---

D W Concentration of the Empirical Measure
We use the following general concentration result for the empirical measure of dependent variables, established in the companion paper Amini and Vinas (2026) We reproduce the result here for reference.
Proposition 8. Let (n #/2 E dy be the empirical measure of vector-valued random variables Vi, E Rd for [n],, and let pnn Epn. Assume that for some sequence I' = =1( and for any 0 E S
(a) (0, Xi is uniformly vr Sub-Gaussian, that is, there exists ((0) > 0. such that suPie[n] [1 Vl, ((0)-
(b) var(n 1 (0= Yi,))") - 0 aas 0o for all E.
(c) suppz1 Mi (jmn) xc.
Then, IE W pn)] as n co.
The proof of Proposition 8 rellie on approximating Lipschitz test functions with polynomials via Jackson kernels. This approach requires precise control over the growth of the polynomial coefficients. For completeness, we list the key approximation lemmas used in [2] to establish the result.
Lemma 11. Let Tg be the kth Chebyshev polynomial, and let [Tkl be the coefficient of x² in Tz(x).
Then, [T I 1 lndd
[Tx]al S (1 v2)* 3
SSjSk
Lemma 12 (Chebyshev-Jackson approximation). Let B 2 3. Then, for any f [-B, + R 1-Lipschitz with (0) O, there exists a polynomial P(x) -ijo oja), with m 4N, such that
18B
sup [f(z) - [(z)) s
|cyl 6B 3m for all j 0.
E RR
m
We refer the reader for the detailed proof's Proposition 8 and the derivation of the coefficient bounds.
E Remaining proofs
E.1 Proof of Lemma 6
Let (i) be the set of directed, length i walks starting at node i E [n]. We consider r-tuples of walks called walk sequences where w (i) gives (w"),=1 with w" E Wx(1). We
define the last vertex projection p (i) - [n]] and walk products A = IT Aigie with w* = ((ie, fe) Relating back to Aio, let
e(w) = II (Aw E[Aw-r (xp(w))))))))))))
with = XO. Then
E [
Σ o(w).
WEWI(
Further let [w] and [w] be the set of unique edges and vertices, respectively, found on walk w. A walk sequence w is said to be overlapping if for every E [r] there exists a distinct s' E [r] such that [w=]] n [w=]] 3 Ø. Walk sequence which are not overlapping have e(w) = 0. For this reason define the following walk sets
(i). == {w E W[( w overlapping, [[w]]
[[w]] m}
(29)
24

---

where [w)] = 1²=1/ [wm] and [w]] = --=1|
The walk sets (i)).. form a partition for ( with 2 <044+1 t. S rk - [rr/2]. This gives the sum equivalence
and 1 S / $ 4, where
2+1
Σ
e(w) = ΣΣ Σ e(w),
WEW
t= t= w
which gives fine-grained control of g(w) for the specific walk sets N,,,, (t).
To prove the result, start by expanding the variance of the r-empirical moment of 7
Var
Σ
(30)
m
n²
1
By the -2 scaling over i E [n]. it suffices show
Cov A3.;) = oI - 1E nn -)
for every i, E [n].
Introduce the new notation for walk-sequence pairs (NU, (b)
e(w, w) = E (II (Aw - ()=pt))
[II (Aw ()x()))x((00
s=1
s=1
Then, the walk-linearized covariance expansion
Cov Ab,0)
E (wn, (EE
o(w, 20) e(w)
(31)
Vn 1)
We are interested in the case g(w, w) does factorize as e(w, w) ((w) o Collect walk pairs under the concatenation notation w ü = (ww..... w", w ,..., W and define the walk set
My = [(w, w) "WT() w/D overlapping, || w| t, || w|ll 2, || [
0}.
(32)
The last condition of (32) filters walk pairs (un, () which factorize e(wr w) e( Similarly, if w t0 is not overlapping e(w, i) = 0 and, consequently, ((w))(())))
Let's start with the case i'. By the set construction in 32). MM.. (i, S (2). So
[.M (1, i) < (i2 and by the counting result [18 Lemma 13]
Mr. s (u 1)2nk n )
(33)
similar argument can be made when i and i' are distinct. By fixing and i' we are left selecting (==2) unique vertices with walk selection factor of (u - 1)2rk Altogether,
(i.t.. S (u - 1)ark n 2)
2 2
(34)
For bounds on u and we note that u == w ü is an overlapping walk sequence, which by the partition
result [18] Lemma 12], means it must have, most, [[4]] < 2rk unique edges. Similarly, the
number of unique vertices bounds as [[u]] < [[x]] + since the discrete graph ([и],, [u]) associated
with is necessarily connected by the rooted nature of the walks in the sequence u (walks must start
at or z') and the last condition of (32).
Next, we consider the bound |e( w) < 2 max Wb), (e(w) ()) Introduce the notation,
(1(w) = E [T, (Aw - [[[A==))] and 02 (2(w) = E I =1 [p(w-)] ]. We analogously define,
(1(w, w) = e1 (w (w)w) and @2 (w, w) = 02 ()(w)w). From 18
Lemma 10],
lei (t (w)) 2 (vn/ ||=]|++[[0|] < 2n (vn, /n) [|m|aa]||| and [e (w, w)) < 22 2 (vn/n) [m/[
25

---

and
[2(2w) (w)) I (ko) 2 and
02 (. w S (2vTko)
where Ko is defined as in Proposition
Let t, = r2(h 1) then
4.
Cov ( 10,w) S
(4vrRo)2* 2r
(35)
(2k-11
Un
t= u=
For the case = i', cardinality and [Mnnvo(i 8)1
n0-1 < n' by (33
4. ++1
S
(4Vrko)2 - 1
(22--1)
Un
1=1
(2k-
V/
where the last line follows from the fact and & are fixed relative to Similarly for the off- off-diagonal case of # Y', (M,..(1, 2')l S n² nn"2
S n'=1 by (4) and
4. (4VTRO)
1
((2k
122
U/
Noting f. = r(2k 1), this proofs the claim that Cov (ov(A,,0 1b,z) S n 1((1))
E.2
Proof of Lemma 7
Shown in 18 the dominant term in a walk-based for Âς, is given by the proxy term
Th'(r)) 11!
Σ
II PG. (1 Pij. (c) [E(]])
where pr/2 Ma) is the set of coordinate distinct (r/2)- on [n] \ {t). Specifically, was shown for E 2N and vn sufficiently large
| un (rk- ()) s C(r)x =r5)
(36)
where can be used parameterize the separation of higher- and lower-order terms م 18 Lemma 14 and Lemma 18).
To obtain the limiting closed form, we utilize [[m]
pr/2 P C(r)n and
r/2
Σ Pig(1 - (1)0- f/2
Σ
II
Pisel pije) P1
jEIm)
For brevity, let fi(f) = Pp))c((Ao- (X 1/2
Then, noting P PM)) S [m]
|0 (rk-r1/) 77t1 (r) - (r- 1)!! [[B[[[])
r/2
r/2
= (r - (1)! Σ
II
Σ
q=1
/22
S - [m]]
p1/2
(max /())
JE(m]
Let We-1(i) be the set of k - 1 walks on [n]] starting at j. Then, with W = We-1(i) x w
f(() (pt./vn) Pij)
Σ
II
[X0)) p( II (P(wr))/
wc NOEW.,10
#=1
26

---

Recall that ( < xs by assumption. Since [ S [[x]=-||= n=-1 and Piy/Un S 1/n we have
Лi()) S sL/n
for every i.j [n].
Altogether, this yields the inequality
(r) - (r- 1)!! VEE
C(r)a'n
where constants not depending on J. have been absorbed in C. Noting that n- S vn for 6 < and piecing together with (36) produces desired bound.
E.3
Proof of Lemma 3
Similar to the proof Lemma we begin with walk analysis, Define the simple walk partition element (i) {w (i( [w]]| = t, [[w]] -v. Note that, in this case, (i) no longer has an overlapping constraint. As such.
k
H+
8)1
ΣΣ D
Σ
E[Aw (((0))p)))
2=
(E)
where notation A.. Iê Aigie Similarly define (B[A)) I R[Aicie for walks on the the edges of w are all unique and the expected matrix E[[]]. Note that, when = expectation factorizes
Σ
((X0))((X)ppcu)))
Σ (E[A)) B((X0)
wEN
Therefore,
E B
00] -97
(7
vy ΣΣ E (E[[A) 114A)~(BBJAnl (E()))(()))))((((()) 1fu + k 1}.
(1)
Setting r = 1 in Lemma 13 of 18 gives the counting bound Dd+1 (in,((i) S (en)), Finally,
noting that [[Aw] (E[A))= m - 2(v,/n)) lmo,
b 1+1 U
[[ 0)] (77 0) -
(k)
W (v) 110 +
1-1
(i.
+ (1
< (k- 1)
1
* ''r..' Σ
+
1 1=1
< Clk)sau
Since the above holds for any i [r]] and any gd-1
KE PM) [B[0 (k)
7f max max [K(EEO0 (k) 1 < C(k)a.m kela BEg4-1
max
Joint Wasserstein Distance and the Class-Conditional Supremum
In Theorem state that the joint empirical distribution converges in 1-Wasserstein distance and then provide a related, gronger-looking glass-conditional convergence statement (1I). This note formalizes the relationship between these two quantities, showing that the latter is tractable upper bound on the former.
Consider the joint space [L]] I with the metric d( 91), (z2, (2))12) = 1(2 + +lyi y2ll 12ll2- The true joint I-Wasserstein distance is the supremum of the difference expectations over all 1 I-Lipschitz functions F ; [L] Rd +R R.
27

---

Distribution of Poly-GNN Features for 2-Class SBM
0.30
Empirical Theoretical
0.25
Density
0.20
0.10
0.05
0.00
-10.0
-7.5
-5.0
-2.5
0.0
2.5
5.0
10.0
E(k)
Figure 5: Empirical distrihution of a two-class CSBM with exaggerated class proportions and edge probabilities. Both mixture components centered at zero with visible difference between the peak widths and heights of each component.
A function F is 1-Lipschitz with respect to this metric if and only if its component functions, (2) The collection {fe] is jointly coupled by the constraint [fe, (y1) fe, (y2) S + 11 2/ for any & * lz.
fe(v) == F y), satisfy two conditions: (1) Each ft Rd + E is I-Lipschitz.
In contrast, the cansiioondiional expression in Eq. (II) takes its supremum over all possible collec- tions of 1-Lipschitz functions { without enforcing the second joint constraint.
The set of test functions for the joint Wi distance is therefore strict subset of the functions for the class-conditional expression. Consequently, the class-conditional expression provides a valid upper bound on the joint L-Wasserstein distance. This justifies our proof strategy: showing that this upper bound converges to zero is sufficient condition to prove the desired joint convergence.
G Simulation Details for Figures
This appendix details the experimental setups for the figures presented in the main text. Specific parameters for these and all other figures are provided in the subsequent subsections.
G.1 Details for Figure
The plots in Figure were simulated from a 1-class SBM, commonly referred to as an Rédös-Réyni graph, with probability parameter p Vs/nn. Depth & = 3 used with unit, univariate features X; = for E [n]. A grid search was performed on graph sizes n E (300, 3000, 30000] with expected degrees Vn {2, 4, 16}. These graph very sparse, yet they approach Gaussianity fairly quickly. Particularly, the plot associated with v,, = 16 has nearly symmetrical tails and a bell curve shape.
G.2
Details for Figure
The plots in Figure 2 were generated using a 3-class CSBM with n 8192 nodes. Class proportions were म = 0.25, πश = 0.45, n3 = 0.30, average degree parameter was vn /8192, and the inter-
00.4
1
community probability scaling matrix was = (vn/n).
0.4
1
Initial features X, where
0.4/
d 2 dimensional and generated X, N(M, M 0²
with o² 0.25 and M1, 2
Ma.- -3 and Ma., 1
28

---

Cross entropy training was run for a single linear classifier layer for 10 epochs with learning rate 10 on the SGD optimization. Although small differences are expected later time steps. Figure still shows good agreement between the empirical and theoretical gradient average.
G.3 Details for Figure
The plots in Figure 3 were generated using 2-class SBM with 32000 nodes. Class proportions were = 0.4, T22 = 0.6, average degree parameter was V/ 30, and the inter-community
0.5
probability scaling matrix was (vn/n) mn)
Initial features X, were dimensional
0.5
drawn from mean vectors M1,, 2 and M2,+ = [-1,-- -24. Quadratic discriminant analysis
(k)
was performed using the sample statistics of o; with 2. Cross-entropy training consisted of
single linear layer trained for 5000 epochs at learning rate 0.5 with SGD optimizer
G.4 Details for Figure 4
The plots in Figure 4 were generated in the same setting as Section G.3 with the exception of a higher
(A) average degree Vn2 35. The plots show Kernel Density Estimates (KDEs) of the क; features for k E {2, 4, 6}. The KDEs were computed using Gaussian kernels with bandwidth selected by Scott's rule.
G.5 Details for Figure
The plot of Figure 5 was generated from a 2-class SBM with 32000 nodes. Class proportions
were J1 = 0.9, π2 = 0.1, average degree parameter was V = /32000, and the inter-community
(10
0.1
probability scaling matrix was (un/n)
Initial features X, were dimensional
0.1
10
and generated X, (MM,, o²) for Mi 10-2, 2, M2 10-22 and 0² 10-4.
For the plot of Figure 5 we simulate 100 CSBM graphs each at 32000 nodes. From these 100 replicates, we obtain an estimate for [[{( with h: = The final figure is 100 bin histogram of the 3200000 empirical elements with theoretical density given by our theory drawn on top.
29

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In our abstract we highlight a feature CLT and potential explanation for GNN
oversmoothing. Both points addressed in Sections 3 and
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [No]
Justification: Limitations were not discussed but could revolve around the question of generative model. remains an open question whether Poly-GNN feature CLTs hold for non-community-biee graphs
Guidelines:
The answer NA means that the paper has 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 separate "I "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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
30

---

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

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: Code is not instrumental to understanding our result. Plots are supplementary to the theoretical results shown in this paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.ccpublle wwwppppguuuiiieeeep http:///uuiiees/deeuuuubiiis
(CodeSubiisss wwtauubmmsssooni ssiiiioicccy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
No benchmarking was done for this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: Figures provided are for visual aid. No tables or statistical tests were provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
32

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: Computer resources included one local machine with 64Gb of RAM and a Nvidia 4090 GPU.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
Our theoretical results do have direct causes for harm ethical concerns.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This did not seem relevant to the work we presented.
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 why the paper does not address societal impact.
33

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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)?
Question:
Answer: [NA]
Justification: No model is released as part of this paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: No external models or assets were used for this paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
34

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
There are no new assets introduced by this paper.
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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. 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:
No crowdsourcing was used for this paper.
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 contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No participants were studied.
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 NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
35

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [No]
Justification: Core methodology and proofs were not changed due to an LLM
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy for what should or should not be described.
36


Reviews:
[{"review_id": "IFSTrY8DJu", "reviewer": "Reviewer_ovye", "summary": "This paper provides a rigorous theoretical analysis of the asymptotic behavior of k-layer Polynomial Graph Neural Networks (Poly-GNNs) on sparse community-based graphs, such as those modeled by the Contextual Stochastic Block Model (CSBM). The authors derive two central limit theorems (CLTs) characterizing the empirical distributions of Poly-GNN embeddings:\nTheorem 1 proves that the joint distribution of degree-normalized node embeddings and class labels converges to a mixture of Gaussians with vanishing covariances.\nTheorem 2 shows that the centered and scaled embeddings converge to a stable mixture of multivariate Gaussian distributions.\nThe paper also analytically characterizes mean and covariance collapse under repeated aggregation, offering a precise mathematical explanation for the oversmoothing phenomenon observed in deep GNNs. A key contribution is the demonstration that training a linear classifier with cross-entropy loss on Poly-GNN features is asymptotically equivalent to training on the limiting Gaussian mixture, offering theoretical insight into GNN training dynamics.", "questions": "Applicability Beyond Poly-GNNs: Can the authors comment on how the analysis might extend to nonlinear or weighted GNNs (e.g., GCN, GAT, GPR-GNN)? What technical barriers exist?\nSensitivity to νₙ Assumptions: Many results hinge on νₙ → ∞ and νₙ = o(n). Are the convergence rates or limiting distributions significantly affected if νₙ remains constant or grows slowly?\nPractical Implications for Model Design: Given that the class means collapse to a 1D subspace, can these results motivate architectural changes (e.g., early stopping, skip connections, regularization)?\nEmpirical Validation: Would the authors consider adding numerical simulations (beyond Figures 1–3) to illustrate how closely the empirical distributions of embeddings follow the theoretical Gaussian mixtures, especially for moderate n?\nBeyond CSBM: The authors mention the challenge of generalizing beyond community-based graphs. Can they speculate on potential extensions or possible failures of the current CLTs in graphs with heavy-tailed degree distributions or assortative mixing?", "limitations": "No — The paper does not adequately discuss limitations, although the authors indirectly allude to model constraints. I recommend:\nExplicitly stating the limitations of the Poly-GNN assumption (e.g., no learnable weights or non-linearities).\nDiscussing how sensitivity to νₙ or non-community-based graphs may affect the validity of the results.\nConsidering the gap between asymptotic and finite-n behavior, especially since real graphs are not infinitely large or cleanly community-structured.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Quality\nStrengths:\nThe mathematical exposition is rigorous and detailed.\nThe CLTs are proven with clear assumptions, and proof sketches are well-motivated.\nExplicit formulas for limiting means and covariances are derived, which are novel and impactful.\nWeaknesses:\nNo experimental validation beyond illustrative figures; this limits the practical understanding of how well the theoretical predictions manifest in real datasets.\nAssumptions (e.g., community-based graph structure and νₙ → ∞) may be restrictive in real-world applications.\n\nClarity\nStrengths:\nThe paper is very well written and logically structured.\nEach section flows naturally into the next, and technical results are motivated with clear intuition.\nThe discussion on oversmoothing via spectral analysis is particularly enlightening.\nWeaknesses:\nSome parts of the proof outline (e.g., sub-Gaussian arguments, moment bounds) assume familiarity with advanced probability without intuitive explanation.\nNotation can be heavy for non-theory audiences, especially in the oversmoothing section.\n\nSignificance\nStrengths:\nOffers an original, quantitative understanding of GNN oversmoothing—previously treated heuristically in much literature.\nBridges the gap between feature propagation theory and classifier training behavior.\nWeaknesses:\nApplicability is currently limited to polynomial GNNs on stochastic block models, which may reduce perceived generality.\nImpact on GNN design may be indirect unless extended to more expressive models.\n\nOriginality\nStrengths:\nThe use of CLTs to characterize GNN embeddings under label-aware graph models is novel.\nProvides, to my knowledge, the first exact analytical treatment of Poly-GNN oversmoothing via spectral power iteration arguments.\nWeaknesses:\nThe Poly-GNN class considered is a simplification of practical GNNs (e.g., lacks nonlinearity or learnable weights), which might limit originality for practitioners.", "was_revised": false, "final_justification": "", "rebuttal": ">  Weaknesses: The Poly-GNN class considered is a simplification of practical GNNs (e.g., lacks nonlinearity or learnable weights), which might limit originality for practitioners.\n> Can the authors comment on how the analysis might extend to nonlinear or weighted GNNs (e.g., GCN, GAT, GPR-GNN)? What technical barriers exist?\n\nIn its current formulation, our work allows for non-linear and learnable transformations on the already aggregated node features $\\phi^{(k)}$. The authors are also interested in CLT-like results for non-linear models of aggregations. The path formalism which our current results are based on are flexible enough to handle ReLU-based gating seen in standard graph convolutional neural networks. As shown in equation (1) of [1], this would require introducing a gating random variable $H_{i,j}$ which depends on the path history of terms between nodes $i$ and $j$. This would include a path-dependency complication to the analysis however some simplifications could exist given the short-circuiting behavior of binary paths ($H_w = 0$ if $H_{w'} = 0$ and $w'$ is within $w$). A similar complication holds for the case of a learnable weight $H$ where, under the element-wise multiplication $H\\circ A$, the aggregator $H\\circ A$ now has paths $(H\\circ A)_w$ which are not homogeneous in expectation (even in the 1-community setting). It remains an interesting open problem on how to extend our current results to the case of path-dependent aggregated quantities.\n\n> Sensitivity to $\\nu_n$ Assumptions: Many results hinge on $\\nu_n\\to\\infty$ and $\\nu_n = o(n)$. Are the convergence rates or limiting distributions significantly affected if $\\nu_n$ remains constant or grows slowly?\n\nThe requirement that $\\nu_n\\to\\infty$ is indeed necessary. See the empirical failure for small $\\nu_n$ we discuss in response to your other question below. In the context of social graphs and other real-world networks, the setting of $\\nu_n = o(n)$ is practical. Our arguments still work for the dense regime $\\nu_n = \\Omega(n)$ but the limiting characterization of the covariance would need to change, as the feature noise would no longer be negligible in the limit. \n\n>  Practical Implications for Model Design: Given that the class means collapse to a 1D subspace, can these results motivate architectural changes (e.g., early stopping, skip connections, regularization)? \n\nAlternatively, this may inspire additional research into flatter GNN with more expressive propagation mechanisms. Recent implementations of spectral GNNs [2,3] seem to favor this flat architecture with expressive propagators.\n\n>  Empirical Validation: Would the authors consider adding numerical simulations (beyond Figures 1–3) to illustrate how closely the empirical distributions of embeddings follow the theoretical Gaussian mixtures, especially for moderate n?\n\nFigures 4 and 5 in the supplement (Appendix G, p. 36) already provide this comparison. Even for small $n$, the empirical distribution aligns remarkably well with the predicted Gaussian mixtures. The decisive factor is the degree parameter $\\nu_n$: values as modest as $\\nu_n = 16$ suffice, whereas very small $\\nu_n$ lead to noticeable deviations, as the plots show (and inline with our theory). In our revision, we plan to move one or two of these figures into the main paper now that we have an additional page.\n\n> Beyond CSBM: The authors mention the challenge of generalizing beyond community-based graphs. Can they speculate on potential extensions or possible failures of the current CLTs in graphs with heavy-tailed degree distributions or assortative mixing?\n\nOur framework should extend to the **degree-corrected stochastic block model (DCSBM)**, which naturally accommodates heavy-tailed degree sequences. When the (normalized) degree distribution remains stable as $n$ grows—that is, all degrees scale at the same rate—we expect the a similar CLT to hold, perhaps with some adjustments to the limit. In contrast, if the degree distribution’s tail becomes progressively heavier with $n$, the variance conditions underlying the CLTs may fail, and alternative normalizations might be required.\n\nRegarding **assortative versus disassortative mixing**, the general SBM analyzed in the paper already allows any combination of within- and between-block connection probabilities, so our results cover both assortative and disassortative regimes without modification.\n\n\n> Limitations: No — The paper does not adequately discuss limitations, although the authors indirectly allude to model constraints. I recommend: Explicitly stating the limitations of the Poly-GNN assumption (e.g., no learnable weights or non-linearities). Discussing how sensitivity to $\\nu_n$ or non-community-based graphs may affect the validity of the results. Considering the gap between asymptotic and finite-n behavior, especially since real graphs are not infinitely large or cleanly community-structured.\n\nWe will add an explicit **Limitations** section. Key points:\n\n- **Scope of the theory.** Our results characterize multi-hop features optimized under Lipschitz losses. They exclude nonlinear propagation and other complex GNN variants; extending to those architectures is future work.\n- **Learnable components.** Trainable functions can act on the aggregated features (the “head”), but the propagation operator itself is fixed. We will clarify this constraint.\n- **Dependence on average degree $\\nu_n$.** The theory holds for $\\nu_n \\to \\infty$ up to to $\\nu_n = o(n)$; the unrealistic $\\nu_n = O(1)$ regime is excluded, and $\\nu_n = \\Omega(n)$ requires additional arguments. Empirically, asymptotic behavior appears once $\\nu_n \\gtrsim 16$ (Appendix G).\n- **Model class.** We assume an SBM. While this omits truly arbitrary graphs, SBMs with large $K$ are universal $L^{2}$-graphon approximators [4–6], so the restriction is less severe than it first seems.\n- **Asymptotic vs. finite $n$.** Theorems are asymptotic; finite-sample deviations are possible. Nonetheless, experiments show excellent agreement even at modest $n$, with accuracy driven more by $\\nu_n$ than by graph size.\n\n\n---\n\n[1] Choromanska, A., Henaff, M., Mathieu, M., Ben Arous, G. & LeCun, Y.. (2015). The Loss Surfaces of Multilayer Networks.\n\n[2] Wang, X. & Zhang, M.. (2022). How Powerful are Spectral Graph Neural Networks.\n\n[3] Mingguo H., Zhewei W., Zengfeng H. & Hongteng Xu (2021). BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation.\n\n[4] Wolfe, P. J., & Olhede, S. C. (2013). Non-parametric graphon estimation.\n\n[5] Orbanz, P., & Roy, D. M. (2015). Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(2), 437–461.\n\n[6] Gao, C., Lu, Y., & Zhou, H. H. (2015). Rate-optimal graphon estimation. Annals of Statistics, 43(2), 762–785."}, {"review_id": "pKZYidBs4R", "reviewer": "Reviewer_vVTK", "summary": "This paper establishes CLTs for the features of a particular class of GNNs when the input data follow a form of stochastic block model. The limits distributions in the CLTs are mixtures of Gaussians with parameters expressed in terms of the ingredients of the block model. Insights into the performance of linear classification and the over smoothing phenomenon are derived from the CLTs and the theory is illustrated with numerical experiments.", "questions": "1) The work in this paper has the potential to stimulate similar analysis of GNN's other than Poly-GNN's, can the authors very briefly comment on what the main opportunities and obstacles might be? If they need to save some space to accommodate this, I would recommend condensing section 1.1, I think it could easily be half the length and still do the job of summarising the existing contributions.\n\n2) Regarding the place of this work within the literature, I think more should be said about the current state of theory for GNN's and poly GNN's in particular. Are there any existing CLT's, or other theory related to behaviour of GNN's under block models etc? If, in any sense, the results in this paper are the first of their kind, I think that must be highlighted. More broadly to frame originality, what was the inspiration for this work? Is it based on any existing analysis, or something in a completely new direction? I think these questions should be answered in the paper, not just in the response to the review.\n\n3) A technical question, related to reqs (10), (11) and elsewhere: inside the expectation their is a sup over a (presumably) uncountable family of random variables (associated with each of the Lipschitz functions). Consider this uncountable sup, how do you know the sup is measurable, and hence well-defined as a random variable?\n\n4) Line 230 \"...significant practical implications...\" On first reading this, I was expecting that the theory would be use derive some guidance or new techniques for how GNNs should be use in practice. I'm not sure I got that, but rather some (detailed) insights into phenomena that might be observed in practice. The authors may consider re-wording slightly here to manage the readers' expectations.\n\n5) Line 238 \"...as these are the quantities typically used by the classifier” Please clarify - the degree normalised features depend on nu_n; even if one accepts the assumption that the data are generated by the block model, it seems too much of a stretch to assume that the true value of nu_n is known.\n\n6) Line 272 \"...is a well-documented empirical observation” Please add references to the literature.\n\nA couple of typos:\n\nAbstract \"Our results provides a...\"\n\nFigure 1 caption “Ten gradients steps…”", "limitations": "The authors have answered “No” to the question of whether limitations are discussed. This feels like a missed opportunity!! Surely there must be something you can say here?!\n\nThey have also answered “No” to the question about open access to data and code. Whilst I agree the numerical experiments are not a focal point of the paper, it seems an unnecessary restriction to not make it easy for the community to reproduce or further experiment with the numerical examples. They have also answered “No” to the question about compute resources. Again this feels unnecessary: just add it as a brief comment in the supplementary material. \n\nThe authors have answered “No” to the question about societal impacts. This is not inappropriate given the theoretical nature of the contribution.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "From a rigorous mathematical point of view, GNNs have remained a somewhat murky subject. In the ML literature, even the motivation for GNN’s is often not well explained beyond simple heuristics, and their has been an absence of careful statistical formulation of GNN’s operation, nevermind statistical theory of the sort set out in this paper. As such I believe the work set out in this paper could make an important step forward and stimulate more work in this area. \n\nThe mathematical clarity of the paper is very good. I have experience in statistical theory of networks and graphs, but am not an expert in GNNs; for me the presentation of theory made it easy to digest.\n\nThe paper focuses on one particular class of GNN’s: poly-GNN’s, which have a relatively simple linear structure. \nMy questions below include a request to clarify exactly where this paper sits in the literature on GNN’s, its originality,  and for comments to be added on the prospects of the theory being extended beyond GNN’s. Subject to that being clarified, I think it would be wrong to regard the focus on poly-GNN’s as a “weakness” of the paper, so much as a natural limitation in its scope. \n\nI think there are some opportunities for other small improvements — see questions below. \n\nIf the authors can further clarify the originality of this work and its position in the literature about the theory of GNNs I am willing to up my scores about significance and originality, and hence boost my overall score for the paper. Clarification of originality and place in the literature is of course a very important matter, so without this addressed I have currently rated as \"borderline reject\".", "was_revised": true, "final_justification": "I have upped my score to 4 to reflect the fact I find the authors’ response satisfactory.", "rebuttal": "> 1. The work in this paper has the potential to stimulate similar analysis of GNN's other than Poly-GNN's, can the authors very briefly comment on what the main opportunities and obstacles might be? If they need to save some space to accommodate this, I would recommend condensing section 1.1, I think it could easily be half the length and still do the job of summarising the existing contributions.\n\nThank you for the positive comment. We agree that our work can stimulate similar analyses of other GNNs.\n\n**Main Opportunities:**\n1.  **Feasibility and Guidance:** By demonstrating that a CLT exists for Poly-GNNs, we establish its feasibility for the broader GNN family. Once you show that the CLT exists for one family, there is a high chance that it exists for others. Our theoretical framework, particularly the characterization of the CLT's scale (normalization by $\\nu_n^{k-1/2}$) and the quantity to look at (empirical distribution of the GNN embeddings), provides a roadmap for researchers seeking to develop new CLTs for other architectures.\n2.  **Stochastic Analysis:** We show that studying GNNs under a stochastic network model (asymptotically as $n \\to \\infty$ in the sparse regime) is a fruitful approach. This allows us to precisely characterize the effect of graph noise and observe non-trivial phenomena: the original feature covariance vanishes and is replaced by a purely graph-induced covariance, which in turn collapses in the \"worst possible\" direction (the same as the signal). We hope this sparks more interest in the stochastic analysis of GNNs, moving beyond the common assumption of a known, noiseless graph.\n3.  **Optimization in the Limit:** Our use of Wasserstein-type bounds, which implies asymptotic convergence for all Lipschitz functions, shows that the entire cross-entropy optimization objective can be studied in the limit. This may inspire others to seek Wasserstein-type CLTs when studying the optimization aspects of GNNs.\n4.  **A Generalizable Technique:** The walk-analysis technique, while complex, reduces the problem to careful combinatorics and allows for sharp control of the moments. This technique could potentially be used to derive a CLT for GNNs of the form $\\sum_{k=1}^K A^k X W_k$, revealing interesting interactions between aggregations at different layers.\n\n**Main Obstacle:**\nThe primary obstacle is the walk analysis itself. It is best suited for polynomial aggregation, though an extension to gated networks might be possible (see our response to Reviewer ovye). However, the method of moments we employ is just one approach to deriving CLTs. We believe other, more general approaches may exist that, once discovered, could allow for the derivation of CLTs for many GNN families from a few foundational results.\n\n> 1. Regarding the place of this work within the literature, I think more should be said about the current state of theory for GNN's and poly GNN's in particular. Are there any existing CLT's, or other theory related to behaviour of GNN's under block models etc? If, in any sense, the results in this paper are the first of their kind, I think that must be highlighted. More broadly to frame originality, what was the inspiration for this work? Is it based on any existing analysis, or something in a completely new direction? I think these questions should be answered in the paper, not just in the response to the review.\n\nWe discuss the literature further in response to Reviewers SM6e and BzXf and will expand on this in the revision.\n\nTo briefly answer your questions: to our knowledge, there are no other CLTs for GNNs in the literature. While theoretical analyses of GNNs exist, most are non-stochastic, assuming a fixed, given (and often \"true\") graph. Treating the connections as stochastic (i.e., noisy) is more realistic and adds significant nuance. The few works that consider stochastic models (like SBMs) often provide non-rigorous analysis (e.g., physics-type arguments) or are limited in scope (e.g., to $k=1$ or bounds on misclassification error). They do not provide an exact characterization of the asymptotic distribution as we do here.\n\nYes, we believe our results are the first of their kind and will highlight this in the revision.\n\nThe inspiration for this paper comes from a previous work of ours, which we cannot cite due to anonymity. In that work, we sought to understand the effect of depth in GNNs (i.e., is there an optimal depth $k$?). We studied the signal-to-noise ratio (SNR) of the GNN output and demonstrated that the rate at which the SNR increases with $n$ is independent of depth (the signal grows like $\\nu_n^k$ while the noise grows like $\\nu_n^{k-1/2}$, so $k$ cancels in the ratio). The walk analysis we used there was sharp enough (providing tight upper and lower bounds) that we realized we could exactly characterize the limiting moments. This observation led to the current paper, though many new details needed to be worked out (e.g., controlling moment variances, characterizing asymptotic covariance, and concentrating the empirical distribution). We believe the two papers together chart a new direction and will add a discussion along these lines to the revision once the anonymity barrier is lifted.\n\n> 2. A technical question, related to reqs (10), (11) and elsewhere: inside the expectation their is a sup over a (presumably) uncountable family of random variables (associated with each of the Lipschitz functions). Consider this uncountable sup, how do you know the sup is measurable, and hence well-defined as a random variable?\n\nThank you for this interesting technical question. The supremum is indeed well-defined because it can be reduced to a supremum over a countable subset, ensuring measurability.\n\nThe argument is as follows: for any 1-Lipschitz function $f$, one can construct a sequence of functions $\\\\{\\phi_m\\\\}\\_{m\\ge 1}$ where each $\\phi_m$ matches $f$ on $[-m, m]$ and extends linearly with slope $\\pm 1$ outside this interval. The difference of the two measures on $f$ will be the same as $\\sup_{m \\ge 1}$ of the difference over $\\phi_m$.  Furthermore, for any given $m$, the space of 1-Lipschitz functions on the compact interval $[-m, m]$ (equipped with the sup-norm) is totally bounded and thus separable. It admits a countable dense subset, say $\\mathcal{F}\\_m$. Therefore, the original supremum over an uncountable set is equal to the supremum over the countable set $\\bigcup_{m \\ge 1} \\mathcal{F}_m$.\n\nSimilar approximation arguments are used in the proof of Proposition 8 in Appendix E.\n\nFor completeness, we note there are other general approaches to handle such measurability issues: (1) redefining the supremum, as in Talagrand's *The Generic Chaining* (Equation (0.2)), or (2) using outer expectation in place of $\\mathbb{E}$, as in the work of van der Vaart and Wellner.\n\n> 3. Line 230 \"...significant practical implications...\" On first reading this, I was expecting that the theory would be use derive some guidance or new techniques for how GNNs should be use in practice. I'm not sure I got that, but rather some (detailed) insights into phenomena that might be observed in practice. The authors may consider re-wording slightly here to manage the readers' expectations.\n\nWill do. Thank you for the suggestion.\n\n> 4. Line 238 \"...as these are the quantities typically used by the classifier” Please clarify - the degree normalised features depend on nu_n; even if one accepts the assumption that the data are generated by the block model, it seems too much of a stretch to assume that the true value of nu_n is known.\n\nThat is a fair point. But, the average degree of the observed graph provides is a very good empirical approximation of $\\nu_n$ , up to a constant. Since only the scaling matters for the normalization, using the observed average degree is a practical and effective approach.\n\n> 5. Line 272 \"...is a well-documented empirical observation” Please add references to the literature.\n\nThis will be done. We have also added a brief review of the oversmoothing literature in responses to Reviewers SM6e and BzXf.\n\nRegarding the limitations, we will add a discussion of them in the revision.  Key points:\n\n- **Scope of the theory.** Our results characterize multi-hop features optimized under Lipschitz losses. They exclude nonlinear propagation and other complex GNN variants; extending to those architectures is future work.\n- **Learnable components.** Trainable functions can act on the aggregated features (the “head”), but the propagation operator itself is fixed. We will clarify this constraint.\n- **Dependence on average degree $\\nu_n$.** The theory holds for $\\nu_n \\to \\infty$ up to to $\\nu_n = o(n)$; the unrealistic $\\nu_n = O(1)$ regime is excluded, and $\\nu_n = \\Omega(n)$ requires additional arguments. Empirically, asymptotic behavior appears once $\\nu_n \\gtrsim 16$ (Appendix G).\n- **Model class.** We assume an SBM. While this omits truly arbitrary graphs, SBMs with large $K$ are universal $L^{2}$-graphon approximators [4–6], so the restriction is less severe than it first seems.\n- **Asymptotic vs. finite $n$.** Theorems are asymptotic; finite-sample deviations are possible. Nonetheless, experiments show excellent agreement even at modest $n$, with accuracy driven more by $\\nu_n$ than by graph size.\n---\n\n[4] Wolfe, P. J., & Olhede, S. C. (2013). Non-parametric graphon estimation.\n\n[5] Orbanz, P., & Roy, D. M. (2015). Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(2), 437–461.\n\n[6] Gao, C., Lu, Y., & Zhou, H. H. (2015). Rate-optimal graphon estimation. Annals of Statistics, 43(2), 762–785.\n\nThanks for catching the typos. They will be fixed."}, {"review_id": "HRc1Mbelcw", "reviewer": "Reviewer_SM6e", "summary": "In this paper, the authors show two CLT-type convergence results for linear GNNs on CSBM random graphs when the number of nodes go to infinity, and the graph is sparse. The first result pertains to rescaled node features, which they show converge to a mixture of Gaussians with vanishing covariances. The second result concerns a centered and again-rescaled version of these features, which they show converge to a sum of centered Gaussians with specific covariances. They show two applications, one concerning the training of classifiers on these features for which they give a uniform deviation result, and one concerning some remarks on oversmoothing, when the number of layers grows. The proofs rely mostly on moment computations.", "questions": "See above for several questions.", "limitations": "Limitations are appropriate.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strength\n- the paper is well-written and clear, despite heavily technical content\n- one notable strength of the results is that, as CLTs, the limit does not depend on the distribution of the input node features (only on its mean), which is quite original in this literature. Is this due to the sparsity? (looking at the proof it allows to discard some terms)\n- beyond the convergence results themselves, the applications on training and oversmoothing are interesting\n\nWeaknesses\n- the references are quite scarce, given this large literature, especially on the oversmoothing aspect. Several papers performed similar theoretical analyses before (with shrinking Gaussian communities, collapsing covariances, and so on), and while that of the authors is new (as far as I know), it must commented with regard to these previous results. It would help better outline the novelty and strength of the results: while the current formulation gives an impression of novel \"idea\" that is relatively incorrect, it is rather a new take on a classical idea. See eg [1,2,3] (non-exhaustive list).\n\nIn the same vein, linear GNNs are very often called \"Simplified Graph Convolution\" (SGC), as per the seminal paper [4]. To my knowledge, polynomial GNNs are more often used for polynomial filters, where every power of the graph matrix (eg Chebnet).\n\n[1] Baranwal et al. \"Effects of Graph Convolutions in Multi-layer Networks\"\n[2] Keriven \"Not too little, not too much: a theoretical analysis of graph (over)smoothing\"\n[3] Wu et al \"A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks\"\n[4] Wu et al. \"Simplifying Graph Convolutional Networks\"\n\n- could the result on training linear GNNs be pushed further? It feels a bit \"unfinished\" at the moment. Surely the limit problem is a known classification problem, with guarantees?\n- while Theorem 2 indeed feels like a CLT, this is not quite the case of Theorem 1, which uses vanishing covariances. Unless I am missing something, a Gaussian with vanishing covariance converges to a Dirac in Wasserstein norm, does that means that the distribution really converges to a sum of Diracs? What would be the implication of this for the other results? (training, oversmoothing). This may be discussed\n- In theorem 2 the centering of the features uses their unknown mean. Could it be replaced by some kind of empirical average? Otherwise it must be clearly written that this is a theoretical result that uses oracle quantities.\n- the authors mention the importance of sparsity, but that \"some\" results may carry to the dense setting. Is it possible to provide a bit more details what would not carry, and why?\n- minor comment: it is just a personal appreciation, but I feel like some of the language used by the authors oversells a bit the results; eg I'm not sure a result pertaining to linear GNNs on sparse CSBM can be said to have \"profound implications for the training of GNNs\" in general. Paradoxically, this is a bit detrimental to the just appreciation of the results, which I find to be valuable and carry interesting intuitions by themselves.", "was_revised": true, "final_justification": "The detailed answers by the authors strengthened my positive view of their results. I have increased my score, understanding that the interesting discussion in their answers will be added to some extent to the final version of the paper.", "rebuttal": "> The references are quite scarce, given this large literature, especially on the oversmoothing aspect. Several papers performed similar theoretical analyses before (with shrinking Gaussian communities, collapsing covariances, and so on), and while that of the authors is new (as far as I know), it must commented with regard to these previous results.\n\nIn our work, we establish a limiting distributional result for multi-hop aggregated node features on community-structured graphs. Our result, along with its closed-form characterization, is novel. Moreover, its mode of convergence is unique, the convergence in expected Wasserstein distance enables high-probability guarantees for Lipschitz optimization problems involving multi-hop aggregated node features. We emphasize that this is much stronger than the usual \"convergence in distribution\" result common with CLTs.\n\nThe related literature for multi-hop node features can be broken into three categories: distributional characterizations, oversmoothing phenomenon, and improvement results for select learning tasks (commonly classification or regression). \n    \nFor **distributional characterizations**, [1] is closest to the work of the authors. In [1], the results hinge on the statement that $\\phi^k_i$ is exactly component-wise Gaussian. Note, that this cannot be the case as even $\\phi_i^{(1)} = \\sum_{j}A_{ij}x_j$ with Bernoulli $A_{ij}$ and normal $x_j$ is, by definition, a (scaled) mixture of Gaussians. \n    \nIn the vein of **oversmoothing**, works [2], [3], and [4] show how properly normalized aggregations can still oversmooth in the presence of non-linearities. Oversmoothing can be seen as a consequence of the power iteration $A^k$ collapsing the range onto the Perron eigenvectors. The works [2] and [3] show that non-linearities like ReLU do not help oversmoothing since the ReLU operator is also contractive under the operator norm (see [5]). In [4] the authors extend these results to include to also include attention-based non-linearities. Outside of [2], which considers the effects of oversmoothing on a $L=1$ community graph, the results of all other works assume a deterministic graph.\n\nWith respect to **improving task performance**, works [6] and [7] show how multi-hop features can improve downstream learning tasks. Between the two works the generative formulation differs, [6] assumes $(p,q)$-SBM with mixed mean feature representations while [7] assumes a low rank, latent variable model which yields dense observed graphs. The losses considered by [6] and [7] are Lipschitz, highlighting the importance of understanding behavior of multi-hop features under the 1-Wasserstein metric. \n\n> In the same vein, linear GNNs are very often called \"Simplified Graph Convolution\" (SGC), as per the seminal paper [4]. To my knowledge, polynomial GNNs are more often used for polynomial filters, where every power of the graph matrix (eg Chebnet).\n\nYes. Our original thought was that, since we provide the limit for every $k$, it should be straightforward to derive similar results for polynomial GNNs of the form $\\sum_{k=1}^{K} A^{k} X W_{k}$, which includes ChebNet and the like. Upon further reflection, we realized that there are still complications to resolve—specifically, the statistical dependence between $A^{k} X$ and $A^{k'} X$ for $k \\neq k'$. Nevertheless, we believe our approach can be extended (with some tedious bookkeeping) to derive CLTs for these models.\n\nThat said, we can rename the present paper “monomial GNNs” if you feel strongly about it. “SGC” is not very descriptive, and we believe “polynomial” or “monomial” is more appropriate.\n\n> could the result on training linear GNNs be pushed further? It feels a bit \"unfinished\" at the moment. Surely the limit problem is a known classification problem, with guarantees?\n\nThe discussion of training linear GNNs with cross-entropy is meant only as an illustrative example. Indeed, we comment (Lines 266-268) that it is generally **sub-optimal**: unless the asymptotic covariances are equal, the Bayes decision boundaries are quadratic, so any linear classifier will incur a (typically small) excess risk. Highlighting this gap is one insight of our analysis.\n\nNothing in our framework restricts us to linear decision rules or to the CE loss. One could instead fit $f(\\bar\\phi_i^{(k)})$ using richer function classes—quadratics, higher-order polynomials, RKHS functions, etc.—and our theory still applies so long as the composed \"loss $\\circ f$\"  is Lipschitz. Each choice maps to a corresponding (simpler) population-level optimisation problem in the limit.\n  \nFinally, when the loss is convex, classical results establish conditions under which minimising that convex surrogate matches the Bayes-optimal zero-one risk. See, for example,\n\nBartlett, P. L., Jordan, M. I., & McAuliffe, J. D. (2006). Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473), 138–156.\n\nWe will cite this work in the revision; a deeper treatment lies beyond the scope of the present paper.\n\n> Unless I am missing something, a Gaussian with vanishing covariance converges to a Dirac in Wasserstein norm, does that means that the distribution really converges to a sum of Diracs?\n\nThank you for the observation. You are correct: as the covariance matrix vanishes, a Gaussian collapses to a Dirac mass. However, for any finite (even moderately large) n, the covariance is still positive (as it is scaled by $\\nu_n$ which could grow very slowly), so the Gaussian approximation retains valuable second-order information that the Dirac limit loses. We therefore interpret Theorem 1 as a finite-n approximation; the Dirac point mass is merely the asymptotic endpoint, while the Gaussian mixture captures the covariances that matter in practice.\n\nFigure 4 in Appendix G illustrates this behavior: with an average degree as low as $\\nu_n = 16$, the empirical distributions already match the Gaussian prediction, and the covariances remain far from negligible.\n\n> In theorem 2 the centering of the features uses their unknown mean. Could it be replaced by some kind of empirical average?\n\nThe CLT exists irrespective of whether we can estimate $\\mathbb{E}[\\phi]$ in a finite sample setting. Estimating $\\mathbb{E}[\\phi]$ is closely related to correct identification of the labels $z$, which is the goal in the first place.\n\n>  Otherwise it must be clearly written that this is a theoretical result that uses oracle quantities.\n\nWe would not describe our result as relying on “oracle” quantities. It is simply a central-limit-type statement.  Consider the classical CLT: We have i.i.d. variables $X_1,\\dots,X_n$ with unknown mean $\\mu$ and the CLT says \n$\\sqrt{n} (\\bar X_n - \\mu) \\to N(0,1).$\nAlthough $\\mu$ is unknown, no one regards the theorem as “oracle-based”. The CLT in fact is used to give uncertainty bounds on the unknown $\\mu$ based on the empirical mean $\\bar X_n$. Now, replace $\\bar X_n$ with $\\bar \\phi_i^{(k)}$ and $\\mu$ with $\\mathbb E \\bar \\phi_i^{(k)}$ and you get a similar interpretation in our case (with a bit of nuance since we look at the empirical distribution of these after scaling, a step which is not present in classical CLT.)\n\n> The authors mention the importance of sparsity, but that \"some\" results may carry to the dense setting. Is it possible to provide a bit more details what would not carry, and why?\n\nThe limiting CLT still holds for the dense regime although the limiting characterization of the GNN may differ. Section A.1 gives a detailed breakdown of graph and feature noise ($\\Delta$ and $\\Lambda$ resp.) and how these terms contribute to the overall noise characteristic of the centered aggregated features $\\phi^{(k)} - \\mathbb{E}[\\phi^{(k)}]$. The scale of both the graph noise and the feature noise is given in Section A.3. Here, we see that the feature noise scale depends on a $\\beta_{k,n}$ parameter. As shown in Lemma 5 of the supplement, this parameter goes to zero whenever $\\nu_n/n\\to 0$ and $\\nu_n \\to\\infty$. \n\nIn the dense regime, the feature noise $\\Lambda$ makes non-negligible contributions to the empirical distribution's sliced moments $\\langle \\xi_i^{(k)},\\theta\\rangle^r$. As a result, one would need to account for $\\Lambda_{i,\\theta}^r$ in approximation Lemma 5. This, in turn, would have downstream impacts on the closed form of the limiting covariance (Proposition 4 of the supplement). \n\nThat being said, while the addition of non-negligible feature noise may complicate the final characterizations of the limiting covariance, there does not seem to be any hard technical barriers to showing an analogous CLT result for the dense graph case.\n\n> I feel like some of the language used by the authors oversells a bit the results\n\nThis language will be amended appropriately in the final revision of our paper.\n\n\n[1]  Wu, X., Chen, Z., Wang, W., & Jadbabaie, A. (2022). A non-asymptotic analysis of oversmoothing in graph neural networks.\n\n[2] Oono, K., & Suzuki, T. (2020). Graph neural networks exponentially lose expressive power for node classification.\n\n[3] Cai, C., & Wang, Y. (2020). A note on over‑smoothing for graph neural networks.\n\n[4] Wu, X., Ajorlou, A., Wu, Z., & Jadbabaie, A. (2023). Demystifying oversmoothing in attention‑based graph neural networks.\n\n[5] Dittmer, S., King, E. J., & Maass, P. (2018). Singular values for ReLU layers.\n\n[6] Baranwal, A., Fountoulakis, K., & Jagannath, A. (2022). Effects of graph convolutions in multi‑layer networks.\n\n[7] Keriven, N. (2022). Not too little, not too much: a theoretical analysis of graph (over)smoothing.\n\n[8] Baranwal, A., Fountoulakis, K., & Jagannath, A.. (2021). Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization."}, {"review_id": "ZjBZ3HSLin", "reviewer": "Reviewer_BzXf", "summary": "The paper studies the asymptotic properties of the product $A^k X$ where $A$ is an adjacency matrix and $X$ is a matrix of node features under a sparse community graph model, and in doing so are able to characterize the asymptotic distribution of the embedding vectors produced through this matrix product. In particular, they are able to give guarantees for a Wasserstein-bound CLT for these features (both after being re-scaled by a suitable power of the average degree of the network, and after the typical centering/scaling one expects for CLT results). This is then used to give some discussion and insights into the behavior of using these features for classification, and the well known phenomenon of over-smoothing in GNNs.", "questions": "1. I am surprised that the results do not extend to the dense regime - for instance, by rewriting Assumption 3 as $( \\nu_n / n)^{1/2} \\cdot \\sqrt{n} ( \\pi_l - | \\mathcal{C}_l | / n ) = o(1)$, it appears that if $\\nu_n = n$, then a standard assumption of assuming that the community assignments are drawn from a Multinomial distribution would break this assumption. Can you please give some intuition as to what breaks down in this regime?\n\n2. I am a bit confused by the presentation of Assumption 1, where the average degree parameter $\\nu_n$ is said to need to grow to infinity as the number of nodes does (which is a standard assumption). There is then also the assumption that $\\nu_n B_{ll'} / n \\leq C/n$ for some constant $C$, which when rearranged gives that $\\nu_n B_{ll'} \\leq C$, which contradicts $\\nu_n \\to \\infty$. I'm assuming this is a typo and that it just suffices to assume that $B_{ll'}$ is bounded, which under the assumptions that $L$ is fixed with $n$ is going to be the case anyways. \n\n3. Can you please provide some intuition for why the covariance matrices in Theorem 1 and Theorem 2 have no dependence on the covariance structure of the node features $X_i$? Just thinking out loud about the variance of the node features, we know that by the law of total variance, it will break down into two terms - one corresponding to how the covariance of the node features is smoothed by the random walks on the graph of length $k$, and the other corresponding to the uncertainty in the graph mixed by the mean signal of the $X_i$. This second term is what appears in the variance bound - why does this end up being the dominating term? \n\n4. Can you please give a summary of where your results fit into the existing literature on theoretical guarantees for GNNs? For example, there is a substantial literature already which covers the oversmoothing phenomenon in GNNs - to what extent is the discussion in this paper novel? For example, to cite some well known papers which discuss this phenomenon: \n\n- In \"Graph Neural Networks Exponentially Lose Expressive Power for Node Classification\" by Oono and Suzuki, they are able to give a characterization of this phenomenon for Erdos-Renyi graphs within GCNs with ReLU activations, and are able to show subspace collapse in the learned embeddings which is achieved exponentially in the number of layers.\n- In \"A Note on Over-Smoothing for Graph Neural Networks\" by Cai and Wang, this is extended to handle other non-linear activation functions.\n- \"Not too little, not too much: a theoretical analysis of graph (over)smoothing\" by Keriven studies the same type of model as in the current paper, albeit with the Laplacian rather than the adjacency matrix (which is the more frequently used model). \n- \"Demystifying Oversmoothing in Attention-Based Graph Neural Networks\" by Wu et al studies GNNs with attention mechanisms, and also handles the non-linear regime.\n\nCan you explain the novelty in your contribution compared to these papers? To be clear, this last question is the one of main importance to me in terms of understanding the overall contribution of the work. An understanding of whether the results in this paper develop substantial **new** understanding for the behavior of GNNs will be the main factor in whether my overall evaluation would increase.", "limitations": "The authors have adequately addressed the societal impact of their work. As it comes to the limitations of the theoretical analysis, there is not really much of a discussion at all except a sentence at the very end of the conclusion referring to non-linear GNNs and different graph models. I would appreciate a more involved discussion about a) why their results cannot be extended easily to non-linear GNNs, GNNs with learnable weight matrices within layers, GNNs with Laplacian matrices, and so on; and b) a discussion about what aspects of the theory break down when moved to the either the dense regime where $\\nu_n = \\Omega(n)$ or the regime where $\\nu_n = O(1)$. This would improve the overall contribution of the paper.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths of the paper:\nThe results in the paper are quite technical in their nature (for instance, requiring some detailed analysis into random walks of graphs) and are generally presented well and are of high quality. The mathematical details in the appendix are correct, and are covered at an appropriate level of detail. From a probabilistic perspective, the results of the paper are interesting. To my knowledge, the mathematical results in of themselves are new.\n\nWeaknesses of the paper:\nIt is generally unclear how this paper fits into the larger literature on GNNs and the phenomenon which the paper seeks to explain, and the extent to which it is novel is unclear. The GNN model being studied is also relatively simple - even ignoring the removal of the non-linear activation function between layers, the features being studied are simply node features propagated by a power of the adjacency matrix. With the exception of Section 4.1 (where there is only a discussion of a linear model applied to the features), there is no reference to trainable features for this model. Moreover, there are already a large number of papers which study the GNN oversmoothing phenomenon, some of which already give explanations under more realistic assumptions than the current paper. The overall novel contribution in terms of understanding these models from a ML perspective appears to be minimal.", "was_revised": true, "final_justification": "After the rebuttals from the authors clarifying the significance of their results, the way in which their results are distinguished from the rest of the literature (this being my main barrier to recommending the acceptance of the paper), and to also highlight the ways in which their work may be extended (using similar approaches) to models of closer interest to practitioners, I am happy to recommend the acceptance of the paper.", "rebuttal": "> 1. I am surprised that the results do not extend to the dense regime - for instance, by rewriting Assumption 3 as , it appears that if , then a standard assumption of assuming that the community assignments are drawn from a Multinomial distribution would break this assumption. Can you please give some intuition as to what breaks down in this regime?\n\nAssumption 3 can be relaxed, as we have already done in the supplementary material (we will clarify this in the revision). The assumption can be weakened to $|C_\\ell| / n - \\pi_\\ell = o(1)$, which holds even when $\\nu_n=n$ for balanced community assignments.\n\nHowever, other parts of our argument rely on the sparse regime, $\\nu_n = o(n)$. Specifically, in this regime, the graph noise is the dominant source of variance, and the initial feature noise can be ignored in the limit. This is not the case in the dense regime ($\\nu_n = \\Omega(n)$), where the feature noise is no longer negligible. In the dense case, the limiting covariance matrix would need to be modified to account for both sources of noise. We elaborate on this in the rebuttal for reviewer SM6e.\n\n> 2. I am a bit confused by the presentation of Assumption 1, where the average degree parameter is said to need to grow to infinity as the number of nodes does (which is a standard assumption). There is then also the assumption that for some constant , which when rearranged gives that , which contradicts . I'm assuming this is a typo and that it just suffices to assume that is bounded, which under the assumptions that is fixed with is going to be the case anyways.\n\nThank you for pointing this out, and our apologies for the confusion. This is indeed a typo. The condition should be $B_{\\ell\\ell'} \\le C$, meaning the entries of the affinity matrix $B$ are bounded. We will correct this in the revision.\n\n> 3. Can you please provide some intuition for why the covariance matrices in Theorem 1 and Theorem 2 have no dependence on the covariance structure of the node features ? Just thinking out loud about the variance of the node features, we know that by the law of total variance, it will break down into two terms - one corresponding to how the covariance of the node features is smoothed by the random walks on the graph of length , and the other corresponding to the uncertainty in the graph mixed by the mean signal of the . This second term is what appears in the variance bound - why does this end up being the dominating term?\n\nThis is an excellent question, and your intuition is correct. The total variance indeed breaks down into two terms, which correspond to the graph noise ($\\Delta^\\circ$ in our proof) and the feature noise ($\\Lambda^\\circ$). See Equation (22) in the Supplement.\n\nOur analysis shows that graph noise dominates in the sparse regime we consider (i.e., as $\\nu_n \\to \\infty$ with $\\nu_n = o(n)$). In the dense regime ($\\nu_n = \\Omega(n)$), however, the feature noise is no longer negligible and contributes to the limiting variance.\n\nWhy this happens? We don't have a simple answer;  it is a direct consequence of our careful moment analysis. By characterizing the dominant walk structures, we precisely determine the asymptotic order of these two noise terms. Please see Propositions 2 and 3 and Lemma 5 of the supplementary material. We also touch upon this in rebuttal to reviewer SM6e. \n\n> 1. Can you please give a summary of where your results fit into the existing literature on theoretical guarantees for GNNs?\n\nThere is a **straighforward explanation** for oversmoothing via **power iteration**: If you take a fixed, known positive matrix $A$ and iterate it to get $A^k$. Then, as $k$ gets large ($k \\to \\infty$), the operator collapses towards a rank-one operator in the direction of the Perron eigenvector. In other words, power iteration uncovers the leading eigenvector of matrix. This is not very surprising. The work you cite (including the nonlinear extensions) provide this type of explanation.\n\nOur work differs fundamentally by considering a **stochastic setting**. Here, the aggregation operator $A$ is a noisy, random matrix, not a fixed one. We analyze the limit as the graph size $n \\to \\infty$ for a *fixed* depth $k$. In this asymptotic regime, a Central Limit Theorem emerges.\n\nWhile the power iteration analogy still applies to the first-order term (the mean signal), our CLT also characterizes the second-order effects. Crucially, we show that the covariance *also* collapses (via a term related to power iteration) in the same direction as the signal. This means that for sparse graphs, the potentially high-dimensional nature of the features is lost in the limit—a much stronger statement than standard oversmoothing results. Characterizing this behavior as $n \\to \\infty$ under a stochastic model is a key distinction from prior work. Please see the rebuttal to reviewer SM6e for more context on our work relative to the current literature.\n\n**Limitation**\n\nWe will add a thorough discussion of limitations to the revised manuscript. In short:\n*   **Dense Regime:** There is no fundamental obstacle to applying our techniques to the dense regime ($\\nu_n = \\Omega(n)$), though the analysis would need to be extended to account for both graph and feature noise sources, as mentioned earlier.\n*   **Nonlinearities:** A significant challenge is extending our walk-based analysis to GNNs with nonlinear activation functions. In response to Reviewer ovye, we outline some potential ideas. However, developing entirely new methods for deriving CLTs for GNNs might be a more fruitful long-term direction. We see our work as a first step, establishing a foundation for more general and easily applicable techniques.\n*   **Attention/Trainable Weights:** Extending the analysis to models like GAT with trainable aggregation weights is another direction. While potentially feasible, it would require a substantial and non-trivial extension of the walk analysis."}]

Author rebuttal:

Meta-review: This paper presents a novel and technically rigorous Central Limit Theorem for the embeddings of polynomial GNNs on sparse community-based graphs. The work provides a good theoretical contribution by introducing a "covariance collapse" mechanism, which shows that feature variance diminishes in the same direction as the mean signal, offering a more precise explanation for the oversmoothing phenomenon than prior work. The authors' detailed rebuttal effectively clarified the paper's originality and positioning within the literature, addressing initial reviewer concerns and leading to a clear consensus for acceptance.
Decision: Accept (poster)