Lesson overview | Previous part | Next part

Spectral Graph Theory: Part 7: Spectral Filtering to 13. Common Mistakes

7. Spectral Filtering

7.1 Filtering in the Spectral Domain

A spectral filter on a graph is an operation that modifies the frequency content of a graph signal:

$$\mathbf{y} = g(L)\mathbf{x} = U g(\Lambda) U^\top \mathbf{x}$$

where $g: \mathbb{R} \to \mathbb{R}$ is a scalar function applied pointwise to the eigenvalues: $g(\Lambda) = \operatorname{diag}(g(\lambda_1), g(\lambda_2), \ldots, g(\lambda_n))$.

Common filters:

Implementation cost: Directly computing $U g(\Lambda) U^\top \mathbf{x}$ requires the full eigendecomposition - $O(n^3)$ preprocessing and $O(n^2)$ per signal. This is intractable for large graphs. Polynomial approximation (7.2) reduces cost to $O(K|E|)$ per signal.

7.2 Polynomial Filters and Localization

A $K$-th order polynomial filter has the form:

$$g(L) = \sum_{k=0}^K \theta_k L^k$$

Key property: K-localization. The filter $g(L) = \sum_{k=0}^K \theta_k L^k$ is exactly $K$-localized: $(g(L)\mathbf{x})_i$ depends only on the values of $\mathbf{x}$ at vertices within graph distance $K$ from $i$.

Proof. $(L^k)_{ij} = 0$ whenever $\text{dist}(i,j) > k$ (by the walk-counting property of graph matrix powers). Therefore $(g(L))_{ij} = \sum_k \theta_k (L^k)_{ij} = 0$ whenever $\text{dist}(i,j) > K$.

Complexity. Computing $\mathbf{y} = g(L)\mathbf{x}$ using the recurrence $L^k \mathbf{x} = L \cdot (L^{k-1}\mathbf{x})$ requires $K$ sparse matrix-vector multiplications, each $O(|E|)$. Total: $O(K|E|)$.

Spatial interpretation. A polynomial filter is exactly equivalent to a $K$-hop neighborhood aggregation, connecting spectral and spatial GNN views. This is the theoretical justification for why GNNs with $K$ layers aggregate information from $K$-hop neighborhoods.

Approximation theorem. By the Stone-Weierstrass theorem, any continuous function $g: [0, \lambda_{\max}] \to \mathbb{R}$ can be uniformly approximated by polynomials. So polynomial filters are universal approximators for spectral filters on any graph.

7.3 Chebyshev Polynomial Approximation

Why Chebyshev? Among all polynomials of degree $\leq K$, the $K$-th Chebyshev polynomial $T_K$ has the smallest maximum deviation from zero on $[-1, 1]$ - it is the optimal polynomial approximation basis.

Definition. The Chebyshev polynomials $T_k: [-1, 1] \to [-1, 1]$ satisfy:

$$T_0(x) = 1, \quad T_1(x) = x, \quad T_k(x) = 2x T_{k-1}(x) - T_{k-2}(x)$$

They have the closed form $T_k(x) = \cos(k \arccos x)$.

Chebyshev graph filter (ChebNet, Defferrard et al., 2016). Scale the Laplacian to $\tilde{L} = 2L/\lambda_{\max} - I \in [-I, I]$ (shifting eigenvalues from $[0, \lambda_{\max}]$ to $[-1, 1]$). Define:

$$g_{\boldsymbol{\theta}}(L) = \sum_{k=0}^K \theta_k T_k(\tilde{L})$$

Computation via recurrence:

$$\bar{\mathbf{x}}_0 = \mathbf{x}, \quad \bar{\mathbf{x}}_1 = \tilde{L}\mathbf{x}, \quad \bar{\mathbf{x}}_k = 2\tilde{L}\bar{\mathbf{x}}_{k-1} - \bar{\mathbf{x}}_{k-2}$$ $$\mathbf{y} = \sum_{k=0}^K \theta_k \bar{\mathbf{x}}_k$$

Each step requires one sparse matrix-vector multiply $O(|E|)$; total cost $O(K|E|)$.

Advantages over truncated Taylor series:

• The Chebyshev approximation error decays exponentially in $K$ (geometric convergence for smooth $g$)
• No numerical instability from large powers of $\tilde{L}$
• The learned parameters $\theta_k$ have clear frequency interpretation

7.4 Heat Kernel and Diffusion Filters

The graph heat equation generalizes diffusion to graphs:

$$\frac{\partial \mathbf{x}(t)}{\partial t} = -L\mathbf{x}(t), \quad \mathbf{x}(0) = \mathbf{x}_0$$

Solution: $\mathbf{x}(t) = e^{-tL}\mathbf{x}_0$. In the spectral domain: $\hat{x}_k(t) = e^{-t\lambda_k}\hat{x}_{k,0}$ - each frequency decays at rate $\lambda_k$.

The heat kernel $H_t = e^{-tL}$ is a positive semidefinite matrix representing the diffusion of heat on the graph over time $t$. Entries $(H_t)_{ij}$ give the heat at vertex $j$ after time $t$ when a unit heat source is placed at vertex $i$.

Properties:

• For $t \to 0$: $H_t \to I$ (no diffusion)
• For $t \to \infty$: $H_t \to \frac{1}{n}\mathbf{1}\mathbf{1}^\top$ (heat equalizes, constant temperature on each component)
• Relates to random walk: $(H_t)_{ij} = \sum_k e^{-t\lambda_k}(U)_{ik}(U)_{jk}$

