Paper deep dive
Lifted Model Construction under Approximate Commutativity
Malte Luttermann, Jan Speller, Tanya Braun, Marcel Gehrke, Ralf Möller
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Lifted inference algorithms enable scalable probabilistic inference even for large object domains by leveraging the indistinguishability of objects in a probability distribution. An essential prerequisite for constructing a lifted representation is to identify commutative factors, i.e., functions whose output values are invariant under permutations of a subset of their input values, in a potential-based factorisation. In practice, however, parameters learned from data inevitably deviate even if associated objects are indistinguishable, causing their corresponding factors to be only approximately commutative instead of being exactly commutative. We address this problem by introducing the concept of {\epsilon}-commutativity, a relaxation of commutativity where output values are only approximately invariant under permutations of input values. Specifically, we show how {\epsilon}-commutativity can be exploited for lifted model construction, downstream probabilistic inference, and prove strict bounds on the induced approximation error, thereby ensuring the practical applicability of lifted model construction while maintaining highly accurate query results. These theoretical guarantees are confirmed empirically, demonstrating comparable query accuracy at lower runtime.
Tags
Links
- Source: https://arxiv.org/abs/2608.24713v1
- Canonical: https://arxiv.org/abs/2608.24713v1
Trouble viewing inline? Open PDF directly →
Full Text
96,268 characters extracted from source content.
Expand or collapse full text
Lifted Model Construction under Approximate Commutativity Malte Luttermann∗* Affiliation: Institute for Humanities-Centered Artificial Intelligence, University of Hamburg E-mail malte.luttermann,marcel.gehrke,ralf.moeller@uni-hamburg.de Jan Speller∗* Affiliation: Data Science Group, University of Münster E-mail jan.speller,tanya.braun@uni-muenster.de Tanya Braun Affiliation: Data Science Group, University of Münster E-mail jan.speller,tanya.braun@uni-muenster.de Marcel Gehrke Affiliation: Institute for Humanities-Centered Artificial Intelligence, University of Hamburg E-mail malte.luttermann,marcel.gehrke,ralf.moeller@uni-hamburg.de Ralf Möller Affiliation: Institute for Humanities-Centered Artificial Intelligence, University of Hamburg E-mail malte.luttermann,marcel.gehrke,ralf.moeller@uni-hamburg.de Abstract Lifted inference algorithms enable scalable probabilistic inference even for large object domains by leveraging the indistinguishability of objects in a probability distribution. An essential prerequisite for constructing a lifted representation is to identify commutative factors, i.e., functions whose output values are invariant under permutations of a subset of their input values, in a potential-based factorisation. In practice, however, parameters learned from data inevitably deviate even if associated objects are indistinguishable, causing their corresponding factors to be only approximately commutative instead of being exactly commutative. We address this problem by introducing the concept of ε -commutativity, a relaxation of commutativity where output values are only approximately invariant under permutations of input values. Specifically, we show how ε -commutativity can be exploited for lifted model construction, downstream probabilistic inference, and prove strict bounds on the induced approximation error, thereby ensuring the practical applicability of lifted model construction while maintaining highly accurate query results. These theoretical guarantees are confirmed empirically, demonstrating comparable query accuracy at lower runtime. $*$$*$footnotetext: These authors contributed equally to this work. 1 Introduction Uncertain reasoning is a fundamental task in artificial intelligence, where uncertainty is commonly represented through probability distributions over random variables. Probabilistic graphical models such as fg provide a compact way to encode joint distributions over a set of rv by decomposing a distribution into products of local functions, called factors. Even with a factorised representation, the problem of probabilistic inference (i.e., computing marginal or conditional distributions of rv) is intractable in general as the computational cost grows exponentially with the number of rv [3]. To allow for tractable probabilistic inference whose complexity grows polynomially in the number of objects in the underlying domains, lifted inference algorithms exploit the indistinguishability of objects by using a representative for computations [13]. Performing lifted inference, however, requires a lifted representation in which indistinguishable objects are grouped together. The construction of such a lifted representation includes identifying factors that exhibit symmetries and can therefore be grouped together. One important class are commutative factors (that is, factors whose output values are invariant under permutations of a subset of their input values). Whether a factor is commutative depends on the precise output values it maps its input values to, and herein lies a subtle but pervasive practical issue: When numbers are estimated from observational data, two values that should ideally coincide hardly ever do so up to the last digit. Even in simple cases such as counted data, learning can always yield a distribution of values, which makes an otherwise commutative factor fail the strict definition of commutativity, even though the commutativity is clearly present from a modelling perspective. Current state-of-the-art algorithms for detecting commutative factors have no means to tolerate such discrepancies. In this paper, we address this problem by softening the underlying equality requirement, thereby enabling the detection of approximate commutativity and allowing for further compression of fg. Previous work. When dealing with noisy distributions, typical approximate techniques control the deviation on the level of the full (global) probability distribution based on classes of prior distributions [1], as done, e.g., by distortion models such as the constant odds ratio model, which bounds the multiplicative deviation from a nominal reference distribution [12]. In contrast, we consider a factorised distribution and bound individual potentials directly via a local constant-odds-ratio-type neighbourhood on the level of a single factor. Structurally, however, the overall global approximation follows the same guarantees as distortion models. There has also been research on robustness in graph learning against false measurements and outliers [6, 14], whereas our approach relaxes exact structural symmetry in factors for lifted inference. The line of work on lifted probabilistic inference goes back to Poole [15], who introduced pfg as a representation that interleaves first-order logic with probabilistic modelling and lve (lve) as an inference algorithm operating on pfg. A substantial body of subsequent research has refined and extended lve in various directions [18]. One of these refinements includes the introduction of so-called crv [11], which count over the occurrences of range values in the input of a factor instead of explicitly listing possible combinations of input values, thereby exploiting the commutativity of factors. The current state-of-the-art to construct a lifted representation such as a pfg is the acp (acp) algorithm [7]. A core ingredient of acp is to determine, for every factor, a maximum sized subset of commutative arguments such that factors can be compressed by using crv to count over the commutative arguments. To determine maximum sized subsets of commutative arguments, the decor (decor) algorithm [8, 9] is the state-of-the-art. Such lifted model construction techniques have so far focused on approximate factors rather than approximate commutativity [10, 16]. Our contributions. We introduce ε -commutativity, an approximate variant of commutativity in which output values are allowed to deviate depending on a hyperparameter ε . On the basis of ε -commutativity, we show how approximately commutative factors can be compressed by replacing groups of similar values with representative values, thereby simplifying the underlying distribution by giving events of a symmetry set the same value. We further establish a strict bound on the approximation error induced by such a compression, guaranteeing that subsequent inference on the resulting lifted representation remains accurate. Finally, we empirically demonstrate that the approximation error remains well below the theoretical bounds in practice, while the proposed algorithm substantially reduces runtime across a range of parameter settings. Structure of this paper. The remainder of the paper is organised as follows. We first introduce the necessary background on fg and commutative factors therein. We then formalise the concept of ε -commutativity, develop a compression scheme based on ε -commutative representatives, and prove important properties leading to a strict bound on the resulting approximation error. Afterwards, we embed the compression of ε -commutative factors into the acp algorithm for lifted model construction and empirically show that downstream probabilistic inference still produces highly accurate results. Due to space constraints, detailed proofs are relegated to App. 0.A and further experimental results to App. 0.B. 2 Background We briefly introduce the notion of an fg and then formally define what a commutative factor is. An fg compactly encodes a joint probability distribution over rv as a product of factors [4, 5]. In the following, we write range(R)range(R) to denote the values a rv R can take (called range) and :=×R∈range(R)X_ R:=×_R∈ Rrange(R) to denote the Cartesian product over the ranges of a set of rv R. Definition 1 (Factor Graph). An fg is a tuple M=(,,,)M=( R, F, E, ) where =R1,…,Rp R=\R_1,…, R_p\ is a set of rv, =f1,…,fm F=\f_1,…, f_m\ is a set of factor nodes, and =ϕ1,…,ϕm =\ _1,…, _m\ is a set of function definitions (called factors). Each ϕj(ϕj)∈ _j( R_ _j)∈ defines a function ϕj:ϕj→ℝ≥0 _j _ R_ _j _≥ 0 over the Cartesian product of the ranges of its argument sequence of rv ϕj⊆ R_ _j R. The image of ϕj _j consists of non-negative real numbers (potentials), and each factor is non-trivial in the sense that it attains at least one positive value. For each pair of variable node Ri∈R_i∈ R and factor node fj∈f_j∈ F, there is an edge Ri,fj∈⊆R,f∣R∈∧f∈\R_i, f_j\∈ E \\R,f\ R∈ R f∈ F\ if Ri∈ϕjR_i∈ R_ _j. The full joint probability distribution encoded by M for an assignment (R1=r1,…,Rp=rp)(R_1=r_1, …, R_p=r_p) to the rv in R, abbreviated as = R= r, is the normalised product over all factors in M: PM(=) P_M( R= r) =1Zψ()=1Z∏j=1mϕj(ϕj=j), = 1Zψ( r)= 1Z _j=1^m _j( R_ _j= r_j), where j r_j is a projection of r to the argument list of ϕj _j and Z is the normalisation constant, defined as Z=∑∈∏j=1mϕj(ϕj=j)Z= _ r _ R _j=1^m _j( R_ _j= r_j). Example 1 Fig. 1(a) shows an fg M modelling the interplay between the competences ComAComA and ComBComB of two employees AliceAlice and BobBob, respectively, and the revenue RevRev of the company they work for. The ranges of the rv are range(ComA)=range(ComB)=range(Rev)=high,lowrange(ComA)=range(ComB)=range(Rev)=\high, \ and Fig. 1(b) shows the function definition of the factor ϕ3(ComA,ComB,Rev) _3(ComA,ComB,Rev), illustrated as a potential table, i.e., ϕ3(ComA=high,ComB=high,Rev=high)=φ1 _3(ComA=high, ComB=high, Rev=high)= _1, and so on, such that φ1,…,φ6∈ℝ≥0 _1, …, _6 _≥ 0 are non-negative real numbers with φi≠φj _i≠ _j for all i≠ji≠ j. We omit the potential tables of ϕ1(ComA) _1(ComA) and ϕ2(ComB) _2(ComB) for brevity. RevRevComAComAComBComBf1f_1f2f_2f3f_3 (a) ComAComA ComBComB RevRev ϕ3(ComA,ComB,Rev) _3(ComA,ComB,Rev) highhigh highhigh highhigh φ1 _1 highhigh highhigh lowlow φ2 _2 highhigh lowlow highhigh φ3 _3 highhigh lowlow lowlow φ4 _4 lowlow highhigh highhigh φ3 _3 lowlow highhigh lowlow φ4 _4 lowlow lowlow highhigh φ5 _5 lowlow lowlow lowlow φ6 _6 (b) Figure 1: (a) An fg modelling the interplay between the competences of two employees and the revenue of the company they work for. (b) The function definition of ϕ3 _3, where φ1,…,φ6∈ℝ≥0 _1, …, _6 _≥ 0 with φi≠φj _i≠ _j for all i≠ji≠ j. Ex. 1 illustrates that the output of ϕ3(ComA,ComB,Rev) _3(ComA, ComB, Rev) depends only on the number of highly competent employees, not on their identities. For instance, ϕ3(ComA=high,ComB=low,Rev=high)=ϕ3(ComA=low,ComB=high,Rev=high)=φ3 _3(ComA=high, ComB=low, Rev=high)= _3(ComA=low, ComB=high, Rev=high)= _3. Thus, permuting ComAComA and ComBComB leaves the output unchanged—only the count of competences set to highhigh matters. This invariance under permutations is a key property exploited by lifted inference algorithms and motivates the following formal definition of commutativity. Definition 2 (Commutative Factor [7]). Let ϕ(R1,…,Rn)φ(R_1,…,R_n) denote a factor and let ϕ⊆ϕ:=R1,…,Rn C_φ R_φ:=\R_1,…,R_n\ be a subset of ϕφ’s arguments with |ϕ|≥2 C_φ ≥ 2. Then, ϕφ is commutative with respect to ϕ C_φ if for all assignments =(r1,…,rn)∈ϕ r=(r_1,…, r_n) _ R_φ it holds that ϕ(r1,…,rn)=ϕ(rπ(1),…,rπ(n))φ(r_1,…,r_n)=φ(r_π(1),…,r_π(n)) for all permutations π of 1,…,n\1,…,n\ with π(i)=iπ(i)=i for all Ri∉ϕR_i∉ C_φ. We refer to the arguments in ϕ C_φ as commutative arguments. Note that arguments can only be commutative if they have the same range because only arguments with identical ranges can be permuted. Thus, when searching for commutative arguments, only subsets with the same range need to be considered. Consider again ϕ3(ComA,ComB,Rev) _3(ComA,ComB,Rev) from Fig. 1(b). According to Def. 2, ϕ3 _3 is commutative with respect to ComA,ComB\ComA, ComB\. The above definition relies on exact equality of potentials. In practice, however, small estimation errors often break this equality even when the underlying symmetry is still present. The next section therefore introduces approximate commutativity. 3 Approximate Commutativity So far, the definition of a commutative factor requires strict equality among potentials, which we relax here, introducing the notion of ε -commutativity based on the idea of ε -equivalence [10], establish its fundamental properties, and derive the bounds needed for its practical application in lifted model construction. We begin to introduce the more general notion of ε -equivalence between two potentials φ1,φ2∈ℝ≥0 _1, _2 _≥ 0, written as φ1=εφ2 _1=_ _2, which holds if φ1∈[φ2⋅(1−ε),φ2⋅(1+ε)] and φ2∈[φ1⋅(1−ε),φ1⋅(1+ε)]. _1∈[ _2·(1- ), _2·(1+ )] and _2∈[ _1·(1- ), _1·(1+ )]. (1) Two factors are ε -equivalent if there exists a permutation of arguments such that Eq. 1 holds for all pairwise row comparisons of potentials. Combining ε -equivalence and commutativity naturally leads to the notion of ε -commutativity. Definition 3 (ε -Commutative Factor). Let ϕ(R1,…,Rn)φ(R_1,…,R_n) denote a factor, let ϕ⊆ϕ C_φ R_φ be a subset of its arguments with |ϕ|≥2 C_φ ≥ 2, and let ε∈[0,1] ∈[0,1]. Then, ϕφ is ε -commutative with respect to ϕ C_φ if for all assignments (r1,…,rn)∈ϕ(r_1,…, r_n) _ R_φ and all permutations π∈Πϕ:=π∈Sn∣π(i)=i for all Ri∉ϕ, π∈ _ C_φ:= \π∈ S_n π(i)=i for all R_i∉ C_φ \, where SnS_n is the symmetric group over 1,…,n\1,…,n\, the potentials ϕ(r1,…,rn)φ(r_1,…,r_n) and ϕ(rπ(1),…,rπ(n))φ(r_π(1),…,r_π(n)) are ε -equivalent, i.e., ϕ(r1,…,rn) φ(r_1,…,r_n) ∈[ϕ(rπ(1),…,rπ(n)) ∈[φ(r_π(1),…,r_π(n)) ⋅(1−ε),ϕ(rπ(1),…,rπ(n)) ·(1- ),φ(r_π(1),…,r_π(n)) ⋅(1+ε)] and ·(1+ )] and ϕ(rπ(1),…,rπ(n)) φ(r_π(1),…,r_π(n)) ∈[ϕ(r1,…,rn) ∈[φ(r_1,…,r_n) ⋅(1−ε),ϕ(r1,…,rn) ·(1- ),φ(r_1,…,r_n) ⋅(1+ε)]. ·(1+ )]. We refer to the arguments in ϕ C_φ as ε -commutative arguments. Note that, for the choice of ε=0 =0, ε -commutativity reduces to strict commutativity. As illustrated in Table 1(b), the commutativity of a factor can be exploited to obtain a more compact representation of the factor by introducing a crv that groups the commutative arguments such that the original potentials are replaced by aggregated potentials. Here, ComAComA and ComBComB are not listed individually but have been replaced by a crv #E[Com(E)]\#_E[Com(E)] that counts the number of employees with a certain competence (i.e., [2,0][2,0] stands for two employees with a high competence and none with a low competence, [1,1][1,1] stands for one employee with a high competence and one with a low competence, and [0,2][0,2] stands for two employees with a low competence and none with a high competence). Given a commutative factor such as ϕ3 _3 from Fig. 1(b), all assignments that differ only by a permutation of the range values of the commutative arguments share the same potential, so choosing φi∗=φi ^*_i= _i preserves the semantics exactly. However, for an ε -commutative factor such as ϕφ from Table 1(a), potentials corresponding to assignments only differ by a permutation on the commutative arguments may deviate by a factor of up to (1±ε)(1± ), and hence collapsing them into a single potential φi∗ ^*_i inevitably discards information (e.g., φ3∗ ^*_3 must be chosen to represent both φ3 _3 and φ3′ _3 at the same time). We therefore seek to choose φi∗ ^*_i such that its deviation from the original potentials is minimised. ComAComA ComBComB RevRev ϕ(ComA,ComB,Rev)φ(ComA,ComB,Rev) highhigh highhigh highhigh φ1 _1 highhigh highhigh lowlow φ2 _2 highhigh lowlow highhigh φ3 _3 highhigh lowlow lowlow φ4 _4 lowlow highhigh highhigh φ3′ _3 lowlow highhigh lowlow φ4′ _4 lowlow lowlow highhigh φ5 _5 lowlow lowlow lowlow φ6 _6 (a) #E[Com(E)]\#_E[Com(E)] RevRev ϕ(#E[Com(E)],Rev)φ(\#_E[Com(E)],Rev) [2,0][2,0] highhigh φ1∗ ^*_1 [2,0][2,0] lowlow φ2∗ ^*_2 [1,1][1,1] highhigh φ3∗ ^*_3 [1,1][1,1] lowlow φ4∗ ^*_4 [0,2][0,2] highhigh φ5∗ ^*_5 [0,2][0,2] lowlow φ6∗ ^*_6 (b) Table 1: (a) An exemplary factor ϕ(ComA,ComB,Rev)φ(ComA,ComB,Rev) with ε -commutative arguments ComA,ComB\ComA, ComB\ provided that φ3 _3 and φ3′ _3 as well as φ4 _4 and φ4′ _4 are ε -equivalent. (b) A compressed representation of ϕ(ComA,ComB,Rev)φ(ComA,ComB,Rev) from (a) using a crv to represent the ε -commutative arguments ComA,ComB\ComA, ComB\. Example 2 Consider the factor ϕ(ComA,ComB,Rev)φ(ComA,ComB,Rev) from Table 1(a). Given that φ3 _3 and φ3′ _3 as well as φ4 _4 and φ4′ _4 are ε -equivalent for some ε∈[0,1] ∈[0,1], ϕφ is ε -commutative with respect to ComA,ComB\ComA, ComB\. In the following, we aim to find an optimal representative factor to compress an ε -commutative factor such that the underlying semantics is preserved as much as possible. To do so, we need a few theoretical properties induced by the notion of ε -commutativity. The following lemma, which has been proven only across different factors [10, Lemma 6], establishes a useful consequence of the symmetric definition of ε -commutativity and serves as a tool to derive subsequent bounds. Lemma 1 Let ϕφ denote a factor that is ε -commutative with respect to a subset of its arguments ϕ C_φ. Then, for all permutations π∈Πϕπ∈ _ C_φ, it holds that ϕ(r1,…,rn) φ(r_1,…,r_n) ∈[ϕ(rπ(1),…,rπ(n)) ∈[φ(r_π(1),…,r_π(n)) ⋅11+ε,ϕ(rπ(1),…,rπ(n)) · 11+ ,φ(r_π(1),…,r_π(n)) ⋅(1+ε)] and ·(1+ )] and ϕ(rπ(1),…,rπ(n)) φ(r_π(1),…,r_π(n)) ∈[ϕ(r1,…,rn) ∈[φ(r_1,…,r_n) ⋅11+ε,ϕ(r1,…,rn) · 11+ ,φ(r_1,…,r_n) ⋅(1+ε)]. ·(1+ )]. The proof follows the same structural argument as [10, Lemma 6], using the symmetric definition of ε -commutativity. Details are given in App. 0.A. Before we turn our attention to the compression of an ε -commutative factor, we briefly state two important structural properties of ε -commutativity, which are algorithmically relevant when it comes to detecting ε -commutativity of a factor (which needs to be done before the compression can take place). A natural question is whether ε -commutativity with respect to a set is inherited by its subsets (as it is the case for the exact version of commutativity [9, Prop. 10]). Proposition 1 Let ϕφ be ε -commutative with respect to ϕ C_φ. Then, ϕφ is ε -commutative with respect to every subset ϕ′⊆ϕ C_φ C_φ satisfying |ϕ′|≥2 C_φ ≥ 2. Proof. Since, ϕ′⊆ϕ C_φ C_φ, we have Πϕ′⊆Πϕ _ C _φ _ C_φ. Hence, by Def. 3, for all π∈Πϕπ∈ _ C_φ and assignments =(r1,…,rn) r=(r_1,…,r_n), it holds that ϕ() φ( r) ∈[ϕ(rπ(1),…,rπ(n)) ∈[φ(r_π(1),…,r_π(n)) ⋅(1−ε),ϕ(rπ(1),…,rπ(n)) ·(1- ),φ(r_π(1),…,r_π(n)) ⋅(1+ε)] and ·(1+ )] and ϕ(rπ(1),…,rπ(n)) φ(r_π(1),…,r_π(n)) ∈[ϕ() ∈[φ( r) ⋅(1−ε),ϕ() ·(1- ),φ( r) ⋅(1+ε)]. ·(1+ )]. Since Πϕ′⊆Πϕ _ C _φ _ C_φ, the same relations hold for all π′∈Πϕ′π ∈ _ C _φ. ∎ Prop. 1 shows that ε -commutativity is preserved when moving from a set of rv to its subsets. Hence, a factor that is commutative with respect to ϕ′ C_φ may be ε -commutative with respect to a strict superset ϕ⊋ϕ′ C_φ C_φ , thereby enabling further compression of the original factor. An important follow-up question is whether local ε -commutativity of smaller subsets implies this also for their union, which is indeed the case for exact commutativity [9, Theorem 11] and gives rise to an efficient algorithm to compute subsets of commutative arguments [9, Algorithm 2]. The following theorem shows that the corresponding property does not hold for ε -commutativity, implying that computing subsets of ε -commutative arguments is more sophisticated than computing subsets of strictly commutative arguments. Theorem 3.1 ε -commutativity is not closed under unions of sets with respect to which a factor ϕφ is ε -commutative. Proof. Let (r1,r2,r3)∈×i=13high,medium,low(r_1,r_2,r_3)∈×_i=1^3\high, , \ denote any assignment to the rv R1,R2,R3R_1,R_2,R_3. Let ε be 0.10.1. The potentials of the factor ϕφ are given by R1R2R3ϕ(R1,R2,R3)highmediumlow1highlowmedium1.1mediumhighlow1.1mediumlowhigh1.21lowhighmedium1.21lowmediumhigh1.1 array[]c|cR_1&R_2&R_3&φ(R_1,R_2,R_3)\\ &medium&low&1\\ high&low&medium&1.1\\ medium&high&low&1.1\\ medium&low&high&1.21\\ low&high&medium&1.21\\ low&medium&high&1.1\\ array -4.26773pt All non-listed assignments are mapped to the potential 11. ϕφ is ε -commutative with respect to all individual pairs R1,R2\R_1, R_2\, R1,R3\R_1, R_3\, and R2,R3\R_2, R_3\, but not with respect to the set R1,R2,R3\R_1, R_2, R_3\. Consider the assignment (r1,r2,r3)=(high,medium,low)(r_1, r_2, r_3)=(high, , ) and the permutation π(1)=3,π(2)=1,π(3)=2π(1)=3, π(2)=1, π(3)=2, (cycle of two transpositions), which maps (high,medium,low)(high, , ) to (rπ(1),rπ(2),rπ(3))=(r3,r1,r2)=(low,high,medium)(r_π(1), r_π(2), r_π(3))=(r_3, r_1, r_2)=(low, , ). However, ϕ(high,medium,low)=1φ(high, , )=1 is not an element of the interval [ϕ(low,high,medium)⋅(1−0.1),ϕ(low,high,medium)⋅(1+0.1)]=[1.089,1.331][φ(low, , )·(1-0.1),φ(low, , )·(1+0.1)]=[1.089, 1.331]. Thus, ϕφ is not ε -commutative with respect to R1,R2,R3\R_1, R_2, R_3\.∎ Theorem 3.1 implies that the algorithm presented in [9, Algorithm 2] to efficiently compute a maximum sized subset of commutative arguments cannot directly be transferred to compute a subset of ε -commutative arguments instead. We next turn our attention to the compression of an ε -commutative factor, which is performed by replacing it with a smaller representative factor. 3.1 Replacement of Potentials by Representative The construction developed in this subsection formalises the aggregation of potentials over symmetry sets induced by permutations of ε -commutative arguments. We first introduce symmetrised representative factors as weighted representatives over symmetry sets and then study the algebraic structure induced by the permutation group Πϕ _ C_φ, which partitions the assignment space into equivalence classes of pairwise ε -equivalent potentials. Definition 4 (Symmetrised Representative Factor). Let ϕ(R1,…,Rn)φ(R_1,…,R_n) be a factor, which is ε -commutative with respect to ϕ⊆ϕ=R1,…,Rn C_φ R_φ=\R_1,…,R_n\. For an assignment =(r1,…,rn)∈ϕ r=(r_1,…,r_n) _ R_φ, the symmetrised representative factor ϕ∗φ^* associated with ϕφ is defined by ϕ∗():=∑′∈ϕ()ω′⋅ϕ(′), φ^*( r):= _ r ∈ S_φ( r) _ r ·φ( r ), where ϕ():=(rπ(1),…,rπ(n))|π∈Πϕ S_φ( r):= \(r_π(1),…,r_π(n))\; |\;π∈ _ C_φ \ denotes the symmetry set of r under permutations of the ε -commutative arguments, and where the weights satisfy ω′≥0 _ r ≥ 0 and ∑′∈ϕ()ω′=1 _ r ∈ S_φ( r) _ r =1. To better understand why such a construction is possible, we first investigate the structure underlying these symmetry classes. This leads us to examine Πϕ _ C_φ, which is shown to be closed under composition and inversion in the following. Lemma 2 For a set ϕ⊆ϕ=R1,…,Rn C_φ R_φ=\R_1,…,R_n\, Πϕ _ C_φ is a subgroup of SnS_n. Proof. By definition πid∈Πϕ _id∈ _ C_φ. If π1,π2∈Πϕ _1, _2∈ _ C_φ, then (π1∘π2)(i)=π1(π2(i))=π1(i)=i( _1 _2)(i)= _1( _2(i))= _1(i)=i for all Ri∉ϕR_i∉ C_φ, resulting in closed group operations π1∘π2∈Πϕ _1 _2∈ _ C_φ. If π∈Πϕπ∈ _ C_φ, then π∈Snπ∈ S_n due to Πϕ⊆Sn _ C_φ S_n. SnS_n is a group and therefore π−1∈Snπ^-1∈ S_n. This means that for all i with Ri∉ϕR_i∉ C_φ it holds that i=πid(i)=(π−1∘π)(i)=π−1(π(i))=π−1(i)i= _id(i)=(π^-1 π)(i)=π^-1(π(i))=π^-1(i), which means that the inverse π−1π^-1 is also in Πϕ _ C_φ. ∎ This subgroup naturally induces a group operation of Πϕ _ C_φ on the assignment space ϕX_ R_φ via (r1,…,rn)↦(rπ(1),…,rπ(n))for π∈Πϕ(r_1,…,r_n)\; \;(r_π(1),…,r_π(n))\;for π∈ _ C_φ, whose properties are inherited by the corresponding symmetry sets ϕ() S_φ( r). Hence, symmetry sets are precisely the orbits of this group operation. Corollary 1 Let ϕ(R1,…,Rn)φ(R_1,…,R_n) be a factor, which is ε -commutative with respect to ϕ⊆ϕ=R1,…,Rn C_φ R_φ=\R_1,…,R_n\. If ′∈ϕ() r ∈ S_φ( r), then ϕ(′)=ϕ() S_φ( r )= S_φ( r). Proof. As ′∈ϕ() r ∈ S_φ( r), there exists π1∈Πϕ _1∈ _ C_φ such that ′=(rπ1(1),…,rπ1(n)) r =(r_ _1(1),…,r_ _1(n)). Let ′∈ϕ(′) r ∈ S_φ( r ). Then, there is π2∈Πϕ _2∈ _ C_φ such that ′=(rπ2(1)′,…,rπ2(n)′)=(rπ1(π2(1)),…,rπ1(π2(n))) r =(r _ _2(1),…,r _ _2(n))=(r_ _1( _2(1)),…,r_ _1( _2(n))). Since Πϕ _ C_φ is a subgroup of SnS_n, it is closed under composition, hence π1∘π2∈Πϕ _1 _2∈ _ C_φ. Therefore ′∈ϕ() r ∈ S_φ( r), which shows ϕ(′)⊆ϕ() S_φ( r ) S_φ( r). The reverse inclusion follows analogously for π1−1,π2−1∈Πϕ _1^-1, _2^-1∈ _ C_φ. ∎ While the previous result describes how ε -commutativity behaves on the level of argument subsets, the following lemma establishes the induced equivalence on the level of potentials via ε -equivalence. Lemma 3 Let ϕ(R1,…,Rn)φ(R_1,…,R_n) be ε -commutative with respect to ϕ C_φ. Then, all potentials induced by assignments within the same symmetry set are pairwise ε -equivalent, i.e., if ′,′∈ϕ() r , r ∈ S_φ( r), then ϕ(′)=εϕ(′)φ( r )=_ φ( r ). Proof. Let ′,′∈ϕ() r , r ∈ S_φ( r). Then there exist permutations π1,π2∈Πϕ _1, _2∈ _ C_φ such that ′=(rπ1(1),…,rπ1(n)) r =(r_ _1(1),…,r_ _1(n)) and ′=(rπ2(1),…,rπ2(n)) r =(r_ _2(1),…,r_ _2(n)). Since Πϕ _ C_φ is a subgroup of SnS_n (Lemma 2), it is closed under composition and taking inverses. Hence, τ:=π2∘π1−1∈Πϕτ:= _2 _1^-1∈ _ C_φ. Therefore, ′=(rτ(1)′,…,rτ(n)′) r =(r _τ(1),…,r _τ(n)). Because ϕφ is ε -commutative with respect to ϕ C_φ, it follows from Def. 3 that ϕ(′)∈[ϕ(′)⋅(1−ε),ϕ(′)⋅(1+ε)]φ( r )∈[φ( r )·(1- ),φ( r )·(1+ )] and ϕ(′)∈[ϕ(′)⋅(1−ε),ϕ(′)⋅(1+ε)].φ( r )∈[φ( r )·(1- ),φ( r )·(1+ )]. Hence, it holds that ϕ(r1′,…,rn′)=εϕ(r1′,…,rn′)φ(r_1 ,…,r_n )=_ φ(r_1 ,…,r_n ). ∎ Thus, we can also view ϕ()=:[]ϕ S_φ( r)=:[ r]_φ as the equivalence class of the equivalence relation ∼ on ϕX_ R_φ induced by the group operation of Πϕ _ C_φ via ∼′:⟺∃π∈Πϕ:(r1′,…,rn′)=(rπ(1),…,rπ(n)). r r : ∃π∈ _ C_φ (r_1 ,…,r_n )=(r_π(1),…,r_π(n)). Consequently, the quotient space ϕ/∼X_ R_φ/ is well-defined and can be identified with the set of all symmetry sets. Hence, there exists a representative set ℛϕ⊂ϕX_R_φ _ R_φ containing exactly one element per equivalence class, inducing a bijection ϕ/∼≅[]ϕ∣∈ℛϕ=ϕ()∣∈ℛϕ. _ R_φ/ \; \;\[ r]_φ r _R_φ\=\ S_φ( r) r _R_φ\. Different symmetry sets (equivalence classes) of the same factor may induce different weighting schemes. Within each equivalence class, however, the weights must be chosen consistently with the quotient structure ϕ/∼X_ R_φ/ so that every class contributes exactly once to the representative potential (for the size of the symmetry set, see Section 0.A.1). This raises the question whether replacing potentials by symmetrised representatives preserves ε -equivalence of factors. Theorem 3.2 Let ϕφ be ε -commutative with respect to ϕ C_φ and let ϕ∗φ^* be its symmetrised representative factor for ε∈[0,1] ∈[0,1]. Then, ϕφ and ϕ∗φ^* are ε -equivalent. Proof. By Lemma 3, all potentials ϕ(′)φ( r ) with ′∈ϕ() r ∈ S_φ( r) are pairwise ε -equivalent. Hence, by [17, Theorem 15], any weighted mean ∑′∈ϕ()ω′⋅ϕ(′) _ r ∈ S_φ( r) _ r ·φ( r ) is also ε -equivalent to ϕ(′)φ( r ). Applied row-wise to all assignments and potentials relative to their equivalence classes, this yields ε -equivalent factors. ∎ Choosing the arithmetic mean ϕ¯ φ as the symmetrised representative factor arises as a trivial special case of Thm. 3.2 by assigning uniform weights ω′:=1|ϕ()| _ r := 1 S_φ( r) on ϕ() S_φ( r) for which ∑′∈ϕ()ω′=1 _ r ∈ S_φ( r) _ r =1 holds, yielding ϕ∗()=ϕ¯()φ^*( r)= φ( r). Corollary 2 Let ϕφ be ε -commutative with respect to ϕ C_φ and let the mean ϕ∗():=ϕ¯():=1|ϕ()|∑′∈ϕ()ϕ(′), φ^*( r):= φ( r):= 1| S_φ( r)| _ r ∈ S_φ( r)φ( r ), (2) be defined with weights ω′:=1|ϕ()| _ r := 1 S_φ( r) for ′∈ϕ() r ∈ S_φ( r) for a given ε∈[0,1] ∈[0,1]. Then ϕ∗φ^* is a symmetrised representative factor of ϕφ and is ε -equivalent to ϕφ. The mean is particularly attractive as it treats all symmetric assignments uniformly avoiding bias towards specific permutations and minimises the squared deviation [10]. It is also optimal with respect to the squared deviation in the sense that, when all values ϕ(′)φ( r ) are replaced by the same representative within the group ∈ϕ() r∈ S_φ( r), the resulting deviation from the original factor is minimised. These properties make it a natural choice for the symmetrised representative factor in practical implementations (see Sec. 4 for experiments). However, when prior knowledge indicates a bias toward specific arguments in the underlying data, or when domain expertise is available, the weights assigned to individual arguments of the original factor can always be adapted accordingly. 3.2 Asymptotic Bounds To quantify the approximation error induced by symmetrisation, we next analyse the resulting deviation between the original model and the model obtained by symmetrising ε -commutative factors. We make use of the following symmetric distance measure, which allows us to bound the change in query results [2, 10]. Definition 5 ([2]). The symmetric distance DCD(PM,PM′)D_CD(P_M,P_M ) between two distributions PMP_M and PM′P_M introduced in [2] (see [10] for details) is defined as DCD(PM,PM′):= D_CD(P_M,P_M ):= lnmaxPM′()PM()−lnminPM′()PM() _ r P_M ( r)P_M( r)- _ r P_M ( r)P_M( r) (3) = = lnmaxψ′()ψ()−lnminψ′()ψ(). _ r ψ ( r)ψ( r)- _ r ψ ( r)ψ( r). (4) With this measure at hand, we first derive a general bound for arbitrary weighting schemes. Theorem 3.3 Let M be an fg with factors ϕ1,…,ϕm _1,…, _m, of which ϕ1,…,ϕk _1,…, _k with 0≤k≤m0≤ k≤ m are ε -commutative with respect to ϕ1,…,ϕk C_ _1,…, C_ _k, respectively. Let M′M be the fg with factors ϕ1∗,…,ϕk∗,ϕk+1,…,ϕm _1^*,…, _k^*, _k+1,…, _m, where ε -commutative factors of M are replaced by their symmetrised representative factors. Further, let PMP_M and PM′P_M denote the underlying full joint probability distributions encoded by M and M′M , respectively. Then, it holds that DCD(PM,PM′) D_CD(P_M,P_M ) ≤ln(1+ε)2k. ≤ (1+ )^2k. Proof. According to Def. 3, every updated potential ϕi∗(i) _i^*( r_i) in M′M differs from its original potential ϕi(i) _i( r_i) in M by at most a factor (1±ε)(1± ) for i=1,…,ki=1,…,k, while all remaining factors i>ki>k are left unchanged. Since ψ()=∏j=1mϕj(j)ψ( r)= _j=1^m _j( r_j) for any assignment r, using Lemma 1 we obtain ψ′() ψ ( r) ≥∏j=1kϕj(j)⋅11+ε⋅∏j=k+1mϕj(j)=1(1+ε)k⋅∏j=1mϕj(j), and ≥ _j=1^k _j( r_j)· 11+ · _j=k+1^m _j( r_j)= 1(1+ )^k· _j=1^m _j( r_j), and ψ′() ψ ( r) ≤∏j=1kϕj(j)⋅(1+ε)⋅∏j=k+1mϕj(j)=(1+ε)k⋅∏j=1mϕj(j). ≤ _j=1^k _j( r_j)·(1+ )· _j=k+1^m _j( r_j)=(1+ )^k· _j=1^m _j( r_j). Consequently, minψ′()ψ() _ r ψ ( r)ψ( r) ≥1(1+ε)k⋅∏j=1mϕj(j)∏j=1mϕj(j)=1(1+ε)k,and ≥ 1(1+ )^k·Π _j=1^m _j( r_j)Π _j=1^m _j( r_j)= 1(1+ )^k,~and maxψ′()ψ() _ r ψ ( r)ψ( r) ≤(1+ε)k⋅∏j=1mϕj(j)∏j=1mϕj(j)=(1+ε)k, ≤ (1+ )^k·Π _j=1^m _j( r_j)Π _j=1^m _j( r_j)=(1+ )^k, where j∈ϕj r_j _ R_ _j denotes the projection of ∈ r _ R. Substituting these bounds into Eq. 4 yields DCD(PM,PM′)≤ln(1+ε)k−ln1/(1+ε)k=ln(1+ε)2kD_CD(P_M,P_M )≤ (1+ )^k- 1/(1+ )^k= (1+ )^2k. ∎ For the special case of arithmetic averaging, we can sharpen this bound. Lemma 4 Let ϕφ be an ε -commutative factor with respect to ϕ C_φ, let ℛϕ=∪˙j=1ljX_R_φ= ∪_j=1^l\ r^j\ be a set of disjoint representatives j r^j for all disjoint equivalence classes ∪˙j=1l[j]ϕ=∪˙j=1lϕ(j)=ϕ ∪_j=1^l[ r^j]_φ= ∪_j=1^l S_φ( r^j)=X_ R_φ ordered by size such that m1:=|[1]ϕ|≥…≥ml:=|[l]ϕ|≥1m_1:= [ r^1]_φ ≥…≥ m_l:= [ r^l]_φ ≥ 1, and let ϕ∗φ^* be the symmetrised representative factor via the mean as in Eq. 2. Then, 1≤maxϕ∗()ϕ()minϕ∗()ϕ()≤(1+m2−1m2ε)(1+ε)1+1m1ε. 1\;≤\; _ r φ^*( r)φ( r) _ r φ^*( r)φ( r)\;≤\; (1+ m_2-1m_2 )(1+ )1+ 1m_1 . Condensed Proof (Longer Version inApp. 0.A). The mean ϕ∗()φ^*( r) is uniquely determined within each equivalence class [j]ϕ[ r^j]_φ. First, observe that for every equivalence class [j]ϕ[ r^j]_φ and all ′,′∈[j]ϕ r , r ∈[ r^j]_φ, Lemma 3 implies pairwise ε -equivalence, so the potentials ϕ(′)φ( r ) within one equivalence class [j]ϕ[ r^j]_φ can be ordered 0≤11+εϕ(j,max)≤ϕ(j,min)≤ϕ(′)≤ϕ(j,max)≤ϕ(j,min)(1+ε), 0≤ 11+ φ( r^j, )≤φ( r^j, )≤φ( r )≤φ( r^j, )≤φ( r^j, )(1+ ), where ϕ(j,max):=max′∈[j]ϕϕ(′)φ( r^j, ):= _ r ∈[ r^j]_φ( r ) and ϕ(j,min):=min′∈[j]ϕϕ(′)φ( r^j, ):= _ r ∈[ r^j]_φ( r ). When the maximum and minimum originate from two different equivalence classes [i]ϕ[ r^i]_φ and [j]ϕ[ r^j]_φ with i≠ji≠ j, the worst-case assignments are independent. For the maximum choose ϕ()=ϕ(i,min)φ( r)=φ( r^i, ), while all remaining potentials in the same equivalence class attain their maximal admissible value ϕ(′):=ϕ(i,max)=(1+ε)ϕ(i,min)φ( r ):=φ( r^i, )=(1+ )φ( r^i, ) for all ′∈[i]ϕ∖ r ∈[ r^i]_φ \ r\. This yields max∈[i]ϕϕ∗()ϕ() _ r∈[ r^i]_φ φ^*( r)φ( r) =(ϕ(i,min)+(|[i]ϕ|−1)(1+ε)ϕ(i,min))/|[i]ϕ|ϕ(i,min)=1+(mi−1)εmi = (φ( r^i, )+( [ r^i]_φ -1)(1+ )φ( r^i, ))/ [ r^i]_φ φ( r^i, )=1+ (m_i-1) m_i For the minimum choose ϕ()=ϕ(j,max)φ( r)=φ( r^j, ), while all remaining values in the same equivalence class attain their minimal admissible value ϕ(′):=ϕ(j,min)=11+εϕ(i,max)φ( r ):=φ( r^j, )= 11+ φ( r^i, ) for all ′∈[j]ϕ∖ r ∈[ r^j]_φ \ r\. Consequently, min∈[j]ϕϕ∗()ϕ() _ r∈[ r^j]_φ φ^*( r)φ( r) =((|[j]ϕ|−1)11+εϕ(j,max)+ϕ(j,max))/|[j]ϕ|ϕ(j,max)=1+1mjε1+ε. = (( [ r^j]_φ -1) 11+ φ( r^j, )+φ( r^j, ))/ [ r^j]_φ φ( r^j, )= 1+ 1m_j 1+ . Observe, that 1+(mi−1)εmi1+ (m_i-1) m_i is monotonically increasing in mim_i, whereas 1+1mjε1+ε 1+ 1m_j 1+ is monotonically decreasing in mjm_j. Hence, the largest equivalence classes by size produce the extremal deviations. To determine which class size appear in the numerator and denominator, consider the monotonically decreasing g(x)=(1+x−1xε)(1+1xε)g(x)= (1+ x-1x\; ) (1+ 1x ) for x≥2x≥ 2. Therefore, for x1,x2∈ℕ≥2x_1,x_2 _≥ 2 it follows: g(x1) g(x_1) ≥g(x2)⇔1+x1−1x1ε1+1x2ε≥1+x2−1x2ε1+1x1ε. ≥ g(x_2)\;\; \;\; 1+ x_1-1x_1\; 1+ 1x_2 ≥ 1+ x_2-1x_2\; 1+ 1x_1 . Consequently, the sharpest bound is obtained by using x1=m2x_1=m_2 and x2=m1x_2=m_1. When both extrema originate from the same equivalence class, ϕ∗()=ϕ∗(′)φ^*( r)=φ^*( r ) for all ,′∈[j]ϕ r, r ∈[ r^j]_φ, the quotient is maximised via ϕ()=ϕ(j,min)=11+εϕ(j,max)φ( r)=φ( r^j, )= 11+ φ( r^j, ) and ϕ(′)=ϕ(j,max)=(1+ε)ϕ(j,min)φ( r )=φ( r^j, )=(1+ )φ( r^j, ), leading to smaller values max∈[j]ϕϕ∗()ϕ()min′∈[j]ϕϕ∗(′)ϕ(′)=max∈[j]ϕ1ϕ()min′∈[j]ϕ1ϕ(′)≤1ϕ(j,min)1(1+ε)ϕ(j,min)=1+ε. _ r∈[ r^j]_φ φ^*( r)φ( r) _ r ∈[ r^j]_φ φ^*( r )φ( r )\;= _ r∈[ r^j]_φ 1φ( r) _ r ∈[ r^j]_φ 1φ( r )≤ 1φ( r^j, ) 1(1+ )φ( r^j, )=1+ . ∎ Combining the class-wise extremal bounds yields the final global statement for the representative mean-construction, which we show next. Theorem 3.4 Let M be an fg with factors ϕ1,…,ϕm _1,…, _m, of which ϕ1,…,ϕk _1,…, _k with 0≤k≤m0≤ k≤ m are ε -commutative with respect to ϕ1,…,ϕk C_ _1,…, C_ _k, respectively. Let ℛϕi=∪˙j=1liijX_R_ _i= ∪_j=1^l_i\ r_i^j\ be the set of disjoint representatives ij r^j_i for all equivalence classes ∪˙j=1li[ij]ϕi=ϕi ∪_j=1^l_i[ r^j_i]_ _i=X_ R_ _i ordered by size with m1i:=|[i1]ϕi|≥…≥mli:=|[il]ϕi|≥1m_1_i:= [ r^1_i]_ _i ≥…≥ m_l_i:= [ r^l_i]_ _i ≥ 1. Let M′M be the fg obtained by M by replacing each factor ϕi _i by its mean-based symmetrised representative factor ϕi∗ _i^* as in Eq. 2. Then, for the induced distributions PMP_M and PM′P_M and ε>0 >0, it holds that DCD(PM,PM′) D_CD(P_M,P_M ) ≤ln∏i=1k(1+m2i−1m2iε)(1+ε)1+1m1iε<ln(1+ε)2k. ≤ \; _i=1^k (1+ m_2_i-1m_2_i )(1+ )1+ 1m_1_i < \; (1+ )^2k. Proof. The statement follows by factorisation of the joint potential, the determination of the extrema on a projected factor-level instead of a global assignment-level, and the class-wise bound from Lemma 4 for the monotonic logarithm. DCD D_CD (PM,PM′)=Eq. 4lnmaxψ′()ψ()−lnminψ′()ψ() (P_M,P_M ) @crefcreftype~refnumeq:eacp_distance_measure= \; _ r ψ ( r)ψ( r)- \; _ r ψ ( r)ψ( r) =lnmax∏i=1kϕi∗(i)∏i=k+1mϕi(i)∏i=1mϕi(i)−lnmin∏i=1kϕi∗(i)∏i=k+1mϕi(i)∏i=1mϕi(i) = \; _ r _i=1^k _i^*( r_i) _i=k+1^m _i( r_i) _i=1^m _i( r_i)- \; _ r _i=1^k _i^*( r_i) _i=k+1^m _i( r_i) _i=1^m _i( r_i) =lnmax∏i=1kϕi∗(i)ϕi(i)−lnmin∏i=1kϕi∗(i)ϕi(i) = \; _ r _i=1^k _i^*( r_i) _i( r_i)- \; _ r _i=1^k _i^*( r_i) _i( r_i) ≤ln∏i=1kmaxiϕi∗(i)ϕi(i)−ln∏i=1kminiϕi∗(i)ϕi(i)=ln∏i=1kmaxiϕi∗(i)ϕi(i)miniϕi∗(i)ϕi(i) ≤ \; _i=1^k _ r_i _i^*( r_i) _i( r_i)- \; _i=1^k _ r_i _i^*( r_i) _i( r_i)= \; _i=1^k _ r_i _i^*( r_i) _i( r_i) _ r_i _i^*( r_i) _i( r_i) ≤Lemma 4ln∏i=1k(1+m2i−1m2iε)(1+ε)1+1m1iε. @crefcreftype~refnumlemma:bound≤ \; _i=1^k (1+ m_2_i-1m_2_i )(1+ )1+ 1m_1_i . ∎ Even more precisely, the bound is sharp in the general non-trivial case. Theorem 3.5 The bound given in Thm. 3.4 is optimal. Proof Sketch. Ex. 3 in App. 0.A uses the construction from the proof of Lemma 4 per factor, hits the bound, and is therefore sharp. ∎ Note that the choice of a multiplicative relaxation in Def. 3 is what makes this bound attainable in the first place, as DCD_CD is based on quotients of potentials and only relies on relative sizes. An additive relaxation, requiring permuted potentials differ by at most a constant, would lead to arbitrary large deviations. 4 Experiments We complement our theoretical results with an empirical evaluation assessing to what extent ε -commutativity translates into practical benefits for lifted model construction and downstream inference. In particular, we answer the question of how the trade-off between higher compression and accuracy of query results behaves when compressing ε -commutative factors. Concretely, we compare the run time of lve on the compressed model returned by the exact acp algorithm (which is only able to compress strictly commutative factors) to the run time of lve on the compressed model returned by its ε -relaxed variant using the mean as the symmetrised representative factor (denoted as “acp ±ε± ” in the following) and measure the deviation of the query results, quantified by the per-query quotient p′/p /p between the query result (i.e., marginal probability) p′p obtained on the acp ±ε± -compressed model and the query result p obtained on the exact acp-compressed model. For our experiments, we use the same input fg as in the original acp paper [7] and add noise to the potentials of the (strictly) commutative factors to obtain ε -commutative factors. We only manipulate commutative factors and leave the remaining factors unchanged to investigate the effect of ε -commutativity on the compression-accuracy trade-off in isolation (the effect of grouping different factors that are approximately equal has been investigated in [10] and hence, we only consider indistinguishability within factors — characterised by ε -commutativity — and no indistinguishability between factors). Specifically, each input fg contains between 2d+12d+1 and d⋅⌊log2(d)⌋+2d+2d· _2(d) +2d+2 rv with Boolean range and between 2d+12d+1 and d⋅⌊log2(d)⌋+d+2d· _2(d) +d+2 factors, where d∈2,4,8,12,16,20d∈\2, 4, 8, 12, 16, 20\ controls the size of the fg. Each input fg contains k∈1,3,7k∈\1, 3, 7\ ε -commutative factors, where ε∈0.001,0.01,0.1 ∈\0.001, 0.01, 0.1\. The ε -commutative factors are obtained by multiplying the potentials of the (strictly) commutative factors by a uniform sample from [1,1+ε][1,1+ ]. 1030100300248121620domain size ddtime (ms)LVE (ACP)LVE (ACP ±ε± ) (a) lve run time (ms). 0.40.60.81.01.21.41.6248121620domain size ddp′/p /p (b) Query result quotient p′/p /p. Figure 2: Downstream lifted inference performance, averaged over all generated instances and queries. (a) Run time of lve on the compressed model returned by acp and its ε -relaxed variant (acp ±ε± ). (b) Distribution of the per-query quotient p′/p /p between the approximate result p′p and the exact result p. Fig. 2 reports the results averaged over all generated instances and queries. Fig. 2(a) shows that the compression of ε -commutative factors substantially accelerates downstream probabilistic inference, where the speedup increases exponentially with the domain size. At the same time, Fig. 2(b) confirms that the query results (i.e., marginal probabilities) remain extremely close to those obtained with exact acp: The per-query quotient p′/p /p concentrates tightly around the optimal value one across all evaluated configurations (except for very few outliers). In other words, acp ±ε± unlocks the speedup of lifted inference at almost no loss of accuracy. To give insights into the influence of k and ε , we provide further experimental results for individual choices in App. 0.B. 5 Conclusion We have introduced ε -commutativity, a principled relaxation of commutativity that tolerates the minute numerical deviations that inevitably arise in practice, e.g., when factor potentials are estimated from data. On this basis, we have developed a representative-based compression scheme that collapses ε -equivalent potentials into a shared value, integrated the relaxation into the state-of-the-art acp algorithm, and proved a sharp (optimal) bound on the resulting approximation error of probabilistic queries. Our empirical evaluation confirms that the bound is loose in practice: Compressing ε -commutative factors unlocks substantial lifted inference speedups while the deviation of query results stays well within the theoretical guarantee. As factors are merely non-negative functions, all proposed concepts directly apply to the detection and compact storage of approximately symmetric functions in more general settings. An interesting direction for future work is to investigate approximate indistinguishability for fg with continuous variables. Currently, the usage of a crv restricts the present work to the discrete case and a continuous counterpart of a crv is required to handle ε -commutativity in models with continuous variables. Acknowledgments This work was partially funded by the Ministry of Culture and Science of the German State of North Rhine-Westphalia. References [1] J. O. Berger (1990) Robust Bayesian Analysis: Sensitivity to the Prior. Journal of Statistical Planning and Inference 25, p. 303–328. Cited by: §1. [2] H. Chan and A. Darwiche (2005) A Distance Measure for Bounding Probabilistic Belief Change. International Journal of Approximate Reasoning 38, p. 149–174. Cited by: §3.2, Definition 5, Definition 5. [3] G. F. Cooper (1990) The Computational Complexity of Probabilistic Inference using Bayesian Belief Networks. Artificial Intelligence 42, p. 393–405. Cited by: §1. [4] B. J. Frey, F. R. Kschischang, H. Loeliger, and N. Wiberg (1997) Factor Graphs and Algorithms. In Proceedings of the Thirty-Fifth Annual Allerton Conference on Communication, Control, and Computing, p. 666–680. Cited by: §2. [5] F. R. Kschischang, B. J. Frey, and H. Loeliger (2001) Factor Graphs and the Sum-Product Algorithm. IEEE Transactions on Information Theory 47, p. 498–519. Cited by: §2. [6] Z. Li, S. Junna, and W. Liao (2025) A Robust Factor Graph Framework for Navigation on PDR/Magnetic Field Integration. Measurement 245, p. 116509. Cited by: §1. [7] M. Luttermann, T. Braun, R. Möller, and M. Gehrke (2024) Colour Passing Revisited: Lifted Model Construction with Commutative Factors. In Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-2024), p. 20500–20507. Cited by: §1, §4, Definition 2. [8] M. Luttermann, J. Machemer, and M. Gehrke (2024) Efficient Detection of Commutative Factors in Factor Graphs. In Proceedings of the Twelfth International Conference on Probabilistic Graphical Models (PGM-2024), p. 38–56. Cited by: §1. [9] M. Luttermann, R. Möller, and M. Gehrke (2026) On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions. arXiv preprint, https://arxiv.org/abs/2605.26908. Cited by: §1, §3, §3, §3. [10] M. Luttermann, J. Speller, M. Gehrke, T. Braun, R. Möller, and M. Hartwig (2025) Approximate Lifted Model Construction. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-2025), p. 9077–9085. Cited by: Appendix 0.A, §1, §3.1, §3.2, §3, §3, §3, §4, Definition 5. [11] B. Milch, L. S. Zettlemoyer, K. Kersting, M. Haimes, and L. P. Kaelbling (2008) Lifted Probabilistic Inference with Counting Formulas. In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI-2008), p. 1062–1068. Cited by: §1. [12] E. Miranda, I. Montes, and S. Destercke (2019) A Unifying Frame for Neighbourhood and Distortion Models. In Proceedings of the Eleventh International Symposium on Imprecise Probabilities: Theories and Applications, p. 304–313. Cited by: §1. [13] M. Niepert and G. Van den Broeck (2014) Tractability through Exchangeability: A New Perspective on Efficient Probabilistic Inference. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI-2014), p. 2467–2475. Cited by: §1. [14] T. Pfeifer, P. Weissig, S. Lange, and P. Protzel (2016) Robust Factor Graph Optimization – A Comparison for Sensor Fusion Applications. In Proceedings of the Twenty-First IEEE International Conference on Emerging Technologies and Factory Automation, p. 1–4. Cited by: §1. [15] D. Poole (2003) First-Order Probabilistic Inference. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-2003), p. 985–991. Cited by: §1. [16] J. Speller, M. Luttermann, M. Gehrke, and T. Braun (2025) Compression versus Accuracy: A Hierarchy of Lifted Models. In Proceedings of the Twenty-Eighth European Conference on Artificial Intelligence (ECAI-2025), p. 5051–5058. Cited by: §1. [17] J. Speller, M. Luttermann, M. Gehrke, and T. Braun (2025) Towards Explainability of Approximate Lifted Model Construction: A Geometric Perspective. In Proceedings of the Eleventh Workshop on Formal and Cognitive Reasoning (FCR-2025), p. 41–56. Cited by: §3.1. [18] N. Taghipour (2013) Lifted Probabilistic Inference by Variable Elimination. Ph.D. Thesis, KU Leuven. Cited by: §1. Appendix 0.A Detailed Proofs See 1 Proof. The proof follows the same structural argument as [10, Lemma 6]. For any permutation π∈Πϕπ∈ _ C_φ of a given assignment =(r1,…,rn) r=(r_1,…,r_n), by definition, the symmetric properties ϕ()≤ϕ(rπ(1),…,rπ(n))⋅(1+ε)φ( r)≤φ(r_π(1),…,r_π(n))·(1+ ) and ϕ(rπ(1),…,rπ(n))≤ϕ()⋅(1+ε)φ(r_π(1),…,r_π(n))≤φ( r)·(1+ ) hold, and therefore also the rearranged inequalities ϕ()⋅11+ε≤ϕ(rπ(1),…,rπ(n))φ( r)· 11+ ≤φ(r_π(1),…,r_π(n)) and ϕ(rπ(1),…,rπ(n))⋅11+ε≤ϕ()φ(r_π(1),…,r_π(n))· 11+ ≤φ( r). ∎ See 4 Proof. A direct worst-case analysis requires some care. Although the extrema maxϕ∗()ϕ() _ r φ^*( r)φ( r) and minϕ∗()ϕ() _ r φ^*( r)φ( r) are taken independently over the entire assignment space, the mean value ϕ∗()φ^*( r) is uniquely determined within each equivalence class [j]ϕ[ r^j]_φ. Consequently, the extremal configurations cannot always be chosen independently, and we therefore distinguish several cases. First observe that for every equivalence class [j]ϕ[ r^j]_φ and all ′,′∈[j]ϕ r , r ∈[ r^j]_φ, Lemma 3 guarantees pairwise ε -equivalence and Lemma 1 implies ϕ(′)∈[ϕ(′)⋅11+ε,ϕ(′)⋅(1+ε)] and ϕ(′)∈[ϕ(′)⋅11+ε,ϕ(′)⋅(1+ε)].φ( r )∈[φ( r )· 11+ ,φ( r )·(1+ )] and φ( r )∈[φ( r )· 11+ ,φ( r )·(1+ )]. Hence, the potentials within one equivalence class can be ordered as 0<11+ε⋅ϕ(j,max)≤ϕ(j,min)≤ϕ(′)≤ϕ(j,max)≤ϕ(j,min)⋅(1+ε), 0< 11+ ·φ( r^j, )≤φ( r^j, )≤φ( r )≤φ( r^j, )≤φ( r^j, )·(1+ ), where ϕ(j,max):=max′∈[j]ϕϕ(′)φ( r^j, ):= _ r ∈[ r^j]_φ( r ) and ϕ(j,min):=min′∈[j]ϕϕ(′)φ( r^j, ):= _ r ∈[ r^j]_φ( r ). This directly affects the class-wise mean ϕ∗(′)=ϕ¯(′)=1|[j]ϕ|∑′∈[j]ϕ(′), φ^*( r )= φ( r )= 1 [ r^j]_φ _ r ∈[ r^j]_φ( r ), which is constrained to vary only within a restricted range of values. Consider first the case where the assignments attaining the maximum and minimum orignate from two different equivalence classes [i]ϕ[ r^i]_φ and [j]ϕ[ r^j]_φ with i≠ji≠ j. In this situation, the worst-case deviations can be chosen independently. For the maximum, the denominator should be as small as possible. Hence, choose ϕ()=ϕ(i,min)φ( r)=φ( r^i, ) for the denominator, while all remaining potentials in the same equivalence class attain their maximimal admissible value ϕ(′):=ϕ(i,max)=(1+ε)ϕ(i,min)φ( r ):=φ( r^i, )=(1+ )φ( r^i, ) for all ′∈[i]ϕ∖ r ∈[ r^i]_φ \ r\ to maximise the numerator. This yields max∈[i]ϕϕ∗()ϕ() _ r∈[ r^i]_φ φ^*( r)φ( r) =(ϕ(i,min)+(|[i]ϕ|−1)⋅(1+ε)⋅ϕ(i,min))/|[i]ϕ|ϕ(i,min) = (φ( r^i, )+( [ r^i]_φ -1)·(1+ )·φ( r^i, ))/ [ r^i]_φ φ( r^i, ) =1+(|[i]ϕ|−1)(1+ε)|[i]ϕ|=1+mi−1miε. = 1+( [ r^i]_φ -1)(1+ ) [ r^i]_φ =1+ m_i-1m_i\; . For the minimum, the denominator should instead be as large as possible. Thus, choose ϕ()=ϕ(j,max)φ( r)=φ( r^j, ), while all remaining values in the same equivalence class attain their minimal admissible value ϕ(′):=ϕ(j,min)=11+εϕ(j,max)φ( r ):=φ( r^j, )= 11+ φ( r^j, ) for all ′∈[j]ϕ∖ r ∈[ r^j]_φ \ r\. Consequently, min∈[j]ϕϕ∗()ϕ() _ r∈[ r^j]_φ φ^*( r)φ( r) =((|[j]ϕ|−1)⋅11+ε⋅ϕ(j,max)+ϕ(j,max))/|[j]ϕ|ϕ(j,max) = (( [ r^j]_φ -1)· 11+ ·φ( r^j, )+φ( r^j, ))/ [ r^j]_φ φ( r^j, ) =(|[j]ϕ|−1)⋅11+ε+1|[j]ϕ|=|[j]ϕ|+ε(1+ε)⋅|[j]ϕ|=1+1mjε1+ε. = ( [ r^j]_φ -1)· 11+ +1 [ r^j]_φ = [ r^j]_φ + (1+ )· [ r^j]_φ = 1+ 1m_j 1+ . Observe, that 1+mi−1miε1+ m_i-1m_i\; is monotonically increasing in mim_i, whereas 1+1mjε1+ε 1+ 1m_j 1+ is monotonically decreasing in mjm_j. Hence, the largest equivalence classes by group size produce the extremal deviations. To determine which class size appear in the outer quotient as the numerator and denominator, respectively, consider g(x):=(1+x−1xε)(1+1xε)g(x):= (1+ x-1x\; ) (1+ 1x ). Its derivative equals g′(x)=ε2(2−x)x3g (x)= ^2(2-x)x^3, which is non-positive for all x≥2x≥ 2. Therefore, for x1,x2∈ℕ≥2x_1,x_2 _≥ 2 it follows: (1+x1−1x1ε)(1+1x1ε)=g(x1) (1+ x_1-1x_1\; ) (1+ 1x_1 )=g(x_1) ≥g(x2)=(1+x2−1x2ε)(1+1x2ε) ≥ g(x_2)= (1+ x_2-1x_2\; ) (1+ 1x_2 ) ⇔1+x1−1x1ε1+1x2ε \;\;\;\;\; 1+ x_1-1x_1\; 1+ 1x_2 ≥1+x2−1x2ε1+1x1ε. ≥ 1+ x_2-1x_2\; 1+ 1x_1 . Consequently, the sharpest bound is obtained by using m2m_2 for the maximum term and m1m_1 for the minimum term. If several equivalence classes with maximal group size exist, then simply m1=m2m_1=m_2. It remains to analyse the case where both extrema originate from the same equivalence class. Since ϕ∗()=ϕ∗(′)φ^*( r)=φ^*( r ) for all ,′∈[j]ϕ r, r ∈[ r^j]_φ, we obtain max∈[j]ϕϕ∗()ϕ()min′∈[j]ϕϕ∗(′)ϕ(′)=max∈[j]ϕ1ϕ()min′∈[j]ϕ1ϕ(′). _ r∈[ r^j]_φ φ^*( r)φ( r) _ r ∈[ r^j]_φ φ^*( r )φ( r )\;= _ r∈[ r^j]_φ 1φ( r) _ r ∈[ r^j]_φ 1φ( r ). If the equivalence class contains only a single assignment, the quotient equals 11. Otherwise, m1≥m2≥2m_1≥ m_2≥ 2 holds, and the quotient is maximised by choosing ϕ()=ϕ(j,min)=11+εϕ(j,max)φ( r)=φ( r^j, )= 11+ φ( r^j, ) and ϕ(′)=ϕ(j,max)=(1+ε)ϕ(j,min)φ( r )=φ( r^j, )=(1+ )φ( r^j, ). Hence, for m2≤m1m_2≤ m_1 we get max∈[j]ϕ1ϕ()min′∈[j]ϕ1ϕ(′) _ r∈[ r^j]_φ 1φ( r) _ r ∈[ r^j]_φ 1φ( r ) ≤1ϕ(j,min)1(1+ε)ϕ(j,min)=1+ε≤(1+m2−1m2ε)(1+ε)1+1m1ε, ≤ 1φ( r^j, ) 1(1+ )φ( r^j, )=1+ ≤ (1+ m_2-1m_2 )(1+ )1+ 1m_1 , which establishes the bound in all cases. ∎ See 3.5 For the proof, consider the following example. Example 3 Let M be the fg with factors ϕ1,…,ϕm _1,…, _m, of which ϕ1,…,ϕk _1,…, _k with 0≤k≤m0≤ k≤ m are ε -commutative with respect to disjoint argument sets ϕ1,…,ϕk C_ _1,…, C_ _k with finite domains, respectively, each satisfying |ϕi|≥2 C_ _i ≥ 2. Let ℛϕi=∪˙j=1liijX_R_ _i= ∪_j=1^l_i\ r_i^j\ be the set of disjoint representatives ij r^j_i for all disjoint equivalence classes [ij]ϕi[ r^j_i]_ _i united to ∪˙j=1li[ij]ϕi=ϕi ∪_j=1^l_i[ r^j_i]_ _i=X_ R_ _i ordered by group size with m1i:=|[i1]ϕi|≥…≥mli:=|[il]ϕi|≥1m_1_i:= [ r^1_i]_ _i ≥…≥ m_l_i:= [ r^l_i]_ _i ≥ 1 for every ε -commutative factor ϕi _i with i=1,…,ki=1,…,k. Let Rj=range(Rj)X_R_j=range(R_j) have at least two deviating elements and within a group ϕi C_ _i the same ranges. For i=1,…,ki=1,…,k define ϕi(i):=(1+ε)⋅1if i=i1, 1if i∈[i1]ϕi∖i1, 2if i=i2,(1+ε)⋅2if i∈[i2]ϕi∖i2,jfor i∈[ij]ϕi and 2<j≤li. _i( r_i):= cases\;(1+ )· 1&if r_i= r_i^1,\\ \;1&if r_i∈[ r_i^1]_ _i \ r_i^1\,\\ \;2&if r_i= r_i^2,\\ \;(1+ )· 2&if r_i∈[ r_i^2]_ _i \ r_i^2\,\\ \;j&for r_i∈[ r_i^j]_ _i and 2<j≤ l_i. cases Thus, the first equivalence class contains exactly one maximal value and otherwise minimal values, whereas the second class contains exactly one minimal value and otherwise maximal ones, following the same construction as in the proof of Lemma 4. All remaining parts are constant and therefore contribute no approximation error. Proof of Thm. 3.5. We show that the construction from Ex. 3 attains the bound. Let M′M denote the model obtained from M by replacing every ε -commutative factor ϕi _i by the arithmetic mean as in Eq. 2. Notice that ϕi∗(i)=ϕi(i) _i^*( r_i)= _i( r_i) for i=k+1,…,mi=k+1,…,m and all i∈ϕi r_i _ R_ _i, but also ϕi∗(i)=ϕi(i) _i^*( r_i)= _i( r_i) for i=1,…,ki=1,…,k and i∈[ij]ϕi r_i∈[ r_i^j]_ _i and 2<j≤li2<j≤ l_i implying ϕi∗(i)ϕi(i)=1 _i^*( r_i) _i( r_i)=1. Consequently, all extremal deviation are attained exclusively within the first two equivalence classes. For i∈[i1]ϕi r_i∈[ r_i^1]_ _i, the definition results in ϕi∗(i)=(1+ε)+(m1i−1)m1i=1+1m1iε, _i^*( r_i)= (1+ )+(m_1_i-1)m_1_i=1+ 1m_1_i , and for i′∈[i2]ϕi r _i∈[ r_i^2]_ _i in ϕi∗(i′)=(1+ε)⋅2⋅(m2i−1)+2m2i=2⋅(1+(m2i−1)m2iε). _i^*( r _i)= (1+ )· 2·(m_2_i-1)+2m_2_i=2· (1+ (m_2_i-1)m_2_i ). For i∈[i1]ϕi r_i∈[ r_i^1]_ _i the maximum becomes maxi∈[i1]ϕiϕi∗(i)ϕi(i)=1+1m1iε1=1+1m1iε>1, _ r_i∈[ r_i^1]_ _i _i^*( r_i) _i( r_i)= 1+ 1m_1_i 1=1+ 1m_1_i >1, and for i′∈[i2]ϕi r _i∈[ r_i^2]_ _i it becomes maxi′∈[i2]ϕiϕi∗(i′)ϕi(i′)=2⋅(1+(m2i−1)m2iε)2=1+(m2i−1)m2iε>1, _ r _i∈[ r_i^2]_ _i _i^*( r _i) _i( r _i)= 2· (1+ (m_2_i-1)m_2_i )2=1+ (m_2_i-1)m_2_i >1, which is larger than the first one due to m2i≥2m_2_i≥ 2. Analogously, for i∈[i1]ϕi r_i∈[ r_i^1]_ _i the minimal quotient inside this class reaches mini∈[i1]ϕiϕi∗(i)ϕi(i)=1+1m1iε1+ε<1, _ r_i∈[ r_i^1]_ _i _i^*( r_i) _i( r_i)= 1+ 1m_1_i 1+ <1, which is as small as the following one for i′∈[i2]ϕi r _i∈[ r_i^2]_ _i due to m2i≥2m_2_i≥ 2 mini′∈[i2]ϕiϕi∗(i′)ϕi(i′)=2⋅(1+(m2i−1)m2iε)2⋅(1+ε)=1+(m2i−1)m2iε1+ε<1. _ r _i∈[ r_i^2]_ _i _i^*( r _i) _i( r _i)= 2· (1+ (m_2_i-1)m_2_i )2·(1+ )= 1+ (m_2_i-1)m_2_i 1+ <1. Using Eq. 4 from the definition of the Chan-Darwiche distance leads to D D (PM,PM′)CD=lnmaxψ′()ψ()−lnminψ′()ψ()_CD(P_M,P_M )= \; _ r ψ ( r)ψ( r)- \; _ r ψ ( r)ψ( r) =lnmax∏i=1kϕi∗(i)∏i=k+1mϕi(i)∏i=1mϕi(i)−lnmin∏i=1kϕi∗(i)∏i=k+1mϕi(i)∏i=1mϕi(i) = \; _ r _i=1^k _i^*( r_i) _i=k+1^m _i( r_i) _i=1^m _i( r_i)- \; _ r _i=1^k _i^*( r_i) _i=k+1^m _i( r_i) _i=1^m _i( r_i) =lnmax∏i=1kϕi∗(i)ϕi(i)−lnmin∏i=1kϕi∗(i)ϕi(i). = \; _ r _i=1^k _i^*( r_i) _i( r_i)- \; _ r _i=1^k _i^*( r_i) _i( r_i). Since the argument sets are pairwise disjoint, the extrema can be atteined independently for every factor. Hence, D D (PM,PM′)CD=ln∏i=1kmaxiϕi∗(i)ϕi(i)−ln∏i=1kminiϕi∗(i)ϕi(i)_CD(P_M,P_M )= \; _i=1^k _ r_i _i^*( r_i) _i( r_i)- \; _i=1^k _ r_i _i^*( r_i) _i( r_i) =ln∏i=1kmaxi′∈[i2]ϕiϕi∗(i′)ϕi(i′)−ln∏i=1kmini∈[i1]ϕiϕi∗(i)ϕi(i) = \; _i=1^k _ r _i∈[ r_i^2]_ _i _i^*( r _i) _i( r _i)- \; _i=1^k _ r_i∈[ r_i^1]_ _i _i^*( r_i) _i( r_i) =ln∏i=1k(1+(m2i−1)m2iε)−ln∏i=1k1+1m1iε1+ε=ln∏i=1k(1+m2i−1m2iε)(1+ε)1+1m1iε. = \; _i=1^k (1+ (m_2_i-1)m_2_i )- \; _i=1^k 1+ 1m_1_i 1+ = \; _i=1^k (1+ m_2_i-1m_2_i )(1+ )1+ 1m_1_i . Thus, the bound of Thm. 3.4 is attained exactly and is therefore optimal. ∎ 0.A.1 Additional Result Symmetry Set Proposition 2 (Cardinality of the Symmetry Set) Let =(r1,…,rn)∈ϕ r=(r_1,…,r_n) _ R_φ and Iϕ:=i∣Ri∈ϕI_ C_φ:=\\,i R_i∈ C_φ\,\ denote the indices of the commutative arguments. Further, let a1,…,ak=ri∣i∈Iϕ\a_1,…,a_k\=\\,r_i i∈ I_ C_φ\,\ be the set of distinct values occurring among the commutative arguments, and let nj:=|i∈Iϕ∣ri=aj|n_j:= |\\,i∈ I_ C_φ r_i=a_j\,\ | denote the multiplicity of value aja_j for a fixed assignment r. Then the cardinality of the symmetry set is |ϕ()|=|ϕ|!∏j=1knj! | S_φ( r)|= | C_φ|! _j=1^kn_j! with 1≤|ϕ()|≤|ϕ|!1≤| S_φ( r)|≤| C_φ|!, where the upper bound is attained if and only if all commutative arguments have pairwise non-ε -equivalent values. Proof. Since permutations in Πϕ _ C_φ act only on the positions corresponding to ε -commutative arguments, it holds that |Πϕ|=|ϕ|!| _ C_φ|=| C_φ|!. If all values among the commutative arguments are pairwise distinct, every permutation produces a distinct tuple, and thus |ϕ()|=|ϕ|!| S_φ( r)|=| C_φ|!. Now assume that some values coincide. For each distinct value aja_j, there are exactly mjm_j positions among the commutative arguments whose assigned value equals aja_j. Permuting these mjm_j positions among themselves does not change the resulting tuple. Hence, every distinct tuple in the symmetry set is generated exactly ∏j=1knj! _j=1^kn_j! times by permutations in Πϕ _ C_φ. Since there are |ϕ|!| C_φ|! permutations in total, the number of distinct tuples is |ϕ()|=|ϕ|!∏j=1knj!. | S_φ( r)|= | C_φ|! _j=1^kn_j!. ∎ Appendix 0.B Additional Experimental Results In addition to the experimental results provided in Sec. 4, we provide further experimental results for individual scenarios in this section. 1030100300248121620domain size ddtime (ms)LVE (ACP)LVE (ACP ±ε± ) (a) lve run time (ms). 0.40.60.81.01.21.41.6248121620domain size ddp′/p /p (b) Query result quotient p′/p /p. Figure 3: (a) Run time of lve on the compressed model returned by acp and its ε -relaxed variant (acp ±ε± ), and (b) distribution of the per-query quotient p′/p /p between the approximate result p′p and the exact result p for input fg containing k=1k=1 ε -commutative factors with ε=0.001 =0.001. 1030100300248121620domain size ddtime (ms)LVE (ACP)LVE (ACP ±ε± ) (a) lve run time (ms). 0.40.60.81.01.21.41.6248121620domain size ddp′/p /p (b) Query result quotient p′/p /p. Figure 4: (a) Run time of lve on the compressed model returned by acp and its ε -relaxed variant (acp ±ε± ), and (b) distribution of the per-query quotient p′/p /p between the approximate result p′p and the exact result p for input fg containing k=1k=1 ε -commutative factors with ε=0.01 =0.01. 1030100300248121620domain size ddtime (ms)LVE (ACP)LVE (ACP ±ε± ) (a) lve run time (ms). 0.40.60.81.01.21.41.6248121620domain size ddp′/p /p (b) Query result quotient p′/p /p. Figure 5: (a) Run time of lve on the compressed model returned by acp and its ε -relaxed variant (acp ±ε± ), and (b) distribution of the per-query quotient p′/p /p between the approximate result p′p and the exact result p for input fg containing k=1k=1 ε -commutative factors with ε=0.1 =0.1. 1030100300248121620domain size ddtime (ms)LVE (ACP)LVE (ACP ±ε± ) (a) lve run time (ms). 0.60.81.01.21.4248121620domain size ddp′/p /p (b) Query result quotient p′/p /p. Figure 6: (a) Run time of lve on the compressed model returned by acp and its ε -relaxed variant (acp ±ε± ), and (b) distribution of the per-query quotient p′/p /p between the approximate result p′p and the exact result p for input fg containing k=3k=3 ε -commutative factors with ε=0.001 =0.001. 1030100300248121620domain size ddtime (ms)LVE (ACP)LVE (ACP ±ε± ) (a) lve run time (ms). 0.60.81.01.21.4248121620domain size ddp′/p /p (b) Query result quotient p′/p /p. Figure 7: (a) Run time of lve on the compressed model returned by acp and its ε -relaxed variant (acp ±ε± ), and (b) distribution of the per-query quotient p′/p /p between the approximate result p′p and the exact result p for input fg containing k=3k=3 ε -commutative factors with ε=0.01 =0.01. 1030100300248121620domain size ddtime (ms)LVE (ACP)LVE (ACP ±ε± ) (a) lve run time (ms). 0.60.81.01.21.4248121620domain size ddp′/p /p (b) Query result quotient p′/p /p. Figure 8: (a) Run time of lve on the compressed model returned by acp and its ε -relaxed variant (acp ±ε± ), and (b) distribution of the per-query quotient p′/p /p between the approximate result p′p and the exact result p for input fg containing k=3k=3 ε -commutative factors with ε=0.1 =0.1. 101001000248121620domain size ddtime (ms)LVE (ACP)LVE (ACP ±ε± ) (a) lve run time (ms). 0.60.81.01.21.4248121620domain size ddp′/p /p (b) Query result quotient p′/p /p. Figure 9: (a) Run time of lve on the compressed model returned by acp and its ε -relaxed variant (acp ±ε± ), and (b) distribution of the per-query quotient p′/p /p between the approximate result p′p and the exact result p for input fg containing k=7k=7 ε -commutative factors with ε=0.001 =0.001. 301003001000248121620domain size ddtime (ms)LVE (ACP)LVE (ACP ±ε± ) (a) lve run time (ms). 0.60.81.01.21.4248121620domain size ddp′/p /p (b) Query result quotient p′/p /p. Figure 10: (a) Run time of lve on the compressed model returned by acp and its ε -relaxed variant (acp ±ε± ), and (b) distribution of the per-query quotient p′/p /p between the approximate result p′p and the exact result p for input fg containing k=7k=7 ε -commutative factors with ε=0.01 =0.01. 101001000248121620domain size ddtime (ms)LVE (ACP)LVE (ACP ±ε± ) (a) lve run time (ms). 0.60.81.01.21.4248121620domain size ddp′/p /p (b) Query result quotient p′/p /p. Figure 11: (a) Run time of lve on the compressed model returned by acp and its ε -relaxed variant (acp ±ε± ), and (b) distribution of the per-query quotient p′/p /p between the approximate result p′p and the exact result p for input fg containing k=7k=7 ε -commutative factors with ε=0.1 =0.1. The averaged results in Fig. 2 aggregate over the number of ε -commutative factors k and the tolerance ε . To disentangle the influence of these two parameters, Figs. 3 to 11 report the lve run time and the per-query quotient p′/p /p separately for each combination of k∈1,3,7k∈\1,3,7\ and ε∈0.001,0.01,0.1 ∈\0.001,0.01,0.1\. The run time behaviour is qualitatively consistent across all configurations: The run time of lve on the ε -relaxed model stays almost constant in the domain size, whereas exact acp—which must leave the ε -commutative factors uncompressed—slows down steeply, so the speedup grows exponentially with the domain size d. The speedup is essentially independent of ε (given that the ε -deviation in the model is within the chosen ε -value used when running acp, which is the case in our experiments), since the structure of the compressed model depends only on the commutativity pattern and not on the magnitude of ε , while it increases with the number of ε -commutative factors k, as each additional compressed factor widens the gap between the two models. At the same time, the per-query quotient remains tightly concentrated around the optimal value of one in every scenario. In line with the theoretical bound, increasing ε from 0.0010.001 to 0.10.1 slightly widens the spread of the quotient, and increasing the number of ε -commutative factors k admits a few more outliers, since each compressed factor potentially contributes to the overall deviation. Even for the largest tested k=7k=7 and for the largest tested ε=0.1 =0.1, however, the quotient stays well within the theoretical guarantee, confirming that the bound is loose in practice. 131030248121620domain size ddspeedup (a) Speedup factor for lve. 1e+011e+031e+05248121620domain size ddtime (s)ACPACP ±ε± (b) Color passing run times. Figure 12: (a) Speedup for online inference run times (i.e., ratio of the run time of lve on the compressed model returned by acp and the run time of lve on the compressed model returned by the ε -relaxed variant of acp). (b) Offline run times of acp and its ε -relaxed variant (acp ±ε± ). A plot showcasing the resulting speedup of online inference (averaged over all choices of k and ε ) is given in Fig. 12(a). It becomes evident that the speedup grows exponentially with the domain size d and eventually reaches a factor of more than 3030 for the choice of d=20d=20. Figure 12(b) further displays the offline run times of acp and its ε -relaxed variant (averaged over all choices of k and ε ). As expected, the offline run time of the ε -relaxed variant does not surpass the offline run time of exact acp, demonstrating that the relaxation does not introduce any overhead at all. In fact, ε -relaxed acp even slightly reduces the run time compared to exact acp, since ε -relaxed acp is able to find ε -commutative factors and hence requires less iterations when searching for subsets of ε -commutative arguments (acp needs more iterations as it checks all subsets of arguments until it is able to conclude that no subset of strictly commutative arguments exists). 0.000.250.500.751.00248121620domain size d|M′|/|M||M | /|M|LVE (ACP)LVE (ACP ±ε± ) (a) Compression ratio for ε=0.001 =0.001. 0.000.250.500.751.00248121620domain size d|M′|/|M||M | /|M|LVE (ACP)LVE (ACP ±ε± ) (b) Compression ratio for ε=0.1 =0.1. Figure 13: Compression ratio |M′|/|M| M / M between the compressed model M′M and the original model M for input fg containing k=1k=1 ε -commutative factors with (a) ε=0.001 =0.001 and (b) ε=0.1 =0.1. 0.000.250.500.751.00248121620domain size d|M′|/|M||M | /|M|LVE (ACP)LVE (ACP ±ε± ) (a) Compression ratio for ε=0.001 =0.001. 0.000.250.500.751.00248121620domain size d|M′|/|M||M | /|M|LVE (ACP)LVE (ACP ±ε± ) (b) Compression ratio for ε=0.1 =0.1. Figure 14: Compression ratio |M′|/|M| M / M between the compressed model M′M and the original model M for input fg containing k=3k=3 ε -commutative factors with (a) ε=0.001 =0.001 and (b) ε=0.1 =0.1. 0.000.250.500.751.00248121620domain size d|M′|/|M||M | /|M|LVE (ACP)LVE (ACP ±ε± ) (a) Compression ratio for ε=0.001 =0.001. 0.000.250.500.751.00248121620domain size d|M′|/|M||M | /|M|LVE (ACP)LVE (ACP ±ε± ) (b) Compression ratio for ε=0.1 =0.1. Figure 15: Compression ratio |M′|/|M| M / M between the compressed model M′M and the original model M for input fg containing k=7k=7 ε -commutative factors with (a) ε=0.001 =0.001 and (b) ε=0.1 =0.1. Finally, we examine the structural reduction achieved by the compression stemming from exact acp and its ε -relaxed variant. Figures 13 to 15 show the compression ratio |M′|/|M| M / M between the compressed model M′M and the original model M for k∈1,3,7k∈\1,3,7\ at the smallest and largest tolerance ε∈0.001,0.1 ∈\0.001,0.1\ (that is, a compression ratio of one means that no compression is achieved at all, whereas a smaller ratio indicates more compression). The ε -relaxed variant attains a substantially smaller compression ratio than exact acp, because it is able to compress the ε -commutative factors that exact acp cannot compress. For both variants, the compression ratio decreases as the domain size grows, illustrating that larger models offer more indistinguishability to be exploited. 0.000.250.500.751.00248121620domain size d|M′|/|M||M | /|M|LVE (ACP)LVE (ACP ±ε± ) (a) employee instance class. 0.000.250.500.751.00248121620domain size d|M′|/|M||M | /|M|LVE (ACP)LVE (ACP ±ε± ) (b) epidemic instance class. Figure 16: Compression ratio |M′|/|M| M / M between the compressed model M′M and the original model M broken down per instance class, averaged over the number of commutative factors k and the tolerance ε . Interestingly, as shown in Fig. 16, acp is not able to obtain any compression at all for some of the input fg: The input instances are generated from two different classes of fg—employee and epidemic—which have different structural properties, and exact acp is only able to achieve compression for the employee instance class, while it fails to achieve any compression for the epidemic instance class. This particular behaviour highlights that even if there is just a single ε -commutative factor in a given fg, exact acp may fail to find any compression at all (although there are other parts in the input fg that could be compressed and that do not involve commutativity), which is due to the propagation of information throughout acp’s colour passing procedure.