![[2510.20220] Alternatives to the Laplacian for Scalable Spectral Clustering with Group Fairness Constraints](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2510.20220] Alternatives to the Laplacian for Scalable Spectral Clustering with Group Fairness Constraints
Summary
This paper presents the Fair-SMW algorithm, an innovative approach to spectral clustering that enhances computational efficiency while ensuring group fairness in clustering outcomes.
Why It Matters
The study addresses the critical issue of algorithmic bias in clustering, proposing a more efficient method that balances fairness and performance. This is particularly relevant as organizations increasingly rely on data-driven decisions that must be equitable across different demographic groups.
Key Takeaways
- Introduces Fair-SMW algorithm to improve spectral clustering efficiency.
- Utilizes alternatives to the Laplacian matrix for better performance.
- Achieves clustering solutions with enhanced balance and reduced computation time.
- Evaluated on real-world datasets, demonstrating significant runtime improvements.
- Addresses algorithmic bias by ensuring equitable representation in clusters.
Computer Science > Machine Learning arXiv:2510.20220 (cs) [Submitted on 22 Oct 2025 (v1), last revised 18 Feb 2026 (this version, v2)] Title:Alternatives to the Laplacian for Scalable Spectral Clustering with Group Fairness Constraints Authors:Iván Ojeda-Ruiz, Young Ju Lee, Malcolm Dickens, Leonardo Cambisaca View a PDF of the paper titled Alternatives to the Laplacian for Scalable Spectral Clustering with Group Fairness Constraints, by Iv\'an Ojeda-Ruiz and 3 other authors View PDF HTML (experimental) Abstract:Recent research has focused on mitigating algorithmic bias in clustering by incorporating fairness constraints into algorithmic design. Notions such as disparate impact, community cohesion, and cost per population have been implemented to enforce equitable outcomes. Among these, group fairness (balance) ensures that each protected group is proportionally represented within every cluster. However, incorporating balance as a metric of fairness into spectral clustering algorithms has led to computational times that can be improved. This study aims to enhance the efficiency of spectral clustering algorithms by reformulating the constrained optimization problem using a new formulation derived from the Lagrangian method and the Sherman-Morrison-Woodbury (SMW) identity, resulting in the Fair-SMW algorithm. Fair-SMW employs three alternatives to the Laplacian matrix with different spectral gaps to generate multiple variations of Fair-SMW, achieving clustering solutions with...