# Projected Tensor Power Method for Hypergraph Community Recovery

arXiv: https://arxiv.org/abs/2307.00210 · HTML: https://mlsanity.com/paper/2307.00210/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2023.

## Built on by (most cited first, 2 of 2)

- [On the Estimation Performance of Generalized Power Method for Heteroscedastic Probabilistic PCA](https://mlsanity.com/paper/2312.03438/) (2023)
- [Performance Gaps in Multi-view Clustering under the Nested Matrix-Tensor Model](https://mlsanity.com/paper/2402.10677/) (2024)

## Abstract (arXiv)

This paper investigates the problem of exact community recovery in the symmetric d-uniform (d ≥ 2) 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 K≥ 2 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 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 O(nlog2n/loglog n) when the aforementioned initialization condition is met. We also conduct numerical experiments to validate our theoretical findings.