# Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 52 references that are in the map.
- First posted on arXiv 20 Nov 2021.

## Builds on (most cited first, 17 of 17)

- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Correlation Clustering in Constant Many Parallel Rounds](https://mlsanity.com/paper/2106.08448/) (2021)
- [Parallel Correlation Clustering on Big Graphs](https://mlsanity.com/paper/1507.05086/) (2015)
- [Differentially Private Correlation Clustering](https://mlsanity.com/paper/2102.08885/) (2021)
- [Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering](https://mlsanity.com/paper/1712.05825/) (2017)
- [A Message Passing Algorithm for the Minimum Cost Multicut Problem](https://mlsanity.com/paper/1612.05441/) (2016)
- [Correlation Clustering and Biclustering with Locally Bounded Errors](https://mlsanity.com/paper/1506.08189/) (2015)
- [Scalable Community Detection via Parallel Correlation Clustering](https://mlsanity.com/paper/2108.01731/) (2021)
- [Local Correlation Clustering with Asymmetric Classification Errors](https://mlsanity.com/paper/2108.05697/) (2021)
- [Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds](https://mlsanity.com/paper/1411.0547/) (2014)
- [Correlation Clustering with Asymmetric Classification Errors](https://mlsanity.com/paper/2108.05696/) (2021)
- [On the Relation of Strong Triadic Closure and Cluster Deletion](https://mlsanity.com/paper/1803.00807/) (2018)
- [Correlation Clustering Generalized](https://mlsanity.com/paper/1809.09493/) (2018)
- [Motif and Hypergraph Correlation Clustering](https://mlsanity.com/paper/1811.02089/) (2018)
- [A Parallel Projection Method for Metric Constrained Optimization](https://mlsanity.com/paper/1901.10084/) (2019)
- [Project and Forget: Solving Large-Scale Metric Constrained Problems](https://mlsanity.com/paper/2005.03853/) (2020)
- [A new correlation clustering method for cancer mutation analysis](https://mlsanity.com/paper/1601.06476/) (2016)

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

- [Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!](https://mlsanity.com/paper/2305.13560/) (2023)
- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [ClusterFuG: Clustering Fully connected Graphs by Multicut](https://mlsanity.com/paper/2301.12159/) (2023)
- [A 4-approximation algorithm for min max correlation clustering](https://mlsanity.com/paper/2310.09196/) (2023)
- [Partial Optimality in Cubic Correlation Clustering](https://mlsanity.com/paper/2302.04694/) (2023)
- [Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds](https://mlsanity.com/paper/2307.06723/) (2023)
- [Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling](https://mlsanity.com/paper/2306.04884/) (2023)
- [Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network](https://mlsanity.com/paper/2502.14536/) (2025)
- [Correlation Clustering of Organoid Images](https://mlsanity.com/paper/2403.13376/) (2024)
- [Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better](https://mlsanity.com/paper/2404.16131/) (2024)
- [Partial Optimality in Cubic Correlation Clustering for General Graphs](https://mlsanity.com/paper/2510.20431/) (2025)
- [Inductive Correlation Clustering with Graph Neural Networks](https://mlsanity.com/paper/2608.27153/) (2026)

## Abstract (arXiv)

Correlation clustering is a widely studied framework for clustering based on pairwise similarity and dissimilarity scores, but its best approximation algorithms rely on impractical linear programming relaxations. We present faster approximation algorithms that avoid these relaxations, for two well-studied special cases: cluster editing and cluster deletion. We accomplish this by drawing new connections to edge labeling problems related to the principle of strong triadic closure. This leads to faster and more practical linear programming algorithms, as well as extremely scalable combinatorial techniques, including the first combinatorial approximation algorithm for cluster deletion. In practice, our algorithms produce approximate solutions that nearly match the best algorithms in quality, while scaling to problems that are orders of magnitude larger.