Compressive Spectral Clustering

Nicolas Tremblay, Gilles Puy, Remi Gribonval, Pierre Vandergheynst
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:1002-1011, 2016.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-tremblay16, title = {Compressive Spectral Clustering}, author = {Tremblay, Nicolas and Puy, Gilles and Gribonval, Remi and Vandergheynst, Pierre}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {1002--1011}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/tremblay16.pdf}, url = {https://proceedings.mlr.press/v48/tremblay16.html}, 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.} }
Endnote
%0 Conference Paper %T Compressive Spectral Clustering %A Nicolas Tremblay %A Gilles Puy %A Remi Gribonval %A Pierre Vandergheynst %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-tremblay16 %I PMLR %P 1002--1011 %U https://proceedings.mlr.press/v48/tremblay16.html %V 48 %X 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.
RIS
TY - CPAPER TI - Compressive Spectral Clustering AU - Nicolas Tremblay AU - Gilles Puy AU - Remi Gribonval AU - Pierre Vandergheynst BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-tremblay16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 1002 EP - 1011 L1 - http://proceedings.mlr.press/v48/tremblay16.pdf UR - https://proceedings.mlr.press/v48/tremblay16.html AB - 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. ER -
APA
Tremblay, N., Puy, G., Gribonval, R. & Vandergheynst, P.. (2016). Compressive Spectral Clustering. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:1002-1011 Available from https://proceedings.mlr.press/v48/tremblay16.html.

Related Material