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

Kevin Bello, Jean Honorio

Introduction: The Causal Discovery Bottleneck

Uncovering "who causes what" is the holy grail of science, from mapping gene regulatory networks to understanding complex economic models. However, relying solely on observational data (passive correlations) hits a fundamental wall known as the Markov equivalence class. This limitation means multiple different causal structures can explain the exact same data, leaving researchers unable to distinguish whether variable $X$ causes $Y$, or $Y$ causes $X$.

To break these ties, scientists rely on interventions—experiments where a variable is manually forced to a specific value to observe downstream effects. Unfortunately, traditional interventional methods are prohibitively expensive. Previous state-of-the-art approaches often required an exponential number of experiments or massive sample sizes to guarantee accuracy.

Researchers from Purdue University have developed a novel framework that maps out causal relationships using a fraction of the data previously required. By framing causal discovery as a series of "path queries," they achieved a polynomial-time algorithm with logarithmic sample complexity, effectively breaking the exponential bottleneck that has long plagued the field.

Methodology: Two-Stage Causal Discovery

The authors introduce a framework based on interventional path queries. A path query asks a straightforward question: "Is there a directed path from node $A$ to node $B$?" By reducing the problem to reachability rather than full conditional independence testing, the authors bypass the need for the massive intervention sets required by previous methods.

The algorithm operates in two main stages:

1. Learning the Transitive Reduction

The algorithm first identifies the "skeleton" of the network—the minimum set of edges needed to represent all reachability, known as the transitive reduction. Most real-world networks are sparse in a way that makes their transitive reduction contain the vast majority of the causal information.

A causal graph (left) and its transitive reduction (right)

The algorithm finds this skeleton by performing single-node interventions and observing the downstream effects. The authors prove that for both discrete and continuous (sub-Gaussian) variables, you only need $O(\log n)$ samples per query to get the right answer with high probability.

2. Recovering Transitive Edges

Once the skeleton is established, the algorithm looks for "shortcuts" (direct edges that bypass existing paths, like the edge removed in the transitive reduction). This requires more complex multiple-vertex interventions to "block" indirect influence. However, the authors demonstrate that the sample complexity remains polynomial during this phase.

Key Results and Validation

The authors validated their algorithms using a mix of synthetic Directed Acyclic Graphs (DAGs), benchmark Bayesian networks, and real-world biological data, including a gene perturbation atlas where researchers manually knocked out genes to observe effects.

Key findings include:

  • Massive Efficiency Gains: Compared to previous methods that required $O(2^{n/2})$ experiments in the worst case, this approach uses only $n$ single-node interventions to find the transitive reduction.
  • Logarithmic Sample Complexity: The paper proves that $O(\log n)$ samples are sufficient for high-probability recovery in discrete networks, and $O(\sigma^2 \log n)$ for continuous ones. This logarithmic scaling suggests that causal discovery in massive systems with thousands of variables is practically feasible.
  • Sharp Phase Transitions: Experimental results demonstrate a sharp phase transition: as the number of samples increases, the probability of recovering the perfect graph jumps from near-zero to near-one very quickly, confirming the theoretical efficiency.
  • Optimizations for Rooted Trees: For hierarchical, tree-like structures, the total number of path queries is slashed from $O(n^2)$ to $O(n \log n)$.

Limitations and Future Work

While the paper makes significant strides in both computational and statistical efficiency, some challenges remain. First, while the sample complexity for finding shortcut transitive edges is polynomial, the time complexity for discrete networks can still be exponential relative to the maximum number of parents a node has.

Second, for continuous networks, the current method relies on comparing expected values (means). The authors suggest that integrating more sophisticated tools, like kernel density estimators, could make the method more robust for complex, non-linear distributions. Finally, while the method is robust to some hidden confounders due to its use of interventions, a full treatment of latent variable models—where critical variables are never measured—remains an important avenue for future research.

Summary updated

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.
BibTeX
@inproceedings{bello2018computationally,
  author = {Kevin Bello and Jean Honorio},
  title = {{Computationally and statistically efficient learning of causal Bayes nets using path queries}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=H1NpGw-_br},
}
Figure