{"id":"28810e0b-2b08-4fe4-8d45-3df0eb14d433","arxiv_id":"1908.09644","paper_version":5,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":3.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A modified random walk with acceptance probabilities yields node rankings close to DeepWalk's, computed up to 34 times faster via a matrix power series.","lead":"This paper introduces a modified random walk, called a frustrated random walk, whose expected hitting times can be computed from a matrix formula rather than slow simulation. The authors report ranking nodes 7 to 34 times faster than the DeepWalk algorithm on four real-world graphs, while producing similar rankings.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper's O(V^2) speed claim rests on Nmax≈V (Eq. 22), which its own Appendix A.2 contradicts (Nmax=7500 for V=100); if Nmax scales with inverse spectral gap instead of V, the advertised speedup may not generalize to large graphs.","rationale":"The reader's weakest assumption (DeepWalk as ground truth) is a genuine limitation of the quality comparison, and the paper's own statement in Section IV A about lacking ground truth is properly flagged. However, I find the speed/complexity claim to be the more load-bearing concern for the paper's central assertion of a 'faster algorithm.' The mathematical derivation of Eq. (16) is standard and internally consistent for the stated random-walk model, and the measured per-target speedups on the four datasets are plausible. The problem is the asymptotic claim used to justify applicability to huge graphs: Eq. (21)-(22) assume Nmax is approximately V, but the appendix's own numerical experiment and Figure 5 show much larger expansion orders. Because DeepWalk's cost is a one-time embedding cost while FRW must be rerun per target, the advertised speedup is workload-dependent even when the single-target measurements are correct. This does not invalidate the paper's core contribution, but it means the abstract's sweeping speed/scalability claims need substantial qualification. Hence the verdict stays conditional: the algorithm and its exact per-target formula can be accepted, but the complexity analysis and benchmark framing must be corrected or carefully scoped.","tokens_in":18129,"tokens_out":15742,"duration_ms":157171,"concrete_test":"Run Algorithm 3 on the Fig. 7 graph and on synthetic paths and random graphs of increasing size (V = 50, 100, 200, 400), recording Nmax needed to reach the Section IV D tolerance (ranking difference < 1e-4). If Nmax/V is not roughly constant, Eq. (22) and the O(V^2) complexity claim fail; for path-like graphs, Nmax should grow roughly as V^2. This directly tests whether the reported per-target speedups extrapolate to larger graphs.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section IV E derives O(V^2) total time from Eq. (21), a 'naive approximation' that the row-sum defect over target neighbors sums to 1, so Nmax≈NB≈V. This is not a harmless crude estimate: for a substochastic random-walk matrix, the number of power-series terms needed to reach tolerance ε is roughly ln(1/ε)/(1−λmax), and λmax can lie much closer to 1 than the average row sum. The paper's own Appendix A.2 reports that a 100-vertex, 704-edge graph already needs 7500 iterations, and Fig. 5 shows expansion orders up to 20,000 on datasets with only 183 and 4626 nodes. If Nmax grows like the inverse spectral gap (often Θ(V^2) on graphs with bottlenecks), the per-target cost becomes O(E·V^2)=O(V^3) for sparse graphs, not O(V^2). Additionally, Table X compares FRW's per-target running time with DeepWalk's one-time embedding cost; FRW must rebuild a target-specific B and rerun the series for each target, so multi-target workloads (recommendation, targeted ads) may erase or reverse the advertised 7–34× speedup. The speed claim therefore rests on an unverified, internally contradicted scaling assumption.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines a \"frustrated random walk\" on an undirected weighted graph in which a step from i to j is proposed with probability w_ij/D_i and accepted with probability w_ij/D_j, giving off-diagonal transition probabilities w_ij^2/(D_iD_j). It derives an analytical expression for the vector of expected hitting times to a target t, ⟨N_t⟩ = Σ_{n≥0} B^n 1 (Eq. (16)), where B is the transition matrix with the target and its adherents removed. The authors propose to use the resulting asymmetric distances for node ranking, compare rankings against DeepWalk, SRW, and PPR via Spearman correlation, and report 7–34× speedups over DeepWalk. They claim O(V^2) time on sparse graphs, with Nmax (the power-series truncation order) as the only parameter and no tuning needed.","tokens_in":18426,"tokens_out":6832,"duration_ms":268168,"significance":"Equation (16) is a correct and useful closed form for expected hitting times; Appendix A.1 validates it on a small graph, and the authors provide code. If the ranking and speed claims held, FRW would be a practical parameter-free node-distance method for weighted graphs. However, the quality evaluation uses DeepWalk as its only quantitative benchmark while claiming to beat DeepWalk, and the complexity analysis is contradicted by the paper's own Appendix A.2. The contribution is therefore conditional: the analytic derivation is sound, but the two headline claims need substantial revision or re-scoping.","major_comments":[{"comment":"The derivation of O(V^2) time rests on Eq. (21), which approximates the sum over target neighbors of w_it^2/(D_iD_t) by 1, leading to Nmax ≈ NB ≈ V in Eq. (22). The paper's own Appendix A.2 reports that a graph with only 100 vertices and 704 edges requires 7500 power-series terms to reach machine precision, i.e., Nmax ≈ 75V, not Nmax ≈ V. The number of terms needed is governed by the spectral gap of B, not by the average row-sum defect over target neighbors, and graphs with bottlenecks can make 1 - λmax much smaller than the value implied by Eq. (21). The advertised O(V^2) scaling is therefore not established; the authors should replace this heuristic with an empirical scaling study on larger graphs or with a bound explicitly involving 1/(1 - λmax).","section":"Section IV E, Eqs. (21)-(22), and Appendix A.2"},{"comment":"The running-time comparison is apples-to-oranges. Table X reports FRW as the mean per-target time over 89, 82, and 99 targets, while the DeepWalk time is a one-time embedding cost. For tasks that require distances to many targets, such as recommendation or targeted ads, FRW must rebuild the target-specific matrix B and rerun the power series for each target, so the total cost scales with the number of targets. The 7–34× speedup is only demonstrated for the single-target ranking task, and the abstract's blanket 'more than ten times acceleration' claim is too broad.","section":"Section IV D, Table X"},{"comment":"The quality evaluation is benchmark-circular. The manuscript explicitly states that 'we can only benchmark our computational results with human judgement or with DeepWalk results due to lack of ground truth' (Section IV A), and then uses Spearman correlation with DeepWalk as the quantitative quality measure. High correlation with DeepWalk shows similarity to DeepWalk, not superiority over it, so the repeated conclusion that FRW 'beats' or 'outperforms' DeepWalk is not supported by the tables. The informal top-neighbor checks in Tables VI and VII are anecdotal, and the Spearman coefficients are reported without confidence intervals or significance tests. The authors should either drop the claim of beating DeepWalk or evaluate on a task with external ground truth, such as link prediction or node classification.","section":"Section IV A, Section IV B, Tables III-V and VIII-IX"}],"minor_comments":[{"comment":"The phrase 'beat DeepWalk results with more than ten times acceleration' conflates quality and speed; the paper should distinguish 'produces rankings highly correlated with DeepWalk' from 'runs faster than DeepWalk'.","section":"Abstract and Section I"},{"comment":"After Section IV A states that ground truth is lacking, Section IV B calls DeepWalk results 'our ground truth label'; this terminology is contradictory and should be aligned.","section":"Section IV B"},{"comment":"The 'ranking difference' plotted in Fig. 5 is defined only in prose; please give the exact formula used to compute it from normalized similarity vectors.","section":"Section IV C, Fig. 5"},{"comment":"The reported Nmax = 7500 is for machine precision; it would be informative to also report the Nmax required for the ranking-difference threshold 10^-4 used in Section IV D.","section":"Appendix A.2"},{"comment":"The Spearman coefficients are computed for only a handful of targets per dataset, with no confidence intervals or significance tests; reporting the number of targets and a measure of uncertainty would strengthen the comparison.","section":"Tables III-V and VIII-IX"}],"recommendation":"major_revision","confidential_remarks":"The analytic core of the paper is sound and reproducible, but the headline speed and 'beats DeepWalk' claims are not supported as written. If the authors re-scope the claims, provide a fair multi-target timing comparison, and add an empirical scaling study for Nmax on larger graphs, the paper could become publishable; in its current form the load-bearing complexity and quality arguments need substantial work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick read of arXiv:1908.09644. The genuinely new thing is the transition matrix B_ij = w_ij^2/(D_i D_j): proposal probability times acceptance probability, giving a symmetric substochastic matrix with self-loops. That is a simple, interpretable modification, and the motivation (minions attaching to protagonists) is clear. The hitting-time formula, Eq. (16), is the standard Neumann series for expected hitting times of a Markov chain, which the authors acknowledge by citing Lovasz; deriving it via generating functions is fine. The Appendix A sanity check on a five-node graph, comparing exact, Monte Carlo, and numerical results, is a nice touch, and the code is on GitHub. Credit where due: the derivation is correct as far as it goes, and the parameter-robustness claim for rankings is plausible because only the ordering needs to stabilize.\n\nThe soft spots, in descending order. The time-complexity claim is the weakest. Section IV E derives Nmax ≈ V from Eq. (21), a \"naive approximation\" that the row-sum defect over target neighbors sums to one. But Appendix A.2 reports a 100-vertex, 704-edge graph needing 7500 power-series terms—about 75V, not V. The paper therefore contradicts its own O(V^2) claim. For graphs with bottlenecks, Nmax scales with the inverse spectral gap and can be much larger, so the advertised speedup may not generalize. This is load-bearing for the abstract's \"huge graphs\" claim.\n\nThe evaluation is also benchmark-circular. Section IV A says they use DeepWalk as the benchmark because ground truth is lacking, then treat Spearman correlation with DeepWalk as quality, and later conclude FRW \"beats DeepWalk.\" What they actually show is that FRW approximates DeepWalk's rankings quickly on small to medium graphs. That is useful, but it is not a quality win over DeepWalk. Table X also compares FRW's per-target time with DeepWalk's one-time embedding cost; for workloads with many targets, FRW must rebuild B and rerun the series for each target, which can erase or reverse the speedup. The absence of error bars and significance tests is minor by comparison.\n\nFor a small-graph variant, the paper is a reasonable contribution: one new matrix, correct formula, some empirical sanity checks. For the claims made—beating DeepWalk, handling huge graphs—it falls short. I would send it to review rather than desk-reject, because the core derivation is checkable and the new transition matrix is worth discussing, but the referee should push hard on the complexity analysis and the benchmark framing.","headline":"The new transition matrix is a clean idea and the hitting-time derivation is correct, but the speed claim rests on an approximation the paper's own appendix contradicts, and the evaluation benchmarks against the algorithm it claims to beat.","tokens_in":18939,"tokens_out":2085,"would_cite":false,"duration_ms":454581,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C81","05C85","60J10","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Frustrated random walks compute expected hitting times from a matrix power series and match DeepWalk rankings at 7–34 times the speed.","keywords":["frustrated random walk","expected hitting time","node proximity","weighted undirected graph","matrix power series","DeepWalk comparison","spectral radius","graph distance"],"falsifier":"Take a weighted co-occurrence or social graph with independently obtained human relevance ratings for a sample of node pairs (or a synthetic graph with planted node distances), rank nodes from each target by FRW and by DeepWalk, and compare both rankings to those labels; the central quality claim fails unless FRW matches or beats DeepWalk's agreement with the labels, not just with DeepWalk itself.","tokens_in":17893,"feed_emoji":"🕸️","tokens_out":9294,"duration_ms":90441,"temperature":0.7,"pith_summary":"The paper proposes a frustrated random walk (FRW), in which every proposed hop from node $i$ to neighbor $j$ is accepted with probability $w_{ji}/D_j$, so the effective transition probability is $(w_{ij}/D_i)(w_{ji}/D_j)$. It derives an analytical formula, $\\langle N_t\\rangle=\\sum_{n=0}^\\infty B^n\\mathbf{1}$, for the expected hitting time to a target $t$, using only the weighted adjacency matrix and no matrix inversion or Monte Carlo simulation. The authors test node-proximity rankings built from these hitting times on four real weighted graphs and report that FRW matches DeepWalk's rankings and human judgement more closely than simple random walk or personalized PageRank on heavily weighted graphs, while running 7 to 34 times faster than DeepWalk. The only parameter is the power-series truncation order, and the paper shows relative rankings stabilize as that order grows. If the claim holds, large social and interaction graphs can be ranked by proximity with a sparse matrix-vector iteration, without corpus generation, embedding training, or hyperparameter tuning.","feed_headline":"Frustrated random walks rank nodes as well as DeepWalk, 7–34× faster","feed_subtitle":"Expected hitting times from a closed-form matrix series reproduce DeepWalk-style rankings on weighted social graphs—no embedding training…","key_machinery":"The load-bearing object is the target-dependent probability transition matrix $B$ of the frustrated random walk. Off-diagonal transition probabilities are products of a proposal probability $w_{ij}/D_i$ and an acceptance probability $w_{ji}/D_j$, so for undirected graphs $B$ is symmetric; diagonal entries correspond to staying in place when a proposal is rejected, which makes $B$ primitive. Because rows adjacent to the target sum to less than one, $B$ is not a Markov matrix and by Perron–Frobenius has spectral radius below one. That spectral-radius bound is what turns the hitting-time recurrence into the convergent matrix power series of Eq. (16), and it also sets the required number of terms: the paper estimates $N_{\\max}\\propto 1/(1-\\lambda_{\\max})\\approx V$, giving $O((E+V)V)$ time overall, or $O(V^2)$ for sparse graphs.","core_discovery":"The central discovery is that adding an acceptance probability to each random-walk transition produces a target-dependent transition matrix $B$ whose spectral radius is provably below one, and whose powers sum in closed form to all expected hitting times. For a fixed target $t$, the off-diagonal entries are $B_{ij}=\\frac{w_{ij}}{D_i}\\frac{w_{ji}}{D_j}$ for $j\\ne t$, and the diagonal entries absorb rejected proposals so every row sums to one except rows adjacent to the target. Hitting probabilities satisfy $X_n=B X_{n-1}$, and summing this recurrence gives $\\langle N_t\\rangle=\\sum_{n=0}^\\infty B^n\\mathbf{1}$, so expected hitting times are independent of the starting distribution. On the weighted Harry Potter, Dream of the Red Chamber, IMDB, and arXiv graphs, the authors use Spearman correlation with DeepWalk rankings as the quality measure; FRW has the highest correlations on the heavily weighted datasets and matches DeepWalk's top-neighbor lists, with a 7–34× running-time advantage. The paper therefore claims FRW is a practical distance oracle for huge undirected weighted graphs, with one untuned parameter.","pith_inferences":["Because $B$ is symmetric for a fixed target, each target's hitting-time vector is a single matrix-power recurrence; one could reuse one target's solution to warm-start neighboring targets, an acceleration the paper does not explore.","The FRW formula depends only on weighted adjacency, so it should transfer directly to link prediction or recommendation features on graphs where no node attributes exist; this is a testable extension the paper mentions only in passing.","The observed exponential decay of ranking differences suggests a formal adaptive stopping rule based on the spectral gap, rather than a fixed threshold; on larger graphs this could be verified by comparing rankings at successive truncation orders.","Since FRW does not require ground-truth labels, a natural stress test is to compare FRW distances with shortest-path distances on synthetic weighted graphs with planted community structure; the paper does not run this test."],"forward_implications":["Node proximity on weighted undirected graphs can be obtained by iterating sparse matrix-vector products, with no embedding training, random-walk corpus, or matrix inversion.","On heavily weighted graphs that capture human interaction, FRW rankings track DeepWalk more closely than simple random walk rankings, which overrate low-degree neighbors of hubs, and personalized PageRank rankings, which overrate global hubs.","The 7–34× speedup over DeepWalk grows with graph size, making the method suitable for graphs too large for embedding-based approaches.","The single truncation parameter does not need tuning: ranking differences decay to zero as the expansion order grows, so the iteration can stop when the ranking stabilizes.","The time complexity on sparse graphs is roughly $O(V^2)$, quadratic in the number of nodes, so the method remains practical where DeepWalk's memory and CPU cost do not scale."],"supporting_citations":[{"why":"Supplies the embedding-based node ranking used as the benchmark for all quality comparisons.","marker":"[5]"},{"why":"Defines expected hitting times of random walks as a graph distance, the metric FRW builds on.","marker":"[7]"},{"why":"Provides the random-walk distance framework and the comparison with geodesic distance that motivates hitting times.","marker":"[8]"},{"why":"Gives the Perron–Frobenius results used to show that $B$ has spectral radius below one, so the power series converges.","marker":"[17]"},{"why":"Introduces the simple-random-walk node proximity baseline that FRW is compared against.","marker":"[18]"},{"why":"Presents topic-sensitive PageRank, one of the personalized PageRank baselines.","marker":"[3]"},{"why":"Provides the personalized PageRank distance baseline used in experiments.","marker":"[4]"},{"why":"Defines PageRank, whose per-target values are used to select targets of varying centrality.","marker":"[9]"},{"why":"Supplies the trained word-embedding model used to produce DeepWalk vectors in the running-time comparison.","marker":"[28]"}],"fun_headline_variants":["Closed-form walk outruns DeepWalk 34×, no tuning","One-parameter FRW: DeepWalk accuracy at 34× speed","Frustrated walk distances: closed-form, beats DeepWalk 7–34×","Matrix series gives exact hitting times, 34× faster than DeepWalk","Skip training: closed-form random walk ranks like DeepWalk, 34× faster"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that DeepWalk's cosine-distance rankings are a valid proxy for true node proximity—the paper states in Section IV A that without ground truth it can only benchmark against human judgement or DeepWalk and then defines quality as Spearman correlation with DeepWalk—so if DeepWalk is a poor measure of proximity, the tables show only that FRW approximates DeepWalk faster, not that FRW is the better distance.","fun_headline_variants_meta":{"raw":{"variants":["Closed-form walk outruns DeepWalk 34×, no tuning","One-parameter FRW: DeepWalk accuracy at 34× speed","Frustrated walk distances: closed-form, beats DeepWalk 7–34×","Matrix series gives exact hitting times, 34× faster than DeepWalk","Skip training: closed-form random walk ranks like DeepWalk, 34× faster"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000706,"raw_usage":{"total_tokens":3192,"prompt_tokens":963,"completion_tokens":2229,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":579,"completion_tokens_details":{"reasoning_tokens":2128}},"tokens_in":579,"tokens_out":2229,"duration_ms":15100,"temperature":1.0,"reasoning_tokens":2128,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:02:39.971464+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a weighted co-occurrence or social graph with independently obtained human relevance ratings for a sample of node pairs (or a synthetic graph with planted node distances), rank nodes from each target by FRW and by DeepWalk, and compare both rankings to those labels; the central quality claim fails unless FRW matches or beats DeepWalk's agreement with the labels, not just with DeepWalk itself.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the embedding-based node ranking used as the benchmark for all quality comparisons."},{"cited_title":"Perozzi, R","cited_arxiv_id":null,"evidence_quote":"Defines expected hitting times of random walks as a graph distance, the metric FRW builds on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the Perron–Frobenius results used to show that $B$ has spectral radius below one, so the power series converges."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the simple-random-walk node proximity baseline that FRW is compared against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Presents topic-sensitive PageRank, one of the personalized PageRank baselines."},{"cited_title":"Jeh and J","cited_arxiv_id":null,"evidence_quote":"Provides the personalized PageRank distance baseline used in experiments."},{"cited_title":"Lov´ asz, Combinatorics, Paul erdos is eighty 2, 1 (1993)","cited_arxiv_id":null,"evidence_quote":"Defines PageRank, whose per-target values are used to select targets of varying centrality."}],"review_version":1}