Lifted Message Passing for the Generalized Belief Propagation
This work addresses scalability issues in probabilistic inference for relational models, offering a domain-size independent solution that is incremental in improving existing methods.
The paper tackles the problem of efficiently computing sum-product queries in Probabilistic Relational Models by introducing a lifted Generalized Belief Propagation algorithm that forms a compact region graph and modifies message passing to mimic ground model behavior, achieving domain-size independence.
We introduce the lifted Generalized Belief Propagation (GBP) message passing algorithm, for the computation of sum-product queries in Probabilistic Relational Models (e.g. Markov logic network). The algorithm forms a compact region graph and establishes a modified version of message passing, which mimics the GBP behavior in a corresponding ground model. The compact graph is obtained by exploiting a graphical representation of clusters, which reduces cluster symmetry detection to isomorphism tests on small local graphs. The framework is thus capable of handling complex models, while remaining domain-size independent.