Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions
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. This graph specifies node pairs that can represent each other with respect to sensitive attributes and is observed in addition to the usual \textit{similarity graph}. Our goal is to find clusters in the similarity graph while respecting a new individual-level fairness constraint encoded by the representation graph. We develop variants of unnormalized and normalized spectral clustering for this task and analyze their performance under a \emph{fair} planted partition model induced by the representation graph. This model uses both the cluster membership of the nodes and the structure of the representation graph to generate random similarity graphs. To the best of our knowledge, these are the first consistency results for constrained spectral clustering under an individual-level fairness constraint. Numerical results corroborate our theoretical findings.
Code (0)
등록된 구현이 없습니다.
Tasks
AttributeClusteringDecision MakingFairnessStochastic Block ModelMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
On consistency of constrained spectral clustering under representation-aware stochastic block model
Spectral clustering is widely used in practice due to its flexibility, computational efficiency, and well-understood theoretical performance guarantees. Recently, spectral clustering has been studied to find balanced clu…
ClusteringComputational EfficiencyStochastic Block ModelMulti-view Spectral Clustering on the Grassmannian Manifold With Hypergraph Representation
Graph-based multi-view spectral clustering methods have achieved notable progress recently, yet they often fall short in either oversimplifying pairwise relationships or struggling with inefficient spectral decomposition…
ClusteringRepresentation LearningRiemannian optimizationStrong Consistency, Graph Laplacians, and the Stochastic Block Model
Spectral clustering has become one of the most popular algorithms in data clustering and community detection. We study the performance of classical two-step spectral clustering via the graph Laplacian to learn the stocha…
ClusteringCommunity DetectionStochastic Block ModelHigher-Order Spectral Clustering for Geometric Graphs
The present paper is devoted to clustering geometric graphs. While the standard spectral clustering is often not effective for geometric graphs, we present an effective generalization, which we call higher-order spectral…
ClusteringRevisiting Self-Supervised Heterogeneous Graph Learning from Spectral Clustering Perspective
Self-supervised heterogeneous graph learning (SHGL) has shown promising potential in diverse scenarios. However, while existing SHGL methods share a similar essential with clustering approaches, they encounter two signif…
ClusteringGraph Learning