# Scalable Spectral Clustering with Group Fairness Constraints

arXiv: https://arxiv.org/abs/2210.16435 · HTML: https://mlsanity.com/paper/2210.16435/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 56 references that are in the map.
- First posted on arXiv 28 Oct 2022.

## Builds on (most cited first, 17 of 17)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Regression: Quantitative Definitions and Reduction-based Algorithms](https://mlsanity.com/paper/1905.12843/) (2019)
- [The Frontiers of Fairness in Machine Learning](https://mlsanity.com/paper/1810.08810/) (2018)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making](https://mlsanity.com/paper/1903.10598/) (2019)
- [Guarantees for Spectral Clustering with Fairness Constraints](https://mlsanity.com/paper/1901.08668/) (2019)
- [The Price of Fair PCA: One Extra Dimension](https://mlsanity.com/paper/1811.00103/) (2018)
- [Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys](https://mlsanity.com/paper/1506.03645/) (2015)
- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [A Framework for Deep Constrained Clustering -- Algorithms and Advances](https://mlsanity.com/paper/1901.10061/) (2019)
- [Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions](https://mlsanity.com/paper/2105.03714/) (2021)
- [Role of normalization in spectral clustering for stochastic blockmodels](https://mlsanity.com/paper/1310.1495/) (2013)

## Built on by (most cited first, 16 of 16)

- [Doubly Constrained Fair Clustering](https://mlsanity.com/paper/2305.19475/) (2023)
- [Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint](https://mlsanity.com/paper/2310.18593/) (2023)
- [Distribution-Specific Auditing For Subgroup Fairness](https://mlsanity.com/paper/2401.16439/) (2024)
- [Towards Cohesion-Fairness Harmony: Contrastive Regularization in Individual Fair Graph Clustering](https://mlsanity.com/paper/2402.10756/) (2024)
- [Spectral Normalized-Cut Graph Partitioning with Fairness Constraints](https://mlsanity.com/paper/2307.12065/) (2023)
- [A Unified Framework for Fair Spectral Clustering With Effective Graph Learning](https://mlsanity.com/paper/2311.13766/) (2023)
- [Fair Supervised Learning with A Simple Random Sampler of Sensitive Attributes](https://mlsanity.com/paper/2311.05866/) (2023)
- [Robust Fair Clustering with Group Membership Uncertainty Sets](https://mlsanity.com/paper/2406.00599/) (2024)
- [Recovering Fairness Directly from Modularity: a New Way for Fair Community Partitioning](https://mlsanity.com/paper/2505.22684/) (2025)
- [Accelerating Spectral Clustering under Fairness Constraints](https://mlsanity.com/paper/2506.08143/) (2025)
- [Alternatives to the Laplacian for Scalable Spectral Clustering with Group Fairness Constraints](https://mlsanity.com/paper/2510.20220/) (2025)
- [A Deep Latent Factor Graph Clustering with Fairness-Utility Trade-off Perspective](https://mlsanity.com/paper/2510.23507/) (2025)
- [FairAD: Computationally Efficient Fair Graph Clustering via Algebraic Distance](https://mlsanity.com/paper/2510.27136/) (2025)
- [Incorporating Fairness in Neighborhood Graphs for Fair Spectral Clustering](https://mlsanity.com/paper/2512.09810/) (2025)
- [Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals](https://mlsanity.com/paper/2604.26446/) (2026)
- [Fairness-Aware Network Embeddings: Methods, Applications, and Challenges](https://mlsanity.com/paper/2608.19381/) (2026)

## Abstract (arXiv)

There are synergies of research interests and industrial efforts in modeling fairness and correcting algorithmic bias in machine learning. In this paper, we present a scalable algorithm for spectral clustering (SC) with group fairness constraints. Group fairness is also known as statistical parity where in each cluster, each protected group is represented with the same proportion as in the entirety. While FairSC algorithm (Kleindessner et al., 2019) is able to find the fairer clustering, it is compromised by high costs due to the kernels of computing nullspaces and the square roots of dense matrices explicitly. We present a new formulation of underlying spectral computation by incorporating nullspace projection and Hotelling's deflation such that the resulting algorithm, called s-FairSC, only involves the sparse matrix-vector products and is able to fully exploit the sparsity of the fair SC model. The experimental results on the modified stochastic block model demonstrate that s-FairSC is comparable with FairSC in recovering fair clustering. Meanwhile, it is sped up by a factor of 12 for moderate model sizes. s-FairSC is further demonstrated to be scalable in the sense that the computational costs of s-FairSC only increase marginally compared to the SC without fairness constraints.