论文标题
光谱集群的性能保证
A Performance Guarantee for Spectral Clustering
论文作者
论文摘要
两步光谱聚类方法由Laplacian eigenmap和一个圆形步骤组成，是一种广泛使用的图形分区方法。它可以看作是自然放松与最低比率削减问题的自然放松。在本文中，我们研究了一个中心问题：何时能够找到对最小比率削减问题的全球解决方案？首先，我们提供的条件自然取决于给定分区的内部和集群间连接性，我们可以证明该分区是解决最小比率削减问题的解决方案。然后，我们为与$ k $最小的特征值相对应的图形laplacian的不变子空间开发了一个确定性的两到赋形标准扰动。最后，通过结合这两个结果，我们给出了一个条件，在该条件下，保证光谱聚类可以将全局解决方案输出到最小比率削减问题，这是光谱群集的性能保证。
The two-step spectral clustering method, which consists of the Laplacian eigenmap and a rounding step, is a widely used method for graph partitioning. It can be seen as a natural relaxation to the NP-hard minimum ratio cut problem. In this paper we study the central question: when is spectral clustering able to find the global solution to the minimum ratio cut problem? First we provide a condition that naturally depends on the intra- and inter-cluster connectivities of a given partition under which we may certify that this partition is the solution to the minimum ratio cut problem. Then we develop a deterministic two-to-infinity norm perturbation bound for the the invariant subspace of the graph Laplacian that corresponds to the $k$ smallest eigenvalues. Finally by combining these two results we give a condition under which spectral clustering is guaranteed to output the global solution to the minimum ratio cut problem, which serves as a performance guarantee for spectral clustering.
