Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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. 

However, 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.

In 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.

The 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).
limitations_and_societal_impact: The discussion here is adequate, given the focus of the paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

It 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.

What other methods exist for structure learning that rely on the inverse of the covariance matrix? How does the proposed method compare to them?

Near 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.

There 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.

In 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.

Spelling / grammar:
34: charactezation - letters missing
55: constraint -> constrain
210: the strong SUCF assumption -> a strong SUCF assumption; consider adding quotes around "strong SUCF assumption"

UPDATE: I appreciate that the authors are incorporating my comments into their manuscript. (My score didn't change.)
limitations_and_societal_impact: Adequately addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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. 

(1) Theorems 1 and 2 seems to be straight forward: 

In 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. 
Omega_{jk} = - \beta_{jk} \sigma_k^2 + \sum_{ l such that (j,k,l) is unshilded collider } \beta_{jl} \beta_{kl} / \sigma_{l}^2. 
This directly implies the Theorems 1 and 2. 
 
(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.

(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. 

(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.

However, 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.

In addition, it is unclear that the meaning of the ordering \pi in Algorithm 1. 
 
(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. 

Hence, 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. 

In 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. 

Lastly, 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.

Minor: 

Definitions 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.

Line 370, it would be sample version of the faithfulness assumption, so called \alpha-faithfulness.

########## Updated ###########
Thanks 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. 

By the way, the references are not requried for the definition of the neighbors, but its definition should be clarified in the paper. 

In 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.
limitations_and_societal_impact: Not related
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper improves the scalability of exact methods for structural learning of Bayesian networks.
The 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. 
The paper theoretically proves that the developed approach guarantees correct results under the assumption of infinite data when weaker assumptions than faithfulness are considered. 
The 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.
main_review: Originality: 
The 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.
Furtherore, the paper also develops a new algorithm i.e.,a local A* approach for causal discovery.

Quality: 
The paper is well structured and written. Terms are properly introduced and defined before using them.
The paper reads very well and the narration is sensible while each piece of information is appropriately presented and discussed.
Technical 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.
I did not check the proof of theorems but according to theorems in the paper, the author/s convinced me that their algorithm works.

Clarity:
The 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.
I also appreciated the numerical experiments section which shows on synthetic data how the proposed approach works and performs.

Significance: 
The paper is significant to the community of machine learning with specific reference to bayesian networks and causal networks structural learning from data.
However, the contibution is limited to a very specifc class of models and thus its' potential impact should be retrospectively evaluated.
limitations_and_societal_impact: I was not able to find any discussion about limitations of the proposed approach. 
Some 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.
In particular, I read discussion about numerical results, but still I think something more specific to be concluded when evaluating judging the proposed apporoach.
The paper devotes some space to potential extensions and future works but no mentions to critics of the proposed approach.
The 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.
review_title: null

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)