The Cheeger inequality relates the spectral gap lambda_2 of the normalized graph Laplacian to the edge expansion h(G): lambda_2/2 <= h(G) <= sqrt(2 * lambda_2). Why is the Fiedler vector (eigenvector for lambda_2) useful for graph partitioning?
AThe Fiedler vector assigns each vertex a real value, and thresholding these values at zero gives a bisection whose expansion is at most sqrt(2 * lambda_2) — within a square-root factor of optimal by the Cheeger inequality
BThe Fiedler vector directly encodes the optimal partition
CThe Fiedler vector minimizes the number of edges in the graph
DThe Fiedler vector is only useful for planar graphs
The Fiedler vector v solves min_{v perp 1} (v^T L v)/(v^T v) = lambda_2, where v^T L v = sum_{(i,j) in E} (v_i - v_j)^2 measures how much v varies across edges. Vertices with similar v-values are well-connected; vertices with different values have few edges between them. A sweep cut — sorting vertices by Fiedler value and trying all threshold cuts — finds a cut with expansion at most sqrt(2*lambda_2). Since lambda_2/2 <= h(G), this is within a sqrt(2/lambda_2) factor of the true optimum when lambda_2 is not too small. This spectral relaxation → rounding paradigm mirrors LP relaxation → rounding for combinatorial optimization.
Question 2 True / False
The number of zero eigenvalues of the graph Laplacian L equals the number of connected components of the graph.
TTrue
FFalse
Answer: True
The Laplacian L = D - A is positive semidefinite with smallest eigenvalue 0. The null space of L is spanned by indicator vectors of the connected components: if x is constant on each component, then x^T L x = sum_{(i,j)} (x_i - x_j)^2 = 0 (all edges connect vertices with the same x-value). Conversely, if x^T L x = 0, then x_i = x_j for all edges (i,j), so x is constant on each component. The dimension of the null space — the multiplicity of eigenvalue 0 — equals the number of connected components. This is the most basic spectral graph fact and motivates all further spectral analysis.
Question 3 Short Answer
Explain how Spielman-Teng's near-linear time Laplacian solver works at a high level and why solving Laplacian systems is so broadly useful.
Think about your answer, then reveal below.
Model answer: Spielman-Teng solve Lx = b (where L is a graph Laplacian) in O(m * log^c(n)) time using a hierarchy of graph sparsifiers: each level replaces the graph with a sparser graph (fewer edges) that preserves the Laplacian's spectral properties within (1+epsilon). The solver uses this hierarchy as a preconditioner for an iterative method (preconditioned Chebyshev or conjugate gradient). Each level reduces the problem size, and the hierarchy has O(log n) levels, giving near-linear total work. Laplacian systems arise everywhere: in electrical network analysis (computing effective resistances and current flows), in maximum flow (interior point methods reduce to Laplacian solves), in graph partitioning (computing the Fiedler vector), in machine learning (semi-supervised learning via label propagation), and in scientific computing (finite element methods on meshes).
The key breakthrough was showing that graph sparsification — replacing a graph with a spectrally similar graph having O(n log n) edges — preserves the solution quality. Batson-Spielman-Srivastava (2012) proved that twice-Ramanujan sparsifiers exist with O(n/epsilon^2) edges, enabling even stronger reductions.
Question 4 True / False
Spectral clustering uses the top-k eigenvectors of the graph Laplacian to embed vertices in R^k, then applies k-means clustering in this embedding space. This approach has no theoretical guarantees.
TTrue
FFalse
Answer: False
Spectral clustering has strong theoretical guarantees under planted partition models and stochastic block models. If the graph has k well-separated clusters with inter-cluster edge density much lower than intra-cluster density, the top-k eigenvectors approximately recover the cluster indicator vectors, and k-means in the spectral embedding correctly identifies the clusters with high probability. The guarantees are quantified by the eigengap (lambda_k - lambda_{k+1}): a large gap indicates well-separated clusters. Davis-Kahan perturbation theory bounds how much the empirical eigenvectors deviate from the ideal cluster indicators. These results make spectral clustering one of the best-understood clustering algorithms.