Abstract
This paper introduces the first-ever lifted division operator, a mathematical tool that allows probabilistic inference to "undo" multiplications at a symbolic level. By filling this theoretical gap, the authors enable Lifted Hugin Belief Propagation, a message-passing scheme for junction trees that is significantly faster than previous methods. Its primary advantage is that its complexity is independent of the number of neighbors a node has in the model, overcoming a major bottleneck in lifted inference.
Introduction
In probabilistic graphical models, "lifting" is the technique of performing inference on groups of indistinguishable individuals rather than treating each one separately. This makes reasoning tractable even when domain sizes (the number of individuals) are massive.
The Lifted Junction Tree (LJT) algorithm is a state-of-the-art approach for handling multiple queries efficiently. However, LJT previously relied on the Shafer-Shenoy propagation scheme. In Shafer-Shenoy, to send a message to one neighbor, a node must multiply information from all other neighbors. If a node has $d$ neighbors, it performs $O(d)$ multiplications per message. In classical AI, the Hugin scheme avoids this by maintaining a single "pool" of information at each node and using division to quickly extract the specific message needed for a neighbor. Until now, Hugin could not be "lifted" because no mathematically sound way existed to perform division on "lifted" factors (parfactors), which involve complex counting constraints.
Methods
The authors contribute two main innovations:
- The Lifted Division Operator ($\oslash$): They define a formal operator that serves as the inverse of lifted multiplication. The challenge with lifting is that one "lifted" variable might represent $N$ individuals. When multiplying or dividing, one must "count-normalize" the potentials—scaling the probabilities to account for how many ground-level instances are being affected.
- Lifted Hugin Propagation: Using the new division operator, the authors adapt the Hugin architecture to First-Order Junction Trees (FO-jtrees).
Instead of re-multiplying factors for every neighbor, each node in the FO-jtree maintains a "Hugin factor." To send a message, the node simply divides its current state by the last message received from that neighbor. This reduces the per-message runtime to $O(1)$ with respect to the tree degree $d$.
Key Results
The authors evaluated the algorithm using synthetic benchmarks, including star and chain topologies where the number of neighbors (degree) varied from 1 to 100, and domain sizes scaled up to 1,000.
The empirical results confirm several key insights:
- Degree Independence: Lifted Hugin's runtime per message is $O(1)$ with respect to the tree degree, whereas Shafer-Shenoy is $O(d)$. This provides a massive advantage in models with high-degree nodes.
- Amortization: For multiple queries, the overhead of the initial "inward" pass in Hugin is quickly outweighed by the extreme efficiency of the "outward" pass and subsequent query answering.
- Tractability: Lifted Hugin remains polynomial in the domain size, preserving the core benefit of lifted inference while adding the efficiency of the Hugin scheme.
Conclusion and Future Work
The introduction of the lifted division operator completes the suite of operators required for exact lifted inference. While Hugin requires more memory than Shafer-Shenoy to store Hugin factors at every node, its speed and ability to "undo" information make it a powerful tool for large-scale probabilistic reasoning. Future work includes applying this to dynamic models, where division can handle temporal updates more gracefully, and exploring its use in lifted approximate inference.
Summary updated