Partial Identification under Causal Orders by Linear Programming
Authors: Eric Rossetto, Alessandro Antonucci
Organizations: Istituto Dalle Molle di Studi sull’Intelligenza Artificiale (IDSIA) Scuola Universitaria Professionale della Svizzera Italiana (SUPSI) Lugano, Switzerland
Non-parametric (partial) identification of counterfactual queries typically relies on a fully specified causal graph. Motivated by settings with incomplete domain knowledge, we challenge this requirement by leveraging structural assumptions that are inherently implied by the query itself. We show that any counterfactual inquiry induces a, mostly partial, topological ordering over relevant variables, which, in turn, enables an explicit query parametrisation reducing the identification task to a linear program. This allows bounding arbitrary counterfactual and nested counterfactual queries. Our work can be viewed as a generalisation of the classical bounding framework of Tian and Pearl (2000), originally developed for probabilities of causation. We also prove the tightness of our bounds by constructing structural causal models that attain the bounds whilst being compatible with both the observed data and the query-implied order. To assess both the generality and practical utility of the proposed bounding procedure, we revisit several case studies from the literature, demonstrating how the derived bounds can be used to yield informative insights even in the absence of an input causal graph.
Figures & tables
Figure 1: Causal diagrams considered in the examples. (a) Confounded treatment-outcome pair. (b) Instrumental Variable (IV) setting, where Z serves as an instrument for X . (c) Mediation model with a direct effect and confounding between the mediator W and the outcome. Grey nodes denote unobserved exogenous variables.
Assumption Set
CDEx0,x1w0(y1)
CDEx0,x1w1(y1)
∣Sσ∣
∣Tσ∣
Lower
Upper
Lower
Upper
No additional assumptions
Cai et al. (2008) (Fig. 1(c) )
-0.200
0.385
-0.781
0.634
–
–
This paper
-0.599
0.694
-0.891
0.817
128
20
Monotonicity
Cai et al. (2008)
0.000
0.036
0.000
0.582
–
–
Table 1: Comparison of CDE bounds on the (binary) Lipid data ( Cai et al., 2008 , Tab. 1) against analytical bounds under varying assumptions. In this experiment, Monotonicity forces positive effects of X on W , X on Y , and W on Y ; whilst, weak exogeneity imposes no-interaction between X and W on Y .
Lower
Upper
∣Sσ∣
∣Tσ∣
Assumptions for NDEx0,x1(y1)
Query-induced Order
-0.691
0.688
294,912
60
Y⊥⊥X
-0.503
0.497
294,912
96
{Y,W}⊥⊥X
-0.503
0.497
294,912
528
Y⊥⊥{X,W}
-0.628
0.679
294,912
89,172
Y⊥⊥{X,W} & W⊥⊥X
-0.489
0.637
294,912
294,912
Table 2: UC Berkeley dataset: NDE bounds under various weak exogeneity assumptions (top) and individual unnested query terms under query-induced assumptions (bottom).
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Method
Lower
Upper
Vitamin A
Balke and Pearl (1997)
-0.195
0.005
This paper
-0.587
0.412
Coronary
Balke and Pearl (1997)
0.262
0.868
This paper
-0.685
0.971
Appendix
Table 3: Comparison of ACE bounds. Lower and upper bounds for the ACE grouped by Study.
Figure 2: End-to-end computation time for GPNS(r) bounds, on a semi-logarithmic scale, as a function of the variable cardinalities ( n=∣X∣=∣Y∣ ).
Figure 3: Examples of canonical PSCM specifications compatible with the endogenous order σ:−(X,W,Y) . (a) Markovian specification. (b) Specification with one exogenous variable shared by W and Y . (c) Specification with one exogenous variable shared by all endogenous variables. Grey nodes denote exogenous variables.
Previous work establishing completeness results for counterfactual identification has been circumscribed to the setting where the input data belongs to observational or interventional distributions (Layers 1 and 2 of Pearl's Causal Hierarchy), since it was generally presumed impossible to obtain data from counterfactual distributions, which belong to Layer 3. However, recent work (Raghavan & Bareinboim, 2025) has formally characterized a family of counterfactual distributions which can be directly estimated via experimental methods - a notion they call counterfactual realizability. This leaves open the question of what additional counterfactual quantities now become identifiable, given this new access to (some) Layer 3 data. To answer this question, we develop the CTFIDU+ algorithm for identifying counterfactual queries from an arbitrary set of Layer 3 distributions, and prove that it is complete for this task. Building on this, we establish the theoretical limit of which counterfactuals can be identified from physically realizable distributions, thus implying the fundamental limit to exact causal inference in the non-parametric setting. Finally, given the impossibility of identifying certain critical types of counterfactuals, we derive novel analytic bounds for such quantities using realizable counterfactual data, and corroborate using simulations that counterfactual data helps tighten the bounds for non-identifiable quantities in practice.
Arvind Raghavan, Elias Bareinboim
Causal Artificial Intelligence Lab, Department of Computer Science, Columbia University
This paper investigates the development of causal foundation models for bounding the effect of interventions and counterfactuals from observational data. We show that a canonical prior can be defined with full support over the space of structural causal models with discrete observables. With this canonical prior, we translate the problem of bounding counterfactuals into that of learning distributions over functions that map data (and possibly structural assumptions) to a causal query of interest. This extends the promising causal foundational modelling paradigm to the estimation of partially-identifiable causal effects, i.e., under unobserved confounding, where multiple values are equally compatible with the observed data and prior structural assumptions.
Probabilities of causation are fundamental to individual-level explanation and decision making, yet they are inherently counterfactual and not point-identifiable from data in general. Existing bounds either disregard available covariates, require complete causal graphs, or rely on restrictive binary settings, limiting their practical use. In real-world applications, causal information is often partial but nontrivial. This paper proposes a general framework for bounding probabilities of causation using partial causal information. We show how the available structural or statistical information can be systematically incorporated as constraints in a optimization programming formulation, yielding tighter and formally valid bounds without full identifiability. This approach extends the applicability of probabilities of causation to realistic settings where causal knowledge is incomplete but informative.
Yuxuan Xie, Ang Li
University of Ottawa, Ontario, Canada · Department of Computer Science, Florida State University, FL, U.S.A.