# Fermat Distances: Metric Approximation, Spectral Convergence, and Clustering Algorithms

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 56 references that are in the map.
- First posted on arXiv 7 Jul 2023.

## Builds on (most cited first, 15 of 15)

- [Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator](https://mlsanity.com/paper/1801.10108/) (2018)
- [Spectral convergence of diffusion maps: improved error bounds and an alternative normalisation](https://mlsanity.com/paper/2006.02037/) (2020)
- [Path-Based Spectral Clustering: Guarantees, Robustness to Outliers, and Fast Algorithms](https://mlsanity.com/paper/1712.06206/) (2017)
- [Balancing Geometry and Density: Path Distances on High-Dimensional Data](https://mlsanity.com/paper/2012.09385/) (2020)
- [The geometry of kernelized spectral clustering](https://mlsanity.com/paper/1404.7552/) (2014)
- [Multidimensional Scaling, Sammon Mapping, and Isomap: Tutorial and Survey](https://mlsanity.com/paper/2009.08136/) (2020)
- [Spectral Analysis Of Weighted Laplacians Arising In Data Clustering](https://mlsanity.com/paper/1909.06389/) (2019)
- [Geometric structure of graph Laplacian embeddings](https://mlsanity.com/paper/1901.10651/) (2019)
- [Power Weighted Shortest Paths for Clustering Euclidean Data](https://mlsanity.com/paper/1905.13345/) (2019)
- [Intrinsic persistent homology via density-based metric learning](https://mlsanity.com/paper/2012.07621/) (2020)
- [Minimax-optimal semi-supervised regression on unknown manifolds](https://mlsanity.com/paper/1611.02221/) (2016)
- [Approximating geodesics via random points](https://mlsanity.com/paper/1711.06952/) (2017)
- [Exact Computation of a Manifold Metric, via Lipschitz Embeddings and Shortest Paths on a Graph](https://mlsanity.com/paper/1709.07797/) (2017)
- [Hyperspectral Image Clustering with Spatially-Regularized Ultrametrics](https://mlsanity.com/paper/2004.05048/) (2020)
- [Clustering dynamics on graphs: from spectral clustering to mean shift through Fokker-Planck interpolation](https://mlsanity.com/paper/2108.08687/) (2021)

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

- [Learning Distances from Data with Normalizing Flows and Score Matching](https://mlsanity.com/paper/2407.09297/) (2024)
- [Probability Density Geodesics in Image Diffusion Latent Space](https://mlsanity.com/paper/2504.06675/) (2025)
- [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)
- [Manifold learning in metric spaces](https://mlsanity.com/paper/2503.16187/) (2025)
- [Geodesic Calculus on Implicitly Defined Latent Manifolds](https://mlsanity.com/paper/2510.09468/) (2025)
- [Combining Statistical Depth and Fermat Distance for Uncertainty Quantification](https://mlsanity.com/paper/2404.08476/) (2024)
- [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)
- [Learning Locally Adaptive Metrics that Enhance Structural Representation with textttLAMINAR](https://mlsanity.com/paper/2411.08557/) (2024)
- [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)

We analyze the convergence properties of Fermat distances, a family of density-driven metrics defined on Riemannian manifolds with an associated probability measure. Fermat distances may be defined either on discrete samples from the underlying measure, in which case they are random, or in the continuum setting, in which they are induced by geodesics under a density-distorted Riemannian metric. We prove that discrete, sample-based Fermat distances converge to their continuum analogues in small neighborhoods with a precise rate that depends on the intrinsic dimensionality of the data and the parameter governing the extent of density weighting in Fermat distances. This is done by leveraging novel geometric and statistical arguments in percolation theory that allow for non-uniform densities and curved domains. Our results are then used to prove that discrete graph Laplacians based on discrete, sample-driven Fermat distances converge to corresponding continuum operators. In particular, we show the discrete eigenvalues and eigenvectors converge to their continuum analogues at a dimension-dependent rate, which allows us to interpret the efficacy of discrete spectral clustering using Fermat distances in terms of the resulting continuum limit. The perspective afforded by our discrete-to-continuum Fermat distance analysis leads to new clustering algorithms for data and related insights into efficient computations associated to density-driven spectral clustering. Our theoretical analysis is supported with numerical simulations and experiments on synthetic and real image data.