Search papers, labs, and topics across Lattice.
This paper develops a spectral theory for normalized corrected GNN propagation, focusing on the symmetric normalized adjacency matrix with its degree-stationary component removed to address oversmoothing in GCN-style models. The authors prove a high-probability exact-recovery theorem for the binary Contextual Stochastic Block Model, demonstrating that class-discriminative signals can be preserved after \(k=O(\log n)\) propagation steps under specific conditions. Additionally, they provide a multi-class partial recovery theorem, indicating that most nodes contract toward their respective class centers, supported by synthetic and real-world node-classification experiments.
Class-discriminative signals can be preserved in GNNs even after extensive propagation, challenging the oversmoothing narrative.
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.
