mlsanityData to 7 Oct 2026

Fair Correlation Clustering

arXiv 2002.02274 ↗First posted 6 Feb 2020cs.DS cs.AI cs.LGcited by 27

Not on the map. Why?

Abstract (arXiv)

In this paper, we study correlation clustering under fairness constraints. Fair variants of k-median and k-center clustering have been studied recently, and approximation algorithms using a notion called fairlet decomposition have been proposed. We obtain approximation algorithms for fair correlation clustering under several important types of fairness constraints. Our results hinge on obtaining a fairlet decomposition for correlation clustering by introducing a novel combinatorial optimization problem. We define a fairlet decomposition with cost similar to the k-median cost and this allows us to obtain approximation algorithms for a wide range of fairness constraints. We complement our theoretical results with an in-depth analysis of our algorithms on real graphs where we show that fair solutions to correlation clustering can be obtained with limited increase in cost compared to the state-of-the-art (unfair) algorithms.

Key facts. Cited by 27 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 Feb 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 4; 2023: 5; 2024: 7; 2025: 2; 2026: 3.

27 papers.

Sort:

  1. 2021Fair Clustering Under a Bounded Costcited by 21
  2. 2021Through the Data Management Lens: Experimental Analysis and Evaluation of Fair Classificationcited by 13
  3. 2023Doubly Constrained Fair Clusteringcited by 9
  4. 2022Individual Preference Stability for Clusteringcited by 8
  5. 2023Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!cited by 8
  6. 2024A Scalable Algorithm for Individually Fair K-means Clusteringcited by 8
  7. 2021Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositionscited by 7
  8. 2024Query-Efficient Correlation Clustering with Noisy Oraclecited by 7
  9. 2022Improved Approximation for Fair Correlation Clusteringcited by 6
  10. 2022FAL-CUR: Fair Active Learning using Uncertainty and Representativeness on Fair Clusteringcited by 6
  11. 2021Efficient Algorithms For Fair Clustering with a New Fairness Notioncited by 5
  12. 2021Learning to Generate Fair Clusters from Demonstrationscited by 4
15 more
  1. 2022Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Costcited by 4
  2. 2021Modification-Fair Cluster Editingcited by 3
  3. 2023Spectral Normalized-Cut Graph Partitioning with Fairness Constraintscited by 3
  4. 2024Diversity-aware clustering: Computational Complexity and Approximation Algorithmscited by 3
  5. 2023Fair Clustering via Hierarchical Fair-Dirichlet Processcited by 1
  6. 2024Robust Fair Clustering with Group Membership Uncertainty Setscited by 1
  7. 2024Fair Clustering: Critique, Caveats, and Future Directionscited by 1
  8. 2025Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social networkcited by 1
  9. 2023Fair Correlation Clustering in Forestscited by 0
  10. 2024Multilayer Correlation Clusteringcited by 0
  11. 2024Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Timecited by 0
  12. 2025Online Correlation Clustering: Simultaneously Optimizing All ℓp-normscited by 0
  13. 2026A Generic Framework for Fair Consensus Clustering in Streamscited by 0
  14. 2026Why Colors Make Clustering Harder:Global Integrality Gaps, the Price of Fairness, and Color-Coupled Algorithms in Chromatic Correlation Clusteringcited by 0
  15. 2026UniFair: A unified fair clustering approach based on separation and compactnesscited by 0