Graph Approximation and Clustering on a Budget
Abstract
We consider the problem of learning from a similarity matrix (such as spectral clustering and lowd imensional 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
Text
Fetaya et al. "Graph Approximation and Clustering on a Budget." International Conference on Artificial Intelligence and Statistics, 2015.Markdown
[Fetaya et al. "Graph Approximation and Clustering on a Budget." International Conference on Artificial Intelligence and Statistics, 2015.](https://mlanthology.org/aistats/2015/fetaya2015aistats-graph/)BibTeX
@inproceedings{fetaya2015aistats-graph,
title = {{Graph Approximation and Clustering on a Budget}},
author = {Fetaya, Ethan and Shamir, Ohad and Ullman, Shimon},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2015},
url = {https://mlanthology.org/aistats/2015/fetaya2015aistats-graph/}
}