218590
20190525071229.0
ArXiv
1602.02018
CONF
Compressive Spectral Clustering
2016
2016
Conference Papers
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.
graph signal processing
spectral clustering
machine learning
Tremblay, Nicolas
242927
Puy, Gilles
179918
Gribonval, RĂ©mi
240428
Vandergheynst, Pierre
120906
33rd International Conference on Machine Learning (ICML)
New York, USA
June 19-24
252392
LTS2
U10380
oai:infoscience.tind.io:218590
conf
STI
GLOBAL_SET
120906
EPFL-CONF-218590
EPFL
REVIEWED
ACCEPTED
CONF