{"id":"5ff98cf9-13e2-4bd7-ac61-3b6c4816d141","arxiv_id":"2501.00762","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For linear GNNs, the oversmoothing rate is exactly the second eigenvalue magnitude of the neighbor-averaging matrix, and residual connections provably push that rate toward 1 for many weight distributions.","lead":"This paper proves exact mathematical rates at which deep graph neural networks lose the ability to distinguish vertices, and shows that adding residual connections slows or stops that collapse. It matters because oversmoothing is a main barrier to training deep GNNs, and the rates cover several families of random weight matrices.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Theorem 2.5 relies on Proposition 3.5, whose exceptional set is constructed incorrectly: U=U2(Q1)⊂Q1 misses the other invariant summands, so vectors with u1∈U2(Q1) can lie outside U yet fail to attain the maximal Lyapunov exponent. Taking U=U2(Q1)⊕Q2⊕...⊕Qk repairs the proof.","rationale":"The reader's weakest assumption is the identity-activation scope, which is a real limitation of the paper's title and interpretation. However, the more load-bearing technical issue is in the proof of the central residual theorem: Lemma 3.12 is obtained by 'a direct application of Proposition 3.5', and the construction of the exceptional set in Proposition 3.5 is wrong as written. The proposition's statement may be true, and the proof is repairable by taking the bad set to be U2(Q1)⊕Q2⊕...⊕Qk, so this is not a reason to reject the mathematical claims. It is, however, a correctness gap that a conditional acceptance should require fixing. The Theorem 2.10 corollary condition noted by the reader is also a real but secondary issue, as are the title/abstract overclaims about general GNNs. With the proof of Proposition 3.5 corrected and the scope clarified, the linear-GNN results appear sound and the reader's CONDITIONAL verdict remains appropriate.","tokens_in":28452,"tokens_out":25888,"duration_ms":253246,"concrete_test":"Run the deterministic sanity check for Proposition 3.5 on Ω={ω}, Φ(t)=diag(2,1)^t, Q1=span(e1), Q2=span(e2). The proof's U=U2(Q1)={0}; for u=e2 compute lim (1/t)log||Φ(t)u||=0, whereas max ν1=log2, showing the construction is wrong. Then replace U by U2(Q1)⊕Q2=span(e2), verify the proposition's conclusion, and re-derive Lemma 3.12 by taking the union of the two corrected direct-sum bad sets. If the repaired proof yields exactly the two limits in (3.30), Theorem 2.5 stands conditional on this fix.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Proposition 3.5, after fixing the top invariant subspace Q1, the proof sets U(ω) to be the Oseledets subspace U2(Q1) of the restriction to Q1, viewed as a subspace of C^m. It then proves the desired rate only under the condition u1∉U(ω). But the proposition's conclusion requires the rate for every u outside U(ω), and U(ω)⊂Q1 does not control the other components. For example, with C^2=Q1⊕Q2 and A=diag(2,1), the proof's U is {0}; u=e2 is outside U, yet its growth rate is 0, not log2. The correct bad set is U2(Q1)⊕Q2⊕...⊕Qk, since u1∉U2(Q1) is then equivalent to u being outside that direct sum. Lemma 3.12 needs 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. Thus the main residual theorem is likely true, but the manuscript's proof of the central result is incomplete as written. This is an internal correctness issue, distinct from the σ=Id scope limitation that the reader already flagged.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":1930,"tokens_out":2093,"duration_ms":87109,"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":[{"comment":"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":"Section 3.1, Proposition 3.5"},{"comment":"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.","section":"Section 2.2.3, Theorem 2.10 and Section 3.5.3"},{"comment":"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.","section":"Title, Abstract, and Section 2.1 (Assumption 1)"}],"minor_comments":[{"comment":"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":"Section 3.2, equation (3.7)"},{"comment":"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":"Section 3.1, text before Proposition 2.3"},{"comment":"There is a typo in the caption and text: 'LeakyRuLU' should be 'LeakyReLU.'","section":"Section 4.1, Table 1"},{"comment":"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":"Section 2.2.1, first paragraph"},{"comment":"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).","section":"Section 3.5.1, proof of Theorem 2.7"}],"recommendation":"major_revision","confidential_remarks":"The paper's core idea is sound and the results, if the proof gaps are fixed, are a meaningful contribution to the theoretical understanding of oversmoothing in linear GNNs. The flaw in Proposition 3.5 is serious but appears repairable with the construction U = U_2(Q_1) ⊕ Q_2 ⊕ ... ⊕ Q_k, and the Theorem 2.10 corollary can likely be repaired by strengthening the stated condition or correcting the proof. I would encourage the editor to request a revision that addresses these two points explicitly, and to ask the authors to qualify the title/abstract claims. The numerical experiments are supportive but should not be taken as evidence for the nonlinear case, which the authors themselves acknowledge as an open problem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know before reading it. First, the theorems all assume identity activation, despite the title's general claim. Second, the proof of the central residual result (Theorem 2.5) has a gap in Proposition 3.5, though the fix is straightforward.\n\nWhat is genuinely new: Theorem 2.4 gives the exact oversmoothing rate for non-residual GNNs, lim μ(x)^{1/(2t)} = max_{λ≠1}|λ|, independent of the weight distribution. That sharpens the upper bounds of Oono-Suzuki and Cai-Wang. Theorem 2.5 characterizes the residual rate via Lyapunov exponents R(αλ, P_W), with equality for diagonalizable P, and the explicit computations for Ginibre, bounded-norm, and simultaneously diagonalizable weights are real contributions. The multiplicative ergodic theory framework fits naturally, and the tensor-product decomposition is clean. The numerical experiments support the qualitative claims.\n\nSoft spots, in order of severity. (1) All theorems require σ = Id. The authors mention this in the limitations paragraph, but the abstract and title promise more; the ReLU experiments are suggestive only. This should be a prominent caveat. (2) The proof of Proposition 3.5 is incorrect as written. It defines U = U2(Q1) ⊂ Q1 and proves the rate only under u1 ∉ U2(Q1), but the proposition claims the rate for every u outside U. Vectors with u1 ∈ U2(Q1) but nonzero components in other invariant summands are outside U yet need not attain the maximal Lyapunov exponent (e.g., C^2 = Q1 ⊕ Q2, A = diag(2,1), u = e2). The correct exceptional set is U2(Q1) ⊕ Q2 ⊕ ... ⊕ Qk; Lemma 3.12 needs two such bad sets and their union has measure zero, so the almost-everywhere statements survive. The gap is repairable but real. (3) The corollary in Theorem 2.10 states a sufficient condition, (1−max)/(1−min) > αr_W/(1+αr_W), that is weaker than the proof's actual condition and does not imply the claimed strict inequality. That needs correcting.\n\nBottom line: the main ideas and residual-mitigation conclusion are likely sound, but the manuscript needs a revision fixing Proposition 3.5 and the Theorem 2.10 corollary, and prominently confining claims to linear dynamics. I would send it to referees rather than desk-reject, but I would ask for a careful proof check.","headline":"Excellent exact-rate results for linear GNNs, but the residual theorem's proof has a gap and the title overreaches beyond σ = Id.","tokens_in":29283,"tokens_out":5708,"would_cite":true,"duration_ms":51809,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["37H15","60B20","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"Residual connections provably slow the exponential fading of node features in linear graph neural networks.","keywords":["oversmoothing","graph neural networks","residual connections","multiplicative ergodic theorem","Lyapunov exponents","random matrices","vertex similarity","asymptotic rates"],"falsifier":"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.","tokens_in":28249,"feed_emoji":"📉","tokens_out":7131,"duration_ms":60012,"temperature":0.7,"pith_summary":"This paper asks a precise question: how fast do node features in a deep message-passing GNN become indistinguishable, and can a skip connection change the answer? For linear activations, a constant aggregation matrix, and independent identically distributed weight matrices, it derives exact asymptotic rates for a normalized vertex similarity measure $\\mu(x)$. The non-residual dynamics collapse features at an exponential rate set only by the second-largest eigenvalue magnitude of the aggregation matrix, regardless of the weight distribution. The residual dynamics either collapse at a strictly slower rate or not at all, depending on the weight distribution and step size $\\alpha$. The authors conclude that residual connections provably mitigate or prevent oversmoothing for the covered linear dynamics.","feed_headline":"Residual connections provably slow GNN oversmoothing","feed_subtitle":"Sharp rates show plain GNNs fade exponentially while residual versions can stay distinguishable in deep networks.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Original multiplicative ergodic theorem that supplies the Lyapunov exponents used to define $R(\\beta, P_W)$.","marker":"[Ose68]"},{"why":"Textbook statement of the multiplicative ergodic theorem and random dynamical systems used throughout the proofs.","marker":"[Arn98]"},{"why":"Prior exponential oversmoothing upper bound for GCNs that this paper refines to an exact rate.","marker":"[OS20]"},{"why":"Prior analysis of over-smoothing convergence rate that this paper's Theorem 2.4 sharpens.","marker":"[CW20]"},{"why":"Prior result on residual GNNs with ReLU and Gaussian weights that this paper broadens to other weight distributions without layer-count-dependent step size.","marker":"[DH23]"},{"why":"Provides the one-dimensional distributional result used to compute $R(\\beta, P_W)$ for the Ginibre ensemble.","marker":"[CN84]"},{"why":"Existing proof that residual connections can prevent oversmoothing, contrasted with the consecutive-layer residual studied here.","marker":"[SWJS24]"},{"why":"Standard reference for the Markov chain and Perron-Frobenius facts behind Assumption 2.","marker":"[Nor98]"}],"fun_headline_variants":["Residual connections provably fix GNN oversmoothing","GNN oversmoothing stopped by residual links","Provable cure: residual connections beat oversmoothing","Residual links prevent exponential GNN fading"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Residual connections provably fix GNN oversmoothing","GNN oversmoothing stopped by residual links","Provable cure: residual connections beat oversmoothing","Residual links prevent exponential GNN fading"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000925,"raw_usage":{"total_tokens":3955,"prompt_tokens":926,"completion_tokens":3029,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":542,"completion_tokens_details":{"reasoning_tokens":2968}},"tokens_in":542,"tokens_out":3029,"duration_ms":21427,"temperature":1.0,"reasoning_tokens":2968,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:43:38.368473+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}