Source-linked AI summary
Partial Identification under Causal Orders by Linear Programming
Eric Rossetto, Alessandro Antonucci
TL;DR
The paper studies how to partially identify arbitrary counterfactual queries when a fully specified causal graph is unavailable and observational information leaves multiple compatible models. It parameterizes queries using their implied variable order and solves the resulting problem with linear programming. The resulting bounds are tight, extend classical probability-of-causation bounds, and support practical case studies without an input causal graph.
Problem
Partial identification of counterfactual queries typically relies on a fully specified causal graph, although practical settings may lack sufficient structural assumptions for point identification.
Method
The paper uses a canonical structural causal model based on a query-compatible total order and reduces arbitrary, including nested, counterfactual identification to a linear program.
Results
The linear programs yield tight bounds, with structural causal models constructed to attain the solutions; the framework also recovers classical probability-of-causation bounds.
Takeaways & Limitations
Query-implied structural assumptions can produce informative bounds and tractable optimization without requiring an input causal graph.
Takeaways & Limitations
The underlying bounding optimization tasks are NP-hard, despite available approximate techniques for efficient bound estimation.
Abstract
from arXiv · showhide
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 \emph{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.
1 Introduction
The paper addresses partial identification when causal assumptions are insufficient for point identification and a fully specified causal graph may be unavailable. It extends graph-free bounding by using assumptions implied by counterfactual queries to formulate linear programs for arbitrary queries.
- Partial identification computes bounds when available causal assumptions do not uniquely determine a counterfactual query.This setting arises because multiple structural causal models may remain compatible with the available information.
- Tian and Pearl’s graph-free linear program computes sharp bounds on probabilities of causation from experimental and observational data.The framework can operate under general or mild assumptions, whereas weak assumptions may produce wide bounds.
- The paper uses precedence constraints implied by a query to reduce arbitrary counterfactual, including nested, partial-identification problems to linear programs.This approach avoids imposing additional structural commitments beyond those inherent in the query.
- The authors prove tightness by constructing witnessing structural causal models that attain the resulting bounds.The construction extends the classical bounding framework while preserving compatibility with the query-implied structure.
- The paper evaluates the procedure through case studies intended to show informative bounds without an input causal graph.The paper’s structure includes a bounding framework, extensions, practical examples, and conclusions.
2 Background
The background defines structural causal models, interventions, counterfactual and nested counterfactual queries, and partial identification. It then explains how query-implied precedence constraints support bounding while standard identifiability is recovered when bounds coincide.
- Structural Causal Models: A structural causal model consists of endogenous variables, exogenous variables with a distribution, and structural equations determining endogenous values.The paper represents each structural equation as a deterministic mechanism from endogenous and exogenous inputs.
- Structural Causal Models: The analysis restricts attention to recursive structural causal models whose induced directed graphs are acyclic.The graph connects each variable to its endogenous parents, and compatible models share the structural-equation signature.
- Interventions: An intervention replaces selected structural equations with constant assignments while leaving the exogenous distribution and other equations unchanged.Potential responses record the value of an outcome under the resulting sub-model for a given exogenous state.
- Counterfactuals: A counterfactual query asks for the probability of a conjunction of atomic assignments across potentially different intervened sub-models.When intervention subscripts differ, the query is characterized through a counterfactual distribution rather than a single interventional distribution.
- Nested Counterfactuals: Nested counterfactuals represent outcomes when one variable is set to the value it would have taken under another intervention.They therefore generalize ordinary interventions by allowing intervention values themselves to be potential outcomes.
- Partial Identifiability: Partial identification arises because multiple compatible structural causal models can yield different query values, so the task is to compute bounds.The paper focuses on minimization for brevity, with maximization handled analogously.
- Partial Identifiability: The optimization tasks are NP-hard, while approximate methods can estimate bounds efficiently; point identification occurs when the two bounds coincide.This establishes both the computational difficulty of general bounding and the relationship between partial and point identification.
- Queries and Partial Orders: A counterfactual variable can be non-trivial only when the intervention variable precedes the outcome in the underlying causal graph.If the intervention variable is not an ancestor of the outcome, the potential response equals the un intervened response.
3 Bounding Framework
The framework replaces an unavailable causal graph with query-compatible order information and a canonical response representation, reducing partial identification to linear programming. Signature partitioning and marginalisation preserve tightness while improving tractability.
- Response Representation: The optimisation can use a complete canonical PSCM determined by a total variable order instead of structurally heterogeneous compatible SCMs.Its single exogenous variable indexes all structural relations between endogenous variables and their ordered predecessors.
- Response Representation: Any counterfactual query in the ordered model is a linear combination of joint probabilities over response signatures.Observational probabilities are included as the special case with no interventions.
- Linear Programming Formulation: The resulting signature-state formulation has linear constraints and objective, so the bounds are obtained through a linear program.The optimisation variables q_sσ represent probabilities of signature states.
- Linear Programming Formulation: The LP yields the relaxed SCM optimisation exactly, and an SCM compatible with the order attains its solution, establishing tight identification bounds.This result applies to the LP before signature-state partitioning.
- Signature State Partitioning: Grouping signature states with identical evaluations against observations and the query produces a lifted LP that preserves soundness and tightness while improving tractability.The lifted formulation uses aggregated masses for equivalence classes.
- Marginalising Non-Queried Variables: For queries involving only Vγ, the empirical distribution is marginalised to Vγ before applying the LP formulation.This extends the method beyond the initial case where every endogenous variable appears in the query.
- Coping with Partial Orders: A partial query-implied order is handled by considering linear extensions, while Theorem 6 makes evaluating an arbitrary extension sufficient.Although unconstrained queries can have |Vγ|! extensions, no specific total order must be assumed or enforced.
- Complexity: The lifted LP’s optimisation space scales linearly with the size of the sample space of Vγ, contrasting with the naïve LP’s double-exponential scaling.The cited complexity result attributes the reduction to the quotient-space formulation.
4 Extensions
The LP mapping extends to conditional, nested, experimental, and structurally constrained queries. These extensions preserve linear optimisation by transforming query terms and incorporating additional evidence or expert restrictions.
- Conditional Queries: Conditional queries become linear-fractional programmes and are reduced to standard LPs using the Charnes-Cooper transformation.The equivalence relation is refined to evaluate both the joint event γ ∧δ and the conditioning event δ.
- Nested Queries: Nested counterfactuals are handled by un-nesting each nested term into standard counterfactual queries, preserving a linear objective.The procedure applies to the general case after all nested terms are transformed.
- Experimental Data: Experimental probabilities enter as linear constraints on signature probabilities, and multiple trials or heterogeneous data sources can be appended within the same LP.The lifted formulation refines equivalence classes using relevant interventional-event evaluations.
- Monotonicity and Weak Exogeneity: Monotonicity and weak exogeneity translate expert assumptions into logical restrictions on response signatures.Monotonicity removes states violating the specified inequality, while exogeneity imposes restrictions associated with unobserved confounding.
5 Examples
The examples show that query-implied orders and assumptions support tight, computationally feasible bounds for standard and nested counterfactuals, while stronger structural assumptions narrow intervals at the cost of larger optimization spaces.
- Probabilities of Causation: The framework reproduces classical tight bounds for probabilities of causation and extends them to non-binary treatments and outcomes.PNS uses eight signature variables and four empirical constraints, while conditional extensions yield analogous PN and PS bounds.
- Average Causal Effect: For ACE, the LP recovers established bounds without explicitly specifying a causal graph or its structural equations.With |X| = 3, the formulation uses 24 signature variables and six empirical constraints.
- Controlled Direct Effect: In the Lipid-data CDE example, query-implied assumptions alone produce valid but wide intervals, whereas weak exogeneity recovers Cai et al.’s analytical bounds.The weak-exogeneity constraint is implemented as {Y, W} ⊥⊥X; adding Y ⊥⊥{X, W} can collapse the bound to a point estimate.
- Natural Direct Effect: Nested counterfactual syntax induces the complete order X ≺W ≺Y, enabling un-nesting and an LP whose optimization space is bounded by O(|X| · |W| · |Y|).The transformation preserves linearity and supports modern LP solvers without requiring additional graph assumptions.
- Natural Direct Effect: In the Berkeley admissions example, stronger weak-exogeneity assumptions narrow NDE bounds but expand |Tσ| and may misrepresent complex dynamics.The method evaluates the NDE using only query-inherent assumptions, while the standard fairness model gives a point estimate of 0.043 under stronger structure.
6 Conclusions
The paper presents a linear-programming framework for tightly bounding arbitrary counterfactual queries, including nested ones, using only assumptions implied by the query. It constructs bound-attaining SCMs and reduces optimization complexity through query symmetries, while accepting wider intervals than fully specified graphs.
- Conclusions: The framework partially identifies arbitrary, including nested, counterfactual queries using only structural assumptions inherent to each query.It extends Tian and Pearl’s classical probability-of-causation bounding framework.
- Conclusions: The bounds are tight, invariant to marginalizing variables absent from the query, and accompanied constructively by an SCM attaining them.Query symmetries further reduce the optimization space and improve tractability.
- Conclusions: Reducing reliance on domain knowledge and explicit conditional independencies yields naturally wider intervals than a fully specified causal graph.This is the method’s acknowledged trade-off rather than a failure of the LP formulation.
A Proofs
The proofs establish that counterfactual queries can be represented through response signatures and solved exactly by ordinary or lifted linear programs. They also show tightness, witness SCMs, and invariance across compatible orderings.
- Response-signature representation: Each exogenous state corresponds bijectively to a response signature, whose truth values determine atomic and conjunctive counterfactual queries.Deterministic structural equations make the signature mapping well-defined, while canonicalisation establishes bijectivity.
- Tightness: The LP over response-signature probabilities yields the exact optimisation value and admits an SCM that attains its bound.The proof constructs feasible distributions and translates an optimal LP solution back into a compatible SCM.
- Tightness: The lifted LP preserves feasibility, objective values, and tightness while improving tractability through equivalence classes of signatures.Uniformly redistributing lifted mass recovers a feasible solution in the original signature space.
- Partial orders: For partial orders, optimisation can range over linear extensions, but the resulting LP is identical for every compatible extension.The variables, constraints, and objective are independent of the chosen extension, so any compatible ordering gives the same bounds.
B Additional Experiments
The experiments examine ACE bounds, GPNS scalability, and canonical specifications. They show informative but wider bounds than graph-based methods, polynomial lifted-LP scaling, and tractable computation as domains expand.
- ACE with imperfect compliance: The ACE comparison reports lower and upper bounds grouped by study for the vitamin A and coronary prevention datasets.The comparison uses the Balke–Pearl LP formulation and its later generalisation as the graph-based benchmark.
- ACE with imperfect compliance: Our ACE bounds remain informative but are substantially wider than Balke–Pearl bounds because the method uses only query-induced order restrictions.The graphical comparison additionally assumes exclusion of a direct effect from Z to Y and independence from an unobserved confounder.
- ACE with imperfect compliance: Monotonic treatment response raises negative lower bounds on effects to zero, but monotonicity and weak exogeneity remain insufficient to recover graphical-model bounds.The restriction is Yx1,z ≥Yx0,z for every z ∈Z.
- PNS generalisation for non-binary variables: GPNS(r) benchmarks vary ordinal treatment and outcome cardinalities n from 4 to 15 and evaluate r ∈{2, 3, 4}.For binary variables, GPNS(2) reduces to the standard PNS event.
- Canonical specifications: Figure 3 contrasts Markovian, partially confounded, and fully shared-exogenous canonical PSCM specifications compatible with X ≺W ≺Y.Grey nodes denote exogenous variables.
- PNS generalisation for non-binary variables: The lifted GPNS LP has at most n2 variables, consistent with polynomial scaling, and remains tractable for standard solvers as domains expand.Measured end-to-end time includes signature detection, LP construction, aggregation, and numerical optimisation overhead.
C Canonical Specifications
Canonicalisation replaces finite discrete SCMs with equivalent canonical PSCMs that enumerate deterministic response functions. Exogenous states act as selectors for these mappings, including under latent confounding.
- Canonicalisation: A partially specified SCM can be represented canonically from a causal graph when endogenous variables have finite domains.The canonical construction is used in the proof of Theorem 1.
- Response functions: Each exogenous state selects a deterministic mapping from a variable’s parent configurations to its value.For V with parents PaV, exactly |V||PaV| such mappings are possible.
- Confounding: In Markovian models, independent exogenous variables can be replaced by finite canonical variables with cardinality |V||PaV|.Semi-Markovian models instead allow exogenous variables to jointly affect multiple endogenous variables through confounded components.
- Canonicalisation: Canonicalisation preserves the complete set of observational and counterfactual distributions of any discrete SCM or PSCM.Thus the canonical representation is distributionally equivalent for the queries considered.
- Worked example: For X ≺W ≺Y with binary X,Y and ternary W, canonical specifications enumerate response functions across unconfounded and differently confounded structures.The example includes singleton c-components and shared exogenous variables.