Fair Correlation Clustering

Abstract

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.

References in corpus (10)

• The Dynamics of Viral Marketing
• Clustering without Over-Representation
• Scalable Fair Clustering
• Coresets for Clustering with Fairness Constraints
• Guarantees for Spectral Clustering with Fairness Constraints
• Proportionally Fair Clustering
• Correlation Clustering with Adaptive Similarity Queries
• Near Neighbor: Who is the Fairest of Them All?
• Achieving Fairness in Determining Medicaid Eligibility through Fairgroup Construction
• Improved algorithms for Correlation Clustering with local objectives

Cited by in corpus (1)

• Fair Clustering Under a Bounded Cost