On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions

Malte Luttermann, Ralf Möller, Marcel Gehrke · 2026

Read On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions by Malte Luttermann, Ralf Möller, Marcel Gehrke (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-26908.txt.

Introduction

Luttermann, Möller, and Gehrke revisit the basics of spotting commutative factors in factor graphs. A commutative factor is one whose outputs stay the same when inputs to a subset of arguments are permuted. They show the leading algorithm rests on a theorem mistakenly read as sufficient when it only gives a necessary condition, so the algorithm can return wrong results. They prove a corrected necessary test, present a fixed algorithm that keeps its speed and stays correct, and add a second algorithm with tighter worst-case bounds.

Catalog record

CREATORMalte Luttermann, Ralf Möller, Marcel Gehrke
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE88381
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.26908

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions Malte Luttermann, Ralf Möller, Marcel Gehrke Abstract Exploiting the indistinguishability of objects in a probabilistic graphical model such as a fg is key to lifted probabilistic inference algorithms and allows for tractable probabilistic inference problems with respect to domain sizes. A central building block for the exploitation of indistinguishable objects in fg is the identification of commutative factors, i.e., factors whose output values are invariant under permutations of input values assigned to a subset of their arguments. In this paper, we revisit the theoretical foundations underlying the state-of-the-art algorithm to detect commutative factors. Specifically, we show that in its current form, the state-of-the-art algorithm relies on a central theorem that is mistakenly regarded as a sufficient condition to identify commutative factors, while it actually only implies necessary condition. Consequently, the state of the art might, as we show in this paper, deliver incorrect results. To fix the flaws currently present in the state of the art, we prove a slightly modified version of the aforementioned theorem, which serves as a necessary condition to identify commutative factors. Moreover, we present a corrected version of the state-of-the-art algorithm, which keeps its efficiency while ensuring correctness and introduce a complementary algorithm with tighter worst-case bounds. keywords colour passing; factor graphs; lifted inference. 1 Introduction Reasoning under uncertainty is a core challenge in artificial intelligence, and probabilistic graphical models offer a principled framework for this task by factorising a joint probability distribution into a product of local functions (which we call factors). Computing marginal and conditional distributions—the central inference problem—is, however, intractable in general as the computational cost grows exponentially with the number of rv in propositional models such as bn , mn , or fg ( 2 ) . This intractability even persists for approximate inference ( 3 ) . Lifted inference algorithms exploit the indistinguishability of objects to allow for tractable probabilistic inference problems (i.e., inference problems that are solvable in polynomial time) with respect to domain sizes while maintaining exact answers ( 10 ) . To perform lifted inference, however, a lifted representation encoding equivalent semantics as the initially given propositional probabilistic model must be constructed. Constructing such a lifted representation requires the identification of indistinguishable objects, which also includes the identification of commutative factors. A commutative factor is a factor (i.e., a function) that outputs the same value regardless of the order of the input values of a subset of its arguments. In this paper, we solve the problem of efficiently detecting commutative factors by revisiting the theoretical foundations underlying the efficient detection of commutative factors and providing efficient algorithms with correctness guarantees that are missing in the current state of the art. Previous work. 11 has introduced the notion of a pfg ( pfg ) as a lifted representation combining concepts from first-order logic with probabilistic modelling. To perform lifted inference, 11 has proposed lve ( lve ) as a lifted inference algorithm that operates on a pfg , and since its introduction, lve has continuously been refined by many researchers to reach its current form ( 13 ) . The current state of the art to construct a lifted representation such as a pfg from a given propositional model is the acp ( acp ) algorithm ( 6 ) , which has also been generalised to enable approximate lifted model construction ( 8 ; 12 ) . An essential subroutine of lifted model construction (and hence of acp ) is to compute subsets of commutative arguments of a factor to be able to exploit the indistinguishability of objects. In its original form, acp applies a brute-force approach to compute subsets of commutative arguments of a factor. Such a brute-force approach iterates over all possible subsets of arguments and checks whether a subset is actually commutative, thus requiring O(2^{n}) sets to check for a factor with n arguments in the worst case. To avoid a computationally expensive brute-force approach, 7 have presented the decor ( decor ) algorithm, which applies a pruning strategy to heavily restrict the search space of subsets of arguments to consider. However, we found that a central theorem to the decor algorithm does not hold in its current form and hence, the correctness of decor is not guaranteed. Our contributions. We first show that the central theorem underlying the decor algorithm provides only a necessary, not a sufficient, condition for the identification of commutative arguments, and we prove a corrected version of the theorem. Second, based on the corrected theorem, we present the decorplus ( decorplus ) algorithm, which is guaranteed to return a correct solution. We formally prove the correctness of decorplus and show that it maintains the efficiency of decor . Third, we introduce a complementary bottom-up algorithm, called decorapriori ( decorapriori ), which is inspired by the Apriori algorithm ( 1 ) and exploits the downward closure and transitivity of pairwise commutativity, thereby yielding an algorithm with tighter worst-case bounds. Structure of this paper. The remaining part of this paper is organised as follows. In Section 2 , we introduce the necessary background on fg and commutative factors. Then, in Section 3 , we investigate the decor algorithm and provide a counterexample showing that decor does not guarantee correctness in its current form. We further present corrected theoretical results that clarify the necessary conditions for the identification of commutative factors. Thereafter, in Section 4 , we show how our new theoretical results can be incorporated into the decor algorithm to ensure correctness while maintaining efficiency. In Section 5 , we introduce the decorapriori algorithm, which is a complementary bottom-up algorithm with tighter worst-case bounds before we empirically evaluate decorplus and decorapriori Section 6 . 2 Background An fg represents a joint probability distribution over a set of rv by decomposing it into a product of local functions called factors ( 4 ; 5 ) . In the following, we write \mathrm{range}(R) to denote the values a rv R can take (called range). Definition 1 (Factor Graph) . An fg is a tuple M=(\boldsymbol{R},\allowbreak\boldsymbol{F},\allowbreak\boldsymbol{E},\allowbreak\boldsymbol{\Phi}) where \boldsymbol{R}=\{R_{1},\ldots,\allowbreak R_{n}\} is a set of rv , \boldsymbol{F}=\{f_{1},\ldots,\allowbreak f_{m}\} is a set of factor names, and \boldsymbol{\Phi}=\{\phi_{1},\ldots,\allowbreak\phi_{m}\} is a set of function definitions (called factors). Each \phi_{j}(\mathcal{R}_{j}) defines a function \phi_{j}\colon\times_{R\in\mathcal{R}_{j}}\mathrm{range}(R)\mapsto\mathbb{R}_{\geq 0} defined over an argument sequence \mathcal{R}_{j} of rv from \boldsymbol{R} that outputs positive real numbers, called potentials, of which at least one is non-zero. For each pair of variable node R_{i}\in\boldsymbol{R} and factor node f_{j}\in\boldsymbol{F} , there is an edge \{R_{i},\allowbreak f_{j}\}\in\boldsymbol{E}\subseteq\{\{R,f\}\mid R\in\boldsymbol{R}\land f\in\boldsymbol{F}\} if R_{i}\in\mathcal{R}_{j} . The full joint distribution encoded by M for an assignment (R_{1}=r_{1},\allowbreak\ldots,\allowbreak R_{n}=r_{n}) to the rv in \boldsymbol{R} , abbreviated as \boldsymbol{R}=\boldsymbol{r} , is defined as \displaystyle P_{M}(\boldsymbol{R}=\boldsymbol{r}) \displaystyle=\frac{1}{Z}\prod_{j=1}^{m}\phi_{j}(\mathcal{R}_{j}=\boldsymbol{r}_{j}), where \boldsymbol{r}_{j} is a projection of \boldsymbol{r} to the argument list of \phi_{j} and Z is the normalisation constant, defined as Z=\sum_{\boldsymbol{r}\in\mathrm{range}(R_{1})\times\ldots\times\mathrm{range}(R_{n})}\prod_{j=1}^{m}\phi_{j}(\mathcal{R}_{j}=\boldsymbol{r}_{j}) . Example 2 . Figure 1 displays an fg M=(\boldsymbol{R},\allowbreak\boldsymbol{F},\allowbreak\boldsymbol{E},\allowbreak\boldsymbol{\Phi}) that models the interplay between the competences ComA and ComB of two employees Alice and Bob , the revenue Rev of the company they work for, and their corresponding salaries SalA and SalB . The range of each rv is \{\mathrm{high},\allowbreak\mathrm{low}\} . An exemplary function

Read the complete text