Spectral Clustering

Traditional clustering algorithms like K-Means operate in a geometric paradigm: they assume clusters are compact, convex regions in feature space that can be characterized by centroids or prototypes. This assumption works beautifully for well-separated, spherical clusters—but catastrophically fails when clusters have complex shapes, manifold structures, or non-convex boundaries.

Spectral clustering represents a fundamental paradigm shift. Instead of treating data points as coordinates in Euclidean space, we view them as nodes in a graph where edges encode pairwise similarities. Clustering then becomes graph partitioning: finding cuts that separate the graph into coherent subgraphs while minimizing the connections severed.

This reformulation unlocks remarkable capabilities. Spectral methods can discover clusters that wrap around each other, separate interlocking rings, and detect communities in complex networks—all tasks where geometric methods fail completely.

To understand why spectral clustering exists, we must first confront the fundamental limitations of geometric clustering approaches. Consider the K-Means objective:

$$\min_{\mu_1, \ldots, \mu_k} \sum_{i=1}^{n} \min_{j} |x_i - \mu_j|^2$$

This objective minimizes the sum of squared distances from each point to its nearest centroid. The implicit assumption is devastating: clusters are Voronoi cells—convex polytopes defined by proximity to centroids. Any cluster that cannot be expressed as a Voronoi cell is fundamentally invisible to K-Means.

The Two Moons Problem illustrates this limitation dramatically. Two crescent-shaped clusters interlock like parentheses. Geometrically, points from different clusters may be closer to each other than points within the same cluster. K-Means fails spectacularly, typically splitting each moon in half rather than separating them.

The insight behind spectral clustering is profound: what matters for clustering is not absolute position, but connectivity patterns. If we construct a graph where similar points are connected, the cluster structure becomes visible as graph communities—densely connected subgraphs with sparse connections between them.

The graph perspective reveals hidden structure. When we translate the two moons problem into a graph where each point connects to its nearest neighbors, a clear picture emerges: points within each moon form densely connected chains, while only a few edges bridge between moons. The "correct" clustering is now obvious: cut those few bridge edges.

This intuition generalizes powerfully. Any clustering problem can be reframed as: Given a similarity graph, find a partition that keeps similar points together while separating dissimilar ones. The mathematical machinery of spectral graph theory then provides elegant tools to find optimal partitions.

The first step in spectral clustering is constructing a similarity graph $G = (V, E, W)$ where:

• Vertices $V = {1, 2, \ldots, n}$ correspond to data points $x_1, \ldots, x_n$
• Edges $E$ connect similar points
• Weights $W_{ij}$ quantify the similarity between points $i$ and $j$

The choice of how to construct this graph profoundly influences clustering results. Three main approaches dominate practice, each with distinct characteristics and trade-offs.

Understanding the Gaussian Kernel Weight Function:

The Gaussian (RBF) similarity is the most widely used:

$$W_{ij} = \exp\left(-\frac{|x_i - x_j|^2}{2\sigma^2}\right)$$

This function has elegant properties:

1. Bounded range: $W_{ij} \in (0, 1]$ with $W_{ii} = 1$
2. Self-similarity maximum: Identical points have weight 1
3. Smooth decay: Similarity decreases smoothly with distance
4. Locality control: σ determines the scale at which distances become significant

The parameter σ acts as a scale parameter. When $|x_i - x_j| \ll \sigma$, the weight is close to 1 (highly similar). When $|x_i - x_j| \gg \sigma$, the weight approaches 0 (effectively disconnected). A useful heuristic is to set σ based on the distribution of pairwise distances—often the median or a percentile of the distance distribution.

With a similarity graph constructed, clustering becomes graph partitioning: finding a division of vertices into groups such that within-group edges have high weight and between-group edges have low weight.

The Minimum Cut Problem:

Given a partition of vertices into disjoint sets $A$ and $B$ (where $A \cup B = V$ and $A \cap B = \emptyset$), the cut is the total weight of edges crossing between them:

$$\text{cut}(A, B) = \sum_{i \in A, j \in B} W_{ij}$$

A natural objective is to minimize this cut—sever as few connections as possible. For multiple clusters $C_1, \ldots, C_k$, we minimize:

