# Cluster Trees on Manifolds

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jul 2013.

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

- [Learning with Density Matrices and Random Features](https://mlsanity.com/paper/2102.04394/) (2021)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs](https://mlsanity.com/paper/2106.01529/) (2021)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs](https://mlsanity.com/paper/2111.07394/) (2021)
- [An Axiomatic Definition of Hierarchical Clustering](https://mlsanity.com/paper/2407.03574/) (2024)
- [Optimal rates for density and mode estimation with expand-and-sparsify representations](https://mlsanity.com/paper/2602.06175/) (2026)

## Abstract (arXiv)

In this paper we investigate the problem of estimating the cluster tree for a density f supported on or near a smooth d-dimensional manifold M isometrically embedded in ℝD. We analyze a modified version of a k-nearest neighbor based algorithm recently proposed by Chaudhuri and Dasgupta. The main results of this paper show that under mild assumptions on f and M, we obtain rates of convergence that depend on d only but not on the ambient dimension D. We also show that similar (albeit non-algorithmic) results can be obtained for kernel density estimators. We sketch a construction of a sample complexity lower bound instance for a natural class of manifold oblivious clustering algorithms. We further briefly consider the known manifold case and show that in this case a spatially adaptive algorithm achieves better rates.