On the fundamental statistical limit of community detection in random hypergraphs
| Autor: | I-Hsiang Wang, Chung-Yi Lin, I Eli Chien |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Stochastic process
020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Function (mathematics) Minimax 01 natural sciences Upper and lower bounds Combinatorics 010201 computation theory & mathematics Stochastic block model 0202 electrical engineering electronic engineering information engineering Applied mathematics Divergence (statistics) Random variable Rate function Mathematics |
| Zdroj: | ISIT |
| DOI: | 10.1109/isit.2017.8006915 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|