PaperlayerView exact revision on arXiv

Source-linked AI summary

Permutation-based Causal Inference Algorithms with Interventions

Yuhao Wang, Liam Solus, Karren Dai Yang, Caroline Uhler

arXiv:1705.10220v2stat.MEstat.AP

TL;DR

Large-scale genomics creates a need for efficient causal-discovery methods that combine observational and interventional data. This paper develops two interventional adaptations of Greedy SP, proves consistency under faithfulness, and evaluates them on simulated and real datasets. The methods provide consistency guarantees and, for IGSP, a nonparametric alternative suitable for non-Gaussian data, while scalability to 20,000 nodes and latent confounders remain future challenges.

  • Problem

    Large-scale single-cell genomics requires efficient and reliable causal-inference algorithms that use both observational and interventional data.

  • Method

    The paper develops two hybrid, permutation-based interventional adaptations of Greedy SP for causal inference with observational and interventional data.

  • Results

    Both algorithms are consistent under the faithfulness assumption, and the study evaluates them on simulated, protein-signaling, and single-cell gene-expression datasets.

  • Takeaways & Limitations

    IGSP is implementable, competitive with GIES, and nonparametric, so it does not require a linear Gaussian assumption for typically non-Gaussian biological data.

  • Takeaways & Limitations

    Future work must address scalability to 20,000 nodes and extend IGSP to allow latent confounders.

Abstract

from arXiv · show

Learning directed acyclic graphs using both observational and interventional data is now a fundamentally important problem due to recent technological developments in genomics that generate such single-cell gene expression data at a very large scale. In order to utilize this data for learning gene regulatory networks, efficient and reliable causal inference algorithms are needed that can make use of both observational and interventional data. In this paper, we present two algorithms of this type and prove that both are consistent under the faithfulness assumption. These algorithms are interventional adaptations of the Greedy SP algorithm and are the first algorithms using both observational and interventional data with consistency guarantees. Moreover, these algorithms have the advantage that they are nonparametric, which makes them useful also for analyzing non-Gaussian data. In this paper, we present these two algorithms and their consistency guarantees, and we analyze their performance on simulated data, protein signaling data, and single-cell gene expression data.

1 Introduction

Causal discovery from observational data alone generally identifies a DAG only up to Markov equivalence, motivating methods that combine observational and interventional data. New genomics technologies make this challenge especially urgent at single-cell scale.

  • Observational data alone generally identifies the underlying DAG only up to its Markov equivalence class.Different DAGs can encode the same conditional independence relations, so interventional data is needed to identify the complete DAG.
  • Drop-seq enables high-resolution observational single-cell gene-expression data at very large scale.
  • Perturb-seq combines this technology with CRISPR/Cas9 to produce high-throughput interventional gene-expression data.
  • The paper targets efficient and consistent causal-discovery algorithms for datasets of roughly 100,000 cells across 20,000 genes.

2 Related Work

Existing causal-inference methods include constraint-based, score-based, and hybrid approaches, while interventional extensions such as GIES address combined data but leave consistency and distributional limitations.

  • Causal-inference algorithms are commonly classified as constraint-based, score-based, or hybrid methods.Constraint-based methods use conditional-independence tests, whereas score-based methods optimize scores such as BIC through greedy approaches.
  • GIES extends GES to interventional data and can be viewed as greedy ℓ0-penalized maximum-likelihood estimation.This makes an otherwise computationally infeasible score-based approach usable, but GIES is parametric.
  • The paper introduces the first non-enumerative algorithms for observational and interventional causal inference with consistency guarantees.
  • Unlike GIES, the proposed algorithms are nonparametric and do not assume Gaussianity, which suits inherently non-Gaussian gene-expression data.

3 Preliminaries

The preliminaries define DAG-based conditional independence, Markov equivalence, interventions, and GIES, then motivate permutation-based Greedy SP adaptations by exposing a consistency failure of GIES.

  • DAG models: A DAG associates random variables with nodes, while its non-arrows encode conditional-independence relations through the Markov property.
  • DAG models: Markov-equivalent DAGs share the same d-separation statements and form a Markov equivalence class represented by a CP-DAG.
  • Learning from Interventions: An intervention removes incoming arrows to targeted nodes, producing an intervention DAG with respect to which the interventional distribution is Markov.
  • GIES: GIES greedily adds, removes, and reverses arrows across I-MECs, selecting the highest-scoring candidate in repeated forward, backward, and turning phases.
  • GIES: Under faithfulness, GIES may fail to recover the optimal I-MEC even as total interventional and observational sample size tends to infinity.
  • Greedy SP: Greedy SP maps each variable permutation to a minimal I-MAP and searches for sparser DAGs by transposing elements through covered-edge reversals.In the observational setting, Greedy SP is consistent when the data-generating distribution is faithful to the sparsest DAG.

4 Two Permutation-Based Algorithms with Interventions

The paper introduces two interventional adaptations of Greedy SP: a score-based method using interventional BIC scores and IGSP, which restricts edge reversals using intervention-specific criteria. Both algorithms have consistency guarantees under faithfulness, while Algorithm 1 requires a slack parameter and the theory is developed primarily for low-dimensional settings.

  • Algorithm 1: Algorithm 1 retains Greedy SP's moves but optimizes the sum of interventional BIC scores.The score combines interventional log-likelihoods with an edge-count penalty λ_nk = log n_k.
  • Algorithm 1: Algorithm 1 returns the data-generating DAG's I-MEC almost surely when all interventional sample sizes grow and faithfulness holds.The theorem assumes P is Markov with respect to an unknown I-MAP and each interventional distribution is faithful to its corresponding graph.
  • Algorithm 1: Algorithm 1 is inconsistent without the slack parameter δ_n, making that parameter a computationally problematic but necessary design element.The paper demonstrates this necessity through a focused example and refers to supplementary calculations.
  • Algorithm 2: IGSP: IGSP keeps the minimal I-MAP edge-count score but restricts search to I-covered reversals, prioritizing those that are also I-contradicting.Its depth-first search prefers moves that leave the current I-Markov equivalence class and otherwise seeks a sparsest reachable minimal I-MAP.
  • Algorithm 2: IGSP: Algorithm 2 is consistent under faithfulness and, with only observational data, reduces to Greedy SP.Interventional information generally narrows the candidate reversal set and can yield a smaller equivalence class than observational data alone.

5 Evaluation

The evaluation compares IGSP and GIES on simulated, protein-signaling, and perturb-seq data using observational and interventional information. IGSP improves relative to GIES as sample size increases and generally outperforms GIES on the real datasets described.

  • Simulations: IGSP performs better than GIES as the sample size increases in simulated Gaussian DAG studies.The simulations used p ∈ {10, 20}, one or two intervention sets, and n = 10^3, 10^4, 10^5 samples per intervention.
  • Simulations: In the focused simulation where GIES is inconsistent, GIES recovers the target DAG at a lower rate than Algorithm 2.The study varied edge-weight lower bounds c = 0.1, 0.25, 0.5 and intervention targets {4}, {5}, or {4, 5}.
  • Perturb-seq gene expression data: The perturb-seq dataset contains approximately 30,000 cells, 32,777 measured genes, and single-gene deletion interventions.After quality processing, the analysis used 992 observational samples and 13,435 interventional samples from eight gene deletions, learning DAGs over 24 genes.
  • Perturb-seq gene expression data: IGSP predicted held-out perturb-seq intervention effects better than GIES and random guessing for several CI-test cut-offs.Each evaluation left out one intervention dataset while training the corresponding causal DAG.

6 Discussion

The paper presents two interventional adaptations of Greedy SP with consistency guarantees under faithfulness, and identifies IGSP as an implementable, nonparametric alternative to GIES. The discussion highlights its real-data performance while noting scalability and latent-confounder extensions as future challenges.

  • Both proposed algorithms are consistent under the faithfulness assumption and are the first such algorithms using observational and interventional data apart from DAG enumeration.
  • IGSP is implementable, competitive with GIES, and nonparametric, so it does not require a linear Gaussian assumption.The paper reports real-data studies on protein-signaling and single-cell gene-expression datasets with typically nonlinear, non-Gaussian noise.
  • The gene-expression intervention analysis defines an effective deletion using a Wilcoxon rank-sum test with α = 0.05.Ineffective interventions are attributed to poor targeting ability of the guide RNA designed for the gene.
  • For the perturb-seq evaluation, a predicted arrow counts as a true positive when the corresponding gene knockout significantly changes the target-gene distribution.Significance is based on a Wilcoxon rank-sum test with α = 0.05, approximately equivalent to a q-value magnitude ≥3 in Figure 5(a).
  • Scaling the algorithms to 20,000 nodes, the typical number of genes in these studies, remains a future challenge.The paper also identifies extending IGSP to allow latent confounders as future work.

A Counterexample to Consistency of GIES.

The paper constructs a counterexample showing that GIES with the BIC score can converge to a local maximum that is not consistent, even under faithfulness. The score comparison uses observational and interventional contributions under balanced sample sizes.

  • Counterexample setup: GIES can reach a DAG that is a local maximum of its algorithm despite faithfulness of the observational distribution to the data-generating DAG.The counterexample uses interventions I = {∅, {4}, {5}} and sample sizes n1 = Cn2 = Cn3 for C > 1.
  • Deletion and reversal phases: The only covered edge in G is 5 →4, so its I-MEC has size one and no deletion improves the BIC score.G is the minimal I-MAP associated with permutation π = 1276543; consistency of GES under faithfulness handles edge deletions.
  • Score comparison: The score of G is decomposed into regression-residual terms computed using data from intervention sets truncated for each node.For node j, I−j excludes interventions targeting j, and s(j, Pa_G(j), X̂_I−j) is the log regression residual.
  • Deletion and reversal phases: The distributions of the relevant partial-correlation statistics are identical under the balanced sample-size assumption, making reversal of 5 →4 decrease the score with probability 1.Thus Score(G′, X̂) < Score(G, X̂) for the reversal candidate.
  • Deletion and reversal phases: Turning any other non-covered edge also fails to improve the score because sufficiently large observational weight makes G score higher than the alternative.Such alternatives are not independence maps of the un-intervened distribution P1.

B Counterexample to Consistency of Algorithm 1 without the Slack Factor

Without the slack factor δn, Algorithm 1 inherits a related inconsistency counterexample. Its only available reversal decreases the score with probability 1 under the same intervention and sample-size setup.

  • Available move: Algorithm 1 can only reverse the covered arrow 5 →4 because it restricts moves to covered-edge reversals in the observational DAG.Let G′ be the graph after this reversal.
  • Score comparison: The relevant partial-correlation distributions are identical, so Score(G′, X̂) < Score(G, X̂) with probability 1.This prevents the algorithm from accepting the available reversal.

C Proof of Theorem 4.1

The proof of Theorem 4.1 combines Chickering-style sequences, induction over sink resolutions, and score comparisons. Under faithfulness, Algorithm 1 reaches the true I-MEC while allowing score decreases of at most δn along covered reversals.

  • Chickering sequence: An independence-map relation admits a sequence of covered arrow reversals and additions that preserves intermediate independence-map relations.This transformational relationship underlies the construction of the required graph sequences.
  • Sink resolution: APPLY-EDGE OPERATION recursively resolves common sink nodes, separating graph transformations into subsequences that fix one sink at a time.The remaining sinks are resolved through arrow reversals and additions in the relevant subDAG.
  • Inductive path argument: The induction proves that newly created d-connections arise through the sink node removed from the conditioning set, preserving the required path orientation property.This stronger statement supports the lemmas governing covered reversals in the sequence.
  • Consistency conclusion: Under faithfulness of all observational and interventional distributions, Algorithm 1 returns the I-MEC of the data-generating DAG.The proof constructs a sequence of minimal I-MAPs from an arbitrary permutation graph toward the data-generating graph.
  • Score argument: Along the constructed sequence, covered reversals do not reduce the score by more than δn, while transitions involving different I-MECs have higher score at the target graph.The latter comparison uses faithfulness of the relevant interventional distribution.

D Proof of Theorem 4.4

The proof of Theorem 4.4 shows that Algorithm 2 can move from any permutation graph to the data-generating graph using I-covered reversals. It then uses I-contradicting arrows to identify the true I-MEC under faithfulness.

  • Consistency conclusion: Algorithm 2 returns a DAG I-Markov equivalent to the data-generating DAG under the faithfulness assumption.The proof combines the existence of I-covered reversal sequences with the reduction of I-contradicting arrows.
  • I-covered reversals: For any permutation, a sequence of I-covered arrow reversals leads to the data-generating DAG through intermediate I-MAPs.This is established by Theorem D.1.
  • I-covered reversals: Each reversal in the sequence is I-covered because interventions targeting one endpoint cannot contain the corresponding directed edge in the relevant interventional DAG.The argument uses the d-connection orientation property from Lemma C.2.
  • Progress measure: When successive graphs lie in different MECs, the constructed sequence decreases the number of arrows; within the true MEC, it decreases I-contradicting arrows.Thus the two types of moves provide progress toward the true interventional equivalence class.
  • Consistency conclusion: The true I-MEC contains DAGs with the fewest I-contradicting arrows, completing the identification argument within the true MEC.This follows from Theorem D.2 in the proof of Theorem 4.4.

E Supplementary Material for Real Data Analysis

The supplementary material provides additional details on the perturb-seq and protein-signaling analyses, including datasets, reconstructed networks, and interaction-prediction comparisons.

  • Perturb-seq analysis: The supplement documents perturb-seq experiments and presents additional causal-network reconstruction details.Figure E.1 describes gene-deletion effects, while Figure E.2 compares the ground-truth and reconstructed partial networks.
  • Dataset details: Table E.1 and Table E.2 report sample counts for the processed perturb-seq gene deletions and protein interventions, respectively.These tables provide dataset-level details supporting the corresponding real-data analyses.
  • Perturb-seq analysis: Figure E.1 summarizes true effects across 56 guide RNAs and measured genes, with 18 effective guides targeting 8 genes selected for analysis.Red, blue, and white encode positive, negative, and zero effects on the q-value scale, respectively.
  • Perturb-seq analysis: Figure E.2 compares a thresholded ground-truth partial causal network with Algorithm 2 using a Gaussian CI test at α = 0.15.Blue edges are true positives, green edges are false positives, and gray nodes receive interventions.
  • Protein-signaling analysis: The supplement includes protein-signaling network reconstructions and a table comparing IGSP and k-IGSP with methods allowing latent confounders.Figure E.3 uses blue for true positives, purple for reversed edges, and green for false positives.
Loading 1705.10220v2…