2015/02/17 by Wolfgang Gatterbauer, Gatterbauer, Wolfgang
Computer Science · Mathematics · #Advanced Graph Neural Networks #Algorithm #Applied mathematics #Approximate inference #Artificial Intelligence (cs.AI) #Artificial intelligence #Bayesian Modeling and Causal Inference #Bayesian network #Belief propagation #Computer science #Convergence (economics) #Discrete mathematics #Error Correcting Code Techniques #FOS: Computer and information sciences #Graph #Graphical model #Inference #Linearization #Machine Learning (cs.LG) #Markov chain #Markov process #Mathematical optimization #Mathematics #Node (physics) #Nonlinear system #Pairwise comparison #Probabilistic logic #Random graph #Social and Information Networks (cs.SI) #cs.AI #cs.LG #cs.SI
paper · pdf · doi:10.48550/arxiv.1502.04956
published in arXiv (Cornell University) (Cornell University) · Full version of AAAI 2017 paper with same title (23 pages, 9 figures)
openalex publication_date 2015/02/17 · arxiv created 2016/12/27 · arxiv updated 2016/12/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Belief Propagation (BP) is a widely used approximation for exact probabilistic inference in graphical models, such as Markov Random Fields (MRFs). In graphs with cycles, however, no exact convergence guarantees for BP are known, in general. For the case when all edges in the MRF carry the same symmetric, doubly stochastic potential, recent works have proposed to approximate BP by linearizing the update equations around default values, which was shown to work well for the problem of node classification. The present paper generalizes all prior work and derives an approach that approximates loopy BP on any pairwise MRF with the problem of solving a linear equation system. This approach combines exact convergence guarantees and a fast matrix implementation with the ability to model heterogenous networks. Experiments on synthetic graphs with planted edge potentials show that the linearization has comparable labeling accuracy as BP for graphs with weak potentials, while speeding-up inference by orders of magnitude.