Research map / Learning theory and algorithms / Clustering
Same-Cluster Querying for Overlapping Clusters
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use triangle counts to infer direct inner products from noisy quantized pair responses | Uniform-ensemble overlapping clustering · Noisy quantized responses | query complexity for exact similarity-matrix recovery: The paper states sufficient and necessary query counts are \Theta(n\log n) when k=O(\log n) and \Delta\ll k. | Helped |
| Do not require the noise parameter to be known; group triangle counts instead | Uniform-ensemble noisy quantized recovery · Unknown noise parameter | query complexity: The query complexity grows by a multiplicative constant factor only. | Mixed |
| Use direct responses rather than quantized responses | Overlapping-cluster recovery · k=O(log n), Δ≪k | query complexity: Direct responses: O(nk); Quantized responses: O(n·polylog n). | Helped |
| Increase overlap parameter Δ in the MovieLens quantized experiment | Worst-case quantized responses · MovieLens selected categories, perfect clustering | queries: 1.2\times 10^{6} for Δ=2; 1.5\times 10^{6} for Δ=3. | Mixed |
| Increase the number of queries beyond the early partial-recovery regime | Worst-case quantized responses · MovieLens, at most 2 categories | Gram-matrix error: Mean error almost reaches zero around 3×10^5 queries. | Helped |
| Use quantized noisy queries as noise q increases | Uniform-ensemble synthetic recovery · Synthetic data, n=2000, k=7, Δ=2 | query complexity | Mixed |
| Use an insufficient sample size for the noisy regime | Uniform-ensemble noisy quantized recovery · Synthetic data, n=1000, k=8, Δ=2, |S|=400 | incorrect inferences | Hurt |
| Use a sampled full-rank Gram matrix and query remaining items against a basis | FindSimilarity · MovieLens unquantized responses | query complexity as a share of all possible queries: 232126 ... is only 4.34% of the total number of possible queries. | Helped |
Closest papers by meaning
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.88)
- Clustering with Non-adaptive Subset Queries (NeurIPS 2024 · similarity 0.88)
- Competitively Consistent Clustering (ICML 2025 · similarity 0.86)
- Optimal Algorithms for Learning Partitions with Faulty Oracles (NeurIPS 2024 · similarity 0.85)
- Relative Error Fair Clustering in the Weak-Strong Oracle Model (ICML 2025 · similarity 0.85)
- Query-Efficient Correlation Clustering with Noisy Oracle (NeurIPS 2024 · similarity 0.85)
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.