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.
Introduction
Many popular unsupervised learning algorithms—such as spectral clustering, Laplacian eigenmaps, and diffusion maps—rely on a "similarity matrix" that defines how alike every pair of objects in a dataset is. In an ideal world, the full matrix is available. However, in practical applications, calculating these similarities can be prohibitively expensive, requiring physical experiments, complex biological simulations, or slow human annotations.
This paper addresses the challenge of accurately clustering or embedding data by observing only a tiny fraction of the possible pairwise similarities. While previous research was often restricted to simple cases (e.g., two-cluster partitions) and relied on heavy computational steps, this work seeks a general theory for graph approximation and a practical algorithm that scales to any number of clusters efficiently.
Methods
The authors approach the problem through a dual lens of theoretical analysis and algorithmic design.
Theoretical Framework
The analysis focuses on two types of graph approximations:
- Cut Approximation: Ensuring the weight of every "cut" (edges between groups of nodes) in the sampled graph is close to the original.
- Spectral Approximation: A stronger condition ensuring the Laplacian matrix of the sampled graph behaves similarly to the original, preserving structural properties.
A key technical contribution is the application of negative dependence. Since edges are sampled without replacement, standard concentration bounds (like Chernoff-Hoeffding) are shown to still hold, allowing for proofs on the number of samples needed for a guaranteed approximation.
The CLUS2K Algorithm
The authors introduce CLUS2K, an adaptive sampling strategy that "hunts" for informative edges. The algorithm employs a 50/50 mix:
- Exploration: 50% of samples are chosen uniformly at random.
- Exploitation (Adaptive): The remaining 50% use an over-segmentation strategy. The current observed graph is clustered into $2k$ clusters (where $k$ is the target number). The algorithm then queries edges connecting randomly selected pairs of these clusters. This "bridging" helps identify missing links that merge components and define true cluster boundaries.
Experimental Results
The approach was evaluated on synthetic benchmarks (Two Half-Circles, Four Separated Gaussians) and real-world datasets (Iris, Glass, Caltech-7).
Key findings include:
- Superior Purity: CLUS2K consistently reached higher cluster purity faster than uniform sampling or previous adaptive methods across most tests.
- Multi-Cluster Scalability: Unlike previous methods that struggled when $k > 2$, CLUS2K handled the 4-cluster Gaussian and 7-cluster Caltech datasets effectively.
- Efficiency: On the "Four Gaussians" dataset, CLUS2K achieved near-perfect purity after sampling only ~10% of edges, whereas uniform sampling required significantly more data.
Discussion and Future Work
The authors demonstrate that "clusterable" graphs—those with strong internal connections and weak external ones—can be approximated with far fewer samples than general graphs. The use of over-segmentation ($2k$ clusters) is a critical insight, making the algorithm sensitive to fine-grained structures.
While the adaptive part of the algorithm currently lacks the same level of general theoretical guarantees as the uniform sampling part, its empirical performance is robust. Future work may extend this "budgeted" approach to semi-supervised learning or manifold learning, where the cost of similarity computation remains a primary bottleneck.
Summary updated