arxiv: 2604.20907 · v1 · submitted 2026-04-21 · 📊 stat.ML · cs.LG· math.CO· math.PR· math.ST· stat.TH

Recognition: unknown

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

Ludovic Stephan, Manuel Fernandez V, Yizhe Zhu

Authors on Pith no claims yet

Pith reviewed 2026-05-10 00:59 UTC · model grok-4.3

classification 📊 stat.ML cs.LGmath.COmath.PRmath.STstat.TH

keywords non-uniform hypergraph stochastic block modelweak recoveryKesten-Stigum boundnon-backtracking operatorcommunity detectionspectral algorithmmulti-layer hypergraphs

0 comments

The pith

Weak recovery in the non-uniform hypergraph stochastic block model is possible whenever the sum of per-layer signal-to-noise ratios exceeds one for two communities.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies community detection when hyperedges of several different sizes coexist in the same network, each layer generated by its own symmetric probability tensor. It proves that even if every individual uniform layer lies below its own detection threshold, the layers can be combined so that weak recovery succeeds as soon as their signal-to-noise ratios add to more than one. This holds for the two-community case and is realized by a polynomial-time spectral algorithm that uses an optimally weighted non-backtracking operator together with a new Ihara-Bass formula adapted to weighted non-uniform hypergraphs. The result confirms the positive half of a conjecture from earlier work and shows that optimal weighting is required to reach the information-theoretic limit.

Core claim

In the general class of non-uniform hypergraph stochastic block models with r blocks, weak recovery is achievable above the Kesten-Stigum bound given by the sum of the signal-to-noise ratios across all uniform layers when r equals two. The bound is attained by a spectral algorithm that employs an optimally weighted non-backtracking operator whose outlier eigenvalues and eigenvector overlaps are characterized exactly via a tailored Ihara-Bass formula for weighted non-uniform hypergraphs.

What carries the argument

The optimally weighted non-backtracking operator on non-uniform hypergraphs, whose spectrum is reduced to a low-dimensional representation by a novel Ihara-Bass formula that aggregates contributions from all edge sizes.

If this is right

The unweighted non-backtracking matrix attains a strictly weaker algorithmic threshold than the optimally weighted version.
A polynomial-time algorithm matches the information-theoretic limit for weak recovery when r equals two.
The same spectral theory applies to any finite collection of symmetric probability tensors defining the layers.
Weak recovery is possible in the regime where every individual layer is below its own threshold but the aggregate SNR exceeds one.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Optimal weighting appears necessary to extract all available signal from heterogeneous hyperedge sizes.
The same aggregation principle may extend to other multi-view or multi-order network models outside the stochastic block framework.
Empirical tests on real hypergraphs that contain edges of several sizes would reveal whether the theoretical gain from weighting translates to practice.

Load-bearing premise

Hyperedges of each size are generated independently according to fixed symmetric probability tensors that encode the community structure.

What would settle it

Generate a two-community non-uniform HSBM instance whose summed SNR equals 1.1 and check whether the proposed spectral algorithm produces a community estimate whose overlap with the true partition remains bounded away from zero; failure to do so would falsify the achievability claim.

Figures

Figures reproduced from arXiv: 2604.20907 by Ludovic Stephan, Manuel Fernandez V, Yizhe Zhu.

read the original 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 $r$ blocks, generated according to multiple symmetric probability tensors. In the case $r=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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

They prove the positive half of the Chodrow conjecture for non-uniform HSBM by showing weak recovery when the sum of per-layer SNRs exceeds 1, using a new weighted non-backtracking operator and a matching Ihara-Bass formula.

read the letter

The core advance is the confirmation that, for two communities, weak recovery succeeds in the non-uniform HSBM once the total signal-to-noise ratio across all hyperedge sizes passes one. They also supply a polynomial-time spectral algorithm that attains this bound with an optimally weighted non-backtracking operator, while the unweighted version lands at a different threshold that was previously conjectured as well.

Referee Report

0 major / 2 minor

