Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding
Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding
复制标题
通过谱嵌入实现随机游走特征值的锐界
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
S. Gharan
中科院分区：
文献类型：
--
作者：
R. Lyons;S. Gharan
图的谱嵌入使用随机游走矩阵的前k个非平凡特征向量将图嵌入到R^k中。这种嵌入的主要用途是用于实际的谱聚类算法[SM 00，NJW 02]。最近，从理论角度研究了谱嵌入，以证明Cheeger不等式的高阶变体[LOT 12，LRTV 12]。
我们使用谱嵌入提供了一个统一的框架，绑定所有的特征值的图。例如，我们证明了对于任意n个顶点且k ≥ 2的有限图，其第k个最大特征值至多为1-Omega（k^3/n^3），这推广了文献[LO 81]中仅对k=2的结果。如果图是正则的，这个上界改进为1-Omega（k^2/n^2）。我们推广了这些结果，我们提供了尖锐的界限上的谱测度的各类图，包括顶点传递图和无限图，在特定的图形参数，如体积增长。
因此，使用整个频谱，我们提供（改进）上界的返回概率和混合时间的随机游动相当短，更直接的证明。我们的工作介绍谱嵌入作为一种新的工具，在分析可逆马尔可夫链。此外，在[Lyo 05]的基础上，我们设计了一个局部算法来近似大规模图的生成树数目。
Spectral embedding of graphs uses the top k non-trivial eigenvectors of the random walk matrix to embed the graph into R^k. The primary use of this embedding has been for practical spectral clustering algorithms [SM00,NJW02]. Recently, spectral embedding was studied from a theoretical perspective to prove higher order variants of Cheeger's inequality [LOT12,LRTV12].
We use spectral embedding to provide a unifying framework for bounding all the eigenvalues of graphs. For example, we show that for any finite graph with n vertices and all k >= 2, the k-th largest eigenvalue is at most 1-Omega(k^3/n^3), which extends the only other such result known, which is for k=2 only and is due to [LO81]. This upper bound improves to 1-Omega(k^2/n^2) if the graph is regular. We generalize these results, and we provide sharp bounds on the spectral measure of various classes of graphs, including vertex-transitive graphs and infinite graphs, in terms of specific graph parameters like the volume growth.
As a consequence, using the entire spectrum, we provide (improved) upper bounds on the return probabilities and mixing time of random walks with considerably shorter and more direct proofs. Our work introduces spectral embedding as a new tool in analyzing reversible Markov chains. Furthermore, building on [Lyo05], we design a local algorithm to approximate the number of spanning trees of massive graphs.