Learning Bayes networks using interventional path queries in polynomial time and sample complexity

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

A central goal in data science is moving beyond correlation to establish true causation. While standard machine learning excels at predicting outcomes based on observations, causal discovery aims to determine if one variable actually causes another. The fundamental challenge is identifiability: observational data typically only narrows down causal structures to a "Markov equivalence class," unable to distinguish between $X \to Y$ and $Y \to X$. To overcome this, Bello and Honorio propose a framework using interventional path queries to learn the exact structure of Causal Bayesian Networks (CBNs) efficiently.

Methodology: Path Queries and Transitive Reduction

The authors frame causal discovery as a graph reconstruction task using path queries. A path query $Q(i, j)$ asks if a directed path exists from node $i$ to node $j$. This is answered by performing a single-vertex intervention on $i$ (forcing it to a specific value) and observing if the distribution of $j$ changes.

Learning the Transitive Reduction

The first stage of the proposed approach (Algorithm 1) focuses on learning the "transitive reduction" of the graph. This is the minimal set of edges required to represent all reachability within the network. For example, in a network where $1 \to 2$, $2 \to 3$, and $1 \to 3$, the edge $1 \to 3$ is a "shortcut" or transitive edge.

A directed acyclic graph (DAG) containing a transitive edge from node 1 to node 3.

Algorithm 1 recovers this skeleton in polynomial time using $O(n^2)$ path queries. A key theoretical contribution is proving that the number of samples needed per query scales logarithmically ($O(\log n)$) with the number of variables, ensuring statistical efficiency for both discrete and continuous systems.

Identifying Transitive Edges

To recover the full network, the authors use multiple-vertex interventions to identify transitive edges. By intervening on intermediate nodes to "block" indirect paths, they can isolate and confirm direct causal links that were omitted in the transitive reduction.

An interventional path query where node 4 is intervened upon (shaded) to block indirect paths and isolate causal effects.

Experimental Results

The approach was validated using synthetic networks (up to 60 nodes), 21 benchmark Bayesian networks from the bnlearn repository (e.g., Alarm, Insurance), and real-world gene perturbation datasets.

Key findings include:

  • High Accuracy: The algorithms achieved a perfect 1.0 F1 score on several benchmark networks, recovering the true causal graph with 100% precision and recall.
  • Efficiency: The transitive reduction algorithm runs in $O(n^{2.37})$ time, matching the complexity of fast matrix multiplication. In practice, the transitive reduction often accounts for over 99.5% of edges in real-world models, making this first step highly effective.
  • Sample Complexity: Experiments confirmed the predicted "phase transition" where perfect recovery occurs at very low sample sizes, consistent with the $O(\log n)$ theoretical bound.

Conclusion and Future Work

This work demonstrates that exact causal discovery is computationally and statistically feasible using a manageable number of interventions. While the sample complexity is polynomial, the time complexity for identifying transitive edges in dense discrete networks remains a challenge. Future research will focus on robustly handling non-linear relationships and "imperfect" interventions where variables can only be influenced rather than set exactly.

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{bello2018learning,
  author = {Kevin Bello and Jean Honorio},
  title = {{Learning Bayes networks using interventional path queries in polynomial time and sample complexity}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=H1NpGw-_br},
}
Figure