Diffusion distance. The distance between vertices $i$ and $j$ at time scale $t$ is:

$$D_t(i,j)^2 = \lVert (H_t)_{i,:} - (H_t)_{j,:} \rVert^2 = \sum_k e^{-2t\lambda_k}(u_{k,i} - u_{k,j})^2$$

This diffusion distance is more robust than shortest-path distance: it accounts for all paths between $i$ and $j$, not just the shortest one.

For AI: The PPMI (Positive Pointwise Mutual Information) matrix used in graph-based word embeddings is approximately a diffusion kernel. The node2vec random walk (Grover & Leskovec, 2016) approximates diffusion distance.

7.5 From Chebyshev to GCN

The GCN layer (Kipf & Welling, 2017) is derived from ChebNet by:

Step 1: Set $K = 1$ (first-order Chebyshev approximation): $g_{\boldsymbol{\theta}}(L) \approx \theta_0 T_0(\tilde{L}) + \theta_1 T_1(\tilde{L}) = \theta_0 I + \theta_1 \tilde{L}$.

Step 2: Approximate $\lambda_{\max} \approx 2$ (holding for regular and near-regular graphs), so $\tilde{L} \approx L - I$.

$$g_{\boldsymbol{\theta}}(L) \approx \theta_0 I + \theta_1(L - I) = \theta_0 I + \theta_1(D - A - I)$$

Step 3: Constrain $\theta = \theta_0 = -\theta_1$ (reduce parameters to prevent overfitting):

$$g_\theta(L) \approx \theta(I + D^{-1/2}AD^{-1/2}) = \theta \hat{A}$$

Step 4: Add self-loops $\tilde{A} = A + I$, renormalize with $\tilde{D}_{ii} = \sum_j \tilde{A}_{ij}$ to prevent numerical issues (the "renormalization trick"):

$$\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$$

Full GCN layer:

$$H^{(l+1)} = \sigma\!\left(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2} H^{(l)} W^{(l)}\right) = \sigma\!\left(\hat{A} H^{(l)} W^{(l)}\right)$$

Spectral interpretation. The GCN filter $g(\lambda) \approx 1 - \lambda/2$ is a low-pass filter: it passes low frequencies ($\lambda \approx 0$, smooth signals) and attenuates high frequencies ($\lambda \approx 2$, rapidly varying signals). GCN is fundamentally a graph smoother.

Full GNN treatment: For GraphSAGE, GAT, MPNN framework, over-smoothing fixes, and expressiveness theory, see 11-05 Graph Neural Networks.

---

8. Spectral Clustering

8.1 Graph Partitioning Objectives

Minimum cut. Given a graph and integer $k$, partition $V = A_1 \cup \cdots \cup A_k$ (disjoint, non-empty) to minimize:

$$\text{Cut}(A_1, \ldots, A_k) = \frac{1}{2}\sum_{\ell=1}^k |E(A_\ell, \bar{A}_\ell)|$$

where $E(S, \bar{S})$ is the set of edges between $S$ and its complement.

Problem with minimum cut. Minimum cut tends to cut off isolated vertices or very small sets - the trivial solution $A_1 = \{v\}$ for a low-degree vertex $v$ has very few edges to cut. We need objectives that balance cluster sizes.

RatioCut (Hagen & Kahng, 1992):

$$\text{RatioCut}(A_1, \ldots, A_k) = \sum_{\ell=1}^k \frac{|E(A_\ell, \bar{A}_\ell)|}{|A_\ell|}$$

Normalizes by the number of vertices in each partition - prevents very small cuts.

Normalized Cut (NCut) (Shi & Malik, 2000):

$$\text{NCut}(A_1, \ldots, A_k) = \sum_{\ell=1}^k \frac{|E(A_\ell, \bar{A}_\ell)|}{\operatorname{vol}(A_\ell)}$$

Normalizes by the volume (total degree) - weighted version of RatioCut.

Both problems are NP-hard in general. Spectral clustering relaxes them to tractable eigenvalue problems.

8.2 RatioCut and Unnormalized Spectral Clustering

Two-cluster RatioCut. For $k = 2$ with partition $(S, \bar{S})$:

$$\text{RatioCut}(S, \bar{S}) = |E(S,\bar{S})| \cdot \left(\frac{1}{|S|} + \frac{1}{|\bar{S}|}\right)$$

Define the indicator vector $\mathbf{h} \in \mathbb{R}^n$:

$$h_i = \begin{cases} \sqrt{|\bar{S}|/|S|} & i \in S \\ -\sqrt{|S|/|\bar{S}|} & i \in \bar{S} \end{cases}$$

Claim. $\mathbf{h}^\top L \mathbf{h} = n \cdot \text{RatioCut}(S, \bar{S})$. Also: $\lVert \mathbf{h} \rVert^2 = n$ and $\mathbf{h}^\top \mathbf{1} = 0$.

Proof: $\mathbf{h}^\top L \mathbf{h} = \sum_{(i,j)\in E}(h_i - h_j)^2$. The only nonzero terms come from edges crossing the cut: for $(i,j) \in E(S, \bar{S})$:

$$(h_i - h_j)^2 = \left(\sqrt{|\bar{S}|/|S|} + \sqrt{|S|/|\bar{S}|}\right)^2 = \frac{n^2}{|S||\bar{S}|}$$

Summing over all $|E(S,\bar{S})|$ cut edges and using $1/|S| + 1/|\bar{S}| = n/(|S||\bar{S}|)$:

$$\mathbf{h}^\top L \mathbf{h} = |E(S,\bar{S})| \cdot \frac{n^2}{|S||\bar{S}|} = n \cdot \text{RatioCut}(S, \bar{S}) \qquad \square$$

