Source-linked AI summary
Counting Belief Propagation
Kristian Kersting, Babak Ahmadi, Sriraam Natarajan
TL;DR
Standard BP cannot exploit many symmetries in graphical models, limiting efficiency for tasks such as relational inference and Boolean model counting. Counting BP compresses indistinguishable nodes and factors into a smaller graph and runs modified BP on it, preserving BP results. Experiments report significant gains, often by orders of magnitude, although gains disappear when the graph has no exploitable symmetries.
Problem
Many graphical models contain symmetries not reflected in their structure, while tasks such as Boolean model counting can be extremely expensive.
Method
Counting BP compresses nodes and factors that are indistinguishable given the evidence, then runs modified BP on the compressed factor graph.
Results
Counting BP yields the same results as BP on the original graph and often achieves efficiency gains of orders of magnitude across dynamic relational models and Boolean model counting.
Takeaways & Limitations
Counting BP provides a scalable approach for exploiting additional symmetries in finite-variable factor graphs and challenging AI inference tasks.
Takeaways & Limitations
When a graph lacks symmetries, CBP may coincide with BP and provide no efficiency gain or may add compression overhead.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper introduces counting BP to exploit symmetries that standard BP misses, targeting inference tasks that can otherwise be highly expensive. It groups indistinguishable nodes and factors, then applies modified BP to the compressed graph, with experiments showing substantial efficiency gains.
- Motivation: Model counting generalizes propositional satisfiability and is therefore highly useful but extremely expensive in practice.
- Contributions: Counting BP exploits additional model symmetries by grouping indistinguishable nodes and factors into clusternodes and clusterfeatures.The groups are defined by messages received and sent given the evidence.
- Contributions: The compressed graph supports modified BP that yields the same results as BP on the original uncompressed graph.
- Applications: Counting BP is applied to dynamic relational probabilistic models and Boolean model counting.
- Empirical outcome: Significant efficiency gains are obtained in both application domains, often by orders of magnitude.
2 Related Work
Related approaches also exploit indistinguishable variables or clustered structure, but they differ in representation requirements, generality, complexity, and convergence guarantees. Counting BP is presented as directly applicable to finite-variable factor graphs while remaining simpler than several alternatives.
- Lifted belief propagation: LFOBP groups variables that send and receive identical messages, but requires a first-order logical model specification and groups only nodes over the same predicate.
- Lifted belief propagation: Counting BP can be applied directly to any factor graph over finite random variables, making it a generalization of LFOBP.
- Clustered inference: Bisimulation-based clustered inference does not require first-order logical specifications and is guaranteed to converge, but it is much more complex than counting BP.
- Lifted variable elimination: Lifted variable-elimination methods use counting elimination but are extremely complex, do not easily scale to realistic domains, and require first-order logical specifications.
3 Belief Propagation
Factor graphs represent distributions through variable and factor nodes, while BP passes messages between them to compute marginal beliefs. BP is exact on trees but approximate on graphs with cycles, where convergence and correctness are not guaranteed.
- Factor graphs: Graphical models represent a joint distribution as a product of factors over subsets of variables.
- Factor graphs: A factor graph is a bipartite representation with variable nodes for variables, factor nodes for factors, and edges encoding factor arguments.
- Belief propagation: BP computes marginal probability functions by passing messages between variable nodes and neighboring factor nodes.
- Belief propagation: BP is exact when the factor graph is a tree but only approximate on graphs containing cycles.
- Compression: CFG compresses a factor graph by producing groups and signatures before constructing a compressed graph.
- Evidence: Evidence is incorporated by setting factor values to zero for states incompatible with the evidence.
4 Counting Belief Propagation
Counting BP compresses a factor graph by grouping nodes and factors that send and receive identical messages, then runs modified BP on the compressed graph. The resulting procedure preserves standard BP results while exploiting symmetries that standard BP cannot use.
- Motivation and Applications: Counting BP can exploit identical potentials and thereby speed up inference by orders of magnitude, while applying to relational and propositional probabilistic models.The paper highlights dynamic relational inference and Boolean model counting as application areas.
- 4 Counting Belief Propagation: Counting BP first constructs a compressed factor graph and then runs modified BP on that graph.The two stages are compression followed by inference on the compressed representation.
- Step 1 – Compressing the Factor Graph: Compression groups variable nodes and factor nodes according to message behavior and signatures given the evidence.Initial groups reflect known true, known false, and unknown variables; factors are grouped using incoming node colors and their own colors.
- Step 1 – Compressing the Factor Graph: The final graph represents sets of nodes and factors that send and receive the same messages at every BP step.These sets are called clusternodes and clusterfactors.
- Step 2 – BP on the Compressed Factor Graph: Modified BP on the compressed graph simulates BP on the original graph by accounting for multiple represented edges and repeated messages.The exponent c(f, X) − 1 excludes the corresponding factor message when forming a clustervariable-to-clusterfactor message.
- Correctness: Theorem 4.1 states that the compression algorithm returns a unique minimal compressed graph and that counting BP produces the same results as BP on the original graph.This establishes correctness of the compressed representation and its modified message-passing procedure.
5 Dynamic Relational Domains
Dynamic relational models extend probabilistic graphical models with objects, relations, and time, but temporal influences make variables correlated and inference difficult. The experiments apply lifted counting-based methods to dynamic Markov logic networks and report smaller graphs, fewer messages, and qualitatively better cancer-probability estimates.
- Dynamic Markov Logic Networks: Dynamic Markov logic networks extend static relational models by adding time-indexed fluents and intra-time and inter-time formulas.Discrete processes use non-negative integer time steps and a successor function linking consecutive steps.
- Dynamic Markov Logic Networks: Temporal shared influences cause variables to become correlated, so approximate inference is needed even for sparse dynamic models.This differs from static MLNs, where sparse models may not require the same approximation pressure.
- Lifted First-Order Factored Frontier: LFOFF replaces BP within factored frontier and uses counting BP to exploit symmetries in dynamic relational factor graphs.Factored frontier uses a forwards-backwards message protocol, while counting BP groups indistinguishable nodes and factors.
- Experimental Evaluation: In experiments with a 20-person social-network DMLN, LFOFF produced substantially smaller factor graphs and sent fewer messages than standard FF.The comparison used 10 time steps, with similar results reported for 15 time steps.
- Experimental Evaluation: The forwards-backwards protocol clearly outperformed the flooding protocol in message-count comparisons.The figure reports ratios of forwards-backwards to flooding messages, where lower values indicate greater speed-up.
- Experimental Evaluation: LFOFF produced the expected cancer-probability peak near an observed smoking event, whereas MC-SAT probabilities dropped regardless of temporal distance.The qualitative comparison observed smoking for person A at time step 2 and evaluated cancer(A, t) over time.
- Experimental Evaluation: Counting BP does not guarantee compression or speed-up when the factor graph contains no exploitable symmetries.In such cases, including random 3-CNF, counting BP essentially coincides with standard BP.
6 Model Counting
Model counting generalizes propositional satisfiability and is highly useful but extremely expensive in practice. CBPCOUNT replaces BP with counting BP to compute probabilistic lower bounds, yielding substantial efficiency gains when the formula contains exploitable symmetries, though not on all instances.
- Motivation: Model counting computes the number of solutions of a propositional formula and generalizes the NP-complete problem of propositional satisfiability.Its applications include multi-agent reasoning, adversarial reasoning, and graph coloring.
- Method: CBPCOUNT substitutes counting BP for BP within BPCOUNT to estimate variable marginals and recursively compute a probabilistic lower bound on a Boolean formula's model count.BPCOUNT runs BP with damping, identifies balanced variables, fixes variables, and combines residual counts with a slack factor.
- Experimental evaluation: 70.2% fewer messages and approximately twice the speed were achieved on 2bitmax 6, while both methods produced the same lower bound of 5.8×1028.CBP reduced messages by 88.7% when identifying the first most balanced variable; compressed-graph construction took 9% of CBP's total time.
- Experimental evaluation: No efficiency gain was obtained on random 3-CNF wff-3-100-150 because CBP could not compress the factor graph and introduced a small overhead.Both approaches again produced the same lower bound.
- Experimental evaluation: 162 times fewer messages were sent in the first iteration on ls8-norm, where CBP sent only 0.6% of BP's messages.The instance contained 301 variables and 1601 clauses.
- Conclusion: Across the experiments, CBPCOUNT sped up BPCOUNT, and real-world cases yielded several orders of magnitude fewer messages than standard BP.The gains depended on the presence of exploitable symmetries in the factor graph.
7 Conclusions
The paper introduces counting BP, which compresses factor graphs by grouping nodes and factors indistinguishable given the evidence and applies modified BP to the compressed graph. It applies this approach to dynamic relational inference and Boolean model counting, with experiments reporting significant efficiency gains, often by orders of magnitude.
- Contribution: Counting BP groups indistinguishable nodes and factors into clustervariables and clusterfactors, then applies modified belief propagation to the compressed factor graph.The approach is designed to exploit symmetries absent from the original graphical structure.
- Applications: Counting BP supports a lifted factor frontier algorithm for approximate inference in dynamic Markov logic networks and lower-bound computation for Boolean model counting.These applications cover dynamic relational models and Boolean formulas.
- Results and future work: Experiments report significant efficiency gains from counting BP instead of standard BP, often by orders of magnitude.The paper also proposes future work on approximate grouping, generalized variants, relational learning, real-world domains, and SAT-based techniques.