A Spectral Theory of Normalized Corrected GNN Propagation

Standard Graph Convolutional Networks (GCNs) suffer from oversmoothing, where repeated propagation causes node representations to converge to a stationary state, losing class-discriminative information. This paper investigates whether modifying the normalized propagation operator—specifically by removing its degree-stationary rank-one component—can provably preserve class signals over many layers.

The authors introduce a corrected normalized propagation operator, denoted as A-hat, which subtracts the degree-stationary component from the standard symmetric normalized adjacency matrix (D^-1/2 A D^-1/2). They analyze this operator within the Contextual Stochastic Block Model (CSBM), a framework that combines graph structure with Gaussian node features. The study employs atom expansions and decorated-walk counting to derive high-probability bounds on the residual powers of this operator, allowing them to track how class-discriminative signals evolve over k = O(log n) propagation steps.

The paper establishes an exact-recovery theorem for binary CSBMs, showing that the corrected operator preserves linear separability of node features at logarithmic depth, provided the graph signal and feature signal-to-noise ratio (SNR) meet specific thresholds. Additionally, the authors provide a multi-class partial recovery theorem, demonstrating that most node representations contract toward their respective class centers. Empirical experiments on synthetic CSBM data and real-world node-classification benchmarks confirm that this spectral correction significantly mitigates depth-dependent accuracy degradation compared to standard GCN propagation.

This work provides a rigorous theoretical foundation for spectral correction in GNNs. By isolating the specific mechanism of oversmoothing—the amplification of the degree-stationary component—the authors offer a principled way to design deeper GNNs that maintain performance without relying solely on heuristic architectural tweaks like residual connections or edge dropping.