Lune

NeurIPS2025Top-tier venue

A CLT for Polynomial GNNs on Community-Based Graphs

Luciano Vinas, Arash A. Amini

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 ν n → ∞ , we show that the empirical distribution of the centered features, when scaled by ν k − 1 / 2 n 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 ν kn approach that of mixture of multivariate normal distributions, with stable means and covariance matrices vanishing as ν − 1 n . We explicitly identify the asymptotic means and covariances, showing that the mixture collapses towards a 1-D version as k is increased. Our results provide 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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • How Powerful are Spectral Graph Neural Networks cites Adaptive Universal Generalized PageRank Graph Neural Network
  • How Powerful are Spectral Graph Neural Networks cites BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation
  • Not too little, not too much: a theoretical analysis of graph (over)smoothing cites Graph Neural Networks Exponentially Lose Expressive Power for Node Classification
  • Adaptive Universal Generalized PageRank Graph Neural Network cites Graph Neural Networks Exponentially Lose Expressive Power for Node Classification
  • BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation cites Adaptive Universal Generalized PageRank Graph Neural Network
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on9

  1. Graph Neural Networks Exponentially Lose Expressive Power for Node ClassificationKenta Oono, Taiji SuzukiICLR 2020 · 864 citations
  2. BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein ApproximationMingguo He, Zhewei Wei, Zengfeng Huang, Hongteng XuNeurIPS 2021 · 378 citations
  3. How Powerful are Spectral Graph Neural NetworksXiyuan Wang, Muhan ZhangICML 2022 · 309 citations
  4. Not too little, not too much: a theoretical analysis of graph (over)smoothingNicolas KerivenNeurIPS 2022 · 190 citations
  5. Adaptive Universal Generalized PageRank Graph Neural NetworkEli Chien, Jianhao Peng, Pan Li, Olgica MilenkovicICLR 2021 · 93 citations

Related papers

  1. Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?Nicolas KerivenICML 2026 · 4 citations
  2. Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNsMichael Scholkemper, Xinyi Wu, Ali Jadbabaie, Michael T. SchaubICLR 2025
  3. Towards Deeper Graph Neural Networks with Differentiable Group NormalizationKaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha et al.NeurIPS 2020 · 248 citations
  4. Graph Neural Networks Do Not Always OversmoothBastian Epping, Alexandre René, Moritz Helias, Michael T. SchaubNeurIPS 2024 · 22 citations
  5. Convergence and Stability of Graph Convolutional Networks on Large Random GraphsNicolas Keriven, Alberto Bietti, Samuel VaiterNeurIPS 2020 · 111 citations
Dusk over the sea between two cliffs drawn in fine vertical lines