In traditional probabilistic graphical models, inference often scales with the number of individual entities in a domain. If you are modeling a social network of a million people, standard algorithms like Belief Propagation or Variable Elimination treat each person as a distinct variable. This process, known as grounding, leads to a "state explosion" where the computational cost becomes prohibitive.
Lifted Probabilistic Inference (LPI) offers a way out by reasoning about groups of objects rather than individuals. The core intuition is simple: if two entities are governed by the same rules and we have no specific information distinguishing them, we should be able to perform a single computation that applies to both.
Reasoning at the Template Level
Most large-scale models are defined using templates—general rules like "Friends of smokers are likely to smoke." Kristian Kersting and colleagues demonstrated in Template Based Inference in Symmetric Relational Markov Random Fields that we can perform inference at this template level. Instead of a massive graph of individuals, we operate on a compact "lifted" graph where nodes represent populations.
This efficiency relies on the mathematical concept of symmetries or automorphisms. As Sebastian Riedel and others explored in Automorphism Groups of Graphical Models and Lifted Variational Inference, variables can be grouped into "orbits." If the model's structure is invariant under certain permutations of these variables, we only need to solve the problem in a much lower-dimensional space.
The Statistical Foundation: Exchangeability
The theoretical justification for lifting is finite partial exchangeability. In Tractability through Exchangeability, Mathias Niepert and Guy Van den Broeck argue that exchangeability is the fundamental principle that makes models tractable.
If a set of variables is exchangeable, their joint probability distribution is invariant to their ordering. This allows us to use "counting formulas"—instead of tracking which specific individuals have a trait, we only track how many individuals have it. Jesse Davis and Nima Taghipour extended this in Generalized Counting for Lifted Variable Elimination, showing that we can handle complex groups of related atoms (tuples) while maintaining polynomial time complexity relative to the domain size.
The Achilles' Heel: Symmetry Breaking
The primary challenge for LPI is evidence. In a perfectly symmetric model, everyone is identical. But the moment we observe that "Alice has a cold," Alice is no longer interchangeable with Bob. This observation acts as a "symmetry breaker."
As Babak Ahmadi and Kristian Kersting describe in Lifted Online Training of Relational Models, introducing evidence causes the model to shatter. The large, efficient groups of variables split into many smaller groups. If we have unique evidence for every individual, the model shatters completely, reverting to a fully grounded representation. This "death sentence" for lifting is a recurring theme: Hung Hai Bui and colleagues noted in Exact Lifted Inference with Distinct Soft Evidence that unique data for every individual typically destroys the very symmetries that make lifting useful.
Recovering Efficiency in Asymmetric Worlds
Researchers have developed several strategies to handle the "shattering" caused by real-world evidence:
- Approximate Lifting: Instead of requiring perfect symmetry, we group variables that are "similar enough." Prithviraj Sen proposed approximate bisimulation in Bisimulation-based Approximate Lifted Inference to trade a small amount of accuracy for massive speedups. Similarly, Parag Singla introduced Noise-Tolerant Hypercubes in Approximate Lifting Techniques for Belief Propagation to group objects that behave similarly despite minor data variations.
- Low-Rank Evidence Approximation: Guy Van den Broeck and Adnan Darwiche identified Boolean rank as the key to complexity in On the Complexity and Approximation of Binary Evidence. By approximating complex evidence using low-rank matrix factorization, they can maintain a lifted structure even when the raw evidence is asymmetric.
- Lifted Sampling: When exact lifting fails, we can use symmetries to improve sampling. Mathias Niepert and Guy Van den Broeck developed Lifted Metropolis-Hastings (LMH) in Lifted Probabilistic Inference for Asymmetric Graphical Models. LMH uses "almost-symmetries" to propose large jumps in the Markov chain, allowing for faster convergence in asymmetric models without introducing bias.
Why Lifting Matters
The power of lifting isn't just a heuristic speedup; it represents a fundamental shift in computational complexity. In Model Counting of Query Expressions, Dan Suciu and colleagues proved that lifted methods are strictly more powerful than propositional ones. They identified queries that can be solved in polynomial time by exploiting relational structure, whereas any propositional solver would require exponential time. By treating the model as a set of high-level symmetries rather than a collection of independent bits, LPI allows us to reason about systems that are otherwise mathematically unreachable.