Spectral Clustering

Graph Theory · Axiom Academy

Using eigenvectors of graph Laplacians to partition graphs into meaningful clusters The Laplacian matrix L of a graph G is defined as L = D - A, where D is the degree matrix (diagonal matrix of vertex degrees) and A is the adjacency matrix. L is symmetric and positive semi-definite The smallest eigenvalue is always 0 The number of 0 eigenvalues equals the number of connected components All eigenvalues are non-negative 2. The Fiedler Vector for 2-Way Partitioning The Fiedler vector is the eigenvector corresponding to the second-smallest eigenvalue of the Laplacian (called the algebraic connectivity). It provides an optimal way to partition a graph into two clusters. The Fiedler vector minimizes the cut between clusters while balancing their sizes, making it ideal for binary partitioning. 3. K-Way Clustering with Multiple Eigenvectors To partition a graph into k clusters, we use the first k eigenvectors corresponding to the k smallest eigenvalues of the Laplacian. Compute the Laplacian matrix L Find the k smallest eigenvalues and their eigenvectors Form matrix U with these eigenvectors as columns Treat each row of U as a point in k-dimensional space Apply k-means clustering to these points Assign vertices to clusters based on their row's cluster This embedding into eigenspace reveals the natural cluster structure that may be hidden in the original graph. 4. Normalized Laplacian for Balanced Clusters

This is the written version of the interactive lesson above. See the full Graph Theory course.