AI summaryⓘ
The authors study a new way to understand how certain graph neural networks (GNNs) spread information across a network while avoiding a problem called oversmoothing, where node features become too similar. They focus on a specific mathematical operator that removes a part causing this oversmoothing and analyze how well it keeps important class signals after many steps of information spreading. Their main finding is a proof that, under certain conditions, their method can accurately identify groups in a network after a logarithmic number of steps, especially in dense graphs. They also show it helps group nodes around their correct classes for multiple categories and validate these results with tests on simulated and real data.
Graph Neural NetworksOversmoothingNormalized adjacency matrixContextual Stochastic Block ModelSpectral theoryExact recoveryPartial recoverySignal-to-noise ratioNode classificationPropagation steps
Authors
Qihan Chen, Wei Li, Meng Qin, Jianfeng Hou
Abstract
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.