Projected Tensor Power Method for Hypergraph Community Recovery

MaRDI QIDQ6442200zbMATH OpenFDO

Authors Jinxin Wang, Yuen-Man Pun, Xiaolu Wang, Peng Wang, Anthony Man-Cho So

Publication date 30 June 2023

Abstract: This paper investigates the problem of exact community recovery in the symmetric $d$-uniform $(dgeq2)$ hypergraph stochastic block model ($d$-HSBM). In this model, a $d$-uniform hypergraph with $n$ nodes is generated by first partitioning the $n$ nodes into $Kgeq2$ equal-sized disjoint communities and then generating hyperedges with a probability that depends on the community memberships of $d$ nodes. Despite the non-convex and discrete nature of the maximum likelihood estimation problem, we develop a simple yet efficient iterative method, called the emph{projected tensor power method}, to tackle it. As long as the initialization satisfies a partial recovery condition in the logarithmic degree regime of the problem, we show that our proposed method can exactly recover the hidden community structure down to the information-theoretic limit with high probability. Moreover, our proposed method exhibits a competitive time complexity of $mathcalO(nlo{g}^{2}n/loglogn)$ when the aforementioned initialization condition is met. We also conduct numerical experiments to validate our theoretical findings.

This page was built for publication: Projected Tensor Power Method for Hypergraph Community Recovery

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6442200)