Compressive Spectral Clustering

Abstract

Spectral clustering has become a popular technique due to its high performance in many contexts. It comprises three main steps: create a similarity graph between N objects to cluster, compute the first k eigenvectors of its Laplacian matrix to define a feature vector for each object, and run k-means on these features to separate objects into k classes. Each of these three steps becomes computationally intensive for large N and/or k. We propose to speed up the last two steps based on recent results in the emerging field of graph signal processing: graph filtering of random signals, and random sampling of bandlimited graph signals. We prove that our method, with a gain in computation time that can reach several orders of magnitude, is in fact an approximation of spectral clustering, for which we are able to control the error. We test the performance of our method on artificial and real-world network data.

12 pages, 2 figures

References in corpus (3)

• Discrete Signal Processing on Graphs
• Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
• Compressive spectral embedding: sidestepping the SVD

Cited by in corpus (17)

• Graph signal processing for machine learning: A review and new perspectives
• Fast Resampling of 3D Point Clouds via Graphs
• Greedy Sampling of Graph Signals
• Advances in Distributed Graph Filtering
• Approximate fast graph Fourier transforms via multi-layer sparse approximations
• A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization
• An Automated Spectral Clustering for Multi-scale Data
• Discriminative Transformation Learning for Fuzzy Sparse Subspace Clustering
• DCT and DST Filtering with Sparse Graph Operators
• Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian
• Graph reduction with spectral and cut guarantees
• Beyond Linear Subspace Clustering: A Comparative Study of Nonlinear Manifold Clustering Algorithms
• Blind Community Detection from Low-rank Excitations of a Graph Filter
• Spectral Analysis of Laplacians of an Unweighted and Weighted Multidimensional Grid Graph -- Combinatorial versus Normalized and Random Walk Laplacians
• What Happens on the Edge, Stays on the Edge: Toward Compressive Deep Learning
• A Compressive Sensing Approach to Community Detection with Applications
• Scalable Spectral Clustering Using Random Binning Features