Spectral Clustering on Large Datasets: When Does it Work? Theory from Continuous Clustering and Density Cheeger-Buser
Spectral clustering is one of the most popular clustering algorithms that has
stood the test of time. It is simple to describe, can be implemented using
standard linear algebra, and often finds better clusters than traditional
clustering algorithms like $k$-means and $k$-centers. The foundational
algorithm for two-way spectral clustering, by Shi and Malik, creates a
geometric graph from data and finds a spectral cut of the graph.
  In modern machine learning, many data sets are modeled as a large number of
points drawn from a probability density function. Little is known about when
spectral clustering works in this setting -- and when it doesn't. Past
researchers justified spectral clustering by appealing to the graph Cheeger
inequality (which states that the spectral cut of a graph approximates the
``Normalized Cut''), but this justification is known to break down on large
data sets.
  We provide theoretically-informed intuition about spectral clustering on
large data sets drawn from probability densities, by proving when a continuous
form of spectral clustering considered by past researchers (the unweighted
spectral cut of a probability density) finds good clusters of the underlying
density itself. Our work suggests that Shi-Malik spectral clustering works well
on data drawn from mixtures of Laplace distributions, and works poorly on data
drawn from certain other densities, such as a density we call the `square-root
trough'.
  Our core theorem proves that weighted spectral cuts have low weighted
isoperimetry for all probability densities. Our key tool is a new Cheeger-Buser
inequality for all probability densities, including discontinuous ones.