Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix

Julia Gaudio, Nirmit Joshi
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:469-510, 2023.

Abstract

Community detection is a fundamental problem in network science. In this paper, we consider community detection in hypergraphs drawn from the \emph{hypergraph stochastic block model} (HSBM), with a focus on exact community recovery. We study the performance of polynomial-time algorithms which operate on the \emph{similarity matrix} $W$, where $W_{ij}$ reports the number of hyperedges containing both $i$ and $j$. Under this information model, while the precise information-theoretic limit is unknown, Kim, Bandeira, and Goemans derived a sharp threshold up to which the natural min-bisection estimator on $W$ succeeds. As min-bisection is NP-hard in the worst case, they additionally proposed a semidefinite programming (SDP) relaxation and conjectured that it achieves the same recovery threshold as the min-bisection algorithm. In this paper, we confirm this conjecture. We also design a simple and highly efficient spectral algorithm with nearly linear runtime and show that it achieves the min-bisection threshold. Moreover, the spectral algorithm also succeeds in denser regimes and is considerably more efficient than previous approaches, establishing it as the method of choice. Our analysis of the spectral algorithm crucially relies on strong \emph{entrywise} bounds on the eigenvectors of $W$. Our bounds are inspired by the work of Abbe, Fan, Wang, and Zhong, who developed entrywise bounds for eigenvectors of symmetric matrices with independent entries. Despite the complex dependency structure in similarity matrices, we prove similar entrywise guarantees.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-gaudio23a, title = {Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix}, author = {Gaudio, Julia and Joshi, Nirmit}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {469--510}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/gaudio23a/gaudio23a.pdf}, url = {https://proceedings.mlr.press/v195/gaudio23a.html}, abstract = { Community detection is a fundamental problem in network science. In this paper, we consider community detection in hypergraphs drawn from the \emph{hypergraph stochastic block model} (HSBM), with a focus on exact community recovery. We study the performance of polynomial-time algorithms which operate on the \emph{similarity matrix} $W$, where $W_{ij}$ reports the number of hyperedges containing both $i$ and $j$. Under this information model, while the precise information-theoretic limit is unknown, Kim, Bandeira, and Goemans derived a sharp threshold up to which the natural min-bisection estimator on $W$ succeeds. As min-bisection is NP-hard in the worst case, they additionally proposed a semidefinite programming (SDP) relaxation and conjectured that it achieves the same recovery threshold as the min-bisection algorithm. In this paper, we confirm this conjecture. We also design a simple and highly efficient spectral algorithm with nearly linear runtime and show that it achieves the min-bisection threshold. Moreover, the spectral algorithm also succeeds in denser regimes and is considerably more efficient than previous approaches, establishing it as the method of choice. Our analysis of the spectral algorithm crucially relies on strong \emph{entrywise} bounds on the eigenvectors of $W$. Our bounds are inspired by the work of Abbe, Fan, Wang, and Zhong, who developed entrywise bounds for eigenvectors of symmetric matrices with independent entries. Despite the complex dependency structure in similarity matrices, we prove similar entrywise guarantees.} }
Endnote
%0 Conference Paper %T Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix %A Julia Gaudio %A Nirmit Joshi %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-gaudio23a %I PMLR %P 469--510 %U https://proceedings.mlr.press/v195/gaudio23a.html %V 195 %X Community detection is a fundamental problem in network science. In this paper, we consider community detection in hypergraphs drawn from the \emph{hypergraph stochastic block model} (HSBM), with a focus on exact community recovery. We study the performance of polynomial-time algorithms which operate on the \emph{similarity matrix} $W$, where $W_{ij}$ reports the number of hyperedges containing both $i$ and $j$. Under this information model, while the precise information-theoretic limit is unknown, Kim, Bandeira, and Goemans derived a sharp threshold up to which the natural min-bisection estimator on $W$ succeeds. As min-bisection is NP-hard in the worst case, they additionally proposed a semidefinite programming (SDP) relaxation and conjectured that it achieves the same recovery threshold as the min-bisection algorithm. In this paper, we confirm this conjecture. We also design a simple and highly efficient spectral algorithm with nearly linear runtime and show that it achieves the min-bisection threshold. Moreover, the spectral algorithm also succeeds in denser regimes and is considerably more efficient than previous approaches, establishing it as the method of choice. Our analysis of the spectral algorithm crucially relies on strong \emph{entrywise} bounds on the eigenvectors of $W$. Our bounds are inspired by the work of Abbe, Fan, Wang, and Zhong, who developed entrywise bounds for eigenvectors of symmetric matrices with independent entries. Despite the complex dependency structure in similarity matrices, we prove similar entrywise guarantees.
APA
Gaudio, J. & Joshi, N.. (2023). Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:469-510 Available from https://proceedings.mlr.press/v195/gaudio23a.html.

Related Material