21
$\begingroup$

Most of what I've seen about the spectral theory of the graph Laplacian concentrates on $\lambda_2$, the second-smallest eigenvalue. This eigenvalue contains information regarding the connectivity of the graph.

What can one learn from the rest of the eigenvalues and their associated eigenvectors? I'm not interested in special graphs -- e.g. regular graphs -- but large, messy graphs created from data.

Improve this question
$\endgroup$
11
  • 4
    $\begingroup$ John, are you familiar with, say, U. von Luxburg (2007), A tutorial on spectral clustering, Statistics and Computing, vol. 17, no. 4? If I recall (though I don't have it handy), there is at least one chapter of D. Skillicorn, Understanding Complex Datasets: Data Mining with Matrix Decompositions, Chapman and Hall/CRC, 2007 that discusses some high-level aspects, as well. $\endgroup$
    – cardinal
    Commented Jul 15, 2013 at 18:50
  • $\begingroup$ Thanks! I am not familiar with those references. $\endgroup$
    – John D. Cook
    Commented Jul 15, 2013 at 18:57
  • 1
    $\begingroup$ For the more mathematical point of view, see the recent survey arxiv.org/abs/1111.2897 by X.-D. Zhang. A classical way to infer something from the whole ensemble of eigenvalues is to take the product $\frac{\lambda_{2} \ldots \lambda_{n}}{n}$ which counts the spanning trees... $\endgroup$
    – Felix Goldberg
    Commented Jul 15, 2013 at 19:02
  • 1
    $\begingroup$ "The third largest eigenvalue roughly measures how hard it is to cut the graph into distinct pieces." --Leanne R. Silvia & Gary E. Davis $\endgroup$
    – Joseph O'Rourke
    Commented Jul 15, 2013 at 19:07
  • 3
    $\begingroup$ I recently asked a related question: mathoverflow.net/questions/136434/… $\endgroup$
    – Paul Siegel
    Commented Jul 15, 2013 at 21:35

5 Answers 5

Reset to default
6
$\begingroup$

I came across some exciting references to 'holistic spectral data' while watching this great talk by prof. James Lee at UWashington, so it might be worth giving a look. The slides are here. A little search turned up some interesting results:

  1. At arount 28:00 in the talk, he mentions that if $\lambda_i$ and $v_i$ are the eigenvalues (in increasing order) and eigenvectors of the Laplacian, and $g_i$ are random $\mathcal{N}(0,1)$ Gaussians, we have $$\text{cover time of $G$} \asymp |V| \left\|\sum_{i=2}\frac{g_i}{\sqrt{\lambda_i}}v_i \right\|_\infty $$ in the sense of tight concentration. Wow! The quantity in the infinity norm, Lee claims, is called the Gaussian mean field and is useful in other contexts.
  2. At around 30:00 he continues discussing 'holistic spectral data', mentioning how the above spectral characterization helps us prove things about cover time. Examples from electrical networks follow.
  3. In the paper http://arxiv.org/abs/1111.1055, Lee, Gharan and Trevisan resolve a conjecture saying that there are $k$ eigenvalues close to zero, the graph can be partitioned into $k$ parts with small cuts between them (this was alluded to in the comments).
Improve this answer
$\endgroup$
5
$\begingroup$

Besides the already mentioned article by Lee, Gharan and Trevisan, let me mention two aspects of the theory of higher eigenvalues:

  • The possibly earliest appearance of the graph Laplacian dates back to 1973: W.E. Donath, A.J. Hoffman, Lower bounds for the partitioning of graphs, IBM J. Res. Develop. The main theorem of that paper gives an estimate on the number of estimates that are necessary in order to cut the graph into $k$ parts in terms of a weighted sum of the $k$ largest eigenvalues of the Laplacian.

  • E.B. Davies, G.M.L. Gladwell, J. Leydold and P.F. Stadler have written in 2001 an article where Courant's nodal domain theorem is extended to graphs: Discrete nodal domain theorems, Lin. Alg. Appl.

Improve this answer
$\endgroup$
3
$\begingroup$

One thing I've learned after asking this question is spectral coordinates and the analogy with Fourier analysis. From a blog post:

The eigenvectors associated with the smallest eigenvalues of the graph Laplacian are analogous to low frequency sines and cosines. The eigenvalue components corresponding to nearly vertices in a graph should be close together. This analogy explains why spectral coordinates work so well.

Improve this answer
$\endgroup$
1
  • $\begingroup$ oh, right, I completely forgot about the Fourier stuff. speaking of which here is a paper that defines analogues of many standard tools from Fourier analysis for graphs. $\endgroup$
    – amakelov
    Commented May 8, 2016 at 11:00
1
$\begingroup$

You might be interested in this recent work studying the eigenvector of Laplacian of a graph.

Wang, X. and P. Van Mieghem, 2015, "Orthogonal Eigenvector Matrix of the Laplacian", Fourth International IEEE Workshop on Complex Networks and their Applications, November 23-27, Bangkok, Thailand.

https://www.nas.ewi.tudelft.nl/people/Piet/papers/SITIS2015_OrthogonalZMatrix.pdf

Improve this answer
$\endgroup$
0
$\begingroup$

If you know the isoperimetric properties of the graph, you can obtain lower bounds on some of its higher eigenvalues based on its isoperimetric dimension and constant. It is discrete analog of the Poincare inequality.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .