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 initiate a rigorous theoretical study of this basic problem of query complexity of interactive clustering, and provide 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. 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$. Along the way, our work also reveals intriguing connection to popular community detection models such as the stochastic block model, significantly generalizes them, and opens up many venues for interesting future research.
Introduction
Clustering is a fundamental task in machine learning, yet it remains notoriously difficult when the similarity functions used to compare objects are imperfect. This challenge is particularly evident in domains like Entity Resolution—identifying different records of the same real-world entity—where automated similarity metrics often fail to provide definitive answers. To address this, modern systems often incorporate an "oracle" (such as a human expert or crowdsourced workers) to answer pairwise queries: "Do item A and item B belong to the same cluster?"
While human-in-the-loop systems are common in practice, their theoretical limits have been under-explored. Without any prior information, perfectly clustering $n$ items into $k$ clusters requires $\Theta(nk)$ queries. However, practical heuristics leverage computer-generated similarity matrices to guide their queries, often requiring far fewer interactions. This paper provides a rigorous theoretical explanation for why and how much this "side information" helps, even when the noise distributions and the number of clusters are unknown.
The Power of Side Information
The authors frame the problem as a multi-hypothesis testing challenge. They assume a generative model where the similarity between two items is drawn from an unknown distribution $f_+$ if they are in the same cluster, and $f_-$ if they are in different clusters.
The core insight of this work is that the quality of side information is best measured by the squared Hellinger divergence, $\mathcal{H}^2(f_+ \| f_-)$. This metric quantifies the statistical distance between the "same-cluster" and "different-cluster" distributions. The larger this divergence, the more informative the similarity matrix is, and the fewer queries are required from the oracle.
Information-Theoretic Bounds
The paper establishes both lower and upper bounds for the query complexity, demonstrating an exponential reduction in the number of queries needed when side information is available.
Lower Bounds
Using a generalized version of Fano's inequality, the authors prove that any algorithm requires at least: $$\Omega\left(\min\left\{nk, \frac{k^2}{\mathcal{H}^2(f_+ \| f_-)}\right\}\right)$$ expected queries to successfully recover the clusters. This bound represents the fundamental information-theoretic limit of the problem.
Upper Bounds and Algorithms
The authors design two computationally efficient, parameter-free algorithms that do not require prior knowledge of $k$, $f_+$, or $f_-$:
- Monte Carlo Algorithm: Recovers all clusters accurately with high probability ($1 - o(1/n)$) using $O\left(\min\left\{nk, \frac{k^2 \log n}{\mathcal{H}^2(f_+ \| f_-)}\right\}\right)$ queries.
- Las Vegas Algorithm: Achieves exact recovery (zero error) with an expected query complexity of $O\left(n \log n + \min\left\{nk, \frac{k^2 \log n}{\mathcal{H}^2(f_+ \| f_-)}\right\}\right)$.
These algorithms use an Iterative-Update Technique. They begin by querying a few points to build initial clusters, then estimate the empirical distributions for intra-cluster and inter-cluster similarities. Using Sanov's theorem from large deviation theory, the algorithms dynamically set size thresholds for clusters, allowing them to learn the underlying noise parameters on the fly.
Generalizing the Stochastic Block Model
This framework significantly generalizes the well-known Stochastic Block Model (SBM) used in community detection. In standard SBMs, edge probabilities are simple Bernoulli trials. This paper allows the "edges" (side information) to be drawn from any arbitrary probability distribution, providing a more robust model for real-world data where similarity scores are often continuous or follow complex distributions.
Conclusion
This research demonstrates that side information can reduce the query complexity of clustering from scaling linearly with the dataset size ($n$) to scaling only logarithmically ($O(\log n)$). By identifying Hellinger divergence as the key metric for side information quality, the authors provide a bridge between information theory and practical interactive clustering.
Future work remains to close the $O(\log n)$ gap between the lower and upper bounds and to extend these parameter-free algorithms to handle cluster-specific noise distributions where the similarity noise might depend on the specific pair of clusters being compared.
Summary updated