Project 58: Spectral Graph and Laplacian Clusterer

A self-contained deep-dive from the canonical Math from Foundations to Machine Learning curriculum.

  • Difficulty: Level 4: Expert
  • Time: 2 weeks
  • Language: Python
  • Prerequisites: Projects 9, 24-25, and 38
  • Source: ML-Math P30

What You Will Build

Implement spectral clustering from sparse graph structure. Construct adjacency and degree matrices plus unnormalized, random-walk, and symmetric-normalized Laplacians. Compute the smallest eigenpairs, identify trivial zero modes and connected components, use nontrivial eigenvectors as a spectral embedding, and apply your Project 38 k-means implementation. Add eigengap-based suggestions for cluster count, row normalization where appropriate, cut/modularity/silhouette metrics, and repeated-seed stability analysis. Compare spectral clusters with k-means on raw node features or adjacency summaries.

Real World Outcome

Given a network edge list, the clusterer displays the spectrum and eigengaps, recommends k, plots nodes in spectral coordinates, colors recovered communities, and reports normalized cut, modularity, embedding silhouette, and seed stability. Synthetic two-moons and stochastic-block graphs show structures that ordinary Euclidean k-means misses.

Core Question

Why do low-frequency eigenvectors of a graph Laplacian reveal communities hidden in the raw edge representation?

Concepts You Must Understand First

  • Adjacency/degree matrices, graph cuts, and connected components.
  • Eigenvalues/eigenvectors and invariant subspaces — Projects 24-25.
  • Unnormalized and normalized graph Laplacians — Fan Chung, Spectral Graph Theory.
  • Rayleigh quotient, Fiedler vector, spectral embedding, and eigengaps.
  • K-means initialization, seed sensitivity, and clustering metrics — Project 38.

Build Milestones

  1. Construct and validate all three Laplacian variants on small known graphs.
  2. Compute smallest sparse eigenpairs and interpret zero modes/components and the Fiedler vector.
  3. Implement spectral embedding, optional row normalization, and k-means clustering.
  4. Add eigengap selection, cut/modularity/silhouette, and multi-seed stability reports.
  5. Compare variants and baselines on synthetic and one real graph.

Hints in Layers

  1. The number of near-zero Laplacian eigenvalues should match the number of connected components.
  2. Exclude trivial constant eigenvectors from clustering features; disconnected graphs may have several.
  3. Eigenvector signs can flip between runs without changing meaning; compare subspaces or clusters, not raw signs.

Common Pitfalls and Debugging

  • Clusters reflect degree rather than community: normalization is unsuitable for skewed degrees. Compare symmetric/random-walk Laplacians.
  • Results change wildly across runs: weak eigengap or k-means instability. Repeat seeds and report adjusted agreement/stability.
  • Eigensolver is slow or runs out of memory: dense decomposition is used. Keep Laplacians sparse and request only the smallest needed eigenpairs.

Definition of Done

  • Laplacian variants pass symmetry, row-sum, PSD, and component tests where applicable.
  • Sparse eigenpair computation avoids full dense decomposition.
  • Trivial modes are correctly excluded and eigengap choice is explained.
  • Quality report includes cut/modularity, embedding metric, and seed stability.
  • Spectral clustering beats a raw-space baseline on a non-convex synthetic case.
  • Normalization tradeoffs are demonstrated on a degree-imbalanced graph.

Previous: Project 57 · Complete learning path · Next: Project 59