# Efficient Detection of Commutative Factors in Factor Graphs

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 16 references that are in the map.
- First posted on arXiv 23 Jul 2024.

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

- [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)

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

- [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)
- [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)
- [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 probabilistic graphical models to allow for tractable probabilistic inference with respect to domain sizes. To exploit symmetries in, e.g., factor graphs, it is crucial to identify commutative factors, i.e., factors having symmetries within themselves due to their arguments being exchangeable. The current state of the art to check whether a factor is commutative with respect to a subset of its arguments iterates over all possible subsets of the factor's arguments, i.e., O(2n) iterations for a factor with n arguments in the worst case. In this paper, we efficiently solve the problem of detecting commutative factors in a factor graph. In particular, we introduce the detection of commutative factors (DECOR) algorithm, which allows us to drastically reduce the computational effort for checking whether a factor is commutative in practice. We prove that DECOR efficiently identifies restrictions to drastically reduce the number of required iterations and validate the efficiency of DECOR in our empirical evaluation.