Kolev, Pavel ;
Mehlhorn, Kurt
A Note On Spectral Clustering
Abstract
Spectral clustering is a popular and successful approach for partitioning the nodes of a graph into clusters for which the ratio of outside connections compared to the volume (sum of degrees) is small. In order to partition into k clusters, one first computes an approximation of the bottom k eigenvectors of the (normalized) Laplacian of G, uses it to embed the vertices of G into kdimensional Euclidean space R^k, and then partitions the resulting points via a kmeans clustering algorithm. It is an important task for theory to explain the success of spectral clustering.
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 kth eigenvalue of the normalized Laplacian is sufficiently large. They proved 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 kmeans 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.
BibTeX  Entry
@InProceedings{kolev_et_al:LIPIcs:2016:6399,
author = {Pavel Kolev and Kurt Mehlhorn},
title = {{A Note On Spectral Clustering}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {57:157:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770156},
ISSN = {18688969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6399},
URN = {urn:nbn:de:0030drops63994},
doi = {10.4230/LIPIcs.ESA.2016.57},
annote = {Keywords: spectral embedding, kmeans clustering, power method, gap assumption}
}
2016
Keywords: 

spectral embedding, kmeans clustering, power method, gap assumption 
Seminar: 

24th Annual European Symposium on Algorithms (ESA 2016)

Issue date: 

2016 
Date of publication: 

2016 