Spectral clustering

A 2-dimensional spring system.

Spectral clustering is well known to relate to partitioning of a mass-spring system, where each mass is associated with a data point and each spring stiffness corresponds to a weight of an edge describing a similarity of the two related data points, as in the spring system. Specifically, the classical reference [1] explains that the eigenvalue problem describing transversal vibration modes of a mass-spring system is exactly the same as the eigenvalue problem for the graph Laplacian matrix defined as

${\displaystyle L:=D-A}$,

where ${\displaystyle D}$ is the diagonal matrix

${\displaystyle D_{ii}=\sum _{j}A_{ij},}$

and A is the adjacency matrix.

The masses that are tightly connected by the springs in the mass-spring system evidently move together from the equilibrium position in low-frequency vibration modes, so that the components of the eigenvectors corresponding to the smallest eigenvalues of the graph Laplacian can be used for meaningful clustering of the masses. For example, assuming that all the springs and the masses are identical in the 2-dimensional spring system pictured, one would intuitively expect that the loosest connected masses on the right-hand side of the system would move with the largest amplitude and in the opposite direction to the rest of the masses when the system is shaken — and this expectation will be confirmed by analyzing components of the eigenvectors of the graph Laplacian corresponding to the smallest eigenvalues, i.e., the smallest vibration frequencies.

The goal of normalization is making the diagonal entries of the Laplacian matrix to be all unit, also scaling off-diagonal entries correspondingly. In a weighted graph, a vertex may have a large degree because of a small number of connected edges but with large weights just as well as due to a large number of connected edges with unit weights.

A popular normalized spectral clustering technique is the normalized cuts algorithm or Shi–Malik algorithm introduced by Jianbo Shi and Jitendra Malik,[2] commonly used for image segmentation. It partitions points into two sets ${\displaystyle (B_{1},B_{2})}$ based on the eigenvector ${\displaystyle v}$ corresponding to the second-smallest eigenvalue of the symmetric normalized Laplacian defined as

${\displaystyle L^{\text{norm}}:=I-D^{-1/2}AD^{-1/2}.}$

The vector ${\displaystyle v}$ is also the eigenvector corresponding to the second-largest eigenvalue of the symmetrically normalized adjacency matrix ${\displaystyle D^{-1/2}AD^{-1/2}.}$

The random walk (or left) normalized Laplacian is defined as

${\displaystyle L^{\text{rw}}:=D^{-1}L=I-D^{-1}A}$

and can also be used for spectral clustering. A mathematically equivalent algorithm [3] takes the eigenvector ${\displaystyle u}$ corresponding to the largest eigenvalue of the random walk normalized adjacency matrix ${\displaystyle P=D^{-1}A}$.

The eigenvector ${\displaystyle v}$ of the symmetrically normalized Laplacian and the eigenvector ${\displaystyle u}$ of the left normalized Laplacian are related by the identity ${\displaystyle D^{-1/2}v=u.}$

Knowing the ${\displaystyle n}$-by-${\displaystyle k}$ matrix ${\displaystyle V}$ of selected eigenvectors, mapping — called spectral embedding — of the original ${\displaystyle n}$ data points is performed to a ${\displaystyle k}$-dimensional vector space using the rows of ${\displaystyle V}$. Now the analysis is reduced to clustering vectors with ${\displaystyle k}$ components, which may be done in various ways.

In the simplest case ${\displaystyle k=1}$, the selected single eigenvector ${\displaystyle v}$, called the Fiedler vector, corresponds to the second smallest eigenvalue. Using the components of ${\displaystyle v,}$ one can place all points whose component in ${\displaystyle v}$ is positive in the set ${\displaystyle B_{+}}$ and the rest in ${\displaystyle B_{-}}$, thus bi-partitioning the graph and labeling the data points with two labels. This sign-based approach follows the intuitive explanation of spectral clustering via the mass-spring model — in the low frequency vibration mode that the Fiedler vector ${\displaystyle v}$ represents, one cluster data points identified with mutually strongly connected masses would move together in one direction, while in the complement cluster data points identified with remaining masses would move together in the opposite direction. The algorithm can be used for hierarchical clustering by repeatedly partitioning the subsets in the same fashion.

