Scalable Spectral Clustering with Group Fairness Constraints

There are synergies of research interests and in-dustrial efforts in modeling fairness and correct-ing algorithmic bias in machine learning. Inthis paper, we present a scalable algorithm forspectral clustering (SC) with group fairness con-straints. Group fairness is also known as statis-tical parity where in each cluster, each protectedgroup is represented with the same proportion asin the entirety. While FairSC algorithm (Klein-dessner et al., 2019) is able to find the fairer clus-tering, it is compromised by high computationalcosts due to the algorithm’s kernels of computingnullspaces and the square roots of dense matricesexplicitly. We present a new formulation of theunderlying spectral computation of FairSC by in-corporating nullspace projection and Hotelling’sdeflation such that the resulting algorithm, calleds-FairSC, only involves the sparse matrix-vectorproducts and is able to fully exploit the sparsityof the fair SC model. The experimental resultson the modified stochastic block model demon-strate that while it is comparable with FairSC inrecovering fair clustering, s-FairSC is 12× fasterthan FairSC for moderate model sizes. s-FairSCis further demonstrated to be scalable in the sensethat the computational costs of s-FairSC only in-crease marginally compared to the SC withoutfairness constraints.