# Clustering with Same-Cluster Queries

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jun 2016.

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

- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Improved Learning-augmented Algorithms for k-means and k-medians Clustering](https://mlsanity.com/paper/2210.17028/) (2022)
- [Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries](https://mlsanity.com/paper/2102.00504/) (2021)
- [Bounded Memory Active Learning through Enriched Queries](https://mlsanity.com/paper/2102.05047/) (2021)
- [Clustering with Queries under Semi-Random Noise](https://mlsanity.com/paper/2206.04583/) (2022)
- [Active Learning of Driving Scenario Trajectories](https://mlsanity.com/paper/2108.03217/) (2021)
- [Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle](https://mlsanity.com/paper/2106.10374/) (2021)
- [Collaborative Causal Discovery with Atomic Interventions](https://mlsanity.com/paper/2106.03028/) (2021)
- [Matrix Completion with Hierarchical Graph Side Information](https://mlsanity.com/paper/2201.01728/) (2022)
- [Optimal Clustering with Noisy Queries via Multi-Armed Bandit](https://mlsanity.com/paper/2207.05376/) (2022)
- [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)
- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)
- [Personalized Clustering via Targeted Representation Learning](https://mlsanity.com/paper/2412.13690/) (2024)
- [Active Learning Polynomial Threshold Functions](https://mlsanity.com/paper/2201.09433/) (2022)
- [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)
- [Accelerating data-driven algorithm selection for combinatorial partitioning problems](https://mlsanity.com/paper/2402.14332/) (2024)
- [Learning Partitions with Optimal Query and Round Complexities](https://mlsanity.com/paper/2505.05009/) (2025)
- [Fuzzy Clustering with Similarity Queries](https://mlsanity.com/paper/2106.02212/) (2021)
- [Implications of Distance over Redistricting Maps: Central and Outlier Maps](https://mlsanity.com/paper/2203.00872/) (2022)
- [Oracle-guided Contrastive Clustering](https://mlsanity.com/paper/2211.00409/) (2022)
- [Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle](https://mlsanity.com/paper/2305.13402/) (2023)
- [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)
- [Generalized Category Discovery under Domain Shifts: From Vision to Vision-Language Models](https://mlsanity.com/paper/2605.00906/) (2026)
- [Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds](https://mlsanity.com/paper/2608.02176/) (2026)

## Abstract (arXiv)

We propose a framework for Semi-Supervised Active Clustering framework (SSAC), where the learner is allowed to interact with a domain expert, asking whether two given instances belong to the same cluster or not. We study the query and computational complexity of clustering in this framework. We consider a setting where the expert conforms to a center-based clustering with a notion of margin. We show that there is a trade off between computational complexity and query complexity; We prove that for the case of k-means clustering (i.e., when the expert conforms to a solution of k-means), having access to relatively few such queries allows efficient solutions to otherwise NP hard problems. In particular, we provide a probabilistic polynomial-time (BPP) algorithm for clustering in this setting that asks Obig(k2log k + klog n) same-cluster queries and runs with time complexity Obig(knlog n) (where k is the number of clusters and n is the number of instances). The algorithm succeeds with high probability for data satisfying margin conditions under which, without queries, we show that the problem is NP hard. We also prove a lower bound on the number of queries needed to have a computationally efficient clustering algorithm in this setting.