# Query Complexity of Clustering with Side Information

arXiv: https://arxiv.org/abs/1706.07719 · HTML: https://mlsanity.com/paper/1706.07719/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jun 2017.

## Built on by (most cited first, 20 of 20)

- [Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries](https://mlsanity.com/paper/2102.00504/) (2021)
- [Matrix Completion with Hierarchical Graph Side Information](https://mlsanity.com/paper/2201.01728/) (2022)
- [Correlation Clustering with Active Learning of Pairwise Similarities](https://mlsanity.com/paper/2302.10295/) (2023)
- [Learning to Generate Fair Clusters from Demonstrations](https://mlsanity.com/paper/2102.03977/) (2021)
- [How to Design Robust Algorithms using Noisy Comparison Oracle](https://mlsanity.com/paper/2105.05782/) (2021)
- [Random Subgraph Detection Using Queries](https://mlsanity.com/paper/2110.00744/) (2021)
- [Transfer Learning for Latent Variable Network Models](https://mlsanity.com/paper/2406.03437/) (2024)
- [Clustering with Non-adaptive Subset Queries](https://mlsanity.com/paper/2409.10908/) (2024)
- [On Margin-Based Cluster Recovery with Oracle Queries](https://mlsanity.com/paper/2106.04913/) (2021)
- [Learning to Cluster via Same-Cluster Queries](https://mlsanity.com/paper/2108.07383/) (2021)
- [On the Fundamental Limits of Matrix Completion: Leveraging Hierarchical Similarity Graphs](https://mlsanity.com/paper/2109.05408/) (2021)
- [Learning Partitions with Optimal Query and Round Complexities](https://mlsanity.com/paper/2505.05009/) (2025)
- [Active clustering for labeling training data](https://mlsanity.com/paper/2110.14521/) (2021)
- [DMS: Differentiable Mean Shift for Dataset Agnostic Task Specific Clustering Using Side Information](https://mlsanity.com/paper/2305.18492/) (2023)
- [Information-Theoretic Active Correlation Clustering](https://mlsanity.com/paper/2402.03587/) (2024)
- [Fuzzy Clustering with Similarity Queries](https://mlsanity.com/paper/2106.02212/) (2021)
- [How to Query An Oracle? Efficient Strategies to Label Data](https://mlsanity.com/paper/2110.02341/) (2021)
- [Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs](https://mlsanity.com/paper/2506.08405/) (2025)
- [Metric k-clustering using only Weak Comparison Oracles](https://mlsanity.com/paper/2601.19333/) (2026)
- [Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds](https://mlsanity.com/paper/2608.02176/) (2026)

## Abstract (arXiv)

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(frack2logncH2(f_+|f_-)) where cH2 denotes the squared Hellinger divergence. Moreover, this is also information-theoretic optimal within an O(logn) 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 em stochastic block model, significantly generalizes them, and opens up many venues for interesting future research.