Fair Correlation Clustering
It addresses fairness in clustering for applications requiring equitable group representation, but is incremental as it builds on existing fair clustering frameworks.
The paper tackles fair correlation clustering by developing approximation algorithms for various fairness constraints, achieving solutions with limited cost increase compared to unfair state-of-the-art methods on real graphs.
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.