Compressive Spectral Clustering
combining graph signal processing and compressed sensing to accelerate spectral clustering
Given a set of N data points {x_1, x_2, ..., x_N}, spectral clustering (SC) partitions this set into k weakly inter-connected clusters. Several spectral clustering algorithms exist (see references of the litterature in our our paper) but all follow the same scheme. First, compute weights Wij > 0 that model the similarity between pairs of data points (x_i, x_j). This gives rise to a graph G with N nodes and adjacency matrix W. Second, compute the first k eigenvectors Uk := (u_1, ... ,u_k) of the Laplacian matrix L associated to G. And finally, run k-means using the rows of Uk as feature vectors to partition the N data points into k clusters.
We propose a compressive spectral clustering method that accelerates the classical SC algorithm by bypassing both the exact partial diagonalisation of L and the k-means step at high dimension. It can be summarised as follows:
1) generate a feature vector for each node by filtering O(log(k)) random Gaussian signals on G;
2) sample O(k log(k)) nodes from the full set of nodes;
3) cluster the reduced set of nodes;
4) interpolate the cluster indicator vectors back to the complete graph.
We prove that our method, with a gain in computation time that can reach several orders of magnitude, is in fact an approximation of SC, for which we are able to control the error.
Associated paper: Nicolas Tremblay, Gilles Puy, Rémi Gribonval, Pierre Vandergheynst. Compressive Spectral Clustering. In ARXIV, 1602.02018, 2016. [PDF]