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: One important thing I learn is that from the tutorial on spectral cluster: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 2007 arXiv:0711.0189 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. |
ResearchBlog >