Peng et al. (COLT, 2015) made an important step in this direction. They showed that spectral clustering provably works if the gap between the $(k+1)$-th and the $k$-th eigenvalue of the normalized Laplacian is sufficiently large. They prove a structural and an algorithmic result. The algorithmic result needs a considerably stronger gap assumption and does not analyze the standard spectral clustering paradigm; it replaces spectral embedding by heat kernel embedding and $k$-means clustering by locality sensitive hashing.
We extend their work in two directions. Structurally, we improve the quality guarantee for spectral clustering by a factor of $k$ and simultaneously weaken the gap assumption. Algorithmically, we show that the standard paradigm for spectral clustering works. Moreover, it even works with the same gap assumption as required for the structural result.