# Path-Based Spectral Clustering: Guarantees, Robustness to Outliers, and Fast Algorithms

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

## Key facts

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

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

- [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)
- [A Multiscale Environment for Learning by Diffusion](https://mlsanity.com/paper/2102.00500/) (2021)
- [Large sample spectral analysis of graph-based multi-manifold clustering](https://mlsanity.com/paper/2107.13610/) (2021)
- [Hamilton-Jacobi equations on graphs with applications to semi-supervised learning and data depth](https://mlsanity.com/paper/2202.08789/) (2022)
- [Affinity Clustering Framework for Data Debiasing Using Pairwise Distribution Discrepancy](https://mlsanity.com/paper/2306.01699/) (2023)
- [UniForCE: The Unimodality Forest Method for Clustering and Estimation of the Number of Clusters](https://mlsanity.com/paper/2312.11323/) (2023)
- [EmbedOR: Provable Cluster-Preserving Visualizations with Curvature-Based Stochastic Neighbor Embeddings](https://mlsanity.com/paper/2509.03703/) (2025)
- [Clustering dynamics on graphs: from spectral clustering to mean shift through Fokker-Planck interpolation](https://mlsanity.com/paper/2108.08687/) (2021)
- [Min-Max-Jump distance and its applications](https://mlsanity.com/paper/2301.05994/) (2023)
- [TANGO: Clustering with Typicality-Aware Nonlocal Mode-Seeking and Graph-Cut Optimization](https://mlsanity.com/paper/2408.10084/) (2024)
- [High-dimensional Semi-supervised Classification via the Fermat Distance](https://mlsanity.com/paper/2604.23573/) (2026)
- [LINSCAN -- A Linearity Based Clustering Algorithm](https://mlsanity.com/paper/2406.17952/) (2024)
- [CoreSPECT: Enhancing Clustering Algorithms via an Interplay of Density and Geometry](https://mlsanity.com/paper/2507.08243/) (2025)
- [Robust Multi-Manifold Clustering via Simplex Paths](https://mlsanity.com/paper/2507.10710/) (2025)
- [Fermat Active Laplace Learning for Semi-Supervised Hyperspectral Image Classification](https://mlsanity.com/paper/2608.02483/) (2026)

## Abstract (arXiv)

We consider the problem of clustering with the longest-leg path distance (LLPD) metric, which is informative for elongated and irregularly shaped clusters. We prove finite-sample guarantees on the performance of clustering with respect to this metric when random samples are drawn from multiple intrinsically low-dimensional clusters in high-dimensional space, in the presence of a large number of high-dimensional outliers. By combining these results with spectral clustering with respect to LLPD, we provide conditions under which the Laplacian eigengap statistic correctly determines the number of clusters for a large class of data sets, and prove guarantees on the labeling accuracy of the proposed algorithm. Our methods are quite general and provide performance guarantees for spectral clustering with any ultrametric. We also introduce an efficient, easy to implement approximation algorithm for the LLPD based on a multiscale analysis of adjacency graphs, which allows for the runtime of LLPD spectral clustering to be quasilinear in the number of data points.