AISTATS 2015poster9 citations
Graph Approximation and Clustering on a Budget
Ethan Fetaya, Ohad Shamir, Shimon Ullman
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.
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.}
}