Summary. The manuscript studies community detection in the non-uniform hypergraph stochastic block model (HSBM), where hyperedges of different sizes coexist. It establishes a Kesten-Stigum-type bound for weak recovery in a general class of such models generated by multiple symmetric probability tensors with r blocks. For the case r=2, it proves that weak recovery is possible whenever the sum of the per-layer signal-to-noise ratios exceeds one, confirming the positive part of a conjecture from Chodrow et al. (2023). The paper also supplies a polynomial-time spectral algorithm that attains this threshold using an optimally weighted non-backtracking operator, derives a new Ihara-Bass formula for weighted non-uniform hypergraphs, and characterizes outlier eigenvalues and eigenvector overlaps.

Significance. If the derivations hold, the work is significant for resolving the positive direction of the Chodrow et al. (2023) conjecture on combining sub-threshold uniform layers in non-uniform HSBMs. The new spectral theory, including the tailored Ihara-Bass formula and precise outlier characterization for weighted non-backtracking operators, supplies a general framework for analyzing heterogeneous higher-order interactions. The algorithmic result demonstrates that optimal weighting enables efficient achievement of the information-theoretic threshold, which is a concrete advance for multi-view and non-uniform hypergraph clustering with potential impact on network science applications.

minor comments (2)

[Abstract] Abstract: the claim that the unweighted non-backtracking operator attains 'a different algorithmic threshold, also conjectured in (Chodrow et al., 2023)' would be clearer if the explicit form of that threshold (or its relation to the sum-of-SNRs bound) were stated briefly.
[Introduction] The general-r case is introduced but the detailed threshold and algorithm are developed only for r=2; a short remark on why the sum-of-SNRs form does not extend immediately would help readers assess the scope.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the positive assessment, including recognition of the significance of confirming the positive direction of the Chodrow et al. (2023) conjecture and the development of the weighted non-backtracking spectral theory. The recommendation for minor revision is appreciated. As the report contains no listed major comments, we have no specific points requiring point-by-point rebuttal at this stage. We will incorporate appropriate minor revisions to improve clarity, notation, and presentation in the revised version.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper derives the Kesten-Stigum threshold for r=2 as the sum of per-layer SNRs exceeding 1 via a new Ihara-Bass formula and outlier-eigenvalue analysis for weighted non-backtracking operators on non-uniform hypergraphs. This spectral characterization is developed directly from the model definition using symmetric probability tensors, without reducing any prediction to a fitted parameter, self-referential definition, or load-bearing self-citation. The citation to Chodrow et al. (2023) is used only to identify the conjecture being confirmed, not to justify the derivation itself. The polynomial-time algorithm follows from the same independent operator analysis, rendering the central claims self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the definition of the non-uniform HSBM and standard tools from spectral graph theory and random matrix analysis, without new free parameters or invented entities.

axioms (2)

standard math Standard results from linear algebra, probability, and random matrix theory apply to the analysis of the weighted non-backtracking operator and its eigenvalues.
Invoked throughout the development of the spectral theory and Ihara-Bass formula.
domain assumption The hypergraph is generated according to the non-uniform HSBM with multiple symmetric probability tensors.
This is the model definition under which the Kesten-Stigum-type bound and algorithm are derived.

pith-pipeline@v0.9.0 · 5598 in / 1431 out tokens · 73301 ms · 2026-05-10T00:59:21.437841+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

16 extracted references · 13 canonical work pages · 1 internal anchor

[1]

Fundamental limits of community detection in contextual multi-layer stochastic block models

[GHL26] Shuyang Gong, Dong Huang, and Zhangsong Li. Fundamental limits of commu- nity detection in contextual multi-layer stochastic block models.arXiv preprint arXiv:2602.08173,

work page arXiv
[2]

Exact community recovery under side information: Optimality of spectral algorithms.arXiv preprint arXiv:2406.13075,

[GJ24] Julia Gaudio and Nirmit Joshi. Exact community recovery under side information: Optimality of spectral algorithms.arXiv preprint arXiv:2406.13075,

work page arXiv
[3]

