Computationally and statistically efficient learning of causal Bayes\n nets using path queries

Kevin Bello, Jean Honorio

Abstract

Causal discovery from empirical data is a fundamental problem in many scientific domains. Observational data allows for identifiability only up to Markov equivalence class. In this paper we first propose a polynomial time algorithm for learning the exact correctly-oriented structure of the transitive reduction of any causal Bayesian network with high probability, by using interventional path queries. Each path query takes as input an origin node and a target node, and answers whether there is a directed path from the origin to the target. This is done by intervening on the origin node and observing samples from the target node. We theoretically show the logarithmic sample complexity for the size of interventional data per path query, for continuous and discrete networks. We then show how to learn the transitive edges using also logarithmic sample complexity (albeit in time exponential in the maximum number of parents for discrete networks), which allows us to learn the full network. We further extend our work by reducing the number of interventional path queries for learning rooted trees. We also provide an analysis of imperfect interventions.

Introduction

Uncovering causal relationships—knowing that $X$ causes $Y$ rather than just being correlated with it—is a "holy grail" in fields like genomics and economics. The fundamental challenge is that observational data (simply watching a system) is often insufficient. It can only identify a graph up to its Markov Equivalence Class. For example, observationally, $X \to Y$ and $Y \to X$ look identical. To break this symmetry, we need interventions (experiments where we force a variable to take a specific value).

However, performing interventions is expensive or difficult. Previous methods often required an exponential number of experiments or massive amounts of data. This research, presented at NeurIPS 2018, addresses this gap by proposing a two-stage algorithm that uses "interventional path queries" to learn the exact structure of a causal graph with remarkably low sample complexity—scaling only logarithmically with the number of variables.

Methodology

The authors introduce a strategy based on interventional path queries. A path query asks: "Is there a directed path from node $i$ to node $j$?" To answer this, they intervene on node $i$ and observe the effect on node $j$. The approach works in two main phases:

1. Learning the Transitive Reduction

The algorithm first identifies the "transitive reduction"—the minimal version of the graph that maintains all reachability. For instance, if $1 \to 2$ and $2 \to 3$ exist, a direct edge $1 \to 3$ is considered redundant for reachability. The authors prove this backbone can be identified in polynomial time using single-node interventions.

Comparison between a graph with a transitive edge (left) and its transitive reduction (right).

2. Learning Transitive Edges

To recover the full network, the algorithm must identify redundant "shortcut" edges (transitive edges). To distinguish a direct edge from an indirect path, the authors use multiple-vertex interventions to "block" intermediate paths and see if a direct causal link remains.

A causal graph (left) and an intervention on node 4 (right) used to isolate specific causal paths.

Crucially, the statistical analysis for both discrete and continuous (sub-Gaussian) variables shows that the number of samples needed per query scales with $O(\log n)$, where $n$ is the number of nodes.

Experimental Results

The approach was validated using three types of data:

  • Synthetic CBNs: Randomly generated DAGs used to empirically prove the logarithmic "phase transition" of accuracy. Experiments showed that once the number of samples reached the $O(\log n)$ threshold, the probability of correct recovery jumped from near-zero to near-certainty.
  • Benchmark Bayesian Networks: 21 standard networks (e.g., Alarm, Insurance). On benchmarks like Carpo and Win95pts, the algorithm achieved 1.0 precision and recall, perfectly recovering the causal structure. A key insight was that most real-world benchmark networks are very close to their transitive reductions; transitive edges often make up less than 1% of total edges.
  • Real-World Gene Perturbation: Applied to yeast, mouse, and human gene expression data. In the yeast dataset, the algorithm correctly identified the gene YFL044C as a major causal hub influencing 11 other genes.

Discussion and Conclusion

This work provides a significant theoretical win by proving that sample complexity for exact causal discovery is $O(\log n)$. This suggests that as we map larger systems, like the human genome, the data requirements grow very slowly.

However, some limitations remain. While sample complexity is low, the time complexity for learning transitive edges in discrete networks can be exponential relative to the maximum number of parents per node. Additionally, while the method is robust to imperfect interventions and hidden confounders to some extent, a more formal treatment of latent variables and more complex distribution comparisons are areas for future research.

Summary updated

Abstract

Causal discovery from empirical data is a fundamental problem in many\nscientific domains. Observational data allows for identifiability only up to\nMarkov equivalence class. In this paper we first propose a polynomial time\nalgorithm for learning the exact correctly-oriented structure of the transitive\nreduction of any causal Bayesian network with high probability, by using\ninterventional path queries. Each path query takes as input an origin node and\na target node, and answers whether there is a directed path from the origin to\nthe target. This is done by intervening on the origin node and observing\nsamples from the target node. We theoretically show the logarithmic sample\ncomplexity for the size of interventional data per path query, for continuous\nand discrete networks. We then show how to learn the transitive edges using\nalso logarithmic sample complexity (albeit in time exponential in the maximum\nnumber of parents for discrete networks), which allows us to learn the full\nnetwork. We further extend our work by reducing the number of interventional\npath queries for learning rooted trees. We also provide an analysis of\nimperfect interventions.\n
BibTeX
@inproceedings{bello2018computationally,
  author = {Kevin Bello and Jean Honorio},
  title = {{Computationally and statistically efficient learning of causal Bayes\textbackslash\{\}n nets using path queries}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=H1NpGw-_br},
}
Figure