Reproduce “Accelerating Spectral Clustering under Fairness Constraints” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Francesco Tonin, Alex Lambert, Johan A. K. Suykens, Volkan Cevher
This research introduces an accelerated algorithm for Fair Spectral Clustering (Fair SC) based on a Difference of Convex (DC) programming reformulation and a tailored ADMM framework. The proposed method dramatically reduces the computational complexity from cubic to effectively quadratic, achieving significant speedups over existing approaches while preserving comparable fairness and clustering quality on both synthetic and real-world datasets.
Key insights
- Casting Fair Spectral Clustering into a Difference of Convex (DC) framework enables the application of powerful, scalable optimization techniques like ADMM.
- A novel variable augmentation strategy, by introducing an auxiliary variable Y such that MH = Y, effectively decouples the complex objective from the linear fairness constraints, allowing for efficient subproblem solutions.
- Optimizing with the squared affinity matrix M^2 rather than M provides a computationally efficient proxy for the original objective, yielding comparable fairness and clustering quality.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.