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 clusters under population-level constraints. These constraints are specified by additional information available in the form of auxiliary categorical node attributes. In this paper, we consider a scenario where these attributes may not be observable, but manifest as latent features of an auxiliary graph. Motivated by this, we study constrained spectral clustering with the aim of finding balanced clusters in a given \textit{similarity graph} $\mathcal{G}$, such that each individual is adequately represented with respect to an auxiliary graph $\mathcal{R}$ (we refer to this as representation graph). We propose an individual-level balancing constraint that formalizes this idea. Our work leads to an interesting stochastic block model that not only plants the given partitions in $\mathcal{G}$ but also plants the auxiliary information encoded in the representation graph $\mathcal{R}$. We develop unnormalized and normalized variants of spectral clustering in this setting. These algorithms use $\mathcal{R}$ to find clusters in $\mathcal{G}$ that approximately satisfy the proposed constraint. We also establish the first statistical consistency result for constrained spectral clustering under individual-level constraints for graphs sampled from the above-mentioned variant of the stochastic block model. Our experimental results corroborate our theoretical findings.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringComputational EfficiencyStochastic Block ModelMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
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, req…
AttributeClusteringDecision MakingFairness+1Multi-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 optimizationRevisiting 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 LearningOn Constrained Spectral Clustering and Its Applications
Constrained clustering has been well-studied for algorithms such as $K$-means and hierarchical clustering. However, how to satisfy many constraints in these algorithmic settings has been shown to be intractable. One alte…
ClusteringConstrained ClusteringTransfer LearningvalidStrong 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 Model