Spectral Graph Theory

\(L = D - A\)

Also called

• Graph Laplacian
• Admittance matrix
• Discrete Laplacian

Laplacian matrix is the discrete form of Laplace Operator obtained by using finite difference method. It relates to many properties of the graph:

• Number of spanning trees of the graph using Kirchoff's theorem
• Sparsest cut can be approximated using Fiedler vector
• Spectral decomposition gives low dimensional embeddings for use in Machine Learning applications
• Signal processing based on graph fourier transform uses eigenvectors of laplacian matrix as the basis
• Multiplicity of zero eigenvalue gives the number of connected components of the graph.

Spectral methods apply well to graphs with a lot of structure, such as strongly regular graphs. The eigenvalue and eigenvectors of the graph laplacian have a concrete interpretation from physics based on three natural differential equations: (From math.stackexchange.com)

1. The wave equation: Eigenvectors are the harmonics of the graph. They describe the standing wave solution of the wave equation. And eigenvalues describe the frequency of those harmonics.
2. The heat equation: Eigenvectors are still the harmonics of the graph. The eigenvalues describe the rate at which heat decays for each harmonics. This is also about Brownian motion on the graphs, and related to random walks.
3. The Schrodinger equation: Eigenvectors are energy eigenstates of a continuous time quantum random walk (??), and eigenvalues are energy eigenvalues.

When the graph is regular, the laplacian and adjacency matrix are related in simple way: eigenvectors are same, and eigenvalues are related by simple relation. For irregular graphs, the relation is quite complicated.

(From The Unreasonable Effectiveness of Spectral Graph Theory [youtube.com])

Think of the heat flow problem. At each timestep we can update the temperature of each node to be average of its temperature and its neighbour's temperature:

\[ u_i = \frac 1 2 u_i + \frac 1 {2d} \sum_{j \sim i} u_j \]

(The factor \(1/2\) can be any other constant.)

If the graph is connected, eventually all the nodes will have same temperature. This can be modelled by a Random Walk matrix \(W\).

\begin{align*} W_{ii} &= \frac 1 2 \\ W_{ij} &= \frac 1 {2d} \textrm{ for } j \sim i \end{align*}

Diagonalizing this matrix allows for an understanding of heat flow through its eigenbasis. This spectrum of the walk matrix has the following properties for a connected graph:

• The first eigenvalue is 1 with eignevector \((1, 1, ..., 1)\).

  This is the steady state uniform heat distribution.

• All other eigenvalues will be less than 1.

  This means as we repeatedly update \(u\), by multiplying with \(W\), all other eigenvector componentets will die off and only the steady state component (eignevalue 1) remains.

• The second eignevalue thus gives us the hint of the rate at which average value will propagate. It is also another way to look at connectedness of the graph. If the graph has a bottleneck, it will take long time to transfer heat from one part to another. Such, graphs with bottleneck will have larger second eigenvalue.

Alternatively we can look at the laplacian matrix: \(L = I - W\). All the results hold but the equations look a bit nicer.

• The eigenvalues will be 1 - previous eigenvalue
• Lowest eigenvalue will be zero
• The first non zero eignvalue will give the connectedness