突破非均匀超图社区检测的理论极限,实现最优聚合。
Achieving the Kesten-Stigum bound in the non-uniform hypergraph stochastic block model

- 提出加权非回溯算子,统一处理多阶超边
- 证明信号噪声比总和超1即可弱恢复社区
- 适合研究高阶网络聚类与算法优化者
研究非均匀超图随机块模型(HSBM)中的社区检测问题,该模型包含不同大小的超边,能刻画高阶与多视角交互。核心问题是:多个低于检测阈值的均匀超图层能否组合实现弱恢复?本文在含 $r$ 个块、由多重对称概率张量生成的一般非均匀 HSBM 中,建立了类 Kesten-Stigum 的弱恢复界。当 $r=2$ 时,证明只要所有均匀超图层的信号-噪声比之和大于1,弱恢复即可实现,验证了 Chodrow 等人(2023)的猜想。同时提出一种多项式时间谱算法,通过最优加权非回溯算子达到此阈值。对于未加权的非回溯矩阵,该方法也实现了另一算法阈值,同样符合原猜想。研究发展了非均匀超图加权非回溯算子的谱理论,精确刻画了异常特征值与特征向量重叠。引入专为加权非均匀超图设计的新 Ihara-Bass 公式,实现高效低维表示,并导出可证明的谱重构算法。结果提供了一种原理清晰且计算高效的非均匀超图聚类方法,凸显最优加权在聚合异质高阶交互中的关键作用。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。