Item

Abstract

Consistency is a key property of statistical algorithms when the data
is drawn from some underlying probability distribution. Surprisingly,
despite decades of work, little is known about consistency of most
clustering algorithms. In this paper we investigate consistency of
the popular family of spectral clustering algorithms, which clusters
the data with the help of eigenvectors of graph Laplacian matrices. We
develop new methods to establish that for increasing sample size,
those eigenvectors converge to the eigenvectors of certain limit
operators. As a result we can prove that one of the two major classes
of spectral clustering (normalized clustering) converges under very
general conditions, while the other (unnormalized clustering) is only
consistent under strong additional assumptions, which are not always
satisfied in real data. We conclude that our analysis provides strong
evidence for the superiority of normalized spectral clustering.