Spectral Clustering on a Budget


Ohad Shamir, Naftali Tishby ;
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:661-669, 2011.


Spectral clustering is a modern and well known method for performing data clustering. However, it depends on the availability of a similarity matrix, which in many applications can be non-trivial to obtain. In this paper, we focus on the problem of performing spectral clustering under a budget constraint, where there is a limit on the number of entries which can be queried from the similarity matrix. We propose two algorithms for this problem, and study them theoretically and experimentally. These algorithms allow a tradeoff between computational efficiency and actual performance, and are also relevant for the problem of speeding up standard spectral clustering. [pdf][supplementary]

Related Material