Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a score-based algorithm to recover the structure of a Bayesian network. The algorithm first constructs a topological order, by greedily adding the vertex that contributes the least to the score, with all ancestors as its parents. The algorithm then prunes the edges by thresholding the contribution of the edge relative to its absence. The overall runtime is a polynomial (in the size of the graph), times the cost of calculating a score. Theoretical results are proven generally for scores given by Bregman divergences. Under a set of assumptions, for the population case the recovery is exact and for the sample case, with a modification of the pruning stage, the recovery holds with high probability. The work is also supported by experiments.
main_review: ### Strengths

+ The problem of Bayesian network structure learning continues to be relevant, particularly invigorated by causal models. The polynomial complexity of the proposed algorithm and its relationship with topological order based algorithms make this a contribution worth sharing with the community. _(originality, significance)_

+ The paper is well-written, the motivation, contribution, and technical details are clear. _(clarity)_

### Weaknesses

- The Bregman divergence and exponential family formulation in Section 4.1, including Lemma 4.2, is known. _(novelty)_

### Suggestions

* In the algorithm, during the first stage $W$ needs to be updated too for the notation to make sense. The way I understand it, $W$ becomes $W[T\to i]$, before $T$ gets updated.

* The notation used in Definition 5.5 is following that of the proof of Theorem 5.4, but this doesn’t read well in the flow of the main text. It would be better rewritten or at least if that notation is introduced. Clearly comparing also to the original second (pruning) stage would help.

* Questions: In the identifiable case, the context of Theorem 4.6 and Corollary 4.7, I may be confused, but doesn’t the recovery of the true model imply that the score is indeed minimized? (Granted that this is under assumptions.) Is the conjecture that in more general settings, when polynomial-time recoverability is not precluded by hardness results, the proposed greedy algorithm may also be able to minimize the score? What $\Delta$ (or $\gamma$, pruning threshold) was used in the experiments, and what can one do when this is not known? How do you explain the large gap for the (SF-2, NGP) experiment?

* Typos: `line 140` _Furthermore_, `line 313` _its parents_, references [32] and [33] repeat

[Edit: Thank you authors for your clarifying response.]
limitations_and_societal_impact: Authors adequately discuss some limitations and impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper acts as a review and a generalization of existing greedy learning algorithms for DAGs, through the introduction of a score function. The paper also introduces a new score function based on Bregman information and provide sample and computational complexities for this function. They provide empirical results for this greedy algorithm in learning models that violate their main assumption, Assumption 4.4.
main_review: The strong point of this paper is that it acts a review of existing greedy techniques for learning DAGs and generalizes some of these techniques into their GFBS algorithm. I think the work on determining the sample and computational complexity is worth publishing.

However, I think the authors have to include more substantial discussions in two main areas:

1) How does the sample and computational complexity of using Bregman information as a score compare to that of other greedy techniques that fall into a specific case of the GFBS algorithm? I think this is an important area to address and if the Bregman information does improve upon the sample and computational complexity of the greedy algorithm then this enhances the introduction of a general function significantly.

2) More discussion needs to be included for the experimental results on how these models used for the experiments violate Assumption 4.4.  

3) In the section on main contributions, the authors describe their learning algorithm is vertex based, whereas existing algorithms are edge based. In the next point, they mentioned that some existing algorithms fall under the special case of their function by determining a score functions. I think these two points sound like they are at odds which each other since if the second point is true, then it needs to be discussed how many of existing algorithms are edged based or vertex based. Also, the advantages of vertex based algorithms need to be discussed.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the structure learning of graphical models over directed acyclic graphs, and proposes a two-pass greedy algorithm (Greedy Forward-Backward Search) which evaluates a score based on Bregman information to learn directed acyclic graphical models in polynomial time under mild statistical assumptions.
main_review: - The algorithm is efficient, requires only a quadratic number of score evaluations.
- The algorithm recovers the correct DAG for properly chosen score functions.
- Conceptually, the proposed algorithm generalizes other order-based algorithms for structure learning.
- The paper proves identifiability of graphical models under mild statistical assumptions.
- The paper is well written and easy to follow.

limitations_and_societal_impact: The paper has a short paragraph explaining the possible societal impact, which is typical for a theory-oriented paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper provides a conceptually simple greedy algorithm for solving the Bayesian Network Structure Learning (BNSL) problem. More precisely, the Greedy Forward-Backward Search (BFBS) algorithm is first presented for arbitrary scoring functions. Then, the paper results are refined using different scoring functions, inspired from variance measures (Section 3.1) and Bregman divergences (Sections 4 & 5). Comparative experiments are presented in Section 6.

main_review: Unless I missed something, this paper has established that P = NP: 
* The output of GFBS is a minimizer of Problem (1), which is to find a directed acyclic graph that minimizes a scoring function $S$.
* As stated in Lines 149-150, “The running time of GFBS is polynomial in $d$ and the time needed to compute the score $S(.)$.”
* Suppose that $S$ is the BDe metric with the standard assumptions considered in Chickering (1996). For any DAG $W$, $S(W)$ can be computed in time polynomial in $d$ and the size of the dataset $X$. Since the GFBS problem with the BDe metric is NP-hard, this immediately implies that P = NP.
* Alternatively, suppose that $S$ is linear, that is, for any input digraph $W$, $S(W) = \sum_{v \in V} S_v(Q_v)$, where $Q_v$ is the set of parents of $v$ and $S_v(Q) = \sum_{q \in Q} S_v(\{q})$ for all $Q \subseteq V$. Observe that $S$ can be described using a representation that is polynomial in $d$.  Then, for this additive score function, a reduction of BNSL to the Feedback Arc Set problem can be easily found, which again implies that GFBS is solving in polynomial time an NP-hard problem. 

Based on this evidence, I would suggest a strong revision of the paper. The correctness of Algorithm 1 should be checked and formally proved. If the output is not a minimizer of (1) but an approximation of it (depending on the scoring function and possibly other parameters), approximation bounds should be found. Note that the aforementioned Feedback Arc Set problem is already APX-hard.

--- After Rebuttal ---

I was originally confused by the fact that the output of their GFBS algorithm (see the third line of Page 4):

$ \mathrm{argmin}_{\mathrm{DAG} W} S(W) $

is a minimizer of Problem (1). Based on the authors’ response, GFBS is optimal (on expectation) for specific classes of cost functions that depend on some properties of the underlying data distribution (actually, $S$ should depend on $\mathcal D$). 


limitations_and_societal_impact: Broader impacts are briefly discussed at the end of Page 9. The (technical) limitations of the approach (in particular the GFBS algorithm) have not really been discussed.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies polynomial-time algorithm of DAG learning, which aims to build a connection between order-based greedy algorithm and score-based methods. A greedy algorithm that sequentially finds an order of the nodes according to a score function is proposed, which is shown to find the optimal score function under proper models. The method on equal-variance Gaussian linear model is generalized using Bregman divergence and Bregman information. Under two key assumptions, properties of the greedy algorithm are proved, which hold in a similar fashion to the variance minimization in gaussian linear model, but in a more general sense. The validity and applicability of the proposed method to several types of score functions and underlying models are evaluated. 
main_review: Originality & significance:

This paper finds connection between greedy order search algorithm and score minimization algorithms under particular model assumptions. Most of the results are generalization of the greedy algorithm for equal-variance linear DAG in [Chen et al., 2019], where the gap in variance is generalized to the gap in Bregman score. From the theoretical perspective, the results are not surprising, as they are in the similar sense to [Chen et al., 2019]. However the paper provides a more general perspective in understanding what kinds of DAG models are polynomial-time learnable. 

Quality / clarity:

The paper is clearly written and organized. 
The algorithm is clearly presented, followed by an explanation to its connection to existing methods in literature. 
The main part of Bregman information and score minimization is clearly stated. The theories are correct. 
The numerical experiments are illustrative, which shows the performance of the algorithm in some examples.

Questions:

1. It's shown that the forward pass of the algorithm is equivalent to [Chen et al., 2019] under linear gaussian DAG. The backward step is new compared to [Chen et al., 2019] but its role in the algorithm is not explained. I think it is used to eliminated unnecessary edges so that $\hat{W}=W$ with high probability, which could be elaborated a bit. 
2. The identification relies on a gap condition ($\Delta$), but the parameter in the backward step also relies on the possibly unknown constant. Is there a way to mitigate this problem? 
3. Often the DAG problem is concerned with high dimensionality. The constant gap condition $\Delta$ might not be enough for characterizing the high dimensional case when signal strength might be weak. Is it possible to have more specific considerations in the high dimensional setting? 



Reference:
[Chen et al., 2019] W. Chen, M. Drton, and Y. S. Wang. On causal discovery with an equal-variance assumption. Biometrika, 106(4):973–980, 09 2019. ISSN 0006-3444. doi: 10.1093/biomet/asz049.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This paper proposes a general greedy algorithm for score-based learning of Bayesian networks from data. The algorithm generalizes a number of prior approaches to learning such models by using a score function that is based on a sum of Bregman informations. 

The algorithm is simple and computationally efficient (assuming that the score function can be computed efficiently). It is shown to succeed under what seem like fairly restrictive assumptions which generalize to the Bregman setting the corresponding restrictive assumptions used in some prior papers. 

Thus the main strength of the paper is in its generality and unification of prior algorithms. 

The main weakness are that (1) given the restrictiveness of the assumed conditions, it would have been nice to have obtained some insight about whether these are necessary, and (2) the main contribution is in placing prior ideas in a more general setting. Thus, it is not clear what substantial new insights into the basic phenomena the current work provides. Definitively addressing either of these weaknesses is a worthwhile direction for future work. 
Decision: Accept (Poster)