{"id":"c75972c2-6a0a-4ab6-8b8f-f7ef9373f20f","arxiv_id":"2506.18356","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Componentwise perturbation bounds and subtraction-free Newton and block Jacobi variants keep multilinear PageRank accurate even as the Jacobian becomes singular at alpha=1/2.","lead":"This paper proves that standard error estimates overstate how badly multilinear PageRank solutions can be perturbed, and it gives algorithms that stay accurate when the problem nears a singularity. If correct, network scientists can trust tiny probability values in higher-order ranking models, and analysts get new tools for a family of quadratic equations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 'no blow-up at α=1/2' bound in Thm 4.4 relies on Thm 3.4's bounded-S lemma, whose irreducibility and constant-offdiag hypotheses are neither stated nor verified for R_m^T; if they fail, omega in (4.8) may diverge.","rationale":"Reading in good faith, the paper is a solid contribution: Theorem 3.4 is an interesting decomposition, the componentwise perturbation framework is well motivated, and the numerical experiments convincingly show componentwise gains for the proposed GTH-based algorithms. However, the strongest advertised result — that the minimal-solution perturbation bound does not blow up at α=1/2 — is load-bearing on the boundedness of S in Theorem 3.4. That boundedness is proved only under irreducibility of the M-matrix sequence, with constant off-diagonal entries, while Theorem 4.4 applies it to R_m^T without stating or verifying either condition. Since m(α) varies with α, the off-diagonal entries of R_m^T are not constant along the sequence, and for reducible P the support graph may fail to be irreducible. The proof therefore does not justify the 'does not diverge when α→1/2' statement for the claimed generality. This matches the reader's weakest_assumption, and I agree with it. The secondary issue — the theorem guarantees only 'a solution', not the minimal solution — is real and should be clarified, but it is less central than the unproven boundedness of omega. The concrete test proposed would settle whether the concern lands as a genuine counterexample or only as a proof gap requiring an additional assumption.","tokens_in":1040,"tokens_out":1018,"duration_ms":347478,"concrete_test":"Fix a reducible-support stochastic tensor, for example n=2 with P(1) = [[1,0,0,0],[0,1,1,1]] and v = (0.5,0.5), plus n=3 variants having a closed subset in the support graph of R_m^T. For alpha_k = 0.5 − 10^{-k}, k = 4,...,14, compute the minimal solution m, form M = R_m^T, construct S by formula (3.6), and evaluate omega_k = max_i (S^T m)_i/m_i. If sup_k omega_k diverges like (1−2 alpha_k)^{-1}, the bound 2*omega*gamma*epsilon blows up and the 'no blow-up' claim fails as stated; if omega_k stays bounded despite reducibility, then the gap is only in the proof, and the paper should be revised to add the missing hypothesis or a generalized stability theorem covering non-constant-offdiag reducible sequences.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's central singularity-avoidance claim is Theorem 4.4, whose proof replaces R_m^{-1} by S^T, using the decomposition of Theorem 3.4, and asserts that S is bounded as α→1/2. But Theorem 3.4's boundedness property is proved only for sequences M(w_k) that are irreducible and have constant off-diagonal entries while w_k→0. In Section 4.3, M = R_m^T; its off-diagonal entries change with α through m = m(α), and no irreducibility of the support graph of R_m^T is stated or verified in Theorem 4.4. If R_m^T is reducible, the polynomials D_i in the proof of Theorem 3.4 can vanish, and the bound used to control S may fail; omega in (4.8) could then grow like 1/(1−2α). In that case the formal inequality d(m_tilde,m) ≤ 2*omega*gamma*epsilon is still true for each fixed α, but it blows up at α=1/2, exactly the singularity the abstract promises to ignore. Thus the advertised 'ignore the singularity' property is unsupported for a class of valid stochastic tensors. The theorem needs either an explicit irreducibility/positive-support assumption on P or on R_m^T, or a separate argument showing that the tensor column-sum structure keeps S bounded even when R_m^T is reducible; neither is supplied. This is a genuine proof gap in the central claim, not merely a presentation issue.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies componentwise perturbation stability and numerical accuracy for the multilinear PageRank equation x = (1-α)v + αP x^2, and the more general quadratic equation x = a + Bx^2. The main theoretical results are: (i) a componentwise perturbation bound for the minimal solution when α < 1/2 (Theorem 4.3); (ii) an improved bound under zero-sum stochasticity-preserving perturbations, based on a decomposition of the inverse of an M-matrix into a rank-one part and a bounded remainder S, giving d(m̃,m) ≤ 2ωγε with ω defined via S (Theorem 4.4); (iii) an analysis of the limiting accuracy of Newton's method for α > 1/2, replacing the classical factor ‖R^{-1}_{x*}‖‖x*‖ by ‖|R^{-1}_{x*}|x*‖ (Theorems 6.1 and 6.2); and (iv) subtraction-free GTH-based Newton and block-Jacobi algorithms for computing the minimal solution with componentwise accuracy. Numerical experiments on real and synthetic tensors compare the proposed algorithms with standard Newton and illustrate the bounds.","tokens_in":24245,"tokens_out":10668,"duration_ms":112050,"significance":"If the central claims hold, the paper gives a genuinely useful message for multilinear PageRank: componentwise stability can be much better than classical Jacobian-based bounds suggest, both for perturbations and for rounding errors in Newton-type iterations. The combinatorial matrix-tree decomposition of the inverse into a bounded remainder S and a rank-one part is an interesting technical contribution that may have applications beyond PageRank. The algorithms are concrete, and the paper explicitly identifies the novel subtraction-free residual formula r = αPh². The theoretical derivations are internally consistent, and I checked the decomposition of Theorem 3.4 on small examples. The main caveat is that the headline 'ignoring the α = 1/2 singularity' claim depends on a boundedness property of S that is proved only under hypotheses not stated or verified in the main application, so the central claim needs an additional assumption or a separate argument.","major_comments":[{"comment":"The boundedness of the remainder S is the load-bearing ingredient in the claim that the componentwise bound d(m̃,m) ≤ 2ωγε 'ignores the singularity' at α = 1/2. Theorem 3.4 proves boundedness only for sequences M(w_k) of irreducible matrices with constant off-diagonal entries while w_k → 0. In Section 4.3, M = R_m^T has w = (1-2α)1 → 0, but the off-diagonal entries of R_m^T change with α through m = m(α), and Theorem 4.4 neither assumes nor verifies that R_m^T is irreducible. If the support graph of R_m^T is reducible, the polynomials D_i in the proof of Theorem 3.4 can vanish, the bound on S may fail, and ω defined in (4.8) can diverge as α → 1/2, e.g. like 1/(1-2α). In that case the formal inequality d(m̃,m) ≤ 2ωγε is still true for each fixed α, but it blows up exactly at the singularity that the abstract promises to ignore. The theorem needs an explicit irreducibility/positive-support assumption on P or R_m^T, or a separate argument showing that the tensor stochasticity structure keeps S bounded even when R_m^T is reducible; neither is supplied.","section":"Section 4.3, Theorems 3.4 and 4.4"},{"comment":"The fixed-point argument defines Bkh = {h : 1^T h = 0, |h| ≤ k_h m} and claims φ(Bkh) ⊆ Bkh, where φ(h) = S̃^T(ã - a + (B̃ - B)m² + B̃h²). The proof bounds |φ(h)| componentwise but does not show 1^T φ(h) = 0. This zero-sum preservation is necessary for the Brouwer fixed-point argument to produce a point in Bkh. It can be supplied from the conditions 1^T(ã-a)=0, 1^T(B̃-B)(1)=0, 1^T B̃ h² = α(1^T h)² = 0, and 1^T R̃_m = (1-2α)1^T; the argument should be written out.","section":"Section 4.3, proof of Theorem 4.4"},{"comment":"The numerical experiments include stochastic tensors with many zero entries, such as the 4×17 tensor in Example 4 and the tensor in Example 5. These are exactly the cases where the missing irreducibility hypothesis in Theorem 4.4 is most relevant. Before accepting the experimental confirmation of the non-blow-up bound as evidence for the theorem, the authors should verify that R_m^T is irreducible (or that the boundedness of S holds) for these examples, or state which additional property of these tensors makes the application of Theorem 3.4 valid.","section":"Section 7, Examples 4 and 5"}],"minor_comments":[{"comment":"The assumption m > 0 is stated in Section 2.3, but it should be recalled explicitly in the statements of Theorems 4.3 and 4.4 and in the abstract-level claims, since the componentwise distance d(·,·) divides by m_i and the quantities κ,ω in (4.2),(4.8) are undefined when some m_i = 0.","section":"Section 2.3 and Theorems 4.3-4.4"},{"comment":"The estimate |e_k| ≤ γ̃_{n²} x* + o(u) mixes the limit k → ∞, used to justify x̃_k - x* = o(1), with the limit u → 0 used in the o(u) term. The asymptotic regime in which (6.1) is intended should be stated more precisely (e.g., u → 0 with k large enough so that x̃_k is within a fixed contraction region).","section":"Theorem 6.2, equation (6.1)"},{"comment":"The notation ∥R^{-1}_{x*} e∥ in Theorem 6.1 is used for a vector norm applied to a vector, while ∥R^{-1}_{x*}∥ is an induced matrix norm; the norms should be named explicitly to avoid confusion between the two inequalities.","section":"Section 6, paragraph before Theorem 6.1"},{"comment":"The text correctly notes that the variant with the Newton-based scalar z_k may violate w_k ≤ m and has no monotonic convergence guarantee. Since the algorithm is still recommended on the basis of experiments, it would help to report a convergence failure rate or a theoretical condition under which the iteration converges.","section":"Section 5.2, variant of block Jacobi-GTH"},{"comment":"The paper observes that the theoretical perturbation bounds are quite loose. A short explanation of the main sources of looseness (the factor γ from Theorem 3.2, the use of ω or κ, and the quadratic term in the fixed-point argument) would make the experimental section more informative.","section":"Section 7, Figures 5-7"}],"recommendation":"major_revision","confidential_remarks":"The main risk is the gap in Theorem 4.4: the bounded-S property is essential for the 'ignore the singularity' headline, and its hypotheses are not checked for R_m^T. This is fixable by adding an irreducibility assumption or by proving boundedness under the stochastic-tensor structure, so I do not recommend rejection. The authors should also be asked to verify the irreducibility condition on the specific examples used in the experiments, since those tensors have many zeros."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a useful paper on componentwise stability of multilinear PageRank. The new results are real: Theorem 3.4 gives a rank-one-plus-stable decomposition of M-matrix inverses with good entrywise conditioning; Theorem 4.4 gets a componentwise bound under zero-sum (stochasticity-preserving) perturbations; and the two algorithms, Newton-GTH and block Jacobi-GTH, convincingly achieve componentwise accuracy where plain Newton stagnates. The residual identity r = αP h^2 is a neat trick that makes the Newton update subtraction-free. I would cite this work.\n\nThe fixed-α mathematics is internally consistent; I checked the key steps of Theorems 3.4 and 4.4 and they hold. The experiments are informative: the new algorithms reach errors near machine precision, and the quantity ∥|R^{-1} x*|x*∥ is a much better predictor of Newton's limiting accuracy than the Jacobian norm, as advertised.\n\nThe soft spot is the headline singularity-avoidance claim. Theorem 3.4's boundedness of the S term is proved only for sequences of irreducible M-matrices with constant off-diagonal entries while w→0. In Section 4.3, they apply this to R_m^T as α→1/2, but the off-diagonal entries of R_m^T change with α through m(α), and no irreducibility assumption on the support graph is stated or verified. Without that, ω in (4.8) could diverge like 1/(1−2α), which is exactly what the bound was supposed to avoid. The theorem as written is a fixed-α statement, and the asymptotic 'ignore the singularity' claim is not supported. This is a genuine proof gap, not a presentation nitpick. The fix is likely straightforward: add an explicit irreducibility (or positive-support) assumption on P, and argue the off-diagonals stay in a compact set so the polynomials D_i remain bounded away from zero. The authors should also soften 'bounds for the minimal solution' in the abstract, since the Brouwer argument gives some nearby solution, not necessarily the minimal one — minor, but it overstates the result.\n\nOverall, the algorithms and the fixed-α bounds are solid, and the paper deserves a serious referee. I'd send it with a request for major revision on the singularity claim, then accept.","headline":"Worth refereeing: solid componentwise perturbation theory and effective GTH-based algorithms, but the headline 'no blow-up at α=1/2' claim rests on an unstated irreducibility condition.","tokens_in":24886,"tokens_out":5905,"would_cite":true,"duration_ms":53183,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A69","15B51","65H10"],"pacs":[],"model":"deepseek-v4-flash","headline":"For alpha <= 1/2, multilinear PageRank solutions admit componentwise perturbation bounds that do not blow up at the alpha = 1/2 singularity.","keywords":["multilinear PageRank","componentwise perturbation bound","partial inverse of M-matrices","Newton method","GTH algorithm","block Jacobi method","quadratic vector equations","stochastic tensors"],"falsifier":"Take a tensor with two disconnected blocks, set $\\alpha$ extremely close to $1/2$, perturb $\\mathcal{P}$ and $v$ by a zero-sum componentwise perturbation of size $\\varepsilon$, and compare the observed $d(\\tilde m,m)$ with $2\\omega\\gamma\\varepsilon$: if $\\omega$ diverges or the inequality fails, the irreducibility support condition is load-bearing.","tokens_in":23690,"feed_emoji":"🧮","tokens_out":9403,"duration_ms":86048,"temperature":0.7,"pith_summary":"This paper studies how accurately solutions of the multilinear PageRank equation $x=(1-\\alpha)v+\\alpha \\mathcal{P}x^2$ can be computed and how stable they are under small data perturbations. The central claim is that standard error bounds based on the norm of the Jacobian are pessimistic: for $\\alpha\\le 1/2$, the minimal solution obeys a componentwise perturbation bound that stays finite as $\\alpha\\to 1/2$, the point where the Jacobian becomes singular, as long as perturbations preserve the stochastic normalization. For $\\alpha>1/2$, the limiting accuracy of Newton's method is controlled by the smaller quantity $u\\|\\lvert R_{x^*}^{-1}\\rvert x^*\\|$ rather than by $u\\|R_{x^*}^{-1}\\|\\|x^*\\|$. The paper also proposes subtraction-free GTH-based variants of Newton and block-Jacobi iterations that compute the minimal solution with componentwise accuracy even when the Jacobian is nearly singular. A new partial inverse of an M-matrix, which remains bounded as the matrix approaches singularity, is the mechanism behind this improved bound.","feed_headline":"Multilinear PageRank is componentwise stable up to alpha = 1/2","feed_subtitle":"Error bounds survive the alpha = 1/2 singularity; Newton's accuracy target is much smaller than classical bounds.","key_machinery":"The central object is a decomposition $M^{-1}=R+S$ for an M-matrix, obtained from the all-minors matrix tree theorem: $R$ is a rank-one matrix, and $S$ is a partial inverse that acts like the inverse on zero-sum vectors and remains bounded as the row sums of $M$ tend to zero (Theorem 3.4). Applied to $R_m^T$, this $S$ replaces the exploding $R_m^{-1}$ in the perturbation analysis, giving the finite quantity $\\omega$ in (4.8). The computational half uses a triplet representation of the Newton or block-Jacobi linear system and the GTH factorization, together with the subtraction-free residual update $r=\\alpha \\mathcal{P}h^2$; these avoid cancellation so that small entries of $m$ are computed with relative accuracy.","core_discovery":"The paper establishes two accuracy results. First, for the multilinear PageRank equation with $\\alpha\\le 1/2$, the minimal solution $m$ obeys the componentwise perturbation bound $d(\\tilde m,m)\\le 2\\omega\\gamma\\varepsilon$ for perturbations that preserve the stochastic constraints $1^T a=1-\\alpha$ and $1^T \\mathcal{P}_{(1)}=\\alpha 1^T_{n^2}$, where $d$ is the componentwise distance $d(\\tilde x,x)=\\max_i |\\tilde x_i-x_i|/|x_i|$; here $\\omega$ is defined through a bounded partial inverse $S$ of $R_m^T$ and does not diverge as $\\alpha\\to 1/2$, unlike $R_m^{-1}$. Second, for $\\alpha>1/2$, Newton's limiting accuracy is $u\\|\\lvert R_{x^*}^{-1}\\rvert x^*\\|+o(u)$, replacing the classical $u\\|R_{x^*}^{-1}\\|\\|x^*\\|$; numerical experiments confirm that the smaller quantity tracks the observed stagnation. The same analysis yields GTH-based subtraction-free Newton and block-Jacobi algorithms that compute the minimal solution with componentwise accuracy near the singularity.","pith_inferences":["Editorial inference: the decomposition $M^{-1}=R+S$ is effectively a pseudoinverse on the zero-sum subspace, so it could produce condition-number-free componentwise bounds for other stochastic-structure problems, such as ordinary PageRank or Perron vectors of column-stochastic matrices, whenever data are renormalized after perturbation.","Editorial inference: the paper's experiments note that the perturbation bound seems to hold for stochastic solutions with $\\alpha>1/2$ even though the proof covers minimal solutions; a targeted test in this regime could turn that numerical observation into a theorem.","Editorial inference: a practical takeaway for implementers is to stop Newton-type iterations on a componentwise residual, since the subtraction-free residual $r=\\alpha \\mathcal{P}h^2$ makes the relative error in small entries the natural cost function."],"forward_implications":["Near $\\alpha=1/2$, the minimal solution can be computed with componentwise accuracy by the Newton-GTH and block-Jacobi-GTH algorithms even though the Jacobian is ill-conditioned.","Under stochastic-normalization-preserving perturbations, errors on very small entries of the minimal solution are not amplified by the condition number of $R_m$.","For $\\alpha>1/2$, the stagnation level of Newton's method is predicted by $u\\|\\lvert R_{x^*}^{-1}\\rvert x^*\\|$, so small solution entries do not necessarily pollute the computation as much as a normwise analysis suggests.","The partial-inverse argument applies to general quadratic vector equations of the form $x=a+Bx^2$ with $\\rho(Bm:+B:m)<1$, giving componentwise bounds beyond the PageRank setting."],"supporting_citations":[{"why":"Introduces the multilinear PageRank problem and the Newton and fixed-point iterations studied here.","marker":"[9]"},{"why":"Establishes existence of the minimal solution, the M-matrix property of R_m, and monotone convergence.","marker":"[16]"},{"why":"Supplies the entrywise perturbation bound for inverses of M-matrices and the GTH variant used in the algorithms.","marker":"[2]"},{"why":"Provides the GTH algorithm's relative-error accuracy that the subtraction-free solvers rely on.","marker":"[15]"},{"why":"Introduces the vector y=R^{-1}a and the componentwise parameter kappa used to derive the bounds.","marker":"[21]"},{"why":"Is the classical Newton limiting-accuracy theorem that Theorem 6.1 sharpens.","marker":"[20]"},{"why":"Documents the non-Lipschitz behavior and possible disappearance of stochastic solutions for alpha>1/2, justifying the separation into two regimes.","marker":"[13]"}],"fun_headline_variants":["Componentwise stable PageRank even at alpha=1/2","Newton accuracy for multilinear PageRank beats Jacobian bounds","Subtraction-free Newton tames PageRank singularity","Multilinear PageRank: stable beyond classical limits","Partial inverse rescues PageRank near singularity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes the tensor's underlying graph stays strongly connected near $\\alpha=1/2$ (so the partial inverse $S$ stays bounded) and that the minimal solution has no zero entries; if the graph becomes reducible, the claimed finite bound can become vacuous.","fun_headline_variants_meta":{"raw":{"variants":["Componentwise stable PageRank even at alpha=1/2","Newton accuracy for multilinear PageRank beats Jacobian bounds","Subtraction-free Newton tames PageRank singularity","Multilinear PageRank: stable beyond classical limits","Partial inverse rescues PageRank near singularity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000163,"raw_usage":{"total_tokens":1270,"prompt_tokens":999,"completion_tokens":271,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":615,"completion_tokens_details":{"reasoning_tokens":196}},"tokens_in":615,"tokens_out":271,"duration_ms":2772,"temperature":1.0,"reasoning_tokens":196,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:53:28.680649+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a tensor with two disconnected blocks, set $\\alpha$ extremely close to $1/2$, perturb $\\mathcal{P}$ and $v$ by a zero-sum componentwise perturbation of size $\\varepsilon$, and compare the observed $d(\\tilde m,m)$ with $2\\omega\\gamma\\varepsilon$: if $\\omega$ diverges or the inequality fails, the irreducibility support condition is load-bearing.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the multilinear PageRank problem and the Newton and fixed-point iterations studied here."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the entrywise perturbation bound for inverses of M-matrices and the GTH variant used in the algorithms."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the GTH algorithm's relative-error accuracy that the subtraction-free solvers rely on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the vector y=R^{-1}a and the componentwise parameter kappa used to derive the bounds."},{"cited_title":"Tisseur , Newton’s method in floating point arithmetic and iterative refinement of generalized eigen- value problems , SIAM J","cited_arxiv_id":null,"evidence_quote":"Is the classical Newton limiting-accuracy theorem that Theorem 6.1 sharpens."},{"cited_title":"Meini and F","cited_arxiv_id":null,"evidence_quote":"Documents the non-Lipschitz behavior and possible disappearance of stochastic solutions for alpha>1/2, justifying the separation into two regimes."}],"review_version":1}