Graph Laplacians and Spectral Graph Theory

Matrix as Graph distinguishes adjacency, incidence, and transition matrices. Spectral graph theory asks how their eigenvalues reflect global structure. This first version assumes a finite, undirected graph with nonnegative weights.

Zero weights and connectivity

Zero-weight edges contribute no energy. The zero-eigenvalue multiplicity counts connected components of the positive-weight support graph. Treating a zero-weight edge as a genuine connection would break that statement. Here zero-weight edges are absent and graphs have no self-loops.

The Laplacian measures differences more directly than adjacency

Let $A$ be the adjacency matrix and $D=\operatorname{diag}(d_1,\ldots,d_n)$, where $d_i=\sum_j a_{ij}$. The combinatorial Laplacian is

$$L=D-A.$$

For a signal $\mathbf x$ on the vertices,

$$(L\mathbf x)_i=\sum_j a_{ij}(x_i-x_j).$$

It accumulates differences between one vertex and its neighbors. A constant signal has no differences, so $L\mathbf1=\mathbf0$.

The incidence matrix gives the same operator

Choose an arbitrary orientation for every undirected edge. Put $-1$ at its tail and $1$ at its head in the corresponding column of an incidence matrix $B$. If $W$ is the diagonal matrix of edge weights, then

$$L=BWB^{\mathsf T}.$$

Reversing one temporary orientation multiplies a column of $B$ by $-1$ and leaves the product unchanged. Orientation is bookkeeping here rather than part of the undirected graph.

Entrywise, the column for edge $\{i,j\}$ contributes $w_{ij}$ to diagonal positions $(i,i),(j,j)$ and $-w_{ij}$ to $(i,j),(j,i)$, with zero elsewhere. Summing edges gives precisely $D-A$, proving the incidence identity.

A quadratic form measures graph-signal roughness

The incidence factorization gives

$$\mathbf x^{\mathsf T}L\mathbf x =\sum_{\{i,j\}\in E}w_{ij}(x_i-x_j)^2\ge0.$$

Thus $L$ is symmetric positive semidefinite. The energy is small when adjacent values are close and large when the signal changes sharply across edges.

The energy vanishes exactly when values agree across every edge. A null vector is constant on each connected component, so the multiplicity of eigenvalue zero equals the number of connected components.

ProofKernel and connected components

If $L\mathbf x=0$, its energy is zero. Since every retained edge weight is positive, each squared difference is zero. Equality propagates along paths, making $\mathbf x$ constant on each component. Conversely such a signal gives $(L\mathbf x)_i=0$ directly from the neighbor-difference formula. The component indicators are independent (their supports are disjoint) and span all these signals. Thus the kernel dimension is exactly the number of components. The spectral theorem identifies this dimension with the algebraic multiplicity of zero.

The second eigenvalue measures the weakest connection

For a connected graph,

$$0=\lambda_1<\lambda_2\le\cdots\le\lambda_n.$$

The value $\lambda_2$ is the algebraic connectivity. The Rayleigh characterization is

$$\lambda_2=\min_{\mathbf x\perp\mathbf1,\,\mathbf x\ne0} \frac{\sum_{\{i,j\}}w_{ij}(x_i-x_j)^2}{\|\mathbf x\|^2}.$$

If a weak connection separates two clusters, a signal that is nearly constant on each side changes mainly across that cut and has low energy. The associated Fiedler vector can suggest a bipartition.

Assume $n\ge2$ here. Choose the first unit eigenvector as $\mathbf q_1=\mathbf1/\sqrt n$. A vector perpendicular to $\mathbf1$ has expansion $\sum_{i=2}^n c_i\mathbf q_i$, so its Rayleigh quotient is $\sum_{i=2}^n\lambda_i c_i^2/\sum_{i=2}^n c_i^2\ge\lambda_2$, with equality at $\mathbf q_2$. This proves the stated minimum.

For a cut into nonempty sets $S,T$, write $s=|S|$, $t=|T|$, and choose $x_i=\sqrt{t/s}$ on $S$ and $x_i=-\sqrt{s/t}$ on $T$. Then $\mathbf x\perp\mathbf1$, $\|\mathbf x\|^2=s+t=n$, and only crossing edges contribute. If their total weight is $c(S,T)$, the quotient is

$$R_L(\mathbf x)=c(S,T)\left(\frac1s+\frac1t\right).$$

This is the two-way RatioCut objective. Dropping the requirement that coordinates take these two values leaves exactly the Rayleigh minimization above. Thus $\lambda_2$ is a lower bound on the discrete objective, and a Fiedler vector solves this particular continuous relaxation. A rounding step need not recover the optimal discrete cut.

