提出高效公平谱聚类算法，加速大规模数据处理。
Accelerating Spectral Clustering under Fairness Constraints
- 将公平谱聚类转化为凸差框架，设计新变量扩展策略
- 无需昂贵特征分解，计算速度显著提升
- 适合需要公平性保障的大规模聚类场景
决策算法的公平性日益重要。本文研究带有群体公平约束的谱聚类，要求每个群组在各聚类中的比例与总体人口一致。我们提出一种新的高效公平谱聚类（Fair SC）方法，将问题纳入凸差函数（DC）框架，并引入新颖的变量扩展策略，结合适用于DC问题的交替方向乘子法。证明每个子问题均可高效求解，相比先前工作避免了计算成本高昂的特征分解，显著提升效率。数值实验表明，在合成与真实世界基准上均有效，尤其在问题规模增大时计算时间大幅缩短。该工作为公平聚类在实际应用中的落地迈出关键一步。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。