{
 "id": "ep19b7xjbx",
 "slug": "correlation-clustering",
 "title": "Correlation clustering",
 "updated": "2026-10-15",
 "topic_path": [
  {
   "id": "physical",
   "label": "Physical world and mathematics",
   "api_url": "https://www.edgepedia.org/api/v1/topics/physical"
  },
  {
   "id": "physical.math",
   "label": "Mathematics and statistics",
   "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math"
  },
  {
   "id": "physical.math.discrete",
   "label": "Logic and discrete mathematics",
   "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.discrete"
  }
 ],
 "geo": [
  {
   "id": "geo.nongeo.t1946.physical.math.discrete",
   "label": "Non-geographic · 1946 to 2000: Logic and discrete mathematics",
   "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.discrete",
   "path": [
    {
     "id": "geo.nongeo",
     "label": "Non-geographic",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo"
    },
    {
     "id": "geo.nongeo.t1946",
     "label": "Non-geographic · 1946 to 2000",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946"
    },
    {
     "id": "geo.nongeo.t1946.physical",
     "label": "Physical world and mathematics",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical"
    },
    {
     "id": "geo.nongeo.t1946.physical.math",
     "label": "Mathematics and statistics",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math"
    },
    {
     "id": "geo.nongeo.t1946.physical.math.discrete",
     "label": "Logic and discrete mathematics",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.discrete"
    }
   ]
  }
 ],
 "excerpt": "Correlation clustering is a graph clustering method that partitions vertices using pairwise similarity labels, introduced by Bansal, Blum, and Chawla in 2004 and used in machine learning.",
 "snippet": "Correlation clustering is a graph clustering method that partitions vertices using pairwise similarity labels, introduced by Bansal, Blum, and Chawla in 2004 and used in machine learning.",
 "node": "physical.math.discrete",
 "markdown": "# Correlation clustering\n\nCorrelation clustering is a graph clustering method that partitions the vertices of a graph whose edges carry pairwise similarity labels, seeking a clustering that agrees with those labels as much as possible. Each edge is labeled \"+\" (similar) or \"−\" (dissimilar), and the output is a partition of the vertices into clusters.<sup>[1](https://pages.cs.wisc.edu/~shuchi/papers/corrclusteringFOCS.pdf)</sup> The method is used in machine learning and algorithms for tasks including document clustering, image segmentation, link prediction, and community detection.<sup>[2](https://proceedings.neurips.cc/paper_files/paper/2023/file/149ad6e32c08b73a3ecc3d11977fcc47-Paper-Conference.pdf)</sup>\n\n| Key fact | Detail |\n|---|---|\n| Input | A graph (typically complete) with each edge labeled + or −, or weighted analogs<sup>[1](https://pages.cs.wisc.edu/~shuchi/papers/corrclusteringFOCS.pdf)</sup> |\n| Output | A partition of the vertices; the number of clusters is not a parameter and can range from 1 to n<sup>[1](https://pages.cs.wisc.edu/~shuchi/papers/corrclusteringFOCS.pdf)</sup> |\n| Objective | Minimize disagreements: positive edges between clusters plus negative edges within clusters<sup>[3](https://proceedings.neurips.cc/paper_files/paper/2025/file/e482e1c0581af762dc3e01c722f8038d-Paper-Conference.pdf)</sup> |\n| Complexity | NP-complete; APX-hard on complete graphs and on general graphs<sup>[1](https://pages.cs.wisc.edu/~shuchi/papers/corrclusteringFOCS.pdf)</sup><sup> • </sup><sup>[4](https://dl.acm.org/doi/10.1016/j.jcss.2004.10.012)</sup> |\n| Best guarantees | 1.437-approximation for minimization on complete graphs; \\( O(\\log n) \\) on general graphs via multicut<sup>[5](https://drops.dagstuhl.de/storage/00lipics/lipics-vol334-icalp2025/html/LIPIcs.ICALP.2025.40/LIPIcs.ICALP.2025.40.html)</sup><sup> • </sup><sup>[6](https://i11www.iti.kit.edu/_media/teaching/winter2006/graphclustering/ef-ccmda-03.pdf)</sup> |\n| Workhorse algorithm | Pivot: expected 3-approximation, linear time<sup>[7](https://raw.githubusercontent.com/mlresearch/v267/main/assets/behnezhad25a/behnezhad25a.pdf)</sup> |\n| Applications | Document clustering, entity disambiguation, image segmentation, community detection, link prediction<sup>[2](https://proceedings.neurips.cc/paper_files/paper/2023/file/149ad6e32c08b73a3ecc3d11977fcc47-Paper-Conference.pdf)</sup> |\n\n## How it works\n\nThe model takes a set of objects as vertices and a noisy binary classifier's labels on the edges: a positive edge means its endpoints are similar, a negative edge that they are dissimilar.<sup>[2](https://proceedings.neurips.cc/paper_files/paper/2023/file/149ad6e32c08b73a3ecc3d11977fcc47-Paper-Conference.pdf)</sup> Two objectives are standard. MaxAgree counts the + edges inside clusters plus the − edges across clusters; MinDisagree minimizes the complementary mistakes, the number of positive edges between different clusters plus the number of negative edges within the same cluster.<sup>[8](https://ar5iv.labs.arxiv.org/html/0704.2092)</sup><sup> • </sup><sup>[3](https://proceedings.neurips.cc/paper_files/paper/2025/file/e482e1c0581af762dc3e01c722f8038d-Paper-Conference.pdf)</sup>\n\nA defining feature is that the number of clusters is not a separate parameter, unlike k-median or min-sum clustering; the optimal number of clusters can be any value between 1 and n depending on the edge labels.<sup>[1](https://pages.cs.wisc.edu/~shuchi/papers/corrclusteringFOCS.pdf)</sup> In the weighted formulation motivated by document clustering, a probabilistic classifier gives the natural edge label log(Pr(same)/Pr(different)).<sup>[1](https://pages.cs.wisc.edu/~shuchi/papers/corrclusteringFOCS.pdf)</sup>\n\nThe problem is NP-complete,<sup>[1](https://pages.cs.wisc.edu/~shuchi/papers/corrclusteringFOCS.pdf)</sup> and Charikar, Guruswami, and Wirth proved it APX-hard, so a [PTAS](https://www.edgepedia.org/polynomial-time-approximation-scheme) (polynomial-time approximation scheme; near-optimal efficient algorithm) is unlikely even on complete graphs.<sup>[4](https://dl.acm.org/doi/10.1016/j.jcss.2004.10.012)</sup><sup> • </sup><sup>[2](https://proceedings.neurips.cc/paper_files/paper/2023/file/149ad6e32c08b73a3ecc3d11977fcc47-Paper-Conference.pdf)</sup> On general weighted graphs, Dotan Emanuel and Amos Fiat reduced minimization to the multicut problem, obtaining an \\( O(\\log n) \\) approximation and proving APX-hardness even for unweighted general graphs.<sup>[6](https://i11www.iti.kit.edu/_media/teaching/winter2006/graphclustering/ef-ccmda-03.pdf)</sup> The LP used there has an \\( \\Omega(\\log n) \\) integrality gap, and the problem is equivalent to minimum multicut, so no better-than-Θ(log n) approximation is expected on general graphs.<sup>[9](https://erikdemaine.org/papers/Clustering_APPROX2003/paper.pdf)</sup><sup> • </sup><sup>[3](https://proceedings.neurips.cc/paper_files/paper/2025/file/e482e1c0581af762dc3e01c722f8038d-Paper-Conference.pdf)</sup> For maximization, it is NP-hard to approximate weighted MaxAgree within \\( 80/79 - \\varepsilon \\) and unweighted MaxAgree within \\( 116/115 - \\varepsilon \\).<sup>[8](https://ar5iv.labs.arxiv.org/html/0704.2092)</sup>\n\n## How it is done\n\n**Pivot.** The classic combinatorial algorithm picks a random unclustered vertex as pivot, forms a cluster of the pivot plus all unclustered vertices joined to it by a positive edge, removes that cluster, and repeats.<sup>[7](https://raw.githubusercontent.com/mlresearch/v267/main/assets/behnezhad25a/behnezhad25a.pdf)</sup><sup> • </sup><sup>[10](https://cs-people.bu.edu/ncordner/papers/cocoa2023_paper.pdf)</sup> It attains an expected 3-approximation in time O(n + m₊), linear in the size of the positive graph, and the analysis of 3 is tight for it.<sup>[7](https://raw.githubusercontent.com/mlresearch/v267/main/assets/behnezhad25a/behnezhad25a.pdf)</sup><sup> • </sup><sup>[11](http://www.cs.yale.edu/homes/el327/papers/CCtuto_kdd14.pdf)</sup>\n\n**Local search.** LocalSearch improves a Pivot clustering by moving single nodes between clusters, each pass costing Θ(|V| + |E₊|); InnerLocalSearch instead runs local search to convergence inside each cluster only, is easily parallelizable, and experimentally lowers objective values while sharply reducing convergence time.<sup>[10](https://cs-people.bu.edu/ncordner/papers/cocoa2023_paper.pdf)</sup>\n\n**LP and SDP roundings.** For MinDisagree on complete graphs, a 4-approximation came first, followed by combinatorial and LP-based Pivot variants with factors 3 and 2.5, and then a 2.06-approximation from Chawla, Makarychev, Schramm, and Yaroslavtsev, nearly matching the integrality gap of 2.<sup>[12](https://ar5iv.labs.arxiv.org/html/2208.12636)</sup><sup> • </sup><sup>[13](https://doi.org/10.48550/arxiv.1412.0681)</sup><sup> • </sup><sup>[14](https://arxiv.org/html/2503.20883v5)</sup> For MaxAgree, a PTAS exists on complete unweighted graphs, and semidefinite programming gives a 0.766-approximation.<sup>[12](https://ar5iv.labs.arxiv.org/html/2208.12636)</sup> A drawback is size: linear programs for correlation clustering have at least a cubic number of constraints, which makes them intractable for graphs with millions of nodes.<sup>[10](https://cs-people.bu.edu/ncordner/papers/cocoa2023_paper.pdf)</sup>\n\n**Current frontier.** The best known approximation for minimizing disagreements on complete graphs is 1.437, against an explicit hardness of 24/23.<sup>[5](https://drops.dagstuhl.de/storage/00lipics/lipics-vol334-icalp2025/html/LIPIcs.ICALP.2025.40/LIPIcs.ICALP.2025.40.html)</sup>\n\n## Origin\n\nCorrelation clustering was introduced by Nikhil Bansal, Avrim Blum, and Shuchi Chawla, published in Machine Learning in 2004.<sup>[15](https://doi.org/10.1023/b:mach.0000033116.57574.95)</sup> Their formulation, motivated by document clustering with a learned pairwise similarity function, asks for a partition that correlates with that function as much as possible, and can be viewed as a kind of agnostic learning problem.<sup>[1](https://pages.cs.wisc.edu/~shuchi/papers/corrclusteringFOCS.pdf)</sup> The work was motivated in part by clustering problems at Whizbang Labs, such as clustering entity names.<sup>[1](https://pages.cs.wisc.edu/~shuchi/papers/corrclusteringFOCS.pdf)</sup> A constant-factor approximation for minimizing disagreements and a PTAS for maximizing agreements are known.<sup>[1](https://pages.cs.wisc.edu/~shuchi/papers/corrclusteringFOCS.pdf)</sup> The problem of clustering from qualitative similarity judgments, formalized as the graph problem Cluster Editing, appears in earlier work the method built on.<sup>[8](https://ar5iv.labs.arxiv.org/html/0704.2092)</sup>\n\n## Variants\n\nTwo standard settings are distinguished: correlation clustering on complete graphs, and correlation clustering with noisy partial information (arbitrary weights, missing edges), which are computationally quite different.<sup>[12](https://ar5iv.labs.arxiv.org/html/2208.12636)</sup> For the partial-information case with edge weights +1 or −1, an \\( O(\\log n) \\)-approximation based on LP rounding and region-growing applies.<sup>[9](https://erikdemaine.org/papers/Clustering_APPROX2003/paper.pdf)</sup> When the number of clusters is fixed at a constant k, a PTAS exists for both objectives.<sup>[16](https://theoryofcomputing.org/articles/v002a013/v002a013.pdf)</sup>\n\nScalable models are a major thread. A single-pass randomized semi-streaming algorithm achieves \\( 3 + O(1/k) \\) approximation using \\( O(k \\cdot n) \\) words of memory.<sup>[2](https://proceedings.neurips.cc/paper_files/paper/2023/file/149ad6e32c08b73a3ecc3d11977fcc47-Paper-Conference.pdf)</sup> An almost-3-[approximation algorithm](https://www.edgepedia.org/approximation-algorithm) runs in [MapReduce](https://www.edgepedia.org/mapreduce) and streaming models in a small number of rounds.<sup>[17](https://psycnet.apa.org/doi/10.1145/2623330.2623743)</sup> In the MPC model, a \\( 3 + \\varepsilon \\)-approximation is known in constant rounds and a 2.4-approximation in polylogarithmic rounds with Õ(|E|^1.5) sequential time.<sup>[18](https://arxiv.org/html/2404.05433)</sup> PRUNED PIVOT, by Dalirrooyfard, Makarychev, and Mitrović (2024), gives a (3+ε)-approximation while exploring only \\( O(1/\\varepsilon) \\) nodes per query, yielding the first fully dynamic algorithm whose expected update time does not depend on graph size.<sup>[19](https://doi.org/10.48550/arxiv.2402.15668)</sup> MODIFIEDPIVOT maintains a 2.99-approximate clustering with polylogarithmic update time, breaking the 3-approximation barrier; experimentally it makes on average less than 77% of the mistakes Pivot makes.<sup>[7](https://raw.githubusercontent.com/mlresearch/v267/main/assets/behnezhad25a/behnezhad25a.pdf)</sup>\n\n## Applications\n\nDocumented applications include image segmentation, link prediction, document clustering, and community detection,<sup>[2](https://proceedings.neurips.cc/paper_files/paper/2023/file/149ad6e32c08b73a3ecc3d11977fcc47-Paper-Conference.pdf)</sup> as well as disambiguation tasks, automated labeling,<sup>[7](https://raw.githubusercontent.com/mlresearch/v267/main/assets/behnezhad25a/behnezhad25a.pdf)</sup> clustering ensembles, duplicate detection, and community mining.<sup>[18](https://arxiv.org/html/2404.05433)</sup> The method is described as a basic primitive in the data miner's toolkit, with uses ranging from entity matching to social network analysis.<sup>[17](https://psycnet.apa.org/doi/10.1145/2623330.2623743)</sup>\n\n## Limitations and alternatives\n\nUnlike k-means or k-median, correlation clustering uses qualitative pairwise edge labels rather than distances in a metric space, and the number of clusters is not a parameter.<sup>[12](https://ar5iv.labs.arxiv.org/html/2208.12636)</sup> Noisy or inconsistent pairwise labels are the model's premise rather than an anomaly, so the objective itself absorbs label noise; the documented practical failure mode is that greedy heuristics that work very well can provably fail sometimes, and efficient provable algorithms for weighted or partial graphs remain an open challenge.<sup>[11](http://www.cs.yale.edu/homes/el327/papers/CCtuto_kdd14.pdf)</sup> Pivot itself is inherently sequential and needs \\( \\Omega(n) \\) memory to store the pivots found so far, which motivates the distributed, streaming, dynamic, and local versions above.<sup>[11](http://www.cs.yale.edu/homes/el327/papers/CCtuto_kdd14.pdf)</sup>\n\n## References\n\n1. [Correlation Clustering (Bansal, Blum, Chawla, FOCS 2002)](https://pages.cs.wisc.edu/~shuchi/papers/corrclusteringFOCS.pdf)\n2. [Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple! (NeurIPS 2023)](https://proceedings.neurips.cc/paper_files/paper/2023/file/149ad6e32c08b73a3ecc3d11977fcc47-Paper-Conference.pdf)\n3. [Learning-Augmented Streaming Algorithms for Correlation Clustering (NeurIPS 2025)](https://proceedings.neurips.cc/paper_files/paper/2025/file/e482e1c0581af762dc3e01c722f8038d-Paper-Conference.pdf)\n4. [Clustering with qualitative information (Demaine, Emanuel, Fiat, Immorlica, JCSS 2005)](https://dl.acm.org/doi/10.1016/j.jcss.2004.10.012)\n5. [Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering (ICALP 2025, LIPIcs)](https://drops.dagstuhl.de/storage/00lipics/lipics-vol334-icalp2025/html/LIPIcs.ICALP.2025.40/LIPIcs.ICALP.2025.40.html)\n6. [Correlation Clustering – Minimizing Disagreements on Arbitrary Weighted Graphs (Emanuel & Fiat, WAOA 2003)](https://i11www.iti.kit.edu/_media/teaching/winter2006/graphclustering/ef-ccmda-03.pdf)\n7. [Correlation Clustering Beyond the Pivot Algorithm (ICML/PMLR 2025)](https://raw.githubusercontent.com/mlresearch/v267/main/assets/behnezhad25a/behnezhad25a.pdf)\n8. [A Note on the Inapproximability of Correlation Clustering](https://ar5iv.labs.arxiv.org/html/0704.2092)\n9. [Correlation Clustering with Partial Information (Demaine, Emanuel, Fiat, Immorlica, APPROX 2003)](https://erikdemaine.org/papers/Clustering_APPROX2003/paper.pdf)\n10. [An Efficient Local Search Algorithm for Correlation Clustering (InnerLocalSearch, COCOA 2023)](https://cs-people.bu.edu/ncordner/papers/cocoa2023_paper.pdf)\n11. [Correlation Clustering: from Theory to Practice (KDD'14 tutorial)](http://www.cs.yale.edu/homes/el327/papers/CCtuto_kdd14.pdf)\n12. [Four Algorithms for Correlation Clustering: A Survey](https://ar5iv.labs.arxiv.org/html/2208.12636)\n13. [Chawla, Shuchi and colleagues (2014). Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.1412.0681)\n14. [Solving the Correlation Cluster LP in Sublinear Time (arXiv 2025)](https://arxiv.org/html/2503.20883v5)\n15. [Nikhil Bansal, Avrim Blum, Shuchi Chawla (2004). Correlation Clustering. Machine Learning.](https://doi.org/10.1023/b:mach.0000033116.57574.95)\n16. [Correlation Clustering with a Fixed Number of Clusters (Giotis & Guruswami, Theory of Computing)](https://theoryofcomputing.org/articles/v002a013/v002a013.pdf)\n17. [Correlation clustering in MapReduce (Chierichetti et al., KDD 2014)](https://psycnet.apa.org/doi/10.1145/2623330.2623743)\n18. [Combinatorial Correlation Clustering (arXiv 2024)](https://arxiv.org/html/2404.05433)\n19. [Dalirrooyfard, Mina, Makarychev, Konstantin, Mitrović, Slobodan (2024). Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.2402.15668)\n\n---\n*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics*\n\n*Initially written Sep 29, 2026 · Edited: Oct 15, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n",
 "same_as": [
  "https://pages.cs.wisc.edu/~shuchi/papers/corrclusteringFOCS.pdf"
 ],
 "url": "https://www.edgepedia.org/correlation-clustering",
 "markdown_url": "https://www.edgepedia.org/correlation-clustering.md",
 "license": {
  "name": "Edgepedia Community License 1.0",
  "url": "https://www.edgepedia.org/edgepedia/license",
  "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.",
  "spdx": "LicenseRef-Edgepedia-Community-1.0"
 },
 "credit": "\"Correlation clustering\", Edgepedia (EdgeChat), https://www.edgepedia.org/correlation-clustering. Edgepedia Community License 1.0.",
 "credit_md": "\"[Correlation clustering](https://www.edgepedia.org/correlation-clustering)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/correlation-clustering](https://www.edgepedia.org/correlation-clustering). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).",
 "credit_html": "\"<a href=\"https://www.edgepedia.org/correlation-clustering\">Correlation clustering</a>\", Edgepedia (EdgeChat), <a href=\"https://www.edgepedia.org/correlation-clustering\">https://www.edgepedia.org/correlation-clustering</a>. <a href=\"https://www.edgepedia.org/edgepedia/license\">Edgepedia Community License 1.0</a>.",
 "speakable": "Correlation clustering is a graph clustering method that partitions vertices using pairwise similarity labels, introduced by Bansal, Blum, and Chawla in 2004 and used in machine learning."
}