Scalable Spectral Clustering with Group Fairness Constraints
Scalable Spectral Clustering with Group Fairness Constraints
复制标题
DOI：
10.48550/arxiv.2210.16435
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Ji Wang;Ding Lu;Z. Bai;I. Davidson
中科院分区：
文献类型：
--
作者：
Ji Wang;Ding Lu;Z. Bai;I. Davidson
研究兴趣和工业努力在建模公平性和纠正机器学习中的算法偏见方面具有协同作用。本文提出了一种具有组公平性约束的谱聚类算法。组公平性也被称为统计奇偶性，在每个集群中，每个受保护组都以与整体相同的比例表示。虽然FairSC算法（Kleindessner等人，2019）能够找到更公平的聚类，但由于显式计算零空间的内核和稠密矩阵的平方根而导致高成本。我们提出了一个新的配方的基础频谱计算，通过将零空间投影和Hotelling的通缩，从而产生的算法，称为S-FairSC，只涉及稀疏矩阵向量产品，并能够充分利用稀疏的公平SC模型。在改进的随机块模型上的实验结果表明，s-FairSC算法在恢复公平聚类方面与FairSC算法相当.同时，对于中等模型尺寸，它的速度提高了12倍。S-FairSC被进一步证明是可扩展的，在这个意义上，S-FairSC的计算成本相比于没有公平性约束的SC仅略微增加。
There are synergies of research interests and industrial efforts in modeling fairness and correcting algorithmic bias in machine learning. In this paper, we present a scalable algorithm for spectral clustering (SC) with group fairness constraints. Group fairness is also known as statistical parity where in each cluster, each protected group is represented with the same proportion as in the entirety. While FairSC algorithm (Kleindessner et al., 2019) is able to find the fairer clustering, it is compromised by high costs due to the kernels of computing nullspaces and the square roots of dense matrices explicitly. We present a new formulation of underlying spectral computation by incorporating nullspace projection and Hotelling's deflation such that the resulting algorithm, called s-FairSC, only involves the sparse matrix-vector products and is able to fully exploit the sparsity of the fair SC model. The experimental results on the modified stochastic block model demonstrate that s-FairSC is comparable with FairSC in recovering fair clustering. Meanwhile, it is sped up by a factor of 12 for moderate model sizes. s-FairSC is further demonstrated to be scalable in the sense that the computational costs of s-FairSC only increase marginally compared to the SC without fairness constraints.