Compressive Spectral Clustering
By Nicolas Tremblay, Gilles Puy, Rémi Gribonval, Pierre Vandergheynst. 2016
119 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Representation & Self-Supervised Learning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Pascal Frossard
- Pierre Vandergheynst
- Xavier Bresson
- Antonio Ortega
- Michaël Defferrard
- José M. F. Moura
- Jelena Kovacevic
- Michael M. Bronstein
In Statistical and Nonlinear Physics
- Pascal Frossard
- Pierre Vandergheynst
- Xavier Bresson
- Michaël Defferrard
- Antonio Ortega
- José M. F. Moura
- Jelena Kovacevic
- Michael M. Bronstein
In Representation & Self-Supervised Learning
- Huaimin Wang
- José M. F. Moura
- Dinggang Shen
- Antonio Ortega
- Chang-Fu Tang
- Jianping Yin
- Pierre Vandergheynst
- Pascal Frossard
Citations in the corpus
- Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering (2016, background): “In [35], the authors investigated compressed sensing recovery conditions for graph spectral signal analysis.”
- Graph Signal Processing: Overview, Challenges, and Applications (2017, methodology): “example, spectral clustering methods use the low frequency eigenvectors of the Laplacian [13] and can thus be addressed from a GSP perspective too [14].”
- Late Fusion Incomplete Multi-view Clustering (2018, methodology): “Note that any technique that can boost the scalability of kernel kmeans (or spectral clustering) such as [33] can be directly applied to ours to shorten this initialization.”