Research map / Learning theory and algorithms / Clustering
Clustering with Non-adaptive Subset Queries
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first non-adaptive algorithms for exact k-clustering using subset-count queries, achieving near-linear query complexity (O(n log log n) for constant k, O(n log^2 n log k) in general) and matching bounded-size query lower bounds up to log factors.
Problem
Exactly recovering an unknown k-clustering of n points using non-adaptive subset queries that return the number of clusters intersecting the queried subset, where pairwise non-adaptive queries require Omega(n^2) queries.
Approach
Replace pairwise same-cluster queries with subset queries counting intersected clusters; random subsets of geometrically varying sizes let one recover clusters via connectivity of random graphs (constant k), and OR-query group-testing support recovery (general k), yielding non-adaptive near-linear algorithms.
Key results
- Non-adaptive algorithm with O(n log log n · k log k) subset queries for constant k, with success probability at least 1-δ.
- Non-adaptive algorithm with O(n log^2 n log k) subset queries for arbitrary k; O(n log k) for roughly balanced clusters when k = O(n/log^3 n).
- Bounded query size s: near-optimal Õ(n^2/s^2) queries for constant k, matching the Ω(n^2/s^2) lower bound up to log factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace non-adaptive pair-wise queries with unbounded-size subset queries | Clustering recovery for arbitrary k · Arbitrary k-clustering | queries: Ω(n2) -> O(n log2 n log k) | Helped |
| Use the constant-k non-adaptive algorithm | Clustering recovery · Constant-k clustering | queries: O(n log2 n log k) -> O(n log log n) | Helped |
| Bound subset-query size by O(√n) | Non-adaptive clustering recovery · Constant-k clustering | queries: O(n log log n) -> O(n log n log log n) | Mixed |
| Assume clusters are roughly balanced | Non-adaptive clustering recovery · Roughly balanced k-clustering, k ≤ O(n / log3 n) | queries: O(n log2 n log k) -> O(n log k) | Helped |
| Allow two rounds of adaptivity | Clustering recovery for arbitrary k · Arbitrary k-clustering | queries: O(n log2 n log k) -> O(n log k) | Helped |
| Allow two rounds of adaptivity and assume roughly balanced clusters | Clustering recovery · Roughly balanced k-clustering | queries: O(n log k) -> O(n log log k) | Helped |
| Restrict every subset query to size at most s | Non-adaptive 3-clustering recovery · Non-adaptive 3-clustering, subsets of size at most s | queries: Ω(n2) -> Ω(n2/s2) | Hurt |
| Use unbounded subset queries instead of pair-wise queries | Non-adaptive clustering recovery · Arbitrary k-clustering | queries: Ω(n2) -> O(n log2 n log k) | Helped |
Surprising findings
- Non-adaptive pair-wise query algorithms need Omega(n^2) queries even for k=3, while subset queries of unbounded size allow near-linear non-adaptive algorithms.
Limitations
- Algorithms are randomized and succeed with constant probability (boostable), not deterministic for the main non-adaptive results.
- Constant-k algorithm dependence on k is O(k log k) and the general-k algorithm's dependence on k is weaker than adaptive O(nk) in some regimes.
- Balanced-cluster results require cluster sizes within a constant factor, a restrictive assumption.
Experimental setup
Metrics: query complexity success probability
Baselines: trivial all-pairs non-adaptive querying adaptive pair-wise query algorithms (Theta(nk))
Builds on: Mazumdar and Saha clustering with pair-wise queries group testing coin weighing Erdős-Rényi connectivity
Closest papers by meaning
- Clustering with Noisy Queries (NeurIPS 2017 · similarity 0.89)
- Optimal Clustering with Noisy Queries via Multi-Armed Bandit (ICML 2022 · similarity 0.89)
- Same-Cluster Querying for Overlapping Clusters (NeurIPS 2019 · similarity 0.88)
- Query-Efficient Correlation Clustering with Noisy Oracle (NeurIPS 2024 · similarity 0.87)
- Competitively Consistent Clustering (ICML 2025 · similarity 0.86)
- Improved Fixed-Parameter Bounds for Min-Sum-Radii and Diameters k-Clustering and Their Fair Variants (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.