# Item

ITEM ACTIONSEXPORT

Released

Paper

#### A Note On Spectral Clustering

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:1509.09188.pdf

(Preprint), 251KB

1509.09188v3.pdf

(Preprint), 353KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Kolev, P., & Mehlhorn, K. (2015). A Note On Spectral Clustering. Retrieved from http://arxiv.org/abs/1509.09188.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0028-8F4F-A

##### Abstract

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)$.