Research map / Learning theory and algorithms / Clustering
Query-Efficient Correlation Clustering with Noisy Oracle
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies correlation clustering with unknown, real-valued similarities accessed through a noisy bandit oracle, and gives two pure-exploration algorithms (KC-FC for fixed confidence, KC-FB for fixed budget) that combine threshold bandits or successive-reject sampling with KwikCluster to obtain 5-approximate clusterings.
Problem
Correlation clustering when pairwise similarities in [0,1] are unknown and only noisy samples can be queried, so the goal is to get a good clustering with few queries. Prior query-based methods assume binary similarities or a strong oracle.
Approach
Frame query-efficient correlation clustering as pure exploration in combinatorial bandits with an NP-hard offline problem; use threshold-bandit sampling (FC) or successive-reject budget allocation (FB) to estimate which pairs exceed 0.5, then run KwikCluster on the estimates, retaining a 5-approximation up to additive error.
Key results
- KC-FC returns a (5, epsilon)-approximate clustering with probability at least 1-delta, with sample complexity depending on instance gaps and decreasing as the minimum gap grows; it uses far fewer samples than Uniform-FC, which is prohibitive even on small graphs.
- KC-FB's error probability decays exponentially in the budget T, and it yields lower clustering cost than Uniform-FB for all tested instances and most budgets (e.g., Email 218k vs 221k, Wiki-Vote 10,222k vs 10,428k at T=n^2.2).
- KC-FC's clustering quality is comparable to KwikCluster run on the true similarity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive sampling with KC-FB instead of uniform sampling | Correlation clustering · Email | cost of clustering: 221k$\pm$0.5k -> 218k$\pm$1.1k | Helped |
| Use adaptive sampling with KC-FB instead of uniform sampling | Correlation clustering · ego-Facebook | cost of clustering: 3,780k$\pm$29.6k -> 3,716k$\pm$36.5k | Helped |
| Use adaptive sampling with KC-FB instead of uniform sampling | Correlation clustering · Wiki-Vote | cost of clustering: 10,428k$\pm$32.0k -> 10,222k$\pm$45.5k | Helped |
| Use KC-FC rather than Uniform-FC | Fixed-confidence correlation clustering · Real-world graph instances with n<1,000 | sample complexity | Helped |
| Increase the lower bound on the minimum gap | KC-FC · Real-world graph instances with n<1,000 | sample complexity | Helped |
| Use KC-FC rather than KwikCluster with access to true similarity | Fixed-confidence correlation clustering · Real-world graph instances with n<1,000 | cost of clustering | No clear effect |
| Use KC-FB rather than Uniform-FB | Fixed-budget correlation clustering · Small instances (n<1,000), across the tested budgets | cost of clustering | Helped |
| Use KC-FB rather than KwikCluster with access to true similarity | Fixed-budget correlation clustering · Large instances (n≥1,000) | cost of clustering: 209k$\pm$0.5k -> 218k$\pm$1.1k; 3,373k$\pm$59.8k -> 3,716k$\pm$36.5k; 9,749k$\pm$34.7k -> 10,222k$\pm$45.5k | Hurt |
Limitations
- Information-theoretic lower bounds for the NP-hard PE-CMAB setting are not derived; the n^2/max(Delta_min, eps'/2)^2 term's necessity is unproven.
- Experiments are limited to graphs with n<1000 for most runs and Uniform-FC is not actually run due to its sample complexity.
- Only Bernoulli or sub-Gaussian noise with a homoscedastic setting is analyzed.
Experimental setup
Datasets: Lesmis Adjnoun Football Jazz Email ego-Facebook Wiki-Vote
Benchmarks: Lesmis Adjnoun Football Jazz Email ego-Facebook Wiki-Vote
Metrics: sample complexity (number of queries) correlation clustering cost
Baselines: Uniform-FC Uniform-FB KwikCluster with true similarity
Builds on: KwikCluster threshold bandits PE-CMAB Combinatorial Successive Accept Reject
Closest papers by meaning
- Optimal Clustering with Noisy Queries via Multi-Armed Bandit (ICML 2022 · similarity 0.91)
- Clustering with Noisy Queries (NeurIPS 2017 · similarity 0.91)
- Correlation Clustering with Adaptive Similarity Queries (NeurIPS 2019 · similarity 0.90)
- Clustering Items through Bandit Feedback: Finding the Right Feature out of Many (ICML 2025 · similarity 0.87)
- Clustering with Non-adaptive Subset Queries (NeurIPS 2024 · similarity 0.87)
- Optimal Algorithms for Learning Partitions with Faulty Oracles (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.