Note that there's two different "graph matrices" that people consider spectra of:

1. The _adjacency matrix_ as you discuss above.

2. The _Laplacian matrix_ which is defined as $\sum_i d_i e_{i i} - \sum_{i,j\in E} e_{i j}$, i.e. putting the degree (number of incident edges) on the diagonal with the opposite signs to actual edges.

Firstly note that both these matrices are hermitian, so all eigenvalues are real and all eigenvectors are orthogonal. One of the things about the Laplacian matrix is "diagonally dominant", which amongst other things means the spectrum is well defined. Now if you scale the edges of the adjacency graph there's the straightforward connection that an eigenvector corresponds to the probability of where a particle will end up after a huge number of "uniformly random" steps if its initial distribution is uniform over all the nodes. This is of practical use, since if you think that the eigenvector of an enormous adjacency matrix is a solution, you can get an approximate eigenvector by summing lots of a random walks statistics.

For the Laplacian matrix there's [spectral partitioning](http://en.wikipedia.org/wiki/Graph_partition#Spectral_partitioning_and_spectral_bisection), which shows that eigenvectors are related to partitions that minimise certain weigh functions over cuts which divde the graph into various partitions.

One final interesting thing, which I'm interested in a lot, is the question: is there an analogue of "mulit-scale" decompositions like wavelets and fourier decompositions are for "1-D data" for "data on a graph"? One popular way to do this is to say "in the 1-D case we have various "basis functions" (sines, cosines of various frequencies), these turn out to be eigenfunctions fo certain differential equation kernels, and we know how to define similar kernels on graphs and numerically solve for eigenfunctions and say these define the multiscale decomposition basis functions". If you do this, it's related to graph spectra. I'm not too keen on this approach because it doesn't have that many nice properties, but I'm not aware of anything better.

There's plenty more stuff around, but these show graph spectra have lots of connections.

1. The _adjacency matrix_ as you discuss above.

2. The _Laplacian matrix_ which is defined as $\sum_i d_i e_{i i} - \sum_{i,j\in E} e_{i j}$, i.e. putting the degree (number of incident edges) on the diagonal with the opposite signs to actual edges.

Firstly note that both these matrices are hermitian, so all eigenvalues are real and all eigenvectors are orthogonal. One of the things about the Laplacian matrix is "diagonally dominant", which amongst other things means the spectrum is well defined. Now if you scale the edges of the adjacency graph there's the straightforward connection that an eigenvector corresponds to the probability of where a particle will end up after a huge number of "uniformly random" steps if its initial distribution is uniform over all the nodes. This is of practical use, since if you think that the eigenvector of an enormous adjacency matrix is a solution, you can get an approximate eigenvector by summing lots of a random walks statistics.

For the Laplacian matrix there's [spectral partitioning](http://en.wikipedia.org/wiki/Graph_partition#Spectral_partitioning_and_spectral_bisection), which shows that eigenvectors are related to partitions that minimise certain weigh functions over cuts which divde the graph into various partitions.

One final interesting thing, which I'm interested in a lot, is the question: is there an analogue of "mulit-scale" decompositions like wavelets and fourier decompositions are for "1-D data" for "data on a graph"? One popular way to do this is to say "in the 1-D case we have various "basis functions" (sines, cosines of various frequencies), these turn out to be eigenfunctions fo certain differential equation kernels, and we know how to define similar kernels on graphs and numerically solve for eigenfunctions and say these define the multiscale decomposition basis functions". If you do this, it's related to graph spectra. I'm not too keen on this approach because it doesn't have that many nice properties, but I'm not aware of anything better.

There's plenty more stuff around, but these show graph spectra have lots of connections.