Document Open Access Logo

Inference and Mutual Information on Random Factor Graphs

Authors Amin Coja-Oghlan, Max Hahn-Klimroth, Philipp Loick, Noela Müller, Konstantinos Panagiotou, Matija Pasch

PDF
Thumbnail PDF

File

LIPIcs.STACS.2021.24.pdf
  • Filesize: 0.71 MB
  • 15 pages

Document Identifiers

Author Details

Amin Coja-Oghlan
  • Mathematics Institute, Goethe Universität Frankfurt am Main, Germany
Max Hahn-Klimroth
  • Mathematics Institute, Goethe Universität Frankfurt am Main, Germany
Philipp Loick
  • Mathematics Institute, Goethe Universität Frankfurt am Main, Germany
Noela Müller
  • Mathematics Institute, University of Munich, Germany
Konstantinos Panagiotou
  • Mathematics Institute, University of Munich, Germany
Matija Pasch
  • Mathematics Institute, University of Munich, Germany

Funding

  • Coja-Oghlan, Amin: Supported by DFG CO 646/3.
  • Hahn-Klimroth, Max: Supported by Stiftung Polytechnische Gesellschaft and DFG FOR 2975.
  • Loick, Philipp: Supported by DFG CO 646/3.
  • Müller, Noela: Supported by the European Research Council, ERC Grant Agreement 772606–PTRCSP.
  • Panagiotou, Konstantinos: Supported by the European Research Council, ERC Grant Agreement 772606–PTRCSP.
  • Pasch, Matija: Supported by the European Research Council, ERC Grant Agreement 772606–PTRCSP.

Cite As Get BibTex

