# Efficient Detection of Exchangeable Factors in Factor Graphs

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 14 references that are in the map.
- First posted on arXiv 15 Mar 2024.

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

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

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

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

## Abstract (arXiv)

To allow for tractable probabilistic inference with respect to domain sizes, lifted probabilistic inference exploits symmetries in probabilistic graphical models. However, checking whether two factors encode equivalent semantics and hence are exchangeable is computationally expensive. In this paper, we efficiently solve the problem of detecting exchangeable factors in a factor graph. In particular, we introduce the detection of exchangeable factors (DEFT) algorithm, which allows us to drastically reduce the computational effort for checking whether two factors are exchangeable in practice. While previous approaches iterate all O(n!) permutations of a factor's argument list in the worst case (where n is the number of arguments of the factor), we prove that DEFT efficiently identifies restrictions to drastically reduce the number of permutations and validate the efficiency of DEFT in our empirical evaluation.