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.

$\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
    Jul 15, 2013 at 18:50
  • $\begingroup$ Thanks! I am not familiar with those references. $\endgroup$ 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$ 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$ Jul 15, 2013 at 19:07
  • 3
    $\begingroup$ I recently asked a related question: mathoverflow.net/questions/136434/… $\endgroup$ Jul 15, 2013 at 21:35

5 Answers 5

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).
$\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.

$\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.

$\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
    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

$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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