Amin Coja-Oghlan, Max Hahn-Klimroth, Philipp Loick, Noela Müller, Konstantinos Panagiotou, and Matija Pasch. Inference and Mutual Information on Random Factor Graphs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.STACS.2021.24

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Probabilistic inference problems
Keywords
  • Information theory
  • random factor graphs
  • inference problems
  • phase transitions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. E. Abbe and A. Montanari. Conditional random fields, planted constraint satisfaction and entropy concentration. Theory of Computing, 11:413-443, 2015. Google Scholar
  2. M. Aldridge, O. Johnson, and J. Scarlett. Group testing: an information theory perspective. Foundations and Trends in Communications and Information Theory, 2019. Google Scholar
  3. F. Altarelli, A. Braunstein, L. Dall’Asta, A. Lage-Castellanos, and R. Zecchina. Bayesian inference of epidemics on networks via belief propagation. Physical review letters, 112:118701, 2014. Google Scholar
  4. D. Amit, H. Gutfreund, and H. Sompolinsky. Storing infinite numbers of patterns in a spin-glass model of neural networks. Physical Review Letters, 55:1530, 1985. Google Scholar
  5. J. Banks, C. Moore, J. Neeman, and P. Netrapalli. Information-theoretic thresholds for community detection in sparse networks. Proc. 29th COLT, pages 383-416, 2016. Google Scholar
  6. V. Bapst, A. Coja-Oghlan, S. Hetterich, F. Rassmann, and D. Vilenchik. The condensation phase transition in random graph coloring. Communications in Mathematical Physics, 341:543-606, 2016. Google Scholar
  7. J. Barbier, C. Chan, and N. Macris. Mutual information for the stochastic block model by the adaptive interpolation method. Proc. IEEE International Symposium on Information Theory, pages 405-409, 2019. Google Scholar
  8. J. Barbier and N. Macris. The adaptive interpolation method for proving replica formulas. applications to the Curie–Weiss and Wigner spike models. Journal of Physics A: Mathematical and Theoretical, 52:294002, 2019. Google Scholar
  9. A. Coja-Oghlan, A. Ergür, P. Gao, S. Hetterich, and M. Rolvien. The rank of sparse random matrices. Proc. 31st SODA, pages 579-591, 2020. Google Scholar
  10. A. Coja-Oghlan, O. Gebhard, M. Hahn-Klimroth, and P. Loick. Optimal group testing. Proceedings of Machine Learning Research (COLT), 2020. Google Scholar
  11. A. Coja-Oghlan, F. Krzakala, W. Perkins, and L. Zdeborová. Information-theoretic thresholds from the cavity method. Advances in Mathematics, 333:694-795, 2018. Google Scholar
  12. A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Phys. Rev. E, 84:066106, 2011. Google Scholar
  13. M. Dia, N. Macris, F. Krzakala, T. Lesieur, and L. Zdeborová. Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula. Advances in Neural Information Processing Systems, pages 424-432, 2016. Google Scholar
  14. D. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52:1289-1306, 2006. Google Scholar
  15. D. Donoho, A. Javanmard, and A. Montanari. Information-theoretically optimal compressed sensing via spatial coupling and approximate message passing. IEEE Transactions on Information Theory, 59:7434-7464, 2013. Google Scholar
  16. A. Giurgiu, N. Macris, and R. Urbanke. Spatial coupling as a proof technique and three applications. IEEE Transactions on Information Theory, 62:5281-5295, 2016. Google Scholar
  17. D. Guo and C. Wang. Multiuser detection of sparsely spread cdma. IEEE journal on selected areas in communications, 26:421-431, 2008. Google Scholar
  18. S. Janson, T. Łuczak, and A. Rucinski. Random graphs. John Wiley & Sons, 45, 2011. Google Scholar
  19. F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborova. Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. National Academy of Sciences, 104:10318-10323, 2007. Google Scholar
  20. S. Kudekar, T. Richardson, and R. Urbanke. Spatially coupled ensembles universally achieve capacity under belief propagation. IEEE Transactions on Information Theory, 59:7761-7813, 2013. Google Scholar
  21. S. Kumar, A. Young, N. Macris, and H. Pfister. Threshold saturation for spatially coupled ldpc and ldgm codes on bms channels. IEEE Transactions on Information Theory, 60:7389-7415, 2014. Google Scholar
  22. M. Lelarge and L. Miolane. Fundamental limits of symmetric low-rank matrix estimation. Conference on Learning Theory (COLT), pages 1297-1301, 2017. Google Scholar
  23. M. Mézard. Mean-field message-passing equations in the Hopfield model and its generalizations. Physical Review E, 95:022117, 2017. Google Scholar
  24. M. Mézard and A. Montanari. Information, physics and computation. Oxford University Press, 2009. Google Scholar
  25. A. Montanari. Tight bounds for ldpc and ldgm codes under map decoding. IEEE Transactions on Information Theory, 51:3221-3246, 2005. Google Scholar
  26. C. Moore. The computer science and physics of community detection: landscapes, phase transitions, and hardness. Bull. EATCS, 121, 2017. Google Scholar
  27. E. Mossel, J. Neeman, and A. Sly. Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, 162:431-461, 2015. Google Scholar
  28. D. Panchenko. The Sherrington-Kirkpatrick model. Springer, 2013. Google Scholar
  29. J. Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Elsevier, 2014. Google Scholar
  30. J. Raymond and D. Saad. Sparsely spread cdma - a statistical mechanics-based analysis. Journal of physics A: mathematical and theoretical, 40:12315, 2007. Google Scholar
  31. T. Richardson and R. Urbanke. Modern coding theory. Cambridge University Press, 2012. Google Scholar
  32. J. van den Brand and N. Jaafari. The mutual information of ldgm codes. arXiv, 2017. URL: http://arxiv.org/abs/1707.04413.
  33. L. Zdeborová and F. Krzakala. Phase transition in the coloring of random graphs. Phys. Rev. E, 76:031131, 2007. Google Scholar
  34. L. Zdeborová and F. Krzakala. Statistical physics of inference: thresholds and algorithms. Advances in Physics, 65:453-552, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact