Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration

Abstract

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.

arXiv comment53 pages, 5 figures

References in corpus (16)

• The structure of scientific collaboration networks
• Stochastic blockmodels and community structure in networks
• Higher-order organization of complex networks
• Fast community detection by SCORE
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
• Coauthorship and Citation Networks for Statisticians
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• A statistical model for tensor PCA
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Tensor principal component analysis via sum-of-squares proofs
• Detecting Overlapping Communities in Networks Using Spectral Methods
• Mixed Membership Estimation for Social Networks
• Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
• Optimal Estimation of Low Rank Density Matrices
• The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
• Characterizing Spatiotemporal Transcriptome of Human Brain via Low Rank Tensor Decomposition

Cited by in corpus (17)

• Mapping flows on hypergraphs
• Randomizing hypergraphs preserving degree correlation and local clustering
• Improvements on SCORE, Especially for Weak Signals
• Testing Community Structures for Hypergraphs
• Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit
• A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration
• A useful criterion on studying consistent estimation in community detection
• Strong Consistency of Spectral Clustering for the Sparse Degree-Corrected Hypergraph Stochastic Block Model
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons
• Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Model
• Community Detection in General Hypergraph via Graph Embedding
• Model-based clustering in simple hypergraphs through a stochastic blockmodel
• Flow-based Community Detection in Hypergraphs
• Heterogeneous Dense Subhypergraph Detection
• Multiway Spherical Clustering via Degree-Corrected Tensor Block Models
• Latent Space Model for Higher-order Networks and Generalized Tensor Decomposition
• Exact Recovery in the General Hypergraph Stochastic Block Model