Title: Learning causal Bayes networks using interventional path queries in polynomial time and sample complexity,
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 networks 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 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 further extend our work to learn the transitive edges using
logarithmic sample complexity (albeit in time exponential in the maximum number
of parents for discrete networks). This allows us to learn the full network. We
also provide an analysis of imperfect interventions.