A Spectral Theory of Normalized Corrected GNN Propagation
Provides theoretical guarantees for GNN propagation depth and oversmoothing, addressing a key bottleneck in graph neural network design.
The paper develops a spectral theory for normalized corrected GNN propagation, proving exact recovery for the binary Contextual Stochastic Block Model after O(log n) propagation steps under dense regimes, and establishing multi-class partial recovery. Experiments validate the theoretical predictions.
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.