Reliable Causal Discovery with Improved Exact Search and Weaker Assumptions
Authors: Ignavier Ng
Yujia Zheng
Jiji Zhang
Kun Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Causal discovery
exact score-based method
weaker assumptions
scalability

Abstract: Many of the causal discovery methods rely on the faithfulness assumption to guarantee asymptotic correctness. However, the assumption can be approximately violated in many ways, leading to sub-optimal solutions. Although there is a line of research in Bayesian network structure learning that focuses on weakening the assumption, such as exact search methods with well-defined score functions, they do not scale well to large graphs. In this work, we introduce several strategies to improve the scalability of exact score-based methods in the linear Gaussian setting. In particular, we develop a super-structure estimation method based on the support of inverse covariance matrix which requires assumptions that are strictly weaker than faithfulness, and apply it to restrict the search space of exact search. We also propose a local search strategy that performs exact search on the local clusters formed by each variable and its neighbors within two hops in the super-structure. Numerical experiments validate the efficacy of the proposed procedure, and demonstrate that it scales up to hundreds of nodes with a high accuracy.

Reliable Causal Discovery with Improved Exact Search and Weaker Assumptions
Ignavier Ng', Yujia Zheng', Jiji Zhang", Kun Zhang'
1 Carnegie Mellon University
2 Hong Kong Baptist University
fignavierng, yujiazh) (etalazzhmmmmmeeeemmmmmmm edu, zhangj jiihhbuu. hdu kunzidcma edu
Abstract
Many of the causal discovery methods rely the faithfulness assumption guarantee asymptotic correctness. However, the assumption can be approximately violated many ways, leading sub-optimal solutions. Although there is line of research in Bayesian network structure learning that focuses on weakening the assumption, such as exact search methods with well-defined score functions, they do not scale well to large graphs. In this work, we introduce several strategies improve the scalability of exact score-based methods in the linear Gaussian setting. In particular, we develop super-structure estimation method based the support of inverse covariance matrix which requires assumptions that are strictly weaker than faithfulness, and apply it to restrict the search space of exact search. We also propose local search strategy that performs exact search on the local clusters formed by each variable and its neighbors within two hops in the super- structure. Numerical experiments validate the efficacy of the proposed procedure, and demonstrate that scales up to hundreds of nodes with high accuracy.
1 Introduction
Although it is often more reliable to discover causal relationships by making use of interventions or randomized experiments, they are practically challenging. expensive, or even prohibited owing to ethical considerations. Thus, causal discovery from observational data has received considerable attention in recent decades, and has been widely applied in different fields such genetics [29].
One major class of causal discovery methods is the constraint- -baed methods, such as PC [40] and FCI [43, 4], that leverage conditional independence tests to estimate the skeleton and then perform edge orientation. These methods are guaranteed to asymptotically return the true Markov equivalence class (MEC) under the Markov and faithfulness assumptions. Several modifications [30, 41] to these constraint-bart based methods have been developed to allow certain types of unfaithfulness, which, however, generally give rise weaker claims and are not guaranteed to estimate the true MEC.
Another popular approach is the GES [3] algorithm that searches the space of MECs greedily by maximizing well-defined score, such the Bayesian information criterion (BIC) [36] score. It starts with an empty structure and consists of two phases: (1) adding edges until a local maximum is found, and (2) removing edges until local maximum is reached. In spite of the greedy strategy, GES converges in the large sample limit to the true MEC under the Markov and faithfulness assumptions, similar the aforementioned constraint-based methods.
Recently, NOTEARS [52] casts the Bayesian network structure learning task into a continuous constrained optimization problem with the least squares objective, using algebraic characterization of directed acyclic graph (DAG). Subsequent work GOLEM [23] adopts a continuous unconstrained optimization formulation with fikelihood-base objective. For NOTEARS. it remains unclear
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

of the required assumptions for asymptotic correctness, whereas GOLEM adopts the generalized faithfulness assumption [9] learn linear Gaussian DAGs, which could be converted their MECs for causal interpretation [42]. These methods enable the application of numerical solvers and GPU acceleration, which thus are scalable to large graphs. However, they are only guaranteed to find local optimum of the optimization problem, and therefore the quality of the solution in practice may not be guaranteed, even in the asymptotic case.
Another line of research focuses on weakening the faithfulness assumption required for asymptotic correctness of the search results, since. given finite samples, approximate violations of faithfulness occur surprisingly often, especially when there is large number of variables [46]. For instance, exact search methods find the optimal Bayesian network based on a predefined score function, such as dynamic programming (DP) [18, 24, 39, 38], A [49, 48], and integer programming [1, 5]. The DAGs estimated by these methods can be converted to their MECs for causal interpretation [42]. Note that the approaches based on sparsest permutation (SP) [32] and Boolean satisfiability solver (SAT) [15, 16] can be viewed as instances exact methods. Lu et al. [22] further demonstrated that these exact methods may produce correct results in cases where methods relying on faithfulness fail.
Due to the large search space of possible DAGs [2. 13), exact search methods are feasible only for small structures, Therefore, super-structure has been adopted to constrain the search space [27, 45], which is defined to be an undirected graph that restricts the search candidate DAGs whose skeleton is its subgraph. However, most of these methods rely on discovering the skeleton of the true DAG for use as super-structure, utilizing estimation methods like MMPC [45], which require the faithfulness assumption to be asymptotically correct. Under approximate violations of faithfulness, these skeleton estimation methods may miss some edges owing to unfaithful conditional independencies in the data distribution; thus, further exact search procedures are guaranteed to miss those edges.
Contributions. In this work, we introduce several strategies improve the scalability of exact search in the linear Gaussian setting, giving rise to a more reliable causal discovery procedure. Our main contributions can be summarized follows:
We develop super-structure estimation method based on the support of inverse covariance matrix of the data distribution, and show that it is asymptotically correct under assumptions strictly weaker than faithfulness (or, more specifically, than faihhlesaaihhfullees)). We combine this with exact search method like DP or A* reduce search space.
To further scale up exact search, we develop a local search strategy, called Local A*, on the local clusters formed by each variable and its neighbors within two hops in the super-structure.
We demonstrate the efficacy of our super-structure estimation method and local search strategy by conducting extensive experiments, and show that it scales up to hundreds of nodes with a high accuracy.
Paper organization. We review the common assumptions for causal discovery and the linear struc- tural equation model (SEM) in Section 2. In Section 3, we establish weaker variants of faithfulness and show how they could be used to learn a sound super-structure. We further formulate an improved exact search strategy in Section 4. The empirical studies in Section 5 validate our theoretical results and the efficacy of the proposed procedure. We then conclude our work in Section 6.
2 Background
We first review the concepts of causal Bayesian networks and some commonly used assumptions that related to our further analysis. We then give brief overview of the linear SEM.
2.1 Causal Bayesian Network and Common Assumptions
Let e - (V, E) be a DAG with vertex set V = {X1...., Xa) in which each node X, corresponds to random variable. Denote X (X1,-. X.) the random vector concatenating all variables and its associated probability distribution P.. Let X Xnn()) be the set of parental nodes of X, in g such that there is directed edge from X, E Xpa(s) to Xz, or X, + X E E. We assume causal sufficiency, i.., no hidden variables, throughout the paper.
In Bayesian network, the distribution IP is assumed to be Markov w.r.t. to DAG G, as defined below.

