PaperlayerView exact revision on arXiv

Source-linked AI summary

Permutation-Based Causal Structure Learning with Unknown Intervention Targets

Chandler Squires, Yuhao Wang, Caroline Uhler

arXiv:1910.09007v2stat.ME

TL;DR

Unknown intervention targets complicate causal DAG learning, particularly when gene-knockout experiments have off-target effects. The paper characterizes the identifiable interventional equivalence class and proposes a consistent algorithm that learns it alongside the targets. Under a specific faithfulness assumption, targets are identifiable and the degree of model identifiability matches the known-target setting.

  • Problem

    The paper addresses learning causal DAGs from observational and interventional data when intervention targets are unknown, a relevant issue because gene knockouts can have off-target effects.

    Source: §1 · p. 1

  • Method

    A score-based greedy permutation-search algorithm learns intervention targets and the I-MEC from mixed observational and interventional data.

    Source: §1 · p. 2, §4.2 · p. 5

  • Results

    Under a specific faithfulness assumption, all intervention targets are identifiable, so causal-model identifiability matches the known-target setting.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The protein-signaling analysis suggests the method is a viable tool for biological data analysis.

    Source: §6 · p. 9

    The identifiability result relies on the stronger I-faithfulness assumption, which requires conditional distributions for intervened targets to differ from observational ones across conditioning sets.

    Source: §3.2 · p. 4, §4.2 · p. 6

Abstract

from arXiv · show

We consider the problem of estimating causal DAG models from a mix of observational and interventional data, when the intervention targets are partially or completely unknown. This problem is highly relevant for example in genomics, since gene knockout technologies are known to have off-target effects. We characterize the interventional Markov equivalence class of DAGs that can be identified from interventional data with unknown intervention targets. In addition, we propose a provably consistent algorithm for learning the interventional Markov equivalence class from such data. The proposed algorithm greedily searches over the space of permutations to minimize a novel score function. The algorithm is nonparametric, which is particularly important for applications to genomics, where the relationships between variables are often non-linear and the distribution non-Gaussian. We demonstrate the performance of our algorithm on synthetic and biological datasets. Links to an implementation of our algorithm and to a reproducible code base for our experiments can be found at https://uhlerlab.github.io/causaldag/utigsp.

1 INTRODUCTION

Causal structure learning aims to recover causal relationships from data, but observational data alone can leave DAGs indistinguishable. This paper addresses unknown intervention targets by characterizing the identifiable equivalence class and proposing a consistent learning algorithm.

1 INTRODUCTION

  • Prior methods for known intervention targets can be inconsistent with off-target effects, while existing unknown-target approaches have scalability, parametric, or modeling-assumption limitations.The paper also proposes comparing its algorithm with the JCI framework.Source: §1 · pp. 1–2
  • Under a specific faithfulness assumption, all intervention targets are identifiable, giving the same degree of causal-model identifiability as when targets are known.The result addresses uncertainty from off-target effects in gene-knockout experiments, which can otherwise lead to model misspecification and incorrect conclusions.Source: §1 · pp. 1–2
  • The paper introduces a score minimized by graphs in the true I-MEC and a provably consistent greedy algorithm that learns targets and the I-MEC from mixed data.The method is designed for intervention targets that are partially or completely unknown.Source: §1 · p. 2
  • The authors demonstrate the algorithm on synthetic and biological datasets.The supplied passage does not report specific performance comparisons.Source: §1 · p. 2

2 PRELIMINARIES AND RELATED WORK

The preliminaries establish DAG-based causal models and the equivalence classes used to describe what data can identify. They then introduce intervention invariance and situate the proposed unknown-target method among existing discovery algorithms.

2.1 Causal DAG model

  • A causal DAG encodes a model whose density factorizes according to the graph; under faithfulness, conditional independences correspond to its d-separation statements.DAGs are Markov equivalent when they have the same skeleton and v-structures, and equivalent DAGs can be connected by covered edge reversals.Source: §2.1 · p. 2

2.2 Interventions

  • The I-Markov property requires conditional distributions of non-intervened variables to remain invariant across observational and interventional distributions, defining an I-Markov equivalence class.The discussion distinguishes perfect interventions, which remove dependencies between targets and causes, from imperfect interventions, which modify those relationships.Source: §2.2 · pp. 2–3

2.3 Causal structure discovery algorithms

  • Existing discovery methods include constraint-based, score-based, and hybrid approaches, but assume no interventional data or known targets; the paper adapts GSP to JCI and develops UT-IGSP.JCI-GSP treats intervention variables like system variables, motivating UT-IGSP; JCI had not previously been applied to hybrid methods.Source: §2.3 · p. 3

3 IDENTIFIABILITY WITH UNKNOWN INTERVENTION TARGETS

The paper characterizes what can be identified when intervention targets are unknown and shows that, under a faithfulness condition, target uncertainty does not reduce identifiability. It also establishes a condition needed for identifying the I-MEC in this setting.

