提出一种公平图聚类方法，平衡聚类精度与群体公平性。
A Semidefinite Relaxation Approach for Fair Graph Clustering
- 将公平性建模为优化约束，通过半定松弛求解
- 在随机块模型上实现更优的准确率-公平性权衡
- 支持调节公平与聚类质量的平衡，适合社会网络分析
公平图聚类对于确保网络分析中不同社群的公平代表性和待遇至关重要。传统方法常忽视社会、经济和人口群体间的差异，导致偏见结果并加剧不平等。本文在差别影响原则框架下提出公平图聚类，将其视为融合聚类质量与公平性约束的联合优化问题。由于该问题为NP难，采用半定松弛方法近似求解：对中小规模图使用基于奇异值分解的算法，对大规模图则提出基于交替方向乘子法的新算法。与现有方法不同，本方法可调节聚类质量与公平性的权衡。在标准随机块模型生成的图上，实验表明本方法在准确率-公平性权衡上优于当前最优方法。
原文摘要 · Abstract (English)
Fair graph clustering is crucial for ensuring equitable representation and treatment of diverse communities in network analysis. Traditional methods often ignore disparities among social, economic, and demographic groups, perpetuating biased outcomes and reinforcing inequalities. This study introduces fair graph clustering within the framework of the disparate impact doctrine, treating it as a joint optimization problem integrating clustering quality and fairness constraints. Given the NP-hard nature of this problem, we employ a semidefinite relaxation approach to approximate the underlying optimization problem. For up to medium-sized graphs, we utilize a singular value decomposition-based algorithm, while for larger graphs, we propose a novel algorithm based on the alternative direction method of multipliers. Unlike existing methods, our formulation allows for tuning the trade-off between clustering quality and fairness. Experimental results on graphs generated from the standard stochastic block model demonstrate the superiority of our approach in achieving an optimal accuracy-fairness trade-off compared to state-of-the-art methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。