Riemannian Optimization for Fair Spectral Clustering

Fair graph clustering has emerged as a critical research area for addressing algorithmic bias in machine learning. The objective is to ensure that the proportion of each protected group within a cluster is consistent with its representation in the entire dataset. However, most existing spectral solutions rely on computationally expensive eigendecompositions of the graph Laplacian, limiting their scalability. In this paper, we propose Riemannian Fair Spectral Clustering (R-FairSC), a novel method that formulates fair spectral clustering as a constrained optimization problem on a Riemannian manifold. We develop a Riemannian alternating direction method of multipliers employing a variable-splitting strategy to efficiently solve the associated subproblems. Numerical experiments on large synthetic and real-world graphs demonstrate that R-FairSC significantly improves computational efficiency over state-of-the-art methods while maintaining high clustering quality and fairness.

Graph clustering is a widely used method that analyzes relationships within a network to group closely connected entities together. For example, in a social network, people with close relationships may be placed in the same group. However, such a grouping may neglect their inherent demographic traits, causing members of a minority group to be concentrated in one cluster rather than spread proportionally across clusters. This can negatively impact high-stakes decisions in areas such as finance, education, or risk assessment. Fair graph clustering addresses this problem by ensuring that different demographic groups are fairly represented across all clusters. The goal is to produce groups that remain meaningful in terms of the network's structure, while also making sure that the proportion of different demographics in each cluster roughly matches their proportion in the overall network. In this work, we design a faster method for fair graph clustering. Instead of relying on the costly computations used by existing methods, our approach reformulates the problem as an optimization on a curved geometric space (known as a Riemannian manifold) and uses a tailored strategy to solve it efficiently. Our work provides a more scalable solution for implementing fair graph clustering in practical applications.