In the general case ${\displaystyle k>1}$, any vector clustering technique can be used, e.g., DBSCAN.

The graph Laplacian can be and commonly is constructed from the adjacency matrix. The construction can be performed matrix-free, i.e., without explicitly forming the matrix of the graph Laplacian and no AO. It can also be performed in-place of the adjacency matrix without increasing the memory footprint. Either way, the costs of constructing the graph Laplacian is essentially determined by the costs of constructing the ${\displaystyle n}$-by-${\displaystyle n}$ graph adjacency matrix.

Moreover, a normalized Laplacian has exactly the same eigenvectors as the normalized adjacency matrix, but with the order of the eigenvalues reversed. Thus, instead of computing the eigenvectors corresponding to the smallest eigenvalues of the normalized Laplacian, one can equivalently compute the eigenvectors corresponding to the largest eigenvalues of the normalized adjacency matrix, without even talking about the Laplacian matrix.

Naive constructions of the graph adjacency matrix, e.g., using the RBF kernel, make it dense, thus requiring ${\displaystyle n^{2}}$ memory and ${\displaystyle n^{2}}$ AO to determine each of the ${\displaystyle n^{2}}$ entries of the matrix. Nystrom method[6] can be used to approximate the similarity matrix, but the approximate matrix is not elementwise positive,[7] i.e. cannot be interpreted as a distance-based similarity.

Algorithms to construct the graph adjacency matrix as a sparse matrix are typically based on a nearest neighbor search, which estimate or sample a neighborhood of a given data point for nearest neighbors, and compute non-zero entries of the adjacency matrix by comparing only pairs of the neighbors. The number of the selected nearest neighbors thus determines the number of non-zero entries, and is often fixed so that the memory footprint of the ${\displaystyle n}$-by-${\displaystyle n}$ graph adjacency matrix is only ${\displaystyle O(n)}$, only ${\displaystyle O(n)}$ sequential arithmetic operations are needed to compute the ${\displaystyle O(n)}$ non-zero entries, and the calculations can be trivially run in parallel.

The cost of computing the ${\displaystyle n}$-by-${\displaystyle k}$ (with ${\displaystyle k\ll n}$) matrix of selected eigenvectors of the graph Laplacian is normally proportional to the cost of multiplication of the ${\displaystyle n}$-by-${\displaystyle n}$ graph Laplacian matrix by a vector, which varies greatly whether the graph Laplacian matrix is dense or sparse. For the dense case the cost thus is ${\displaystyle O(n^{2})}$. The very commonly cited in the literature cost ${\displaystyle O(n^{3})}$ comes from choosing ${\displaystyle k=n}$ and is clearly misleading, since, e.g., in a hierarchical spectral clustering ${\displaystyle k=1}$ as determined by the Fiedler vector.

In the sparse case of the ${\displaystyle n}$-by-${\displaystyle n}$ graph Laplacian matrix with ${\displaystyle O(n)}$ non-zero entries, the cost of the matrix-vector product and thus of computing the ${\displaystyle n}$-by-${\displaystyle k}$ with ${\displaystyle k\ll n}$ matrix of selected eigenvectors is ${\displaystyle O(n)}$, with the memory footprint also only ${\displaystyle O(n)}$ — both are the optimal low bounds of complexity of clustering ${\displaystyle n}$ data points. Moreover, matrix-free eigenvalue solvers such as LOBPCG can efficiently run in parallel, e.g., on multiple GPUs with distributed memory, resulting not only in high quality clusters, which spectral clustering is famous for, but also top performance. [8]

The weighted kernel k-means problem[16] shares the objective function with the spectral clustering problem, which can be optimized directly by multi-level methods.[17]

In the trivial case of determining connected graph components — the optimal clusters with no edges cut — spectral clustering is also related to a spectral version of DBSCAN clustering that finds density-connected components.[18]