paper

Approximate Spectral Clustering: Efficiency and Guarantees

arXiv:1509.09188

Abstract

Approximate Spectral Clustering (ASC) is a popular and successful heuristic 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. ASC consists of the following two subroutines: i) compute an approximate Spectral Embedding via the Power method; and ii) partition the resulting vector set with an approximate -means clustering algorithm. The resulting -means partition naturally induces a -way node partition of . We give a comprehensive analysis of ASC building on the work of Peng et al.~(SICOMP'17), Boutsidis et al.~(ICML'15) and Ostrovsky et al.~(JACM'13). We show that ASC i) runs efficiently, and ii) yields a good approximation of an optimal -way node partition of . Moreover, we strengthen the quality guarantees of a structural result of Peng et al. by a factor of , and simultaneously weaken the eigenvalue gap assumption. Further, we show that ASC finds a -way node partition of with the strengthened quality guarantees.

arXiv commentA preliminary version of this paper was presented at the 24th Annual European Symposium on Algorithms (ESA 2016)

References in corpus (2)

Cited by in corpus (1)