Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares

Chiheon Kim; Afonso S. Bandeira; Michel X. Goemans

doi:10.1109/SAMPTA.2017.8024470

Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares

Chiheon Kim, Afonso S. Bandeira, Michel X. Goemans

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English (US)
Title of host publication	2017 12th International Conference on Sampling Theory and Applications, SampTA 2017
Editors	Gholamreza Anbarjafari, Andi Kivinukk, Gert Tamberg
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	124-128
Number of pages	5
ISBN (Electronic)	9781538615652
DOIs	https://doi.org/10.1109/SAMPTA.2017.8024470
State	Published - Sep 1 2017
Event	12th International Conference on Sampling Theory and Applications, SampTA 2017 - Tallinn, Estonia Duration: Jul 3 2017 → Jul 7 2017

Publication series

Name	2017 12th International Conference on Sampling Theory and Applications, SampTA 2017

Other

Other	12th International Conference on Sampling Theory and Applications, SampTA 2017
Country	Estonia
City	Tallinn
Period	7/3/17 → 7/7/17

ASJC Scopus subject areas

Signal Processing
Statistics, Probability and Uncertainty
Analysis
Statistics and Probability
Applied Mathematics

Access to Document

10.1109/SAMPTA.2017.8024470

Fingerprint Dive into the research topics of 'Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares'. Together they form a unique fingerprint.

Cite this

Kim, C., Bandeira, A. S., & Goemans, M. X. (2017). Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares. In G. Anbarjafari, A. Kivinukk, & G. Tamberg (Eds.), 2017 12th International Conference on Sampling Theory and Applications, SampTA 2017 (pp. 124-128). [8024470] (2017 12th International Conference on Sampling Theory and Applications, SampTA 2017). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SAMPTA.2017.8024470

Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares. / Kim, Chiheon; Bandeira, Afonso S.; Goemans, Michel X.

2017 12th International Conference on Sampling Theory and Applications, SampTA 2017. ed. / Gholamreza Anbarjafari; Andi Kivinukk; Gert Tamberg. Institute of Electrical and Electronics Engineers Inc., 2017. p. 124-128 8024470 (2017 12th International Conference on Sampling Theory and Applications, SampTA 2017).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kim, C, Bandeira, AS & Goemans, MX 2017, Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares. in G Anbarjafari, A Kivinukk & G Tamberg (eds), 2017 12th International Conference on Sampling Theory and Applications, SampTA 2017., 8024470, 2017 12th International Conference on Sampling Theory and Applications, SampTA 2017, Institute of Electrical and Electronics Engineers Inc., pp. 124-128, 12th International Conference on Sampling Theory and Applications, SampTA 2017, Tallinn, Estonia, 7/3/17. https://doi.org/10.1109/SAMPTA.2017.8024470

Kim C, Bandeira AS, Goemans MX. Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares. In Anbarjafari G, Kivinukk A, Tamberg G, editors, 2017 12th International Conference on Sampling Theory and Applications, SampTA 2017. Institute of Electrical and Electronics Engineers Inc. 2017. p. 124-128. 8024470. (2017 12th International Conference on Sampling Theory and Applications, SampTA 2017). https://doi.org/10.1109/SAMPTA.2017.8024470

Kim, Chiheon ; Bandeira, Afonso S. ; Goemans, Michel X. / Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares. 2017 12th International Conference on Sampling Theory and Applications, SampTA 2017. editor / Gholamreza Anbarjafari ; Andi Kivinukk ; Gert Tamberg. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 124-128 (2017 12th International Conference on Sampling Theory and Applications, SampTA 2017).

@inproceedings{dd643921b9b04665bfbd09a2cddfd1f2,

title = "Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares",

abstract = "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.",

author = "Chiheon Kim and Bandeira, {Afonso S.} and Goemans, {Michel X.}",

year = "2017",

month = sep,

day = "1",

doi = "10.1109/SAMPTA.2017.8024470",

language = "English (US)",

series = "2017 12th International Conference on Sampling Theory and Applications, SampTA 2017",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "124--128",

editor = "Gholamreza Anbarjafari and Andi Kivinukk and Gert Tamberg",

booktitle = "2017 12th International Conference on Sampling Theory and Applications, SampTA 2017",

note = "12th International Conference on Sampling Theory and Applications, SampTA 2017 ; Conference date: 03-07-2017 Through 07-07-2017",

}

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.

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 -