mlsanityData to 7 Oct 2026

Query-Efficient Correlation Clustering with Noisy Oracle

arXiv 2402.01400 ↗First posted 2 Feb 2024stat.ML cs.DS cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

We study a general clustering setting in which we have n elements to be clustered, and we aim to perform as few queries as possible to an oracle that returns a noisy sample of the weighted similarity between two elements. Our setting encompasses many application domains in which the similarity function is costly to compute and inherently noisy. We introduce two novel formulations of online learning problems rooted in the paradigm of Pure Exploration in Combinatorial Multi-Armed Bandits (PE-CMAB): fixed confidence and fixed budget settings. For both settings, we design algorithms that combine a sampling strategy with a classic approximation algorithm for correlation clustering and study their theoretical guarantees. Our results are the first examples of polynomial-time algorithms that work for the case of PE-CMAB in which the underlying offline optimization problem is NP-hard.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 41 of its 83 references that are in the map. First posted on arXiv 2 Feb 2024.

Builds on

41 of 83 references.

References · 41

  1. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
  2. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 280
  3. 2016Optimal Best Arm Identification with Fixed Confidencecited by 233
  4. 2013lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Banditscited by 148
  5. 2019Sequential Experimental Design for Transductive Linear Banditscited by 88
  6. 2014Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Armscited by 78
  7. 2016An optimal algorithm for the Thresholding Bandit Problemcited by 62
  8. 2019Pure Exploration with Multiple Correct Answerscited by 60
  9. 2020An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Banditscited by 45
  10. 2017Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applicationscited by 44
  11. 2017Clustering with Noisy Queriescited by 34
  12. 2017Good Arm Identification via Bandit Feedbackcited by 29
29 more
  1. 2014Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphscited by 27
  2. 2020Fair Correlation Clusteringcited by 27
  3. 2021Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedbackcited by 19
  4. 2015On the Optimal Sample Complexity for Best Arm Identificationcited by 17
  5. 2019Correlation Clustering with Same-Cluster Queries Bounded by Optimal Costcited by 16
  6. 2019PAC Identification of Many Good Arms in Stochastic Multi-Armed Banditscited by 15
  7. 2022Correlation Clustering with Sherali-Adamscited by 15
  8. 2015Parallel Correlation Clustering on Big Graphscited by 14
  9. 2016Pure Exploration of Multi-armed Bandit Under Matroid Constraintscited by 13
  10. 2021Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Boundscited by 12
  11. 2017Approximate Correlation Clustering Using Same-Cluster Queriescited by 11
  12. 2019Polynomial-time Algorithms for Multiple-arm Identification with Full-bandit Feedbackcited by 8
  13. 2022Clustering with Queries under Semi-Random Noisecited by 8
  14. 2022On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Banditscited by 8
  15. 2023Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!cited by 8
  16. 2019Correlation Clustering with Adaptive Similarity Queriescited by 7
  17. 2020Query-Efficient Correlation Clusteringcited by 7
  18. 2023Fast Combinatorial Algorithms for Min Max Correlation Clusteringcited by 7
  19. 2021Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oraclecited by 6
  20. 2023Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clusteringcited by 6
  21. 2013Local correlation clusteringcited by 5
  22. 2022Optimal Clustering with Noisy Queries via Multi-Armed Banditcited by 5
  23. 2023Correlation Clustering with Active Learning of Pairwise Similaritiescited by 5
  24. 2020Online Dense Subgraph Discovery via Blurred-Graph Feedbackcited by 4
  25. 2021Combinatorial Pure Exploration with Bottleneck Reward Functioncited by 4
  26. 2022Thompson Sampling for (Combinatorial) Pure Explorationcited by 4
  27. 2017Predicting Positive and Negative Links with Noisy Queries: Theory & Practicecited by 3
  28. 2018Combinatorial Pure Exploration with Continuous and Separable Reward Functions and Its Applications (Extended Version)cited by 3
  29. 2023Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Banditcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 2; 2026: 2.

7 papers.

  1. 2024Learning-augmented Maximum Independent Setcited by 11
  2. 2024Information-Theoretic Active Correlation Clusteringcited by 1
  3. 2025Learning-Augmented Streaming Algorithms for Correlation Clusteringcited by 1
  4. 2024Multilayer Correlation Clusteringcited by 0
  5. 2025Cold-Start Active Correlation Clusteringcited by 0
  6. 2026On the Sparsifiability of Correlation Clustering: Approximation Guarantees under Edge Samplingcited by 0
  7. 2026Inductive Correlation Clustering with Graph Neural Networkscited by 0