ResearchBlog‎ > ‎

Related tutorials/papers about convergence issue of spectral clustering

posted May 6, 2015, 10:05 AM by Teng-Yok Lee   [ updated May 6, 2015, 10:08 AM ]
I am applying spectral clustering for graph partitioning, but ARPACK can fail to converge to compute the eigenvectors of the smallest 20 eigenvalues. Then I found the following tutorials/papers about the convergence issue:

On the convergence of spectral clustering on random samples: the normalized case.
von Luxburg, U., Bousquet, O., and Belkin, M.
In Proceedings of the 17th Annual Conference on Learning Theory (COLT) (pp. 457 – 471). 2004.
Limits of spectral clustering.
von Luxburg, U., Bousquet, O., and Belkin, M.
Advances in Neural Information Processing Systems (NIPS) 17 (pp. 857 – 864), 2005.

A Tutorial on Spectral Clustering
Ulrike von Luxburg

One important thing I learn is that from the tutorial on spectral cluster:

We have to make sure that the eigenvalues of L corresponding to the eigenvectors used in unnormalized spectral clustering are significantly smaller than the minimal degree in the graph.

More detail are in the tutorial. It also introduces 2 ways to normalize.