# Large sample spectral analysis of graph-based multi-manifold clustering

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 66 references that are in the map.
- First posted on arXiv 28 Jul 2021.

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

- [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)
- [A variational approach to the consistency of spectral clustering](https://mlsanity.com/paper/1508.01928/) (2015)
- [Spectral convergence of diffusion maps: improved error bounds and an alternative normalisation](https://mlsanity.com/paper/2006.02037/) (2020)
- [Lipschitz regularity of graph Laplacians on random data clouds](https://mlsanity.com/paper/2007.06679/) (2020)
- [Spectral Convergence of the connection Laplacian from random samples](https://mlsanity.com/paper/1306.1587/) (2013)
- [A simple SVD algorithm for finding hidden partitions](https://mlsanity.com/paper/1404.3918/) (2014)
- [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)
- [Spectral Clustering Based on Local PCA](https://mlsanity.com/paper/1301.2007/) (2013)
- [The geometry of kernelized spectral clustering](https://mlsanity.com/paper/1404.7552/) (2014)
- [Greedy Subspace Clustering](https://mlsanity.com/paper/1410.8864/) (2014)
- [Geometric structure of graph Laplacian embeddings](https://mlsanity.com/paper/1901.10651/) (2019)
- [Multiclass Total Variation Clustering](https://mlsanity.com/paper/1306.1185/) (2013)
- [Multiple Manifold Clustering Using Curvature Constrained Path](https://mlsanity.com/paper/1812.02327/) (2018)
- [An Adaptive Total Variation Algorithm for Computing the Balanced Cut of a Graph](https://mlsanity.com/paper/1302.2717/) (2013)
- [Scalable Sparse Subspace Clustering via Ordered Weighted ℓ1 Regression](https://mlsanity.com/paper/1807.03746/) (2018)
- [Path-Based Distance for Street Map Comparison](https://mlsanity.com/paper/1309.6131/) (2013)
- [Riemannian Multi-Manifold Modeling](https://mlsanity.com/paper/1410.0095/) (2014)

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

- [TRACE: Trajectory Recovery for Continuous Mechanism Evolution in Causal Representation Learning](https://mlsanity.com/paper/2601.21135/) (2026)
- [Eikonal depth: an optimal control approach to statistical depths](https://mlsanity.com/paper/2201.05274/) (2022)
- [On Linear Separation Capacity of Self-Supervised Representation Learning](https://mlsanity.com/paper/2310.19041/) (2023)
- [ACEV: Unsupervised Intersecting Manifold Segmentation using Adaptation to Angular Change of Eigenvectors in Intrinsic Dimension](https://mlsanity.com/paper/2410.00930/) (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)
- [Robust Tangent Space Estimation via Laplacian Eigenvector Gradient Orthogonalization](https://mlsanity.com/paper/2510.02308/) (2025)
- [SWING: Unlocking Implicit Graph Representations for Graph Random Features](https://mlsanity.com/paper/2602.12703/) (2026)

## Abstract (arXiv)

In this work we study statistical properties of graph-based algorithms for multi-manifold clustering (MMC). In MMC the goal is to retrieve the multi-manifold structure underlying a given Euclidean data set when this one is assumed to be obtained by sampling a distribution on a union of manifolds M = M1 cupdots cup MN that may intersect with each other and that may have different dimensions. We investigate sufficient conditions that similarity graphs on data sets must satisfy in order for their corresponding graph Laplacians to capture the right geometric information to solve the MMC problem. Precisely, we provide high probability error bounds for the spectral approximation of a tensorized Laplacian on M with a suitable graph Laplacian built from the observations; the recovered tensorized Laplacian contains all geometric information of all the individual underlying manifolds. We provide an example of a family of similarity graphs, which we call annular proximity graphs with angle constraints, satisfying these sufficient conditions. We contrast our family of graphs with other constructions in the literature based on the alignment of tangent planes. Extensive numerical experiments expand the insights that our theory provides on the MMC problem.