Fair Spectral Clustering Based on Coordinate Descent

Research on the fairness of spectral clustering has gradually increased attention. Normally, existing methods of fair spectral clustering add a fairness constraint to the original objective function so that fairness is guaranteed. However, similar to the solver of traditional spectral clustering, that of fairness spectral clustering has to relax a discrete value condition into an arbitrary one, which leads to the deterioration of both fairness and clustering quality. Moreover, the eigen-problem is inevitable in the solver, which takes O(n3) time complexity and is not available for large-scale data. In this paper, we propose a fair spectral clustering algorithm by employing the coordinate descent method to find the solution. As the relaxation of the discreteness condition is discarded, the fairness is improved. Furthermore, we refine the process of coordinate descent by avoiding redundant calculations, and as a result, the time complexity is reduced from O(n3) to O(n2). Additionally, the importance of clustering quality and fairness is symmetric; hence, we achieve a trade-off between them by adjusting the parameters. The experimental findings, obtained from both real-world and synthetic datasets, clearly illustrate that our proposal delivers superior fairness and clustering quality with the best BAL compared to other fair clustering methods. In addition, our method is more efficient than existing fair spectral clustering algorithms.