# Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Sep 2019.

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

- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [Exact Recovery in the General Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2105.04770/) (2021)
- [Latent Space Model for Higher-order Networks and Generalized Tensor Decomposition](https://mlsanity.com/paper/2106.16042/) (2021)
- [Community Detection in General Hypergraph via Graph Embedding](https://mlsanity.com/paper/2103.15035/) (2021)
- [Estimating Higher-Order Mixed Memberships via the ℓ2,∞ Tensor Perturbation Bound](https://mlsanity.com/paper/2212.08642/) (2022)
- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)
- [Sharp detection boundaries on testing dense subhypergraph](https://mlsanity.com/paper/2101.04584/) (2021)
- [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022)
- [Nonparametric Modeling of Higher-Order Interactions via Hypergraphons](https://mlsanity.com/paper/2105.08678/) (2021)
- [Multiway Spherical Clustering via Degree-Corrected Tensor Block Models](https://mlsanity.com/paper/2201.07401/) (2022)
- [Nonbacktracking spectral clustering of nonuniform hypergraphs](https://mlsanity.com/paper/2204.13586/) (2022)
- [Online Tensor Learning: Computational and Statistical Trade-offs, Adaptivity and Optimal Regret](https://mlsanity.com/paper/2306.03372/) (2023)
- [Co-clustering Vertices and Hyperedges via Spectral Hypergraph Partitioning](https://mlsanity.com/paper/2102.10169/) (2021)
- [A useful criterion on studying consistent estimation in community detection](https://mlsanity.com/paper/2109.14950/) (2021)
- [Heterogeneous Dense Subhypergraph Detection](https://mlsanity.com/paper/2104.04047/) (2021)
- [Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix](https://mlsanity.com/paper/2208.12227/) (2022)
- [Multilayer hypergraph clustering using the aggregate similarity matrix](https://mlsanity.com/paper/2301.11657/) (2023)
- [Degree Heterogeneity in Higher-Order Networks: Inference in the Hypergraph boldsymbolβ-Model](https://mlsanity.com/paper/2307.02818/) (2023)
- [Community detection in censored hypergraph](https://mlsanity.com/paper/2111.03179/) (2021)
- [Tensorized Hypergraph Neural Networks](https://mlsanity.com/paper/2306.02560/) (2023)
- [Scalable tensor methods for nonuniform hypergraphs](https://mlsanity.com/paper/2306.17825/) (2023)
- [Tensor Methods in High Dimensional Data Analysis: Opportunities and Challenges](https://mlsanity.com/paper/2405.18412/) (2024)
- [Community and hyperedge inference in multiple hypergraphs](https://mlsanity.com/paper/2505.04967/) (2025)
- [Perfect Clustering in Very Sparse Diverse Multiplex Networks](https://mlsanity.com/paper/2507.19423/) (2025)
- [From Representation to Clusters: A Contrastive Learning Approach for Attributed Hypergraph Clustering](https://mlsanity.com/paper/2603.09370/) (2026)
- [Achieving the Kesten-Stigum bound in the non-uniform hypergraph stochastic block model](https://mlsanity.com/paper/2604.20907/) (2026)
- [Dynamic Topic Modeling with a Higher-Order Hypergraphical Representation](https://mlsanity.com/paper/2605.28269/) (2026)

## Abstract (arXiv)

To date, social network analysis has been largely focused on pairwise interactions. The study of higher-order interactions, via a hypergraph network, brings in new insights. We study community detection in a hypergraph network. A popular approach is to project the hypergraph to a graph and then apply community detection methods for graph networks, but we show that this approach may cause unwanted information loss. We propose a new method for community detection that operates directly on the hypergraph. At the heart of our method is a regularized higher-order orthogonal iteration (reg-HOOI) algorithm that computes an approximate low-rank decomposition of the network adjacency tensor. Compared with existing tensor decomposition methods such as HOSVD and vanilla HOOI, reg-HOOI yields better performance, especially when the hypergraph is sparse. Given the output of tensor decomposition, we then generalize the community detection method SCORE (Jin, 2015) from graph networks to hypergraph networks. We call our new method Tensor-SCORE. In theory, we introduce a degree-corrected block model for hypergraphs (hDCBM), and show that Tensor-SCORE yields consistent community detection for a wide range of network sparsity and degree heterogeneity. As a byproduct, we derive the rates of convergence on estimating the principal subspace by reg-HOOI, with different initializations, including the two new initialization methods we propose, a diagonal-removed HOSVD and a randomized graph projection. We apply our method to several real hypergraph networks which yields encouraging results. It suggests that exploring higher-order interactions provides additional information not seen in graph representations.