{"id":"7fba13b7-054e-4556-96e7-efcd8bb91ac9","arxiv_id":"2508.21506","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The rate of change of a graph's Kemeny constant when an edge weakens gives an always-positive, cut-edge-safe edge centrality, and its unweighted version also scores non-edges for link prediction.","lead":"This paper defines directional derivatives of Kemeny's constant, the average random-walk travel time in a graph, and uses them to score the importance of every edge, including edges whose removal would split the graph. Because the same scoring also ranks missing edges, the authors apply it to road networks and to predicting new collaborations in a co-authorship network.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Non-edge score is a formal derivative along a non-stochastic direction; the link-prediction claim is unvalidated and load-bearing for the advertised application.","rationale":"I re-derived the central identities: Cor. 1 follows from the Sherman-Morrison formula applied to Spq(t) = S - t a_pq w_pq w_pq^T, and Thm. 2 follows by applying the same formula to Spq = S - a_pq w_pq w_pq^T. Positivity is immediate from S^{-1} D S^{-1} being symmetric positive definite. The cut-edge case is legitimate for the weighted measure because for 0 < t < 1 the loop-compensated graph remains connected and the formula is finite. The non-edge/unweighted case, however, is a formal extrapolation: although P + t D^{-1} w_pq w_pq^T preserves row sums, for a_pq = 0 it contains negative transition probabilities and leaves the set of stochastic matrices. Thus ¯μ(p,q) is not the derivative of Kemeny's constant under any graph perturbation that adds or removes the non-edge. All link-prediction claims depend on the unproved heuristic that low ¯μ means a future collaboration is likely; the evidence in Section 6 is anecdotal and lacks a baseline. This is a genuine load-bearing concern for the advertised application, but it does not undermine the core mathematical contribution. The factor-of-two errors identified by the reader should be corrected, but they are not the main issue. Since the reader already returned CONDITIONAL, my assessment does not change the verdict: the paper should be revised to correct the secondary errors and either validate or substantially soften the link-prediction claim.","tokens_in":17818,"tokens_out":11601,"duration_ms":122496,"concrete_test":"Run a temporal link-prediction experiment on the netscience collaboration network: restrict to the largest connected component with edges up to time T, compute ¯μ for every non-edge, and score precision@k and AUC for edges first appearing in (T, T+Δ]. Compare against Jaccard, Adamic-Adar, resource allocation, and common-neighbour indices. If ¯μ does not match or beat these baselines on the held-out split, the Section 6 link-prediction claim is unsupported. As an internal sanity check, compare the sign of ¯μ with the sign of the actual change κ(G + ε{p,q}) − κ(G) for a sample of non-edges; the paper should explain the expected sign relation before presenting ¯μ as a link predictor.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central algebraic identities (Cor. 1 and Thm. 2) are sound: for an existing edge, Ppq(t) = D^{-1}(A + t a_pq w_pq w_pq^T) is a stochastic matrix for 0 ≤ t ≤ 1, and the Sherman-Morrison calculation giving μ = a_pq β(p,q) is correct. Positivity follows from the positive definiteness of S^{-1} D S^{-1}. The vulnerability is the non-edge score. When a_pq = 0, the unweighted path P + t D^{-1} w_pq w_pq^T does not correspond to any graph or Markov chain: A + t w_pq w_pq^T has negative off-diagonal entries, so ¯μ(p,q) is not the derivative of Kemeny's constant under any edge-insertion process. It is an algebraic derivative of an extended Kemeny function. The link-prediction interpretation ('low ¯μ means probable future collaboration') is therefore a heuristic, supported only by hand-checking 3 of 10 top predictions in one collaboration network, with no temporal split, no AUC/Precision@k evaluation, and no comparison against the common-neighbour baselines listed in the same section. If that heuristic fails, the non-edge centrality is merely a positive definite quadratic form on pairs, not a link predictor. The factor-of-two errors in Thm. 3 / Cor. 3 and in eq. (3.7) are real but secondary; they do not affect Cor. 1 / Thm. 2.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces two directional derivatives of Kemeny's constant for edges and non-edges of an undirected weighted graph: a weighted derivative μ(p,q) and an unweighted derivative μ̄(p,q). The central algebraic results are: μ(p,q)=a_pq β(p,q), where β(p,q)=w_pq^T S^{-1} D S^{-1} w_pq with S = L + dd^T/‖d‖_1; the positivity of β, including for cut-edges and for non-edges; the relation c(p,q)=μ(p,q)/(1−a_pq w_pq^T S^{-1} w_pq) to the Altafini et al. centrality; an algorithm based on Cholesky factorization; explicit formulas for one-path graphs; and applications to road-network centrality, link prediction, and a global sensitivity measure ζ(G). The main identities (Corollary 1 and Theorem 2) are self-contained and appear correct. However, several secondary but stated results contain factor-of-two errors, and the link-prediction application is supported only by anecdotal evidence.","tokens_in":18003,"tokens_out":7000,"duration_ms":69997,"significance":"If the central identities are correct, the paper makes a useful contribution: μ(p,q) is a universally defined, always-positive edge centrality that avoids the cut-edge singularities and numerical cancellation of the measure in [3], and the closed form via S^{-1}DS^{-1} is parameter-free and directly computable. The connection to the existing centrality of [3] is elegant, and the proposed algorithm appears to yield substantial speedups on large road networks. The unweighted measure μ̄(p,q) gives a positive score to every pair of vertices, which is a potentially valuable algebraic heuristic for link prediction. That said, the advertised link-prediction application is not yet established: the derivative for non-edges is a formal extrapolation along a non-stochastic direction, and the empirical validation is minimal. The factor-of-two errors in Theorem 3 and Eq. (3.7) are real and must be corrected before the paper can be accepted.","major_comments":[{"comment":"The formula for ζ(G) is off by a factor of 2. Since μ̄(p,q) = (e_p−e_q)^T M (e_p−e_q) with M = S^{-1}DS^{-1}, summing over all ordered pairs gives Σ_{p,q} μ̄(p,q) = 2n tr(M) − 2 1^T M 1, not n tr(M) − 1^T M 1. Thus ζ(G) should be [2n tr(M) − 2 1^T M 1]/n^2. This error propagates to Figure 6, where the reported values and the comparison across graph families are affected.","section":"§3.2, Eq. (3.7)"},{"comment":"Theorem 3 and Corollary 3 each contain a factor-of-two error. On the two-node graph with a single edge of weight 1, direct computation gives the filtered centrality c_F = 1/2, while Theorem 3 gives c_F = 1. The coefficient in Theorem 3 should be 1 rather than 2, and the bounds in Corollary 3 should have 1/a_pq rather than 2/a_pq. This also affects the comparison with [3] in Section 6 and any use of c_F.","section":"§3, Theorem 3 and Corollary 3"},{"comment":"The unweighted derivative for a non-edge, a_pq = 0, is taken along D^{-1}w_pq w_pq^T, which has negative off-diagonal entries; P + tD^{-1}w_pq w_pq^T is not a stochastic matrix of any graph. Hence μ̄(p,q) is an algebraic derivative of an extended Kemeny function, not the derivative under an edge-insertion process. The paper does not state this distinction. The link-prediction claim in the abstract and conclusions ('low μ̄ means probable future collaboration') is then validated only by hand-checking 3 of the top 10 predicted pairs in one collaboration network, with no temporal split, no AUC/Precision@k evaluation, and no comparison against the common-neighbour baselines mentioned in the same section. This is insufficient support for a central advertised application. The authors should either supply a quantitative evaluation or substantially soften the link-prediction interpretation.","section":"§3 (definition of μ̄) and §6 (link prediction)"}],"minor_comments":[{"comment":"The notation in (4.6), \"w_pq = (w_pq)_{i=1,\\dots,n-1}\", is confusing because the same symbol is used for the full vector and its first n−1 components. Suggest using a different symbol, e.g., ̂w_pq.","section":"§4, Algorithm 1"},{"comment":"The matrices of centrality values are printed with many digits and are hard to read. A heatmap with a color scale, or a smaller number of displayed digits, would improve readability.","section":"§6, Figure 4"},{"comment":"The text states that correlations are 'as expected' because the Kemeny derivative is sorted oppositely, but the reported correlations are only pairwise; no statistical significance or ranking metrics are given. This is acceptable as exploratory, but it should be labeled as such.","section":"§6, Table 1 and Figure 5"},{"comment":"The formula for μ(q,q+1) is stated for q=1,\\dots,n−1, but the notation σ_{q−1} and λ_{q−1} requires q≥1; this is implicit but could be made explicit.","section":"§5, Theorem 4"},{"comment":"The phrase 'it is numerically stable since its computation avoids cancellation' is plausible but not demonstrated with a rounding-error analysis; a brief justification or reference would help.","section":"§1"}],"recommendation":"major_revision","confidential_remarks":"The central contribution of the paper (Corollary 1 and Theorem 2) is sound and valuable, and the computational improvements over the earlier measure are real. However, the factor-of-two errors in Theorem 3, Corollary 3, and Eq. (3.7) are concrete and need correction, and the link-prediction application is overclaimed relative to the evidence. The overlapping-author references [3], [8], [9] provide background results but do not appear to create circularity in the main derivation. I would be willing to assess a revised version that fixes the formulas and either strengthens or appropriately qualifies the link-prediction claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core of this paper is sound and worth engaging with. The directional derivative formulas for Kemeny's constant, mu(p,q) = a_pq * beta(p,q) and mu-bar(p,q) = beta(p,q), are derived cleanly via Sherman-Morrison, and the positivity for all edges including cut-edges is a genuine improvement over the regularized/filtered measures in [3]. The identity in Theorem 2 connecting mu to the Altafini centrality is correct, and the one-path closed form is elegant. The banded algorithm is a real practical contribution: it computes the measure without forming the inverse of the modified Laplacian, and the complexity analysis is careful.\n\nThe soft spots are real but mostly secondary. Theorem 3, Corollary 3, and eq. (3.7) each carry a factor-of-two error. I verified the two-node case: c_F should be 1/2, not 1, and the sum in the sensitivity formula needs a factor 2. These errors do not touch Corollary 1 or Theorem 2, but they are advertised in the abstract and used in the figures, so they must be fixed before the paper appears.\n\nThe non-edge interpretation is the weakest conceptual step. For a non-edge, the direction D^{-1} w_pq w_pq^T does not correspond to any Markov chain or graph perturbation; mu-bar(p,q) is an algebraic derivative of an extended Kemeny function. That is fine as a definition, but calling it a link-prediction score is a heuristic. The evidence in Section 6 is thin: three of ten top predictions hand-checked in one network, no temporal split, no AUC or Precision@k, no baselines beyond correlation tables. The road-network comparison is mostly qualitative, and the claim of a \"more definite ranking\" rests on differences under 0.3% after normalization. None of this invalidates the algebra, but it should be labeled as a preliminary observation, not a validation.\n\nThe paper deserves a serious referee. The central identities are correct, the cut-edge universal definition is a useful contribution, and the algorithm is solid. A careful revision should fix the factor-of-two errors, clarify the non-edge direction as an extrapolation, and either strengthen the link-prediction experiment or soften the claim. I would send it to review.","headline":"Kemeny derivative centrality is a real result with correct core identities; two factor-of-two errors and a thin link-prediction section need fixing before publication.","tokens_in":18730,"tokens_out":1245,"would_cite":true,"duration_ms":14179,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","15B51","60J20","65F05","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that the directional derivative of Kemeny's constant, expressed through a rank-one-modified graph Laplacian, gives a positive, finite importance score for every edge—including cut-edges—and its unweighted version gives pos","keywords":["Kemeny constant","directional derivative","edge centrality","cut edges","link prediction","graph Laplacian","random walk","sensitivity measure"],"falsifier":"Take a network whose future links are known, compute β(p,q) for all non-edges, and compare precision at the top of the ranking against Jaccard and Adamic-Adar baselines; if the top-scoring non-edges are not future links at least as often as the baselines, the link-prediction interpretation is not supported.","tokens_in":17528,"feed_emoji":"🔗","tokens_out":10396,"duration_ms":98798,"temperature":0.7,"pith_summary":"This paper proposes using the directional derivative of Kemeny's constant—the average time for a random walk to travel between two randomly chosen vertices—as a measure of an edge's importance. It proves that this derivative has a closed form involving the inverse of a modified graph Laplacian, and that it is finite and positive for every edge, including cut-edges, where earlier finite-difference measures either diverge or need special filtering. The same expression, in its unweighted form, assigns a positive score to every non-edge, which the authors use for link prediction. A related theorem ties the new derivative to an earlier edge-centrality measure, explaining why the two largely agree while the new one avoids regularization and numerical cancellation. If correct, the paper supplies one uniform computation for ranking both existing edges and candidate future links.","feed_headline":"One derivative formula ranks every edge by Kemeny's constant","feed_subtitle":"The unweighted version also scores non-edges, turning the same computation into link prediction.","key_machinery":"The load-bearing object is the quadratic form β(p,q) = w_pq^T S^{-1} D S^{-1} w_pq, with w_pq = e_p - e_q, D = diag(d), and S = L + dd^T/||d||_1, the graph Laplacian plus a rank-one term that makes it invertible. This form is the unweighted directional derivative of Kemeny's constant, and multiplied by the edge weight a_pq it is the weighted derivative. It works through the rank-one update S - t a_pq w_pq w_pq^T: applying the inverse-update formula to the trace expression for Kemeny's constant turns the perturbed Kemeny constant into a rational function of t whose first derivative is β(p,q), with positivity following from positive definiteness. Because S is invertible even when {p,q} is a cu","core_discovery":"The central discovery is that the derivative of Kemeny's constant along an edge is not just a formal object but a computable, universally positive quantity. Writing w_pq = e_p - e_q, S = L + dd^T/||d||_1, and D = diag(d), the paper proves that the weighted directional derivative is µ(p,q) = a_pq · w_pq^T S^{-1} D S^{-1} w_pq and the unweighted derivative is µ̄(p,q) = w_pq^T S^{-1} D S^{-1} w_pq. Because S is invertible for every connected graph, both quantities are finite; the quadratic form is positive for every pair p ≠ q, including cut-edges and non-edges. The paper further proves that for non-cut-edges the earlier finite-difference measure of [3] equals µ(p,q) divided by 1 - a_pq w_pq^T","pith_inferences":["Since β(p,q) = ||D^{1/2} S^{-1}(e_p - e_q)||^2, the non-edge scores form a squared Euclidean distance between vertices in the metric induced by S^{-1} D S^{-1}; this suggests triangle-inequality-based shortcuts and a direct connection to resistance-like measures.","The identity µ(p,q) = a_pq β(p,q) means edge importance scales linearly with weight while β itself is weight-free; a natural testable extension is to use β alone as a scale-free ranking that does not over-prioritize heavy edges.","The global sensitivity measure could be used as a design objective: among candidate edge additions, choose the one that most reduces the sensitivity of Kemeny's constant, a computation that can be done from a single inverse matrix; the paper does not run this optimization.","A held-out-edge benchmark with AUC and precision-at-k against common-neighbour indices would establish how broadly the non-edge scores transfer, beyond the anecdotal checks reported."],"forward_implications":["Because µ(p,q) = a_pq β(p,q) is positive and finite for every edge, one formula and one algorithm replace the earlier three-way case split for ordinary edges, regularized cut-edges, and filtered cut-edges.","Because β(p,q) is well defined for all pairs, the same matrix S^{-1} D S^{-1} yields a ranking of all non-edges, so link prediction no longer requires common neighbours to assign a nonzero score.","Theorem 2 gives c(p,q) = µ(p,q) / (1 - a_pq w_pq^T S^{-1} w_pq) on non-cut-edges, so the new derivative and the earlier finite-difference measure agree up to an edge-dependent factor there.","For one-path graphs, µ(q,q+1) = σ_{q-1}(1 - σ_{q-1}) / (λ_{q-1} π_{q-1}); with unit weights this becomes a parabola peaking near the middle edge, quantifying which edge most hurts circulation if weakened.","The normalized average of β(p,q) over all pairs defines a single scalar sensitivity of Kemeny's constant, computable from the trace and total sum of S^{-1} D S^{-1} without enumerating edges."],"supporting_citations":[{"why":"defines the finite-difference edge measure c(p,q) with loop compensation, supplies the perturbation model for the derivative, and provides the formula that Theorem 2 extends.","marker":"[3]"},{"why":"gives the regularized and filtered cut-edge centralities and explicit one-path expressions that the new measure connects to and compares with.","marker":"[9]"},{"why":"introduced a directional derivative of Kemeny's constant for Markov chains, the conceptual source of the derivative definition used here.","marker":"[7]"},{"why":"establishes Kemeny's constant as the trace of a pseudoinverse, the algebraic starting point for the paper's expression.","marker":"[20]"},{"why":"supplies the definition of Kemeny's constant as the expected travel time between stationary-random destinations.","marker":"[21]"},{"why":"shows that the trace expression for Kemeny's constant is independent of the chosen vector v, used in equation (2.2).","marker":"[22]"},{"why":"provides the birth-death formula for Kemeny's constant on one-path graphs used to prove the explicit edge centrality in Theorem 4.","marker":"[8]"},{"why":"supplies the collaboration network dataset used for the link-prediction experiment.","marker":"[25]"},{"why":"defines the link-prediction problem and the common-neighbour-based baselines that the new measure is compared with.","marker":"[24]"}],"fun_headline_variants":["Edge centrality from Kemeny constant derivative","Derivative of Kemeny's constant measures edge importance","Rank edges and non-edges by Kemeny constant derivative","Derivative of Kemeny's constant gives edge and non-edge scores"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The edge-importance reading depends on the perturbation model in which weakening an edge always comes with compensating self-loops at its endpoints, and for non-edges it further assumes the formal unweighted derivative predicts real future links—a link-prediction assumption supported only by a few hand-checked examples.","fun_headline_variants_meta":{"raw":{"variants":["Edge centrality from Kemeny constant derivative","Derivative of Kemeny's constant measures edge importance","Rank edges and non-edges by Kemeny constant derivative","Derivative of Kemeny's constant gives edge and non-edge scores"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000714,"raw_usage":{"total_tokens":3043,"prompt_tokens":738,"completion_tokens":2305,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":482,"completion_tokens_details":{"reasoning_tokens":2246}},"tokens_in":482,"tokens_out":2305,"duration_ms":14924,"temperature":1.0,"reasoning_tokens":2246,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T14:21:40.254756+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a network whose future links are known, compute β(p,q) for all non-edges, and compare precision at the top of the ranking against Jaccard and Adamic-Adar baselines; if the top-scoring non-edges are not future links at least as often as the baselines, the link-prediction interpretation is not supported.","supporting_citations":[{"cited_title":"Altafini, D","cited_arxiv_id":null,"evidence_quote":"defines the finite-difference edge measure c(p,q) with loop compensation, supplies the perturbation model for the derivative, and provides the formula that Theorem 2 extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the regularized and filtered cut-edge centralities and explicit one-path expressions that the new measure connects to and compares with."},{"cited_title":"Berkhout and B","cited_arxiv_id":null,"evidence_quote":"introduced a directional derivative of Kemeny's constant for Markov chains, the conceptual source of the derivative definition used here."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"establishes Kemeny's constant as the trace of a pseudoinverse, the algebraic starting point for the paper's expression."},{"cited_title":"Kemeny and J","cited_arxiv_id":null,"evidence_quote":"supplies the definition of Kemeny's constant as the expected travel time between stationary-random destinations."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"shows that the trace expression for Kemeny's constant is independent of the chosen vector v, used in equation (2.2)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the birth-death formula for Kemeny's constant on one-path graphs used to prove the explicit edge centrality in Theorem 4."},{"cited_title":"Finding community structure in networks using the eigenvectors of matrices","cited_arxiv_id":"physics/0605087","evidence_quote":"supplies the collaboration network dataset used for the link-prediction experiment."},{"cited_title":"Liben-Nowell and J","cited_arxiv_id":null,"evidence_quote":"defines the link-prediction problem and the common-neighbour-based baselines that the new measure is compared with."}],"review_version":1}