# Clustering with Queries under Semi-Random Noise

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 53 references that are in the map.
- First posted on arXiv 9 Jun 2022.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1606.02404/) (2016)
- [A simple SVD algorithm for finding hidden partitions](https://mlsanity.com/paper/1404.3918/) (2014)
- [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)
- [Approximate Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1704.01862/) (2017)
- [Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle](https://mlsanity.com/paper/2106.10374/) (2021)
- [Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering](https://mlsanity.com/paper/1803.00926/) (2018)
- [Learning to Cluster via Same-Cluster Queries](https://mlsanity.com/paper/2108.07383/) (2021)

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

- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)
- [Clustering with Non-adaptive Subset Queries](https://mlsanity.com/paper/2409.10908/) (2024)
- [Learning Partitions with Optimal Query and Round Complexities](https://mlsanity.com/paper/2505.05009/) (2025)
- [Reweighting Improves Conditional Risk Bounds](https://mlsanity.com/paper/2501.02353/) (2025)
- [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)
- [Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds](https://mlsanity.com/paper/2608.02176/) (2026)

## Abstract (arXiv)

The seminal paper by Mazumdar and Saha citeMS17a introduced an extensive line of work on clustering with noisy queries. Yet, despite significant progress on the problem, the proposed methods depend crucially on knowing the exact probabilities of errors of the underlying fully-random oracle. In this work, we develop robust learning methods that tolerate general semi-random noise obtaining qualitatively the same guarantees as the best possible methods in the fully-random model. More specifically, given a set of n points with an unknown underlying partition, we are allowed to query pairs of points u,v to check if they are in the same cluster, but with probability p, the answer may be adversarially chosen. We show that information theoretically Oleft(fracnk log n (1-2p)2right) queries suffice to learn any cluster of sufficiently large size. Our main result is a computationally efficient algorithm that can identify large clusters with Oleft(fracnk log n (1-2p)2right) + polyleft(log n, k, frac11-2p right) queries, matching the guarantees of the best known algorithms in the fully-random model. As a corollary of our approach, we develop the first parameter-free algorithm for the fully-random model, answering an open question by citeMS17a.