Optimal and exact recovery on general non-uniform Hypergraph Stochastic Block Model
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916372097794048 |
|---|---|
| author | Dumitriu, Ioana Wang, Haixiao |
| author_facet | Dumitriu, Ioana Wang, Haixiao |
| contents | Consider the community detection problem in random hypergraphs under the non-uniform hypergraph stochastic block model (HSBM), where each hyperedge appears independently with some given probability depending only on the labels of its vertices. We establish, for the first time in the literature, a sharp threshold for exact recovery under this non-uniform case, subject to minor constraints; in particular, we consider the model with multiple communities. One crucial point here is that by aggregating information from all the uniform layers, we may obtain exact recovery even in cases when this may appear impossible if each layer were considered alone. Besides that, we prove a wide-ranging, information-theoretic lower bound on the number of misclassified vertices \emph{for any algorithm}, depending on a \emph{generalized Chernoff-Hellinger} divergence involving model parameters. We provide two efficient algorithms which successfully achieve exact recovery when above the threshold, and attain the lowest possible mismatch ratio when the exact recovery is impossible, proved to be optimal. The theoretical analysis of our algorithms relies on the concentration and regularization of the adjacency matrix for non-uniform random hypergraphs, which could be of independent interest. We also address some open problems regarding parameter knowledge and estimation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_13139 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Optimal and exact recovery on general non-uniform Hypergraph Stochastic Block Model Dumitriu, Ioana Wang, Haixiao Statistics Theory Probability Machine Learning Consider the community detection problem in random hypergraphs under the non-uniform hypergraph stochastic block model (HSBM), where each hyperedge appears independently with some given probability depending only on the labels of its vertices. We establish, for the first time in the literature, a sharp threshold for exact recovery under this non-uniform case, subject to minor constraints; in particular, we consider the model with multiple communities. One crucial point here is that by aggregating information from all the uniform layers, we may obtain exact recovery even in cases when this may appear impossible if each layer were considered alone. Besides that, we prove a wide-ranging, information-theoretic lower bound on the number of misclassified vertices \emph{for any algorithm}, depending on a \emph{generalized Chernoff-Hellinger} divergence involving model parameters. We provide two efficient algorithms which successfully achieve exact recovery when above the threshold, and attain the lowest possible mismatch ratio when the exact recovery is impossible, proved to be optimal. The theoretical analysis of our algorithms relies on the concentration and regularization of the adjacency matrix for non-uniform random hypergraphs, which could be of independent interest. We also address some open problems regarding parameter knowledge and estimation. |
| title | Optimal and exact recovery on general non-uniform Hypergraph Stochastic Block Model |
| topic | Statistics Theory Probability Machine Learning |
| url | https://arxiv.org/abs/2304.13139 |