A Spectral Theory of Normalized Corrected GNN Propagation

• URL: http://arxiv.org/abs/2606.23572v1
• Date: Mon, 22 Jun 2026 16:38:50 GMT
• Title: A Spectral Theory of Normalized Corrected GNN Propagation
• Abstract summary: We develop a spectral theory for emphnormalized corrected GNN propagation.<n>The central theoretical question is whether this corrected normalized operator preserves class-discnative signal after many propagation layers.<n>We also establish a multi-class partial recovery theorem showing contraction toward class centers for most nodes.
• Score: 2.9801823421431854
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop a spectral theory for \emph{normalized corrected GNN propagation}. The object of study is the symmetric normalized adjacency with its degree-stationary component removed, matching the normalization used by standard GCN-style models while isolating the stationary direction most directly tied to oversmoothing. The central theoretical question is whether this corrected normalized operator preserves class-discriminative signal after many propagation layers. Our main result is a high-probability exact-recovery theorem for the binary Contextual Stochastic Block Model after \(k=O(\log n)\) propagation steps in the dense polylogarithmic regime \(p\ge C\log^B n/n\), for any fixed \(B>4\), under explicit graph-signal and feature-SNR conditions. We also establish a multi-class partial recovery theorem showing contraction toward class centers for most nodes. Synthetic and real node-classification experiments are included as empirical checks of the theory's predicted dependence on depth, graph signal, and feature noise.

Related papers

• Spectral Embeddings of Degree-$α$ Laplacians in Random Dot Product Graphs [3.133932152358817]
  We show how degree normalization affects both population geometry and the local uncertainty of embedded nodes.<n>The favored normalization depends on network density, community imbalance, and block-probability structure.<n>These results provide a unified distributional understanding of when and why alternative normalizations may improve spectral clustering.
  arXiv  Detail & Related papers  (2026-08-11T12:16:29Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Beyond ReLU: Bifurcation, Oversmoothing, and Topological Priors [28.452964044443906]
  Graph Neural Networks (GNNs) learn node representations through iterative network-based message-passing.<n>Deep GNNs suffer from oversmoothing, where node features converge to a homogeneous, non-informative state.<n>We re-frame this problem of representational collapse from a emphbifurcation theory perspective, characterizing oversmoothing as convergence to a stable homogeneous fixed point.
  arXiv  Detail & Related papers  (2026-02-17T15:03:28Z)
• Rethinking Diffusion Models with Symmetries through Canonicalization with Applications to Molecular Graph Generation [56.361076943802594]
  CanonFlow achieves state-of-the-art performance on the challenging GEOM-DRUG dataset, and the advantage remains large in few-step generation.
  arXiv  Detail & Related papers  (2026-02-16T18:58:55Z)
• Which Graph Shift Operator? A Spectral Answer to an Empirical Question [2.0917449835910404]
  We introduce a novel alignment gain metric that quantifies the geometric distortion between the input signal and label subspaces.<n>Our theoretical analysis connects this alignment directly to generalization bounds via a spectral proxy for the Lipschitz constant.<n>This yields a principled, efficient criterion to rank computation and select the optimal GSO for any prediction task prior to training.
  arXiv  Detail & Related papers  (2026-02-06T09:59:54Z)
• Latent Object Permanence: Topological Phase Transitions, Free-Energy Principles, and Renormalization Group Flows in Deep Transformer Manifolds [0.5729426778193398]
  We study the emergence of multi-step reasoning in deep Transformer language models through a geometric and statistical-physics lens.<n>We formalize the forward pass as a discrete coarse-graining map and relate the appearance of stable "concept basins" to fixed points of this renormalization-like dynamics.<n>The resulting low-entropy regime is characterized by a spectral tail collapse and by the formation of transient, reusable object-like structures in representation space.
  arXiv  Detail & Related papers  (2026-01-16T23:11:02Z)
• Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNs [30.003409099607204]
  We provide a formal and precise characterization of (linearized) graph neural networks (GNNs) with residual connections and normalization layers.<n>We show that the centering step of a normalization layer alters the graph signal in message-passing in such a way that relevant information can become harder to extract.<n>We introduce a novel, principled normalization layer called GraphNormv2 in which the centering step is learned such that it does not distort the original graph signal in an undesirable way.
  arXiv  Detail & Related papers  (2024-06-05T06:53:16Z)
• Towards Training Without Depth Limits: Batch Normalization Without Gradient Explosion [83.90492831583997]
  We show that a batch-normalized network can keep the optimal signal propagation properties, but avoid exploding gradients in depth. We use a Multi-Layer Perceptron (MLP) with linear activations and batch-normalization that provably has bounded depth. We also design an activation shaping scheme that empirically achieves the same properties for certain non-linear activations.
  arXiv  Detail & Related papers  (2023-10-03T12:35:02Z)
• ResNorm: Tackling Long-tailed Degree Distribution Issue in Graph Neural Networks via Normalization [80.90206641975375]
  This paper focuses on improving the performance of GNNs via normalization. By studying the long-tailed distribution of node degrees in the graph, we propose a novel normalization method for GNNs. The $scale$ operation of ResNorm reshapes the node-wise standard deviation (NStd) distribution so as to improve the accuracy of tail nodes.
  arXiv  Detail & Related papers  (2022-06-16T13:49:09Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• When Does Preconditioning Help or Hurt Generalization? [74.25170084614098]
  We show how the textitimplicit bias of first and second order methods affects the comparison of generalization properties. We discuss several approaches to manage the bias-variance tradeoff, and the potential benefit of interpolating between GD and NGD.
  arXiv  Detail & Related papers  (2020-06-18T17:57:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.