$$\text{cut}(C_1, \ldots, C_k) = \frac{1}{2} \sum_{i=1}^{k} W(C_i, \bar{C_i})$$

where $\bar{C_i}$ denotes the complement of cluster $C_i$ and $W(A, B) = \sum_{i \in A, j \in B} W_{ij}$.

The Problem with Minimum Cut:

Unfortunately, naive minimum cut produces degenerate solutions. Consider a graph with 100 nodes and one outlier loosely connected to the main mass. The minimum cut would isolate that single outlier—technically minimizing cut weight but producing a useless "cluster" of size 1.

The minimum cut objective is biased toward cutting off small, isolated portions of the graph rather than finding balanced partitions. We need objective functions that account for cluster sizes.

Ratio Cut and Normalized Cut:

Two classical solutions normalize the cut by cluster size:

Ratio Cut (RatioCut): $$\text{RatioCut}(C_1, \ldots, C_k) = \sum_{i=1}^{k} \frac{\text{cut}(C_i, \bar{C_i})}{|C_i|}$$

Divides by the number of vertices in each cluster. Penalizes small clusters because $|C_i|$ appears in the denominator.

Normalized Cut (NCut): $$\text{NCut}(C_1, \ldots, C_k) = \sum_{i=1}^{k} \frac{\text{cut}(C_i, \bar{C_i})}{\text{vol}(C_i)}$$

where $\text{vol}(C) = \sum_{i \in C} d_i$ and $d_i = \sum_j W_{ij}$ is the degree of node $i$.

NCut normalizes by the total edge weight (volume) incident to each cluster, accounting for the connectivity of nodes rather than just their count. This is generally preferred and connects more naturally to random walk interpretations.

Computational Complexity:

Here's the critical challenge: finding the exact minimum of RatioCut or NCut is NP-hard. We cannot efficiently solve these problems by exhaustive search over all possible partitions—the number of partitions grows exponentially with $n$.

This is where spectral methods enter. By relaxing the discrete optimization problem (partitions) to a continuous one (real-valued vectors), we transform an intractable combinatorial problem into an eigenvalue problem solvable in polynomial time. The eigenvectors of graph Laplacian matrices provide approximate solutions to RatioCut and NCut that are, in practice, remarkably effective.

This connection—between graph cuts and eigenvalue problems—is the mathematical heart of spectral clustering and the subject of the following pages.

To build deep intuition, let's examine the simplest case: partitioning a graph into exactly two clusters. This reveals the core mathematics before generalizing to k clusters.

Indicator Vector Representation:

We encode a partition ${A, B}$ using an indicator vector $f \in \mathbb{R}^n$:

$$f_i = \begin{cases} \sqrt{|B|/|A|} & \text{if } i \in A \ -\sqrt{|A|/|B|} & \text{if } i \in B \end{cases}$$

This specific scaling ensures the vector is orthogonal to the constant vector and has unit norm in an appropriate sense. For the simple case of equal-sized clusters: $f_i = +1$ if $i \in A$, $f_i = -1$ if $i \in B$.

Connection to RatioCut:

A remarkable fact emerges: the RatioCut objective can be written as:

$$\text{RatioCut}(A, B) = \frac{f^T L f}{f^T f}$$

where $L$ is the graph Laplacian matrix (to be developed in the next page). This is a Rayleigh quotient—a ratio whose minimization over vectors is a classic eigenvalue problem!

Why This Matters:

Minimizing the Rayleigh quotient $f^T L f / f^T f$ over all vectors $f$ orthogonal to constants yields the second-smallest eigenvector of $L$—called the Fiedler vector.

The Fiedler vector provides a real-valued "ordering" of vertices that respects cluster structure:

1. Vertices in the same cluster tend to have similar Fiedler vector values
2. Vertices in different clusters tend to have different values
3. The sign of the Fiedler vector naturally suggests a binary partition

For two moons data, the Fiedler vector might assign positive values to all points in one moon and negative values to all points in the other—even though the moons geometrically interlock!

The Spectral Clustering Recipe (Two Clusters):

1. Construct similarity graph with weight matrix $W$
2. Compute graph Laplacian $L = D - W$ (where $D$ is diagonal degree matrix)
3. Find the Fiedler vector (second eigenvector of $L$)
4. Assign points to clusters based on the sign of their Fiedler vector component

