A Spectral Theory of Normalized Corrected GNN Propagation

arXiv:2606.23572v1 Announce Type: new Abstract: We develop a spectral theory for normalized corrected GNN propagation. The object of study is the symmetric normalized adjacency with its degree-stationary component removed, matching the normalization used by standard GCN-style models while isolating the stationary direction most directly tied to oversmoothing. The central theoretical question is whether this corrected normalized operator preserves class-discriminative signal after many propagation layers. Our main result is a high-probability exact-recovery theorem for the binary Contextual Stochastic Block Model after (k=O(log n)) propagation steps in the dense polylogarithmic regime (pge Clog^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.

Source: arXiv cs.LG | 2026-06-23