Spectral Graph Theory

Throughout, let $A\in {\mathbb{R}}^{n\times n}$ be the adjacency matrix of a graph, and $D\in {\mathbb{R}}^{n\times n}$ be the diagonal (in)degree matrix.

Adjacency

$$A_{ij}=1⟺\text{there is a link from j to i}.$$

Properties

• For connected undirected graphs and irreducible directed graphs, the leading eigenvector of $A$ corresponding to the largest eigenvalue is the only eigenvector with elements all non-negative. Moreover, it has strictly positive elements.

Markov

A Random Walk on a graph is a Markov Chain with kernel

$$P=D^{-1}A$$

Properties

• The is a row-stochastic matrix, so ${\lambda }_1=1$ is an eigenvalue with the corresponding eigenvector $1$.
• 1 is the largest eigenvalue, with its multiplicity equal to the number of CCs (undirected) or terminal SCCs (recurrent classes, directed).
• A simple proof of the Mixing Property: let ${\mu }_0=\pi +x_0$, where $x_0\perp \pi$. Then $\Vert {\mu }_0{P}^t-\pi \Vert =\Vert x_0{P}^t\Vert$; since $x_0$ lies in the subspace spanned by the eigenvectors corresponding to eigenvalues other than 1, $\Vert x_0{P}^t\Vert \le |{\lambda }_2{|}^t\Vert x_0\Vert$.
• The mixing rate is captured by the spectral gap $1-|{\lambda }_2|$.
• For undirected graphs, $P$ corresponds to a reversible Markov chain with steady-state distribution ${\pi }_i=d_i/d$.
  • ${\pi }^{T}P=\pi$ and ${\pi }_i{P}_{ij}=A_{ij}/d=A_{ji}/d={\pi }_j{P}_{ji}$.
  • Conversely, every reversible Markov chain can be represented as a random walk on an undirected graph with edge weights $A_{ij}={\pi }_i{P}_{ij}$.
  • We further have $|P_t(ij)-{\pi }_j|\le \sqrt{{\pi }_j/{\pi }_i}|{\lambda }_2{|}^t$.
• Note that for an undirected graph, $D^{1/2}(D^{-1}A)D^{-1/2}=D^{-1/2}A{D}^{-1/2}$ is symmetric, and thus $P$ has real eigenvalues. Then, we can sort the eigenvalues by their values (not absolute values) and the spectral gap becomes $1-\max \{|{\lambda }_2|,|{\lambda }_n|\}$

Laplacian

For undirected graphs, we define the graph Laplacian as

$$L=D-A.$$

Properties

• $L$ is positive semidefinite, and the multiplicity of the zero eigenvalue of $L$ equals the number of CCs in the graph, with the eigenvectors being indicators of the CCs.
• Let $s\in \{-1,+1{\}}^n$ specify a partition of the nodes into two sets. Then $s^{T}Ls=4|\delta (s)|$, where $\delta (s)$ is the cut set (edges that connect two sets) of the partition. ^spectral-partition
  • $\begin{array}{rl}{s}^{T}Ls=& s^{T}Ds-s^{T}As\\ =& \sum _i{d}_i-\sum _{ij}{s}_i{A}_{ij}{s}_j\\ =& \sum _i{d}_i-\sum _{ij}|s_i|A_{ij}|s_j|+2\sum _{ij}1\{s_i\ne s_j\}{A}_{ij}\\ =& 4\sum _{j>i}1\{s_i\ne s_j\}{A}_{ij}\\ =& 4|\delta (s)|.\end{array}$