On the fundamental statistical limit of community detection in random hypergraphs
On the fundamental statistical limit of community detection in random hypergraphs
复制标题
随机超图中社区发现的基本统计极限
DOI：
10.1109/isit.2017.8006915
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
I
中科院分区：
文献类型：
--
作者：
Chung;Eli Chien;I
研究了随机超图中的社团发现问题。我们将随机块模型（SBM）从图扩展到具有d-一致超边的超图，我们称之为“d-超随机块模型”（d-hSBM），并考虑一个均匀且近似相等大小的K社区的情况.对于d = 3，我们充分刻画了极小极大风险在恢复底层社区时的指数衰减率，其中损失函数是真实社区分配与恢复社区分配之间的失配率。事实证明，速率函数是几个发散项的加权组合，每个发散项都是两个伯努利分布之间的1阶Renyi发散。在速率函数的表征所涉及的伯努利分布是那些管理在d-hSBM中的超边的随机实例化。下限是通过找到一个更小的参数空间来设置的，我们可以在这里分析风险，而上限是通过最大似然估计来实现的。技术上的贡献是表明，上限有相同的衰减率作为下限，这涉及到仔细界定的各种概率的错误。最后，我们将极大极小风险与贝叶斯框架下的恢复准则联系起来，并推导出精确恢复的阈值条件。
The problem of community detection in random hypergraphs is considered. We extend the Stochastic Block Model (SBM) from graphs to hypergraphs with d-uniform hyperedges, which we term “d-wise hyper stochastic block model” (d-hSBM) and consider a homogeneous and approximately equal-sized K community case. For d = 3, we fully characterize the exponentially decaying rate of the minimax risk in recovering the underlying communities, where the loss function is the mis-match ratio between the true community assignment and the recovered one. It turns out that the rate function is a weighted combination of several divergence terms, each of which is the Renyi divergence of order 1 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. The lower bound is set by finding a smaller parameter space where we can analyze the risk, while the upper bound is achieved with the Maximum Likelihood estimator. The technical contribution is to show that upper bound has the same decaying rate as the lower bound, which involves careful bounding of the various probabilities of errors. Finally, we relate the minimax risk to the recovery criterion under the Bayesian framework and derive a threshold condition for exact recovery.