Query Complexity of Clustering with Side Information

Arya Mazumdar, Barna Saha

Introduction

In many real-world data processing tasks, such as Entity Resolution, automated clustering algorithms often struggle with noisy data. For instance, determining whether "M. Weldon" and "Marcus Weldon" represent the same individual in a database can be highly ambiguous. To resolve these ambiguities, practitioners frequently employ a "human-in-the-loop" approach, querying a domain expert (an oracle) with pairwise questions: "Do these two elements belong to the same cluster?"

Standard theoretical models dictate that clustering $n$ elements into $k$ unknown clusters requires $\Theta(nk)$ queries. For large-scale datasets, this linear dependence on $n$ makes interactive clustering prohibitively expensive. To circumvent this, practitioners often rely on "side information"—noisy similarity scores between elements derived from metadata—to guide their queries. While empirically successful, there has been a significant gap in formal theory explaining exactly how much side information helps and what the fundamental limits of this approach are. This paper provides a rigorous theoretical foundation for interactive clustering with side information, demonstrating that query complexity can be reduced from a linear to a logarithmic dependence on $n$.

Theoretical Framework: The Power of Side Information

The authors model side information as a similarity matrix representing noisy pairwise relationships. Specifically, similarity values are drawn independently from a probability distribution $f_+$ if the underlying pair of elements belongs to the same cluster, and from a distribution $f_-$ if they belong to different clusters.

The Hellinger Connection

A central contribution of this work is identifying the squared Hellinger divergence ($\mathcal{H}^2$) between $f_+$ and $f_-$ as the critical measure of noise. The harder it is to distinguish between the two distributions, the more queries the algorithm must ask. The authors chose Hellinger distance over the more commonly used Kullback-Leibler (KL) divergence because it is a true metric, which is essential for establishing the concentration bounds used in their proofs.

By leveraging this framework, the authors prove an exponential speedup in query efficiency. With side information, the query complexity drops drastically from $\Theta(nk)$ to $O(\frac{k^2 \log n}{\mathcal{H}^2(f_+ \| f_-)})$. This establishes that the algorithm's query complexity is information-theoretically optimal within an $O(\log n)$ factor.

Generalizing the Stochastic Block Model

This problem formulation serves as a significant generalization of the Stochastic Block Model (SBM), a popular framework for community detection in graphs. The paper demonstrates how active, adaptive queries can effectively "break" the traditional recovery thresholds associated with standard SBMs.

Algorithmic Approach

Beyond theoretical bounds, the authors propose practical, efficient, and "parameter-free" algorithms (both Monte Carlo and Las Vegas variants). These algorithms do not require prior knowledge of the number of clusters $k$, or the noise distributions $f_+$ and $f_-$; instead, they learn these parameters on the fly.

The algorithm operates in three distinct phases:

  1. Phase 1 (Bootstrap): The algorithm randomly queries elements to grow at least one cluster to a statistically significant size of $O(\log n)$.
  2. Phase 2 (Iterative Estimation): Using the clusters grown in the first phase, the algorithm estimates the underlying distributions $f_+$ and $f_-$.
  3. Phase 3 (Adaptive Querying): For new elements, the algorithm calculates a "Membership" score based on the Hellinger distance. If the score is definitively high or low, the algorithm trusts the side information and assigns the element without querying the oracle. It only expends a query if the score falls into a "gray region" of uncertainty.

Empirical Validation

To validate their theoretical findings, the authors evaluated their approach on the Cora bibliographic dataset, which consists of 1,879 nodes (research papers) and 191 clusters (unique authors/entities). The task was to group different manifestations of the same entity using side information computed from attributes like paper titles and author names.

The empirical results were striking. A naive approach without side information would have required roughly $n \times k \approx 220,000$ queries to achieve perfect results. In contrast, the proposed greedy strategy achieved 80% precision and nearly 90% recall with only 1,136 queries. Furthermore, the algorithm demonstrated high robustness, performing nearly as well when using approximate or perturbed distributions as it did with exact ones—a crucial feature for real-world scenarios where the true noise model is unknown.

Limitations and Future Directions

While this paper establishes a strong foundation for clustering with side information, the authors note a few areas for future exploration:

  • The Sparse Regime: The current theoretical bounds are not yet tight for the "sparse" regime of the Stochastic Block Model, where similarities are very rare. The authors conjecture a sharper threshold but leave the formal proof for future work.
  • Oracle Reliability: The current model assumes the oracle is infallible. Although the authors suggest majority voting as a heuristic for noisy oracles, a more integrated theoretical treatment of erroneous oracle answers would be a valuable extension.
  • Closing the Log Gap: There remains a small gap of $O(\log n)$ between the established lower and upper bounds, presenting an open challenge for future theoretical research.

Summary updated

Abstract

Suppose, we are given a set of $n$ elements to be clustered into $k$ (unknown) clusters, and an oracle/expert labeler that can interactively answer pair-wise queries of the form, ``do two elements $u$ and $v$ belong to the same cluster?''. The goal is to recover the optimum clustering by asking the minimum number of queries. In this paper, we provide a rigorous theoretical study of this basic problem of query complexity of interactive clustering, and give strong information theoretic lower bounds, as well as nearly matching upper bounds. Most clustering problems come with a similarity matrix, which is used by an automated process to cluster similar points together. To improve accuracy of clustering, a fruitful approach in recent years has been to ask a domain expert or crowd to obtain labeled data interactively. Many heuristics have been proposed, and all of these use a similarity function to come up with a querying strategy. Even so, there is a lack systematic theoretical study. Our main contribution in this paper is to show the dramatic power of side information aka similarity matrix on reducing the query complexity of clustering. A similarity matrix represents noisy pair-wise relationships such as one computed by some function on attributes of the elements. A natural noisy model is where similarity values are drawn independently from some arbitrary probability distribution $f_+$ when the underlying pair of elements belong to the same cluster, and from some $f_-$ otherwise. We show that given such a similarity matrix, the query complexity reduces drastically from $\Theta(nk)$ (no similarity matrix) to $O(\frac{k^2\log{n}}{\cH^2(f_+\|f_-)})$ where $\cH^2$ denotes the squared Hellinger divergence. Moreover, this is also information-theoretic optimal within an $O(\log{n})$ factor. Our algorithms are all efficient, and parameter free, i.e., they work without any knowledge of $k, f_+$ and $f_-$, and only depend logarithmically with $n$.
BibTeX
@inproceedings{mazumdar2017query,
  author = {Arya Mazumdar and Barna Saha},
  title = {{Query Complexity of Clustering with Side Information}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=SJZ3-vWOZS},
}
Figure