Spectral Detection on Sparse Hypergraphs

Maria Chiara Angelini 1 Francesco Caltagirone 2 Florent Krzakala 2, 3 Lenka Zdeborová 4
1 Dipartimento di Fisica, Sapienza Università di Roma
2 LPS - Laboratoire de Physique Statistique de l'ENS
3 Neuroépidémiologie [CHU Pitié-Salpêtrière]
4 IPHT - Institut de Physique Théorique - UMR CNRS 3681
Abstract : We consider the problem of the assignment of nodes into communities from a set of hyperedges, where every hyperedge is a noisy observation of the community assignment of the adjacent nodes. We focus in particular on the sparse regime where the number of edges is of the same order as the number of vertices. We propose a spectral method based on a generalization of the non-backtracking Hashimoto matrix into hypergraphs. We analyze its performance on a planted generative model and compare it with other spectral methods and with Bayesian belief propagation (which was conjectured to be asymptotically optimal for this model). We conclude that the proposed spectral method detects communities whenever belief propagation does, while having the important advantages to be simpler, entirely nonparametric, and to be able to learn the rule according to which the hyperedges were generated without prior information.
Document type :
Conference papers
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download
https://hal-cea.archives-ouvertes.fr/cea-01330412
Contributor : Emmanuelle de Laborderie <>
Submitted on : Friday, June 10, 2016 - 3:33:24 PM
Last modification on : Tuesday, May 14, 2019 - 11:05:04 AM

File

1507.04113v1.pdf
Files produced by the author(s)

Identifiers

Collections

CEA | CNRS | UPMC | ENS-PARIS | DSM-IPHT | CEA-UPSAY | PSL | UNIV-PARIS-SACLAY | LPS | CEA-DRF | SORBONNE-UNIVERSITE | UNIV-PARIS7 | USPC | SU-SCIENCES

Citation

Maria Chiara Angelini, Francesco Caltagirone, Florent Krzakala, Lenka Zdeborová. Spectral Detection on Sparse Hypergraphs. Allerton Conference 2015 : 53rd Annual Allerton Conference on Communication, Control, and Computing, Sep 2015, Monticello, United States. pp.66-73, ⟨10.1109/ALLERTON.2015.7446987⟩. ⟨cea-01330412⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

358

Files downloads

242

Contact

CCSD