Graph Approximation and Clustering on a Budget
This work addresses the challenge of efficient graph-based learning for applications with expensive similarity computations, offering a more general and practical solution.
The paper tackles the problem of learning from similarity matrices when only a limited number of costly pairwise similarities can be observed, providing a theoretical analysis that generalizes prior results and proposing an adaptive sampling algorithm that matches or improves on previous methods while being more general and computationally cheaper.
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.