Relaxation. The discrete optimization $\min_S \mathbf{h}^\top L \mathbf{h}$ subject to $\mathbf{h}^\top \mathbf{1} = 0$, $\lVert \mathbf{h} \rVert = \sqrt{n}$, $h_i \in \{c_+, c_-\}$ is NP-hard. Relax the integrality constraint: allow $h_i \in \mathbb{R}$. By Courant-Fischer, the solution is the Fiedler vector $\mathbf{u}_2$.

Recovery. Given $\mathbf{u}_2$, assign vertex $i$ to $S$ if $(\mathbf{u}_2)_i \geq 0$, to $\bar{S}$ otherwise. In practice, use k-means with $k=2$ on $\mathbf{u}_2$ for robustness.

8.3 Normalized Cut (Shi & Malik 2000)

NCut relaxation. Define the indicator $\mathbf{h}$ analogously to RatioCut but with volume weights: for partition $(S, \bar{S})$:

$$h_i = \begin{cases} \sqrt{\operatorname{vol}(\bar{S})/\operatorname{vol}(S)} & i \in S \\ -\sqrt{\operatorname{vol}(S)/\operatorname{vol}(\bar{S})} & i \in \bar{S} \end{cases}$$

Then $\mathbf{h}^\top L \mathbf{h} = \operatorname{vol}(V) \cdot \text{NCut}(S, \bar{S})$, subject to $\mathbf{h}^\top D \mathbf{1} = 0$ and $\mathbf{h}^\top D \mathbf{h} = \operatorname{vol}(V)$.

Generalized eigenvalue problem. The continuous relaxation is:

$$\min_{\mathbf{h} \perp_D \mathbf{1}} \frac{\mathbf{h}^\top L \mathbf{h}}{\mathbf{h}^\top D \mathbf{h}} = \min_{\tilde{\mathbf{h}} \perp D^{1/2}\mathbf{1}} \frac{\tilde{\mathbf{h}}^\top L_{\text{sym}} \tilde{\mathbf{h}}}{\lVert \tilde{\mathbf{h}} \rVert^2}$$

via the substitution $\tilde{\mathbf{h}} = D^{1/2}\mathbf{h}$. This is the standard Rayleigh quotient for $L_{\text{sym}}$, minimized by $\tilde{\mathbf{u}}_2$. Thus:

$$\mathbf{h}^* = D^{-1/2}\tilde{\mathbf{u}}_2$$

where $\tilde{\mathbf{u}}_2$ is the Fiedler vector of $L_{\text{sym}}$.

Shi-Malik algorithm (2-cluster):

1. Build $L_{\text{sym}} = D^{-1/2}(D-A)D^{-1/2}$
2. Compute Fiedler vector $\tilde{\mathbf{u}}_2$ of $L_{\text{sym}}$
3. Assign vertex $i$ to $S$ if $(D^{-1/2}\tilde{\mathbf{u}}_2)_i \geq \text{threshold}$
4. Choose threshold: empirically (try all $n-1$ thresholds) or at 0

Multi-class NCut. For $k$ clusters, use the $k$ smallest eigenvectors of $L_{\text{sym}}$, form the $n \times k$ matrix $U_k$, normalize each row to unit norm, then apply k-means to the rows.

8.4 Multi-Way Spectral Clustering

The Ng-Jordan-Weiss (NJW) algorithm (2002) is the standard multi-class spectral clustering:

1. Build the normalized Laplacian $L_{\text{sym}}$
2. Compute the $k$ smallest eigenvectors $\tilde{\mathbf{u}}_1, \ldots, \tilde{\mathbf{u}}_k$ (smallest eigenvalues of $L_{\text{sym}}$)
3. Form $U_k \in \mathbb{R}^{n \times k}$ with these eigenvectors as columns
4. Normalize rows: let $Y_{i,:} = U_{k,i,:} / \lVert U_{k,i,:} \rVert_2$ (row normalization)
5. Apply k-means to the rows of $Y$

Why row normalization? The perturbation theory of 8.5 shows that in a perfect $k$-cluster graph, the rows of $U_k$ lie exactly on $k$ orthogonal vectors. Row normalization maps these to the same point on the unit sphere regardless of degree, making k-means converge cleanly.

Perturbation theory justification. Consider a "block graph" $G_0$ consisting of $k$ disconnected cliques. The $k$ smallest eigenvalues of $L_{\text{sym}}$ are all $0$, with eigenvectors being the normalized indicators of each clique. Any real graph with $k$ communities can be seen as a perturbed block graph; if the perturbation (inter-community edges) is small, the eigenvectors are close to the block indicators. Weyl's perturbation theorem quantifies how much $\lambda_2$ changes.

8.5 Complete Algorithm and Implementation

SPECTRAL CLUSTERING ALGORITHM
========================================================================

  Input:  Adjacency matrix A \in \mathbb{R}^n^x^n, number of clusters k
  Output: Cluster assignments c \in {1,...,k}^n

  1. Compute degree matrix D = diag(A*1)
  2. Compute normalized Laplacian L_sym = D^(-1/2) (D - A) D^(-1/2)
     (or use L_rw = I - D^(-1) A, but use L_sym for symmetric version)

  3. Compute k smallest eigenvalues and eigenvectors of L_sym
     -> eigenvectors form columns of U_k \in \mathbb{R}^n^x^k

  4. Normalize rows: Y_i = U_k[i,:] / ||U_k[i,:]||_2
     (skip for RatioCut; required for NCut)

  5. Apply k-means clustering to rows of Y
     -> cluster centers \mu_1,...,\mu_k; assignments c[i] \in {1,...,k}

  6. Return c

  Complexity: O(n^3) for full eigendecomposition;
              O(k*n*|E|) with Lanczos + k-means (large graphs)

========================================================================

Practical notes:

• Use Lanczos algorithm or LOBPCG for computing the $k$ smallest eigenvectors of $L_{\text{sym}}$ on large sparse graphs (avoid full eigendecomposition)
• The choice of $k$ can be guided by the eigengap heuristic: choose $k$ where the gap $\lambda_{k+1} - \lambda_k$ is largest
• K-means is run multiple times with random restarts; take the best result (lowest inertia)
• For disconnected graphs, the $k$ zero eigenvalues directly give the cluster indicators

8.6 When Spectral Clustering Beats k-Means

K-means minimizes within-cluster variance assuming convex, isotropic, similarly-sized clusters. It fails on non-convex cluster shapes. Spectral clustering has no shape assumption - it works on any cluster structure that is well-separated in the graph.

When spectral clustering excels:

• Concentric rings, spirals, moons - any shape detectable by graph connectivity
• Clusters at multiple scales (nested communities)
• Data with non-Euclidean structure (molecules, social networks)

When k-means excels:

• Truly Gaussian clusters in $\mathbb{R}^d$
• Very large $n$ where eigenvector computation is too slow
• Cluster structure is well-captured by Euclidean distance

A critical nuance: Spectral clustering requires building the adjacency/affinity graph first. The $k$-NN graph or $\epsilon$-neighborhood graph choice matters enormously for quality. A common failure mode: if the graph is built with too small $k$ or $\epsilon$, communities may become disconnected even within a true cluster. If too large, community structure is washed out.

---

9. Laplacian Eigenmaps and Graph Embeddings

9.1 The Embedding Problem

Given a graph $G = (V, E)$, we want a mapping $\phi: V \to \mathbb{R}^d$ ($d \ll n$) that preserves the graph structure: vertices that are nearby in the graph should be nearby in the embedding. Formally, we want:

$$\phi = \arg\min_{\phi: V \to \mathbb{R}^d} \sum_{(i,j) \in E} w_{ij} \lVert \phi(i) - \phi(j) \rVert^2$$

subject to constraints that prevent the trivial solution $\phi(i) = \mathbf{0}$ for all $i$.

Decomposing dimension by dimension, this is $d$ separate problems, each of the form:

$$\min_{\mathbf{f} \in \mathbb{R}^n} \mathbf{f}^\top L \mathbf{f} \quad \text{subject to normalization and orthogonality constraints}$$

This is exactly minimizing the Dirichlet energy, solved by the eigenvectors of $L$.

9.2 Laplacian Eigenmaps Algorithm

Belkin & Niyogi (2001/2003). Given $n$ data points $\mathbf{x}^{(1)}, \ldots, \mathbf{x}^{(n)} \in \mathbb{R}^D$:

1. Build the adjacency graph: Connect points $i$ and $j$ if they are among each other's $k$ nearest neighbors (or $\lVert \mathbf{x}^{(i)} - \mathbf{x}^{(j)} \rVert < \epsilon$).

2. Set edge weights: Use the heat kernel $w_{ij} = \exp(-\lVert \mathbf{x}^{(i)} - \mathbf{x}^{(j)} \rVert^2 / t)$ for connected pairs (with $t > 0$ a bandwidth parameter).

3. Compute degree and Laplacian: $D_{ii} = \sum_j w_{ij}$, $L = D - W$.

4. Solve the generalized eigenvalue problem:

$$L \mathbf{u} = \lambda D \mathbf{u}$$

Equivalently: find eigenvectors of $L_{\text{rw}} = D^{-1}L$ (or $L_{\text{sym}}$).

1. Embed: Take the $d$ eigenvectors $\mathbf{u}_2, \mathbf{u}_3, \ldots, \mathbf{u}_{d+1}$ (skip $\mathbf{u}_1 = \mathbf{1}$) and set $\phi(i) = (u_{2,i}, u_{3,i}, \ldots, u_{d+1,i}) \in \mathbb{R}^d$.

Optimality theorem. The Laplacian eigenmap embedding is the solution to the optimization problem:

$$\min_{\mathbf{f}_1, \ldots, \mathbf{f}_d} \sum_k \mathbf{f}_k^\top L \mathbf{f}_k \quad \text{s.t. } \mathbf{f}_k^\top D \mathbf{f}_k = 1,\; \mathbf{f}_k^\top D \mathbf{f}_j = 0 \text{ for } k \neq j$$

The solution is $\mathbf{f}_k = \mathbf{u}_{k+1}$ (the $(k+1)$-th eigenvector of $L_{\text{sym}}$). This is optimal in the sense that no other $d$-dimensional embedding has smaller total Dirichlet energy.

Manifold learning interpretation. If the data points $\mathbf{x}^{(i)}$ lie on a $d$-dimensional manifold embedded in $\mathbb{R}^D$, the Laplacian eigenmap recovers the intrinsic coordinates of the manifold. As $n \to \infty$ and the bandwidth $t \to 0$ at an appropriate rate, the graph Laplacian converges to the Laplace-Beltrami operator on the manifold (Belkin & Niyogi, 2008).

9.3 Diffusion Maps

Coifman & Lafon (2006) introduced diffusion maps as a multiscale version of Laplacian eigenmaps.

Define the diffusion operator $M = D^{-1}W$ (the random walk matrix) and its $t$-step version $M^t$. The diffusion distance at scale $t$:

$$D_t(i,j)^2 = \sum_k \mu_k^{2t} (\psi_k(i) - \psi_k(j))^2$$

where $\mu_k, \psi_k$ are eigenvalues/eigenvectors of $M$. The diffusion map embedding:

$$\Phi^t(i) = (\mu_2^t \psi_{2,i},\, \mu_3^t \psi_{3,i},\, \ldots,\, \mu_d^t \psi_{d,i}) \in \mathbb{R}^{d-1}$$

The Euclidean distance in the diffusion map equals the diffusion distance: $\lVert \Phi^t(i) - \Phi^t(j) \rVert = D_t(i,j)$.

Multi-scale property. By varying $t$, diffusion maps reveal structure at different scales:

• Small $t$: local neighborhood structure
• Large $t$: global cluster structure (only the dominant eigenvectors with $\mu_k^t \gg 0$ remain)

9.4 Relationship to PCA and Kernel PCA

Kernel PCA (Scholkopf et al., 1998) computes the principal components of data in a feature space defined by a kernel $k(\mathbf{x}, \mathbf{y})$. For a kernel matrix $K \in \mathbb{R}^{n \times n}$ with $K_{ij} = k(\mathbf{x}^{(i)}, \mathbf{x}^{(j)})$, kernel PCA computes the eigenvectors of the centered kernel matrix.

Commute-time embedding. The commute time $C(i,j)$ between vertices $i$ and $j$ is the expected number of steps for a random walk starting at $i$ to reach $j$ and return. It equals:

$$C(i,j) = \operatorname{vol}(V) \sum_{k=2}^n \frac{1}{\lambda_k}\left(\frac{(u_{k,i})}{\sqrt{d_i}} - \frac{(u_{k,j})}{\sqrt{d_j}}\right)^2$$

This is kernel PCA with the commute-time kernel $k(i,j) = (C(i,i) + C(j,j) - C(i,j))/2$. So Laplacian eigenmaps is a special case of kernel PCA.

9.5 Spectral Positional Encodings for Transformers

Standard Transformers process tokens with positional encodings to handle sequence order. Graph Transformers need analogous positional encodings for graph nodes - but graphs have no canonical ordering.

Laplacian Positional Encoding (LapPE). Use the eigenvectors of the graph Laplacian as node positional encodings:

$$\text{PE}(v) = [\mathbf{u}_2(v), \mathbf{u}_3(v), \ldots, \mathbf{u}_{k+1}(v)] \in \mathbb{R}^k$$

where $\mathbf{u}_j(v)$ is the $v$-th entry of the $j$-th Laplacian eigenvector.

Challenge: Sign ambiguity. Each eigenvector $\mathbf{u}_j$ is defined only up to sign: $-\mathbf{u}_j$ is also a valid eigenvector. This creates non-uniqueness in the PE.

Solutions:

• Random sign flips during training (Dwivedi et al., 2022): randomly flip signs in training; the Transformer learns sign-invariant functions
• SignNet (Lim et al., 2022): use a Deep Sets architecture that is invariant to sign flips: $\phi(\mathbf{u}_j) + \phi(-\mathbf{u}_j)$
• BasisNet: extend to the case of repeated eigenvalues (multiplicity $> 1$), which introduce rotational ambiguity

RWPE (Random Walk Positional Encoding). Instead of Laplacian eigenvectors, use $k$ steps of a random walk:

$$\text{RWPE}(v)_j = (P^j)_{vv} = \text{probability of returning to } v \text{ after } j \text{ steps}$$

where $P = D^{-1}A$. This avoids the sign ambiguity issue and is invariant to graph automorphisms. Used in GPS (Rampasek et al., 2022) - one of the best-performing graph Transformers.

Why LapPE/RWPE matter. Without positional encodings, graph Transformers cannot distinguish graph structure - all nodes with the same degree distribution look identical. Spectral PE gives each node a unique "spectral fingerprint" derived from its position in the graph's Fourier basis.

---

10. Directed Graph Spectra

10.1 Directed Laplacians

For a directed graph (digraph) $G = (V, E)$ with $E \subseteq V \times V$ (ordered pairs), the adjacency matrix $A$ is not symmetric: $A_{ij} = 1$ if $(i \to j) \in E$ but $A_{ji}$ may be $0$.

In-degree and out-degree: For each vertex $i$, $d_i^{\text{in}} = \sum_j A_{ji}$ (number of incoming edges) and $d_i^{\text{out}} = \sum_j A_{ij}$ (outgoing edges).

Out-degree Laplacian: $L^{\text{out}} = D^{\text{out}} - A$ where $D^{\text{out}} = \operatorname{diag}(d_1^{\text{out}}, \ldots, d_n^{\text{out}})$.

In-degree Laplacian: $L^{\text{in}} = D^{\text{in}} - A^\top$ (or equivalently, the out-degree Laplacian of the reversed graph).

Key difference from undirected case:

• $L^{\text{out}}$ is NOT symmetric in general
• Eigenvalues may be complex
• The row-sum-zero property holds: $L^{\text{out}}\mathbf{1} = \mathbf{0}$ (since each row sums to $d_i^{\text{out}} - d_i^{\text{out}} = 0$)
• But column sums are $d_j^{\text{in}} - d_j^{\text{out}}$, not necessarily zero

Stationary distribution. The directed random walk $P = (D^{\text{out}})^{-1}A$ is row-stochastic. For a strongly connected digraph, the unique stationary distribution $\boldsymbol{\pi}$ satisfies $\boldsymbol{\pi}^\top P = \boldsymbol{\pi}^\top$. The stationary distribution is NOT necessarily uniform (unlike $d$-regular undirected graphs).

10.2 Kirchhoff's Matrix-Tree Theorem

Theorem (Kirchhoff, 1847). For a connected undirected graph $G$, the number of spanning trees equals any cofactor of $L$:

$$\tau(G) = \frac{1}{n}\prod_{k=2}^n \lambda_k(L)$$

where $\lambda_2, \ldots, \lambda_n$ are the non-zero eigenvalues of $L$.

Proof via the Matrix-Tree theorem. By the Matrix-Tree theorem, $\tau(G)$ equals any $(n-1) \times (n-1)$ principal minor of $L$. By the Cauchy-Binet formula, this minor equals $\frac{1}{n}\lambda_2\lambda_3\cdots\lambda_n$, which follows from the spectral decomposition and the fact that $\lambda_1 = 0$ with eigenvector $\mathbf{1}/\sqrt{n}$.

Examples:

• $K_n$: $\lambda_2 = \cdots = \lambda_n = n$ (all equal), so $\tau(K_n) = n^{n-2}$ (Cayley's formula).
• $P_n$ (path): $\tau(P_n) = 1$ (only one spanning tree - the path itself).
• $C_n$ (cycle): $\tau(C_n) = n$.

For AI: The number of spanning trees measures "graph robustness." Networks with many spanning trees (like expanders) remain connected even after many edge failures. This metric appears in network reliability analysis for distributed training clusters.

10.3 PageRank as a Spectral Problem

PageRank (Page, Brin, Motwani, Winograd, 1998) - the algorithm behind Google Search - is fundamentally a spectral computation on a directed graph.

Setup. Model the Web as a directed graph: pages are vertices, hyperlinks are directed edges. Define the Google matrix:

$$G = \alpha P + (1-\alpha) \frac{\mathbf{1}\mathbf{1}^\top}{n}$$

where $P = (D^{\text{out}})^{-1}A$ is the column-stochastic random-walk matrix, $\alpha \in (0,1)$ is the damping factor (typically $\alpha = 0.85$), and $(1-\alpha)\mathbf{1}\mathbf{1}^\top/n$ represents teleportation (random jumps to any page).

PageRank vector. The PageRank of each page is the stationary distribution $\boldsymbol{\pi}$ of the Markov chain defined by $G$:

$$\boldsymbol{\pi}^\top = \boldsymbol{\pi}^\top G \implies \boldsymbol{\pi}^\top(I - G) = \mathbf{0}$$

Equivalently, $\boldsymbol{\pi}$ is the dominant left eigenvector of $G$ (eigenvalue $1$).

Spectral computation. By the Perron-Frobenius theorem, $G$ is a positive stochastic matrix (all entries $> 0$ due to the teleportation term), so it has a unique dominant eigenvalue $\mu_1 = 1$ with a unique positive eigenvector $\boldsymbol{\pi}$.

Power iteration. PageRank is computed by:

$$\boldsymbol{\pi}^{(t+1)} = \boldsymbol{\pi}^{(t)} G = \alpha \boldsymbol{\pi}^{(t)} P + (1-\alpha)\frac{\mathbf{1}}{n}$$

Convergence rate: geometric with ratio $\alpha$ - the second eigenvalue of $G$ is at most $\alpha$. Each iteration is a sparse matrix-vector multiply $O(|E|)$.

For AI (RLHF and LLM preference graphs): In reinforcement learning from human feedback (RLHF), preference data can be modeled as a directed graph over responses, with edge $(r_i, r_j)$ meaning "response $r_i$ is preferred over $r_j$." PageRank on this preference graph gives a global ranking consistent with pairwise preferences. This is closely related to Bradley-Terry models used in reward model training (Ouyang et al., 2022).

10.4 Directed Graph Spectra in AI

Attention as a directed graph. In a Transformer, the attention weights $A_{ij}$ define a directed weighted graph over tokens. The spectral properties of this attention graph have interpretability implications:

• The dominant eigenvector of the attention matrix identifies "hub" tokens - tokens that receive most attention
• Spectral analysis of attention graphs has been used in mechanistic interpretability to identify "induction heads" and "name mover heads" (Olsson et al., 2022)
• The spectral gap of the attention graph determines how quickly information mixes across token positions

Causal DAGs. In causal inference (Chapter 22), structural causal models are represented as DAGs. The spectral properties of the DAG adjacency matrix are related to the "depth" of causal chains: a large spectral radius means long-range causal effects.

---

11. Advanced Topics

11.1 Spectral Sparsification

Problem. For a dense graph $G$ with $n$ vertices and $\Theta(n^2)$ edges, many spectral algorithms are too slow. Can we find a sparse graph $\tilde{G}$ with $O(n \log n)$ edges that preserves the spectrum of $L$?

Definition. $\tilde{G}$ is an $\epsilon$-spectral sparsifier of $G$ if for all $\mathbf{x} \in \mathbb{R}^n$:

$$(1-\epsilon)\mathbf{x}^\top L_G \mathbf{x} \leq \mathbf{x}^\top L_{\tilde{G}} \mathbf{x} \leq (1+\epsilon)\mathbf{x}^\top L_G \mathbf{x}$$

Equivalently, $(1-\epsilon)L_G \preceq L_{\tilde{G}} \preceq (1+\epsilon)L_G$ in the PSD order.

Theorem (Spielman & Srivastava, 2011). Every graph $G$ has an $\epsilon$-spectral sparsifier with $O(n \log n / \epsilon^2)$ edges, computable in near-linear time using random sampling weighted by effective resistances.

Effective resistance. The effective resistance $R_{\text{eff}}(i,j)$ between vertices $i$ and $j$ is the electrical resistance between them when unit resistors are placed on each edge. It equals:

$$R_{\text{eff}}(i,j) = (\mathbf{e}_i - \mathbf{e}_j)^\top L^\dagger (\mathbf{e}_i - \mathbf{e}_j)$$

where $L^\dagger$ is the pseudoinverse of $L$.

Algorithm: Sample each edge $(i,j)$ independently with probability proportional to $w_{ij} R_{\text{eff}}(i,j)$, and rescale the weight. The resulting sparse graph preserves all spectral properties.

For AI: Spectral sparsification can reduce the computational cost of graph-based ML. A 10-million-edge social graph can be sparsified to $\sim 500K$ edges while preserving spectral clustering quality.

11.2 Random Matrix Theory and Graph Spectra

The spectrum of a random graph has universal limiting behavior described by random matrix theory.

Erdos-Renyi model $G(n, p)$. For a random graph where each edge appears independently with probability $p$, the empirical spectral distribution of $A/\sqrt{np(1-p)}$ converges to the semicircle law (Wigner, 1955):

$$\rho(\lambda) = \frac{1}{2\pi}\sqrt{4 - \lambda^2} \quad \text{for } \lambda \in [-2, 2]$$

The leading eigenvalue separates from the bulk at $\mu_1 \approx np$ when $p \gg \ln n / n$, corresponding to the emergence of a giant connected component.

Implications for GNNs:

• Random weight matrices in GNNs have spectra approximated by the semicircle law (for large enough hidden dimensions)
• The alignment between the spectra of data graph $A$ and random weight matrices $W$ affects gradient flow in training
• Spectral norm regularization of GNN weights controls training stability by constraining the spectral radius

11.3 Graph Wavelets

Motivation. Laplacian eigenvectors are global: $\mathbf{u}_k$ is supported on all $n$ vertices. For signals with local structure (e.g., a signal that varies in one part of the graph but is constant elsewhere), global eigenvectors are inefficient. We need a local, multiscale basis - a graph wavelet transform.

Hammond, Vandergheynst & Gribonval (2011). For a vertex $t$ and scale $s$, define the graph wavelet centered at $t$ at scale $s$:

$$\psi_{s,t} = g_s(L)\boldsymbol{\delta}_t$$

where $\boldsymbol{\delta}_t$ is the indicator vector of vertex $t$ and $g_s(\lambda) = s \cdot g(s\lambda)$ is a scaled spectral filter (bandpass at frequency $1/s$). In the spectral domain:

$$\hat{\psi}_{s,t}(\lambda) = g_s(\lambda) U^\top \boldsymbol{\delta}_t = g_s(\lambda) \mathbf{u}(:,t)$$

Properties of graph wavelets:

• Spatially localized: if $g$ has compact spectral support $[\omega_{\min}, \omega_{\max}]$, then $\psi_{s,t}$ is $K$-hop localized where $K$ depends on the bandwidth and $s$
• Frequency selective: wavelets at scale $s$ are sensitive to frequency $\approx 1/s$
• Frame bounds: for appropriate $g$, $\{\psi_{s,t}\}$ forms a frame (redundant but stable basis)

Scattering transform on graphs (Gama et al., 2019): Compose multiple wavelet transforms with pointwise nonlinearities to build invariant/equivariant features. Provides theoretical guarantees for GNN expressiveness.

11.4 Infinite Graphs and Spectral Measures

For infinite graphs (e.g., the integer lattice $\mathbb{Z}^d$, infinite trees), the Laplacian is an unbounded operator on $\ell^2(V)$ and the spectrum is no longer a finite set but a spectral measure $\mu_L$.

Example: Integer lattice $\mathbb{Z}^d$. The Laplacian $L$ on $\mathbb{Z}^d$ has a continuous spectrum $[0, 4d]$ (the $d$-dimensional discrete Laplacian spectrum). This connects to the theory of periodic operators in solid-state physics (Bloch's theorem).

Spectral measure. For a vertex $v$, the spectral measure $\mu_v$ is defined by:

$$\langle \boldsymbol{\delta}_v, f(L) \boldsymbol{\delta}_v \rangle = \int f(\lambda)\, d\mu_v(\lambda)$$

The spectral measure encodes everything about the local geometry of the graph as seen from $v$.

Convergence of finite graphs. If a sequence of finite graphs $G_n$ converges in the Benjamini-Schramm sense to an infinite graph $G_\infty$, the empirical spectral distributions of $L_{G_n}$ converge weakly to the spectral measure of $L_{G_\infty}$.

Preview: The spectral theory of infinite-dimensional operators is the subject of Chapter 12: Functional Analysis, where Hilbert spaces, unbounded operators, and spectral measures are developed fully.

---

12. Applications in Machine Learning

12.1 Semi-Supervised Learning on Graphs

The problem. Given a graph $G$ with $n$ nodes, a few labeled nodes $\mathcal{L} \subset V$ with labels $y_i \in \{1, \ldots, k\}$, and many unlabeled nodes $\mathcal{U} = V \setminus \mathcal{L}$, assign labels to all unlabeled nodes.

Graph-based regularization (Zhou et al., 2004; Zhu et al., 2003). Find a label function $\mathbf{f}: V \to [0,1]^k$ that:

1. Agrees with the given labels on $\mathcal{L}$
2. Is smooth on the graph (nearby nodes have similar labels)

The objective:

$$\min_{\mathbf{f}} \sum_{i \in \mathcal{L}} \lVert \mathbf{f}_i - \mathbf{y}_i \rVert^2 + \gamma \sum_{(i,j) \in E} w_{ij} \lVert \mathbf{f}_i - \mathbf{f}_j \rVert^2 = \min_\mathbf{f} \lVert \mathbf{f}_\mathcal{L} - \mathbf{y} \rVert^2 + \gamma \operatorname{tr}(\mathbf{f}^\top L \mathbf{f})$$

The closed-form solution involves $(I + \gamma L)^{-1}$ - a smoothing operator. In the spectral domain:

$$\hat{f}_k = \frac{\hat{y}_k}{1 + \gamma\lambda_k}$$

High-frequency components ($\lambda_k$ large) are strongly regularized toward zero; low-frequency components are preserved.

Connection to label propagation. The Gaussian Fields and Harmonic Functions algorithm (Zhu et al., 2003) sets labeled node values to the true labels and propagates via:

$$\mathbf{f}_\mathcal{U} = L_{\mathcal{U}\mathcal{U}}^{-1} L_{\mathcal{U}\mathcal{L}} \mathbf{y}_\mathcal{L}$$

(where $L_{\mathcal{U}\mathcal{U}}$ is the Laplacian restricted to unlabeled nodes). This harmonic interpolation assigns each unlabeled node the weighted average of its neighbors' labels, with weights determined by graph structure.

Modern variant: GCN for semi-supervised learning. The two-layer GCN of Kipf & Welling (2017) was originally proposed for exactly this task: semi-supervised node classification. The Laplacian smoothing is built into the propagation rule, making it a parameterized (learnable) version of label propagation.

12.2 Knowledge Graph Analysis

A knowledge graph (KG) represents world knowledge as a graph: entities (nodes) connected by typed relations (edges). Examples: Freebase, Wikidata, ConceptNet, UMLS (medical).

Spectral properties of KGs:

• KGs are heterogeneous (multiple edge types) and sparse ($|E| = O(|V|)$)
• The adjacency spectrum often follows a power law: many small eigenvalues, a few large ones
• The spectral gap $\lambda_2$ measures how well-integrated the KG is: a small gap indicates a KG with isolated sub-graphs (different domains not well-connected)

Spectral regularization. KG embedding models (TransE, RotatE, ComplEx) learn entity and relation embeddings. Adding a spectral regularization term:

$$\mathcal{L}_{\text{smooth}} = \sum_r \text{tr}(E_r^\top L_r E_r)$$

encourages entity embeddings to be smooth with respect to each relation type $r$'s graph - entities connected by relation $r$ should have similar embeddings. This improves link prediction accuracy, especially for rare relations.

12.3 Molecular Property Prediction

Molecules are naturally represented as graphs: atoms are nodes, chemical bonds are edges. Predicting molecular properties (solubility, toxicity, drug-likeness) from molecular graphs is a key application of GNNs.

Spectral molecular fingerprints. The eigenvalue spectrum of the molecular graph Laplacian provides rotation- and permutation-invariant descriptors. The "spectral profile" $(\lambda_1, \lambda_2, \ldots, \lambda_n)$ uniquely characterizes many molecular structures.

Graph edit distance and spectral distance. Two molecules have similar properties if they have similar spectral profiles. The distance:

$$d_{\text{spec}}(G_1, G_2) = \lVert \boldsymbol{\lambda}(G_1) - \boldsymbol{\lambda}(G_2) \rVert_2$$

(where eigenvalues are sorted and zero-padded to the same length) approximates graph edit distance and correlates with molecular similarity.

Equivariance and invariance. Spectral fingerprints are invariant to atom permutation (graph isomorphism), which is the correct invariance for molecular property prediction. However, they are blind to chirality (mirror image molecules) - a known limitation requiring higher-order structural features.

12.4 Attention Pattern Analysis in LLMs

A $d$-head attention layer in a Transformer computes $h$ attention weight matrices $\{A^{(1)}, \ldots, A^{(h)}\}$, each $A^{(k)} \in \mathbb{R}^{T \times T}$ for sequence length $T$. These define $h$ weighted directed graphs over the token positions.

Spectral analysis of attention. The eigenvalues of $A^{(k)}$ reveal the attention pattern structure:

• If $A^{(k)} \approx \mathbf{1}\mathbf{1}^\top/T$ (uniform attention): $\mu_1 = 1$, all others $\approx 0$
• If $A^{(k)} \approx I$ (attend only to self): $\mu_1 = \cdots = \mu_T = 1$
• Induction heads (Olsson et al., 2022) have $A^{(k)}$ with large spectral gap between $\mu_1$ and $\mu_2$ - they attend sharply to a few positions

Attention graph Laplacian. Define the symmetrized attention Laplacian $L^{(k)} = D^{(k)} - (A^{(k)} + A^{(k)^\top})/2$. The Fiedler vector $\mathbf{u}_2^{(k)}$ of $L^{(k)}$ identifies the two groups of tokens most separated by head $k$'s attention.

Applications:

• Attention head pruning: Heads whose attention graphs have very small spectral gap (uniform attention) contribute little and can be pruned (Michel et al., 2019; Voita et al., 2019)
• Mechanistic interpretability: Spectral analysis of multi-head attention composition identifies information routing circuits (Elhage et al., 2021)
• Context window analysis: The Laplacian spectrum of attention graphs grows as more tokens are added; sudden changes in $\lambda_2$ indicate "phase transitions" in how the model processes context

---

13. Common Mistakes

---