Balancing Geometry and Density: Path Distances on High-Dimensional Data
  New geometric and computational analyses of power-weighted shortest-path
distances (PWSPDs) are presented. By illuminating the way these metrics balance
density and geometry in the underlying data, we clarify their key parameters
and discuss how they may be chosen in practice. Comparisons are made with
related data-driven metrics, which illustrate the broader role of density in
kernel-based unsupervised and semi-supervised machine learning.
Computationally, we relate PWSPDs on complete weighted graphs to their
analogues on weighted nearest neighbor graphs, providing high probability
guarantees on their equivalence that are near-optimal. Connections with
percolation theory are developed to establish estimates on the bias and
variance of PWSPDs in the finite sample setting. The theoretical results are
bolstered by illustrative experiments, demonstrating the versatility of PWSPDs
for a wide range of data settings. Throughout the paper, our results require
only that the underlying data is sampled from a low-dimensional manifold, and
depend crucially on the intrinsic dimension of this manifold, rather than its
ambient dimension.
