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.
Authors use single vertex interventions and declare the variables whose distribution changes with the intervention to be the descendants. Based on this, they can recover the transitive reduction of a causal graph with n interventions. The advantage of this approach, although it increases the number of interventions from log^2(n) to n compared to [13], is that it requires much less number of samples, since intervention sets are all of size 1.   The fact that an intervention changes the distribution of the descendants even in the presence of latents has been known and is lately used in [13]. Accordingly, the overall approach is not surprising, when the goal is to minimize the number of interventional samples. This approach is presented using what the authors call "a path query". What the authors call a path query seems equivalent to a conditional independence test on the post-interventional distribution when we use a stochastic intervention. Algorithm 3, the algorithm for recovering the true causal edges, gradually increments the parent set of each node by including the newfound parent to the current parent set. This algorithm however requires exponential number of samples, and its advantage is not clear to me over the algorithms of [13].   Given this high level idea, authors analyze the number of samples required to reliably run these tests. I am happy to see this analysis and this is definitely an important direction for the causality literature. However the presented analysis have some issues. Most importantly, the authors use DKW inequality, which is useful for continous variables, in the proof of Theorem 1. However, since they are using empirical counts to approximate a discrete distribution, they could have used Chernoff bounds. In fact, had they used Chernoff bounds, I believe they would get a 1/sqrt(gamma) dependence, whereas with the current analysis, they have a 1/gamma^2 dependence. (details below)   Another important issue with the submission is the title: The title is very misleading. The authors only find the transitive reduction of a causal graph. Not learn the whole Bayesian network. I recommend mentioning causal graph and transitive reduction in the title. It is also surprising to see that the authors did not choose causality as primary or secondary topic for the submission.  Despite the not surprising algorithm and some issues with the analysis, I am leaning more towards acceptance. However, I would appreciate if the authors could respond to the questions I asked in the following and clarify certain points for me to make a better assessment.  Following are more details and my feedback/other questions for the authors:  What authors call a path query is simply checking if a descendants distribution changes or not. I understand that they are following up on [32], but calling this known test a "path query" makes the work seem disconnected from the existing causality literature. I would remove this language from the paper since it is simply checking if the underlying distribution of the other nodes changes with different interventions. Also, the test seems equivalent to a CI test, when we use a stochastic intervention on the support of the intervened node. Could you please comment on this and maybe add a discussion about this equivalence in the paper?  There are certain issues with the way background is explained. The authors state that Bayesian networks are also used to describe causal relations. hen they are called causal Bayesian networks. This is not correct. A Bayesian network is a graph according to which the joint distribution factorizes. Bayesian networks do not have causal interpretations. Please change the narrative accordingly in line 24 and also in line 100, where it is told that a Bayesian network can also be viewedd as a causal model or a causal Bayesian network. This narrative is misleading.  The definition of a v-structure in footnote 1 in page 1 should mention the fact that X, Z should not be adjacent.  The authors use "number of interventions" for the number of total experiments performed in order to realize a collection of interventions: If they perform a single intervention on a 5 state variable, they count this as 5 interventions. This arises slight confusion, especially when they are citing the performance of the related work. I would use "number of interventional samples" for this to avoid confusion. But this is not a major point.  In line 108, the probability expression should contain Xi as well, since authors use indicator Xi=xi on the right hand side.  The path query definition given in lines 120-122 is word by word taken from [32], which the authors cite elsewhere in the paper. Please add this citation here in the definition to signify where the definition is taken from.  In line 149, authors mention that their method is robust to latent confounders. This is correct since they only use interventional data and search for the desendants by looking at the invariances in the interventional distribution (This is in fact how I would describe this work and the algorithm rather than using the path query language. This would also make the paper more consistent with the existing causality literature). However, it is too important to simply mention in a single line. Please elaborate and explain why latent confounders do not affect any of the analysis in the paper (no need to respond here).  Proof of proposition 2 is not rigorous. Authors should use faithfulness. Please see the appendix of [13] for a similar proof. (I suspect interventional faithfulness to be necessary here). Please comment on this.  In Theorem 1, the authors simply estimate each interventional distribution from the empirical counts, and check if they are different enough. The analysis of this algorithm uses what is known as DKW inequality. This inequality is useful for continuous random variables. I don't understand why the authors have not used a Chernoff boumd. I believe with Chernoff bound, they should be able to get a 1/sqrt(gamma) bound, whereas with this inequality, they can only show 1/gamma^2 bound. The only change in the analysis would be that, since the difference in distributions is assumed to be gamma, you need a concentration of gamma/2 in each distribution. But this would only change the constant. Please check the analysis to verify this suggestion.  In Theorem 2, the authors assume that Xj are subGaussian. But how do we know P(Xj|do(Xi)) are also subGaussian? Please explain. Because the proof of theorem 2 uses this. The authors should state this as an assumption of Theorem 2. This seems necessary for this result.  Algorithm 3 operates by, for each node adding the parental nodes not already included in the transitive reduction. The algorithm seems correct. However, with the authors' definition of the number of interventions, this requires exponential in n number of interventions since they have to intervene on all the parents of every node. They acknowledge this elsewhere in the paper, but not including this fact in the theorem statement is a slighly misleading. It is not clear what the advantage of Algorithm 3 is, compared to the algorithms given in [13]. Please elaborate.   There are various grammatical errors and typos throughout. I recommend proofreading the submission. Following are what I could catch:  Line 5: any causal Bayesian networks -> any causal Bayesian network Line 8: by intervening the origin node -> by intervening on the origin node Line 23: are a powerful representation -> are powerful representations Line 33: the effect on Y by changing X -> the effect of changing X on Y Line 34: DAGs -> causal graphs Line 40: or assume that have one -> or assume that they have one Algorithm 2, Line 1: Intervene Xi -> Intervene on Xi