Sharp bounds on random walk eigenvalues via spectral embedding

DOI10.1093/IMRN/RNX082MaRDI QIDQ5233822zbMATH OpenOpenAlexFDO

Authors

Publication date 9 September 2019

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.0589

zbMATH Keywords

matrix-tree theoremrandom walksuniform spanning forests

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random walks on graphs (05C81)

Abstract: 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.

Recommendations

• Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians
• Spectral graph theory via higher order eigenvalues and applications to the analysis of random walks
• Sharp spectral bounds of several graph parameters using eigenvector norms
• Metric uniformization and spectral bounds for graphs
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows

Cited in

(19)

• Conformal growth rates and spectral geometry on distributional limits of graphs
• Explicit universal minimal constants for polynomial growth of groups
• Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians
• The social network model on infinite graphs
• A comparison principle for random walk on dynamical percolation
• The exclusion process mixes (almost) faster than independent particles
• Upper bounds for the spectral function on homogeneous spaces via volume growth
• Estimating graph parameters with random walks
• Sparse expanders have negative curvature
• Sensitivity of mixing times in Eulerian digraphs
• Rotor walks on transient graphs and the wired spanning forest
• Three conjectures of Ostrander on digraph Laplacian eigenvectors
• Spectral graph theory via higher order eigenvalues and applications to the analysis of random walks
• On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
• Multiple random walks on graphs: mixing few to cover many
• Spread of information and diseases via random walks in sparse graphs
• The asynchronous DeGroot dynamics
• On eigenvalue problems for the random walks on the Sierpinski pre- gaskets
• Occupation measure of random walks and wired spanning forests in balls of Cayley graphs

This page was built for publication: Sharp bounds on random walk eigenvalues via spectral embedding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233822)