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

• URL: http://arxiv.org/abs/2605.26908v1
• Date: Tue, 26 May 2026 12:05:53 GMT
• Title: On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions
• Abstract summary: We revisit the theoretical foundations underlying the state-of-the-art algorithm to detect commutative factors.<n>We prove a slightly modified version of the aforementioned theorem, which serves as a necessary condition to identify commutative factors.<n>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.
• Score: 4.503368323711748
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Exploiting the indistinguishability of objects in a probabilistic graphical model such as a factor graph 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 factor graphs 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.

Related papers

• Lifted Model Construction under Approximate Commutativity [5.629677133940586]
  We show how -commutativity can be exploited for lifted model construction, downstream probabilistic inference, and prove strict bounds on the induced approximation error.<n>These theoretical guarantees are confirmed empirically, demonstrating comparable query accuracy at lower runtime.
  arXiv  Detail & Related papers  (2026-08-25T15:32:47Z)
• Computational Identifiability [58.12019389497595]
  'Identical identifiability' assumes properties, infinite data, or other mathematically idealized conditions.<n>'Computational identifiability' is to instead define a finite computational search procedure for an empirical estimator.<n>We show how this framework allows us to answer fine-grained, practical identification questions.
  arXiv  Detail & Related papers  (2026-06-08T19:39:59Z)
• Partial Transportability for Domain Generalization [56.37032680901525]
  Building on the theory of partial identification and transportability, this paper introduces new results for bounding the value of a functional of the target distribution.<n>Our contribution is to provide the first general estimation technique for transportability problems.<n>We propose a gradient-based optimization scheme for making scalable inferences in practice.
  arXiv  Detail & Related papers  (2025-03-30T22:06:37Z)
• Efficient Detection of Commutative Factors in Factor Graphs [1.1323769002489257]
  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.
  arXiv  Detail & Related papers  (2024-07-23T08:31:24Z)
• Identifiable Latent Neural Causal Models [82.14087963690561]
  Causal representation learning seeks to uncover latent, high-level causal representations from low-level observed data. We determine the types of distribution shifts that do contribute to the identifiability of causal representations. We translate our findings into a practical algorithm, allowing for the acquisition of reliable latent causal representations.
  arXiv  Detail & Related papers  (2024-03-23T04:13:55Z)
• Efficient Detection of Exchangeable Factors in Factor Graphs [1.1323769002489257]
  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. We prove that DEFT efficiently identifies restrictions to drastically reduce the number of permutations and validate the efficiency of DEFT in our empirical evaluation.
  arXiv  Detail & Related papers  (2024-03-15T10:20:56Z)
• Nonparametric Partial Disentanglement via Mechanism Sparsity: Sparse Actions, Interventions and Sparse Temporal Dependencies [58.179981892921056]
  This work introduces a novel principle for disentanglement we call mechanism sparsity regularization. We propose a representation learning method that induces disentanglement by simultaneously learning the latent factors. We show that the latent factors can be recovered by regularizing the learned causal graph to be sparse.
  arXiv  Detail & Related papers  (2024-01-10T02:38:21Z)
• Colour Passing Revisited: Lifted Model Construction with Commutative Factors [3.1045268505532566]
  We present a modified version of the colour passing algorithm that uses logical variables to construct a lifted representation independent of a specific inference algorithm. Our proposed algorithm efficiently detects more symmetries than the state of the art and thereby drastically increases compression, yielding significantly faster online query times.
  arXiv  Detail & Related papers  (2023-09-20T11:57:19Z)
• Bounding Counterfactuals under Selection Bias [60.55840896782637]
  We propose a first algorithm to address both identifiable and unidentifiable queries. We prove that, in spite of the missingness induced by the selection bias, the likelihood of the available data is unimodal.
  arXiv  Detail & Related papers  (2022-07-26T10:33:10Z)
• Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
  Probabilistic sentential decision diagrams are logic circuits where the inputs of disjunctive gates are annotated by probability values. We develop the credal sentential decision diagrams, a generalisation of their probabilistic counterpart that allows for replacing the local probabilities with credal sets of mass functions. For a first empirical validation, we consider a simple application based on noisy seven-segment display images.
  arXiv  Detail & Related papers  (2020-08-19T16:04:34Z)
• Structural Causal Models Are (Solvable by) Credal Networks [70.45873402967297]
  Causal inferences can be obtained by standard algorithms for the updating of credal nets. This contribution should be regarded as a systematic approach to represent structural causal models by credal networks. Experiments show that approximate algorithms for credal networks can immediately be used to do causal inference in real-size problems.
  arXiv  Detail & Related papers  (2020-08-02T11:19:36Z)
• Provable Online CP/PARAFAC Decomposition of a Structured Tensor via Dictionary Learning [18.464203215845373]
  We consider the problem of factorizing a structured 3-mutation tensor into its constituent Polyadic (CP) factors. We develop a provable algorithm for structured tensor factorization.
  arXiv  Detail & Related papers  (2020-06-30T00:31:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.