Large-scale spectral clustering

Spectral Clustering

Spectral clustering aims to partition the data points into k clusters using the spectrum of the graph Laplacians Given a dataset X with N data points, spectral clustering algorithm first constructs similarity matrix W, where wᵢⱼ indicates the similarity between data points xᵢ and xⱼ via a similarity measure metric.

Let L=D-W, where L is called graph Laplacian and D is a diagonal matrix with dᵢᵢ = ∑ⱼ₌₁ⁿ wᵢⱼ. The objective function of spectral clustering can be formulated based on the graph Laplacian as follow: max_U tr(Uᵀ L U), s.t. Uᵀ U=I, where tr(·) denotes the trace norm of a matrix. The rows of matrix U are the low dimensional embedding of the original data points. Generally, spectral clustering computes U as the bottom k eigenvectors of L, and finally applies k-means on U to obtain the clustering results.

Large-scale Spectral Clustering

To capture the relationship between all data points in X, an N×N similarity matrix is needed to be constructed in conventional spectral clustering, which costs O(N²d) time and O(N²) memory and is not feasible for large-scale clustering tasks. Instead of a full similarity matrix, many accelerated spectral clustering methods are using a similarity sub-matrix to represent each data points by the cross-similarity between data points and a set of representative data points (i.e., landmarks) via some similarity measures, as B = Φ(X,R), where R = {r₁,r₂,…, rₚ } (p ≪N) is a set of landmarks with the same dimension to X, Φ(·) indicate a similarity measure metric, and B∈ℝ^(N×p) is the similarity sub-matrix to represent the X ∈ℝ^(N×d) with respect to the R∈ℝ^(p×d).

For large-scale spectral clustering using such similarity matrix, a symmetric similarity matrix W can be designed as W=[[ 0 B ;; Bᵀ 0 ]]. The size of matrix W is (N+p)×(N+p). Taking the advantage of the bipartite structure, some fast eigen-decomposition methods can then be used to obtain the spectral embedding. Finally, k-means is conducted on the embedding to obtain clustering results.

The clustering result is directly related to the quality of B that consists of the similarities between data points and landmarks. Thus, the performance of landmark selection is crucial to the clustering result.