License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2021.24
URN: urn:nbn:de:0030-drops-136692
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13669/
Coja-Oghlan, Amin ;
Hahn-Klimroth, Max ;
Loick, Philipp ;
Müller, Noela ;
Panagiotou, Konstantinos ;
Pasch, Matija
Inference and Mutual Information on Random Factor Graphs
Abstract
Random factor graphs provide a powerful framework for the study of inference problems such as decoding problems or the stochastic block model. Information-theoretically the key quantity of interest is the mutual information between the observed factor graph and the underlying ground truth around which the factor graph was created; in the stochastic block model, this would be the planted partition. The mutual information gauges whether and how well the ground truth can be inferred from the observable data. For a very general model of random factor graphs we verify a formula for the mutual information predicted by physics techniques. As an application we prove a conjecture about low-density generator matrix codes from [Montanari: IEEE Transactions on Information Theory 2005]. Further applications include phase transitions of the stochastic block model and the mixed k-spin model from physics.
BibTeX - Entry
@InProceedings{cojaoghlan_et_al:LIPIcs.STACS.2021.24,
author = {Coja-Oghlan, Amin and Hahn-Klimroth, Max and Loick, Philipp and M\"{u}ller, Noela and Panagiotou, Konstantinos and Pasch, Matija},
title = {{Inference and Mutual Information on Random Factor Graphs}},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages = {24:1--24:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-180-1},
ISSN = {1868-8969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13669},
URN = {urn:nbn:de:0030-drops-136692},
doi = {10.4230/LIPIcs.STACS.2021.24},
annote = {Keywords: Information theory, random factor graphs, inference problems, phase transitions}
}
Keywords: |
|
Information theory, random factor graphs, inference problems, phase transitions |
Collection: |
|
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) |
Issue Date: |
|
2021 |
Date of publication: |
|
10.03.2021 |