Hypergraph Stochastic Block Model

A hypergraph stochastic block model is a random hypergraph model in which every vertex receives a block label and the probability of a hyperedge depends on the labels of all its vertices. It generalizes the stochastic block model from pairwise to multiway connections.

Let be the set of allowed hyperedge sizes. For each , let the symmetric tensor specify the connection probabilities. A set is then included independently with probability

The model is uniform when has one member and nonuniform otherwise. In a sparse model, the scaling keeps the expected number of -hyperedges proportional to the number of vertices.

For the symmetric model with equal-sized blocks, let be the expected number of incident -hyperedges whose vertices all lie in the same block, let be the corresponding expectation for hyperedges meeting more than one block, and let be the average -degree. Li et al. (2026) give the Bethe Hessian spectral detectability boundary

This boundary applies to the stated sparse symmetric model, rather than to arbitrary hypergraph distributions. It also shows that different hyperedge sizes contribute with different weights. More generally, the distribution of the vertices of a hyperedge among blocks can make competing partitions differently detectable.