Sparse Hypergraph Community Detection Thresholds in Stochastic Block Model
Date
2022
Authors
Zhang, E.
Suter, D.
Truong, G.
Gilani, S.Z.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Advances in Neural Information Processing Systems, 2022, vol.35, pp.34012-34023
Statement of Responsibility
Erchuan Zhang, David Suter, Giang Truong, Syed Zulqarnain Gilani
Conference Name
Conference on Neural Information Processing Systems (NIPS) (28 Nov 2022 - 9 Dec 2022 : New Orleans)
Abstract
Community detection in random graphs or hypergraphs is an interesting fundamental problem in statistics, machine learning and computer vision. When the hypergraphs are generated by a stochastic block model, the existence of a sharp threshold on the model parameters for community detection was conjectured by Angelini et al. 2015. In this paper, we confirm the positive part of the conjecture, the possibility of non-trivial reconstruction above the threshold, for the case of two blocks. We do so by comparing the hypergraph stochastic block model with its Erdös-Rényi counterpart. We also obtain estimates for the parameters of the hypergraph stochastic block model. The methods developed in this paper are generalised from the study of sparse random graphs by Mossel et al. 2015 and are motivated by the work of Yuan et al. 2022. Furthermore, we present some discussion on the negative part of the conjecture, i.e., non-reconstruction of community structures. © 2022 Neural information processing systems foundation.