Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold
The stochastic block model is a canonical random graph model for clustering and community detection on network-structured data. Decades of extensive study on the problem have established many profound results, among which the phase transition at the Kesten-Stigum threshold is particularly interesting both from a mathematical and an applied standpoint. It states that no estimator based on the network topology can perform substantially better than chance on sparse graphs if the model parameter is below a certain threshold. Nevertheless, if we slightly extend the horizon to the ubiquitous semi-supervised setting, such a fundamental limitation will disappear completely. We prove that with an arbitrary fraction of the labels revealed, the detection problem is feasible throughout the parameter domain. Moreover, we introduce two efficient algorithms, one combinatorial and one based on optimization, to integrate label information with graph structures. Our work brings a new perspective to the stochastic model of networks and semidefinite program research.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringCommunity DetectionStochastic Block ModelSimilar Papers 제목 키워드 기반
A semi-supervised sparse K-Means algorithm
We consider the problem of data clustering with unidentified feature quality and when a small amount of labelled data is provided. An unsupervised sparse clustering method can be employed in order to detect the subgroup …
ClusteringSemi-Unsupervised Learning: Clustering and Classifying using Ultra-Sparse Labels
In semi-supervised learning for classification, it is assumed that every ground truth class of data is present in the small labelled dataset. Many real-world sparsely-labelled datasets are plausibly not of this type. It …
ClusteringRethinking Semi-Supervised Node Classification with Self-Supervised Graph Clustering
The emergence of graph neural networks (GNNs) has offered a powerful tool for semi-supervised node classification tasks. Subsequent studies have achieved further improvements through refining the message passing schemes …
Node ClassificationData AugmentationGraph ClusteringExact Clustering of Weighted Graphs via Semidefinite Programming
As a model problem for clustering, we consider the densest k-disjoint-clique problem of partitioning a weighted complete graph into k disjoint subgraphs such that the sum of the densities of these subgraphs is maximized.…
ClusteringBridged Clustering: Semi-Supervised Sparse Bridging
We introduce Bridged Clustering, a semi-supervised framework to learn predictors from any unpaired input $X$ and output $Y$ dataset. Our method first clusters $X$ and $Y$ independently, then learns a sparse, interpretabl…