Normalized Laplacians account for degree

The combinatorial form weights high-degree vertices more heavily. When every degree is positive, define

$$L_{\mathrm{sym}}=I-D^{-1/2}AD^{-1/2}, \qquad L_{\mathrm{rw}}=I-D^{-1}A.$$

$L_{\mathrm{rw}}$ connects to a random-walk transition matrix, while $L_{\mathrm{sym}}$ is symmetric and supports the spectral theorem. Isolated vertices make $D^{-1}$ undefined and require an explicit convention or separate treatment.

Since $L_{\mathrm{sym}}=D^{-1/2}LD^{-1/2}$, it is positive semidefinite by substituting $D^{-1/2}\mathbf x$ in the energy formula. Moreover

$$D^{1/2}L_{\mathrm{rw}}D^{-1/2}=L_{\mathrm{sym}},$$

so these normalized Laplacians are similar and share their real nonnegative eigenvalues. This similarity uses positive degrees.

Reconcile row and column probability conventions

$D^{-1}A$ is row stochastic: it records transitions from starting vertices and acts on vertex functions. For the column probability states used earlier, instead use

$$P=AD^{-1},\qquad \mathbf p_{n+1}=P\mathbf p_n.$$

The two matrices are transposes. Left-multiplying a column probability vector by the row-stochastic matrix need not preserve total mass. In an undirected graph, normalized degrees form a stationary column distribution; a bipartite graph without self-loops can still produce periodic oscillation.

Indeed, with $s_d=\sum_i d_i>0$ and $\boldsymbol\pi=\mathbf d/s_d$, we have $AD^{-1}\boldsymbol\pi=A\mathbf1/s_d=\mathbf d/s_d$. Column sums of $AD^{-1}$ are one. On a bipartite graph, each step moves all mass to the opposite side, so starting on one side makes its total mass alternate between zero and one, proving possible nonconvergence.

From diffusion to spectral clustering

Continuous diffusion on a graph is

$$\mathbf x'(t)=-L\mathbf x(t), \qquad \mathbf x(t)=e^{-tL}\mathbf x(0).$$

High-eigenvalue modes decay quickly while constant modes remain. Spectral clustering maps vertices into coordinates given by several low-eigenvalue eigenvectors, then clusters those coordinates. It solves a continuous relaxation; a separate rounding or clustering step still produces discrete groups.

Directed graphs, signed weights, and hypergraphs require different Laplacian choices. The conclusions here do not transfer without checking their assumptions.

In an orthonormal eigenbasis the solution is $\sum_i e^{-t\lambda_i}(\mathbf q_i^{\mathsf T}\mathbf x(0))\mathbf q_i$. All positive modes vanish as $t\to\infty$. For a connected graph the remaining term is $\mathbf1\mathbf1^{\mathsf T}\mathbf x(0)/n$, the initial average at every vertex. For several components, projection onto each normalized component indicator gives its own initial average. Total signal is conserved because $(\mathbf1^{\mathsf T}\mathbf x)'=-\mathbf1^{\mathsf T}L\mathbf x=0$. This is diffusion for the combinatorial Laplacian; the degree-weighted random walk has a different stationary normalization.

Compute a three-vertex path

Use unit edges $1\!-!2$ and $2\!-!3$. Then

$$L=\begin{pmatrix}1&-1&0\\-1&2&-1\\0&-1&1\end{pmatrix}.$$

Direct multiplication shows that $(1,1,1)$, $(1,0,-1)$, and $(1,-2,1)$ have eigenvalues $0,1,3$. The second mode varies slowly between the endpoints; the third separates the middle vertex from both endpoints and has higher energy. Diffusion multiplies these modes by $1,e^{-t},e^{-3t}$ respectively.

Exercises

ExerciseA two-vertex graph

Find $L$ and its eigenvalues for two vertices joined by one unit-weight edge.

Solution

$L=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$ has eigenvalues $0$ and $2$, for the constant and difference directions.

ExerciseComponents and the nullspace

A graph has two disconnected components. Construct two independent vectors in $\ker L$.

Solution

Use the indicator vector of each component. Each is constant along every edge and the two supports are disjoint.

ExerciseOrientation does not change the Laplacian

Explain why multiplying one column of $B$ by $-1$ leaves $BB^{\mathsf T}$ unchanged.

Solution

That column contributes $\mathbf b\mathbf b^{\mathsf T}$. Replacing it by $-\mathbf b$ produces the same outer product.