Metric recovery from directed unweighted graphs

Tatsunori B. Hashimoto, Yi Sun, Tommi S. Jaakkola

Abstract

This paper presents a mathematically rigorous framework for recovering the underlying geometry and probability density of a dataset from a directed, unweighted graph. By analyzing the continuum limit of a random walk on the graph, the authors show that the walk converges to an Itô diffusion process where the drift is determined by the gradient of the data density. This allows for the consistent estimation of Euclidean distances and densities across multiple dimensions, providing a theoretical foundation for algorithms like PageRank as tools for manifold learning.

Introduction

In many data science applications, relationships are represented as graphs where nodes are points in a latent Euclidean space $\mathbb{R}^d$. A common example is the $k$-nearest neighbor ($k$-NN) graph. However, when the original coordinates and edge weights are unavailable, reconstructing the latent geometry is a significant challenge. Previous research has often been restricted to undirected graphs or one-dimensional cases. This work addresses the general problem of recovering both the density $p(x)$ and the local scale $\epsilon(x)$ from the connectivity of a directed, unweighted geometric graph.

Methodology: From Random Walks to Diffusion

The core of the proposed method lies in viewing the graph as a landscape for a stochastic process. The authors utilize the Stroock-Varadhan criterion to prove that as the number of nodes $n$ approaches infinity, a discrete random walk on the graph converges to a continuous Itô diffusion.

Unlike undirected graphs where density information is often obscured, the asymmetry in directed graphs encodes the gradient of the density. A random walker on such a graph exhibits a "drift" toward regions of higher density. By solving the Fokker-Planck equation for the stationary distribution $\pi$ of this walk, the authors derive a relationship linking the graph's structure to the underlying density $p(x)$ and local scale $\epsilon(x)$. This allows for the explicit estimation of density and the subsequent reconstruction of global distances by finding shortest paths on a graph weighted by the recovered local scale.

Key Results and Empirical Validation

The method was tested on simulated manifolds, the USPS digits dataset, and the Amazon co-purchasing graph.

Density Recovery

On simulated datasets including mixtures of Gaussians and $t$-distributions, the random walk estimator showed remarkable fidelity to the ground truth density.

Comparison of density estimation methods against ground truth for various simulated distributions.

As shown in the figure above, the "graph random walk" (red line) closely tracks the "ground truth" (black line) across different distribution types, significantly outperforming the noisier path integral approach (green line).

Scaling and Sparsity

A critical finding is the robustness of the recovery as the graph density changes. The estimator maintains high correlation with ground-truth metrics even when the graph is sparse (e.g., $k \approx \log n$).

Correlation between recovered metrics and ground truth as the number of points increases, demonstrating the robustness of the random walk approach.

The results indicate that for random walks with $k = \log(n)$ or $k = \sqrt{n}$, the correlation with the underlying metric approaches 1.0 as the number of points increases, confirming the theoretical consistency of the approach.

Real-World Application: Amazon Co-purchasing

In the Amazon dataset, where no ground truth coordinates exist, the recovered density correlated strongly with sales rank. This suggests that "popularity" in a commercial network is a geometric property that can be extracted via random walks. Furthermore, following the density gradients allowed for the unsupervised discovery of product categories like "Philosophy" and "Classical Music."

Discussion and Limitations

While the results are promising, several theoretical hurdles remain. The current proof for consistency requires the graph degree to grow at a specific rate relative to the dimension $d$. Additionally, the impact of jagged boundaries in real-world data and the formal proof of the "equicontinuity conjecture" regarding the stationary distribution are areas for future research. Despite these limitations, the work provides a powerful bridge between PageRank-style network analysis and the geometric study of manifolds.

Summary updated

BibTeX
@inproceedings{hashimoto2015metric,
  author = {Tatsunori B. Hashimoto and Yi Sun and Tommi S. Jaakkola},
  title = {{Metric recovery from directed unweighted graphs}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2015},
}
Figure