Computationally and statistically efficient learning of causal Bayes
  nets using path queries
  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.
