Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: Learning Bayesian networks is a notoriously difficult task, considering the fact that the search space for all possible graphs scales exponentially with the potential arcs. In the paper, authors propose a heuristic search algorithm which reduces the time complexity of well-known exact algorithms such as PC. PC is a constraint-based algorithm which recovers Bayesian networks based on the conditional independencies entailed by the nodes of the graphs. Whereas the methodology proposed in the paper makes an additional information theoretical assumption for the structure of the graph, i.e. the conditions stated in the paper, which effectively reduces the search space of valid graphs for the given nodes and enables us to make use of a greedy search algorithm.
main_review: Paper is easy to read and very well written in general. Assumptions, theorems, derivations, and algorithms are stated in full clarity. Authors also demonstrate their algorithm on a toy example, which is very helpful for understanding the main principles of the algorithm. I think such a paper will be of interest to NeurIPS community.

The main contribution of the paper is the information theoretical conditions that are proposed to narrow down the overall search space of graphs. In the first phase of the proposed methodology, a topological ordering of the nodes, i.e. the layers of the underlying graph, is found using these conditions. Once the topological ordering is found, the rest of the graph search becomes straightforward, Namely, the edges between the layers of the graph are searched using the conditional independence properties.

However, any topological ordering enforced on a graph would yield a search procedure with the same efficiency as the methodology in the paper. Indeed, one could change the conditional H with any functional F, say negative H, and would still come up with a unique DAG, because there is nothing specific to H in the proposed methodology. So, I believe the selection of H needs further justification, e.g. how does the selected criteria relate to the actual topological ordering of the nodes? What are the advantages of choosing H for narrowing down the search space rather than a more general functional F?

Additionally, it is not perfectly clear to me that why the size of largest markov boundary can be assumed less than logarithm of the number of nodes. This is a critical assumption for calculation of the polynomial time complexity stated in the paper, and I think an addittional justification for this would be helpful, too.
limitations_and_societal_impact: I haven’t seen a part where the limitations and the social impact of the work are mentioned.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors present several novel results regarding learning of discrete graphical models.  They introduce a conditional entropy-based identifiability condition that allows one to decompose an unknown directed acyclic graph (DAG) structure into different layers.  They introduce another entropy based measure to allow them to efficiently locate the markov boundary of nodes in each layer without backtracking or pruning.  These two results are combined to develop a novel algorithm for learning a DAG from sample data.  The authors demonstrate the correctness of the proposed algorithm by empirically verifying that the procedure recovers the expected graphs when the required assumptions are met.  Finally, they introduce a sample complexity result for how quickly one can recover the minimial IMAP G, as a function of the number of nodes and number of layers in the DAG.  

These contributions seem significant and, to the best of my knowledge, are novel.
main_review: My main question/criticism for the authors is how likely are conditions 1 and 3 to be met in practice and what happens to the proposed procedure when these conditions are not satisfied? Do you empirically get sensible results, or results on par with other learning algos, when running on graphs that don't satisfy this criteria?  If condition 3 is relaxed, do you simply lose the sample complexity guarantee?

The proposed algorithm seems to perform worse than PC and GES for small sample size and larger number of nodes. Can you provide any color as to why this is the case?
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes a polynomial time algorithm for learning very sparse DAGs (constant maximum Markov blanket size) from observational data under a new identifiability condition that generalizes some of the existing identifiability condition (especially for the linear Gaussian case). The authors also derive sample complexity of their algorithm which has logarithmic dependence on the number of variables but unfortunately exponential dependence on the maximum MB size. The strengths of the paper are that the authors make no distributional (e.g. Gaussian) or functional (e.g. linear additive model) assumptions for deriving their identifiability condition and the associated algorithm. The algorithm learns a DAG layer-wise and there is a novel masking strategy due to which they identify the layers without requiring that all the nodes have the same conditional entropy. The paper advances the identifiability theory of general Bayesian networks and proposes a novel algorithm. However, even though the method is general and the assumptions are purely information-theoretic, it is not clear if the identifiability condition is useful beyond the linear Gaussian case — non-linear additive noise models and linear non-Gaussian (LinGAM) models are identifiable without any stringent conditions. Furthermore, the exponential dependence of the sample and computational complexity on the MB size is problematic, the experiments are not very strong, and lastly the presentation is too dense and unintuitive. 
main_review: ## Strengths

1. General algorithm and no distributional assumptions. The authors do not even assume additive models. The conditions are fully information-theoretic.
2. The core idea is novel: that once you have identified 0 to j layers, in order to identify the (j+1)-th layer we don't need every node after the (j+1)-th layer to have larger conditional entropy than the nodes in the (j+1)-th layer (whose parents have been identified and hence the conditional entropy is the entropy of the exogenous/noise variable in an additive model). As long as there is one node in the (j+1)-th layer for which this condition is satisfied, we can mask out it's descendants.

## Weakness

- Why not just use the PC algorithm to first estimate the skeleton ? Then, for a node $X_i$, the intersection of its neighbors (in the skeleton) with the layers identified so far should give its parents.
- The current algorithm's computational and sample complexity is exponential in the maximum size of a node's ancestral Markov blanket (M). Whereas the PC algorithm's computational complexity is exponential in the tree-width and sample complexity is polynomial in the maximum neighborhood size ("Estimating High-Dimensional Directed Acyclic Graphs
with the PC-Algorithm", Kalisch and Buhlmann). In addition the PC algorithm doesn't need Condition 3. The PC algorithm doesn't make any distributional or functional assumptions and only requires faithfulness to identify the skeleton.
- How does the identifiability condition fit with existing identifiability results ? We know it generalizes the identifiability condition of Ghoshal and Honorio 2018 (GH2018) and equal variance condition for linear Gaussian case. But we know that linear non-Gaussian (LinGAM) models are identifiable and non-linear additive noise models are identifiable. Polynomial time algorithms exist for both these cases (ICA based method for LinGAM and RESIT for non-linear ANM). For LinGAM and non-linear ANM models the proposed identifiability condition is very strong and is only sufficient but not necessary. In spite of making no distributional and parametric assumptions, looks like the only case where it is useful is linear Gaussian case.
- The presentation can be significantly improved. Notation is too dense and confusing
    - Rather than saying 'the "$X_i$" for "$X_k$"' introduce a term for their relationship and use that.
    - Say what "testing and masking" means
    - Line 176: $d_6$ should be $h_6$.
    - Line 177: "$h_3 < h_{[4:6]}$ and $h_5 < h_6$  imply condition 2 doesn't hold here". Why ? Condition 2 is about conditional entropy of a node given parents, where $h_3, ..., h_6$ are marginal entropies.
- Somehow identifiability condition doesn't significantly relax the identifiability condition of GH2018 for linear SEMs. For a fully connected DAG (i.e. whose skeleton is a complete graph) it looks like the two identifiability condition are the same. The identifiability condition is significantly weaker than GH2018 only for very sparse graphs.
- Experiments: running time comparison with PC and GES (surprisingly GES does well even in spite of returning a local optima).
- Experiments: no experiments when identifiability condition is not satisfied. So it is not clear if how often the condition is satisfied for sparse and dense graphs.
- Experiments: Even when the identifiability condition is satisfied the algorithm doesn't significantly out-perform PC or GES. Why ? This is in spite of the fact that the proposed algorithm specifically exploits the condition. Does the SHD go to zero as the number of samples is further increased ?
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: It analyzes the complexity of learning directed acyclic graphical (DAG) models from observational data.  It proposes an algorithm that uses a local Markov boundary search to learn an identifiable DAG G from samples. They prove an identifiability result on DAG learning. Roughly speaking, this condition requires that the entropy conditioned on an ancestral set of each node in G is dominated by one of its ancestors (Condition 1). They, also derive sample complexity of their algorithm and further illustrate its performance in a simulation study. 
main_review: It studies an interesting and important problem in causal structure learning. 

The paper is well-written but more explanation about the role of Masked set in Algorithm 1 would improve its readability. 

The theoretical results especially the sample complexity results are quite valuable and could be beneficial
 to the researchers in this field. 
However, my main concern is about the conditions under which the results are presented and also the performance of the proposed algorithm. 

Although, it is discussed that C1 is a generalization of equal entropy condition but having C1 or PPS condition heavily depends on the underlying structural equation model (SEM) that generates the data. Moreover, how verifiable are these conditions given observational data? 
What type of systems would satisfy conditions 1 and 2? For instance, linear with non-Gaussian systems etc. 

Although the authors claim that their approach does not directly assume faithfulness but having conditions 1 and 3 somewhat encourages similar phenomena (I do not suggest that these conditions and faithfulness are equivalent). It would be educational to see an example that violates faithfulness but satisfies the conditions 1 and 3. Is MOD model in the experimental section an example?

A brief discussion about the result of proposition 4.1. is required. For instance, when does the right-hand-side of the equation in this proposition is positive? It seems that often (e.g., for Erdos-Renyi graphs) this bound is trivial, i.e., it is negative. Clearly, it depends on the parameters.  

Given the experimental results, the proposed algorithm performs often as good as PC and GES in large sample sizes but for smaller sample size (1000) it often performs poorly. How does Algorithm 1 compare to the others in terms of run-time and computational complexity? Also, it is important to see (e.g., empirically) how tight is the proposed sample complexity in Theorem 5.1.  

limitations_and_societal_impact: Yes. Please see my comments.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the problem of learning the Bayesian network structure of $d$ random variables in the fully observational case.

Among the main contributions, the authors propose:

1. A novel identifiability condition for BN structure learning which does not require the typical faithfulness condition. This new condition is based on conditional entropies of the random variables given their ancestors.

2. Motivated by the proposed conditions in Theorem 3.1, authors show Algorithm 1 to learn the BN structure, which is based on estimating the Markov boundary of each node with respect to its ancestor set. 

3. Computational and statistical complexities are discussed, and they are polynomial when the maximum Markov boundary size is $O(\log d)$.

