# Accelerating Spectral Clustering under Fairness Constraints

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 54 references that are in the map.
- First posted on arXiv 9 Jun 2025.

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

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Empirical Risk Minimization under Fairness Constraints](https://mlsanity.com/paper/1802.08626/) (2018)
- [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)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [Global Convergence of ADMM in Nonconvex Nonsmooth Optimization](https://mlsanity.com/paper/1511.06324/) (2015)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (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)
- [Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems](https://mlsanity.com/paper/1410.1390/) (2014)
- [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019)
- [Fair and Diverse DPP-based Data Summarization](https://mlsanity.com/paper/1802.04023/) (2018)
- [Global convergence of splitting methods for nonconvex composite optimization](https://mlsanity.com/paper/1407.0753/) (2014)
- [Scalable Spectral Clustering with Group Fairness Constraints](https://mlsanity.com/paper/2210.16435/) (2022)
- [On the Convergence of Alternating Direction Lagrangian Methods for Nonconvex Structured Optimization Problems](https://mlsanity.com/paper/1409.8033/) (2014)
- [Extending Kernel PCA through Dualization: Sparsity, Robustness and Fast Algorithms](https://mlsanity.com/paper/2306.05815/) (2023)
- [Bregman Proximal Linearized ADMM for Minimizing Separable Sums Coupled by a Difference of Functions](https://mlsanity.com/paper/2401.02635/) (2024)

## Abstract (arXiv)

Fairness of decision-making algorithms is an increasingly important issue. In this paper, we focus on spectral clustering with group fairness constraints, where every demographic group is represented in each cluster proportionally as in the general population. We present a new efficient method for fair spectral clustering (Fair SC) by casting the Fair SC problem within the difference of convex functions (DC) framework. To this end, we introduce a novel variable augmentation strategy and employ an alternating direction method of multipliers type of algorithm adapted to DC problems. We show that each associated subproblem can be solved efficiently, resulting in higher computational efficiency compared to prior work, which required a computationally expensive eigendecomposition. Numerical experiments demonstrate the effectiveness of our approach on both synthetic and real-world benchmarks, showing significant speedups in computation time over prior art, especially as the problem size grows. This work thus represents a considerable step forward towards the adoption of fair clustering in real-world applications.