---

Assumption (Markov), Given DAG G and distribution P over the variable set V. every variable X in V is probabilistically independent of its non dencenecssssnss given its parents in G.
A causal Bayesian network can be viewed as Bayesian network where the directed edges provided a causal meaning, which thereby allows it to answer interventional queries [20]. In general, there many DAGs that induce the same conditional independence (CI) relations with the distribution P. and are said to be Markov equivalent. The Markov equivalence class (MEC) consists of all DAGs that entail the same conditional independence (CI) relations as & does, and is uniquely determined by its skeleton and v-structures [25]. V-structure is defined to be collider X + Y + Z where X and Z are not adjacent in G, therefore referred as an unshielded collider. If X and Z are adjacent, then it is called a shielded collider.
The following faithfulness assumption is commonly used to relate the CI relations in the distribution to the DAG, and can be thought of as the converse to the Markov assumption.
Assumption (Faithfulness [44]). Given a DAG G and distribution P over the variable set V, P implies no CI relations not already entailed by the Markov assumption.
Under the Markov and faithfulness assumptions, constraint- methods such as PC have been shown to asymptotically output the correct MEC. However, in the finite sample regime, the faithfulness assumption sensitive to statistical testing errors when inferring the CI relations, and its approximate violations occur surprisingly often, especially when there is a large number of variables [46]. Thus, different relaxations of faithfulness have been proposed, such as orientation ivcentaton-aaithullneee faithfulness, adjacency- faithfulness [30], and faitfules [51], which we review in Appendix A.
Clearly, the triangle-faithfulees faithfulness assumption is a consequence of adjacency-faitte faithfulness. Based on these weaker assumptions, different modifications to constraint- methods have been proposed, such as Conservative PC [30] and Very Conservative SGS [41]. As their names suggest, these methods make weaker claims about the estimated causal structure and therefore are not guaranteed to estimate the true MEC. On the other hand, Raskutti and Uhler [32] proposed the following assumption and show that it is strictly weaker than faithfulness.
Assumption (Sparsest Markov representation (SMR) [32]). Given a DAG g and distribution P over the variable set V, the MEC of G is the unique sparsest MEC that satisfies the Markov assumption with P..
Forster et al. [7] referred the above assumption as the (unique) frugality assumption, and argued that it has multiple desirable properties compared to faithfulness. Under the SMR assumption, the SP method [32] has been shown to produce asymptotically correct results. Raskutti and Uhler [32] also conjectured that SP reaches the information-theorett limit in the sense that the SMR assumption may be the weakest assumption guaranteeing the asymptotic correctness of any method for learning the true MEC. It is worth noting that SP can be viewed as an instance of exact score-based method. The study by Lu et al. [22] demonstrated that causal discovery methods that rely on the faithfulness assumption (c.g. ... PC, GES) may output sub-optimal solutions in various cases, whereas exact methods (e.g., SP, A+, SAT) are able to produce the correct results. Therefore, in this work, we aim at improving the scalability of exact score-based methods for reliable causal discovery, by relying on the SMR assumption and relaxing the faithfulness assumption as much as is viable.
2.2 Linear Structural Equation Model
Given linear SEM, each random variable follows the relationship X; = =B, + N₁, where B, is coefficient vector and N, is an exogenous noise variable associated with variable X,. In this work we focus on the linear Gaussian model where the variables N, 's follow the Gaussian distribution. The linear SEM can be written in matrix form as X BT X + N. where B [B, B2. Ba] corresponds to a weighted adjacency matrix, and N = (N1 (N...... .Na) is noise vector characterized by the covariance matrix 52 = cov[N] = diag ..., o2)). We assume that oī > for i = I,...,, d so that the distribution IP has positive measure everywhere. As a standard assumption, we also assume structural minimality [29] which implies that the nonzero coefficients B define the structure of G. i..., X3 X; E if and only if the coefficient in B, corresponding to variable X₁ is nonzero. Since one can always center the data, we assume E[X] = E = O without loss of generality. The inverse covariance matrix θ = 1
1 of X is given by θ (I - B) B)T. Note that O, = if and only if X, T X X,, in the linear Gaussian case.
3

---

