# Balancing Geometry and Density: Path Distances on High-Dimensional Data

arXiv: https://arxiv.org/abs/2012.09385 · HTML: https://mlsanity.com/paper/2012.09385/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Dec 2020.

## Built on by (most cited first, 16 of 16)

- [Geometric Scattering on Measure Spaces](https://mlsanity.com/paper/2208.08561/) (2022)
- [Fermat Distances: Metric Approximation, Spectral Convergence, and Clustering Algorithms](https://mlsanity.com/paper/2307.05750/) (2023)
- [Learning Distances from Data with Normalizing Flows and Score Matching](https://mlsanity.com/paper/2407.09297/) (2024)
- [Large sample spectral analysis of graph-based multi-manifold clustering](https://mlsanity.com/paper/2107.13610/) (2021)
- [Pulling back symmetric Riemannian geometry for data analysis](https://mlsanity.com/paper/2403.06612/) (2024)
- [Pullback Flow Matching on Data Manifolds](https://mlsanity.com/paper/2410.04543/) (2024)
- [Hamilton-Jacobi equations on graphs with applications to semi-supervised learning and data depth](https://mlsanity.com/paper/2202.08789/) (2022)
- [A Convergence Rate for Manifold Neural Networks](https://mlsanity.com/paper/2212.12606/) (2022)
- [Continuum Limits of Ollivier's Ricci Curvature on data clouds: pointwise consistency and global lower bounds](https://mlsanity.com/paper/2307.02378/) (2023)
- [Manifold Learning with Normalizing Flows: Towards Regularity, Expressivity and Iso-Riemannian Geometry](https://mlsanity.com/paper/2505.08087/) (2025)
- [Choosing the parameter of the Fermat distance: navigating geometry and noise](https://mlsanity.com/paper/2311.18663/) (2023)
- [Clustering dynamics on graphs: from spectral clustering to mean shift through Fokker-Planck interpolation](https://mlsanity.com/paper/2108.08687/) (2021)
- [Static and Dynamic Approaches to Computing Barycenters of Probability Measures on Graphs](https://mlsanity.com/paper/2603.26940/) (2026)
- [High-dimensional Semi-supervised Classification via the Fermat Distance](https://mlsanity.com/paper/2604.23573/) (2026)
- [K-means with learned metrics](https://mlsanity.com/paper/2603.14601/) (2026)
- [Fermat Active Laplace Learning for Semi-Supervised Hyperspectral Image Classification](https://mlsanity.com/paper/2608.02483/) (2026)

## Abstract (arXiv)

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.