Class 3 · Test 1 Q1

Graphs &
Laplacian Matrix

A graph $G(V,E)$ has a vertex set $V$ and edge set $E$. Its matrix representations — adjacency $A$, degree $D$, and Laplacian $L = D - A$ — encode structure. The eigenvalues of $L$ reveal connectivity and clustering.

Graph Definitions

Graph Structure

G(V, E): vertices V = {v₁, v₂, ..., vₙ}, edges E = {(vᵢ, vⱼ)} Undirected: if (vᵢ,vⱼ) ∈ E then (vⱼ,vᵢ) ∈ E No loops: (vⱼ,vⱼ) ∉ E for any j Degree dᵢ: number of edges incident to vertex vᵢ

We use undirected graphs with no loops. The degree $d_i$ of vertex $v_i$ is the number of edges connected to it.

Adjacency Matrix $A(G)$

$$a_{ij} = \begin{cases} 1 & \text{if } (v_i, v_j) \in E \\ 0 & \text{otherwise} \end{cases}$$

Properties: $A$ is real, symmetric ($a_{ij} = a_{ji}$), has zero diagonal ($a_{jj} = 0$), and real eigenvalues (symmetric). The row sum $[A]\vec{1}$ gives the degree vector.

Degree Matrix $D(G)$

$$D(G) \stackrel{\text{def}}{=} \text{diag}([A]\vec{1}) = \text{diag}(d_1, d_2, \ldots, d_n)$$

$D$ is diagonal. Each entry $d_i$ is the degree of vertex $v_i$ — the sum of row $i$ of the adjacency matrix.

Laplacian Matrix $L(G)$

$$L = D - A$$

Reading entries of $L$ directly:

$L_{ii}$ = degree of vertex $i$ (positive, on diagonal) $L_{ij}$ = −1 if edge (i,j) exists (off-diagonal) $L_{ij}$ = 0 if no edge (i,j) (off-diagonal)

So to draw a graph from $L$: diagonal gives degrees, off-diagonal $-1$ entries indicate edges.

Properties of the Laplacian

Key Properties

1. L is real and symmetric 2. L is diagonally dominant 3. L is positive semidefinite: L ⪰ 0 (all eigenvalues ≥ 0) 4. Row sums = 0: L⃗1 = ⃗0 and ⃗1ᵀL = ⃗0ᵀ 5. Therefore ⃗1 is an eigenvector of λ₁ = 0 6. tr(L) = 2 × (number of edges in G)

Property 4 is the most important: every row of $L$ sums to zero, because diagonal = sum of off-diagonal magnitudes. This guarantees $\lambda_1 = 0$ always.

Components and Zero Eigenvalues

dim(null(L)) = number of connected components of G

A connected component is a maximal subgraph where every pair of vertices is connected by a path. If $G$ has $k$ components, then $L$ has exactly $k$ zero eigenvalues. For a connected graph: exactly one zero eigenvalue.

Fiedler Vector & Spectral Clustering

The Fiedler Vector

Fiedler vector: eigenvector of the second-smallest eigenvalue λ₂ of L Algorithm for binary clustering: 1. Compute L(G) = D - A 2. Find eigenvector ⃗v₂ for eigenvalue λ₂ (second smallest) 3. Assign vertex vᵢ to cluster +1 if (⃗v₂)ᵢ ≥ 0 4. Assign vertex vᵢ to cluster −1 if (⃗v₂)ᵢ < 0

Named after Miroslav Fiedler (1989), who called this "algebraic connectivity". The sign pattern of the Fiedler vector separates vertices into two clusters based on graph structure — even for nearly-disconnected graphs.

Spectral Clustering (Class 32)

ε-Neighborhood Graph from Data

Given data matrix A, compute pairwise distance matrix C: cᵢⱼ = ‖aᵢ − aⱼ‖ (Euclidean distance) ε-neighborhood adjacency: aᵢⱼ = 1 if 0 < cᵢⱼ ≤ ε aᵢⱼ = 0 otherwise Then compute L = D − A as usual.

This converts a data matrix into a graph. The threshold $\varepsilon$ controls how far apart two observations can be and still be considered "connected". Then spectral clustering on the Laplacian finds natural clusters.

Spectral Clustering Algorithm (k clusters)

1. Compute Laplacian L = D − A 2. Find spectral decomposition L = QΛQᵀ, eigenvalues sorted: λ₁ ≥ λ₂ ≥ ··· ≥ λₙ₋₁ ≥ λₙ = 0 3. Gather the LAST k eigenvectors into matrix E ∈ ℝⁿˣᵏ 4. Apply k-means clustering to the rows of E 5. Assign the resulting cluster labels back to original observations

Key difference from PCA: PCA uses the first (largest) $k$ eigenvectors. Spectral clustering uses the last (smallest) $k$ eigenvectors. This is because the Laplacian's smallest eigenvalues correspond to the least-connected structure — the natural clusters.

Why the Laplacian is PSD — Proof

For any ⃗u ∈ ℝᵐ: ⃗uᵀL⃗u = ⃗uᵀD⃗u − ⃗uᵀW⃗u = (1/2) Σᵢ Σⱼ wᵢⱼ(uᵢ − uⱼ)² ≥ 0

Since $w_{ij} \geq 0$ (non-negative weights) and $(u_i - u_j)^2 \geq 0$ always, the quadratic form is always non-negative. Therefore $L \succeq 0$.

Practice Problems

W26 Test 1 · Q1 Draw the graph for the Laplacian $L = \begin{bmatrix}2&-1&-1&0&0&0\\-1&3&-1&-1&0&0\\-1&-1&2&0&0&0\\0&-1&0&3&-1&-1\\0&0&0&-1&2&-1\\0&0&0&-1&-1&2\end{bmatrix}$ +
Worked Answer
Read degrees from diagonal: $d_1=2, d_2=3, d_3=2, d_4=3, d_5=2, d_6=2$

Read edges from off-diagonal $-1$ entries: $(1,2), (1,3), (2,3), (2,4), (4,5), (4,6), (5,6)$

Graph structure: Vertices 1, 2, 3 form a triangle. Vertex 2 bridges to vertex 4. Vertices 4, 5, 6 form a triangle. This is a "dumbbell" — two triangles connected by a bridge at vertex 2–4.

Verify: $d_2 = 3$ ✓ (connected to 1, 3, 4). $d_4 = 3$ ✓ (connected to 2, 5, 6).
Conceptual A graph has Laplacian with eigenvalues $\{0, 0, 0.44, 2, 3, 3, 4.56\}$. How many connected components does the graph have? +
Worked Answer
The number of zero eigenvalues = number of connected components. There are 2 zeros, so the graph has 2 connected components.
Conceptual For the adjacency matrix $A_5$ of a bipartite graph, what is the structure of $A_5$ when vertices are ordered by partition? +
Worked Answer
A bipartite graph partitions $V$ into sets $V_L$ and $V_R$ where all edges go between $V_L$ and $V_R$, never within. When vertices are ordered with $V_L$ first: $$A_5 = \begin{bmatrix}0 & A_{5S} \\ A_{5S}^T & 0\end{bmatrix}$$ The diagonal blocks are zero (no edges within each partition) and the off-diagonal blocks contain the actual edges.