Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity
Learning the directed acyclic graph (DAG) structure of a Bayesian network from observational data is a notoriously difficult problem for which many non-identifiability and hardness results are known. In this paper we propose a provably polynomialtime algorithm for learning sparse Gaussian Bayesian networks with equal noise variance -a class of Bayesian networks for which the DAG structure can be uniquely identified from observational data -under high-dimensional settings. We show that O(k 4 log p) number of samples suffices for our method to recover the true DAG structure with high probability, where p is the number of variables and k is the maximum Markov blanket size. We obtain our theoretical guarantees under a condition called restricted strong adjacency faithfulness (RSAF), which is strictly weaker than strong faithfulness -a condition that other methods based on conditional independence testing need for their success. The sample complexity of our method matches the information-theoretic limits in terms of the dependence on p. We validate our theoretical findings through synthetic experiments.
ordinary least squares problems, where p is the number of nodes and k is the maximum Markov blanket size of a variable. We show that O(( k 4 /↵ 2 ) log( p / )) samples suffice for our algorithm to recover the true DAG structure and to approximate the parameters to at most ↵ additive error, with probability at least 1 , for some > 0. The sample complexity of O(k 4 log p) is close to the information-theoretic limit of ⌦(k log p) for learning sparse GBNs as obtained by [4]. The main assumption under which we obtain our theoretical guarantees is a condition that we refer to as the ↵-restricted strong adjacency faithfulness (RSAF). We show that RSAF is a strictly weaker condition than strong faithfulness, which methods based on independence testing require for their success. In this identifiable regime, given enough samples, our method can recover the exact DAG structure of any Gaussian distribution. However, existing exact algorithms like the PC algorithm [5] can fail to recover the correct skeleton for distributions that are not faithful, and fail to orient a number of edges that are not covered by the Meek orientation rules [6,7]. Of independent interest is our analysis of OLS regression under the random design setting for which we obtain`1 error bounds.
Related Work. In the this section, we first discuss some identifiability results for GBNs known in the literature and then survey relevant algorithms for learning GBNs and Gaussian SEMs.
[3] proved identifiability of distributions drawn from a restricted SEM with additive noise, where in the restricted SEM the functions are assumed to be non-linear and thrice continuously differentiable. It is also known that SEMs with linear functions and strictly non-Gaussian noise are identifiable [8]. Indentifiability of the DAG structure for the linear function and Gaussian noise case was proved by [9] when noise variables are assumed to have equal variance.
Algorithms for learning BNs typically fall into two distinct categories, namely: independence test based methods and score based methods. This dichotomy also extends to the Gaussian case. Score based methods assign a score to a candidate DAG structure based on how well it explains the observed data, and then attempt to find the highest scoring structure. Popular examples for the Gaussian distribution are the log-likelihood based BIC and AIC scores and the`0-penalized log-likelihood score by [10]. However, given that the number of DAGs and sparse DAGs is exponential in the number of variables [4,11], exhaustively searching for the highest scoring DAG in the combinatorial space of all DAGs, which is a feature of existing exact search based algorithms, is prohibitive for all but a few number of variables. [12] propose a score-based method, based on concave penalization of a reparameterized negative log-likelihood function, which can learn a GBN over 1000 variables in an hour. However, the resulting optimization problem is neither convex -therefore is not guaranteed to find a globally optimal solution -nor solvable in polynomial time. In light of these shortcomings, approximation algorithms have been proposed for learning BNs which can be used to learn GBNs in conjunction with a suitable score function; notable methods are Greedy Equivalence Search (GES) proposed by [13] and an LP-relaxation based method proposed by [14].
Among independence test based methods for learning GBNs, [15] extended the PC algorithm, originally proposed by [5], to learn the Markov equivalence class of GBNs from observational data. The computational complexity of the PC algorithm is bounded by O(p k ) with high probability, where k is the maximum neighborhood size of a node, and is only efficient for learning very sparse DAGs. For the non-linear Gaussian SEM case, [3] developed a two-stage algorithm called RESIT, which works by first learning the causal ordering of the variables and then performing regressions to learn the DAG structure. As we formally show in Appendix C.1, RESIT does not work for the linear Gaussian case. Moreover, Peters et al. proved the correctness of RESIT only in the population setting. Lastly, [16] developed an algorithm, which is similar in spirit to our algorithm, for efficiently learning Poisson Bayesian networks. They exploit a property specific to the Poisson distribution called overdispersion to learn the causal ordering of variables.
Finally, the max-min hill climbing (MMHC) algorithm by [17] is a state-of-the-art hybrid algorithm for BNs that combines ideas from constraint-based and score-based learning. While MMHC works well in practice, it is inherently a heuristic algorithm and is not guaranteed to recover the true DAG structure even when it is uniquely identifiable.
Summary:
    The paper considers a Gaussian Bayesian Network which is directed acyclic and is governed by structural equations which are linear with additive gaussian noise of identical variance. This class of bayesian networks have been shown to be identifiable in prior work. There has been no polynomial time algorithm known even for this case.
