REVIEW 3 major objections 5 minor 2 cited by
Residual connections provably mitigate oversmoothing in graph neural networks
T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read Residual connections provably slow the exponential fading of node features in linear graph neural networks.
desk verdict Excellent exact-rate results for linear GNNs, but the residual theorem's proof has a gap and the title overreaches beyond σ = Id. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is the multiplicative ergodic theorem (Oseledets theorem) applied to linear random dynamical systems on the tensor product space $\mathbb{C}^d \otimes \mathbb{C}^n$. The aggregation matrix $P$ is decomposed into generalized eigenspaces; the dynamics act as products of random matrices $W(t)$ along each eigenvalue branch, and the relevant constants $R(\beta, P_W)$ are the top Lyapunov exponents of the random products of $I_d + \beta W(t)$. The vertex similarity measure $\mu(x)$ is then expressed as the ratio of the Frobenius norm of the component orthogonal to the constant eigenvector to the full norm, and the Oseledets filtration supplies the generic initial conditions that make the rates exact.
What would settle it
Pick a small connected graph and a weight distribution satisfying the assumptions, e.g. $W(t)$ with i.i.d. standard Gaussian entries, run the linear non-residual dynamics for many layers, and check whether $\mu(x_{\mathrm{nrs}}(t))^{1/(2t)}$ converges to the second-largest eigenvalue magnitude of $P$; a persistent discrepancy would disprove Theorem 2.4. For the residual theorem, compute the Lyapunov exponent $R(\alpha\lambda, P_W)$ by direct simulation and compare $\lim \mu(x_{\mathrm{rs}}(t))^{1/(2t)}$ with the lower bound; observing a rate below the bound would refute Theorem 2.5.
Extended reading notes
Core claim
The paper's central claim is that oversmoothing in deep GNNs has a sharp asymptotic rate, and adding a residual connection changes that rate provably. With the vertex similarity measure $\mu(x)$ from Definition 2.1, Theorem 2.4 shows that for the linear non-residual dynamics, $\mu(x_{\mathrm{nrs}}(t))^{1/(2t)}$ converges almost surely to $\max_{\lambda \in \mathrm{spec}(P)\setminus\{1\}} |\lambda| < 1$, a rate independent of the weight distribution. Theorem 2.5 shows that the residual dynamics satisfy $\lim_{t\to\infty} \mu(x_{\mathrm{rs}}(t))^{1/(2t)} \ge \frac{\max_{\lambda \neq 1} R(\alpha\lambda, P_W)}{\max_{\lambda} R(\alpha\lambda, P_W)}$, with equality when $P$ is diagonalizable; for several specific weight ensembles the lower bound is strictly larger than $\max_{\lambda \neq 1} |\lambda|$, and in some cases equals $1$, meaning features only fade subexponentially. The proofs work through the multiplicative ergodic theorem, and the theory is supported by experiments on Cora, CiteSeer, and PubMed with linear, ReLU, and LeakyReLU activations.
Load-bearing premise
The theorems assume the activation is the identity map, so all proven statements concern linear GNN dynamics; the nonlinear cases appear only in numerical experiments.
Editorial extensions
If this is right
- For any graph whose aggregation matrix satisfies the paper's Assumption 2 and any weight distribution meeting the moment condition, a non-residual GNN loses vertex distinguishability at the exponential rate set by the second-largest eigenvalue magnitude of P.
- Residual GNNs have a rigorously computable lower bound on their similarity decay rate, and for deterministic weights, Ginibre Gaussian weights, bounded-norm weights, and simultaneously diagonalizable weights the bound exceeds the non-residual rate.
- In the bounded-norm case with small step size, the residual rate is at least a closed-form expression in the weight norm bound, the step size, and the extreme eigenvalues of P, giving an explicit design criterion.
- When the weight distribution is symmetric and sufficiently small, the residual similarity measure converges to 1, meaning oversmoothing is prevented entirely rather than merely slowed.
Reading between the lines
- If the linear dynamics are a good proxy for ReLU/LeakyReLU networks, the spectral quantity $\max_{\lambda \neq 1} |\lambda|$ becomes a practical predictor of how deep a plain GNN can go before features collapse; the experiments on trained networks are consistent with that but do not prove it.
- The ratio structure of the residual rate suggests a possible initialization or step-size design principle: choose weight distributions and $\alpha$ that maximize the smallest $R(\alpha\lambda, P_W)$ relative to $R(\alpha, P_W)$.
- Because the framework allows complex eigenvalues and asymmetric $P$, it may extend to directed or non-reversible aggregation schemes where previous symmetric-spectrum analyses do not apply.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies oversmoothing in deep graph neural networks. It introduces a normalized vertex similarity measure μ(x) and, under the assumptions that the activation is the identity, the aggregation matrix P is a fixed primitive stochastic matrix, and the weight matrices W(t) are i.i.d., proves two main asymptotic results. Theorem 2.4 shows that for the non-residual linear dynamics, μ(x_nrs(t))^{1/(2t)} converges almost surely to max_{λ∈spec(P)\setminus{1}} |λ| < 1 for Lebesgue-almost every initial condition. Theorem 2.5 shows that for the residual linear dynamics, the corresponding quantity is almost surely at least the ratio of the Lyapunov exponents R(αλ, P_W) over the spectrum of P, with equality when P is diagonalizable over C. The paper then specializes these results to deterministic weights, the Ginibre ensemble, bounded-norm weights, and simultaneously diagonalizable weights, and reports numerical experiments on Cora, CiteSeer, and PubMed that compare linear and nonlinear GCNs with and without residual connections.
Significance. If the proofs are completed, the paper would provide exact exponential oversmoothing rates for linear GNNs, strengthening earlier upper bounds, and would rigorously demonstrate for several weight distributions that residual connections strictly slow or stop exponential oversmoothing, including for aggregation matrices with complex spectrum. The analytical framework based on the multiplicative ergodic theorem is a useful contribution, and the explicit treatment of the Ginibre and bounded-norm cases gives concrete, testable predictions. The manuscript is also honest in its Conclusion about the main limitation: all theorems assume σ = Id, while the numerical experiments include ReLU and LeakyReLU. Because the central proof of Theorem 2.5 currently contains a gap and one of the stated corollaries is not implied by the proof, the paper needs substantial revision before the claims can be accepted as proven.
major comments (3)
- [Section 3.1, Proposition 3.5] The exceptional set U(ω) in Proposition 3.5 is constructed incorrectly, and the proof of the proposition is therefore incomplete. The proposition assumes C^m = Q_1 ⊕ ... ⊕ Q_k with each Q_i invariant, and defines U(ω) as the Oseledets subspace U_2(Q_1) inside the top block Q_1. The proof then establishes the desired rate only under the condition u_1 ∉ U(ω). But the proposition's conclusion is required to hold for every u outside U(ω), and since U(ω) ⊂ Q_1, vectors with components outside Q_1 are outside U(ω) even when their Q_1 component lies in U_2(Q_1). For example, with C^2 = Q_1 ⊕ Q_2 and A = diag(2,1), the proof's U(ω) is {0}, so u = e_2 is outside U(ω), yet its growth rate is 0, not log 2. The correct exceptional set is U_2(Q_1) ⊕ Q_2 ⊕ ... ⊕ Q_k, because u_1 ∉ U_2(Q_1) is then equivalent to u being outside that direct sum. Lemma 3.12 requires two such bad sets (one for the full vector and one for the component orthogonal to the Perron eigenspace), and their union is a finite union of proper subspaces, which is sufficient for the 'almost every x(0)' statements. As written, Proposition 3.5 underpins both limits in Lemma 3.12 and hence the proof of Theorem 2.5; the gap is load-bearing and must be repaired.
- [Section 2.2.3, Theorem 2.10 and Section 3.5.3] The sufficient condition stated in the corollary of Theorem 2.10 is inconsistent with the condition actually proved in Section 3.5.3. The theorem states that strict improvement follows if (1 - max_{λ≠1}|λ|)/(1 - min_{λ≠1}|λ|) > αrW/(1 + αrW), which is equivalent to 1 - max|λ| > αrW(max|λ| - min|λ|). The proof, however, derives the strict inequality from the stronger condition αrW(min|λ| + max|λ|) < 1 - max|λ|. These conditions are not equivalent; for example, max|λ| = 0.6, min|λ| = 0.4, and αrW = 0.5 satisfy the stated corollary condition but violate the proved condition. Consequently, the corollary as stated is unproven, which affects the claim that residual connections provably mitigate oversmoothing for the entire bounded-norm family covered by the theorem.
- [Title, Abstract, and Section 2.1 (Assumption 1)] The title and abstract claim that residual connections 'provably mitigate oversmoothing in graph neural networks' without qualification, but every theorem in the paper assumes Assumption 1, that σ = Id. The numerical experiments include ReLU and LeakyReLU activations, but no theorem covers nonlinear activations, and the Conclusion explicitly lists this as a limitation. The presentation should either restrict the claims to linear GNNs in the title and abstract, or add an explicit discussion stating that the nonlinear case is not proven and is only supported empirically. This is a scope issue rather than a mathematical error, but it is important for accurate dissemination.
minor comments (5)
- [Section 3.2, equation (3.7)] The notation in (3.7) is confusing: the spaces V_i are called 'generalized left eigenspaces,' but the displayed action P φ_{i,j} = λ_i φ_{i,j} + φ_{i,j+1} describes right eigenvectors/columns. Please clarify whether these are left or right generalized eigenspaces and make the orientation consistent with the decomposition C^d ⊗ C^n.
- [Section 3.1, text before Proposition 2.3] The text contains a broken reference: 'see e.g., []raghunathan, Ruelle-1979, Walters-93.' The intended references are not properly formatted and do not appear in the bibliography; please correct this.
- [Section 4.1, Table 1] There is a typo in the caption and text: 'LeakyRuLU' should be 'LeakyReLU.'
- [Section 2.2.1, first paragraph] The sentence 'In all the cases considered here indicate that residual connections effectively mitigate oversmoothing' has a grammatical error ('In all the cases considered here indicate' should read 'In all the cases considered here, the results indicate' or similar).
- [Section 3.5.1, proof of Theorem 2.7] In the proof of Theorem 2.7, the inference 'the inequality is guaranteed by α Re μ0 + 1 ≥ 0' appears to require a separate justification when λ0 is negative; please state explicitly which inequalities are used and confirm the direction for λ0 ∈ (-1,0).
Circularity Check
No significant circularity: the oversmoothing rates are derived from the stated linear random dynamical system via the multiplicative ergodic theorem and standard auxiliary results, with no fitted inputs, load-bearing self-citations, or definitional equivalences.
full rationale
The paper's central results are self-contained derivations from explicit assumptions. Theorem 2.4 and Theorem 2.5 are proved from the multiplicative ergodic theorem (Theorem 3.3) applied to the linear dynamics defined in (3.12) and (3.27); the constants R(P_W) and R(beta, P_W) in Proposition 2.3 are defined as Lyapunov exponents of the same products of random matrices and are then evaluated for specific ensembles (deterministic, Ginibre, bounded norm, simultaneously diagonalizable) using independent standard results such as Gelfand's formula, the strong law of large numbers, and [CN84, Proposition 2.1]. No parameter is fitted to the oversmoothing rate being 'predicted', and no self-citation carries a load-bearing premise. The sigma=Id restriction is stated up front as Assumption 1 and is explicitly acknowledged as a limitation in Section 5, so it is a scope limitation rather than a circular step. The proof gap in Proposition 3.5 flagged by the reviewer is an internal correctness issue, not a circular reduction, and therefore does not affect the circularity score.
Assumptions & free parameters
assumptions (5)
- standard math Multiplicative ergodic theorem for products of random matrices in C^m (Arnold 1998, Theorem 3.4.1).
- standard math Perron-Frobenius theorem for primitive nonnegative matrices.
- standard math Equivalence of norms on finite-dimensional vector space (Propositions 3.6 and 3.8).
- standard math Cohen and Newman (1984) Proposition 2.1 for Lyapunov exponents of isotropic random matrices.
- standard math Strong law of large numbers for i.i.d. real random variables.
Cite this review
Pith. "Pith review of Residual connections provably mitigate oversmoothing in graph neural networks." pith.science (2026). https://pith.science/paper/ZPSLB4XO
@misc{pith2026250100762,
author = {Pith},
title = {Pith review of: Residual connections provably mitigate oversmoothing in graph neural networks},
year = {2026},
howpublished = {\url{https://pith.science/paper/ZPSLB4XO}},
note = {Machine review of arXiv:2501.00762}
}
read the original abstract
Graph neural networks (GNNs) have achieved remarkable empirical success in processing and representing graph-structured data across various domains. However, a significant challenge known as "oversmoothing" persists, where vertex features become nearly indistinguishable in deep GNNs, severely restricting their expressive power and practical utility. In this work, we analyze the asymptotic oversmoothing rates of deep GNNs with and without residual connections by deriving explicit convergence rates for a normalized vertex similarity measure. Our analytical framework is grounded in the multiplicative ergodic theorem. Furthermore, we demonstrate that adding residual connections effectively mitigates or prevents oversmoothing across several broad families of parameter distributions. The theoretical findings are strongly supported by numerical experiments.
Figures
Figures from the paper (1 more)
Forward citations
Cited by 2 Pith papers
-
On the Diverse Dynamical Behaviors Arising in Deep Linear Transformers
Linear self-attention in 2D reduces to a second-harmonic Kuramoto model whose order parameter obeys one ODE; explicit matrix conditions yield clustering, rotating clusters, Hamiltonian oscillations, and bifurcations.
-
Critical attention scaling in long-context transformers
In a simplified attention model with normalized tokens, the phase boundary between token collapse and identity attention occurs when the attention-temperature scaling factor β_n is of order log n, with constant 1/(1−ρ).
Reference graph
Works this paper leans on
-
[1]
Ludwig Arnold. Random dynamical systems . Springer monographs in mathematics. Springer, New York, 1998
work page 1998
-
[2]
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI conference on artificial intelligence , volume 34, pages 3438--3445, 2020
work page 2020
-
[3]
Fastgcn: fast learning with graph convolutional networks via importance sampling
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgcn: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv:1801.10247 , 2018
arXiv 2018
-
[4]
Joel E. Cohen and Charles M. Newman. The stability of large random matrices and their products. Ann. Probab. , 12:283--310, 1984
work page 1984
-
[5]
A note on over-smoothing for graph neural networks
Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006.13318 , 2020
arXiv 2006
-
[6]
Gage DeZoort and Boris Hanin. Principles for initialization and architecture selection in graph neural networks with relu activations. arXiv preprint arXiv:2306.11668 , 2023
work page Pith review arXiv 2023
-
[7]
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric . In ICLR Workshop on Representation Learning on Graphs and Manifolds , 2019
work page 2019
-
[8]
Understanding the difficulty of training deep feedforward neural networks
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics , pages 249--256. JMLR Workshop and Conference Proceedings, 2010
work page 2010
Show all 34 references
-
[9]
Exact combinatorial optimization with graph convolutional neural networks
Maxime Gasse, Didier Ch \'e telat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in neural information processing systems , 32, 2019
2019
-
[10]
Neural message passing for quantum chemistry
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning , pages 1263--1272. PMLR, 2017
2017
-
[11]
An overview on the application of graph neural networks in wireless networks
Shiwen He, Shaowen Xiong, Yeyu Ou, Jian Zhang, Jiaheng Wang, Yongming Huang, and Yaoxue Zhang. An overview on the application of graph neural networks in wireless networks. IEEE Open Journal of the Communications Society , 2:2547--2565, 2021
2021
-
[12]
Deep residual learning for image recognition
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition , pages 770--778, 2016
2016
-
[13]
Not too little, not too much: a theoretical analysis of graph (over) smoothing
Nicolas Keriven. Not too little, not too much: a theoretical analysis of graph (over) smoothing. Advances in Neural Information Processing Systems , 35:2268--2281, 2022
2022
-
[14]
Adam: A method for stochastic optimization
Diederik P Kingma. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 , 2014
2014 arXiv
-
[15]
Kipf and Max Welling
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations , 2017
2017
-
[16]
A review of graph neural networks and their applications in power systems
Wenlong Liao, Birgitte Bak-Jensen, Jayakrishnan Radhakrishna Pillai, Yuelong Wang, and Yusen Wang. A review of graph neural networks and their applications in power systems. Journal of Modern Power Systems and Clean Energy , 10(2):345--360, 2021
2021
-
[17]
Deeper insights into graph convolutional networks for semi-supervised learning
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence , volume 32, 2018
2018
-
[18]
Graph neural networks meet wireless communications: Motivation, applications, and future directions
Mengyuan Lee, Guanding Yu, Huaiyu Dai, and Geoffrey Ye Li. Graph neural networks meet wireless communications: Motivation, applications, and future directions. IEEE Wireless Communications , 29(5):12--19, 2022
2022
-
[19]
Markov chains
James R Norris. Markov chains . Number 2. Cambridge university press, 1998
1998
-
[20]
Graph neural networks exponentially lose expressive power for node classification
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations , 2020
2020
-
[21]
A multiplicative ergodic theorem
Valery Iustinovich Oseledets. A multiplicative ergodic theorem. liapunov characteristic numbers for dynamical systems. Trans. Moscow Math. Soc. , 19:197--231, 1968
1968
-
[22]
A survey on oversmoothing in graph neural networks
T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. SAM Research Report , 2023, 2023
2023
-
[23]
Graph neural networks in particle physics
Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant. Graph neural networks in particle physics. Machine Learning: Science and Technology , 2(2):021001, 2020
2020
-
[24]
The graph neural network model
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks , 20(1):61--80, 2008
2008
-
[25]
Residual connections and normalization can provably prevent oversmoothing in gnns
Michael Scholkemper, Xinyi Wu, Ali Jadbabaie, and Michael Schaub. Residual connections and normalization can provably prevent oversmoothing in gnns. arXiv preprint arXiv:2406.02997 , 2024
2024
-
[26]
Graph attention networks
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations , 2018
2018
-
[27]
Demystifying oversmoothing in attention-based graph neural networks
Xinyi Wu, Amir Ajorlou, Zihui Wu, and Ali Jadbabaie. Demystifying oversmoothing in attention-based graph neural networks. Advances in Neural Information Processing Systems , 37, 2023
2023
-
[28]
A non-asymptotic analysis of oversmoothing in graph neural networks
Xinyi Wu, Zhengdao Chen, William Wei Wang, and Ali Jadbabaie. A non-asymptotic analysis of oversmoothing in graph neural networks. In The Eleventh International Conference on Learning Representations , 2023
2023
-
[29]
A comprehensive survey on graph neural networks
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems , 32(1):4--24, 2020
2020
-
[30]
A review on graph neural network methods in financial applications
Jianian Wang, Sheng Zhang, Yanghua Xiao, and Rui Song. A review on graph neural network methods in financial applications. Journal of Data Science , 20(2), 2022
2022
-
[31]
Revisiting semi-supervised learning with graph embeddings
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning , pages 40--48. PMLR, 2016
2016
-
[32]
Graph neural networks: A review of methods and applications
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. AI Open , 1:57--81, 2020
2020
-
[33]
Graph neural networks and their current applications in bioinformatics
Xiao-Meng Zhang, Li Liang, Lin Liu, and Ming-Jing Tang. Graph neural networks and their current applications in bioinformatics. Frontiers in genetics , 12:690049, 2021
2021
-
[34]
A comprehensive review of the oversmoothing in graph neural networks
Xu Zhang, Yonghui Xu, Wei He, Wei Guo, and Lizhen Cui. A comprehensive review of the oversmoothing in graph neural networks. In CCF Conference on Computer Supported Cooperative Work and Social Computing , pages 451--465. Springer, 2023
2023
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.