Graph Approximation and Clustering on a Budget

Ethan Fetaya, Ohad Shamir, Shimon Ullman

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:

  1. Cut Approximation: Ensuring the weight of every "cut" (edges between groups of nodes) in the sampled graph is close to the original.
  2. 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).

Performance of CLUS2K on synthetic datasets. The top row shows the "Two half circles" and "Four separated Gaussians" datasets. The bottom row shows cluster purity as a function of the percentage of edges sampled, demonstrating that CLUS2K (black line) reaches high purity faster than uniform sampling (blue) or other methods.

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

Abstract

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.
BibTeX
@inproceedings{fetaya2015graph,
  author = {Ethan Fetaya and Ohad Shamir and Shimon Ullman},
  title = {{Graph Approximation and Clustering on a Budget}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2015},
  url = {https://openreview.net/forum?id=PT2FtBYPxqx},
}

Loading related content...

Figure