Spectral and density cluster hierarchies shown to match under conditions
Topological Equivalence of Spectral and Density Cluster Hierarchies
Machine Learning
Summary
This paper looks at two ways people group data points based on how dense the data is: using density to find clusters, and using a method based on graph distances. The authors found conditions where these two ways effectively give the same hierarchy of clusters after adjusting the scale. They also showed that when using nearest-neighbor graphs, the spectral method still matches the density-based clusters well with enough data.
What this means in practice
- •For data engineers: Design clustering algorithms that can rely on either spectral graph methods or density-level sets knowing they yield equivalent structures under certain conditions.
- •For machine learning platform builders: Develop scalable clustering tools using k-NN graphs with guarantees that the spectral methods reflect underlying density clusters accurately.
A theory result. No direct application yet.
Authors
Sajjad Hashemian
Abstract
We compare two canonical ways to recover hierarchical clustering from an underlying density $f$: the \emph{density cluster tree} given by connected components of superlevel sets $\{f\geλ\}$, and a \emph{spectral hierarchy} obtained by applying single linkage to diffusion distances induced by a Laplacian operator. We give conditions under which, at an appropriate diffusion time, the diffusion hierarchy is \emph{topologically equivalent} to the density cluster tree up to a monotone rescaling of heights. It further shows that a $k$-NN graph implementation inherits this equivalence from uniform approximation of diffusion distances, yielding a finite-sample reduction from spectral graph constructions to density-level-set topology.