Graph Approximation and Clustering on a Budget

Ethan Fetaya, Ohad Shamir, Shimon Ullman
Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38:241-249, 2015.

Abstract

We consider the problem of learning from a similarity matrix (such as spectral clustering and low-dimensional embedding), when computing pairwise similarities are costly, and only a limited number of entries can be observed. We provide a theoretical analysis using standard notions of graph approximation, significantly generalizing previous results, which focused on spectral clustering with two clusters. We also propose a new algorithmic approach based on adaptive sampling, which experimentally matches or improves on previous methods, while being considerably more general and computationally cheaper.

Cite this Paper

BibTeX
@InProceedings{pmlr-v38-fetaya15, title = {{Graph Approximation and Clustering on a Budget}}, author = {Fetaya, Ethan and Shamir, Ohad and Ullman, Shimon}, booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics}, pages = {241--249}, year = {2015}, editor = {Lebanon, Guy and Vishwanathan, S. V. N.}, volume = {38}, series = {Proceedings of Machine Learning Research}, address = {San Diego, California, USA}, month = {09--12 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v38/fetaya15.pdf}, url = {https://proceedings.mlr.press/v38/fetaya15.html}, abstract = {We consider the problem of learning from a similarity matrix (such as spectral clustering and low-dimensional embedding), when computing pairwise similarities are costly, and only a limited number of entries can be observed. We provide a theoretical analysis using standard notions of graph approximation, significantly generalizing previous results, which focused on spectral clustering with two clusters. We also propose a new algorithmic approach based on adaptive sampling, which experimentally matches or improves on previous methods, while being considerably more general and computationally cheaper.} }
Endnote
%0 Conference Paper %T Graph Approximation and Clustering on a Budget %A Ethan Fetaya %A Ohad Shamir %A Shimon Ullman %B Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2015 %E Guy Lebanon %E S. V. N. Vishwanathan %F pmlr-v38-fetaya15 %I PMLR %P 241--249 %U https://proceedings.mlr.press/v38/fetaya15.html %V 38 %X We consider the problem of learning from a similarity matrix (such as spectral clustering and low-dimensional embedding), when computing pairwise similarities are costly, and only a limited number of entries can be observed. We provide a theoretical analysis using standard notions of graph approximation, significantly generalizing previous results, which focused on spectral clustering with two clusters. We also propose a new algorithmic approach based on adaptive sampling, which experimentally matches or improves on previous methods, while being considerably more general and computationally cheaper.
RIS
TY - CPAPER TI - Graph Approximation and Clustering on a Budget AU - Ethan Fetaya AU - Ohad Shamir AU - Shimon Ullman BT - Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics DA - 2015/02/21 ED - Guy Lebanon ED - S. V. N. Vishwanathan ID - pmlr-v38-fetaya15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 38 SP - 241 EP - 249 L1 - http://proceedings.mlr.press/v38/fetaya15.pdf UR - https://proceedings.mlr.press/v38/fetaya15.html AB - We consider the problem of learning from a similarity matrix (such as spectral clustering and low-dimensional embedding), when computing pairwise similarities are costly, and only a limited number of entries can be observed. We provide a theoretical analysis using standard notions of graph approximation, significantly generalizing previous results, which focused on spectral clustering with two clusters. We also propose a new algorithmic approach based on adaptive sampling, which experimentally matches or improves on previous methods, while being considerably more general and computationally cheaper. ER -
APA
Fetaya, E., Shamir, O. & Ullman, S.. (2015). Graph Approximation and Clustering on a Budget. Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 38:241-249 Available from https://proceedings.mlr.press/v38/fetaya15.html.

Related Material