提出归一化修正GNN传播的谱理论，解释其如何避免过平滑并保持分类信号。
A Spectral Theory of Normalized Corrected GNN Propagation
- 基于移除度平稳分量的对称归一化邻接矩阵，建模GCN类模型传播机制。
- 在稠密多对数图中，$k=O(\log n)$ 层传播后可高概率精确恢复二分类结构。
- 理论预测深度、图信号强度与特征噪声的影响，实验证实其有效性。
我们构建了 extit{归一化修正GNN传播}的谱理论。研究对象为移除度平稳分量后的对称归一化邻接矩阵，该形式匹配标准GCN类模型的归一化方式，同时分离出最直接关联过平滑的平稳方向。核心理论问题是：该修正后的归一化算子在多层传播后能否保留类别可区分信号？主要结果是在密集多对数稀疏度下（$p \ge C\log^B n/n$，任意固定 $B>4$），于二元上下文随机块模型中，当传播层数 $k=O(\log n)$ 时，在明确的图信号与特征信噪比条件下，实现高概率精确恢复。此外，还建立了多分类部分恢复定理，表明大多数节点趋于类别中心。通过合成与真实节点分类实验，验证了理论对深度、图信号及特征噪声依赖性的预测。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。