Large-scale probabilistic graphical models often contain millions of variables, making exact ground-level inference computationally prohibitive. To combat this combinatorial explosion, researchers developed lifted inference. The core intuition behind lifting is simple: if multiple objects in a domain behave identically, we can group them into a single abstract entity (a "supernode") and perform computation on the group as a whole, rather than reasoning about each individual object. As noted by Stefan Lüdtke et al. in their systematic review, State-Space Abstractions for Probabilistic Inference: A Systematic Review, these symmetry-based compressions allow algorithms to scale independently of the domain size.
However, this elegant mathematical shortcut faces a severe real-world challenge: evidence-induced symmetry breaking. The moment we observe specific data about individuals, the global symmetries that lifted inference relies on begin to dissolve.
The Fragility of Symmetry: Model Shattering
To understand why evidence destroys lifting, imagine a social network model where every person is initially assumed to behave identically. Because of this perfect exchangeability, a lifted inference engine can compress the entire population into a single computational representative.
Now, introduce a single piece of real-world evidence: Alice has tested positive for a rare disease.
Suddenly, Alice is no longer exchangeable with the rest of the population. The inference engine must split the population into two groups: {Alice} and {Everyone Else}. If we then observe that Bob was in contact with Alice, Bob must also be isolated into his own distinct category. As more unique data points are observed, this splitting cascades through the network.
This phenomenon is known as model shattering. As described by Jaesik Choi et al. in Lifted Relational Kalman Filtering, unique observation histories force the model to treat previously identical entities as distinct individuals. When the model shatters completely, the lifted state representation collapses back into a fully grounded list, neutralizing the computational advantages of high-level abstraction and forcing a fallback to expensive ground-level processing.
The Complexity Boundary: Unary vs. Relational Evidence
Not all evidence breaks symmetry in the same way. The theoretical boundaries of this problem were mapped out by Manfred Jaeger et al. in Liftability of Probabilistic Inference: Upper and Lower Bounds. They established a fundamental distinction between two types of observations:
- Unary Evidence: Observations about single-object properties (e.g., "Alice is a smoker," "Bob is an engineer"). Unary evidence restricts properties to individuals but does not link them together. The authors proved that conditioning on unary traits keeps inference tractable because it merely splits the domain into a bounded number of symmetric subgroups.
- Relational (Binary) Evidence: Observations about relationships between specific pairs or tuples of objects (e.g., "Alice is friends with Bob").
Relational evidence is the true catalyst for model shattering. When we specify arbitrary links between pairs of objects, we construct an irregular network topology. The authors demonstrated that conditioning on arbitrary relational evidence destroys the symmetries required for lifting, shifting the complexity of otherwise tractable logic fragments to #P-hard.
Strategies for Mitigating Symmetry Breaking
To prevent lifted inference from collapsing under the weight of real-world data, researchers have developed several distinct paradigms to handle, approximate, or bypass broken symmetries.
1. Relaxing Exactness: Approximate Bisimulation and Clustering
If exact symmetries are rare in noisy datasets, why not group objects that are almost symmetric?
Prithviraj Sen et al. introduced a framework in Bisimulation-based Approximate Lifted Inference that uses approximate bisimulation and factor binning. Instead of requiring identical probability distributions to group nodes, they allow users to trade a small, bounded amount of accuracy for massive speedups by clustering components with minor variations.
Similarly, Parag Singla et al. proposed Noise-Tolerant Hypercubes in Approximate Lifting Techniques for Belief Propagation. By grouping together objects that behave similarly rather than only those that are syntactically identical, their approach prevents minor data variations from shattering the model into unmanageable pieces.
2. Low-Rank Evidence Factorization
When relational evidence forms a complex, asymmetric matrix, we can compress the evidence itself rather than the underlying graphical model.
In On the Complexity and Approximation of Binary Evidence in Lifted Inference, Guy Van den Broeck et al. identified Boolean rank as the fundamental parameter governing the complexity of conditioning on binary evidence. They demonstrated that by approximating a complex, asymmetric binary evidence matrix using low-rank Boolean Matrix Factorization (BMF), one can substitute a highly shattering evidence set with a low-rank approximation. This effectively bypasses the #P-hard complexity barrier by re-introducing a structured, low-rank symmetry back into the conditioned model.
3. Coarse-to-Fine Adaptive Refinement
Rather than deciding on a static grouping before running inference, adaptive methods dynamically adjust the level of abstraction during computation.
For hybrid models containing both discrete and continuous variables, continuous observations act as severe symmetry breakers. To address this, Yuqiao Chen et al. proposed a "coarse-to-fine" extension in Lifted Message Passing for Hybrid Probabilistic Inference that adaptively refines evidence groupings, starting with broad clusters and splitting them only when necessary.
In the domain of optimization, Nicholas Gallo applied this philosophy to variational inference in Lifted Generalized Dual Decomposition. The framework generates anytime upper bounds by maintaining highly compressed, symmetric variable groupings, selectively "un-grouping" or shattering specific variables only when doing so significantly improves the solution quality.
4. Forced Partitioning and Bounding
When a domain is inherently asymmetric, some algorithms choose to force symmetry upon it and correct for the error later.
Somdeb Sarkhel et al. introduced a partitioning trick in Fast Lifted MAP Inference via Partitioning that forces groups of ground atoms to behave identically even when they are asymmetric in reality. This creates an anytime algorithm that bridges the gap between fast, symmetric approximations and slow, exact propositional solvers.
To provide formal guarantees during this process, Nicholas Gallo et al. developed Lifted Weighted Mini-Bucket, which combines the structural compression of lifting with the systematic bounding guarantees of mini-bucket elimination, offering a principled way to handle high-order interactions and real-world asymmetries without collapsing into full grounding.
Key Foundational Work
Template Based Inference in Symmetric Relational Markov Random Fields (2007) — contributed 2 concept elements to this direction.
Bisimulation-based Approximate Lifted Inference (2009) — contributed 1 concept elements to this direction.
Lifted Aggregation in Directed First-Order Probabilistic Models (2009) — contributed 1 concept elements to this direction.