3 IDENTIFIABILITY WITH UNKNOWN INTERVENTION TARGETS

  • With unknown intervention targets, the identifiable I-MEC is the same as when targets are known, so the degree of causal-model identifiability is unchanged.The paper motivates this characterization as a prerequisite for defining consistency in the unknown-target setting.Source: §3 · p. 4

3.1 Preliminaries

  • For multiple experiments, the I-Markov property requires conditional distributions to remain invariant across experiments when the variable is not targeted in either experiment.The setting also assumes access to observational data.Source: §3.1 · p. 4
  • The I-DAG adds intervention vertices and target edges to a DAG; I-equivalence is characterized by matching skeletons and v-structures, and its class can be represented by an I-essential graph.In that graph, directed edges have the same orientation across the class, while undirected edges vary in orientation.Source: §3.1 · p. 4

3.2 Main results

  • Under direct I-faithfulness, the intervention targets are identifiable; violating this assumption can leave distinct I-MECs indistinguishable from the same distributions.The example gives two different DAGs and intervention sets that generate the same observational and interventional distributions.Source: §3.2 · pp. 4–5

4 ALGORITHM AND ITS CONSISTENCY

The paper develops UT-IGSP to learn the I-MEC and intervention targets together without an exhaustive target search. Its permutation-based score and restricted edge reversals support consistency under the stated faithfulness assumption.

4 ALGORITHM AND ITS CONSISTENCY

  • Directly estimating intervention targets may require searching 2^p−1 variable subsets, which is intractable for problems with hundreds or thousands of nodes.UT-IGSP instead learns a complete target list and the I-MEC simultaneously.Source: §4 · p. 5

4.1 Preliminaries

  • UT-IGSP adapts GSP's greedy search over variable permutations, associating each ordering with a minimal I-MAP and searching for lower-scoring alternatives.In GSP, the minimal I-MAP includes an edge when the variables are conditionally dependent given the variables preceding them in the ordering.Source: §4.1 · p. 5

4.2 Main results

  • UT-IGSP replaces GSP's edge-count score with a score whose observational term targets the correct MEC and whose invariance term narrows the optimum to the I-MEC.The score uses conditional-independence and conditional-invariance tests, respectively.Source: §4.2 · p. 5
  • The algorithm estimates targets from conditional distribution changes and searches using I-covered reversals, which use interventional data to restrict the available directions.The algorithm starts from a permutation and iteratively seeks a lower-scoring permutation connected by I-covered arrow reversals.Source: §4.2 · pp. 5–6
  • Under Assumption 2, UT-IGSP and JCI-GSP consistently recover the data-generating I-Markov equivalence class and intervention targets.The proof uses the JCI framework; UT-IGSP has at least as many search directions as JCI-GSP and can have more, yielding consistency under strictly weaker conditions in the paper's comparison.Source: §4.2 · pp. 6–7
  • In Example 2, JCI-GSP is not consistent, while UT-IGSP can reach the target graph through reversals from G312 to G132 and then Gjoint*.The example illustrates UT-IGSP's additional search directions under a faithfulness violation.Source: §4.2 · p. 7, Figure 2 · p. 7
  • Unlike IGSP's marginal-invariance criterion, UT-IGSP's I-covered-edge definition adapts to intervention strength, reducing false negatives when interventions have enough power.False negatives in determining I-covered edges can cut off the path to the sparsest I-MAP.Source: §4.2 · p. 7

5 EMPIRICAL RESULTS

UT-IGSP is evaluated against methods that assume known intervention targets on simulated and protein-signaling data. It performs best in simulations with off-target effects and is comparable to IGSP on the biological data.

5.1 Simulated data

  • In Figure 3 simulations, UT-IGSP outperforms all other methods when off-target effects exist; it also outperforms them with no off-target effects (ℓ = 0).Figure 3 reports structural Hamming distance and the proportion of consistently estimated I-MECs across sample sizes and off-target counts, using 100 Gaussian DAG models on 20 nodes.Source: §5.1 · p. 8, Figure 3 · p. 8
  • GIES performance degrades drastically as off-target effects increase, while IGSP degrades only slightly; UT-IGSP runs in under 1 second on 20-node graphs and 20 seconds at p = 100, ℓ = 3, and s = 1.5.The simulations used 100 Gaussian DAG models with 20 nodes; Figure 3 varies sample count and off-target count.Source: §5.1 · p. 8, Figure 3 · p. 8

5.2 Biological data

  • On protein-signaling data, IGSP and UT-IGSP outperform GIES, perform comparably to each other, and UT-IGSP* performs similarly to UT-IGSP.The authors suggest the comparable IGSP and UT-IGSP performance may indicate that these data contain no off-target effects.Source: §5.2 · p. 9, Figure 4 · p. 9

6 DISCUSSION

