Research map / Learning theory and algorithms / Fairness

Accelerating Spectral Clustering under Fairness Constraints

ICML 2025 · Learning theory and algorithms › Fairness · approach: Fairness-constrained classification · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a faster fair spectral clustering method that casts the group-fairness-constrained trace maximization as a difference-of-convex problem solved with an ADMM-type scheme and dual gradient-based (L-BFGS) optimization, avoiding eigendecomposition.

Problem

Fair spectral clustering with group-proportional fairness constraints is limited in scalability because existing algorithms (o-FSC, s-FSC) require eigendecomposition of a fairness-modified graph Laplacian.

Approach

Reformulate Fair SC as a DC problem in terms of M^2 with a variable augmentation coupling the fairness linear constraint to MH, then use ADMM where the H-subproblem is solved via its dual with L-BFGS and the Y-subproblem has a closed form in a nullspace parameterization, avoiding eigendecompositions.

Key results

• On m-SBM with n=10000, k=50, the proposed method runs in 9.19 s versus 495.70 s for o-FSC and 107.94 s for s-FSC, with balance 1.0 for all methods.
• On real-world datasets with k=25, the method is 4-8x faster than s-FSC (e.g., 4area n=35385: 25.85 s vs 166.92 s) with comparable clustering cost and balance.
• Compared with FFSC and UFSC, the method is 7-12x faster and achieves a much lower fairness violation and better clustering cost on LastFM and Thyroid.

Measured effects reported in the paper

Surprising findings

• Enforcing the fairness constraint on MH rather than H yields solutions with comparable group balance to the exact method, despite the change in formulation.
• Optimizing with M^2 instead of M, avoiding computing M^{1/2}, is reported to give comparable fairness empirically.

Limitations

• No guarantee on the balance of the resulting clustering in general, as in prior fair spectral clustering work.
• Convergence result for nonconvex ADMM relies on an assumption that the dual sequence converges; the proof is only partial.
• Requires M to be full rank (assumed), and the dual cost scales as O(kn^2) per iteration with dense M.

Experimental setup

Datasets: m-SBM RandLaplace Elliptical LastFMNet Thyroid Census 4area FacebookNet DS-577

Benchmarks: m-SBM RandLaplace Elliptical LastFMNet Thyroid Census 4area FacebookNet

Metrics: runtime (s) average balance clustering cost minimum balance constraint feasibility

Baselines: o-FSC s-FSC FFSC UFSC

Builds on: spectral clustering fair spectral clustering (o-FSC) s-FSC ADMM for DC problems

Closest papers by meaning

• Guarantees for Spectral Clustering with Fairness Constraints (ICML 2019 · similarity 0.93)
• Variational Fair Clustering (AAAI 2021 · similarity 0.92)
• Fair Clustering via Alignment (ICML 2025 · similarity 0.88)
• Parameterized Approximation Schemes for Fair-Range Clustering (NeurIPS 2024 · similarity 0.87)
• The Fairness-Quality Tradeoff in Clustering (NeurIPS 2024 · similarity 0.87)
• Towards Fairer Centroids in K-means Clustering (AAAI 2024 · similarity 0.87)