Graph Approximation and Clustering on a Budget

TitleGraph Approximation and Clustering on a Budget
Publication TypeConference Proceedings
Year of Publication2015
AuthorsFetaya, E, Shamir, O, Ullman, S
Conference NameArtificial Intelligence and Statistics

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


Research Area: 

CBMM Relationship: 

  • CBMM Related