Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares
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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/116076 https://orcid.org/0000-0002-3705-5318 https://orcid.org/0000-0002-7331-7557 https://orcid.org/0000-0002-0520-1165 |
| _version_ | 1811082110401773568 |
|---|---|
| author | Kim, Chiheon Sousa Bandeira, Afonso Jose Goemans, Michel X |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Kim, Chiheon Sousa Bandeira, Afonso Jose Goemans, Michel X |
| author_sort | Kim, Chiheon |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T11:57:44Z |
| format | Article |
| id | mit-1721.1/116076 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:57:44Z |
| publishDate | 2018 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1160762022-10-01T07:17:40Z Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares Kim, Chiheon Sousa Bandeira, Afonso Jose Goemans, Michel X Massachusetts Institute of Technology. Department of Mathematics Kim, Chiheon Sousa Bandeira, Afonso Jose Goemans, Michel X 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. 2018-06-05T12:08:06Z 2018-06-05T12:08:06Z 2017-09 2018-05-21T19:20:50Z Article http://purl.org/eprint/type/ConferencePaper 978-1-5386-1565-2 http://hdl.handle.net/1721.1/116076 Kim, Chiheon, Afonso S. Bandeira, and Michel X. Goemans. “Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares.” 2017 International Conference on Sampling Theory and Applications (SampTA) (July 2017). https://orcid.org/0000-0002-3705-5318 https://orcid.org/0000-0002-7331-7557 https://orcid.org/0000-0002-0520-1165 http://dx.doi.org/10.1109/SAMPTA.2017.8024470 2017 International Conference on Sampling Theory and Applications (SampTA) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Kim, Chiheon Sousa Bandeira, Afonso Jose Goemans, Michel X Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares |
| title | Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares |
| title_full | Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares |
| title_fullStr | Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares |
| title_full_unstemmed | Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares |
| title_short | Community detection in hypergraphs, spiked tensor models, and Sum-of-Squares |
| title_sort | community detection in hypergraphs spiked tensor models and sum of squares |
| url | http://hdl.handle.net/1721.1/116076 https://orcid.org/0000-0002-3705-5318 https://orcid.org/0000-0002-7331-7557 https://orcid.org/0000-0002-0520-1165 |
| work_keys_str_mv | AT kimchiheon communitydetectioninhypergraphsspikedtensormodelsandsumofsquares AT sousabandeiraafonsojose communitydetectioninhypergraphsspikedtensormodelsandsumofsquares AT goemansmichelx communitydetectioninhypergraphsspikedtensormodelsandsumofsquares |