A Semidefinite Relaxation Approach for Fair Graph Clustering

Fair graph clustering ensures the equitable representation and treatment of diverse communities in network analysis. Traditional methods often overlook disparities among social, economic, and demographic groups, which can perpetuate bias and reinforce 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 the adjustment of the trade-off between clustering quality and fairness. Furthermore, our approach is compatible with existing graph clustering techniques, enabling easy integration into current frameworks for both researchers and practitioners. Experimental results on synthetic and real-world datasets demonstrate the superiority of our method in achieving an optimal accuracy-fairness balance, outperforming state-of-the-art techniques.