{"id":"8104e1e3-d672-4de1-a47e-fd50c4378366","arxiv_id":"2501.10745","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A two-level gradient-flow algorithm computes the minimal Frobenius-norm perturbation that makes the top m eigenvector-centrality entries coalesce.","lead":"This paper finds the smallest change to a network's edge weights that makes its top eigenvector-based centrality scores tie, turning the ranking into a tie. That 'robustness radius' tells users whether a centrality ranking is trustworthy or easy to flip.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The abstract's global-optimality claim is unsupported: §3.3 concedes the two-level method yields only local minima and an upper bound on ϱ_m, so ε* need not equal the robustness radius; Lemma 5.1's fixed-index gradient adds a second unproven assumption.","rationale":"The reader's CONDITIONAL verdict is appropriate. The paper develops a nontrivial two-level method with explicit gradient formulas, a low-rank characterization, and competitive experiments; these are real contributions. My stress test finds that the strongest advertised claim—global optimality of the returned perturbation and equality of ε* with ϱ_m(G)—is not established and is contradicted by the paper's own Section 3.3. This is an internal inconsistency, not a disagreement with external consensus. The index-set assumption in Lemma 5.1 is a genuine second gap: the reported A27 m=4 experiment shows a top-set change, so the descent proof does not cover a case the authors themselves present. I do not think these flaws warrant rejection: the local-minimum/upper-bound version of the claim is clearly valuable, and the gaps are fixable (multistart, event handling, or an explicit problem reformulation with fixed index sets; code release would help verification).","tokens_in":22668,"tokens_out":11174,"duration_ms":124491,"concrete_test":"Take a small directed graph (e.g., the 4-node example of Section 2 or a random n=6 graph) and compute the true robustness radius ϱ_m by a global search over the free edge entries (fine grid or branch-and-bound) under the constraints of §3.1, for m=2. Then run the proposed two-level method from 20 random feasible initial directions E and record the smallest returned ε*. If any returned ε* is strictly larger than the global minimum, or if results depend on initialization, the abstract's claim that the algorithm 'produces the optimal perturbation' is false; if all starts return the global value, the claim still lacks a proof, but the practical gap is not demonstrated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—that the algorithm produces the smallest-Frobenius-norm perturbation and hence ε* = ϱ_m(G)—is contradicted by the paper's own §3.3. There the authors state that 'in general we cannot be sure to compute global optima, but only to globally converge to local optima, which means that the final computed matrix provides an upper bound to the solution of (8).' Since (8) defines ϱ_m only when F_ε(E(ε)) is the true global minimum over unit-norm, pattern-preserving E, a locally minimized branch can make the returned ε* strictly larger than ϱ_m(G). No global optimality certificate, convexity argument, or uniqueness result is supplied. A second, independent weakness is in Lemma 5.1: the proof of (16)–(17) differentiates v_{i_k}(t) with i_k treated as constant, whereas the lemma defines i1,...,im as the current top-m indices of v(t). If the top-m set changes along E(t), F_ε is continuous but not differentiable at the switch, formula (16) is not the gradient of the actual functional, and Theorem 5.1's monotonicity does not follow. The paper's own Example 1 (A27, m=4) exhibits such a change—node 109 replaces node 29 in the top set—so the assumption is not merely hypothetical. Individually, either issue would force weakening the abstract; together they leave the robustness-radius interpretation of the computed ε* unproven. The numerical experiments may still demonstrate a useful heuristic, but not the stated optimality.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the robustness of eigenvector centrality rankings with respect to weighted perturbations that preserve the graph's sparsity pattern. It defines a robustness radius ϱ_m(G) as the minimal Frobenius-norm perturbation that makes the m largest entries of the Perron eigenvector coalesce, proposes a two-level algorithm (an inner constrained gradient flow that minimizes a dispersion functional for a fixed perturbation norm, and an outer Newton-bisection that seeks the minimal such norm), derives an explicit structured gradient formula via first-order eigenvector perturbation theory, shows that stationary points have a low-rank structure, and reports numerical experiments on a water-network graph and on a large sparse graph. The abstract claims global optimality of the resulting perturbation, while Section 3.3 concedes that only local optima are guaranteed and that the computed matrix provides an upper bound to the problem.","tokens_in":22979,"tokens_out":9497,"duration_ms":93498,"significance":"The problem is well motivated and the paper contains several useful contributions: a clean formulation of the nearness problem, a closed-form gradient that avoids numerical differentiation, a characterization of stationary points as projections of low-rank matrices, a practical inner-outer algorithm that compares favorably with generic constrained optimization in the reported examples, and reproducible-looking experiments on realistic graphs. If the global-optimality gap were closed, or the claims appropriately weakened, the robustness radius would be a valuable addition to the network-sensitivity literature. The derivation of the gradient and the low-rank reduction are the strongest parts of the manuscript.","major_comments":[{"comment":"The Abstract states that the algorithm produces 'the optimal perturbation (i.e., the one with smallest Frobenius norm)' causing coalescence, but Section 3.3 ('Existence of local minima') explicitly says that 'in general we cannot be sure to compute global optima, but only to globally converge to local optima, which means that the final computed matrix provides an upper bound to the solution of (8).' These two statements are inconsistent. Since (8) defines the robustness radius as the infimum over all admissible E, a locally minimizing branch can make the returned ε* strictly larger than ϱ_m(G). No global optimality certificate, convexity argument, or uniqueness proof is supplied. The Abstract and the discussion in Sections 3.3 and 8 should be revised to present the computed quantity as an upper bound, or the claimed global optimality must be proved.","section":"Abstract and Section 3.3"},{"comment":"Lemma 5.1 derives the derivative d/dt F_ε(E(t)) under the convention that i1,...,im are the indices of the m largest entries of v(t) at each t. In the proof, the identities (17) differentiate v_{i_k}(t) while treating i_k as constant. If the set of top-m indices changes along the path E(t), F_ε is continuous but not differentiable at the switching point, and formula (16) is not the gradient of the actual top-m dispersion functional. The paper's own Example 1 (Section 7.1, m=4) exhibits such a change: node 109 enters the top set and node 29 leaves it. No mechanism for detecting or handling these index switches is described. Consequently, Theorem 5.1's monotonicity statement is not established for the full flow, and the 'gradient descent' interpretation of (25) is not rigorous in general. The authors should either restrict the flow to intervals where the index set is constant and add a switch-detection/reinitialization strategy, or prove that the formula remains valid in a suitable weaker sense.","section":"Lemma 5.1, Eqs. (16)-(17)"},{"comment":"Lemma 6.1 concludes f'(ε) = -||G_ε(E(ε))||. The proof shows f' = ⟨G,E⟩ and then invokes 'property no. 3' of Theorem 5.1, which says E ∝ G. Since ||E|| = 1, this only gives ⟨G,E⟩ = ±||G||; the sign is not determined. The negative sign would follow if f(ε) were the value of a global minimum that is non-increasing in ε, but neither global optimality nor monotonicity of f has been established. If the sign is wrong, the Newton step (39) in the outer iteration points in the wrong direction. This is load-bearing for the outer iteration's correctness and for the claim that the computed root is the minimal ε. The authors should provide a correct proof of the sign, or use a derivative-free outer iteration.","section":"Lemma 6.1, Eqs. (37)-(38)"}],"minor_comments":[{"comment":"The display 'eεm − →arg min ε>0 F_ε(E(ε)) = 0' is not standard mathematical notation; please rewrite it as a precise optimization or root-finding statement.","section":"Equation (8)"},{"comment":"The column 'fc(εk)' is not defined in the caption; it appears to denote F^c_ε(E_k), but this should be spelled out.","section":"Table 1"},{"comment":"The statement that 'we can prove' a one-to-one correspondence of stationary points and local convergence of the rank-1 ODE, followed by 'we omit a full derivation', is not sufficient for a journal paper unless the omitted result is readily available in [18]; please either include the proof or mark the statement explicitly as a conjecture with numerical support.","section":"Section 5.6"},{"comment":"The percentages quoted for the perturbation norms appear to be off by several orders of magnitude: for a matrix with ||A||_F = 1, ε2 = 0.00383633 is about 0.38%, not 0.00008%, and ε5 = 0.0161 is about 1.6%, not 0.00016%. Please correct these values or clarify what they are relative to.","section":"Section 7.2"},{"comment":"The sentence 'It is interesting to note the the node 109 was not at the highest rank but replaced the node 29 after the perturbation' contains a typographical error ('the the') and also demonstrates the index-switching issue discussed above; please correct the typo and comment on the implications for the fixed-index assumption in Lemma 5.1.","section":"Section 7.1, Example 1"},{"comment":"The set Ω in (4) is defined using the indices i1,...,im of the m largest entries of u, but it would be clearer to specify how ties are handled, especially because the numerical examples intentionally create ties at coalescence.","section":"Section 3.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely to be of interest to the numerical linear algebra and network-science communities. The main concerns are internal consistency (Abstract vs. Section 3.3) and two unproven assumptions in the theoretical core (the fixed-index assumption in Lemma 5.1 and the sign determination in Lemma 6.1). The numerical experiments are encouraging but not sufficient to support global optimality. I recommend major revision; the authors should be able to fix the issues by weakening the claims, adding switch handling in the inner iteration, and correcting the derivative sign proof."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: this is a real contribution to a niche but useful problem—how fragile is eigenvector centrality ranking, and what is the nearest graph that makes the top m ambiguous. The authors formulate a new structured matrix nearness problem, derive explicit gradient formulas via first-order perturbation theory, and uncover a low-rank (rank-1/rank-2) structure in the stationary points. The numerical experiments on realistic graphs (A27, nopoly) are convincing: the method converges quickly and beats fmincon by orders of magnitude in CPU time. That part is solid.\n\nThe soft spots are real, though, and they sit precisely where the authors overclaim. The abstract promises 'the optimal perturbation' with smallest Frobenius norm. Section 3.3 concedes the gradient-flow inner iteration only globally converges to local minima, so the computed ε* is an upper bound on ϱ_m(G), not the exact robustness radius. No global optimality certificate is supplied. That mismatch should be fixed by either proving global optimality (unlikely for this nonconvex problem) or systematically softening the claims in the abstract and text.\n\nThe second issue is the fixed-index assumption in Lemma 5.1. The proof differentiates F_ε(E(t)) treating the top-m indices as constant, but those indices are defined as the current top-m set. If the set changes along the path—and the paper's own Example 1 (m=4) shows node 109 replacing node 29—the functional is nonsmooth and formula (16) is not the gradient of the actual functional. The theorem's monotonicity conclusion doesn't follow without handling index switches. This is also addressable: one can add an explicit regularity assumption, or track switch events and restart the flow. As written, it's a gap in the theory, though the numerics suggest it doesn't break the method in practice.\n\nMinor: Lemma 6.1's proof is terse—the εE' term vanishes because E ∝ G at a minimizer, which is true but should be said. Also, no code or data is released, so the CPU-time claims and the fmincon comparison are hard to reproduce. That's a normal request for a numerical paper.\n\nOverall: the core idea is good, the derivation is mostly sound, and the local-minimum algorithm is genuinely useful for sensitivity analysis and manipulation studies. The paper deserves a proper referee. I would send it out, but the referee should insist on resolving the local-global language and the index-set stability issue before publication. I would not cite the global optimality claim as is, but I would cite the algorithm and gradient formulas once cleaned up.","headline":"A useful local-minimum algorithm for a new eigenvector-centrality nearness problem, but the abstract's global optimality claim is not supported and the gradient theory has a fixed-index gap.","tokens_in":23539,"tokens_out":5025,"would_cite":false,"duration_ms":44527,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A60","05C50","15A42","47A55"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that the robustness of eigenvector-centrality rankings can be quantified by the smallest weight perturbation, preserving the graph's edge structure, that makes the top m centrality scores exactly equal, and proposes a…","keywords":["eigenvector centrality","Perron eigenvector","matrix nearness problem","robustness radius","structured eigenvalue optimization","graph perturbation","gradient flow","ranking sensitivity"],"falsifier":"Track which nodes occupy the top m positions during the inner gradient flow on a graph where the top set changes, as in the paper's own Example 1 with m=4, where node 109 enters the top set. If the dispersion functional $F_\\varepsilon$ ever increases along the numerically integrated flow at the moment the index set changes, the gradient formula no longer describes the true functional and the monotone-descent theorem fails; alternatively, run a global search over admissible unit-norm perturbations $E$ for the smallest $\\varepsilon$ with $F_\\varepsilon(E)=0$ and compare with the reported value, since any smaller $\\varepsilon$ found would disprove the claimed optimality.","tokens_in":22420,"feed_emoji":"📊","tokens_out":9771,"duration_ms":92070,"temperature":0.7,"pith_summary":"Eigenvector centrality ranks the nodes of a weighted graph by the entries of the Perron eigenvector of its adjacency matrix, and that ranking is only trustworthy if it survives realistic uncertainty in the edge weights. This paper tries to measure that trustworthiness directly: how far, in Frobenius norm, must the weights move, preserving the graph's edge structure, before the top m centrality scores become exactly equal and the ranking at the top turns ambiguous. The authors propose a two-level algorithm that alternates a constrained matrix gradient flow, which for a fixed perturbation size drives the spread of the top m scores to a minimum, with an outer one-dimensional search that shrinks the perturbation until the spread reaches zero. They derive an explicit formula for the gradient using first-order eigenvector perturbation theory, show that stationary perturbations have an underlying low-rank form, and demonstrate on sparse graphs with hundreds to ten thousand nodes that the approach is faster than generic constrained optimization. If the algorithm is correct, the computed perturbation size gives a robustness radius for the ranking, and the perturbing matrix itself identifies which edges are most able to change the ranking.","feed_headline":"A tiny weight tweak can make a graph's top ranks tie","feed_subtitle":"New algorithm finds the smallest such tweak, exposing fragile eigenvector-centrality rankings.","key_machinery":"The argument is carried by the dispersion functional $F_\\varepsilon(E)=\\frac{1}{2}\\sum_{k=1}^m (v_{i_k}(A+\\varepsilon E)-\\langle v\\rangle_m)^2$, which is zero exactly when the m largest entries of the Perron eigenvector are equal. The paper computes its structured gradient $G_\\varepsilon(E)$ by projecting the free gradient, built from the group inverse $(A+\\varepsilon E-\\lambda I)^\\#$ and rank-one outer products of the Perron eigenvector with the relevant coordinate vectors, onto the graph's edge pattern; this formula comes from first-order eigenvector perturbation theory. The inner iteration integrates the constrained gradient flow under the unit-Frobenius-norm and sparsity constraints, and the outer iteration uses the identity $f'(\\varepsilon)=-\\|G_\\varepsilon(E(\\varepsilon))\\|$ to run a Newton-bisection root find. At stationary points the perturbation is proportional to the projected gradient, which is a projection of a rank-one matrix in the directed case and of a rank-two symmetric matrix in the undirected case, and the paper exploits this low-rank structure computationally.","core_discovery":"The paper's central claim is that the robustness of an eigenvector-centrality ranking can be quantified by a structured matrix nearness problem: find the smallest Frobenius-norm change to the weighted adjacency matrix, keeping zero entries fixed and keeping the matrix nonnegative, such that the m largest entries of the Perron eigenvector coalesce. The proposed solution is a nested iteration: an inner constrained gradient system minimizes the dispersion functional $F_\\varepsilon(E)$ at fixed perturbation size $\\varepsilon$, and an outer Newton-bisection iteration finds the smallest $\\varepsilon$ for which that functional vanishes. The authors state that the algorithm produces the optimal perturbation, with the smallest Frobenius norm causing the coalescence, while also noting in Section 3.3 that the gradient-flow approach converges to local optima, so the computed value is in general an upper bound on the robustness radius $\\varrho_m(G)$. Numerical experiments on realistic sparse graphs report coalescence achieved by perturbations of about one percent or less of the normalized adjacency matrix, with the gradient flow far outperforming a standard constrained-optimization solver.","pith_inferences":["The same gradient-flow machinery could be applied to PageRank and Katz centrality by replacing the Perron eigenvector with the corresponding resolvent-based centrality vector; the paper notes the kinship of these measures but does not derive the analogous gradient or robustness radius.","One testable refinement is to make the inner iteration detect index switches, for example by checking whether the top m set has changed and restarting the flow with the updated set, since the paper's own Example 1 shows such switches do occur.","The robustness radius could be used as a ranking-confidence diagnostic: compare the radius to the estimated uncertainty in the edge weights, and if the radius is smaller, the top m order is not statistically distinguishable from ambiguous, a decision rule the paper does not spell out.","A randomized or rank-restricted variant of the gradient flow could extend the method to very large networks, since the extremizers are known to be projections of low-rank matrices."],"forward_implications":["For any weighted graph, the method yields a concrete robustness radius: a perturbation smaller than the computed value cannot make the top m eigenvector centralities tie, so a small radius signals that the ranking is fragile under weight noise.","The perturbing matrix found at the optimum reveals which edges have the strongest influence on the top of the ranking, since its largest entries are the weights whose adjustment most shrinks the gap.","Because the formulation only needs a nonnegative matrix, the same radius and closest-ambiguous-matrix construction apply to any dominant-eigenvector ranking, including those arising in population models, consensus dynamics, and economic input-output analysis.","For undirected graphs, the stationary perturbations are projections of rank-two symmetric matrices, which keeps the per-step cost dominated by one Perron eigenvector computation plus m solves of a bordered linear system, so large sparse graphs are tractable.","On the tested sparse graphs, the two-level gradient-flow method reached the coalescing perturbation in seconds to minutes, whereas a generic constrained-optimization solver required orders of magnitude more time and many more function evaluations."],"supporting_citations":[{"why":"Supplies the Perron-Frobenius theorem used as Theorem 3.1, guaranteeing the simple positive Perron eigenvalue and eigenvector that define eigenvector centrality.","marker":"[24]"},{"why":"Provides the first-order derivative formula for simple eigenvalues used in the perturbation-theory background of Section 4.","marker":"[14]"},{"why":"Supplies the first-order eigenvector derivative formulas stated as Theorem 4.3, from which the structured gradient in Lemma 5.1 is derived.","marker":"[29]"},{"why":"Provides the rank-one matrix differential equation framework used to exploit the low-rank structure of the stationary perturbations.","marker":"[18]"},{"why":"One of the low-rank matrix nearness approaches whose inner/outer iteration structure the proposed algorithm follows.","marker":"[15]"},{"why":"Related work assigning prescribed stationary distributions to sparse stochastic matrices, used as a comparison point for minimal structured perturbations.","marker":"[12]"},{"why":"Related work enforcing Katz and PageRank centrality scores via constrained optimization, the approach the paper compares against and whose coalescence idea it adapts.","marker":"[8]"},{"why":"Shows how to control eigenvector centrality rankings through minimal sets of controller nodes, a complementary manipulation problem the paper's edge-subset constraints can combine with.","marker":"[31]"},{"why":"Supplies the molecular-dynamics water-network graph used in Example 1 to test the algorithm on a realistic 710-node sparse graph.","marker":"[9]"}],"fun_headline_variants":["Smallest weight tweak that forces eigenvector centrality tie","Algorithm finds minimal weight change to tie graph rankings","Tiny edge-weight shifts can make centrality scores collide","Nudge weights to force a tie in graph importance rankings","Gradient flow finds minimal perturbation to break centrality order"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that the identities of the top m nodes do not change while the perturbation moves; if a new node enters the top m, the gradient formula no longer describes the true dispersion functional and the guaranteed descent can break.","fun_headline_variants_meta":{"raw":{"variants":["Smallest weight tweak that forces eigenvector centrality tie","Algorithm finds minimal weight change to tie graph rankings","Tiny edge-weight shifts can make centrality scores collide","Nudge weights to force a tie in graph importance rankings","Gradient flow finds minimal perturbation to break centrality order"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00056,"raw_usage":{"total_tokens":2727,"prompt_tokens":1079,"completion_tokens":1648,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":695,"completion_tokens_details":{"reasoning_tokens":1572}},"tokens_in":695,"tokens_out":1648,"duration_ms":14661,"temperature":1.0,"reasoning_tokens":1572,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T19:01:34.359978+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Track which nodes occupy the top m positions during the inner gradient flow on a graph where the top set changes, as in the paper's own Example 1 with m=4, where node 109 enters the top set. If the dispersion functional $F_\\varepsilon$ ever increases along the numerically integrated flow at the moment the index set changes, the gradient formula no longer describes the true functional and the monotone-descent theorem fails; alternatively, run a global search over admissible unit-norm perturbations $E$ for the smallest $\\varepsilon$ with $F_\\varepsilon(E)=0$ and compare with the reported value, since any smaller $\\varepsilon$ found would disprove the claimed optimality.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Perron-Frobenius theorem used as Theorem 3.1, guaranteeing the simple positive Perron eigenvalue and eigenvector that define eigenvector centrality."},{"cited_title":"Greenbaum, R.-C","cited_arxiv_id":null,"evidence_quote":"Provides the first-order derivative formula for simple eigenvalues used in the perturbation-theory background of Section 4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the first-order eigenvector derivative formulas stated as Theorem 4.3, from which the structured gradient in Lemma 5.1 is derived."},{"cited_title":"Guglielmi, C","cited_arxiv_id":null,"evidence_quote":"Provides the rank-one matrix differential equation framework used to exploit the low-rank structure of the stationary perturbations."},{"cited_title":"Guglielmi, D","cited_arxiv_id":null,"evidence_quote":"One of the low-rank matrix nearness approaches whose inner/outer iteration structure the proposed algorithm follows."},{"cited_title":"Gillis and P","cited_arxiv_id":null,"evidence_quote":"Related work assigning prescribed stationary distributions to sparse stochastic matrices, used as a comparison point for minimal structured perturbations."},{"cited_title":"Enforcing Katz and PageRank Centrality Measures in Complex Networks","cited_arxiv_id":"2409.02524","evidence_quote":"Related work enforcing Katz and PageRank centrality scores via constrained optimization, the approach the paper compares against and whose coalescence idea it adapts."},{"cited_title":"Nicosia, R","cited_arxiv_id":null,"evidence_quote":"Shows how to control eigenvector centrality rankings through minimal sets of controller nodes, a complementary manipulation problem the paper's edge-subset constraints can combine with."},{"cited_title":"Faccio, M","cited_arxiv_id":null,"evidence_quote":"Supplies the molecular-dynamics water-network graph used in Example 1 to test the algorithm on a realistic 710-node sparse graph."}],"review_version":1}