Spectral Clustering by Recursive Partitioning

Full textClick to download.
Citationin Proceedings of the 2006 European Symposium on Algorithms.
AuthorsAnirban Dasgupta
John Hopcroft
Ravi Kannan
Pradipta Mitra


In this paper, we analyze the second eigenvector technique of spectral partitioning on the planted partition random graph model, by constructing a recursive algorithm using the second eigenvectors in order to learn the planted partitions. The correctness of our algorithm is not based on the ratio-cut interpretation of the second eigenvector, but exploits instead the stability of the eigenvector subspace. As a result, we get an improved cluster separation bound in terms of dependence on the maximum variance. We also extend our results for a clustering problem in the case of sparse graphs.

Back to publications
Back to previous page