English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Spectral embedding of graphs uses the top k non-trivial eigenvectors of therandom walk matrix to embed the graph into R^k. The primary use of thisembedding has been for practical spectral clustering algorithms [SM00,NJW02].Recently, spectral embedding was studied from a theoretical perspective toprove higher order variants of Cheeger's inequality [LOT12,LRTV12].  We use spectral embedding to provide a unifying framework for bounding allthe eigenvalues of graphs. For example, we show that for any finite graph withn vertices and all k >= 2, the k-th largest eigenvalue is at most1-Omega(k^3/n^3), which extends the only other such result known, which is fork=2 only and is due to [LO81]. This upper bound improves to 1-Omega(k^2/n^2) ifthe graph is regular. We generalize these results, and we provide sharp boundson the spectral measure of various classes of graphs, includingvertex-transitive graphs and infinite graphs, in terms of specific graphparameters like the volume growth.  As a consequence, using the entire spectrum, we provide (improved) upperbounds on the return probabilities and mixing time of random walks withconsiderably shorter and more direct proofs. Our work introduces spectralembedding as a new tool in analyzing reversible Markov chains. Furthermore,building on [Lyo05], we design a local algorithm to approximate the number ofspanning trees of massive graphs.

Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding