深度影响图神经网络性能，由信号衰减率决定临界点。
The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy
- 通过泊松伽尔顿-沃森树建模稀疏图，分析消息传递深度的统计极限。
- 深度低于阈值时误差指数收敛，高于阈值时可加速逼近最优分类下限。
- 揭示了有限最优深度的存在性，为模型设计提供理论指导。
在平均度数为常数的稀疏上下文随机块模型（CSBM）上研究图神经网络所需深度。其局部弱极限为带标签的泊松伽尔顿-沃森树。已有工作提出基于距离 $k\le\ell$ 的消息传递分类器 $h_\ell$，聚合衰减证据 $2\operatorname{artanh}(γ^k t(X_v))$，其中 $γ$ 为边信号强度，$t$ 为特征的有界似然比变换。本文证明深度价值由单一参数 $κ=γ^2Δ$ 决定：当 $κ<1$ 时，误差序列以几何速率 $κ^{(\ell+1)/3}$ 收敛，超过 $O(\log(1/ε))$ 层后误差变化小于 $ε$；当 $κ>1$ 时，误差以速率 $κ^{-s\ell}$（$s<1$）逼近分支过程下界，该下界不超过 $1/(κ-1)$，仅在 $κ>17$ 时有实际意义。任何局部分类器都无法突破孤立根设定的通用下界 $e^{-Δ}Φ(-ζ)$（$ζ$ 为信噪比），但第一层能带来明确的总变差提升。模拟显示，配对规则误差曲线非单调，存在最优有限深度（附录中已验证实例）；而精确信念传播（BP）饱和更快，有效每层比率为低于 $κ$ 的值，本文予以识别。
原文摘要 · Abstract (English)
How deep does a graph neural network need to be on a sparse graph? We study its purest statistical form: node classification on the sparse contextual stochastic block model (CSBM) with average degree $Δ=O(1)$, whose local weak limit is a broadcast-labelled Poisson Galton-Watson tree. Prior work derived a message-passing classifier $h_\ell$ that aggregates from each vertex at distance $k\le\ell$ the attenuated evidence $2\operatorname{artanh}(γ^k t(X_v))$, with $γ$ the edge signal and $t$ a bounded likelihood-ratio transform of the feature. We prove that the value of depth is governed by a single number, the Kesten-Stigum ratio $κ=γ^2Δ$. Below the threshold ($κ<1$), the error sequence is Cauchy at a geometric rate, $|\mathcal{E}(\ell)-\mathcal{E}(\ell')|\le Cκ^{(\ell+1)/3}$ for all $\ell'>\ell$, so all layers beyond depth $O(\log(1/ε))$ change the error by less than $ε$; conversely, under mild regularity each sufficiently deep layer still flips the decision with probability at least $cκ^{\ell/2}$, the empirically sharp exponent. Above the threshold ($κ>1$), depth is geometrically productive: $\mathcal{E}(\ell)$ is driven to a branching-process floor of order at most $1/(κ-1)$ at any geometric rate $κ^{-s\ell}$, $s<1$ (this bound has content only for $κ>17$). No local classifier of any depth beats the universal floor $e^{-Δ}Φ(-ζ)$ set by isolated roots ($ζ$ the feature signal-to-noise ratio), while the first layer provably helps by an explicit total-variation amount. Simulations with an exact belief-propagation baseline on the same trees show that the pairwise rule's error curve is mildly non-monotone in $\ell$, so an optimal finite depth exists (an exact instance is certified in the appendix), while BP saturates strictly faster, at an effective per-layer ratio below $κ$ that we identify.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。