Sparse random hypergraphs: Non-backtracking spectra and community detection

The stochastic block model (SBM), first introduced in [56], is a generative model for random graphs with a community structure. It serves as a useful benchmark for clustering algorithms on graph data. When the random graph generated by an SBM is sparse with bounded expected degrees, a phase transition has been observed around the so-called Kesten-Stigum threshold: in particular, above this threshold, a wealth of algorithms are known to achieve partial reconstruction [73, 6, 30, 57, 39]. Most relevant to this line of work are spectral algorithms that use the eigenvectors of a matrix associated with the graph G to perform the reconstruction. In the sparse case, examples include the self-avoiding [69], non-backtracking [38, 62, 23], graph powering [3] or distance [78] matrices. We refer interested readers to the survey [1] for more references, including a more in-depth discussion of the Kesten-Stigum threshold. As a generalization of graphs, hypergraphs are well-studied objects in combinatorics and theoretical computer science.