D-CIS Publication Database

Publication

Type of publication:Inproceedings
Entered by:WW
TitleValidity estimates for loopy belief propagation on binary real-world networks
Bibtex cite ID
Booktitle Advances in Neural Information Processing Systems 17 (NIPS 2004)
Series Advances in Neural Information Processing Systems
Year published 2004
Number 17
Pages 945-952
Location 13-18 December 2004, Vancouver, Canada
Keywords graphical models,approximate inference
Abstract
We introduce a computationally efficient method to estimate the validity of the BP method as a function of graph topology, the connectivity strength, frustration and network size. We present numerical results that demonstrate the correctness of our estimates for the uniform random model and for a real-world network (“C. Elegans”). Although the method is restricted to pair-wise interactions, no local evidence (zero “biases”) and binary variables, we believe that its predictions correctly capture the limitations of BP for inference and MAP estimation on arbitrary graphical models. Using this approach, we find that BP always performs better than MF. Especially for large networks with broad degree distributions (such as scale-free networks) BP turns out to significantly outperform MF.
Authors
Mooij, Joris
Kappen, Hilbert J.
Topics
=SEE CLASSIFICATION DIFFERENCE FROM OTHERS=
BibTeXBibTeX
RISRIS
Attachments
 
Total mark: 5