Approximate Spectral Clustering: Efficiency and Guarantees
Approximate Spectral Clustering: Efficiency and Guarantees
复制标题
近似谱聚类：效率和保证
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
K. Mehlhorn
中科院分区：
文献类型：
--
作者：
Pavel Kolev;K. Mehlhorn
近似谱聚类(ASC)是一种流行且成功的启发式算法，用于将图G$的节点划分成外部连接与体积之比(度和)较小的簇。ASC由以下两个子程序组成：i)通过幂方法计算近似谱嵌入；ii)使用近似$k$-均值聚类算法对生成的向量集进行划分。由此产生的$k$-Means分区自然会导致$G$的$k$路节点分区。
我们在Peng等人~(SICOMP‘17)、Boutsidis等人~(ICML’15)和Ostrovsky等人~(JACM‘13)工作的基础上对ASC的建立进行了全面的分析。我们证明了ASC i)有效地运行，并且ii)产生了$G$的最优$k$路节点划分的良好近似值。此外，我们加强了对彭等人的一个结构结果的质量保证。同时弱化了本征值间隙假设。此外，我们证明了ASC找到了$G$的$k$路节点划分，并且具有加强的质量保证。
Approximate Spectral Clustering (ASC) is a popular and successful heuristic for partitioning the nodes of a graph $G$ 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 $k$-means clustering algorithm. The resulting $k$-means partition naturally induces a $k$-way node partition of $G$.
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 $k$-way node partition of $G$. Moreover, we strengthen the quality guarantees of a structural result of Peng et al. by a factor of $k$, and simultaneously weaken the eigenvalue gap assumption. Further, we show that ASC finds a $k$-way node partition of $G$ with the strengthened quality guarantees.