3 Weaker Assumptions for Super-Structure Estimation
We establish several weaker variants of faithfulness assumption, and show how they are both necessary and sufficient for learning a super-structure of the true DAG via inverse covariance estimation.
3.1 Weaker Assumptions than Faithfulness
We describe several relaxed assumptions of faithfulness required for our super-structure estimation procedure. We first start with the specific types of faithfulness related to different kinds of colliders. Assumption 4
(SCF)). Given a DAG G and distribution P over the variable set V, let X + + Z be any shielded collider G. Then and are dependent conditional any subset of \ {X, }} thut contains Y.
(UCF)). Given a DAG 9 and distribution P over the variable V, let X + Y Z be any unshielded collider in G. Then X and Z are dependent conditional on any subset of \ (X, 3} that contains Y.
Assumption
any subset of The above assumptions are restrictions of the triangle-faithfulness [51] and orientation-faithfuleee [30] assumptions, respectively, to collider structures. Note that they differ only in the type of collider being considered. However, these assumptions require dependence conditioning
V V (x, }}. which may be restrictive in practice. In this work, we further relax them to require only dependence conditioning on V (X, 2}. and will show in Section 3.2 how they are both necessary and sufficient conditions for estimating a sound super-structure of the true DAG. These relaxed assumptions are stated below.
Assumption 6 (Single over the variable set V, let X + Y t Z be any shielded collider in G. Then X V L \ {X, 2}. Assumption 7 (Single P over the variable set V, let X + Y + Z be any unshielded collider in G. Then x (X Z}.
(SSCF)). Given DAG G and distribution P
(SUCF)). Given DAG G and distribution
X
0.5
Figure 1 illustrate the examples in which the SCF and UCF assumptions are violated, respectively, but the SSCF and SUCF assumptions hold. In these examples, we have X 1l Z and X JK Z (Y, W), where the former unfaithful CI relation X Y is constructed via path cancellations.
0.5
W
Z
1.0
Given distribution P. let (P)), Gady (P), (Ir) (er)(P), Goof (P), (P)) (P)) and G be the set DAGS satisfying the faithful- ness, adjacency-faithuulnss,
(a) Violation of SCE.
prientation-faihhulless triangle-faithfulnes. SCF, UCF, SSCF, and SUCF assumptions, respectively. Also, denote by C the proper subset symbol. Combining with the results by Ramsey et al. [30], Zhang and Spirtes [51], we have the following nesting properties, showing that SSCF and SUCF are intuitively much weaker than the faithfulness assumption.
X
0.5
0.5
0.5
W
1.0
Remark 1. 9fas (P) C Godz (P) C (Pr C Geef (P) C (P).
(b) Violation of UCF
Remark 2. Gjas (P) C Gors (P) Guef (P) Gouc (P).
Figure 1: Examples.
3.2 Inverse Covariance Estimation for Learning Super-Structure
Based on the assumptions described in Section 3.1, we develop a super-structure estimation method via inverse covariance estimation. We first study the specific assumptions required for the support of inverse covariance, denoted as supp( (). to be the same as the moralized graph of the underlying DAG. This is similar to the analysis by Loh and Bühlmann [21]. but we focus on formulating precisely the required assumptions from a causal discovery perspective, to shed light on how weak they are as compared to faithfulness. This enables us to further weaken the required assumptions in order to recover a super- strec-str the true DAG based on the support of inverse covariance.
As described, we first have the following theorem that relates the moral graph and the support of inverse covariance to the SUCF and SSCF assumptions, with proof given in Appendix C.I.
Theorem 1. Given DAG G and distribution IP that follow a linear Gaussian model with inverse covariance matrix O under Markov assumption, the SSCF and SUCF ussumptions are satisfied if and only if the structure defined by supp @ is the same the moralized graph of the true DAG G.

---

Although the above theorem guarantees recovering the moral- ized graph via @u in practice the SUCF assumption may be approximately violated. To illustrate, we simulate the lin- ear Gaussian model with edge weights sampled uniformly from [-0.8, 0.22 J 0.8] and exogenous noise variances sampled uniformly from [1, 2]. We then compute the minimum values min;, [ رو| X, and X, correspond to a pair of neighbors in 9) and x
0.32
Min. of
0.35
2.05
Number of modes
: X; and X; correspond to a pair of non- adjacent spouses in g} over 100 simulations, by considering different expected degrees and number of variables d E {10, 20, 50, 100, 200, 500, 1000). Note that X, and Xj being pair of non-adjacent spouses in DAG 9 implies that they share a common child and have an unshielded collider; therefore, SUCF requires that X; v X, V (X, for expected degree of 2 is shown in Figure 2, while those for degrees of 5 and 8 can be be found in Appendix B. Although the values in both cases decrease with larger graphs, the minimum values corresponding to the non-adjacent spouses are significantly smaller than those of neighbors, where the difference grows in the number of nodes. For instance, on 1000-node graphs with degree of 2. the average minimum value of the former is 0.025, while that of the latter is close to 0.1. With finite samples, it very challenging to discover those undirected edges in the former case, since the weights are very close to zero, leading to approximate violations of SUCF especially when there a large number of variables. Indeed, the simulations above are based on a certain range of edge weights and noise variances, whose true values are not known in practice. Therefore, it is possible that the data distribution considered falls into similar setting, leading to violation of SUCF, is thus desirable to further weaken the required assumptions to develop a more reliable procedure.
Nrighbor
Now Nan-ajjasani
Figure 2: Expected degree of 2.
i.e., , * 0 in the linear Gaussian case. The visualizations
If we drop the SUCF assumption, the structure defined by Supp(O) may miss some edges as compared to the moralized graph of the true DAG, Fortunately, these edges correspond to the non- adjacent spouses in the DAG. That is, Supp(@) is still guaranteed contain all undirected edges corresponding to neighbors in the DAG, as long as SSCF (in addition to the Markov assumption) holds, indicating that it is a sound super-structee Figure 2, approximate violations of SSCF are much less likely to happen than those of SUCF.
of the true DAG. Based on the simulations considered in
Theorem 2. Given a DAG G and distribution IP that follow a linear Gaussian model with inverse covariance matrix θ under Markov assumption, the SSCF assumption is satisfied if and only if the structure defined by supp(E) a super-structure of the true DAG G.
The proof is provided in Appendix C. With an asymptotically correct approach to estimate supp (). the theorem implies that one can estimate a sound super-structure of the true DAG under the SSCF assumption that is strictly weaker than triangle- faithlllnsss (cf. Remark 1), an assumption which is intuitively much weaker than faithfulness. This may be considered as a significant improvement over the existing methods that estimate the skeleton of the true DAG for use as a super-structure, utilizing methods like MMPC [45], which require faithfulness to be asymptotically correct.
The question remains as how to estimate supp(e) ()) In the high-dimensional setting, the ei-penalized maximum likelihood estimator can be used to recover the support, with consistency result provided by Ravikumar et al. [33, 34). In this work, we adopt the widely used graphical Lasso (GLasso) [8] method based on the block coordinate descent algorithm for estimating supp (). Other efficient estimation method, e.g.. QUIC [14), can also be adopted, which treated as a future work.
We provide empirical studies in Appendix 1, in which faithfulness is exactly violated but not SSCF, to demonstrate that GLasso finds the true super-structure in these cases, whereas MMPC fails. This is consistent with the experiments in Section 5.1 which show that GLasso is more reliable in practice, since approximate violations of SSCF are less likely to happen as compared to those of faithfulness.
4 Improved Exact Search
We introduce several strategies to improve the scalability of exact score-based search. In Section 4.1, we first establish the connection between the SMR assumption and exact search with BIC. We then leverage the super-structure estimation method described in Section 3.2 to restrict the search space of exact methods in Section 4.2, and develop a local search strategy in Section 4.3.
Note that this is consistent with the analysis of the strong faithfulness assumption by Uhler et al. [46].
5

---

4.1 Exact Search and the SMR Assumption
As described Section 2.1, classical methods such as PC and GES may produce sub- sub-optimal solutions when faithfulness fails. In the following, we show the connection between the SMR assumption, which is strictly weaker than faithfulness, and the asymptotic correctness of exact search with BIC. To the best of our knowledge, this is the first time that this result has been formally established.
Theorem 3. Exact score- based search with BIC asymptotically outputs a DAG that belongs to the MEC of the true DAG 9 if and only if the DAG G and distribution P satisfy the SMR assumption.
The proof can be found in Appendix C.2, which is straightforward from the consistency of BIC [12, 3]. Under the SMR assumption, the DAG estimated by exact search with BIC, is not necessarily identical to, but belongs to the same MEC as, the true DAG g. Therefore, one has to convert the estimated DAG to its MEC for causal interpretation [42].
4.2 A * with Super-Structure
Although exact search methods rely on the SMR assumption that is strictly weaker than faithfulness, is challenging to scale them up to large graphs the task is NP-hard [2]. To remedy this issue, similar to [27]. we propose to explicitly constrain the search space of exact score-based search algorithms using super-structure. This is achieved by limiting the size of parent graphs in the search procedure.
To give brief overview, for exact score- score-based methods such as DP [39, 38] and A* [49, 48], parent graph plays an important role in constructing the search space, which is a data structure that stores the costs for the ares of the order graph. These methods typically construct a parent graph for each variable, which is used to build the order graph. The search is performed on the order graph [39, 48), by solving a shortest path problem from the root node, which corresponds to the empty set, to the leaf node, which corresponds to the complete set of variables. Each variable has its own parent graph, and all optimal parent sets are selected from the candidate parent sets, by selecting the ones with the best score in the corresponding parent graph. Here we omit the details of the parent graph and order graph, and refer the interested reader to the references above for their complete definitions and procedure.
Using the super-structure structure estimation method in Section 3.2, for each variable, we are able to obtain the set of nodes that must not be its candidate parents, and directly remove the entries involving these nodes in the corresponding parent graph. These constrained parent graphs help reduce search space in the order graph, from which the shortest path problem is formulated, and thereby improve the efficiency of the exact search procedure. As a byproduct, this strategy also reduces the memory cost, since one does not have to enumerate all candidate parent sets when constructing the parent graphs.
Note that DP and A differ mainly in the search phase of the order graph. That is, DP has to consider all combinations of nodes (i.e., 2d combinations), and therefore exponentially expensive in computation and quickly becomes infeasible when the graph size increases, while A uses a heuristic function to only expand the most promising node [48], and has been shown empirically to achieve better efficiency. Therefore, in this work we adopt the A algorithm with the incorporated super-structure to further constrain the search space, which we call A *SSS, although similar strategy also works for DP. Under the Markov and SSCF assumptions, our estimated super- super-structure via inverse covariance estimation guaranteed to asymptotically contain the skeleton of the ground-truth DAG (cf. Theorem 2); thus, the proposed constrained search will not suffer from the trade-off between scalability and reliability given a sufficient number of samples.
Besides using super-structure, we apply several existing strategies to improve the efficiency and memory cost of A* In particular, we use the sparse representations [48] of the parent graphs to further remove unnecessary entries, which have been shown to improve the efficiency and substantially reduce the memory cost. We also adopt the optimal path extension [17] and dynamic k-cycle conflict heuristics [48] to reduce search space during the A search. We refer the interested reader to the aforementioned references for detailed explanations of these strategies.
4.3 Local *
Even with super-structure and the other techniques described in Section 4.2, scaling up exact score- based search remains challenge because the large search space. Given the popularity of distributed computation, the idea of divide-and-on and-conquer has been explored for scaling up Bayesian network

---

structure learning [10, 50, 47]. However, most of them involve conditional independence tests, which therefore rely on the faithfulness assumption in some way.
To avoid relying on the faithfulness assumption, we aim to develop a local search strategy based on exact search that relies the SMR assumption. Lu et al. [22] proposed an approximation algorithm, called Triplet A to do so. In particular, they first apply estimation method like MMPC [45] to obtain skeleton. For each variable X and each pair of its neighbors Y and Z, the algorithm constructs a cluster that consists of variables X, Y, Z and their neighbors indicated by the skeleton, and runs exact score-based search such as A on each of these clusters independently. Finally, the final structure is obtained by combining the search results from all clusters. A possible drawback is that the skeleton estimation method like MMPC usually requires the faithfulness assumption, although Triplet A has been shown to be able to recover some of the missing edges caused by the unfaithful CI relations.
Without faithfulness, fortunately, one is still able obtain a super-structure of the underlying DAG using our procedure under a strictly weaker assumption. In particular, the proposed super-structure estimation method involving inverse covariance estimation described in Section 3.2 requires only the SSCF assumption that is intuitively much weaker than faithfulness. Therefore, our goal is to develop a local search strategy based on this super-structure estimation method.
Following the similar strategy in [22], our main idea is that, for any variable X, its parents, children, spouses, and grandparents contain sufficient information for exact based search (with SMR assumption) to correctly discover the undirected edges and v-structures involving X (if there is any). This is because this variable set, denoted as Vx, includes all variables that direct common causes of X and any of its direct neighbors. The question is then how to correctly identify a set that contains those variables in Vx. A naive approach is to apply skeleton estimation methods like MMPC [45] to estimate a skeleton of the true DAG G. Clearly, for each variable X, its neighbors within two hops in the skeleton are guaranteed to contain its parents, children, spouses, and grandparents. However, MMPC requires the faithfulness assumption to be asymptotically correct, which may be restrictive in practice. Fortunately, based on Theorem 2, under the Markov and SSCF assumptions, the structure defined by supp @). denoted as (suupp( (Q)), is asymptotically a super-structure of the true DAG. It straightforwardly follows that the neighbors of variable X within two hops in (supp ()) must contain its parents, children, spouses, and grandparents. These variables. together with X itself, then contain sufficient information for exact score-based search to correctly discover the undirected edges and v-structures involving X. The empirical studies in Section 5.2 suggest that the proposed local search procedure is asymptotically correct as it returns the same solutions as the A *-SS method.
As described in Section 3.2, in practice, one can use the GLasso method to produce an estimate of the inverse covariance matrix Ô, and obtain its defined structure, denoted as (supp @)). Then, we construct local cluster for each variable, which consists of the variable itself and its neighbors within two hops in the structure ((supp(@)) and apply an exact score- method such as A on these local clusters independently. We then obtain the final structure by combining these local results.
Our approach can be easily parallelized by running the local searches for all variables in parallel, in which the complexity depends on the maximum size of local clusters. In practice, the computational resources may be limited and one is not able to do so. Furthermore, there is a huge overlap between different local clusters. leading to the redundancy of computation during the search procedure. To alleviate this, we consider an iterative approach starting from the smallest local cluster to the largest one that keeps some edges fixed to take full advantage of the information obtained from the previous searches. More specifically, in each iteration, we save the discovered undirected edges and v-structures involving the target variable from the local search. Then in the next iteration for, e.g., variable X, we look up the undirected edges and v-structures involving X that have been discovered and saved from previous iterations, and keep these edges fixed in the local search for variable X. By trusting the information conveyed by these edges and keeping them fixed, the search space for the following clusters can be drastically constrained. This improved procedure, called Local A is illustrated in Algorithm 1. Note that one could run some of the local searches in parallel to accelerate the iterative procedure, depending on the available computational resources.
It may be challenging to derive the exact computational complexity of the proposed method, as is the case for the A algorithm, partly owing to the heuristic involved [11, Section 4]. This is because the complexity is affected by different factors such as the size of sparse parent graphs and the heuristic function (i.e., dynamic k-cycle conflict heuristics) [48]. Thus, we are only able to provide the running time as a proxy of the computational complexity in Section 5.4.
7

---

Algorithm/ Local A*
Require: Structure defined by the support of estimated inverse covariance matrix ((supp ())
1: Initialize M as a d x matrix in which all entries are zero.
2: Let (i) denote the set of neighbors of variable X; in the structure ((supp( +)).
3: Obtain a variable ordering т by sorting the variables i, 1ii=1..... 1,...., ... based on the cardinality
of their corresponding local cluster C₁ {X+ (i) (UJEN() ~G)). Specifically, x (())
refers to the index such that (2) is the j-th smallest local cluster.
4: for i= = (1), T (2)...... (d) do
5: Obtain the local cluster C.-
6:
From M. obtain the previously discovered undirected edges and v-structures involving X;-
7:
Orient the undirected edges such that they do not create any cycle or additional v-structure. With these edges fixed, run A* (or A A*-SS) on cluster C₁-
8:
9: Convert the DAG estimated by A# to its MEC, and save the newly discovered undirected edges and v-structures involving variable X; to M.
10:
end for
12: Output the matrix M that represents the final MEC.
5 Experiments
We first conduct experiments to compare the efficacy of GLasso and MMPC for estimating super- structures of the true DAGs. We then validate the proposed search strategies, and compare them to different baselines. Lastly, compare different approaches scale up A search, including the proposed ones. The baselines include Triplet A [22]. PC [40, 30), FGES [31], MMHC [45], and SP [32]. The implementation details of our method and the baselines given in Appendix D.
In our experiments, the ground truth DAGS are simulated using the Rrdös-Rényi model [6] with different degrees and number of variables. We construct the weighted adjacency matrix of each DAG using edge weights sampled uniformly from [-0.8, -0.2] U [0.2, 0.8). Based on the weighted matrix constructed, we simulate exogenous noise variances sampled uniformly from [1, 2]. We report the structural Hammning distance (SHD) over the complete partial DAGs (CPDAGs). We also compute the Fl score of the undirected and directed edges in the estimated CPDAGs. We do not provide the complete results for structural intervention distance (SID) [28], and include only summary in Appendix E.2. Unless otherwise stated, we report the results and standard errors computed over 10 random simulations.
{300, 10000} samples using the linear Gaussian model with
5.1 Different Super-Structure Estimation Methods
To demonstrate the efficacy of GLasso for estimating super-structure, with weaker assumptions, we compare the quality of super-structures estimated by GLasso to those by MMPC. We evaluate their ability for discovering the direct neighbors in the ground truth, by computing the true positive rates (TPRs) and false discovery rates (FDRs) of estimating the true neighbors. Although the output of GLasso may contain non-adjacent spouses, here we only evaluate its discovered direct neighbors as only those are important for further exact search. We consider 10-node graphs with varying sample sizes and expected degrees, and report the results of MMPC with different significance levels
300 are shown in Figure 3, while those for n = 10000 are reported in Figure in Appendix H.3. In the first panel of Figure 3, one observes that GLasso achieves TPRs close to one across all cases, indicating that it rarely misses any direct neighbor, as compared to MMPC with lower TPRs. Notice also that the difference grows as the degree increases. Although GLasso has slightly higher FDRs than MMPC, we believe that the higher TPRs justify the cost of having larger search space for exact search. It is interesting to observe that even with a high significance level such as 0.5 (i.e., the hypothesis tests used by MMPC tend to produce more edges), MMPC has low TPRs on denser graphs. For instance, its TPR is close to 0.7 on graphs with degree of Similar observations can be made for the case n = 10000. These may be ascribed to the approximate violations of faithfulness in the simulated data, and therefore MMPC may miss some neighbors because of unfaithful conditional independencies. On the other hand, GLasso requires only the SSCF assumption, which is intuitively much weaker than faithfulness.
Due space limit, the results for sample size
8

---

12
TPR ofNegitoon
FOR Neightare
SUD of CPDAG
Expected
Experted degres
-
GLo690
MMPC (o-001)
MMPC
MMPC 0.5)
Figure 3: Results of different super-structure estimation methods 10-node graphs with different degrees. The sample size is n 300. Lower better, except for TPR.
SIDDCC
P1 scoce of arnoms
of
2.000
0.000
10
10
30
Number of modes
Number
Number modes
- A
Local A
Figure 4: Validation of the proposed methods on graphs with expected degree of 2. The sample size n 10000. For A * and Local * it assumed here that the ground truth (upp(() known. Higher is better, except for SHD.
We also consider the of the structures estimated by GLasso and MMPC super-structures for A*-SS, to study how they affect the exact search procedure. The third panels Figures and 7 show that the super-structures estimated by GLasso lead better search results than MMPC, especially graphs with high expected degrees. This is because the performance of recovering the true CPDAGs upper-bounded by the proportion of direct neighbors discovered by the super-structure.
5.2 Validation of the Proposed Search Strategies
We now conduct experiments to study the asymptotic correctness of the proposed strategies, by comparing the A SSSS and Local A methods to A# For A A*-SS and Local A*, assume that the support of the true inverse covariance matrix is known to ensure that the exact search does not make errors just because of inaccurate estimate of the inverse covariance. In Sections 5.3 and 5.4, consider the more realistic setting in which the ground truth supp ) is not known. Here we simulate 10000 samples for the graphs with expected degree of 2 and {5, 10, 15, 20) nodes.
The results are reported in Figure 4, which show that the performance Local A and A consistent across all metrics, including the Fl score of undirected and directed edges. This indicates that Local A is able to output the right MECs that are the same as * in most cases, which suggests that Local A is asymptotically correct. It is not surprising that these two methods perform better than A for graphs with 15 and 20 nodes, because we assume here that the true supp( () is known, which greatly reduces the search space and therefore less susceptible statistical errors owing to finite samples. This implies that a sound super- super-structure not only improves the efficiency, but also the performance. On the other hand, although A is guaranteed to find the global optimum, may still miss or incorrectly estimate some edges because of statistical errors.
5.3 Comparison with Other Baselines
To compare the proposed methods, i.c., *-SS and Local A with the baselines, consider graphs with varying sample sizes n E {300, 10000) and expected degrees from 2, 3, 4, 5). The baselines include Triplet * MMHC, PC, FGES, and SP. We start with 7-node graphs since the computation of SP may be too slow on graphs larger than that.
Due to space limit, we report the results for 300 and 10000 samples in Figures 8a and 8b, respectively, in Appendix E.4. With n 300 samples, * and Local A outperform other baselines across all metrics in most settings. Consistent with the observation in Section 5.2, the results of them

---

16
sore dbateeno
sorre offaroos
6:5
Time 10
Namber
Number
modee
offodes
Trpllr
Figure 5: Results and time for graphs with different sizes. The sample size is n 10000. Lower is better, except for F1 score.
exactly the same in all settings, which indicates that, similar to A Local A appears to output the globally optimal solutions. With larger sample size 10000, the advantage of A S-SS and Local A slightly diminishes as their performance is similar to the other baselines. A possible reason is that approximate violations of faithfulness are less likely to occur with more samples; thus, methods like PC and FGES are able to find the right solutions. This also demonstrates that exact methods like A *-SS and Local A * that rely on the SMR assumption relatively reliable in practice since they less susceptible to approximate violations of faithfulness. Notice that SP performs the best for 10000 samples; this is not surprising and Local A that rely on super-structure, their performance may be upper-bounded by the proportion of direct neighbors discovered by the super-structure estimation method (see Section 5.1). However, SP does not scale well to large graphs and can handle at most 8 nodes due to the huge search space.
is guaranteed find the globally optimal solutions. For A *
5.4 Scaling up A to Large Graphs
We have proposed several strategies to scale up exact methods like A such local search and constraining the parent graphs based on super-structure. To study the contribution of each strategy, compare different variants of A*, including A#, A A and Local A*. Here we adopt Triplet A and MMHC as our baselines since they have been shown to have similar performance to the other baselines in Section 5.3. Furthermore, they are the most relevant our proposed Local A method as they are also two-stage hybrid methods, i.e., they first estimate super-structure (or skeleton), and then perform score-based search it. We conduct experiments with different graph sizes up 300 nodes, and terminate the experiments that run for more than four days.
For better readability, the results and time for graphs with 100 nodes or less depicted in Figure 5, and those for larger graphs are provided in Appendix E.5. One observes that Local A * and MMHC significantly outperform the others in terms of scalability. Both of them can scale up to 300 nodes. Note that -SSSS scales up to 30 nodes, while A can only be scaled up to 20 nodes in our experiments. This verifies that incorporating super-structure with A indeed helps reduces search space. Moreover, the search time for Local A increases gently in the number of nodes, which demonstrates the potential of its scalability for large graphs. Note that in some of the experiments, Local A* * did finish within four days and were terminated. As described in Section 4.3, we observe that its running time depends the maximum size of local clusters. If some of the local clusters contain many variables, the running time may be much longer. On the other hand, MMHC has a shorter running time than Local A because it adopts a hill-climbing strategy and known run relatively fast, similar to PC and FGES that generally finish within a few minutes in our experiments. Nevertheless, on large graphs, Local A has much better structure recovery results than MMHC.
Conclusion
We studied the problem of reliable causal discovery with assumptions weaker than faithfulness. Specifically, in our proposed procedure, we adopted exact search that requires the SMR assumption, and relaxed the faithfulness assumption as much as is viable. We developed (1) sound super- super-structure estimation method based on the SSCF assumption that is intuitively much weaker than faithfulness,
(2) an improved exact score- based method with the constraint of the estimated super-structure, and (3) local search strategy that improves the scalability of exact search. The efficacy of the proposed method has been validated in our experiments conducted across various settings. It is worth noting that our procedure, at least in its current form, works only the linear Gaussian setting. Therefore, a future direction is to extend it to the non-Gaussian and discrete cases.
10

---

Acknowledgments
The authors would like to thank the anonymous reviewers for helpful comments and suggestions. This work was supported in part by the National Institutes of Health (NIH) under Contract R01HL159805. by the NST-Convergence Accelerator Track-D award #2134901, by the United States Air Force under Contract No. FFA855017-C77715 and by grant from Apple. The NIH or NSF is not responsible for the views reported this article. JZ's research was supported in part by the RGC of Hong Kong under GRF 13602720.
References
[1] M. Bartlett and J. Cussens. Integer linear programming for the Bayesian network structure learning problem. Artificial Intelligence, 244:258-271, 2017.
[2] D. M. Chickering. Learning Bayesian networks is NP-complete. In Learning from Data: Artificial Intelligence and Statistics V. Springer, 1996.
[3] D. M. Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3(Nov):507-554, 2002.
[4] D. Colombo, M. Maathuis, M. Kalisch, and T. Richardson. Learning high-dimensional directed acyclic graphs with latent and selection variables. The Annals of Statisties, 00:294-321, 2011
[5] Cussens. Bayesian network learning with cutting planes. In Conference on Uncertainty in Artificial Intelligence, 2011.
[6] Erdös and A. Rényi. On random graphs Publicationes Mathematicaee 6:290-297, 1959.
[7] M. Forster, G. Raskutti, R. Stern, and N. Weinberger. The frugal inference of causal relations. The British Journal for the Philosophy of Science, 69, 04 2017.
[8] J. Friedman, T. Hastie, and R. Tibshirani. Sparse inverse covariance estimation with the graphical Lasso. Biostatisties, 9:432-41, 2008.
(9] A. Ghassami, A. Yang, N. Kiyavash, and K. Zhang. Characterizing distribution equivalence and structure learning for eyclic and acyelic directed graphs. In International Conference Machine Learning, 2020.
[10] J. Gu and Q. Zhou. Learning big gaussian Bayesian networks: Partition, estimation and fusion. Journal of Machine Learning Research, 21(Aug):1-31, 2020.
[11] P. F. Hart, J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cyhernetics, 4(2))100-107, 1968.
[12] D. Haughton. On the choice of model to fit data from an exponential family. The Annals of Statistics, 16, 03 1988.
[13] Y. He, Jia, and B. Yu. Counting and exploring sizes of Markov equivalence classes of directed acyclic graphs. Journal of Machine Learning Research, 16:2589-2609, 2015.
[14] C.-.. Hsieh, M. A. Sustik, I. S. Dhillon, and P. Ravikumar. QUIC: Quadratic approximation for sparse inverse covariance estimation. Journal of Machine Learning Research, 15(83): 2911-2947, 2014.
[15] A. Hyttinen, Hoyer. F. Eberhardt, and M. Jarvisalo. Discovering cyclic causal models with latent variables: A general bas-b procedure. In Conference Uncertainty in Artificial Intelligence, 2013.
[16) A. Hyttinen, F. Eberhardt, and M. Järvisalo. Constraint-based causal discovery: Conflict resolution with answer set programming. In Conference on Uncertainty Artificial Intelligence, 2014.
11

---

[17] S. Karan and J. Zola. Exact structure learning of Bayesian networks by optimal path extension. In IEEE International Conference on Big Data, pages 58-55. IEEE Computer Society, 2016.
[18] M. Koivisto and K. Sood. Exact Bayesian structure discovery in Bayesian networks. Journal of Machine Learning Research, 5(Dec):549-573 2004.
[19] K. Kojima, E. Perrier, S. Imoto, and S. Miyano. Optimal search on clustered structural constraint for learning Bayesian network structure. Journal of Machine Learning Research, 1 11(Jan):285- 310, 2010.
[20] D. Koller and N. Friedman. Probubilistic Graphical Models: Principles and Techniques. MIT Press, Cambridge, MA, 2009.
[21] P.-L. Loh and P. Bühlmann. High- nigh-dimenssooal learning of linear causal networks via inverse covariance estimation. Journal of Machine Learning Research, 15(88):3065-3105, 2014.
[22] N. Y. Lu, K. Zhang, and C. Yuan. Improving causal discovery by optimal Bayesian network learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[23] I. Ng, A. Ghassami, and K. Zhang. On the role of sparsity and DAG constraints for learning linear DAGs, In Advances in Neural Information Processing Systems, 2020.
[24] S. Ott, S. Imoto, and S. Miyano. Finding optimal models for small gene networks. Pacific Symposium Biocomputing. Pacific Symposium on Biocomputing, 9:557-67, 2004.
[25] Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, 2009.
[26] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg. J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2888 28380, 2011.
[27] E. Perrier, S. Imoto, and S. Miyano. Finding optimal Bayesian network given super-structure. Journal of Machine Learning Research, 9(74):225-22288 2008.
[28] J. Peters and P. Bühlmann. Structural intervention distance (SID) for evaluating causal graphs. Neural Computation, 27, 2015.
[29] J. Peters, D. Janzing, and B. Schölkopf. Elements of Causal Inference Foundations and Learning Algorithms. MIT Press, 2017.
[30] Ramsey, J. Zhang, and Spirtes. Adjacency-fiitffunnes. and conservative causal inference. In Conference on Uncertainty in Artificial Intelligence, 2006.
[31] Ramsey, M. Glymour, R. Sanchez- Sanchez-Romero, and C. Glymour. A million variables and more: the fast greedy equivalence search algorithm for learning high-dimensional graphical causal models, with an application to functional magnetic resonance images. International Journal of Data Science and Analytics, 3(2): 2017.
[32] G. Raskutti and C. Uhler. Learning directed acyclic graph models based on sparsest permutations. Stat, 7(1)xe183 2018
[33] P. Ravikumar, G. Raskutti, M. J. Wainwright, and B. Yu. Model selection in Gaussian graph- ical models: High-dimensional consistency of e-regularrzed MILE. In Advances in Neural Information Processing Systems, 2008
[34] Ravikumar, M. Wainwright, G. Raskutti, and B. Yu. High-dimensional covariance estima- tion by minimizing & er-penalieed log- log-determinant divergence. Electronic Journal of Statistics, 5, 2011.
[35] R. Scheines, P. Spirtes, C. Glymour, C. Meek, and T. Richardson. The TETRAD project: Constraint based aids to causal model specification. Multivariate Behavioral Research, 33: 65-117, 1998.
12

---

[36] G. Schwarz. Estimating the dimension of model. The Annals of Statistics, 6(2):461-466 1978.
[37] M. Scutari. Learning Bayesian networks with the bnlearn R package. Journal of Statistical Software, 35(3):1-22, 2010.
[38] T. Silander and P. Myllymäki. A simple approach for finding the globally optimal Bayesian network structure. In Conference on Uncertainty in Artificial Intelligence, 2006.
[39] A. Singh and A. W. Moore. Finding optimal Bayesian networks by dynamic programming. Technical report, Carnegie Mellon University, 2005.
[40] Spirtes and C. Glymour. An algorithm for fast recovery of sparse causal graphs. Social Science Computer Review, 9:62-72, 1991.
[41] P. Spirtes and J. Zhang. A uniformly consistent estimator of causal effects under the k-triangle- faithfulness assumption. Statistical Science, 29(4):662-678, 2014.
[42] Spirtes and K. Zhang. Search for causal models. In M. Maathuis, M. Drton, S. Lauritzen, and M. Wainwright, editors, Handbook Graphical Models, chapter 18. CRC Press, Inc., 2018.
[43] P. Spirtes, C. Meek, and T. Richardson. Causal inference in the presence of latent variables and selection bias. In Conference on Uncertainty in Artificial Intelligence, 1995.
[44] P. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction, and Search. MIT press, 2nd edition, 2001.
[45] Tsamardinos, L. Brown, and C. Aliferis. The max-min hill-climbing Bayesian network structure learning algorithm. Machine Learning, 65:31-78, 10 2006.
[46] C. Uhler, G. Raskutti, P. Bühlmann, and B. Yu. Geometry of the faithfulness assumption in causal inference. The Annals of Statistics, 41(2):436 0606664633110 2013.
[47] X. Xie and Z. Geng. A recursive method for structural learning of directed acyelic graphs. The Journal of Machine Learning Research, 95Mrcch)4599-483, 2008.
[48] C. Yuan and B. Malone. Learning optimal Bayesian networks: shortest path perspective. Journal of Artificial Intelligence Research, 48(1):23 65, 2013.
[49] C. Yuan, B. Malone, and X. Wu. Learning optimal Bayesian networks using A search. In International Joint Conference on Artificial Intelligence, 2011.
[50] H. Zhang, S. Zhou, C. Yan, J. Guan, X. Wang, J. Zhang, and J. Huan, Learning causal structures based on divide and conquer. IEEE Transactions Cybernetics, 2020.
[51] Zhang and P. Spirtes. Detection of unfaithfulness and robust causal inference. Minds and Machines, 18, 06 2008.
[52] X. Zheng, B. Aragam, P. Ravikumar, and E. P. Xing. DAGs with NO TEARS: Continuous optimization for structure learning. Advances Neural Information Processing Systems, 2018.
13


Reviews:
[{"review_id": "kjpZKtJ9sw-", "reviewer": "Reviewer_vWU7", "summary": "The authors propose a new method for learning the graph structure of Bayesian networks.  Specifically, the authors propose a method for learning the super-structure and efficient local search methods for producing the final structure given the super-structure.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In general, the experiments (Section 5) appear well conceived and well executed.  They focus on specific aspects of the overall approach proposed in the paper, and they compare to plausible alternatives.  Specifically, the authors use a reasonable and diverse array of baselines in their experiments. \n\nHowever, the authors measure the accuracy of structure learning methods using structural Hamming distance (SHD), a measure that has been strongly and appropriately criticized in recent work (Peters & Bühlmann 2015; Gentzel et al. 2019).  The paper would be stronger if it used a more realistic and informative performance measure.  The results are strong enough that the observed differences in SHD are probably indicative of good overall performance, but measures such as structural intervention distance (SID) or measures of the accuracy of actual interventional queries would be more informative.\n\nIn the second paragraph of the introduction, the authors state that constraint-based methods “first estimate the skeleton of the causal structure and then identify the v-structures based on conditional independence tests.” Edge orientation rules do more than just identify v-structures, although that is perhaps the most important (and justified) rule for edge orientation.  The description should be updated to be more accurate.\n\nThe authors note in the introduction that the limitations of randomized experiments concern ethical issues.  While this is one potential problem with randomized experiments, there are others, including practicality (astronomers cannot randomly assign the size of a galaxy) and cost (it would be prohibitively expensive to randomly assign programmers to multiple teams, each of which develops a major software platforms using a different programming language).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The discussion here is adequate, given the focus of the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "RfscTaeraV2", "reviewer": "Reviewer_H5q9", "summary": "This paper focuses on finding weaker and realistic identifiability conditions for Gaussian linear structural equation models. More precisely, it provides two weaker single shielded-collider-faithfulness and single unshielded-collider-faithfulness assumptions than the widely-used faithfulness, adjacency-faithfulness, orientation faithfulness and triangle-faithfulness assumptions. Based on the proposed assumptions, it further develops a computationally improved exact score-based search methods, and thus, it can recover a large-scale DAG. Lastly, it compares the proposed method and the state-of-the-art A*, MMHC, PC, FGES, and SP algorithm whose accuracy depends on faithfulness or related conditions. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and well-organized. Especially, I like the introduction and the background sections that summarize the prior works well. The proposed method balances the accuracy and computational cost well. However, the novelty of the paper is restricted on the Gaussian linear SEMs, and some results seem to be obvious when focusing on Gaussian linear SEMs. Furthermore, it seems that the proposed method might be difficult to be generalized for general DAG models. Lastly, it does not provide the computation complexity of the proposed algorithm that is one of the main contributions. \n\n(1) Theorems 1 and 2 seems to be straight forward: \n\nIn the Gaussian linear SEM settings, it is well-known that the off-diagonal entries of (j,k) show the conditional independence relationships between (j, k) given the others (V - {j, k}). Together with Markov condition that j and descent of the collider that is not connected to j is conditionally independent, this implies the Theorems 1 and 2 seem to be direct. In addition, as in Lemma 1 of Loh, Po-Ling, and Peter Bühlmann, 2014, also in the supplementary material, the exact value of the element of the inverse covariance matrix can be expressed in terms of edge weights and error variances. \nOmega_{jk} = - \\beta_{jk} \\sigma_k^2 + \\sum_{ l such that (j,k,l) is unshilded collider } \\beta_{jl} \\beta_{kl} / \\sigma_{l}^2. \nThis directly implies the Theorems 1 and 2. \n \n(2) In general linear SEM settings, a conditional dependence does not imply the non-zero partial correlation. Hence, the proposed method seems to be difficult to be generalized to other linear SEMs.\n\n(3) I agree that SUCF assumption can be restrictive in some finite sample settings, as shown in numerical experiments on page 5 in Figure 2. However, the provided result would be meaningful for Gaussian linear SEMs with special range of \\beta_{j,k} and sigma_j. In other words, for some settings of \\beta, \\sigma (e.g., \\beta_{jk} is negative), we can also see that the minimum value of Omega_{jk} for spouses are the bigger than neighbors. In addition, we can also easily find the settings for which SUCF are well-satisfied as the degree increases. Hence, I think this paper should carefully provides the focused settings, and emphasizes why these setting should be considered. \n\n(4) I like Theorem 4 that, in the results produced by exact score-based search on the variable set containing the variable X and its parents, children, spouses, and grandparents, the discovered undirected edges between X and its direct neighbors and the v-structures involving X are asymptotically correct.\n\nHowever, it seems to be unclear that how to apply the Theorem 4 to the proposed algorithm (Local A*), because the local cluster C_i includes not only parents, children, spouses, and grandparents, but also (i) grandchildren, (ii) spouses of parents that are not it parents, (iii) children of its parents, (iv) spouses of children, and (v) spouses of its spouses.\n\nIn addition, it is unclear that the meaning of the ordering \\pi in Algorithm 1. \n \n(5) I think the provided numerical experiments in Section 5 do not effectively support one of the main ideas that SSCF-based local A* algorithm performs better than the compared faithfulness-based DAG learning algorithms. It is mainly because the low performance of a method possibly comes from an inappropriate conditional independence test and a  strength of association (dependency) function, score function, greedy search method, or violation of the incoherence assumption. \n\nHence, it would be better to exploit two types of random Gaussian linear SEMs: (i) violating faithfulness (or related faithfulness) whereas satisfying SSCF in population; and (ii) random Gaussian linear SEMs satisfying faithfulness. And then, compares the performance of the considered algorithms in both limited sample and population settings. Otherwise, it is hard to accept that a better-accuracy of the proposed algorithm comes from weaker identifiability condition. Furthermore, it would be better to provide what conditional independence test and scores for MMPC and FGES, respectively. In addition, it would be also better to explain how to choose appropriate regularization parameter for GLasso. \n\nIn addition, it is hard to understand the purpose the numerical experiments in Section 5.1. As I understood, it shows that Glasso is clearly better than MMPC in terms of recovering the super-structure defined by the support of estimated inverse covariance matrix. However, in principle, Glasso recovers the skeleton of the moralized graph, whereas MMPC recover the skeleton of a true graph. Hence, the direct comparison seems to be awkward. Furthermore, MMPC does not require the incoherence condition that is almost necessary condition for GLasso. \n\nLastly, it seems to be unfair that greedy-search- or forward-selection-based PC, FGES, MMHC were compared in terms of accuracy. However, the PC and FGES were not considered when comparing the run-time. As you also know, they are designed for large-scale graphs with thousands node.\n\nMinor: \n\nDefinitions of neighbors are different on page 5 where it is the set of nodes including parents and children and in Figure 3 where it seems to be a set nodes including parents, children, and spouses.\n\nLine 370, it would be sample version of the faithfulness assumption, so called \\alpha-faithfulness.\n\n########## Updated ###########\nThanks for the kind answer. Based on your asnwer and other reviews, I increase my rate fomr 4 to 6. This paper has a clear contribution, but I thought it is not enough for the NIPS level. However, after reading the other reviews, I changed the my opinion. \n\nBy the way, the references are not requried for the definition of the neighbors, but its definition should be clarified in the paper. \n\nIn addition, there is no statistical guarantees that GLasso performs better than MMPC in terms of recovering direct neighbors. In fact, MMPC is consistent, whereas GLasso is not when recovering neighbors. In addition, there are many settings in which MMPC empirically performs better than GLasso. However, I agree that the simulation settings used in the paper are widely exploited in the relevant sutides. This is my simple curiosity that why most related studies apply these settings.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not related", "review_text": "", "extra_scores": {"ethical_concerns": "None. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12 - 24 hours"}, "extra_text": {}}, {"review_id": "P-xHfcEfaZk", "reviewer": "Reviewer_hS1q", "summary": "This paper improves the scalability of exact methods for structural learning of Bayesian networks.\nThe author/s restrict/s the search space via learning a sound super-structure, and then by performing local exact search on the individual variables with their neighbors within two hops in the super-structure. \nThe paper theoretically proves that the developed approach guarantees correct results under the assumption of infinite data when weaker assumptions than faithfulness are considered. \nThe last part of the paper describes results of a rich set on numerical experiments, synthetic experiments, which support the effectiveness of the proposed approach which scales up to hundreds of nodes while achieving high accuracy.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: \nThe paper is original because it proposes to weaken the standard assumption of faithfulness which is typically the foundation to ensure correcteness when recovering the structure of bayesian networks.\nFurtherore, the paper also develops a new algorithm i.e.,a local A* approach for causal discovery.\n\nQuality: \nThe paper is well structured and written. Terms are properly introduced and defined before using them.\nThe paper reads very well and the narration is sensible while each piece of information is appropriately presented and discussed.\nTechnical quality is very good in my humble opinion, the paper shows tha the author/s know very well the research area and also very recent results from the specialized literature.\nI did not check the proof of theorems but according to theorems in the paper, the author/s convinced me that their algorithm works.\n\nClarity:\nThe paper is clear, in other terms it is is clear the theoretical problem which is tackled and it is also very clear how the problem has been solved.\nI also appreciated the numerical experiments section which shows on synthetic data how the proposed approach works and performs.\n\nSignificance: \nThe paper is significant to the community of machine learning with specific reference to bayesian networks and causal networks structural learning from data.\nHowever, the contibution is limited to a very specifc class of models and thus its' potential impact should be retrospectively evaluated.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I was not able to find any discussion about limitations of the proposed approach. \nSome mention is made about limitations of the proposed approach but I think that the author/s should try to better frame and criticize the limitations of the developed approach and which is the expected impact of their work, which I think is relevant.\nIn particular, I read discussion about numerical results, but still I think something more specific to be concluded when evaluating judging the proposed apporoach.\nThe paper devotes some space to potential extensions and future works but no mentions to critics of the proposed approach.\nThe impact to the reseach community could be good but this strongly depends on the fact that the proposed apporach works for a limited class of models.\n", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "IkVIrHaB3Db", "reviewer": "Reviewer_BZ1f", "summary": "This paper proposes two steps for learning the DAG structure from linear Gaussian data. First, it is shown that under a condition weaker than several forms of faithfulness, the inverse of the observational covariance matrix can be used to find a graph guaranteed to contain all edges in the DAG. Second, another theoretical result is established that shows that an exact structure learning algorithm will find the correct edges and v-structures around X even when it sees only a particular neighbourhood around X. An algorithm is proposed that leverages both results.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think several results in this paper are interesting and novel. In particular, Theorem 4 (guaranteeing partial correctness of local search results) seems to be a powerful new result. I also appreciate how they fit together in this paper. There are a few points where the presentation could be improved, detailed below.\n\nIt should be mentioned earlier on (preferably in the abstract) that this paper deals with linear SEMs, not e.g. discrete BNs. The technique of using the inverse of the covariance matrix is very specific to the linear case.\n\nWhat other methods exist for structure learning that rely on the inverse of the covariance matrix? How does the proposed method compare to them?\n\nNear Figure 2, the term \"spouse\" is used, and apparently (no definition is given) pairs of adjacent nodes are not considered spouses. I don't think that's the standard definition.\n\nThere is something subtly wrong with Theorem 2. Under standard definitions, it is allowed to have B_ij = 0 even though there is an edge there. Such a case is a counterexample to the theorem. It also goes against the SMR assumption, and I think that by assuming SMR in the theorem's statement, the problem can be fixed. Instead of the implication \"edge in E implies B is not 0\" which is currently used in the proof, the SMR assumption can be invoked at that point to get to the same conclusion.\n\nIn the paragraph below Theorem 3, the text about parent graphs isn't very informative: if the reader doesn't know what they are already, they won't learn from reading this.\n\nSpelling / grammar:\n34: charactezation - letters missing\n55: constraint -> constrain\n210: the strong SUCF assumption -> a strong SUCF assumption; consider adding quotes around \"strong SUCF assumption\"\n\nUPDATE: I appreciate that the authors are incorporating my comments into their manuscript. (My score didn't change.)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is consensus on acceptance among reviewers. There are a few suggestions and discussions that can be helpful to improve the manuscript, in particular to appeal the potential audience at neurips 2021.
Decision: Accept (Poster)