MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
4  
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. – cardinal Jul 15 '13 at 18:50
    
Thanks! I am not familiar with those references. – John D. Cook Jul 15 '13 at 18:57
1  
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... – Felix Goldberg Jul 15 '13 at 19:02
1  
"The third largest eigenvalue roughly measures how hard it is to cut the graph into distinct pieces." --Leanne R. Silvia & Gary E. Davis – Joseph O'Rourke Jul 15 '13 at 19:07
3  
I recently asked a related question: mathoverflow.net/questions/136434/… – Paul Siegel Jul 15 '13 at 21:35
up vote 4 down vote accepted

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).
share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer
    
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. – amakelov May 8 at 11:00

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

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.