Counting Belief Propagation

By Kristian Kersting, Babak Ahmadi, Sriraam Natarajan. 2009

178 citations recorded by the source corpus.

A major benefit of graphical models is that most knowledge is captured in the model structure. Many models, however, produce inference problems with a lot of symmetries not reflected in the graphical structure and hence not exploitable by efficient inference techniques such as belief propagation (BP). In this paper, we present a new and simple BP algorithm, called counting BP, that exploits such additional symmetries. Starting from a given factor graph, counting BP first constructs a compressed factor graph of clusternodes and clusterfactors, corresponding to sets of nodes and factors that are indistinguishable given the evidence. Then it runs a modified BP algorithm on the compressed graph that is equivalent to running BP on the original factor graph. Our experiments show that counting BP is applicable to a variety of important AI tasks such as (dynamic) relational models and boolean model counting, and that significant efficiency gains are obtainable, often by orders of magnitude.

Subfields: Artificial Intelligence, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Probabilistic & Bayesian Methods

Citations in the corpus

Learning Convolutional Neural Networks for Graphs (2016, methodology): “Color reﬁnement has attracted considerable interest in the ML community since it can be applied to speed-up inference in graphical models (Kersting et al., 2009; 2014) and as a method to compute graph kernels (Shervashidze et al., 2011).”
Equivariance Through Parameter-Sharing (2017, methodology): “In particular, many probabilistic inference techniques have been extended to graphical models with known symmetry groups (Raedt et al., 2016; Kersting et al., 2009; Bui et al., 2012; Niepert, 2012).”
Statistical Relational Artificial Intelligence: Logic, Probability, and Computation (2016, methodology): “Kersting et al. [2006] employed relational hidden Markov models for protein fold recognition. Singla and Domingos [2006] proposed a Markov logic model for entity resolution (ER), the problem of finding records corresponding to the same real-world entity.”
Lifted Stochastic Planning, Belief Propagation and Marginal MAP (2018, background): “Given this analysis it is natural to ask if we can improve SOGBOFA further by taking advantage of improvements of BP, for example Lifted BP (Singla and Domingos 2008; Kersting, Ahmadi, and Natarajan 2009) where repeated messages are avoided in the computation.”
Gradient-based boosting for statistical relational learning: The relational dependency network case (2011, methodology): “Though there are several lifted inference techniques proposed [45, 24, 39, 10, 31] for SRL models, the research in this area is at a nascent stage and boosting would provide the perfect opportunity to learn the structure and parameters simultaneously.”
Efficient Graph Kernels by Randomization (2012, methodology): “Second, propagation kernels are deeply connected to several recent lifted message-passing approaches [1, 11, 15, 20] to probabilistic inference.”
Learning to Reason: Leveraging Neural Networks for Approximate DNF Counting (2019, methodology): “Beyond hashing techniques, loopy belief propagation (LBP) (Pearl 1982; Murphy, Weiss, and Jordan 1999) has been applied to approximate WMC. LBP does not provide any guarantees (Weiss 2000).”
Markov Chains on Orbits of Permutation Groups (2012, methodology): “Following Poole’s work, several algorithms for lifted probabilistic inference were developed such as lifted and counting belief propagation [41, 22], bi-simulation-based approximate inference [40], general purpose MCMC algorithm for relational models [29] and, more recently, ﬁrst-order knowledge…”
Hinge-Loss Markov Random Fields and Probabilistic Soft Logic (2015, methodology): “Various inference techniques for discrete MRFs have been extended to a lifted approach, including belief propagation (Jaimovich et al., 2007; Singla and Domingos, 2008; Kersting et al., 2009) and Gibbs sampling (Venugopal and Gogate, 2012).”
Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey (2019, methodology): “However, this comes at a computational price and therefore it is often needed to restrict the expressivity of the model by only using model structures that are known to be tractable [221, 117] or to approximate the inference [220, 119, 24].”