stat.MLApr 21, 2026

Achieving the Kesten-Stigum bound in the non-uniform hypergraph stochastic block model

Authors: Manuel Fernandez, Ludovic Stephan, Yizhe Zhu

Organizations: Department of Mathematics, University of Southern California · Univ Rennes, Ensai, CNRS, CREST-UMR 9194, F-35000 Rennes, France

Abstract

We study the community detection problem in the non-uniform hypergraph stochastic block model (HSBM), where hyperedges of varying sizes coexist. This setting captures higher-order and multi-view interactions and raises a fundamental question: can multiple uniform hypergraph layers below the detection threshold be combined to enable weak recovery? We answer this question by establishing a Kesten--Stigum-type bound for weak recovery in a general class of non-uniform HSBMs with rr blocks, generated according to multiple symmetric probability tensors. In the case r=2r=2, we show that weak recovery is possible whenever the sum of the signal-to-noise ratios across all uniform hypergraph layers exceeds one, thereby confirming the positive part of a conjecture in (Chodrow et al., 2023). Moreover, we provide a polynomial-time spectral algorithm that achieves this threshold via an optimally weighted non-backtracking operator. For the unweighted non-backtracking matrix, our spectral method attains a different algorithmic threshold, also conjectured in (Chodrow et al., 2023). Our approach develops a spectral theory for weighted non-backtracking operators on non-uniform hypergraphs, including a precise characterization of outlier eigenvalues and eigenvector overlaps. We introduce a novel Ihara--Bass formula tailored to weighted non-uniform hypergraphs, which yields an efficient low-dimensional representation and leads to a provable spectral reconstruction algorithm. Taken together, these results provide a principled and computationally efficient approach to clustering in non-uniform hypergraphs, and highlight the role of optimal weighting in aggregating heterogeneous higher-order interactions.

Explore similar work

CardsList
Jun 1, 2026cs.IT

Query-Limited Community Recovery in Stochastic Block Models

We study exact community recovery in the two-community stochastic block model on nn vertices under limited and noisy access to network data. The learner may query a noisy neighborhood oracle that reveals each true neighbor of a queried vertex independently with fixed probability and never returns non-neighbors, subject to a finite query budget. We consider both oracle-only access and a combined model where the learner also observes a single subsampled copy of the underlying graph. For oracle-only access, balanced uniform querying gives a sharp non-adaptive benchmark: when each vertex is queried the same integer number of times, the observations reduce to an SBM with attenuated edge probabilities and the Abbe-Bandeira-Hall exact-recovery threshold applies. We show that this benchmark is not adaptively optimal: a two-stage adaptive strategy succeeds with n+o(n)n+o(n) queries in a regime where balanced uniform querying requires mnm n queries for some m>1m>1. With an additional subsampled graph, we prove a sublinear-query adaptivity gap: balanced data-independent uniform querying with a sublinear budget does not improve over the subsampled graph alone, whereas adaptive querying can target a small set of uncertain vertices and achieve exact recovery. Thus adaptive data acquisition can strictly improve the information-theoretic limits of exact recovery.
Sabyasachi Basu, Manuj Mukherjee, Lutz Oettershagen +1
SubgraphsInformation-Theoretic Limits
AskPDF
Feb 19, 2026cs.SI

Simplify to Amplify: Achieving Information-Theoretic Bounds with Fewer Steps in Spectral Community Detection

We propose a streamlined spectral algorithm for community detection in the two-community stochastic block model (SBM) under constant edge density assumptions. By reducing algorithmic complexity through the elimination of non-essential preprocessing steps, our method directly leverages the spectral properties of the adjacency matrix. We demonstrate that our algorithm exploits specific characteristics of the second eigenvector to achieve improved error bounds that approach information-theoretic limits, representing a significant improvement over existing methods. Theoretical analysis establishes that our error rates are tighter than previously reported bounds in the literature. Comprehensive experimental validation confirms our theoretical findings and demonstrates the practical effectiveness of the simplified approach. Our results suggest that algorithmic simplification, rather than increasing complexity, can lead to both computational efficiency and enhanced performance in spectral community detection.
Sie Hendrata Dharmawan, Peter Chin
Spectral AlgorithmsSimplificationInformation-Theoretic Limits
AskPDF
Jun 12, 2026math.ST

Recovery thresholds for hidden weighted sparse graphs

Recovering structural information from noisy high-dimensional data is a fundamental task in statistical inference. We investigate the recovery thresholds for a graph hidden in a randomly weighted complete graph. Specifically, an unknown graph H∗∈HnH^* \in H_n is chosen uniformly at random, and hidden in a complete graph of nn vertices as follows: the weight of an edge e∈He \in H is distributed independently according to PnP_n; otherwise the weight is distributed independently according to QnQ_n. The goal is to recover almost all of HH from these edge weights. Assuming a local Lipschitzness of the Rényi divergence between distributions PnP_n and QnQ_n, and a mild density condition for the graphs HnH_n, we give a unified characterization of the information-theoretic limit for recovering almost all of HH (also known as almost exact recovery). Our characterization connects the KL divergence between PnP_n and QnQ_n to the logarithm of the first moment threshold of HH in the Erdős-Rényi random graph model G(n,p)G(n,p). Our lower bound also extends to the task of partial recovery, in which only a constant λλ-fraction of HH needs to be recovered. Last but not least, for certain Bernoulli and Exponential regimes, and for Gaussian distributions, we are able to show an All-or-Nothing (AoN) threshold phenomenon at the exponential scale.
Zhe Hou, Jingcheng Liu
Exponential Random Graph ModelsInformation-Theoretic LimitsKullback-Leibler Divergence
AskPDF