Non-Relaxed Fair Spectral Clustering on the Stiefel Manifold

Spectral clustering is a powerful paradigm for analyzing non-convex data, yet standard spectral clustering is oblivious to sensitive attributes, often producing clusters that are systematically biased with respect to protected groups. Existing Fairness SC methods face a critical dilemma: analytical approaches lack flexibility for complex constraints, while relaxation-based iterative methods compromise the core orthogonality constraint, thereby deviating from the graph’s intrinsic structure. To bridge this gap, we propose a novel optimization framework that directly solves the original non-convex fair SC problem on the Stiefel manifold. By integrating the Augmented Lagrangian Multiplier method to enforce linear fairness constraint and employing Projected Gradient Descent on the manifold, our approach rigorously guarantees orthogonality without convex relaxation. Extensive experiments on synthetic and real-world datasets demonstrate that our method efficiently optimizes the Normalized Cut objective, achieving numerical precision comparable to analytical solutions. Furthermore, it significantly outperforms state-of-the-art baselines in balancing clustering utility and fairness, exhibiting superior generalization and flexibility in parameter tuning.