Ancestral Causal Inference

Motivation

• Constraint-based methods handle latent confounders and selection bias without parametric modeling assumptions, while logic-based formulations facilitate background-knowledge integration.Source: §1 · p. 1

Limitations of prior work

• Existing reliability improvements either sacrifice accuracy through greedy reasoning or scalability through optimization over super-exponentially large spaces.Source: §1 · pp. 1–2

ACI contribution

• ACI reasons over ancestral rather than direct causal relations, reducing computation while retaining comparable accuracy for latent-variable systems without feedback.Source: §1 · p. 2
• Confidence scores rank causal predictions by reliability, addressing a major practical impediment to the use of constraint-based methods.Source: §1 · p. 2

Results

• ACI is proved sound and asymptotically consistent, outperforms bootstrapped FCI and CFCI in accuracy, and achieves several-orders-of-magnitude speedup over on synthetic data.It also combines observational and interventional data for a protein-data application.Source: §1 · p. 2

Preliminaries

• The framework assumes a causal DAG with possible latent variables, no selection bias, and Causal Markov and Causal Faithfulness assumptions.Source: §2 · p. 2
• An ancestral relation holds when a directed path connects one observed variable to another, and the true ancestral structure is the transitive closure of projected direct relations.Source: §2 · pp. 2–3
• Minimal conditional independences and dependences encode whether conditioning on an additional variable changes the relation, linking statistical tests to ancestral deductions.Source: §2 · p. 3

Ancestral reasoning

• Rules derived from these relations allow ancestral information to be deduced directly from independences, which is central to ACI's scalability.Source: §2 · p. 3

Related work

• Conservative PC, CFCI, BCCD, and COmbINE resolve conflicting inputs through redundant checks, reliability ordering, or incremental constraint integration.Source: §2 · p. 3
• HEJ corrects input errors by minimizing violated weighted independences over causal graphs, but its encoding-DAG search space is computationally demanding.Source: §2 · p. 3

ACI formulation

• ACI replaces HEJ's encoding-DAG optimization with optimization over simpler ancestral structures that remain expressive in the presence of latent variables and statistical errors.Source: §3 · pp. 3–4

Scalability

• For 7 variables, the search contains 6 × 10^6 ancestral structures versus 2.3 × 10^15 ADMGs, illustrating the representation's computational advantage.Source: §3 · p. 3

New rules

• ACI introduces five causal reasoning rules because HEJ's conditioning and marginalization rules cannot be directly adapted to ancestral relations.Source: §3 · p. 4

Correctness

• The proposed reasoning rules are sound, while completeness beyond the conjectured order-1 case is deliberately left for future work.Source: §3 · p. 4

Optimization

• The loss function sums weights of violated input statements over candidate structures, and Answer Set Programming provides a convenient implementation using clingo 4.Source: §3 · p. 4

Weighting schemes

• ACI supports weighted conditional independences and ancestral relations through frequentist p-value weights or Bayesian weights with tunable prior probabilities.Source: §3 · p. 4

Interventional data

• Interventional data can yield weighted ancestral statements by testing whether a target variable's distribution changes under intervention, including perfect, soft, mechanism-change, and activity interventions.Source: §3 · p. 5

• Confidence scores rank ancestral predictions by approximating their marginal probability, addressing the limited reliability estimates of constraint-based methods.Source: §4 · p. 5
• The method can also score direct causal relations when combined with HEJ, although the paper primarily considers ancestral relations.Source: §4 · p. 5
• The scoring method is sound for oracle inputs, assigning positive, negative, or zero confidence according to identifiability.Source: §4 · p. 5
• Completeness is not guaranteed: the rules are conjectured to be order-1-complete, while higher-order completeness remains future work.Source: §4 · p. 5
• Confidence scores are asymptotically consistent when statistical tests have vanishing errors and their weights diverge with sample size.Source: §4 · p. 5

Synthetic data

• For 7 variables, ACI is almost 3 orders of magnitude faster than HEJ, while HEJ completes only four of the first 40 eight-variable models before timeout.Source: §5 · p. 6
• ACI and HEJ outperform bootstrapped FCI and CFCI on synthetic precision-recall evaluations, despite using independence tests only up to order c = 1.Source: §5 · pp. 6–7, Figure 2 · p. 7
• With oracle descendant knowledge for 8-variable systems, ACI improves significantly, especially for ancestral predictions, whereas FCI and CFCI cannot directly use that knowledge.Source: §5 · p. 7

Application on real data

• On flow-cytometry data, ACI combines observational and interventional inputs, needs intervention targets rather than intervention types, and accommodates latent variables.Source: §5 · p. 7, Figure 3 · p. 8
• ACI can recover from faithfulness violations because it weights conflicting independence and ancestral evidence instead of committing first to a reconstructed skeleton.Source: §5 · p. 8

• Ancestral structures support background causal knowledge and offer computational advantages over finer-grained causal representations, while remaining mappable to direct causal relations when needed.Confidence estimates can further improve the reliability of causal relations inferred from data.Source: §6 · p. 8
• Higher-order independence tests do not substantially improve the optimization methods, possibly because the loss function assumes test results are independent.Accounting for dependence among test results could improve accuracy, but extending the loss function may be difficult.Source: §6 · p. 8

7.1 ACI causal reasoning rules

• ACI presents five reasoning rules that use conditional independence and dependence patterns, together with conditioning sets, to infer directed relations among variables.Source: §7.1 · p. 9
• The rule proofs assume a causal DAG with possible latent variables together with the causal Markov and causal Faithfulness assumptions.These assumptions support the path-based arguments used to establish the rules.Source: §7.1 · p. 9

