Hypergraph Clustering in the Weighted Stochastic Block Model via Convex Relaxation of Truncated MLE
share
We study hypergraph clustering under the weighted d-uniform hypergraph stochastic block model (d-WHSBM), where each edge consisting of d nodes has higher expected weight if d nodes are from the same community compared to edges consisting of nodes from different communities. We propose a new hypergraph clustering algorithm, which is a convex relaxation of truncated maximum likelihood estimator (CRTMLE), that can handle the relatively sparse, high-dimensional regime of the d-WHSBM with community sizes of different orders. We provide performance guarantees of this algorithm under a unified framework for different parameter regimes, and show that it achieves the order-wise optimal or the best existing results for approximately balanced community sizes. We also demonstrate the first recovery guarantees for the setting with growing number of communities of unbalanced sizes.
READ FULL TEXT