Scalable Intervention Target Estimation in Linear Models

Burak Varici, Karthikeyan Shanmugam, Prasanna Sattigeri, Ali Tajer

Introduction

This paper introduces CITE (Causal Intervention Target Estimator), a scalable algorithm designed to identify unknown "soft" intervention targets in linear causal models. By leveraging the sparse differences between precision matrices of observational and interventional data, CITE efficiently pinpoints where a system was disturbed, enabling faster and more accurate causal structure discovery in high-dimensional settings.

The Challenge of Unknown Interventions

Causal discovery aims to uncover the "who-causes-what" relationships in a system. While observational data can tell us which variables are related, it often leaves the direction of causality ambiguous—a challenge known as the Markov Equivalence Class problem. To solve this, researchers use interventions, deliberately changing a variable to see how the rest of the system reacts.

A causal graph illustrating an intervention I targeting specific nodes (3 and 5) in a system.

However, most existing methods assume we already know exactly which variables were intervened upon. In real-world scenarios like gene editing or complex IT system failures, we often don't know the exact targets, or there may be unintended "off-target" effects. Existing algorithms that try to find these unknown targets are usually computationally expensive (scaling exponentially as the number of variables grows) or limited to very specific types of data. This paper tackles the challenge of identifying these targets efficiently and at scale.

The CITE Algorithm

The authors focus on soft interventions in linear Structural Equation Models (SEMs). Unlike "perfect" interventions that completely overwrite a variable's value, soft interventions simply change its distribution (e.g., increasing its noise variance) without necessarily breaking its relationship with its parents.

The core innovation is the use of Precision Matrices ($\Theta = \Sigma^{-1}$). The authors observe that when a variable is intervened upon, the difference between the precision matrices of the observational and interventional data ($\Delta_\Theta$) is sparse.

The CITE algorithm works in three main steps:

  1. Filtering: It identifies "non-intervened source nodes"—variables whose statistics remain unchanged—to quickly narrow down the search space.
  2. Grouping: It partitions the remaining variables into equivalence classes based on their ancestral relationships.
  3. Target Identification: It uses a Lasso-type optimization (specifically an ADMM-based Precision Difference Estimation) to find the exact intervention sites within these groups.

By focusing on precision matrix differences rather than performing exhaustive conditional independence tests, CITE avoids the combinatorial explosion that plagues other methods.

Key Insights

  • Precision as a Shortcut: The inverse covariance (precision) matrix is a powerful proxy for local graph structure. Changes in this matrix directly highlight where the causal mechanism has been altered.
  • Topological Efficiency: The distribution of a node only depends on its ancestors. By grouping nodes into equivalence classes based on shared ancestors, the algorithm reduces an exponential search problem into a series of much smaller, manageable sub-problems.
  • Robustness to "Soft" Changes: The method is highly effective even when interventions are subtle, which is a more realistic model for biological systems and complex engineering environments than the "all-or-nothing" perfect intervention model.

Experimental Results

The authors evaluated CITE using synthetic Erdos-Rényi Directed Acyclic Graphs (DAGs) with 40 to 200 nodes, as well as real-world biological datasets (Protein Signaling Data and Gene Expression Data).

CITE demonstrates significant improvements in both speed and accuracy:

  • Speedup: In a 100-node system, CITE runs in less than 0.3 seconds, while the competing UT-IGSP algorithm takes over 61 seconds. CITE’s runtime scales gracefully as the number of variables increases.
  • High Precision: CITE achieves near-perfect precision in identifying intervention targets as the sample size increases, regardless of whether the system has 40 or 200 variables, and across different intervention types (shift, increased variance, and randomized).
Precision of estimating intervention targets across different intervention types and graph sizes.
  • Real-World Performance: On biological datasets, CITE proved more robust than state-of-the-art methods, consistently finding more true causal relationships with fewer false positives.

Limitations and Future Work

The primary limitation is that the current framework is strictly for linear models. While many real-world systems can be approximated as linear, many biological and physical processes are inherently non-linear. Additionally, the model assumes causal sufficiency, meaning there are no unobserved "latent" variables influencing the system. Extending these precision-difference ideas to non-linear DAGs and handling latent confounders are the next logical steps for this research.

Summary updated

Abstract

This paper considers the problem of estimating the unknown intervention targets in a causal directed acyclic graph from observational and interventional data. The focus is on soft interventions in linear structural equation models (SEMs). Current approaches to causal structure learning either work with known intervention targets or use hypothesis testing to discover the unknown intervention targets even for linear SEMs. This severely limits their scalability and sample complexity. This paper proposes a scalable and efficient algorithm that consistently identifies all intervention targets. The pivotal idea is to estimate the intervention sites from the difference between the precision matrices associated with the observational and interventional datasets. It involves repeatedly estimating such sites in different subsets of variables. The proposed algorithm can be used to also update a given observational Markov equivalence class into the interventional Markov equivalence class. Consistency, Markov equivalency, and sample complexity are established analytically. Finally, simulation results on both real and synthetic data demonstrate the gains of the proposed approach for scalable causal structure recovery. Implementation of the algorithm and the code to reproduce the simulation results are available at \url{https://github.com/bvarici/intervention-estimation}.
BibTeX
@inproceedings{varici2021scalable,
  author = {Burak Varici and Karthikeyan Shanmugam and Prasanna Sattigeri and Ali Tajer},
  title = {{Scalable Intervention Target Estimation in Linear Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=sLVJXf-BkIt},
}
Figure