# Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 53 references that are in the map.
- First posted on arXiv 22 May 2023.

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

- [Graph Learning: A Survey](https://mlsanity.com/paper/2105.00696/) (2021)
- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1606.02404/) (2016)
- [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)
- [Approximate Correlation Clustering Using Same-Cluster Queries](https://mlsanity.com/paper/1712.06865/) (2017)
- [On Learning Graphs with Edge-Detecting Queries](https://mlsanity.com/paper/1803.10639/) (2018)
- [Clustering with Queries under Semi-Random Noise](https://mlsanity.com/paper/2206.04583/) (2022)
- [Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle](https://mlsanity.com/paper/2106.10374/) (2021)
- [Tight query complexity bounds for learning graph partitions](https://mlsanity.com/paper/2112.07897/) (2021)
- [Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut](https://mlsanity.com/paper/1305.1681/) (2013)
- [On Margin-Based Cluster Recovery with Oracle Queries](https://mlsanity.com/paper/2106.04913/) (2021)
- [Binary Error-Correcting Codes with Minimal Noiseless Feedback](https://mlsanity.com/paper/2212.05673/) (2022)
- [R'enyi-Ulam Games and Online Computation with Imperfect Advice](https://mlsanity.com/paper/2301.01631/) (2023)
- [The Optimal Error Resilience of Interactive Communication Over Binary Channels](https://mlsanity.com/paper/2110.15395/) (2021)

## Abstract (arXiv)

This paper initiates the study of active learning for exact recovery of partitions exclusively through access to a same-cluster oracle in the presence of bounded adversarial error. We first highlight a novel connection between learning partitions and correlation clustering. Then we use this connection to build a R'enyi-Ulam style analytical framework for this problem, and prove upper and lower bounds on its worst-case query complexity. Further, we bound the expected performance of a relevant randomized algorithm. Finally, we study the relationship between adaptivity and query complexity for this problem and related variants.