Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions

Understand

Spectral clustering is popular among practitioners and theoreticians alike.

• While performance guarantees for spectral clustering are well understood, recent studies have focused on enforcing ``fairness'' in clusters, requiring them to be ``balanced'' with respect to a categorical sensitive node attribute (e.g.
• the race distribution in clusters must match the race distribution in the population).
• In this paper, we consider a setting where sensitive attributes indirectly manifest in an auxiliary \textit{representation graph} rather than being directly observed.