Accelerating Spectral Clustering under Fairness Constraints
Fairness of decision-making algorithms is an increasingly important issue. In this paper, we focus on spectral clustering with group fairness constraints, where every demographic group is represented in each cluster proportionally as in the general population. We present a new efficient method for fair spectral clustering (Fair SC) by casting the Fair SC problem within the difference of convex functions (DC) framework. To this end, we introduce a novel variable augmentation strategy and employ an alternating direction method of multipliers type of algorithm adapted to DC problems. We show that each associated subproblem can be solved efficiently, resulting in higher computational efficiency compared to prior work, which required a computationally expensive eigendecomposition. Numerical experiments demonstrate the effectiveness of our approach on both synthetic and real-world benchmarks, showing significant speedups in computation time over prior art, especially as the problem size grows. This work thus represents a considerable step forward towards the adoption of fair clustering in real-world applications.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringComputational EfficiencyDecision MakingFairnessMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Scalable Spectral Clustering with Group Fairness Constraints
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 …
ClusteringFairnessStochastic Block ModelAlternatives to the Laplacian for Scalable Spectral Clustering with Group Fairness Constraints
Recent research has focused on mitigating algorithmic bias in clustering by incorporating fairness constraints into algorithmic design. Notions such as disparate impact, community cohesion, and cost per population have b…
Incorporating Fairness in Neighborhood Graphs for Fair Spectral Clustering
Graph clustering plays a pivotal role in unsupervised learning methods like spectral clustering, yet traditional methods for graph clustering often perpetuate bias through unfair graph constructions that may underreprese…
Graph ClusteringGuarantees for Spectral Clustering with Fairness Constraints
Given the widespread popularity of spectral clustering (SC) for partitioning graph data, we study a version of constrained SC in which we try to incorporate the fairness notion proposed by Chierichetti et al. (2017). Acc…
ClusteringFairnessStochastic Block ModelDeep Fair Discriminative Clustering
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 repres…
ClusteringDeep ClusteringFairnessRepresentation Learning