Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap
Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap
复制标题
改进的 Cheeger 不等式：通过高阶谱间隙分析谱划分算法
DOI：
10.1145/2488608.2488611
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
L. Trevisan
中科院分区：
文献类型：
--
作者：
T. C. Kwok;L. Lau;Y. Lee;S. Gharan;L. Trevisan
设φ(G)为无向图G的最小电导，设0=λ<sub>1</sub>≤λ<sub>2</sub>≤…≤λ<sub>n</sub>≤2是G的归一化拉普拉斯矩阵的特征值。我们证明了对于任意图G和任意k≥2，[φ(G) = O(k) l<sub>2</sub>/√l<sub>k</sub>]，并通过谱划分算法实现了这一性能保证。这改进了Cheeger不等式，并且对于任意$k$，边界是最优的，直到一个常数因子。结果表明，当l<sub>k</sub>是某个常数k的常数时，谱划分算法是一种寻找稀疏切割的常数因子近似算法。这为其在图像分割和聚类问题中的经验性能提供了一定的理论依据。我们将分析扩展到其他图划分问题的谱算法，包括多路划分、平衡分隔和最大切割。
Let φ(G) be the minimum conductance of an undirected graph G, and let 0=λ<sub>1</sub> ≤ λ<sub>2</sub> ≤ ... ≤ λ<sub>n</sub> ≤ 2 be the eigenvalues of the normalized Laplacian matrix of G. We prove that for any graph G and any k ≥ 2, [φ(G) = O(k) l<sub>2</sub>/√l<sub>k</sub>,] and this performance guarantee is achieved by the spectral partitioning algorithm. This improves Cheeger's inequality, and the bound is optimal up to a constant factor for any $k$. Our result shows that the spectral partitioning algorithm is a constant factor approximation algorithm for finding a sparse cut if l<sub>k</sub> is a constant for some constant k. This provides some theoretical justification to its empirical performance in image segmentation and clustering problems. We extend the analysis to spectral algorithms for other graph partitioning problems, including multi-way partition, balanced separator, and maximum cut.