The discussion presents a consistent method for learning the interventional Markov equivalence class despite unknown intervention targets. It identifies possible applications beyond genomics and names latent confounding as a future extension.

6 DISCUSSION

  • The I-Markov equivalence class is identifiable without prior knowledge of intervention targets, and the paper presents an algorithm with theoretical consistency guarantees for learning it despite off-target effects.The protein-signaling application suggests the method is viable for biological data analysis.Source: §6 · p. 9
  • The method can also treat heterogeneous observational sources from naturally perturbed systems as interventional distributions with imperfect interventions and unknown targets.Examples include gene-expression data from normal and diseased states and stock data before and after a financial crisis.Source: §6 · p. 9
  • Extending UT-IGSP to handle latent confounding and applying it to other datasets are proposed as future work.Source: §6 · p. 9

Supplementary Material

The supplementary material defines graph separation and independence-map terminology used in the paper. It also states how an independence map relates to conditional independence relations.

A DAG models

  • A collider is a triple i → k ← j; d-separation means no d-connecting path exists given the conditioning set.A path is d-connecting when each non-collider is outside the conditioning set and each collider or one of its descendants is in it.Source: A DAG models · p. 11
  • H is an independence map of G when M(G) ⊆ M(H), meaning every distribution Markov with respect to G is also Markov with respect to H.Source: A DAG models · p. 11
  • When G ≤ H, H entails a subset of the conditional independence relations entailed by G.Source: A DAG models · p. 11

B Assumption 1 Incomparability

This supplementary material shows that Assumption 1 and assumptions 4.4 and 4.5 do not imply one another. It also describes conditional invariance testing for multivariate Gaussian distributions.

B Assumption 1 Incomparability

C Conditional Invariance Testing

  • For multivariate Gaussian data, equality of conditional distributions reduces to equality of regression coefficients and variances, tested with Bonferroni-adjusted Chow and F tests.The null is tested at significance level α by testing both components at α/2.Source: C Conditional Invariance Testing · p. 11

D.1 Consistency of GSP

The GSP consistency argument shows how the search reaches a minimal I-MAP in the true I-MEC while retaining known adjacency and order constraints. JCI-GSP incorporates intervention-setting variables and known-target information into a background-constrained GSP search.

D.1 Consistency of GSP

  • GSP is consistent because any permutation whose minimal I-MAP is outside the true I-MEC has a connected reversal path to a graph with fewer edges.The argument uses a Chickering sequence and the fact that a nonminimal starting graph must have an edge addition along that sequence.Source: §D.1 · pp. 11–12
  • Known adjacencies are preserved because every I-MAP of the true graph contains its skeleton, so omitting tests for those pairs does not change the result.This adaptation retains GSP consistency when known adjacency constraints are supplied.Source: §D.1 · p. 12
  • The order-constrained Chickering sequence remains valid: reversals follow the target graph’s edge directions, and the analyzed edge-addition case preserves the known order.The proof rules out the two ways a sequence step could violate the order information.Source: §D.1 · p. 12

E JCI-GSP

  • JCI-GSP adds context variables for intervention settings, encodes generic context and known-target constraints, then runs GSP with that background information.The figure evaluates UT-IGSP and JCI-GSP on intervention-target recovery across sample counts and numbers of off-target effects.Source: E JCI-GSP · p. 13, §D.1 · p. 13, Figure 5 · p. 13

F.1 Intervention Recovery

The intervention-recovery evaluation reports false-positive targets for UT-IGSP and notes that false negatives were negligible for both methods.

F.1 Intervention Recovery

  • False negatives averaged less than 0.04 for both methods in the intervention-target recovery evaluation.The figure reports the number of false-positive intervention targets for UT-IGSP.Source: §F.1 · p. 13
  • The evaluation reports false-positive intervention targets for UT-IGSP.The passage does not provide a numerical false-positive result.Source: §F.1 · p. 13
  • The evaluation uses the same generated data as Section 5.1.Source: §F.1 · p. 13

F.2 Perfect Interventions

With perfect interventions, UT-IGSP outperforms GIES as sample counts grow, although GIES does better at 1,000 samples when there are no off-target effects. Even one off-target intervention sharply reduces GIES performance.

F.2 Perfect Interventions

  • With perfect interventions, UT-IGSP outperforms GIES as samples grow, while one off-target effect sharply reduces GIES; at ℓ=0 and n=1,000, GIES outperforms UT-IGSP.GIES performs better at ℓ=0 than it did with shift interventions.Source: §F.2 · p. 13
  • The experiment uses perfect interventions that remove dependencies between intervened nodes and their parents and change intervened-node noise variance to 0.1 around a mean of 1.Source: §F.2 · p. 13
  • Figure 6 measures average Hamming distance to the true I-essential graph and the proportion of consistently estimated I-MECs across 100 Gaussian DAGs on 20 nodes.The figure varies sample count and number of off-target effects.Source: Figure 6 · p. 14
Loading 1910.09007v2…