This elegant procedure transforms a combinatorial nightmare into straightforward linear algebra.

The success of graph-based methods isn't accidental—it reflects deep mathematical principles about how graphs encode geometric and topological information.

Local Connectivity Preserves Global Structure:

Consider a point $x$ on one moon of the two moons dataset. Its K-nearest neighbors are all on the same moon (assuming noise is moderate). This point connects to its neighbors, those neighbors connect to their neighbors, and so on—forming a chain of connectivity tracing along the moon's shape.

The graph doesn't "know" about the moon's crescent shape in any explicit way. But the pattern of local connections implicitly encodes the manifold structure. When we analyze the graph spectrally, this structure is revealed and exploited.

Random Walk Interpretation:

A beautiful alternative view of spectral clustering comes from random walks. Imagine a random walker hopping between nodes, choosing the next node with probability proportional to edge weights.

The key insight: a random walker tends to stay within clusters if between-cluster edges are sparse. The walker will bounce around within densely connected regions before occasionally escaping to another.

The normalized cut objective exactly measures how quickly a random walk escapes from a cluster. Minimizing NCut finds partitions where random walks are "trapped" within clusters the longest—precisely what we want!

$$\text{NCut probability interpretation: } \frac{\text{cut}(A, \bar{A})}{\text{vol}(A)} = P(\text{transition out of } A | \text{currently in } A)$$

Manifold Structure and Geodesic Distance:

Graph-based clustering also connects to manifold learning. When data lies on a curved manifold embedded in high-dimensional space, Euclidean distance can be misleading—two points might be close in ambient space but far apart along the manifold.

Similarity graphs with local connectivity (like KNN graphs) approximate the manifold's topology. The geodesic distance (shortest path along the manifold) is approximated by the graph distance (shortest path along edges). Spectral clustering thus respects manifold structure in ways Euclidean methods cannot.

Multi-Scale Information:

Eigenvectors of the graph Laplacian capture structure at different scales:

• Lower eigenvectors (small eigenvalues): Capture broad, global structure. The Fiedler vector reveals the coarsest partition.
• Higher eigenvectors (larger eigenvalues): Capture finer, more local variations.

Using multiple eigenvectors for clustering ($k$ eigenvectors for $k$ clusters) leverages multi-scale information simultaneously, finding partitions that are optimal at both global and local levels.

Graph-based clustering extends far beyond standard data clustering, connecting to diverse fields and applications:

Image Segmentation:

Treat pixels as graph nodes, with edges connecting neighboring pixels weighted by color/texture similarity. Spectral clustering finds segments—contiguous regions of similar appearance. The normalized cut formulation was originally proposed for this application (Shi & Malik, 2000).

Community Detection in Networks:

Social networks, citation networks, and biological networks are naturally graphs. Spectral clustering discovers communities—groups of nodes more connected internally than externally. This is the same mathematical problem as data clustering!

Natural Language Processing:

Document similarity graphs enable document clustering. Word co-occurrence graphs support semantic analysis. Spectral methods find topics and categories without explicit labels.

Connections to Other Methods:

• Kernel K-Means: Spectral clustering is equivalent to kernel K-Means with specific kernels derived from the graph. The spectral embedding is the implicit feature space.

• Laplacian Eigenmaps: A dimensionality reduction technique that uses the same eigenvector computation. Spectral clustering adds the final clustering step after embedding.

• Diffusion Maps: Uses powers of the graph's transition matrix. Spectral clustering is related to the limit of diffusion as time goes to infinity.

• Graph Neural Networks: Modern GNNs can be seen as learnable versions of spectral methods, with message passing replacing fixed Laplacian eigenvectors.

Understanding spectral clustering provides deep insight into this entire family of graph-based machine learning methods.

We have established the conceptual foundation for spectral clustering—the shift from geometric to graph-theoretic thinking about cluster structure. Let's consolidate the key insights:

What's Next:

This page established the why and what of graph-based clustering. The next page dives into the how: the graph Laplacian matrix. We will formally define the Laplacian, derive its fundamental properties, and understand why its eigenvectors encode cluster structure. This mathematical foundation is essential for truly mastering spectral clustering.