Guarantees for Spectral Clustering with Fairness Constraints

Abstract

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). According to this notion, a clustering is fair if every demographic group is approximately proportionally represented in each cluster. To this end, we develop variants of both normalized and unnormalized constrained SC and show that they help find fairer clusterings on both synthetic and real data. We also provide a rigorous theoretical analysis of our algorithms on a natural variant of the stochastic block model, where $h$ groups have strong inter-group connectivity, but also exhibit a "natural" clustering structure which is fair. We prove that our algorithms can recover this fair clustering with high probability.

Cited by in corpus (17)

• Fair k-Center Clustering for Data Summarization
• RawlsGCN: Towards Rawlsian Difference Principle on Graph Convolutional Network
• Individual Fairness for $k$-Clustering
• Fair Hierarchical Clustering
• Equalized odds postprocessing under imperfect group information
• Distributional Individual Fairness in Clustering
• Fair Correlation Clustering
• Spectral Normalized-Cut Graph Partitioning with Fairness Constraints
• Fair Clustering with Multiple Colors
• Hypergraph Clustering for Finding Diverse and Experienced Groups
• Principal Fairness: Removing Bias via Projections
• A Stochastic Alternating Balance $k$-Means Algorithm for Fair Clustering
• Deep Fair Discriminative Clustering
• Fair Clustering Using Antidote Data
• Spectral Clustering with Smooth Tiny Clusters
• A Sociotechnical View of Algorithmic Fairness
• Fairness Degrading Adversarial Attacks Against Clustering Algorithms