TY - GEN
T1 - Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares
AU - Kim, Chiheon
AU - Bandeira, Afonso S.
AU - Goemans, Michel X.
N1 - Funding Information:
˚ Part of this work was done while A. S. Bandeira was with the Mathematics Department at MIT and supported by NSF Grant DMS-1317308. : PartiallysupportedbyONRgrantsN00014-14-1-0072andN00014-17-1-2177.
PY - 2017/9/1
Y1 - 2017/9/1
N2 - We study the problem of community detection in hypergraphs under a stochastic block model. Similarly to how the stochastic block model in graphs suggests studying spiked random matrices, our model motivates investigating statistical and computational limits of exact recovery in certain spiked tensor models. In contrast with the matrix case, the spiked model naturally arising from community detection in hypergraphs is different from the one arising in the so-called tensor Principal Component Analysis model. We investigate the effectiveness of algorithms in the Sum-of-Squares hierarchy on these models. Interestingly, our results suggest that these two apparently similar models might exhibit very different computational to statistical gaps.
AB - We study the problem of community detection in hypergraphs under a stochastic block model. Similarly to how the stochastic block model in graphs suggests studying spiked random matrices, our model motivates investigating statistical and computational limits of exact recovery in certain spiked tensor models. In contrast with the matrix case, the spiked model naturally arising from community detection in hypergraphs is different from the one arising in the so-called tensor Principal Component Analysis model. We investigate the effectiveness of algorithms in the Sum-of-Squares hierarchy on these models. Interestingly, our results suggest that these two apparently similar models might exhibit very different computational to statistical gaps.
UR - http://www.scopus.com/inward/record.url?scp=85031665960&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85031665960&partnerID=8YFLogxK
U2 - 10.1109/SAMPTA.2017.8024470
DO - 10.1109/SAMPTA.2017.8024470
M3 - Conference contribution
AN - SCOPUS:85031665960
T3 - 2017 12th International Conference on Sampling Theory and Applications, SampTA 2017
SP - 124
EP - 128
BT - 2017 12th International Conference on Sampling Theory and Applications, SampTA 2017
A2 - Anbarjafari, Gholamreza
A2 - Kivinukk, Andi
A2 - Tamberg, Gert
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 12th International Conference on Sampling Theory and Applications, SampTA 2017
Y2 - 3 July 2017 through 7 July 2017
ER -