A Semidefinite Relaxation Approach for Fair Graph Clustering
This addresses fair representation in network analysis for diverse communities, offering a tunable trade-off between clustering quality and fairness, but it is incremental as it builds on existing optimization frameworks.
The paper tackles fair graph clustering by formulating it as a joint optimization problem with fairness constraints, using a semidefinite relaxation approach to approximate the NP-hard problem. Experimental results on stochastic block model graphs show it achieves an optimal accuracy-fairness trade-off compared to state-of-the-art methods.
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.