Community Detection in Hypergraphs: Optimal Statistical Limit and Efficient Algorithms
Community Detection in Hypergraphs: Optimal Statistical Limit and Efficient Algorithms
复制标题
超图中的社区检测：最优统计极限和高效算法
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
I
中科院分区：
文献类型：
--
作者：
Eli Chien;Chung;I
本文研究超图中的社区发现问题。将随机块模型（SBM）自然地从图扩展到d-一致超图，在一个生成超图模型（d-hSBM）下，刻画了渐近极大极小误分类率的基本极限.为了证明的可扩展性，我们提出了一个两步多项式时间算法，可证明达到的基本限制在稀疏超图制度。为了证明最优性，极小极大风险的下限是通过找到一个更小的参数空间，其中包含最主要的错误事件，灵感来自于分析的可扩展性部分。结果表明，当节点数趋于无穷大时，极小极大风险指数快速衰减到零，而比率函数是几个发散项的加权组合，每个发散项都是两个伯努利分布之间1/2阶的雷尼发散。在速率函数的表征所涉及的伯努利分布是那些管理在d-hSBM中的超边的随机实例化。实验结果的合成和真实世界的数据验证了我们的理论发现。
In this paper, community detection in hypergraphs is explored. Under a generative hypergraph model called “d-wise hypergraph stochastic block model” (d-hSBM) which naturally extends the Stochastic Block Model (SBM) from graphs to d-uniform hypergraphs, the fundamental limit on the asymptotic minimax misclassified ratio is characterized. For proving the achievability, we propose a two-step polynomial time algorithm that provably achieves the fundamental limit in the sparse hypergraph regime. For proving the optimality, the lower bound of the minimax risk is set by finding a smaller parameter space which contains the most dominant error events, inspired by the analysis in the achievability part. It turns out that the minimax risk decays exponentially fast to zero as the number of nodes tends to infinity, and the rate function is a weighted combination of several divergence terms, each of which is the Rényi divergence of order 1/2 between two Bernoulli distributions. The Bernoulli distributions involved in the characterization of the rate function are those governing the random instantiation of hyperedges in d-hSBM. Experimental results on both synthetic and real-world data validate our theoretical finding.