Theoretical Foundations of Spectral Clustering

Spectral Clustering is a powerful technique rooted in graph theory and linear algebra. It is particularly effective in scenarios where clusters are not easily separable by conventional methods like K-Means. In this article, we delve into the mathematical foundations of Spectral Clustering, covering key concepts such as similarity graphs, graph Laplacians, and eigenvalue decomposition.

1. Overview of Spectral Clustering

Spectral Clustering can be viewed as a graph partitioning problem. The main idea is to represent the data points as nodes in a graph, with edges connecting pairs of nodes that are similar. The problem of clustering then becomes one of partitioning this graph into subgraphs (clusters) such that the connections (similarities) between points within the same cluster are strong, while those between different clusters are weak.

2. Constructing the Similarity Graph

The first step in Spectral Clustering is constructing a similarity graph, which encodes the relationships between data points.

2.1 Similarity Matrix

Given a dataset $\{x_1, x_2, \dots, x_n\}$, the similarity between two points $x_i$ and $x_j$ is often represented by a similarity function $s(x_i, x_j)$. This leads to the similarity matrix $S$, where each entry $S_{ij} = s(x_i, x_j)$.

Common Similarity Functions

• Gaussian (RBF) Kernel:

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

  where $\sigma$ is a scale parameter controlling the width of the Gaussian kernel.

• k-Nearest Neighbors (k-NN): A directed neighbor relation must be converted to the symmetric, non-negative affinity expected by the spectral method—for example, by connecting $i$ and $j$ when either is a neighbor of the other. The neighbor count and feature metric can join or disconnect whole regions.

2.2 Types of Graphs

• Fully Connected Graph: Every pair of points is connected, with edge weights given by the similarity function. This approach is computationally expensive for large datasets.

• k-Nearest Neighbors Graph: Each point is connected to its k-nearest neighbors. This graph is sparse and more scalable for larger datasets.

• $\epsilon$-Neighborhood Graph: Points are connected if their distance is less than some threshold $\epsilon$. This method is sensitive to the choice of $\epsilon$.

3. Graph Laplacian

Once the similarity graph is constructed, the next step is to compute the graph Laplacian, a matrix that plays a central role in the clustering process.

3.1 Degree Matrix

The degree matrix $D$ is a diagonal matrix where each diagonal element $D_{ii}$ represents the sum of the similarities connected to node $i$:

$$D_{ii} = \sum_{j} S_{ij}$$

3.2 Graph Laplacian

There are several forms of the graph Laplacian, but the most common ones are:

• Unnormalized Laplacian:

  $$L = D - S$$

• Normalized Laplacian:

  $$L_{\text{sym}} = I - D^{-1/2} S D^{-1/2}$$

  or

  $$L_{\text{rw}} = I - D^{-1} S$$

Where $I$ is the identity matrix. The normalized Laplacians are particularly useful because they help to address issues with varying densities in the data.

3.3 Properties of the Laplacian

• Eigenvalues: The eigenvalues of the graph Laplacian provide important information about the structure of the graph. The smallest eigenvalue $\lambda_1$ of the unnormalized Laplacian is always 0, corresponding to the eigenvector $\mathbf{1}$ (a vector of all ones). The second smallest eigenvalue $\lambda_2$ is known as the algebraic connectivity and reflects how well connected the graph is.

• Eigenvectors and connected components: The multiplicity of eigenvalue zero equals the number of connected components. Standard normalized spectral clustering uses the eigenvectors associated with the smallest eigenvalues, including the trivial one in the idealized $k$-component case; the exact convention depends on the Laplacian formulation. It is therefore wrong to always discard the zero eigenvector.

4. Spectral Clustering Algorithm

4.1 Step-by-Step Procedure

1. Construct the Similarity Graph: Compute the similarity matrix $S$ and construct the graph.

2. Compute the Laplacian: Calculate the graph Laplacian $L$, using either the unnormalized or normalized form.

3. Eigenvalue Decomposition: Solve the eigenvalue problem for the Laplacian to obtain the eigenvalues and eigenvectors:

   $$L \mathbf{v} = \lambda \mathbf{v}$$

4. Select k Smallest Eigenvectors: Select the eigenvectors corresponding to the $k$ smallest eigenvalues under the chosen normalized-Laplacian formulation. Row normalization is part of the common Ng-Jordan-Weiss variant.

5. Cluster the Rows of V: Treat the rows of $V$ as data points in a lower-dimensional space and apply a standard clustering algorithm like K-Means to these points to obtain the final clusters.

4.2 Mathematical Example

Consider a simple dataset with four points:

$$\{x_1 = (0, 0), x_2 = (1, 0), x_3 = (3, 0), x_4 = (4, 0)\}$$

Using a Gaussian kernel with $\sigma = 1$, the similarity matrix $S$ is:

$$S = \begin{pmatrix} 1 & 0.6065 & 0.0111 & 0.0003 \\ 0.6065 & 1 & 0.6065 & 0.0111 \\ 0.0111 & 0.6065 & 1 & 0.6065 \\ 0.0003 & 0.0111 & 0.6065 & 1 \end{pmatrix}$$

The degree matrix $D$ is:

$$D = \begin{pmatrix} 1.6179 & 0 & 0 & 0 \\ 0 & 2.2241 & 0 & 0 \\ 0 & 0 & 2.2241 & 0 \\ 0 & 0 & 0 & 1.6179 \end{pmatrix}$$

The unnormalized Laplacian $L$ is then:

$$L = D - S = \begin{pmatrix} 0.6179 & -0.6065 & -0.0111 & -0.0003 \\ -0.6065 & 1.2241 & -0.6065 & -0.0111 \\ -0.0111 & -0.6065 & 1.2241 & -0.6065 \\ -0.0003 & -0.0111 & -0.6065 & 0.6179 \end{pmatrix}$$

Solving the eigenvalue problem for $L$, we find the eigenvalues $\lambda$ and eigenvectors $\mathbf{v}$. The smallest non-zero eigenvalues provide the clustering information.

4.3 Geometric Interpretation

The eigenvectors corresponding to the smallest eigenvalues give a relaxed graph-cut representation. They do not guarantee that the discrete partition is uniquely correct. Graph construction, connected components, eigensolver tolerances, and the final label-assignment method all affect the result.

5. Cost and validation

A dense affinity matrix has quadratic memory cost in the sample count, and a dense eigendecomposition can be cubic in the worst case. Sparse nearest-neighbor graphs and iterative eigensolvers reduce practical cost but do not make the method automatically suitable for very large data. Validate graph connectivity and stability across justified graph parameters. When labels are unavailable, internal indices are only diagnostics because they encode their own geometric assumptions; do not tune an unsupervised estimator with ordinary GridSearchCV unless a defensible external scoring target and validation design exist.

5. Conclusion

Spectral Clustering is a mathematically rich method that leverages the power of graph theory and linear algebra to uncover complex cluster structures in data. By transforming the clustering problem into an eigenvalue problem, Spectral Clustering can identify clusters that are not easily detected by traditional methods. Understanding the theory behind this method allows practitioners to apply it effectively to a wide range of datasets, especially those with intricate structures.