Research map / Learning theory and algorithms / Clustering
Correlation Clustering with Adaptive Similarity Queries
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Limit pivot queries using a query rate function instead of querying every pivot neighbor | KwikCluster-style correlation clustering · Correlation clustering, general labeling | expected clustering error: 3OPT + O(n^3/Q) | Mixed |
| Set the query rate to f(n)=n, querying all pivot neighbors (ablation) | ACCESS · Correlation clustering | expected clustering error: 3OPT | Helped |
| Add early stopping after sampling the residual graph | ACCESS · Correlation clustering, sparse residual graphs | expected queries: O(n^2 lg(n) / h(n)) | Helped |
| Increase the query rate | ACCESS · Cora | average clustering cost | Helped |
| Use ACCESS rather than KwikCluster at a comparable clustering cost | Cora · Cora | number of queries: an order of magnitude fewer queries | Helped |
| Increase the query budget for an OPT = 0 instance | ACCESS · OPT = 0 experiments | clustering cost | Helped |
| Use AGGRESS early stopping instead of running ACCESS without the stopping test | Correlation clustering with many positive pairs · OPT = 0, sufficiently many similar pairs | expected queries: square root of the queries made by ACCESS | Helped |
| Use a random pair sample and empirical risk minimization | Correlation clustering · General labeling | clustering error: OPT + O(n^2ε) | Helped |
| Run independent ACCESS executions and aggregate node tags by majority | Strongly (1−ε)-knit clusters · Cluster recovery | exact recovery: K = 48 ln(n/p) | Helped |
| Use ACCESS's native single-run recovery without amplification | Strongly (1−ε)-knit clusters · Cluster recovery | symmetric-difference error: 3ε|C| + min{2n/f(n), (1−f(n)/n)|C|} + |C|e^{−|C|f(n)/5n} | Mixed |
Closest papers by meaning
- Query-Efficient Correlation Clustering with Noisy Oracle (NeurIPS 2024 · similarity 0.90)
- Clustering with Same-Cluster Queries (NeurIPS 2016 · similarity 0.90)
- Learning-Augmented Streaming Algorithms for Correlation Clustering (NeurIPS 2025 · similarity 0.87)
- Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering (NeurIPS 2025 · similarity 0.86)
- A3S: A General Active Clustering Method with Pairwise Constraints (ICML 2024 · similarity 0.86)
- Towards Better-than-2 Approximation for Constrained Correlation Clustering (ICML 2025 · similarity 0.86)
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.