A Spectral Theory of Normalized Corrected GNN Propagation

This paper develops a spectral theory for normalized corrected Graph Neural Network (GNN) propagation, focusing on the symmetric normalized adjacency matrix with its degree-stationary component removed to isolate the direction tied to oversmoothing.

• The study addresses whether this corrected operator preserves class-discriminative signal after many layers.
• A high-probability exact-recovery theorem is established for the binary Contextual Stochastic Block Model after k=O(log n) steps in the dense polylogarithmic regime (p ≥ C log^B n / n, B > 4).
• A multi-class partial recovery theorem demonstrates contraction toward class centers for most nodes.
• Synthetic and real node-classification experiments validate the theory's predicted dependence on depth, graph signal, and feature noise.