# Clustering with Non-adaptive Subset Queries

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 48 references that are in the map.
- First posted on arXiv 17 Sep 2024.

## Builds on (most cited first, 21 of 21)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1606.02404/) (2016)
- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Query Complexity of Clustering with Side Information](https://mlsanity.com/paper/1706.07719/) (2017)
- [Semi-supervised clustering methods](https://mlsanity.com/paper/1307.0252/) (2013)
- [Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost](https://mlsanity.com/paper/1908.04976/) (2019)
- [Exact Recovery of Mangled Clusters with Same-Cluster Queries](https://mlsanity.com/paper/2006.04675/) (2020)
- [Same-Cluster Querying for Overlapping Clusters](https://mlsanity.com/paper/1910.12490/) (2019)
- [A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution](https://mlsanity.com/paper/1702.01208/) (2017)
- [Clustering with Queries under Semi-Random Noise](https://mlsanity.com/paper/2206.04583/) (2022)
- [Semisupervised Clustering by Queries and Locally Encodable Source Coding](https://mlsanity.com/paper/1904.00507/) (2019)
- [Recovering Unbalanced Communities in the Stochastic Block Model With Application to Clustering with a Faulty Oracle](https://mlsanity.com/paper/2202.08522/) (2022)
- [Cut query algorithms with star contraction](https://mlsanity.com/paper/2201.05674/) (2022)
- [Computing exact minimum cuts without knowing the graph](https://mlsanity.com/paper/1711.03165/) (2017)
- [Edge Estimation with Independent Set Oracles](https://mlsanity.com/paper/1711.07567/) (2017)
- [Graph Connectivity and Single Element Recovery via Linear and OR Queries](https://mlsanity.com/paper/2007.06098/) (2020)
- [Nearly optimal edge estimation with independent set queries](https://mlsanity.com/paper/1907.04381/) (2019)
- [Quantum algorithms for graph problems with cut queries](https://mlsanity.com/paper/2007.08285/) (2020)
- [Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms](https://mlsanity.com/paper/1911.01651/) (2019)
- [Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries](https://mlsanity.com/paper/2207.02817/) (2022)

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

- [Learning Partitions with Optimal Query and Round Complexities](https://mlsanity.com/paper/2505.05009/) (2025)
- [Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs](https://mlsanity.com/paper/2506.08405/) (2025)
- [Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds](https://mlsanity.com/paper/2608.02176/) (2026)

## Abstract (arXiv)

Recovering the underlying k-clustering of a set U of n points by asking pair-wise same-cluster queries has garnered significant interest in the past few years. Given a query S subset U, |S|=2, the oracle returns "yes" if the points are in the same cluster and "no" otherwise. For adaptive algorithms, the query complexity is known to be Theta(nk), while non-adaptive algorithms are extremely limited: even for k=3, such algorithms require Omega(n2) queries, matching the trivial upper bound. However, non-adaptivity is highly desirable since it allows queries to be asked in parallel. To break the quadratic barrier for non-adaptive queries, we study a natural generalization of this problem to subset queries for |S|>2, where the oracle returns the number of clusters intersecting S. Previous work obtained an O(n) query adaptive algorithm, but the realm of non-adaptive algorithms remained completely unknown. In this paper, we give the first non-adaptive algorithms for clustering with subset queries. Our main result is a non-adaptive algorithm making O(n log k · (log k + loglog n)2) queries, improving to O(n log log n) when k is constant. In addition to non-adaptivity, we make other practical considerations, such as enforcing a bound, s, on the query size. We show Omega(max(n2/s2,n)) queries are necessary and obtain algorithms making smashwidetildeO(n2k/s2) queries for any s ≤ √n and smashwidetildeO(n2/s) queries for any s ≤ n. Finally, we obtain improved upper bounds when the clusters are roughly balanced, and when the algorithm is allowed two rounds of adaptivity.