A Tighter Analysis of Spectral Clustering, and Beyond

Peter Macgregor, He Sun

This work studies the classical spectral clustering algorithm which embeds the vertices of some graph $G=(V_G,E_G)$ into ${\mathbb{R}}^k$ using $k$ eigenvectors of some matrix of $G…