7.2 Soundness

• For oracle inputs with infinite weights, the confidence score is +∞ for identifiable features, −∞ for identifiable negations, and 0 when neither is identifiable.This establishes soundness for any sound causal reasoning rule set, even when the rules are incomplete.Source: §7.2 · p. 10

7.3 Asymptotic consistency of scoring method

• Under the stated test assumptions, confidence scores converge to zero when neither a feature nor its negation is identifiable.The accompanying consistency result covers the identifiable cases as specified in Theorem 4.Source: §7.3 · p. 10

• ACI and HEJ deteriorate rather than improve when using higher-order independence tests with c = 4.The comparison uses frequentist testing with α = 0.05 and contrasts these methods with bootstrapped FCI and CFCI settings using c = 4.Source: §8 · p. 10, Figure 4 · p. 11
• With the Bayesian test and prior independence probability p = 0.1, ACI and HEJ overlap at c = 1 and outperform bootstrapped (C)FCI.The Bayesian test therefore leaves the overall comparison unchanged.Source: §8 · pp. 10–11

9 Application on real data

• The flow-cytometry data contain 11 biochemical agents measured under 14 experimental conditions grouped into no-ICAM and ICAM batches.Each batch includes observational data and seven interventional datasets with different activators and inhibitors.Source: §9 · p. 11, §9.1 · pp. 12–13

9.1 Experimental conditions

• The real-data analysis ignores global interventions in the PMA and β2CAMP datasets and treats PIP3 as the sole LY294002 target.These choices enable weighted ancestral-relations computation but rely on biological background knowledge and differ from the target treatment in [17].Source: §9.1 · p. 13

9.2 Results on no-ICAM batch

• The analysis combines weighted observational independences with weighted ancestral relations obtained by comparing interventional and observational distributions.ACI, bootstrapped anytime FCI, and CFCI estimate ancestral-relations matrices whose colors and intensities encode relation sign and confidence.Source: Figure 6 · p. 14, §9.2 · p. 14

9.3 ICAM batch

• ICAM and no-ICAM results are similar, and weighted ancestral relations give ACI an advantage over FCI and CFCI.The comparison indicates that ancestral predictions are robust across the two batches.Source: Figure 7 · p. 15, §9.3 · p. 15, Figure 8 · p. 16
• ACI recovers the MEK→ERK relation despite an observational faithfulness violation because it weights the independence and intervention evidence jointly.Skeleton-based methods such as (C)FCI or LoCI would treat MEK and ERK as nonadjacent after observing their independence.Source: §9.3 · pp. 15–16

9.4 Comparison with other approaches

• Among the top 21 ancestral relations, ACI and the transitive closure of the top 17 score-based relations from [17] are quite similar despite different assumptions and methods.ACI allows confounders and is constraint-based, whereas [17] assumes causal sufficiency and is score-based.Source: §9.4 · p. 16, Figure 9 · p. 16, Table 2 · p. 17

10 Mapping ancestral structures to direct causal relations

• ACI with restricted HEJ first recovers weighted ancestral relations, then constrains HEJ to compatible ADMGs when scoring direct causal relations.The procedure adds infinite-weight ancestral and non-ancestral constraints to HEJ before scoring direct relations.Source: §10 · pp. 18–19
• 2^(n^2/4)+o(n^2) reduction in the search space is achieved asymptotically for n variables by restricting HEJ to ADMGs matching the ancestral structure.Source: §10 · p. 19
• The restricted approach reuses ancestral scores for infinite direct-prediction scores to avoid flattening their ranking, while soft constraints remain an alternative under investigation.Source: §10 · p. 19
• ACI with restricted HEJ is much faster than standard HEJ while sacrificing only a little accuracy on simulated direct-relation predictions.For 8 variables, standard HEJ exceeds 2,500 seconds for all but 6 of the first 40 simulated models.Source: §10 · p. 19
• A second strategy would reconstruct a possibly incomplete PAG from ancestral relations and conditional (in)dependences before recovering direct relations, but conversion subtleties remain unresolved.Source: §10 · p. 19

11 Complete ACI encoding in ASP

• Answer Set Programming reduces search problems to computing optionally scored stable models and has been applied to NP-hard learning problems including Bayesian networks and ADMGs.Source: §11 · p. 19
• ACI uses the clingo 4 ASP solver and provides a complete encoding in clingo syntax.Source: §11 · p. 19
• Because ASP does not support real numbers, ACI scales all weights by 1000 and rounds them to the nearest integer.Source: §11 · p. 19

12 Open source code repository

• An open-source repository provides the algorithms and evaluation framework, designed to be easily extended.Source: §12 · p. 19
• The encoding generates candidate ancestral structures while forbidding cycles and violations of transitivity.Source: §12 · p. 20
• Set-valued causal relations are represented through existsCauses predicates that express whether a cause affects at least one member of a set.Source: §12 · p. 20
• Input independences and dependences are assigned model relations, with symmetry rules added to simplify subsequent reasoning.Source: §12 · p. 20
• Additional ACI rules encode conditional-independence and dependence constraints, including Rule 1’s derivation of X -/->Y from X || Y | U and X -/->U when causes(X,Y), indep(X,Y,U), and not existsCauses(X,U) hold.Source: §12 · p. 20
• The loss function penalizes mismatches between input and model (in)dependences and weighted ancestral relations, minimizing the total weight of failures.Source: §12 · p. 20