Stochastic block model for hypergraphs: Statistical limits and a semidefinite programming approach.arXiv preprint arXiv:1807.02884,

[KBG18] Chiheon Kim, Afonso S Bandeira, and Michel X Goemans. Stochastic block model for hypergraphs: Statistical limits and a semidefinite programming approach.arXiv preprint arXiv:1807.02884,

work page arXiv
[4]

Community detection for hypergraph net- works via regularized tensor power iteration.arXiv preprint arXiv:1909.06503,

[KSX19] Zheng Tracy Ke, Feng Shi, and Dong Xia. Community detection for hypergraph net- works via regularized tensor power iteration.arXiv preprint arXiv:1909.06503,

work page arXiv 1909
[5]

Low coordinate degree algorithms ii: Categorical signals and gener- alized stochastic block models.arXiv preprint arXiv:2412.21155,

[Kun24] Dmitriy Kunisky. Low coordinate degree algorithms ii: Categorical signals and gener- alized stochastic block models.arXiv preprint arXiv:2412.21155,

work page arXiv
[6]

Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions.Journal of Statistical Mechanics: Theory and Experiment, 2025(9):093302,

[KZ25] Christian Keup and Lenka Zdeborov´ a. Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions.Journal of Statistical Mechanics: Theory and Experiment, 2025(9):093302,

2025
[7]

The algorithmic phase transition in correlated spiked models.arXiv preprint arXiv:2511.06040,

[Li25] Zhangsong Li. The algorithmic phase transition in symmetric correlated spiked wigner model.arXiv preprint arXiv:2511.06040,

work page arXiv
[8]

Higher order trade-offs in hypergraph community detection

[LSP26] Jiaze Li, Michael T Schaub, and Leto Peel. Higher order trade-offs in hypergraph community detection.arXiv preprint arXiv:2601.10502,

work page internal anchor Pith review Pith/arXiv arXiv
[9]

Morgan and C

[MG26] Alexander Morgan and Chenghao Guo. Achievability of heterogeneous hypergraph recovery from its graph projection.arXiv preprint arXiv:2603.01268,

work page arXiv
[10]

Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs

[MSS25] Elchanan Mossel, Allan Sly, and Youngtak Sohn. Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 2062–2073,

2062
[11]

Mergny and L

[MZ25] Pierre Mergny and Lenka Zdeborov´ a. Spectral thresholds in correlated spiked models and fundamental limits of partial least squares.arXiv preprint arXiv:2510.17561,

work page arXiv
[12]

Message-passing on hy- pergraphs: detectability, phase transitions and higher-order information.Journal of Statistical Mechanics: Theory and Experiment, 2024(4):043403,

[RLDB24] Nicol` o Ruggeri, Alessandro Lonardi, and Caterina De Bacco. Message-passing on hy- pergraphs: detectability, phase transitions and higher-order information.Journal of Statistical Mechanics: Theory and Experiment, 2024(4):043403,

2024
[13]

Stephan and Y

[SZ24a] Ludovic Stephan and Yizhe Zhu. Community detection with the bethe-hessian.arXiv preprint arXiv:2411.02835,

work page arXiv
[14]

Quartic quantum speedups for com- munity detection.arXiv preprint arXiv:2510.08494,

[SZ25] Alexander Schmidhuber and Alexander Zlokapa. Quartic quantum speedups for com- munity detection.arXiv preprint arXiv:2510.08494,

work page arXiv
[15]

Välimaa and L

[VL25] Ian V¨ alimaa and Lasse Leskel¨ a. Consistent spectral clustering in sparse tensor block models.arXiv preprint arXiv:2501.13820,

work page arXiv
[16]

Strong consistency and optimality of spectral clustering in symmetric bi- nary non-uniform hypergraph stochastic block model.arXiv preprint arXiv:2306.06845,

59 [Wan23] Haixiao Wang. Strong consistency and optimality of spectral clustering in symmetric bi- nary non-uniform hypergraph stochastic block model.arXiv preprint arXiv:2306.06845,

work page arXiv