  Deep clustering has the potential to learn a strong representation and hence
better clustering performance compared to traditional clustering methods such
as $k$-means and spectral clustering. However, this strong representation
learning ability may make the clustering unfair by discovering surrogates for
protected information which we empirically show in our experiments. In this
work, we study a general notion of group-level fairness for both binary and
multi-state protected status variables (PSVs). We begin by formulating the
group-level fairness problem as an integer linear programming formulation whose
totally unimodular constraint matrix means it can be efficiently solved via
linear programming. We then show how to inject this solver into a
discriminative deep clustering backbone and hence propose a refinement learning
algorithm to combine the clustering goal with the fairness objective to learn
fair clusters adaptively. Experimental results on real-world datasets
demonstrate that our model consistently outperforms state-of-the-art fair
clustering algorithms. Our framework shows promising results for novel
clustering tasks including flexible fairness constraints, multi-state PSVs and
predictive clustering.
