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 queried. This paper introduces a way to perform spectral clustering and graph analysis when you can only afford to compute a tiny fraction of the similarity matrix. The authors provide new theoretical guarantees for graph approximation and propose CLUS2K, an adaptive sampling algorithm that is both more accurate and significantly faster than previous state-of-the-art methods.
The Challenge of Large-Scale Similarity Matrices
Many powerful unsupervised learning algorithms—like spectral clustering, Laplacian eigenmaps, and diffusion maps—rely on a similarity matrix ($W$) that describes how alike every pair of points in a dataset is. For a dataset of size $n$, this matrix has $n^2$ entries.
The "budget" problem arises because computing these similarities can be incredibly expensive. Whether the similarity metric is computationally heavy (e.g., complex image descriptors), requires physical measurements (in biology), or relies on human annotators, we often cannot afford to compute the full $O(n^2)$ matrix. We need to "query" a limited number of entries and still produce a high-quality clustering or graph approximation. While previous theoretical work was largely restricted to simple two-cluster cases, this paper aims for a general solution for $k$ clusters.
Theoretical Approximation and CLUS2K
The authors tackle the problem through two lenses: theoretical bounds and a new algorithm.
1. Theoretical Approximation
They analyze how many edges $m$ need to be sampled to achieve a good spectral approximation (ensuring the approximated Laplacian matrix behaves like the original) and cut approximation (ensuring the weight of "cuts" between groups of nodes is preserved).
- Uniform Sampling: The authors show that if a graph is "well-connected" (high expansion), uniform random sampling works well.
- Negative Dependence: They use a sophisticated probabilistic tool called "negative dependence" to prove that sampling edges without replacement is at least as good as sampling with replacement, simplifying the math for real-world sampling scenarios.
2. The CLUS2K Algorithm
Uniform sampling fails when a graph has very small "cuts" (few edges between clusters), as random queries will likely miss the few edges that actually connect the clusters. To fix this, they propose CLUS2K:
- Hybrid Sampling: For every query, it flips a coin. 50% of the time it samples an edge uniformly at random to maintain a global view. The other 50% of the time it uses an adaptive strategy.
- Adaptive Strategy: It clusters the currently observed graph into $2k$ clusters (over-segmentation). It then randomly picks two of these clusters and queries an edge between them. This "targets" the gaps in the current knowledge.
- Efficiency: Unlike previous methods that required a full, expensive eigen-decomposition at every step to find "sensitive" edges, CLUS2K uses a much simpler clustering-based approach, making it practical for larger scales.
Experimental Evaluation
The authors evaluated their approach on both synthetic and real-world datasets, including "Two half circles," "Four separated Gaussians," and real-world benchmarks like Iris, Glass, and Caltech-7.
Key Results
- Accuracy (Purity): CLUS2K consistently matched or outperformed existing state-of-the-art adaptive sampling methods across all datasets. As shown in the synthetic experiments, CLUS2K reaches near-perfect purity much faster than uniform sampling.
- Sample Efficiency: On the Caltech-7 dataset, CLUS2K reached near-peak accuracy (purity $\approx 0.8$) using only a small fraction of the possible edges.
- Robustness: While competing algorithms like IU_RED performed poorly on datasets with more than two clusters ($k > 2$), CLUS2K scaled gracefully to higher cluster counts.
Conclusion
CLUS2K addresses the computational hurdles of spectral clustering by replacing expensive eigen-decompositions with a simpler iterative clustering-based approach. By leveraging over-segmentation ($2k$ clusters), the algorithm avoids getting stuck in local minima and aggressively finds missing links between components. The result is a robust, computationally cheap method that maintains high purity even under strict query budgets.
Summary updated