Abstract
This paper demonstrates that the underlying Euclidean metric and probability density of a dataset can be recovered from a directed, unweighted graph, such as a $k$-nearest neighbor graph. By establishing that random walks on these graphs converge to continuous drift-diffusion processes, the authors derive a "PageRank-like" estimator to reconstruct latent geometry. The method is shown to be consistent and robust even in sparse graph regimes.
Introduction
In many domains, data is naturally represented as graphs—social networks, biological pathways, or recommendation systems. Often, these graphs are constructed from points in a latent space, yet the original spatial coordinates and density are discarded. Recovering this information from an unweighted, directed graph is a difficult inverse problem. For example, in a $k$-nearest neighbor ($k$-NN) graph, every node has the same out-degree, masking local density variations. This research provides a consistent framework for recovering these geometric properties across various dimensions and sparsity levels.
Methodology
The authors model data as samples from an unknown density $p(x)$ in $\mathbb{R}^d$. They analyze unweighted directed geometric graphs where edges are determined by a local distance threshold $\epsilon(x_i)$. The core contribution involves analyzing a simple random walk on this graph. Using the Stroock-Varadhan criterion, the authors prove that as the number of points $n \to \infty$, the discrete walk converges to a continuous Itô process.
By solving the associated Fokker-Planck equation, they identify that the stationary distribution $\pi(x)$ of the random walk is proportional to $p(x)^2 / \epsilon(x)^2$. Combined with the graph's out-degree, which relates to $p(x)\epsilon(x)^d$, this allows for the algebraic recovery of both the density $p(x)$ and the local scale $\epsilon(x)$.
Key Results
The proposed estimator was validated using simulated distributions, USPS handwritten digits, and Amazon co-purchasing networks. Empirical tests demonstrate that the random-walk approach consistently outperforms existing path-integral methods, particularly as the number of data points increases.
A significant finding is the estimator's robustness to sparsity. While theoretical bounds suggest a specific growth rate for the degree $k$, empirical results show near-perfect recovery even when $k \approx \log(n)$. The convergence behavior is notably more stable than previous approaches.
Discussion and Insights
The research reveals that even in graphs where every node has identical connectivity (like $k$-NN), a random walker is naturally "pulled" toward high-density regions. This "drift toward density" provides a rigorous geometric justification for the success of PageRank-like algorithms in identifying important nodes.
Once the local scale $\epsilon(x)$ is recovered, the graph can be weighted to approximate global geodesic distances, enabling full isometric embeddings. However, limitations remain, such as the requirement for a known dimension $d$ and potential errors near complex boundaries or in highly fragmented graphs. Future work may bridge the gap between theoretical sparsity requirements and the empirical success observed at lower connectivity levels.
Summary updated