Partial Recovery and Weak Consistency in the Non-Uniform Hypergraph Stochastic Block Model

We consider the community detection problem in sparse random hypergraphs under the non-uniform hypergraph stochastic block model (HSBM), a general model of random networks with community structure and higher-order interactions. When the random hypergraph has bounded expected degrees, we provide a spectral algorithm that outputs a partition with at least a $\gamma$ fraction of the vertices classified correctly, where $\gamma\in (0.5,1)$ depends on the signal-to-noise ratio (SNR) of the model. When the SNR grows slowly as the number of vertices goes to infinity, our algorithm achieves weak consistency, which improves the previous results in Ghoshdastidar and Dukkipati (2017) for non-uniform HSBMs. Our spectral algorithm consists of three major steps: (1) Hyperedge selection: select hyperedges of certain sizes to provide the maximal signal-to-noise ratio for the induced sub-hypergraph; (2) Spectral partition: construct a regularized adjacency matrix and obtain an approximate partition based on singular vectors; (3) Correction and merging: incorporate the hyperedge information from adjacency tensors to upgrade the error rate guarantee. The theoretical analysis of our algorithm relies on the concentration and regularization of the adjacency matrix for sparse non-uniform random hypergraphs, which can be of independent interest.

Partial recovery and weak consistency in the non-uniform Hypergraph Stochastic Block Model Ioana Dumitriu∗ Hai-Xiao Wang† Yizhe Zhu‡ This version: June 2026 arXiv:2112.11671v4 [math.ST] 2 Jun 2026 Abstract…

saved by

• Roland Riachi

related reading

• Comparison principle for stochastic heat equation on Rdmath.emory.edu
• The Concentration of Invariant Measures for Stochastic Dynamical Systems with Locally Lipschitz Continuous Coefficients in R^darxiv.org
• Inverse Source Problems for the Stochastic Wave Equations: Far-Field Patternsarxiv.org
• Stochastic Heat Equations with General Multiplicative Gaussian Noises: Hölder Continuity and Intermittencyarxiv.org
• High-Dimensional Gaussian Sampling: A Review and a Unifying Approach Based on a Stochastic Proximal Point Algorithmarxiv.org
• Stochastic Modified Equations and Dynamics of Stochastic Gradient Algorithms I: Mathematical Foundationsjmlr.org
• Density Dependent Singular Stochastic Differential Equationsarxiv.org
• Analysis of Circulant Embedding Methods for Sampling Stationary Random Fieldsarxiv.org
• Hölder-continuity for the nonlinear stochastic heat equation with rough initial conditionsmath.emory.edu
• A Feynman-Kac Approach for the Spatial Derivative of the Solution to the Wick Stochastic Heat Equation Driven by Time Homogeneous White Noisearxiv.org
• A Primer on Stochastic Partial Differential Equationsmath.utah.edu
• Dynamical Approach to RMT.pdfpeople.math.harvard.edu