The authors propose a polynomial time algorithm which involves inverse covariance estimation, ordinary least squares and a simple identification rule for terminal vertices (leaf vertices in the Directed Acyclic Graph) for this problem. Under the assumption of restricted strong adjacency faithfulness (RSAF) (which essentially says that for all induced sub graphs, variables in the Markov Blanket exhibit high enough influence on a variable) the algorithm identifies the correct graph with O(k^4 log p) samples where k is the maximum size of the Markov Blanket.
Strengths:
   a) As far as I am aware this is the first fully polynomial time algorithm for the problem under this setting. 
   b) The paper hinges on few important observations: 
     1) Learning undirected gaussian graphical models is very very efficient due to large number of papers on inverse covariance estimation. 
     2) But usually inverse covariance estimation can only recover the Markov Blanket of every variable (considering the moralized graph) and cannot in general reveal directions.
     3) However, if a topological ordering of the vertices respecting the partial order in the DAG is known, then Ordinary least squares can be repeatedly used to figure out parents of a variable i by considering an induced graph with vertices in the ordering upto i and the inverse covariance structure at every subsequent stage.
     4) The authors exploit the following key fact construct a topological ordering by discovering terminal vertices (lead vertices) recursively: When a terminal vertex i is regressed on the rest of the nodes, then ratio of regression coefficient of vertex j in the graph to (i,j)th entry in the inverse covariance matrix equal to the noise variance in the problem. In fact, for non terminal vertices, the ratio is strictly larger under RSAF condition. This involves only inverse covariance estimation which is efficient.
  c)) Because the authors define effective influence characterizing the markov blanket in terms of the weights in the structural equations, authors can handle cases even when the model is not causally faithful (this is a standard assumption for most causal inference algorithms).
  d) In all its a really good paper. The authors have also compared it to some state of the art algorithms like PC, MMHC and GES and shown that for synthetic gaussian models, they do better in terms of recovery.
 
 However, I only have some semi-mild to some mild comments. Comment d is the most serious. It would be great if authors can address it.
 Weaknesses:
      a) In page 3 at the end, Markov Blanket of vertex i is defined using effective influence and the information theoretic definition that a set of nodes such that conditioned on them, the rest of the variables are independent to i. Under casual faithfulness, markov blanket is simply - parents, children and co-parents. I think defining it in terms of effective influence lets them deal with pathological cases not covered by causal faithfulness. This lets them work on examples in page 5. I think this must be made clear. Because a lot of readers of BN literature may be used to a graph theoretic notion of Markov Blanket. 
     b) In the example in page 5 below Proposition 1, it appears the for i,j which are neighbors if one chooses a pathological set of weights, only then effective influence becomes zero which can still be handled by the algorithm of the authors. I find it to be a corner case although I agree technically its a super set. The reason for this comment is most other algorithms like PC, MMHC are completely non parametric as far as at least skeleton + v-structure discovery is concerned. But this algorithm has very tight parametric assumptions (so it may not be that fair a comparison).
    c) Page 2, before Section 2 "MMHC works well in practice but inherently a heuristic algorithm" - I partially agree with this. MMHC has two parts - one is skeleton recovery (which is provably correct under infinite samples) and the other part used score based optimization heuristic to orient. So it may not be totally correct to say it is heuristic. Another minor point - Like 74 , complexity of PC is said to be p^k. k in the paper is Markov Blanket size. However the PC's complexity exponent is the max degree in the graph. Markov blanket is much larger.
   
   d) Slightly serious concern:
       Page 7 , Algorithm 1, Line 24: Now the algorithm after identifying the order is considering induced subgraphs of first i vertices in the ordering and using regression of i on the remaining is finding the parents of i. First, to find the markov blanket of i i the induced sub graph , \hat{\Omega}_{z_i,j} is used - It should be z_i,z_j in the subscript (I think). But the major concern is which inverse covariance is it ? Is it the induced subgraph's inverse covariance upto vertex i in the ordering ? or is it the inverse covariance of the entire graph estimate at 6? Please clarify. This seems important because this step of identifying node i's parents from just from the ordering and regression is something crucial. In fact, the explanation I understood is:  the global invariance covariance matrix's markov blanket of i is intersected with the the induced sub graph of vertices till i, now the node i is regressed on its non zero entries. And it will turn out that the parent set of i is correctly identified. This is because in the induced sub graph, markov blanket of i will not include the co-parents. This has been explained in the last but one paragraph in page 14 in Appendix A for proof of theorem 1. But I think this reasoning should be included in the main paper and Line 24 in Algorithm 2 must be clarified even better.
e) In Appendix B.5 authors talk about some ref 31 which can split the graph into connected components. Does it mean that the graph in that table has connected components of size at most 500. So has the algorithm applied after the connected components found out ?? If this is the case 500 is not a large number for MMHC algorithm. In fact in the 2006 paper they claim it can actually process 1000 node graphs. Why did the authors not compares to that in that case ?
f)Line 100, (i,j) seems to be directed edge from j to i. From my experience, this seems like an odd choice. It is usually i->j. But this is just my personal quip.
g) Page 11 . Appendix, Proof of Lemma 1, First line. "forward direction follows from (5)". Should it not be Lemma 5 ??