Balancing Geometry and Density: Path Distances on High-Dimensional Data
This work provides a deeper theoretical understanding of PWSPDs for researchers working with high-dimensional data sampled from low-dimensional manifolds, particularly in unsupervised and semi-supervised machine learning.
This paper analyzes power-weighted shortest-path distances (PWSPDs), clarifying how they balance data density and geometry. It provides near-optimal high probability guarantees for their equivalence on complete vs. nearest neighbor graphs and estimates their bias and variance in finite samples.
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.