Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, November 29, 2022 - 3:30pm

Yizhe Zhu

University of California, Irvine

Location

University of Pennsylvania

DRL 4C8

The stochastic block model has been one of the most fruitful research topics in community detection and clustering. Recently, community detection on hypergraphs has become an important topic in higher-order network analysis. We consider the detection problem in a sparse random tensor model called the hypergraph stochastic block model (HSBM). We prove that a spectral method based on the non-backtracking operator for hypergraphs works with high probability down to the generalized Kesten-Stigum detection threshold conjectured by Angelini et al (2015). We characterize the spectrum of the non-backtracking operator for sparse random hypergraphs and provide an efficient dimension reduction procedure using the Ihara-Bass formula for hypergraphs. As a result, the community detection problem can be reduced to an eigenvector problem of a non-normal matrix constructed from the adjacency matrix of the hypergraph. Based on joint work with Ludovic Stephan (EPFL).