On Loopy Belief Propagation – Local Stability Analysis for Non-Vanishing Fields

Christian Knoll, Franz Pernkopf
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:591-600, 2017.

Abstract

In this work we obtain all fixed points of belief propagation and perform a local stability analysis. We consider pairwise interactions of binary random variables and investigate the influence of non-vanishing fields and finite-size graphs on the performance of belief propagation; local stability is heavily influenced by these properties. We show why non-vanishing fields help to achieve convergence and increase the accuracy of belief propagation. We further explain the close connections between the underlying graph structure, the existence of multiple solutions, and the capability of belief propagation (with damping) to converge. Finally we provide insights into why finite-size graphs behave better than infinite-size graphs.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-knoll17a, title = {On Loopy Belief Propagation – Local Stability Analysis for Non-Vanishing Fields}, author = {Knoll, Christian and Pernkopf, Franz}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {591--600}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/knoll17a/knoll17a.pdf}, url = {https://proceedings.mlr.press/r15/knoll17a.html}, abstract = {In this work we obtain all fixed points of belief propagation and perform a local stability analysis. We consider pairwise interactions of binary random variables and investigate the influence of non-vanishing fields and finite-size graphs on the performance of belief propagation; local stability is heavily influenced by these properties. We show why non-vanishing fields help to achieve convergence and increase the accuracy of belief propagation. We further explain the close connections between the underlying graph structure, the existence of multiple solutions, and the capability of belief propagation (with damping) to converge. Finally we provide insights into why finite-size graphs behave better than infinite-size graphs.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T On Loopy Belief Propagation – Local Stability Analysis for Non-Vanishing Fields %A Christian Knoll %A Franz Pernkopf %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-knoll17a %I PMLR %P 591--600 %U https://proceedings.mlr.press/r15/knoll17a.html %V R15 %X In this work we obtain all fixed points of belief propagation and perform a local stability analysis. We consider pairwise interactions of binary random variables and investigate the influence of non-vanishing fields and finite-size graphs on the performance of belief propagation; local stability is heavily influenced by these properties. We show why non-vanishing fields help to achieve convergence and increase the accuracy of belief propagation. We further explain the close connections between the underlying graph structure, the existence of multiple solutions, and the capability of belief propagation (with damping) to converge. Finally we provide insights into why finite-size graphs behave better than infinite-size graphs. %Z Reissued by PMLR on 04 October 2026.
APA
Knoll, C. & Pernkopf, F.. (2017). On Loopy Belief Propagation – Local Stability Analysis for Non-Vanishing Fields. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:591-600 Available from https://proceedings.mlr.press/r15/knoll17a.html. Reissued by PMLR on 04 October 2026.

Related Material