Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families
Authors: Goutham Rajendran
Bohdan Kivva
Ming Gao
Bryon Aragam
Venue: NeurIPS 2021 Poster (2021)
Keywords: structure learning
greedy algorithms
Bregman divergence
Bregman information
exponential families

Abstract: Greedy algorithms have long been a workhorse for learning graphical models, and more broadly for learning statistical models with sparse structure. In the context of learning directed acyclic graphs, greedy algorithms are popular despite their worst-case exponential runtime. In practice, however, they are very efficient. We provide new insight into this phenomenon by studying a general greedy score-based algorithm for learning DAGs. Unlike edge-greedy algorithms such as the popular GES and hill-climbing algorithms, our approach is vertex-greedy and requires at most a polynomial number of score evaluations. We then show how recent polynomial-time algorithms for learning DAG models are a special case of this algorithm, thereby illustrating how these order-based algorithms can be rigourously interpreted as score-based algorithms. This observation suggests new score functions and optimality conditions based on the duality between Bregman divergences and exponential families, which we explore in detail. Explicit sample and computational complexity bounds are derived. Finally, we provide extensive experiments suggesting that this algorithm indeed optimizes the score in a variety of settings.

Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families
Goutham Rajendran University of Chicago goutham@uchicago.. edu
Bohdan Kivva University of Chicago bkivwa@uchicago... edu
Ming Gao University of Chicago
minggao@uchi.cago. edu
Bryon Aragam University of Chicago bryon@cch.cagobooth. edu
Abstract
Greedy algorithms have long been a workhorse for learning graphical models, and more broadly for learning statistical models with sparse structure. In the context of learning directed acyclic graphs, greedy algorithms are popular despite their worst-case exponential runtime. In practice, however, they are very efficient. We provide new insight into this phenomenon by studying general greedy score- based algorithm for learning DAGs. Unlike edge-greedy algorithms such as the popular GES and hill-climbing algorithms, our approach is vertex-greedy and requires at most a polynomial number of score evaluations. We then show how recent polynomial-time algorithms for learning DAG models this algorithm, thereby illustrating how these order-based algorithms can be rigorously interpreted score-based algorithms. This observation suggests new score functions and optimality conditions based on the duality between Bregman divergences and exponential families, which explore in detail. Explicit sample and computational complexity bounds are derived. Finally, we provide extensive experiments suggesting that this algorithm indeed optimizes the score in variety of settings.
special case
Introduction
Learning the structure of a graphical model from data is notoriously difficult combinatorial problem with numerous applications in machine learning, artificial intelligence, and causal inference as well scientific disciplines such genetics, medicine, and physics. Owing to its combinatorial structure, greedy algorithms have proved popular and efficient in practice. For undirected graphical models (e.g. Ising, Gaussian) in particular, strong statistical and computational guarantees exist for variety of greedy algorithms (7 (28). These algorithms are based on the now well-known backwrd
greedy algorithm 229 57], which has been applied range of problems beyond graphical models multi-task learning 522, and atomic norm regularization
including regression
Historically, the use of the basic hewaad-backwart greedy scheme for learning directed acyclic graphical (DAG) models predates some of this work, dating back the classical greedy equivalence search [GES, [3] algorithm. Since its introduction, GES has become gold-standard for learning DAGs, and known to be asymptotically consistent under certain assumptions such as faithfulness and score consistency B3 34 Both of these assumptions are known to hold for certain parametric families (21). however, extending GES to distribution-fin -ree settings has proven difficult. Furthermore,
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

although GES is in practice extremely efficient and has been scaled up to large problem sizes 4 lacks polynomial-tin time guarantees. An important problem in this direction the development of provably polynomial-time, consistent algorithms for DAG learning in general settings.
In this paper, we revisit greedy algorithms for learning DAGs with eye towards these issues. We propose a greedy algorithm for this problem-distinet from GES-and study its computational and statistical properties. In particular, it requires at most a polynomial number of score evaluations and provably recovers the correct DAG for properly chosen score functions. Furthermore, we illustrate its intimate relationship with existing order- basee algorithms, providing link between these existing approaches and classical score-basee approaches, Along the way, we will see how the analysis itself suggests a family of score functions based on the Bregman information [5], which are well-defined without specific distributional assumptions.
Contributions At a high-level. our goal is to understand what kind of Enite-sample and complexity guarantees can be provided for greedy score-based algorithms in general settings. In doing so, we aim to provide deeper insight into the relationships between existing algorithms. Our main contributions can thus be outlined as follows:
A generic greedy barward-bacwwand scheme for optimizing score functions defined over DAGs. Unlike existing algorithm is vertex- vertex-greedy, greedy, i.c. it greedily adds vertices in a topological sort.
algorithms that greedily add or remove edges, our
We show how several existing order-based algorithms from the literature are special cases of this algorithm, for properly defined score functions. Thus, we bring these approaches back under the umbrella of score-based algorithms.
We introduce a new family of score functions derived from the Bregman information, and analyze the sample and computational complexity of our greedy algorithm for this family of scores.
We explore the optimization landscape of the resulting score functions, and provide evidence that not only does our algorithm provably recover the true DAG, does so by globally optimizing score function.
The last claim is intriguing: It suggests that it is possible to globally optimize certain Bayesian network scores in polynomial-time In other words, despite the well-known fact that global optimization of Bayesian networks scoring functions is NP-hard [2] [4], there may be natural assumptions under which these hardness results can be circumvented. This is precisely the case, for example, for undirected graphs: In general, learning Markov random fields is NP-hard [50], but special cases
such as Gaussian graphical models 6 33 and Ising models [8 31 551 can be learned efficiently. Nonetheless, we emphasize that these results on global optimization of the score are merely empirical, and a proof of this fact beyond the linear case remains out of reach.
Previous work The literature on BNSL is vast, so we focus this review on related work involving score-based and greedy algorithms. For broad overview of BNSL algorithms, see the recent survey (24] or the textbooks [42 49.. The current work is closely related to and inspired by generic greedy
algorithms such as 297 44 52 [57. Existing greedy algorithms for score-based learning include GES 13,. hill climbing I1 51), and A search [56]. In contrast to these greedy algorithms are global algorithms that are guaranteed to find a global optimum such as integer programming [66] I7 and dynamic programming (36] 46 47). Another family of order-based a algorithms dating back to [5 centers around the idea of order search- -.c. first searching for a topological sort-from which the DAG structure is casily deduced; see also B 4
9 45 54]. Recently, a series of brder-based algorithms have led to significant breakthroughs, most notable of which are finite-sample and strong It will turn out that many of these algorithms special cases of the greedy algorithm we propose; we revisit this interesting topic in Section 3.1
nolynomial-time guarantees [10 19
22
23
38
2 Background
Let X (Xi....;aa) be a random vector with distribution D. The goal of structure learning is to find a DAG W = (V, E), also called a Bayesian network (BN), for the joint distribution D. Traditionally, there have been two dominant approaches to Bayesian network structure learning
2

---

(BNSL): Constraint-basee based and score- score-based based. In constraint based algorithms such as the PC 48 and MMPC [53] algorithms, tests of conditional independence are used to identify the structure of DAG via exploitation of d-separation in DAG models. Score-based algorithms such as GES [3] define an objective function over DAGs such as the likelihood or a Bayesian posterior, and seek to optimize this score.
To formalize this, denote the space of DAGs on nodes by DAG and let S DAG + IR be a score function. Intuitively, S assigns to each DAG W a "score" S(W) that evaluates the fit between W and D. In the sequel, we assume without loss of generality that the goal to minimize the score:
min S(W).
WEDAG
Although this is an NP-hard combinatorial optimization problem, we can ask whether or not it is possible to design score functions S which can be optimized efficiently, and whose minimizers are close to W. In order for this problem to be well-posed, there must be a unique W that we seek; namely, W must be identifiable from D. The problem of identifiability will be taken up further in Section 4 where it will be connected to the choice of score function. For now, our primary interest is solving the problem ④T.
Regarding score-based learning, we highlight a subtle point: Recovering the true DAG is not necessarily the same minimizing the score function, for instance, see Example 1 in 30) Score- based algorithms in general attempt to learn the true model by way of minimizing the score but it's possible that the graph which minimizes the score could be different from the true model. In other words, the score may not always be properly calibrated to the model. This is a well-studied problem, see e.g. [20 21 26), and it is fascinating and important open problem to better understand under what assumptions a score minimizer is also the true DAG in nonparametric settings.
Exact algorithms Solving problem (1) exactly ("exact" meaning genuine global minimizer of
① is returned) is known to be NP-hard [1 [4] Some of the earliest exact methods for score-based learning relied on the following basic idea 335 39
46 47]: Use dynamic programming to search for optimal sinks W, remove these sinks, and recursively find optimal sinks in the resulting subgraph. In doing so, a topological sort of W can be learned, and from this sort, the optimal DAG can be easily learned. In other words, once the topological sort is known, finding the corresponding DAG is relatively easy. In the sequel. we refer to the problem of finding the topological sort of W as order search. Unfortunately, searching for optimal sinks involves computing d2d-1 local scores, which is both time and memory intensive.
Poly-time algorithms Recently, a new family of algorithms based on applying the idea of order
search has led to significant breakthroughs in our understanding of this problem [10 19 22 23 38). Most notably, unlike the exact algorithms described above, these algorithms run in polynomial-time The key distinction between these algorithms and exact algorithms is the clever exploitation of specific distributional (e.g. moments) or structural properties (e.g. linearity) of DD and as a result do not optimize a specific score function. In contrast, exact algorithms apply to any score S, and do not require any distributional assumptions.
Motivation It is tempting to want draw connections between exact algorithms and poly-time algorithms: After all, they both rely on the same fundamental principle of order search. In this paper, we explore this connection from the perspective of greedy optimization. In particular, we will show how existing polynomial-tin -time algorithms are special cases of a generic greedy forward-ber backward search algorithm for solving (T) under specific choices of S, and show how this leads new insights for this problem. We do not prove that this algorithm exactly solves ( (save for the exceptional case of linear models; see Corollary 3.2). however, we provide empirical evidence to support this idea on variety of linear and nonlinear models in Section 6 Since the score- based learning problem is NP-hard, this of course not possible without additional assumptions.
Notation Let be the number of samples we observe. Each sample is vector of the form X (X,...., Xx) on d variables. this paper, W used for DAGs and the vertex set is [d] = (1,2...., d}. Naturally, we match vertex i to the variable X; We denote the set of parents of a vertex with (i), dropping the subscript when it's clear from context. We will also abuse notation and use W for the adjacency matrix of the graph W as well. Let W(O denote the ith column
3

---

Algorithm 1: Greedy
Search
Input: Dataset X, tolerance parameter
Output: DAG W
W = / n-vertex graph with no edges
2 === /// The ordering
// Forward phase
3 for iter = 1 to do
i == arg min S((er) S/(r)/// Minimize jump in score
W = W[ +1] T.append(1)
// Backward phase for edge e. in W do
SWW -) S(W) 7 then
W = W Delete the edge e
10 return W// Guaranteed to be a DAG
of W, whose nonzero entries are precisely at the set of parents of vertex i. Let W k] denote the (j. le) k)th entry of the matrix.
3 The GFBS algorithm
In this section, we will describe the greedy algorithm in general framework. In subsequent sections, we will specialize particular models or scores, as necessary. Throughout, we S be an arbitrary decomposable score. That is, S(W) Eise (W())) for functions S; an example of which would be the least-squares loss. All the score functions study in the sequel will have this property.
For set of vertices T, let er denote the indicator vector of T. For an edge e of W, denote by W-e the matrix W with the entry corresponding to zeroed out. For any set of vertices J and vertex & J. denote by W[J + E] the matrix W where the ith column W(() is replaced by the indicator vector of J. That is,
W k]
if + if k = i and J if k: and E
W
(f, otherwise,
W [1
W[J - A]
In Algorithm|] [ we outline general framework based on greedy forward-back backward search to learn DAG W by attempting to minimize the score S(W). For now, we focus the algorithm itself, and defer discussions of its soundness to Sections 4 S We denote this algorithm by GFBS for short. Crucially, in contrast traditional greedy algorithms for structure learning, GFBS is vertex-greedy: Instead of greedily adding edges to W. GFBS greedily adds vertices to first build up a topological sort T of W. Specifically, Line 4 in the algorithm greedily finds the next vertex i add to the ordering, by comparing the score changes if we set the parents to be the vertices already in the ordering. Conceptually, this step is one of the most important differences from GES which adds edges one at time. We make this distinction clear in Appendix A
It is worth emphasizing that the output of GFBS is guaranteed be DAG. The backward phase standard greedy optimization, e.g. Greedy Equivalence Search (GES), and serves to eliminate unnecessary edges. In practice, in the backward phase, could also process the edges in batches. As we explore in Section 5 in certain cases, this allows us to prove sample complexity upper bounds.
Computational complexity The rumning time of GFBS is polynomial in d and the time needed to compute the scores S,(.). More specifically, GFBS requires (dd)) score evaluations (compared to (d2d)) for exact algorithms). Evidently, key computational concern the score in the first place. For many models such as linear, generalized linear, and exponential family models, this computation can carried out in poly( d) time, which implies that GFBS on the whole runs in polynomial time. For nonparametric models, this computation may longer be
complexity evaluating

