A Note on Spectral Clustering
Pavel Kolev, Kurt Mehlhorn · MPG.PuRe (Max Planck Society) · 2015
Let $G=(V,E)$ be an undirected graph, $\\lambda_k$ the $k$th smallest eigenvalue of the normalized Laplacian matrix of $G$, and $\\rho(k)$ the smallest value of the maximal conductance over all $k$-way partitions $S_1,\\dots,S_k$ of $V$. Peng et al. [PSZ15] gave the first rigorous analysis of $k$-clustering algorithms that use spectral embedding and $k$-means clustering algorithms to partition the vertices of a graph $G$ into $k$ disjoint subsets. Their analysis builds upon a gap parameter $\\Upsilon=\\rho(k)/\\lambda_{k+1}$ that was introduced by Oveis Gharan and Trevisan [GT14]. In their analysis Peng et al. [PSZ15] assume a gap assumption $\\Upsilon\\geq\\Omega(\\mathrm{APR}\\cdot k^3)$, where $\\mathrm{APR}>1$ is the approximation ratio of a $k$-means clustering algorithm. We exhibit an error in one of their Lemmas and provide a correction. With the correction the proof by Peng et al. [PSZ15] requires a stronger gap assumption $\\Upsilon\\geq\\Omega(\\mathrm{APR}\\cdot k^4)$. Our main contribution is to improve the analysis in [PSZ15] by an $O(k)$ factor. We demonstrate that a gap assumption $\\Psi\\geq \\Omega(\\mathrm{APR}\\cdot k^3)$ suffices, where $\\Psi=\\rho_{avr}(k)/\\lambda_{k+1}$ and $\\rho_{avr}(k)$ is the value of the average conductance of a partition $S_1,\\dots,S_k$ of $V$ that yields $\\rho(k)$.