  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.
