paper-with-me

홈 › Papers

On consistency of constrained spectral clustering under representation-aware stochastic block model

2022-03-03 · Shubham Gupta, Ambedkar Dukkipati

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.

📄 PDF Abstract BibTeX arXiv:2203.02005

Code (0)

등록된 구현이 없습니다.

Tasks

ClusteringComputational EfficiencyStochastic Block Model

Methods 이 논문이 사용한 방법론

Spectral Clustering Spectral clustering has attracted increasing attention due to the promising ability in dealing with nonlinearly separable datasets [15], [16]. In spectral clustering, the…

Similar Papers 제목 키워드 기반

Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions

2021-05-08 · Shubham Gupta, Ambedkar Dukkipati

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+1

Multi-view Spectral Clustering on the Grassmannian Manifold With Hypergraph Representation

2025-03-08 · Murong Yang, Shihui Ying, Xin-Jian Xu, Yue Gao

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 optimization

Revisiting Self-Supervised Heterogeneous Graph Learning from Spectral Clustering Perspective

2024-12-01 · Yujie Mo, Zhihe Lu, Runpeng Yu, Xiaofeng Zhu 외

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

On Constrained Spectral Clustering and Its Applications

2012-01-25 · Xiang Wang, Buyue Qian, Ian Davidson

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 Learningvalid

Strong Consistency, Graph Laplacians, and the Stochastic Block Model

2020-04-21 · Shaofeng Deng, Shuyang Ling, Thomas Strohmer

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