Efficient Symbolic Computations for Identifying Causal Effects

• URL: http://arxiv.org/abs/2604.20516v1
• Date: Wed, 22 Apr 2026 12:59:12 GMT
• Title: Efficient Symbolic Computations for Identifying Causal Effects
• Abstract summary: identifiability of causal effects is decidable through symbolic computation.<n>We show how to practically use symbolic computation for deciding rational identifiability.
• Score: 0.6117371161379209
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Determining identifiability of causal effects from observational data under latent confounding is a central challenge in causal inference. For linear structural causal models, identifiability of causal effects is decidable through symbolic computation. However, standard approaches based on Gröbner bases become computationally infeasible beyond small settings due to their doubly exponential complexity. In this work, we study how to practically use symbolic computation for deciding rational identifiability. In particular, we present an efficient algorithm that provably finds the lowest degree identifying formulas. For a causal effect of interest, if there exists an identification formula of a prespecified maximal degree, our algorithm returns such a formula in quasi-polynomial time.

Related papers

• 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)
• Clustering and Pruning in Causal Data Fusion [1.0923877073891441]
  Do-calculus remains the only general-purpose tool for causal data fusion.<n>We propose pruning (removing unnecessary variables) and clustering (combining variables) as preprocessing operations.
  arXiv  Detail & Related papers  (2025-05-21T07:44:39Z)
• Graph-based Complexity for Causal Effect by Empirical Plug-in [56.14597641617531]
  This paper focuses on the computational complexity of computing empirical plug-in estimates for causal effect queries. We show that computation can be done efficiently, potentially in time linear in the data size, depending on the estimand's hypergraph.
  arXiv  Detail & Related papers  (2024-11-15T07:42:01Z)
• On the Complexity of Identification in Linear Structural Causal Models [3.44747819522562]
  We give a new sound and complete algorithm for generic identification which runs in space. The paper also presents evidence that identification is computationally hard in general.
  arXiv  Detail & Related papers  (2024-07-17T13:11:26Z)
• Towards Bounding Causal Effects under Markov Equivalence [13.050023008348388]
  We consider the derivation of bounds on causal effects given only observational data. We provide a systematic algorithm to derive bounds on causal effects that exploit the invariant properties of the equivalence class.
  arXiv  Detail & Related papers  (2023-11-13T11:49:55Z)
• Efficient Computation of Counterfactual Bounds [44.4263314637532]
  We compute exact counterfactual bounds via algorithms for credal nets on a subclass of structural causal models. We evaluate their accuracy by providing credible intervals on the quality of the approximation.
  arXiv  Detail & Related papers  (2023-07-17T07:59:47Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  We derive a likelihood characterisation for the overall data that leads us to extend a previous EM-based algorithm. The new algorithm learns to approximate the (unidentifiability) region of model parameters from such mixed data sources. It delivers interval approximations to counterfactual results, which collapse to points in the identifiable case.
  arXiv  Detail & Related papers  (2022-12-06T12:42:11Z)
• Causal Effect Identification in Uncertain Causal Networks [30.239874638041904]
  Causal identification is at the core of the causal inference literature. We show that the edges in a causal graph exist with uncertainties which may, for example, represent degree of belief from domain experts. We propose efficient algorithms to approximate this problem evaluate them against both real-world networks and randomly generated graphs.
  arXiv  Detail & Related papers  (2022-08-09T09:44:45Z)
• Experimental Design for Causal Effect Identification [31.23071073904698]
  We consider the problem of designing the collection of interventions with the minimum cost to identify the desired effect. First, we prove that this problem is NP-hard, and subsequently propose an algorithm that can either find the optimal solution or a logarithmic approximation of it. Although these algorithms could potentially stumble on sub-optimal solutions, our simulations show that they achieve small regrets on random graphs.
  arXiv  Detail & Related papers  (2022-05-04T13:19:04Z)
• Typing assumptions improve identification in causal discovery [123.06886784834471]
  Causal discovery from observational data is a challenging task to which an exact solution cannot always be identified. We propose a new set of assumptions that constrain possible causal relationships based on the nature of the variables.
  arXiv  Detail & Related papers  (2021-07-22T14:23:08Z)
• The Causal Neural Connection: Expressiveness, Learnability, and Inference [125.57815987218756]
  An object called structural causal model (SCM) represents a collection of mechanisms and sources of random variation of the system under investigation. In this paper, we show that the causal hierarchy theorem (Thm. 1, Bareinboim et al., 2020) still holds for neural models. We introduce a special type of SCM called a neural causal model (NCM), and formalize a new type of inductive bias to encode structural constraints necessary for performing causal inferences.
  arXiv  Detail & Related papers  (2021-07-02T01:55:18Z)
• 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)

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.