{"id":"14f75ac6-3b19-4047-8134-0573012d482d","arxiv_id":"2608.05385","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A new random-walk co-visitation pipeline reconstructs test graphs with high MCC, but its headline accuracy is largely set by walk coverage because clean walks never cross non-edges.","lead":"This paper presents a method to recover the edges of a hidden network from the path of a random walk, using a matrix of which pairs the walk visits in sequence. On test networks including galaxy-position graphs, it reports high accuracy, but the results rely on the fact that clean random walks only ever cross real edges.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Finite-walk claims depend on a clean-support restriction that makes false positives impossible; the estimator's edge-discrimination ability is never tested at scale, so the coverage-limited conclusion is not yet established for the headline regime.","rationale":"The paper is unusually transparent and the full-basis coverage study plus the multiplicative-noise experiment are genuine evidence for the ranking and readout behavior; the per-edge uncertainties are computed without the ground-truth adjacency. The reader's weakest-assumption identification is correct, and it is the same concern I would put first: the finite-walk headline is not yet a test of false-positive rejection. The concrete pollution experiment would settle whether the estimator can discriminate when the basis contains non-edges. If it passes, the conditional verdict can be upgraded; if it fails, the scale claim needs qualification. No change to the reader's CONDITIONAL verdict is needed, and the proposed check is runnable even without a full code release.","tokens_in":19839,"tokens_out":4383,"duration_ms":39769,"concrete_test":"Run the N=119 Delaunay finite-walk experiment with a deliberately polluted basis: after counting transitions, inject non-edge pairs so that 1%, 3%, and 10% of the support entries are random (i,j) with A_ij=0, then run the same fbLM fit and readout with no other changes. If the readout rejects the injected non-edges and MCC stays near 0.988, the clean-support restriction is not load-bearing for the scale claim. If false positives appear or MCC drops substantially, the finite-walk conclusion is an artifact of the support restriction rather than a property of the estimator. A second, minimal diagnostic is to add the trivial support baseline as an explicit row in Table 1 so the increment fbLM provides over 'edge iff traversed' is visible for every row.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the finite-walk regime the basis is the empirical support of the observed transitions (Sect. 2.1), and for clean trajectories that support is a subset of the true edge set (Sect. 3.1: 'for clean trajectories the observed support is contained in the true edge set'). The Table 1 caption already defines the trivial baseline: declaring an edge wherever the walk traversed one gives TP=m, FN=E-m, FP=0, and states that fbLM reproduces that baseline exactly on nine of the eleven rows, falling two edges short on email-Eu-core at N=20 and one at N=100. Consequently the finite-walk MCCs are, to within two edges, predetermined by walk coverage; the readout is never asked to reject a non-edge. The paper's central claim that reconstructibility is governed by the sampling of the graph rather than by the estimator is therefore supported in the clean regime only in the weak sense that the estimator does not destroy the information the support already contains. The places that would test real discrimination, the full-basis coverage experiment (Fig. 8, N=25) and the multiplicative-noise regime (Table 2, N<=37), do so only at small size, and the multiplicative-noise case is explicitly acknowledged to be easy because exact zeros in the target already encode the non-edges. The abstract's 'essentially every edge the walk visits is recovered' is also slightly too strong given the two traversed-but-missed edges at N=20 and one at N=100. This is not an internal inconsistency: the paper states the restriction and lists support pollution as future work, but the headline scale claim is conditional on a data model in which false positives cannot occur.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript develops a pipeline for reconstructing an unobserved graph from random-walk co-visitation data. The observable is the ordered-pair transition-count matrix C; the model is a pairwise log-weight basis S(β) mapped to a transition matrix by row normalization; the fit is a 'frame-balanced' Levenberg-Marquardt scheme with per-vertex weights obtained from a Stiefel-manifold optimization, gauge fixing, and a self-calibrated per-node readout. The method is tested on email-Eu-core subgraphs, COSMOS Delaunay and Voronoi networks, and two 12-vertex control graphs, under both analytic multiplicative noise and finite-walk sampling, with graphical lasso as a reference and Fisher-propagated uncertainties attached to reconstructed edges. The paper's central conclusion is that in the finite-walk regime reconstruction quality is limited by walk coverage rather than by the fit.","tokens_in":20123,"tokens_out":7012,"duration_ms":64269,"significance":"The paper is careful and unusually transparent: it states the support-restriction caveat, defines the trivial coverage baseline in the Table 1 caption, keeps the ground-truth adjacency out of the fit and readout, and provides a reproducible numerical setup with all constants listed in Appendix A. The pairwise co-visitation observable and the frame-balanced fitter are reasonable and potentially useful contributions, and the per-edge uncertainty propagation is a welcome addition. However, the central claim that the estimator is not the limiting factor is only partially supported in the headline regime, because the finite-walk candidate basis contains only true edges and therefore false positives are impossible by construction. The experiments that genuinely require edge/non-edge discrimination are small in size, and the multiplicative-noise case is explicitly degenerate because exact zeros encode the non-edges. The result is nevertheless a solid contribution if the claims are narrowed or supplemented with a larger discriminating experiment.","major_comments":[{"comment":"In the finite-walk regime the basis is restricted to the observed support of the co-visitation, and for clean trajectories that support is a subset of the true edge set. Consequently FP=0 is enforced by construction, and the MCC is predetermined, to within one or two edges, by the number of edges the walk traverses; the Table 1 caption already defines this trivial baseline. The abstract's claim that 'reconstructibility is governed by the sampling of the graph rather than by the estimator' is therefore only a statement about the support-restricted clean regime, not about the estimator's ability to discriminate edges from non-edges at scale. To make this conclusion load-bearing, the manuscript should either add a finite-walk experiment at N=100 or larger in which the full pairwise basis, or a polluted support containing injected non-edges, is fitted, or it should narrow the abstract and Section 5 conclusions to the support-restricted regime.","section":"§2.1, §3.1, Table 1"},{"comment":"The only experiments that actually require the fitter to reject non-edges are the full-basis coverage study at N=25 (Fig. 8) and the multiplicative-noise runs up to N=37 (Table 2). The multiplicative-noise regime is explicitly degenerate because the exact zeros of the analytic co-visitation already encode the non-edges, as the authors themselves state. At N=25 the AUC margin over a coverage-only ordering is small, and the authors caution that the gap mainly shows that the threshold fails before the ordering does. These small-scale tests do not establish that the readout performs real edge discrimination in the N=100-240 regime. A test with non-edge candidates present at the larger sizes, even at the cost of fewer repeats, would materially strengthen the paper's central claim.","section":"§4.4, §4.5, Table 2"},{"comment":"The comparison with graphical lasso is not like-for-like, as the authors acknowledge: fbLM receives the support-restricted basis while graphical lasso searches all N-choose-2 pairs. The abstract's statement that 'the graphical-lasso reference returns MCC 0.540 against 0.988 for fbLM' should carry this caveat in the abstract itself, since without it the numbers imply a head-to-head comparison. The acknowledgment in Section 4 is clear, but the prominence of the comparison in the abstract and conclusions overstates the evidence for estimator superiority.","section":"Abstract, §4, §5"}],"minor_comments":[{"comment":"The phrase 'essentially every edge the walk visits is recovered' should be quantified: Table 1 shows two traversed edges missed at N=20 and one at N=100 on email-Eu-core, so the statement is true only with the word 'essentially' doing substantial work.","section":"Abstract, §4.4"},{"comment":"The caption is very long and contains much of the paper's interpretive content, including the trivial-baseline discussion and the basis-convention caveat; moving this discussion into the main text, for example into §4.4, would improve readability.","section":"Table 1 caption"},{"comment":"The definition of N_d as 'the number of informative entries of the residual matrix' is vague; please specify how N_d is computed for each regime and why the effective degrees of freedom is N_d - m + 1.","section":"§2.4"},{"comment":"The quoted chi-squared values are not accompanied by the number of data points or degrees of freedom; reporting the reduced chi-squared would make the fit-quality panels interpretable.","section":"§4.6, Figs. 9-13"},{"comment":"The statement that the n<=m case 'covers every test-bed except the radialness control' is correct but the appendix does not give the explicit orthonormal-column form of the retraction condition for n>m; a one-line clarification would help reproducibility.","section":"§3.1, Appendix A"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is honest and well structured; the main issue is not an internal inconsistency but a mismatch between the abstract's strong conclusion and the support-restricted evidence in the headline finite-walk regime. I believe the authors can address this either by adding one larger full-basis or polluted-support experiment or by carefully narrowing the claimed scope. No concerns about citation practice or novelty disclosure."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nYou should know two things about this one. First, it's an unusually honest methods paper—the authors state the support-restriction caveat right in the Table 1 caption. Second, that caveat cuts deeper than the abstract lets on: in the finite-walk regime, for clean trajectories, the candidate basis contains only true edges, so false positives are impossible by construction and the MCC is essentially the fraction of edges the walk happened to traverse. The paper says this itself, but the abstract's 'essentially every edge the walk visits is recovered' glosses over two traversed-but-missed edges at N=20 and one at N=100.\n\nThe genuinely new piece is the combination: co-visitation observable, per-pair log-weight basis, frame-balanced LM with Stiefel group weights, and a self-calibrated readout. That specific package isn't in the cited literature, and applying it to COSMOS Delaunay/Voronoi graphs is new. The gauge-fixing and covariance projection are carefully done, and the per-edge uncertainty propagation is a real contribution. The paper also includes a full-basis experiment (Fig 8) where ranking is tested over all pairs, and it shows the threshold fails before the ordering does—a genuinely informative result, though the margin over coverage is small.\n\nThe soft spots are proportionate. The multiplicative-noise regime is easy by design, since exact zeros in the target encode non-edges; the authors say so. The graphical-lasso comparison is not like-for-like, and that's acknowledged. The bigger problem is that the estimator's edge-discrimination ability is never tested at scale—full-basis runs cap out at N=25 and N=37. And there's no code or data, which hurts for a methods paper.\n\nWho's this for? Someone building graph reconstruction from diffusive processes, or wanting per-edge uncertainties on inferred adjacency. It deserves a serious referee—the issues are addressable: score the trivial support baseline as a row, run full-basis finite-walk experiments at larger N, add error bars, release code. I'd read a revised version. Recommend sending to review, with the coverage limitation as the central point to fix.","headline":"Transparent method paper whose headline finite-walk results mostly measure walk coverage; the real novelty is the full-basis ranking and uncertainty machinery.","tokens_in":20744,"tokens_out":2801,"would_cite":false,"duration_ms":23170,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Using only the ordered pairs a random walk traverses, this paper reconstructs hidden graphs with high fidelity and shows that the only edges missed are those the walk never reached.","keywords":["graph reconstruction","random walk","co-visitation matrix","network inference","frame-balanced Levenberg-Marquardt","Delaunay triangulation","Voronoi tessellation","galaxy distribution"],"falsifier":"Run the finite-walk protocol on the 119-vertex Delaunay graph after redirecting a controlled fraction—say 2 percent—of the recorded transitions to random non-edges before forming the co-visitation support; if the Matthews correlation coefficient stays near 0.988 the fit is genuinely separating edges from non-edges, while if false positives appear in proportion to the injected noise, the coverage-limited conclusion is an artifact of the clean-support assumption.","tokens_in":19565,"feed_emoji":"🕸","tokens_out":18183,"duration_ms":135967,"temperature":0.7,"pith_summary":"This paper claims that an unknown graph can be reconstructed from random-walk trajectories by fitting a pairwise edge-weight model to the co-visitation matrix—the record of which ordered transitions the walk makes. The central result is that in the finite-walk regime the fit is not the bottleneck: nearly every edge the walk actually visits is recovered, and the false negatives are almost exactly the edges the walk never traversed. On an email subgraph and on Delaunay and Voronoi graphs built from the COSMOS sky catalogue, the pipeline reaches Matthews correlation coefficients above 0.96 up to full graph size, while a graphical-lasso reference scores much lower on the triangle-rich cases. The practical conclusion is that reconstruction quality from clean walk data is set by walk coverage, not by the estimator.","feed_headline":"Walk coverage, not the fit, limits graph reconstruction","feed_subtitle":"New estimator recovers essentially every edge a random walk visits; missed edges are simply never reached.","key_machinery":"Three pieces carry the argument. The observable is the co-visitation matrix $C_{ij}=\\sum_{n'<T}p_{n'}(i)P_{ij}$, the walk's transition counts accumulated with the ordered pair intact rather than summed into a per-vertex marginal. The model is the pairwise edge-weight basis $S(\\beta)=\\sum_{(i,j)\\in B}e^{\\beta_{ij}}M_{ij}+\\varepsilon(\\mathbf{1}\\mathbf{1}^{\\top}-I)$, row-normalised into the transition matrix $P=\\mathrm{rownorm}(S)$, which gives every candidate pair an independent log-weight $\\beta_{ij}$ and can therefore represent clustered structure. The mechanism is the frame-balanced Levenberg–Marquardt fitter (a damped least-squares optimizer with per-vertex block weighting): per-vertex Gauss–Newton blocks are whitened and weighted through an orthonormal frame on the Stiefel manifold (the set of matrices with orthonormal rows), steps are scaled by the geometric factor $\\sigma=\\delta^{\\top}g^{(\\lambda)}\\delta_{\\mathrm{prev}}$, and the shift invariance $\\beta\\to\\beta+c\\mathbf{1}$ is removed by mean-centring the parameters after each proposal. The readout $\\rho_{ij}=W_{ij}/\\sqrt{s_i s_j}$, thresholded against the mean of its endpoints' couplings, converts fitted weights into an edge set with no absolute cutoff, while the gauge-projected covariance $V_\\beta=\\hat{\\sigma}^{2}\\Pi(\\Pi I\\Pi)^{+}\\Pi$ pushes uncertainty onto every reconstructed edge.","core_discovery":"The paper's central claim is that graph reconstruction from a random walk is carried by two design choices that only work together: a pairwise observable and a pairwise model. The co-visitation $C_{ij}=\\sum_{n'<T}p_{n'}(i)P_{ij}$ records the ordered pair $(i,j)$ before any row sum is taken, so it keeps pairwise structure that the marginal occupation—essentially the degree sequence—throws away; the model $S(\\beta)=\\sum_{(i,j)\\in B}e^{\\beta_{ij}}M_{ij}+\\varepsilon(\\mathbf{1}\\mathbf{1}^{\\top}-I)$ gives each candidate pair its own log-weight, so clustered structure that an additive node-potential model cannot represent is in reach. The fitter is a frame-balanced Levenberg–Marquardt scheme with per-node Stiefel group weights, an unnormalised geometric scale that self-brakes on overshoot, and a gauge fix for the invariance $\\beta\\to\\beta+c\\mathbf{1}$; the readout declares an edge when the self-calibrated coupling $\\rho_{ij}=W_{ij}/\\sqrt{s_i s_j}$ exceeds the mean coupling of its endpoints, so no absolute threshold is needed. On all five test-beds the finite-walk reconstructions reach MCC 0.967–1.000; in the largest runs every false negative is, to within one or two edges, an edge the walk never traversed, and no false positives occur because the clean-support basis contains no non-edges. The paper therefore concludes that in the finite-walk regime reconstructibility is governed by walk coverage rather than by the estimator: what the walk visits is recovered, and what it never visits carries no signal.","pith_inferences":["If coverage is truly the binding constraint, then adaptive sampling—restarting walks from under-visited vertices or biasing them toward low-coverage regions—should improve reconstruction more than any refinement of the estimator; this is a direct, testable consequence the paper does not pursue.","The finite-walk results never exercise real edge discrimination, because clean walks make the observed support a subset of the true edges; injecting a controlled fraction of spurious transitions, recorded steps that are not true edges, should be the next stress test, and the paper itself names support pollution as the dominant future failure mode.","The gauge-projected covariance machinery is not specific to random walks: any model in which a common shift in the parameters leaves the predictions unchanged could use the same projection to obtain interpretable per-parameter uncertainties."],"forward_implications":["In clean finite-walk data, reconstruction quality is a coverage measurement: an edge the walk never crosses carries no signal, and an edge it crosses is almost always recovered.","A modest number of walks saturates the recoverable fraction—MCC reaches near unity by a few hundred walks at 25 vertices—so oversampling costs nothing and the practical lever is sampling, not fitting.","The self-calibrated readout removes the need to tune an absolute threshold or a size-dependent cutoff to the graph's density, so the procedure transfers between graphs without recalibration.","The pipeline scores above a graphical-lasso baseline on triangle-rich graphs at full size (MCC 0.988 versus 0.540 on the Delaunay graph), though the baseline is not given the same candidate support.","Each recovered edge carries a Fisher-propagated uncertainty (median relative size 30–45 percent on the largest graphs), so edge confidence is available without ground truth."],"supporting_citations":[{"why":"Supplies the information-theoretic reconstructability framing that this paper sharpens into walk coverage as the operative limit.","marker":"Murphy et al. 2024"},{"why":"Poses the joint structural-prior inference alternative that motivates fitting a pairwise likelihood-like model to the co-visitation summary.","marker":"Peixoto 2019"},{"why":"Presents mean first-hitting-time inversion, the alternative reconstruction route against which the co-visitation observable is developed.","marker":"Wittmann et al. 2009"},{"why":"Provides the graphical-lasso baseline whose lower MCC (0.540 on the full Delaunay graph) anchors the method comparison.","marker":"Friedman et al. 2008"},{"why":"Supplies the email-Eu-core dataset used as the empirical 240-vertex test-bed.","marker":"Leskovec et al. 2007"},{"why":"Supplies the COSMOS sky catalogue from which the Delaunay and Voronoi test networks are built.","marker":"Smolčić et al. 2007"}],"fun_headline_variants":["Walk coverage, not fit, limits graph reconstruction","Graph reconstruction limited by walk sampling, not estimator","Random-walk co-visitation recovers all visited edges","Walk coverage is the true limit, not the estimator","Co-visitation matrix: walk coverage decides reconstruction"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every recorded walk step is a true edge of the hidden graph, so the candidate list never contains a false connection; if transitions can be mis-recorded, the pipeline would have to do genuine edge discrimination, which the finite-walk experiments never test.","fun_headline_variants_meta":{"raw":{"variants":["Walk coverage, not fit, limits graph reconstruction","Graph reconstruction limited by walk sampling, not estimator","Random-walk co-visitation recovers all visited edges","Walk coverage is the true limit, not the estimator","Co-visitation matrix: walk coverage decides reconstruction"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001586,"raw_usage":{"total_tokens":6487,"prompt_tokens":1269,"completion_tokens":5218,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":885,"completion_tokens_details":{"reasoning_tokens":5144}},"tokens_in":885,"tokens_out":5218,"duration_ms":35602,"temperature":1.0,"reasoning_tokens":5144,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T14:10:52.599177+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the finite-walk protocol on the 119-vertex Delaunay graph after redirecting a controlled fraction—say 2 percent—of the recorded transitions to random non-edges before forming the co-visitation support; if the Matthews correlation coefficient stays near 0.988 the fit is genuinely separating edges from non-edges, while if false positives appear in proportion to the injected noise, the coverage-limited conclusion is an artifact of the clean-support assumption.","supporting_citations":[{"cited_title":"2024, Nat","cited_arxiv_id":null,"evidence_quote":"Supplies the information-theoretic reconstructability framing that this paper sharpens into walk coverage as the operative limit."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Poses the joint structural-prior inference alternative that motivates fitting a pairwise likelihood-like model to the co-visitation summary."},{"cited_title":"2009, Theor","cited_arxiv_id":null,"evidence_quote":"Presents mean first-hitting-time inversion, the alternative reconstruction route against which the co-visitation observable is developed."},{"cited_title":"2008, Biostatistics, 9, 432","cited_arxiv_id":null,"evidence_quote":"Provides the graphical-lasso baseline whose lower MCC (0.540 on the full Delaunay graph) anchors the method comparison."},{"cited_title":"2007, ACM TKDD, 1, 2","cited_arxiv_id":null,"evidence_quote":"Supplies the email-Eu-core dataset used as the empirical 240-vertex test-bed."}],"review_version":1}