# Colour Passing Revisited: Lifted Model Construction with Commutative Factors

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 23 references that are in the map.
- First posted on arXiv 20 Sep 2023.

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

- [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)
- [Taming Reasoning in Temporal Probabilistic Relational Models](https://mlsanity.com/paper/1911.07040/) (2019)
- [Generating and Sampling Orbits for Lifted Probabilistic Inference](https://mlsanity.com/paper/1903.04672/) (2019)
- [Markov Chains on Orbits of Permutation Groups](https://mlsanity.com/paper/1408.2052/) (2014)

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

- [Efficient Detection of Exchangeable Factors in Factor Graphs](https://mlsanity.com/paper/2403.10167/) (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)
- [Approximate Lifted Model Construction](https://mlsanity.com/paper/2504.20784/) (2025)
- [Compression versus Accuracy: A Hierarchy of Lifted Models](https://mlsanity.com/paper/2505.22288/) (2025)
- [Lifting Factor Graphs with Some Unknown Factors](https://mlsanity.com/paper/2406.01275/) (2024)
- [Lifted Model Construction without Normalisation: A Vectorised Approach to Exploit Symmetries in Factor Graphs](https://mlsanity.com/paper/2411.11730/) (2024)
- [On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions](https://mlsanity.com/paper/2605.26908/) (2026)
- [Towards Privacy-Preserving Relational Data Synthesis via Probabilistic Relational Models](https://mlsanity.com/paper/2409.04194/) (2024)
- [Lifting Factor Graphs with Some Unknown Factors for New Individuals](https://mlsanity.com/paper/2504.04089/) (2025)
- [Lifted Model Construction under Approximate Commutativity](https://mlsanity.com/paper/2608.24713/) (2026)

## Abstract (arXiv)

Lifted probabilistic inference exploits symmetries in a probabilistic model to allow for tractable probabilistic inference with respect to domain sizes. To apply lifted inference, a lifted representation has to be obtained, and to do so, the so-called colour passing algorithm is the state of the art. The colour passing algorithm, however, is bound to a specific inference algorithm and we found that it ignores commutativity of factors while constructing a lifted representation. We contribute a modified version of the colour passing algorithm that uses logical variables to construct a lifted representation independent of a specific inference algorithm while at the same time exploiting commutativity of factors during an offline-step. Our proposed algorithm efficiently detects more symmetries than the state of the art and thereby drastically increases compression, yielding significantly faster online query times for probabilistic inference when the resulting model is applied.