# Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Aug 2019.

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

- [Bounded Memory Active Learning through Enriched Queries](https://mlsanity.com/paper/2102.05047/) (2021)
- [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)
- [Optimal Clustering with Noisy Queries via Multi-Armed Bandit](https://mlsanity.com/paper/2207.05376/) (2022)
- [Correlation Clustering with Active Learning of Pairwise Similarities](https://mlsanity.com/paper/2302.10295/) (2023)
- [Active Learning Polynomial Threshold Functions](https://mlsanity.com/paper/2201.09433/) (2022)
- [Clustering with Non-adaptive Subset Queries](https://mlsanity.com/paper/2409.10908/) (2024)
- [On Margin-Based Cluster Recovery with Oracle Queries](https://mlsanity.com/paper/2106.04913/) (2021)
- [Learning to Cluster via Same-Cluster Queries](https://mlsanity.com/paper/2108.07383/) (2021)
- [Accelerating data-driven algorithm selection for combinatorial partitioning problems](https://mlsanity.com/paper/2402.14332/) (2024)
- [Learning Partitions with Optimal Query and Round Complexities](https://mlsanity.com/paper/2505.05009/) (2025)
- [Information-Theoretic Active Correlation Clustering](https://mlsanity.com/paper/2402.03587/) (2024)
- [Fuzzy Clustering with Similarity Queries](https://mlsanity.com/paper/2106.02212/) (2021)
- [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)
- [Almost Asymptotically Optimal Active Clustering Through Pairwise Observations](https://mlsanity.com/paper/2602.05690/) (2026)

## Abstract (arXiv)

Several clustering frameworks with interactive (semi-supervised) queries have been studied in the past. Recently, clustering with same-cluster queries has become popular. An algorithm in this setting has access to an oracle with full knowledge of an optimal clustering, and the algorithm can ask the oracle queries of the form, "Does the optimal clustering put vertices  u  and  v  in the same cluster?" Due to its simplicity, this querying model can easily be implemented in real crowd-sourcing platforms and has attracted a lot of recent work. In this paper, we study the popular correlation clustering problem (Bansal et al., 2002) under this framework. Given a complete graph G=(V,E) with positive and negative edge labels, correlation clustering objective aims to compute a graph clustering that minimizes the total number of disagreements, that is the negative intra-cluster edges and positive inter-cluster edges. Let  COPT  be the number of disagreements made by the optimal clustering. We present algorithms for correlation clustering whose error and query bounds are parameterized by COPT rather than by the number of clusters. Indeed, a good clustering must have small COPT. Specifically, we present an efficient algorithm that recovers an exact optimal clustering using at most 2COPT  queries and an efficient algorithm that outputs a 2-approximation using at most COPT  queries. In addition, we show under a plausible complexity assumption, there does not exist any polynomial time algorithm that has an approximation ratio better than 1+α for an absolute constant α >0 with o(COPT) queries. We extensively evaluate our methods on several synthetic and real-world datasets using real crowd-sourced oracles. Moreover, we compare our approach against several known correlation clustering algorithms.