Graph reconstruction from random-walk co-visitation: Geometric, empirical, and controlled networks

Abstract

Reconstructing an unknown graph from the trajectory of a random walk arises both for spatial correlation networks in astrophysics and for connectivity inference in network science. We present a reconstruction pipeline whose observable is the random-walk co-visitation matrix, whose model is a pairwise edge-weight basis, and whose fitter is a frame-balanced Levenberg-Marquardt (fbLM) scheme with per-node group weights and a self-calibrated edge readout. Unlike the marginal occupation, the co-visitation retains the ordered pair before the row sum is taken, and the pairwise basis can represent structure that an additive node-potential model cannot; neither change suffices alone. We apply the pipeline to an email communication subgraph, to Delaunay and Voronoi networks built from a COSMOS sky catalogue, and to two controlled 12-vertex test graphs, one unicyclic and one a tree, under both analytic-noise and finite-walk regimes. Reconstructions are scored against the ground-truth adjacency, which enters nowhere in the fit, by true/false positives and the Matthews correlation coefficient (MCC). All test-beds are reconstructed with high fidelity at full graph size: on finite-walk data we recover the COSMOS Delaunay and Voronoi graphs at MCC above 0.98 up to their full extent, N=119 and N=223, the whole graph rather than a cut-out of it, and the empirical email-Eu-core graph at N=240 (417 edges). On the full Delaunay graph a graphical-lasso reference returns MCC 0.540 against 0.988 for fbLM. Each reconstructed edge carries a Fisher-propagated uncertainty, and the residual misses are almost entirely confined to edges the walk never traverses. In the finite-walk regime the limiting factor is therefore walk coverage rather than the fit: essentially every edge the walk visits is recovered, so reconstructibility is governed by the sampling of the graph rather than by the estimator.