# Approximate Lifted Model Construction

arXiv: https://arxiv.org/abs/2504.20784 · HTML: https://mlsanity.com/paper/2504.20784/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 21 references that are in the map.
- First posted on arXiv 29 Apr 2025.

## Builds on (most cited first, 8 of 8)

- [Tractability through Exchangeability: A New Perspective on Efficient Probabilistic Inference](https://mlsanity.com/paper/1401.1247/) (2014)
- [Lifted Variable Elimination: Decoupling the Operators from the Constraint Language](https://mlsanity.com/paper/1402.0565/) (2014)
- [Colour Passing Revisited: Lifted Model Construction with Commutative Factors](https://mlsanity.com/paper/2309.11236/) (2023)
- [Efficient Detection of Exchangeable Factors in Factor Graphs](https://mlsanity.com/paper/2403.10167/) (2024)
- [Lifted Causal Inference in Relational Domains](https://mlsanity.com/paper/2403.10184/) (2024)
- [Efficient Detection of Commutative Factors in Factor Graphs](https://mlsanity.com/paper/2407.16280/) (2024)
- [Estimating Causal Effects in Partially Directed Parametric Causal Factor Graphs](https://mlsanity.com/paper/2411.07006/) (2024)
- [Lifted Model Construction without Normalisation: A Vectorised Approach to Exploit Symmetries in Factor Graphs](https://mlsanity.com/paper/2411.11730/) (2024)

## Built on by (most cited first, 3 of 3)

- [Compression versus Accuracy: A Hierarchy of Lifted Models](https://mlsanity.com/paper/2505.22288/) (2025)
- [On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions](https://mlsanity.com/paper/2605.26908/) (2026)
- [Lifted Model Construction under Approximate Commutativity](https://mlsanity.com/paper/2608.24713/) (2026)

## Abstract (arXiv)

Probabilistic relational models such as parametric factor graphs enable efficient (lifted) inference by exploiting the indistinguishability of objects. In lifted inference, a representative of indistinguishable objects is used for computations. To obtain a relational (i.e., lifted) representation, the Advanced Colour Passing (ACP) algorithm is the state of the art. The ACP algorithm, however, requires underlying distributions, encoded as potential-based factorisations, to exactly match to identify and exploit indistinguishabilities. Hence, ACP is unsuitable for practical applications where potentials learned from data inevitably deviate even if associated objects are indistinguishable. To mitigate this problem, we introduce the varepsilon-Advanced Colour Passing (varepsilon-ACP) algorithm, which allows for a deviation of potentials depending on a hyperparameter varepsilon. varepsilon-ACP efficiently uncovers and exploits indistinguishabilities that are not exact. We prove that the approximation error induced by varepsilon-ACP is strictly bounded and our experiments show that the approximation error is close to zero in practice.