# Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 26 references that are in the map.
- First posted on arXiv 18 Jun 2021.

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

- [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)
- [A simple SVD algorithm for finding hidden partitions](https://mlsanity.com/paper/1404.3918/) (2014)
- [A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution](https://mlsanity.com/paper/1702.01208/) (2017)
- [A Correlation Clustering Approach to Link Classification in Signed Networks -- Full Version --](https://mlsanity.com/paper/1301.4769/) (2013)
- [Predicting Signed Edges with O(n1+o(1) logn) Queries](https://mlsanity.com/paper/1609.00750/) (2016)

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

- [Clustering with Queries under Semi-Random Noise](https://mlsanity.com/paper/2206.04583/) (2022)
- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [Recovering Unbalanced Communities in the Stochastic Block Model With Application to Clustering with a Faulty Oracle](https://mlsanity.com/paper/2202.08522/) (2022)
- [Confident Clustering via PCA Compression Ratio and Its Application to Single-cell RNA-seq Analysis](https://mlsanity.com/paper/2205.09849/) (2022)
- [Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle](https://mlsanity.com/paper/2305.13402/) (2023)
- [Almost Asymptotically Optimal Active Clustering Through Pairwise Observations](https://mlsanity.com/paper/2602.05690/) (2026)

## Abstract (arXiv)

Motivated by applications in crowdsourced entity resolution in database, signed edge prediction in social networks and correlation clustering, Mazumdar and Saha [NIPS 2017] proposed an elegant theoretical model for studying clustering with a faulty oracle. In this model, given a set of n items which belong to k unknown groups (or clusters), our goal is to recover the clusters by asking pairwise queries to an oracle. This oracle can answer the query that ``do items u and v belong to the same cluster?''. However, the answer to each pairwise query errs with probability varepsilon, for some varepsilon∈(0,frac12). Mazumdar and Saha provided two algorithms under this model: one algorithm is query-optimal while time-inefficient (i.e., running in quasi-polynomial time), the other is time efficient (i.e., in polynomial time) while query-suboptimal. Larsen, Mitzenmacher and Tsourakakis [WWW 2020] then gave a new time-efficient algorithm for the special case of 2 clusters, which is query-optimal if the bias δ:=1-2varepsilon of the model is large. It was left as an open question whether one can obtain a query-optimal, time-efficient algorithm for the general case of k clusters and other regimes of δ. In this paper, we make progress on the above question and provide a time-efficient algorithm with nearly-optimal query complexity (up to a factor of O(log2 n)) for all constant k and any δ in the regime when information-theoretic recovery is possible. Our algorithm is built on a connection to the stochastic block model.