{"id":"84579aac-52ed-4d0b-8a0f-1f06d6cf5e82","arxiv_id":"1909.01076","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A link prediction score based on effective transition probabilities from isospectral matrix reductions is introduced, with a fast approximation and tests on social, technological, and natural networks.","lead":"The paper introduces a link prediction method that scores potential links by the probability that a random walk visits one node before returning to the other, computed with isospectral reductions. It works on directed, undirected, weighted, and unweighted networks, and the authors report competitive accuracy on several real-world networks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The advertised competitiveness rests on an empirical evaluation that may select the approximation parameter on the test data; until this is re-run with training-only model selection, the central claim is not established.","rationale":"The reader's overall CONDITIONAL verdict is appropriate, but I do not think the connectivity assumption is the most load-bearing concern: Section 8 explicitly acknowledges the strong-connectivity limitation, the test networks are selected to be (strongly) connected, and the l-step approximation remains defined even when the exact reductions fail. The weakest support for the central claim is the empirical evaluation: a single split, no error bars, unreported baseline parameters, and the apparent selection of l on test data. A concrete proof-level issue also exists in the Appendix: the proof of Proposition 4.3 states that each isoradial reduction I_{i,j}(M) is 'an irreducible row stochastic matrix' for arbitrary irreducible nonnegative M, which is false (for the matrix A in Example 4.4, I_{1,2}(A) has row sums 3 and 0.764, not 1). The proposition is likely repairable by invoking Theorem 3(b) directly instead of row stochasticity, so I do not make this the primary attack, but it reinforces that the paper needs careful revision. The proposed re-validation is the single check that would settle whether the empirical claim is real.","tokens_in":18191,"tokens_out":12996,"duration_ms":129001,"concrete_test":"Recompute Figures 4, 5, and 7 using a training-only model-selection rule: choose l by maximizing accuracy on a validation set carved out of the training edges (e.g., the last 10% by timestamp within the training split), then evaluate on the untouched test edges. Run this over at least 10 alternative temporal splits, report mean and standard deviation of accuracy, and tune all baseline hyperparameters (especially Katz β) by the same training-only procedure. If the Approximate ET advantage over baselines shrinks to within one standard deviation or disappears, the advertised competitiveness is an artifact of test-set tuning.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that effective transitions are 'competitive' is an empirical claim, and the experiments as reported cannot support it yet. Section 5.1 uses a single 80/20 temporal split with no error bars or significance tests, and the baseline predictors from Section 3 are used without reporting their parameters (e.g., the Katz parameter β, tie-breaking details for shortest path). More importantly, the approximation parameter l in Sections 6.2 and 7 is chosen separately for each network (l=3 for HepTh and Facebook, l=2 for Internet, Wikipedia, and the weighted Facebook network) without a rule that separates model selection from evaluation. Figure 6 sweeps l on a network and appears to pick the best l on the same data whose accuracy is then reported as the method's performance. If l is selected using the test edges, the reported 'often outperforming' accuracy is not an unbiased estimate of out-of-sample predictive skill. Additionally, the exact effective transition method requires the 80% temporal training subgraph to be (strongly) connected, but the paper never verifies this after the temporal split; if the training subgraph is not strongly connected, E(M) may not exist and the scores in Figures 3 and 7 cannot be the scores defined in Section 4.3. Either issue independently warrants a conditional verdict.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a link prediction method based on effective transitions, where the score of a potential link (i,j) is the probability that a random walk starting at i reaches j before returning to i. This score is computed via isoradial reductions of the network's transition matrix, yielding an effective transition matrix E(M) for general nonnegative matrices M. The authors prove structural properties of E(M) (nonnegativity, irreducibility, same leading eigenvector, scaled spectral radius), propose an l-step approximation E_l(M), and prove that it converges monotonically to E(M). They present empirical comparisons on several directed and undirected, weighted and unweighted networks, claiming competitiveness with standard link predictors. The appendix contains proofs of the main theorems.","tokens_in":18437,"tokens_out":2834,"duration_ms":29231,"significance":"If the empirical claims are confirmed, this is a useful contribution to link prediction: it provides a single score framework that naturally handles directed, weighted, and unweighted networks, a property few existing predictors have. The theoretical core is a genuine strength: the use of isoradial reductions to define transition probabilities is elegant, and the monotone-convergence result for the approximation is nontrivial. Unlike many heuristics, the score has a clear probabilistic interpretation and comes with a spectral rationale. The main risk is empirical: the reported competitiveness rests on a small, unvalidated experimental setup, so the central claim is not yet established. With a cleaned-up evaluation, the method could merit publication.","major_comments":[{"comment":"The approximation horizon l appears to be selected per network without a rule that separates model selection from evaluation: l=3 for HepTh and Facebook, l=2 for Internet, Wikipedia, and the weighted Facebook network. Figure 6 sweeps l on the smaller HepTh network and the text reports the best accuracy from this sweep; if l is chosen using test edges, the reported accuracies are not unbiased estimates of out-of-sample performance. Please re-run the experiments with l selected on the training portion only (or via nested cross-validation) and report results for all l values considered.","section":"§6.2, Figure 6"},{"comment":"The method's definition requires the graph to be (strongly) connected: Section 8 explicitly states that isoradial reductions can fail otherwise, and Proposition 4.3 relies on irreducibility. After temporally splitting each network into an 80% training and 20% test subgraph, the paper never verifies that the training subgraph is (strongly) connected. If a training subgraph is disconnected, the scores reported in Figures 3, 4, 5, and 7 are not the effective transition scores defined in Section 4. Please report connectivity checks for every training subgraph and state how any disconnected cases were handled.","section":"§5.1, Steps 1–3; §8"},{"comment":"The empirical support for the central 'competitive' claim is a single 80/20 temporal split per network with no error bars, no significance tests, and no variation across subsamples or edge-order permutations. The baseline predictors are also incompletely specified: the Katz parameter β is never reported, and tie-breaking for shortest-path scores is not described. This is insufficient to support the abstract's claim that the method 'often outperforms' standard predictors. Please add repeated splits, error bars, and a clear specification of all baseline parameters.","section":"§5.2, Figures 3–5"}],"minor_comments":[{"comment":"The text says 'remove any edges from the test set that involve nodes not included in the test set'; this should say 'not included in the training set.'","section":"§5.1, Step 2"},{"comment":"The derivation of r_ij is said to use 'Equation (10)', but the displayed formula is the isoradial reduction formula from Definition 3, Equation (8).","section":"Appendix, proof of Theorem 1"},{"comment":"The inequality in (17) displays an infinite sum over k, but P and Q are finite matrices and I^l_S(M) is defined by a finite sum to l; the proof should use finite sums to be consistent with Definition 5.","section":"Appendix, proof of Theorem 2, part (ii)"},{"comment":"The phrase 'We also, prove' contains an errant comma; it should read 'We also prove.'","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The theoretical framework is promising and the paper is likely publishable after the empirical evaluation is made rigorous. The main concern is the handling of the approximation parameter l and the unverified connectivity of the training subgraphs; both are fixable within the manuscript's scope rather than fundamental flaws. The paper also leans heavily on the authors' prior work for Theorem 3, but this is a normal and appropriate dependence."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a look. The paper introduces a link prediction score based on pairwise isoradial reductions of the transition matrix. The entry ε_ij is the probability of hitting j before returning to i, computed by reducing the matrix to a 2x2 block. That's a clean idea and, as far as the cited literature goes, new. The same score works for directed, undirected, weighted, and unweighted networks, which is genuinely useful. The l-step approximation with monotone convergence to the full score is a nice practical complement, and the spectral properties (nonnegative, irreducible, inherited leading eigenvector) are well chosen. If the empirical part held up, this would be a solid contribution to link prediction.\n\nThe empirical part does not hold up as written. The evaluation uses a single 80/20 temporal split, no error bars, no significance tests, and the baselines (Katz β, etc.) do not have their parameters reported. The bigger problem is that the horizon l is selected per network (l=3 for HepTh and Facebook, l=2 for Internet, Wikipedia, and the weighted network) without any description of a model-selection rule that separates training from test. Figure 6 sweeps l and appears to report accuracy on the same data used to pick the best l. That makes the 'often outperforming' claim unsubstantiated. The exact method also requires the training subgraph to be strongly connected; the paper never verifies that after the temporal split. These are fixable, but they are not cosmetic.\n\nThe mathematical core looks basically sound, though the appendix has several typos. The proof of Theorem 2(ii) writes an infinite series where the definition uses a finite one; the proof of Theorem 1 cites Equation (10) when it means the reduction formula; and the proof of Proposition 4.3 mislabels (iii)/(iv) and calls a general non-stochastic reduction row stochastic. None of these sink the results, but the appendix needs a careful rewriting.\n\nBottom line: this is a novel method worth a serious referee. The theory is plausible and the idea is interesting; the experiments need to be redone with proper validation, baseline reporting, and a check on connectivity. I would send it to review, not desk-reject, but I would make it clear that the empirical claims will only survive after a re-run.","headline":"The effective-transition score is a genuinely new link-prediction idea with a plausible theoretical core, but the experiments as written do not establish the claimed competitiveness.","tokens_in":18927,"tokens_out":7939,"would_cite":true,"duration_ms":76852,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62M20","90B15","15B51","05C81","60J10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A random-walk 'effective transition' score predicts links competitively on directed, undirected, weighted, and unweighted networks.","keywords":["link prediction","effective transitions","isoradial reductions","isospectral reductions","transition matrix","weighted networks","random walks","directed networks"],"falsifier":"Run the paper's 80/20 temporal split on a collection of strongly connected directed weighted networks and compare the effective-transition ranking of held-out edges with a random ranking: if its AUC is not above 0.5 while at least one standard predictor is, the competitiveness claim is refuted.","tokens_in":17999,"feed_emoji":"🔗","tokens_out":10804,"duration_ms":100450,"temperature":0.7,"pith_summary":"This paper introduces a link-prediction method based on effective transitions: the probability that a random walk starting at node $i$ reaches node $j$ before returning to $i$. The authors' central claim is that these probabilities, arranged in an effective transition matrix $E(M)$ built from pairwise isoradial reductions, produce link scores that are competitive with standard predictors and often outperform them. Unlike most predictors, the method applies to directed or undirected and weighted or unweighted networks alike, so one score function covers all four cases. The paper also proves structural properties of $E(M)$ and of an $\\ell$-step approximation that is cheaper to compute and, in the authors' experiments, frequently more accurate.","feed_headline":"Effective transitions predict links in nearly any network","feed_subtitle":"New scores from isospectral reductions match or beat common predictors; the fast approximation often wins.","key_machinery":"The load-bearing object is the isoradial reduction $I_S(M)=M_{SS}-M_{S\\bar S}(M_{\\bar S\\bar S}-\\rho(M)I)^{-1}M_{\\bar S S}$, a spectral-radius-preserving Schur complement over a node subset $S$. The effective transition matrix is assembled by computing this reduction for every pair $S=\\{i,j\\}$, reading the off-diagonal entries as eventual-transition scores, and summing the diagonal contributions as in Equations (9)/(10). The approximation replaces the inverse by a truncated Neumann series $\\sum_{k=0}^\\ell (\\rho(M)^{-1}M_{\\bar S\\bar S})^k$ restricted to nodes within distance $\\ell$ of both $i$ and $j$, which keeps the computation local and lowers the temporal complexity from $O(n^5)$ to $O(n^{2.373}+s^{2.373}n)$. This machinery turns a global random-walk quantity into pairwise scores while preserving the network's spectral structure, which is what lets the scores inherit the leading eigenvector and, for stochastic matrices, the stationary distribution.","core_discovery":"The central discovery is that the off-diagonal entries of a matrix $E(M)$ assembled from pairwise isoradial reductions of the network's transition matrix can serve as link-prediction scores. For a stochastic transition matrix $P$, the entry $\\varepsilon_{ij}$ is the probability that a random walk starting at $i$ reaches $j$ before returning to $i$, and the score ranks candidate edges by that probability. The paper proves that $E(M)$ is nonnegative and irreducible, shares its leading eigenvector with $M$, has spectral radius $(n-1)\\rho(M)$, and, when $M$ is row stochastic, yields a primitive stochastic matrix $S(M)=E(M)/(n-1)$ with the same stationary distribution as $M$. It further proves that the $\\ell$-step approximation $E_\\ell(M)$, obtained by truncating the Neumann expansion inside each reduction, converges monotonically to $E(M)$ as $\\ell\\to\\infty$. On social, technological, and information networks, the resulting scores match or beat standard predictors, including on directed and weighted networks.","pith_inferences":["The paper does not pursue it, but the spectral-preservation property suggests a principled coarse-graining: reducing a network to a subset of nodes while keeping the leading eigenvector could support approximate centrality computations on very large graphs.","The reported dependence of accuracy on $\\ell$ implies that the optimal $\\ell$ is itself a measurable network statistic—an effective link-formation horizon—that could be compared across datasets as a signature of how new edges appear.","A testable extension is to choose $\\ell$ adaptively per candidate pair rather than globally, since exact convergence only requires $\\ell$ to reach twice the network diameter; local values could cut the cost further with little loss in ranking quality."],"forward_implications":["One score function covers all four network types—directed or undirected, weighted or unweighted—so a practitioner does not need a separate predictor for each case.","The $\\ell$-step approximation makes the method feasible on large networks, with complexity $O(n^{2.373}+s^{2.373}n)$, and in the reported tests it often predicts more accurately than the exact effective-transition score.","Because $E(M)$ and $M$ share the same leading eigenvector, and because the scaled matrix $S(M)$ has the same stationary distribution as a stochastic $M$, rankings from effective transitions are consistent with the network's long-run random-walk behavior.","The value of $\\ell$ that maximizes accuracy gives a rough measure of the neighborhood size over which links tend to form, so the approximation doubles as a diagnostic for the network's growth mechanism."],"supporting_citations":[{"why":"Supplies the theory of isospectral reductions used to prove that pairwise reductions compute the effective transition probabilities.","marker":"[8]"},{"why":"Defines the Perron complement, the matrix transformation behind the isoradial reduction formula.","marker":"[19]"},{"why":"Establishes existence, nonnegativity, irreducibility, and spectral-radius preservation of isoradial reductions, used in Proposition 4.3.","marker":"[26]"},{"why":"Defines the link prediction problem and the standard baseline predictors the effective-transition scores are compared against.","marker":"[17]"},{"why":"Provides the spectral-radius bound for submatrices used in the proof that the l-step approximation converges.","marker":"[14]"},{"why":"Supplies the fast matrix multiplication algorithm behind the complexity bound of the approximation.","marker":"[16]"},{"why":"Supplies the HepTh coauthorship dataset used in the accuracy comparisons.","marker":"[1]"},{"why":"Supplies the Facebook wall-posts dataset used in the directed-network accuracy comparisons.","marker":"[2]"}],"fun_headline_variants":["Effective transitions: a new link predictor for any network","Link prediction via effective transitions beats common methods","Isospectral reductions power a fast, accurate link predictor","Effective transitions: better link prediction, often faster","New math predicts links: effective transitions outperform"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that the network is strongly connected—every node can reach every other node along directed paths—so the transition matrix is irreducible; if the graph is disconnected, the reductions that define the effective-transition scores can fail to exist.","fun_headline_variants_meta":{"raw":{"variants":["Effective transitions: a new link predictor for any network","Link prediction via effective transitions beats common methods","Isospectral reductions power a fast, accurate link predictor","Effective transitions: better link prediction, often faster","New math predicts links: effective transitions outperform"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001588,"raw_usage":{"total_tokens":6310,"prompt_tokens":901,"completion_tokens":5409,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":517,"completion_tokens_details":{"reasoning_tokens":5337}},"tokens_in":517,"tokens_out":5409,"duration_ms":40733,"temperature":1.0,"reasoning_tokens":5337,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:42:59.439329+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the paper's 80/20 temporal split on a collection of strongly connected directed weighted networks and compare the effective-transition ranking of held-out edges with a random ranking: if its AUC is not above 0.5 while at least one standard predictor is, the competitiveness claim is refuted.","supporting_citations":[{"cited_title":"B unimovich and B","cited_arxiv_id":null,"evidence_quote":"Supplies the theory of isospectral reductions used to prove that pairwise reductions compute the effective transition probabilities."},{"cited_title":"M eyer, Uncoupling the perron eigenvector problem, Linar Algebra and its Applications, 114–115 (1989), pp","cited_arxiv_id":null,"evidence_quote":"Defines the Perron complement, the matrix transformation behind the isoradial reduction formula."},{"cited_title":"S mith and B","cited_arxiv_id":null,"evidence_quote":"Establishes existence, nonnegativity, irreducibility, and spectral-radius preservation of isoradial reductions, used in Proposition 4.3."},{"cited_title":"L iben-Nowell and J","cited_arxiv_id":null,"evidence_quote":"Defines the link prediction problem and the standard baseline predictors the effective-transition scores are compared against."},{"cited_title":"H orn and C","cited_arxiv_id":null,"evidence_quote":"Provides the spectral-radius bound for submatrices used in the proof that the l-step approximation converges."},{"cited_title":"2017, http://konect.uni-koblenz.de/networks/ ca-cit-HepTh","cited_arxiv_id":null,"evidence_quote":"Supplies the HepTh coauthorship dataset used in the accuracy comparisons."},{"cited_title":"2017, http://konect.uni-koblenz.de/ networks/facebook-wosn-wall","cited_arxiv_id":null,"evidence_quote":"Supplies the Facebook wall-posts dataset used in the directed-network accuracy comparisons."}],"review_version":1}