2012/05/09 by Kristian Kersting, Kersting, Kristian, Babak Ahmadi +3 · 7 citations
Computer Science · #AI-based Problem Solving and Planning #Advanced Graph Neural Networks #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1205.2637
openalex publication_date 2012/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.