4. Some synthetic experiments are provided and the proposed method is compared against the classical PC and GES algorithms.

main_review: Here I present my review along the axis of the NeurIPS reviewing guidelines:

**Originality**

- Are the tasks or methods new? 
  - The most novel contribution relates to Theorem 3.1, which is the identifiability condition based on conditional entropies. Under this condition, faithfulness is not required which I find appealing.
The proposed algorithm for learning the structure is not quite novel  on its own in the sense that there are existing work that also learn the network in a layer-wise fashion; similarly, as stated by the authors, learning the Markov boundary has also been studied before.

- Is the work a novel combination of well-known techniques?
  - Given the new identifiability condition, I think Algorithm 1 can be regarded as a novel combination of known ideas for learning the BN structure. Moreover, the algorithm requires several estimations of conditional entropies, for which the authors use existing estimation techniques.

- Is it clear how this work differs from previous contributions? 
  - Yes. The main contrast to previous work is with regards to the identifiability condition. 

- Is related work adequately cited?
  - Yes, although I believe there are some lines of work that have not been commented whatsoever. For instance, learning BN structures from continuous optimization has gained much attention in recent years but they are not been mentioned.


**Quality** 

- Is the submission technically sound? 
  - Yes, claims are sound. 

- Are claims well supported (e.g., by theoretical analysis or experimental results)? 
  - Yes, proofs are provided in the appendix. I have checked most of them and could not find major issues.
Synthetic experiments are also provided although I do not find them convincing.

- Are the methods used appropriate? 
  - Yes.

- Is this a complete piece of work or work in progress? 
  - Complete work.

- Are the authors careful and honest about evaluating both the strengths and weaknesses of their work?
  - Yes. Although some important discussion could be missing. See my questions at the end.


**Clarity** 

- Is the submission clearly written? 
  - Yes. I was able to follow the contributions without any problems. Can be improved, see last section of my review.

- Is it well organized? 
  - Yes.

- Does it adequately inform the reader? 
  - Yes.


**Significance** 

- Are the results important? 
  - I believe the identifiability condition is interesting and important. The algorithm is also compelling; however, I do have some questions that would like to be addressed. See below.

- Are others (researchers or practitioners) likely to use the ideas or build on them? 
  - Maybe. There are open questions that some researchers might find interesting to study.

- Does the submission address a difficult task in a better way than previous work? 
  - Unclear. The experiments are not convincing on this.

- Does it advance the state of the art in a demonstrable way? 
  - No. Relying in the experiments shown, the proposed seems to be at best comparable.

- Does it provide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach?
  - The work is mainly theoretical with a small set of experiments.

# Questions / Comments

1. One of the main arguments of the new identifiability condition is that it applies to general distributions without parametric assumptions. However, the conditions are given in the population case. I believe that the set of unfaithful distributions has Lebesgue measure 0 in the population case. What would be the advantage of the new condition against faithfulness if it is given in the population setting?

2. In Lines 92-93 it is stated that the proposed approach highlights the role of fundamental assumptions obscured in the linear case. Can authors elaborate on this? I could not find a proper discussion of this claim in later sections of the paper.

3. It is not until page 7, line 261, where one notices that there is a "sparsity" assumption of $M \leq \log d$. I believe this is an important assumption that should be stated in the abstract and contributions section. If this assumption does not hold, the sample and time complexity are exponential.

4. Right before line 835, the error bound is confusing to me. Does it decay?

5. The experiments are unconvincing. First, the method seems to work worse than PC and GES in the low sample complexity regime, which is an important drawback. Also, as the number of samples increases, the proposed method is at best comparable. Both reasons undermine the usability of the method in practice. Second, given the sample and time complexity results, it would be interesting to see the log-dependence/phase-transitions plots. Finally, it would help to compare against methods that provide guarantees such as that of Ghoshal & Honorio.

Minor typos/comments:

Line 135: it would perhaps help to define $\lceil a \rceil^+ \equiv \max (a,0)$, and use $\lceil L(X_k) - 2 \rceil^+$ to avoid $L(X_k) - 2$ being negative. 

Line 191: it says "we use apply..."

Line 254: it says "...any any.."

---
I thank the authors for their response. I feel more positive about the paper and will increase my score to 6. I think that the paper could benefit by adding some points of this discussion.



limitations_and_societal_impact: Authors have discussed some limitations of their methods. Being the work of theoretical nature, I do not foresee any negative societal impact.
review_title: null

Meta-review: The general question of identifying conditions under which Bayesian networks can be learned by efficient algorithms is an important direction that deserves further investigation. The present paper identifies a new condition that roughly amounts to entropies increasing in the layers of the network. Under this condition it is fairly straightforward to recover the network in a greedy fashion layer by layer. The condition is strictly weaker than the well-known faithfulness condition. 

The reviewers would have liked to see additional discussion around the conditions for model recovery, including examples and so forth. Along these lines, verifying that the conditions are satisfied in some real-world data would massively strengthen the paper. As it stands, the reviewers opinions remained mixed on the significance of the results and the usefulness of the proposed condition. 
Decision: Accept (Poster)