---

polynomial-time time, but the total number of score evaluations is still O(d)). In particular, GFBS always enjoys an exponential speedup over exact algorithms.
Comparison to GES In the supplement (see Appendix A we exhibit linear Gaussian SEMs and illustrate how GES differs from GFBS for the least squares score as well as the traditional Gaussian BIC score. We first examine a folklore model where we show that their outputs sometimes differ. We also exhibit model where they always differ. The key takeaway is that GFBS really is distinct algorithm from GES.
3.1 Connection to equal variance SEM
An important line of work starting with [22] has shown that the assumption of equal variances in linear Gaussian SEM [40] leads directly to an efficient, order-based algorithm. A similar idea in the setting of so-called quadratic variance function (QVF) DAGs was explored in [8J. In this section, we show that the equal-variane algorithm of [10), Algorithm 1, is special case of GFBS.
Define score function as follows:
SLs(W) = Σ var(Xx paw (1)).
(2)
few comments on this score function are in order:
1. The only assumption needed on X for this score to be well-defined is that EXX" is well-defined, i.e. X; E T,2 for each i.
2. When X satisfies linear structural equation model X W X + minimizing SLS is equivalent to minimizing the least-squares loss Σ (X,- (w x)) Loh and Bühlmann 30 have shown that when cov(z) = I²I, the unique global minimizer of the least-squares loss is the so-called equal variance SEM.
3. More generally, for nonlinear models, have
SLs(W)= = min Σ E(X, (()))) 9
(3)
where .1..... Id W indicates that for each i, 9i depends only on the variables in paw (i). In other words, the minimum is taken over all functions : that respect the dependency structure implied by W. In this case, is essentially I[[;; p&w (i)].
4. We can use (3) to define an empirical score in the obvious way given i.i.d. samples. Alternatively, the residual variance E var (X; (i)( can be replaced with any estimator the residual variance.
The GFBS algorithm consists of two phases: A forward phase and a backward phase. Our claim is that the forward phase of GFBS is identical the equal-variance algorithm from (10]:
Proposition 3.1. After the forward phase, the ordering T returned by GFBS (Algorithm ( is the same as the ordering returned by the top-down equal-variance algorithm from Chen et al. (IO).
Corollary 3.2. Assume the linear SEM X = W X + z with cov(z) = = under the score function (2). Then GFBS returns global minimizer of the problem (T.
Proposition will immediately follow from a more general statement which we prove in Theo- rem 4.6 An intriguing question is to what extent this observation extends to nonlinear models such as additive noise models: While we do not have proof, our experiments Section 6 suggest something along these lines is true.
4 Bregman scores and identifiability via Bregman information
Motivated by the connection between GFBS, global optimality, and the least squares loss, this section we establish nice connection between the greedy algorithm and exponential families via the well-known duality between Bregman divergences and partition functions in exponential families [5)
This can then be used to prove identifiability and recovery guarantees for GFBS.
5

---

Bregman divergences and information Let : R + R be a strietly convex, differentiable function. y)d be the Bregman divergence associated with é and let be the associated Bregman information. The Bregman-divergence is general notion of distance that generalizes squared Fuclidean distance, logistic loss, Itakuro-Saito distance, Kl--divergence, Mahalanobis distance and generalized I-divergences, among others [3]. The Bregman-informatioon of a distribution is a measure of randomness the distribution, that's 's associated with Φ Among others, it generalizes the variance, the mutual-information and the Jensen-Shanme divergence of Gaussian processes [3]. See Appendix [B for brief review this material and a basic treatment of Legendre duality, which will be used in the next section.
Let (z y) = 00x)) -(y)
(a(D) = BR (
4.1 Bregman score functions, duality, and exponential families
By replacing the least squares loss in ① with a Bregman divergence dø, we obtain the following score function, which we call a Bregman score:
SW Σ Bxdo(X, |[X paw (1))
Σ min Exda (X (X (paw (f))
(4)
Before we study the behaviour of GFBS on Bregman scores, it is worth taking a moment to interpret this score function. To accomplish this, let define the notion of an exponential random family DAG:
Definition 4.1. A DAG W and a distribution D define an exponential random family (ERF) DAG if (a) D is Markov with respect W, and (b) The local conditional probabilities come from exponential family, iee P(X; (t)) ~ ERF(g; vii), where the is the log- oog-partiiion function of an exponential family with mean function 9: (paw(1))
Since (gF the) parametrizes a conditional distribution, its mean parameter gi is a function instead of vector, which explains our choice of notation. By the Markov property, any choice of local exponential family ERF(g,, thi gives well-defined joint distribution. The following lemma makes explicit the relationship between Bregman scores, exponential family DAGs, and the Bregman information. Let ø² denote the Legendre dual of Φ.
Lemma 4.2. Let @ strictly convex, differentiable function and let vb == &² Then
So(W)= Σ Bila(Xi paw (i)) = - idd
- Ex log Pn paw (i)) - C(X)
(5)
where C(X) depends only X and not the underlying DAG W and Pg.. is the density of an ERF(g, 4) model.
The proof of this lemma, which can be found in Appendix C follows from the well-known correspon- dence between Bregman divergences and exponential families, given by the dual map & -> d": Given Bregman divergence o, there is a corresponding exponential family whose log-partition function is given by o 5 and vice versa.
Importantly, Lemma shows that the Bregman score S₃ is equivalent to the expected negative log-likelihoon of an exponential family DAG whose local conditional probabilities all have the same log-partition function v.. This means that minimizing the Bregman score can be naturally associated to maximizing the expected log likelihood of such model. Similar observations had also been made and used in prior works on PCA (15), clustering (5] and learning theory (18).
4.2 Identifiability via Bregman information
Motivated by the connection between exponential family DAGs with the same local log- sag-partttion maps, in this section, we state our main assumption that generalizes the equal variance assumptions from prior works.
First, we will need a mild assumption on W that's of similar flavor to causal minimality, but with respect the Bregman-information in the graph W,
are looking Denote Aw (i) be the non-descendants of
Assumption 4.3. For all i S d and all subsets Y C Aw such that pa(i) g Y, EX,(( (X, pa())))

---

This assumption essentially asserts that no edge in W is superfluous with respect to the distribution on X. Now, we state our main assumption.
Assumption 4.4 (Equal Bregman-information upon conditioning). Assume that for constant 7 > 0,
(X, pa())) = E.. (X., = w)] = T for all S n
where pa(i) are the parents of in the underlying DAG W.
Example 4.5 (Special case of ANMs). Suppose we are working with an ANM. That is, there is DAG W such that for all i S d, X = Ii (pa(i)) + e for some function Jú where e, are jointly independent noise variables. Then, the above assumption says that there is a constant T 2 0 such that for all i, Ta(e)) =. When (f(x)) x²2 this is the well-known equal variance assumption.
We are now ready state our main theorem.
Theorem 4.6. Consider a model satisfying Assumption 4.3 and Assumption 4.4
Under the Bregman
score (W),), the GFBS algorithm with tolerance parameter y will output the true model.
As stated, the theorem holds for the population setting. The case of finite samples is studied in detail in Section 5 where we prove the same result given sufficient samples.
Corollary 4.7. model satisfying Assumption and the Equal Bregman-information Assump- tion 4.4 is identifiable.
We defer the proof of the main theorem to the supplement, where prove it for an more general class functionals that subsume the Bregman-information information. Here, we make the following remarks regarding this proof.
The proof is actually shown for general functionals for which "conditioning drops value". Therefore, we don't 't need to only work with with many uncertainty measures of distributions that have this property. This is useful, for example, to show that non- Non-Bregman-typ models such the QVF model from [8 are identifiable using our framework. As result, Theorem 4.6 subsumes several known identifiability results such EQVAR [TO 40), NPVAR [19], QVF-ODS (8), and GHD 37 See Appendix[Djes for details.
informaaiion and we can instead work
2. A similar proof could be adapted for other functionals of distributions that measure the randomness or uncertainty of the distribution. One class of examples could be generalized entropies [ such as the Shannon entropy, Rényi entropy the Tsallis entropy. We leave this for future work.
Remark 4.8. An important reason why our algorithm is efficient is because line of Algorithm 7 we only compute single score for each vertex not in the ordering far This works especially nicely with the Bregman score, precisely because conditioning with respect to more variables only lowers the Bregman information of a variable, is exploited to prove the theorems above.
natural score function for -an-maraettric multiplicative models We study multiplicative noise models of the form X; (pa(i))e, from the perspective of the framework built so far. Examples of such models include growth models from economics and biology [32]. More specifically, we choose ((x) = log for which the Bregman divergence de is the Itakuro-Saine distance commonly used in the Signal and Speech processing community. The associated Bregman score is the Itakuro-Saito score given by
Sw(W) Σ log E[X, pa(i) Eloog X.)).
Interestingly, the equal rregman-informatie assumption reduces purely to assumption about the noise variables, akin to the equal variance assumption in the case of additive noise models. This suggests that for multiplicative models, the Itakuro-Saito score is naturally motivated from the perspective of identifiability. This gives a new insight into the applicability of score-based learning for multiplicative models, with theoretical foundations in our analysis. For details, see Appendix
5 Sample complexity
To derive a sample complexity bound for GFBS, we first need to compute the Bregman score Sg: due to decomposability and (5) this reduces to estimating the Bregman information Ig- Let the
7

---

samples be denoted (x19) _ x for / = ...,...,, Denote the Bregman information of X; conditioning on a set A with conditional mean plugged in as (after some calculation)
.....
n.
S(x; A) == (X A)] [x(())) (
(6)
for some strictly convex, differentiable function Φ. To estimate this quantity, first apply nonparametric regression to estimate feA = [(X; A) and then take the sample mean:
1 Σ ( E (Fia(A))) T1
S(X. |)
To show convergence rate of this estimator, we will need some some regularity conditions on fLa and σ. These assumptions standard in the nonparametric statistics literature, e.g., [25] Chapters 1, 31. First, we recall the definition of the Hölder class of functions:
Definition 5.1. For any (ri,-.. ra), Ti N, let |r| Eir and D
8rrl du, " ...88
The
Hölder class E(8, L) is the set of functions satisfying
D f(x) f(w) S -
for all r such that [r| S and v. TR...
Assumption 5.2. Suppose for all and ancestor sets A of Sia E El8, L). And suppose Φ (X;),
(((A) and (SAA) all have finite second moments.
Denote Aw(i) to be the non-descendants of in graph W, then the following lemma says that have a uniform estimator for the Bregman score:
Lemma 5.3. Suppose the Bregman score and the conditional expectations satisfy Assumption 5.2
Using the estimator defined in ① yields
P (IS(X:1A) -5x,)))-(XX,)) A) S
8
min kE(d),AAAw())
where 63 C(n Tr + n 1n for some constant C.
Using this estimator, we can bound the sample complexity of the forward pass of GFBS as follows: Theorem 5,4 (Forward phase of GFBS), Suppose the BN satisfies the identifiability condition in Theorem 4.6 and assumptions in Lemma 5.3 denote the gap
A min
A) -
iE|d] A. Aew (6)
pa
Let the ordering returned by the first phase of GFBS to be (f1, ... Rd)) If the sample size
2etd v1
d
A
then P( is valid ordering) 2 21c.
The causal minimality Assumption 4.3 is equivalent to stating A > 0. Theorem 5.4 shows that A in fact controls the hardness of the estimation, which is the gap between the minimum Bregman information when all parents are conditioned on and when some parents are missing.
In this section, to obtain strong bounds on sample complexity, we modify the backward phase of GFBS be as follows:
Definition 5.5. Let Ao and for 1, Ā, ( 1.2, For each F5tt,, we find its parents from Ag in the following way, estimate S(X [A)) and S(X A i) for E Az. Then, set
pa( (a(m)+1)= = Ag ( 1(X A,) - S(K 11)0)
(8)
8

---

This says that we keep an edge (i, +)++) depending on its influence on the local score at the vertex g-+1- If the influence is low, then we discard that edge. For our analysis work, we process these low-influence edges in batches grouped according to the vertices they are oriented towards. In contrast, Algorithm|| did not batch the edges and simply processed them one at time.
Theorem 5.6 (Backward phase of GFBS). Suppose the same conditions and sample size in Theo- rem 5. holds, using the backward phase defined in (8) with 7 = A guarantees P(W W) 2 1-c.
Proofs can be found in Appendix in the supplement.
6 Experiments
We conduct experiments to show the performance of GFBS on optimizing the Bregman score. We compare GFBS with existing score-based DAG learning algorithms: Gobnilp (16], NOTEARS (59), and GDS [40]. The implementation of these algorithms and data generating process are detailed in Appendix H Although previous works have evaluated the structure learning performance of special cases of GFBS such as equal variances, we also include these comparisons in the appendix for completeness. Also, in Appendix G we investigate the performance of GFBS on models which violate the identifiability Assumption 4.4
Choice of (b. To show the generality of the Bregman score 4 we investigate two convex functions to define the score: di (2:) x²2 and (x)) = log x. They correspond to sum of residual variances and sum of residual Itakuro-Saito (IS) distances respectively.
Graph rype. We generate three types of graphs: Markov chains (MC), Erdös-Reds Rényí (ER) graphs. Scale-Free (SF) graphs with different expected number of edges. We let the expected number of edges scale with d, e.g. ER-2 stands for Erdös-Rényi with 2d edges.
Model type. We simulate the data as X, f<(a(t)) + Z, or X; = fi(p((t)) x Z₁ for different Ø's, where Zi is independently sampled from some distribution such that Assumption 4.4Jis satisfied. Then we consider the following forms of the parental functions f;: linear (LIN), sine (SIN), additive Gaussian process (AGP), and non-additive Gaussian process (NGP).
The main objective of these experiments is to evaluate the performance of these algorithms in optimizing the score: For this, it is necessary to compute the globally optimal score as benchmark, which computationally intensive.
a result, our experiments are restricted to 5. We use Gobnilp [66 to compute the global minimizer. The results are shown in Figure [ As expected, GFBS returns a near-globally optimal solution in most cases when the sample size large. Due to finite-sample errors, in some cases (notably on the IS score), GFBS returns a slightly higher score due to the backward phase, which allows the score to increase slightly in favour of sparser solutions. At a technical level, the issue is that the score does not distinguish I-maps from minimal I-maps, and this is exacerbated on finite samples. Better regularization and parameter tuning should resolve this, which we leave to future work. Nonetheless, the close alignment between GFBS and the globally optimal score suggest that GFBS and hence the equal variance algorithm is truly minimizing the score.
7 Discussion
We introduced the generic GFBS (Greedy Forward-Backward Search) algorithm for score-based DAG learning. It enjoys the guarantees of always outputting a DAG and running in time polynomial in the input size and the time required to compute the score function. We also showed statistical and sample complexity bounds for this algorithm for the generic Bregman score. We motivate this score by formally connecting it to the negative log- ligliiilloood for all exponential DAG models, and considering the well-known approximation capabilities of exponential families, we expect that the Bregman score and our theoretical results apply to a wide variety of settings. In particular, the Bregman score generalizes the least squares score. For least-squares score, our sample complexity results unify and match or improve existing results such as [10 19 22 For generic Bregman scores, no sample complexity results were known prior to this work to the best of our knowledge and we provide the first such results.

---

Brogman Information score
UN 600) wad
SIN =00
AGP 4x0
NGP -xx SIN 4100 -log00
AGP (xl -logor
NGP e000 log00)
200
1200
1200 2088
2800
2008
Figure 1: Score of output DAG vs. sample size for GFBS and other algorithms. Left four columns: é (z) = x² and Z: is I-distribution with variance 1; Right three columns: Φ2(x) = log(2) and Z, is uniform distribution in [1, 2]. The two sets of columns have different Y-axis scales. The grey dashed line is the score the true graph.
The GFBS algorithm also generalizes several prior works on greedy order-based algorithms for DAG learning, e.g., [10] 19 37 38). Existing score-based greedy algorithms (such as GES or hill climbing) edge-based, whereas these recent order-based algorithms are vertex-based. GFBS shows that each of these prior works can be re- re-interpreted as score- based-baeddd- greedy algorithms, each of which optimizes different score. This brings them back under the umbrella of score based learning. In our statistical guarantees, our assumptions generalize the equal variance assumption that has been studied in the literature the last decade. Moreover, as a byproduct our work, we also propose new score function, the Itakuro-Saito score, for multiplicative SEM models and we leave it to future work to further explore the properties of this score function.
For other future work, it would be insightful to compare Assumption 4.3 to the standard notions such causal minimality. Moreover, our experiments suggest that the various assumptions we make not strictly necessary, so an interesting future direction is to study weaker conditions under which GFBS globally optimizes the score.
Broader impacts
Learning graphical models has important applications in causal inference, which is useful for mitigating bias in ML models. At the same time, causal models be easily misinterpreted and provide false sense of security, especially when they are subject to finite-sample errors. One additional potential negative impact from this line of work the environmental cost of training large causal models, which can be expensive and time-consuming.
Acknowledgements
We thank anonymous reviewers for their helpful comments in improving the manuscript. G.R. was partially supported by NSF grant CCF-1816377 B.K. was partially supported by advisor László Babai's NSF grant CCF 1718902. B.A. was supported by NSF IIS 1956330,330, NIH R016M140467. and the Robert H. Topel Faculty Research Fund at the University of Chicago Booth School of Business, All statements made solely due the authors and have not been endorsed by the NSF
10

---

References
[1] Amari. Information geometry of the em and em algorithms for neural networks. Neural networks, 8(9):1379-140$ 1995.
[2] J. M. Amigó, S. G. Balogh, and S. Hernández. A brief review of generalized entropies. Entropy, 20(11):813, 2018.
[3] B. Aragam, A. A. Amini, and Q. Zhou. Learning directed acyelic graphs with penalized neighbourhood regression. urXiv:1510 151.0663,,, 2015.
[4] B. Aragam, A. Amini, and Q. Zhou. Globally optimal score-based learning of directed acyclic graphs in high-dimensions. 2019.
[5] A. Banerjee, Merugu, I. S. Dhillon, Ghosh, and J. Lafferty. Clustering with bregman divergences. Journal of machine learning research, 6(10), 2005.
[6] O. Banerjee, L. El Ghaoui, and A. d' Aspremont. Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data. Journal of Machine Learning Research, 9:485-511 2008
[7] O. BarndorffNNelsen. Information and exponential families: in statistical theory. John Wiley Sons, 2014.
[8] G. Bresler. Efficiently learning ising models on arbitrary graphs. Proceedings of the serty-seventh annual ACM symposium on Theory of computing, pages 771-782, 2015.
[9] P. Bühlmann, J. Peters, and J. Ernest. CAM: Causal additive models. high-dimensional order search and penalized regression. Annals of Statistics, 42(6))2526-2556, 2014.
[10] 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. 10.1093/biomet/a20449
(11) D. Chickering, D. Geiger, and D. Heckerman. Learning bayesian networks: Search methods and experimental results. In proceedings fifth conference on artificial intelligence and statistics, pages 112-128, 1995.
[12] D. M. Chickering. Learning Bayesian networks is NP-complete. In Learning from data, pages 121-130. Springer, 1996.
[13] D. M. Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3:507-554, 2003.
[14] D. M. Chickering, D. Heckerman, and C. Meek. Large-sample learning of Bayesian networks NP-hard. Journal of Machine Learning Research, 5: 5:17771330, 2004.
[15] M. Collins, S. Dasgupta, and R. E. Schapire. A generalization of principal components analysis to the exponential family. In Nips, volume 13, page 23, 2001.
[16] J. Cussens. Bayesian network learning with cutting planes. arXiv preprint arXiv:1202.3713, 2012.
[17] Cussens, D. Haws, and M. Studený. Polyhedral aspects of score equivalence bayesian network structure learning. Mathematical Programming, 164(1-2):285-324 2017.
[18] J. Forster and M. K. Warmuth. Relative expected instantaneous loss bounds. Journal of Computer and System Sciences, 64(1):76-102, 2002.
[19] M. Gao, Ding, and B. Aragam. A polynomial-time algorithm for learning nonparametric causal graphs. arXiv preprint arXiv:2006. 1970, 2020.
[20] D. Geiger and D. Heckerman. Parameter priors for directed acyclic graphical models and the characterization of several probability distributions. Annals of Statistics, 30: 1412-1440, 2002.
[21] D. Geiger, Heckerman, H. King, and C. Meek. Stratified exponential families: Graphical models and model selection. Annals of Statistics, pages 505-529, 2001.

---

[22] A. Ghoshal and J. Honorio. Learning identifiable gaussian bayesian networks in polynomial time and sample complexity. In Advances in Neural Information Processing Systems 30, pages 6457-6466. 2017.
[23] A. Ghoshal and J. Honorio. Learning linear structural equation models in polynomial time and sample complexity. In A. Storkey and F. Perez- Cruz, editors, Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1466-1475, Playa Blanca, Lanzarote, Canary Islands, 09-11 Apr 2018. PMLR.
[24] C. Glymour, K. Zhang, and P. Spirtes. Review of causal discovery methods based on graphical models. Frontiers in genetics, 10:524, 2019.
[25] L. Györfi, M. Kohler, A. Krzyżak, and H. Walk. A distribution-free theory of nonparametric regression, volume 1. Springer, 2002.
[26] D. Heckerman, D. Geiger, and M. Chickering. Learning Bayesian networks: The combination of knowledge and statistical data. Machine learning, 20(3):197-243, 1995.
[27] A. Jalali, C. Johnson, and P. Ravikumar. On learning discrete graphical models using greedy methods. arXiv preprint arXiv:1107.3258, 2011.
[28] C. Johnson, A. Jalali, and P. Ravikumar. High-dimensional sparse inverse covariance estimation using greedy methods. In Artificial Intelligence and Statistics, pages 574-582. PMLR, 2012.
[29] Liu, J. Ye, and R. Fujimaki. newardd-bccwaar greedy algorithms for general convex smooth functions over a cardinality constraint. In International Conference on Machine Learning, pages 503-511, PMLR, 2014.
[30] P.-L. Loh and P. Bühlmann. High-dimensional learning of linear causal networks via inverse covariance estimation. Journal of Machine Learning Research, 15:3065-3105, 2014.
[31] A. Y. Lokhov, M. Vuffray, S. Misra, and M. Chertkov. Optimal structure and parameter learning of ising models. Science advances, 4(3)e1 2018.
[32] A. W. Marshall and I. Olkin. Life distributions, volume 13. Springer, 2007.
[33] S. Misra, M. Vuffray, and A. Y. Lokhov. Information theoretic optimal learning of gaussian graphical models. In Conference on Learning Theory, pages 2888-2909 PMLR, 2020.
[34] Nandy, A. Hauser, and M. H. Maathuis. High-dimensional consistency in score-based and hybrid structure learning, arXiv preprint arXiv: 2018.
[35] S. Ott and S. Miyano. Finding optimal gene networks using biological constraints. Genome Informatics, 14:124-133, 2003.
[36] S. Out, S. Imoto, and S. Miyano. Finding optimal models for small gene networks. In Pacific symposium on biocomputing, volume 9, pages 557-567. Citeseer, 2004.
[37] G. Park and H. Park. Identifiability of generalized hypergeometric distribution (ghd) directed acyclic graphical models. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 158- 166. PMLR, 2019.
[38] G. Park and G. Raskutti. Learning quadratic variance function (QVF) dag models via overdis- persion scoring (ODS). The Journal of Machine Learning Research, (8(1):8300-8422 2017.
[39] E. Perrier, S. Imoto, and S. Miyano. Finding optimal bayesian network given super-structure. Journal of Machine Learning Research, (0ct): 12286,, 2008
[40] J. Peters and P. Bühlmann. Identifiability of Gaussian structural equation models with equal error variances. Biometrika, 101(1):21--22,, 2013.
[41] Peters and P. Bühlmann. Identifiability of gaussian structural equation models with equal error variances. Biometrika, 101(1):219-22) 2014.
12

---

[42] J. Peters, D. Janzing, and B. Schölkopf. Elements of causal inference: foundations and learning algorithmm. MIT press, 2017.
[43] Ramsey, M. Glymour, R. 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, pages 1-9, 2016.
[44] N. Rao, P. Shah, and S. Wright. regularization. IEEE Transactions on Signal Processing, 63(21):5798-5811 2015.
greedy algorithms for atomic norm
[45] G. Raskutti and C. Uhler. Learning directed acyclic graph models based on sparsest permutations. Stat, 7(1), 2018
[46] Silander and Myllymaki. simple approach for finding the globally optimal bayesian net- work structure. In Proceedings of the 22nd Conference Uncertainty in Artificial Intelligence, 2006.
[47] A. P. Singh and A. Moore. Finding optimal bayesian networks by dynamic programming. 2005.
[48] Spirtes and C. Glymour. An algorithm for fast recovery of sparse causal graphs. Social Science Computer Review, (1):62272, 1991.
[49] P. Spirtes, C. Glymour, and R. Scheines. Causation, prediction, and search, volume 81. The MIT Press, 2000.
[50] N. Srebro. Maximum likelihood bounded tree-width markov networks. Artificial intelligence, 143(1):123-138, 2003.
[51] M. Teyssier and D. Koller. Ordering- based search: A simple and effective algorithm for learning bayesian networks. In Uncertainty in Artifical Intelligence (UAI), 2005.
[52] L. Tian, P. Xu, and Q. Gu. Forward backward greedy algorithms for multi-task learning with faster rates. In UAI, 2016.
[53] I. Tsamardinos, E. Brown, and F. Aliferis. The max-min hill-climbing Bayesian network structure learning algorithm. Machine Learning, 65(1):31-78 2006.
[54] S. van de Geer and P. Bühlmann. lo- fo-penalized maximum likelihood for sparse directed acyclic graphs. Annals of Statistics, 41(2):536-567, 2013.
[55] M. Vuffray, S. Misra, A. Y. Lokhov, and M. Chertkov. Interaction screening: Efficient and sample-optimal learning of ising models. arXiv preprint arXiv:1605.07252, 2016.
[56] C. Yuan and B. Malone. Learning optimal Bayesian networks: A shortest path perspective. J. Artif. Intell. (JA.(J,IR), 48:23-65, 2013.
[57] T. Zhang, Adaptive forward-backward greedy algorithm for sparse learning with linear models. Advances in Neural Information Processing Systems, 21:1921-1922 2008.
[58] X. Zheng, B. Aragam, Ravikumar, and E. Xing. Dags with no tears: Continuous optimiza- tion for structure learning. arXiv preprint arXiv: 0803001422, 2018.
[59] X. Zheng, C. Dan, B. Aragam, P. Ravikumar, and E. Xing. Learning sparse nonparametric dags. In International Conference on Artificial Intelligence and Statistics, pages 3414-3425. PMLR, 2020.
13


Reviews:
[{"review_id": "RERhCeWAeXK", "reviewer": "Reviewer_d421", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 algorithm is efficient, requires only a quadratic number of score evaluations.\n- The algorithm recovers the correct DAG for properly chosen score functions.\n- Conceptually, the proposed algorithm generalizes other order-based algorithms for structure learning.\n- The paper proves identifiability of graphical models under mild statistical assumptions.\n- The paper is well written and easy to follow.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper has a short paragraph explaining the possible societal impact, which is typical for a theory-oriented paper.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "EI8CpyR4C9j", "reviewer": "Reviewer_YN8z", "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.", "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": "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.\n\nHowever, I think the authors have to include more substantial discussions in two main areas:\n\n1) 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.\n\n2) More discussion needs to be included for the experimental results on how these models used for the experiments violate Assumption 4.4.  \n\n3) 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "AuKOQ7V8HJ", "reviewer": "Reviewer_tJvN", "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.", "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": "### Strengths\n\n+ 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)_\n\n+ The paper is well-written, the motivation, contribution, and technical details are clear. _(clarity)_\n\n### Weaknesses\n\n- The Bregman divergence and exponential family formulation in Section 4.1, including Lemma 4.2, is known. _(novelty)_\n\n### Suggestions\n\n* 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.\n\n* 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.\n\n* 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?\n\n* Typos: `line 140` _Furthermore_, `line 313` _its parents_, references [32] and [33] repeat\n\n[Edit: Thank you authors for your clarifying response.]", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors adequately discuss some limitations and impact.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "AWK63Ko6qI4", "reviewer": "Reviewer_xMq4", "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. ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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 & significance:\n\nThis 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. \n\nQuality / clarity:\n\nThe paper is clearly written and organized. \nThe algorithm is clearly presented, followed by an explanation to its connection to existing methods in literature. \nThe main part of Bregman information and score minimization is clearly stated. The theories are correct. \nThe numerical experiments are illustrative, which shows the performance of the algorithm in some examples.\n\nQuestions:\n\n1. 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. \n2. 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? \n3. 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? \n\n\n\nReference:\n[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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "7hAtO97RA_3", "reviewer": "Reviewer_vCrF", "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Unless I missed something, this paper has established that P = NP: \n* The output of GFBS is a minimizer of Problem (1), which is to find a directed acyclic graph that minimizes a scoring function $S$.\n* As stated in Lines 149-150, “The running time of GFBS is polynomial in $d$ and the time needed to compute the score $S(.)$.”\n* 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.\n* 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. \n\nBased 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.\n\n--- After Rebuttal ---\n\nI was originally confused by the fact that the output of their GFBS algorithm (see the third line of Page 4):\n\n$ \\mathrm{argmin}_{\\mathrm{DAG} W} S(W) $\n\nis 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$). \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "Not Applicable.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)