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 : RR + 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-Shannol 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 Σ ( Σ (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
grrl 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 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/a2044.
(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. W. 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: /803.01422, 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": "mVrza7b4INS", "reviewer": "Reviewer_3sfT", "summary": "This paper proposes a general unifying vertex-greedy algorithm (BFGS) for solving the score-based structure learning problem over DAGs. The paper focuses on a family of scoring functions derived from Bregman information. The authors prove that under certain assumptions (4.3: Lack of superfluous edges, 4.4: Equal Bregman-information upon conditioning), the underlying DAG is identifiable using only observed data, and the proposed algorithm can identify it. The authors also give sample complexity guarantees under additional assumptions on the conditional distributions of the variables (Holder continuity and finite second moments). ", "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: The proposed algorithm seems to be a generalization of the algorithm given by Chen et. al.[5]. The arguments and assumptions generalize the idea by replacing variance with Bregman information. This allows the authors to subsume some of the new order-based methods under the general vertex-greedy algorithm. \n\nQuality: The work seems to be technically sound but the motivation behind assumption 4.3 and assumption 4.4 is not completely clear to me. It would be great if the authors could provide some justification for making the assumptions 4.3 and 4.4 for general functions $\\phi$.\n\nClarity: The paper is easy to understand and provides all the necessary technical details.\n\nSignificance: While the work finds a unifying theme for some of the existing order-based approaches, the significance of the observation is not clear to me. I would like to know a bit more about the significance of this result for future work. The authors also mention the relation between Bregman divergence and exponential families in the paper but don't explore its significance later. It would be great if they further explore this relation. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the negative societal impact of the paper.", "review_text": "", "extra_scores": {"ethical_concerns": "I did not find any ethical issues with the paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5-6"}, "extra_text": {}}, {"review_id": "hxrY7B-Wp0A", "reviewer": "Reviewer_m1Q2", "summary": "The authors propose a greedy algorithm for learning graphical model structure, based on adding nodes in a a greedy forward pass, and then removing edges in a backward pass. The nature of the algorithm ensures that it requires at most polynomial score evaluations. They compare their approach to existing approaches experimentally. They posit that their approach typically finds the optimal structure (without proof)\n", "questions": "", "limitations": "", "rating": 4, "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": "The paper is clear, and well written. But overall, I felt that this does not rise to a level of an accept for a few reasons.\n1) The algorithm itself is nice / straightforward. However, the paper does not excel in either theoretical (for eg, showing conditions under which the algorithm is indeed optimal) or experimental analysis.\n\nThe experimental concerns come down to\n1) Their algorithm (GFBS) seems to perform much better for some scoring functions ($log(x)$) than it does for others ($x^2$) (in that it seems to perform the best for the latter but not for the former) - I'm not sure I understood if there was a difference in the setup of these different bregman information scores.\n2) The evaluation was only performed on relatively small graph sizes (restricted to d = 5). And the experiments were only performed on synthetic data. While testing on synthetic data is reasonable, if the algorithm is primarly a practical one, then describing the performance on larger, real world graphs would have been nice.\n3) Given that running time/efficiency for these algorithms is important (and is highlighted in the paper), it would have been nice if the experiments also showed the running times.\n\nThe writing was on the whole pretty good, but there were some nits (for eg line 63 \"In general, learning Markov random fields is NP-hard [41], even for trees [13]\" - I believe learning undirected trees optimally is possible in polynomial queries using Chow-Liu) \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Optimal (or near optimal) structure learning has a variety of impact for learning underlying causal mechanisms, and going beyond \"curve fitting\".", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "b9v5zflKqZU", "reviewer": "Reviewer_VttL", "summary": "This paper studies the problem of learning graphical models defined on DAGs. The authors propose a general vertex-greedy score-based algorithm that requires polynomially many score evaluations.", "questions": "", "limitations": "", "rating": 8, "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": "This paper studies sample and evaluation complexity for learning DAGs using greedy score-based algorithms. The greedy algorithm presented in this paper is very general and runs with polynomial computational complexity. Previous algorithms for learning DAGs are usually edge-greedy by adding or removing edges greedily, while the algorithm in this paper is vertex-greedy which adds vertices in a topological order. This algorithm in fact generalizes known algorithms in the literature which are order-based, under a suitable choice of score functions. In this sense, the greedy algorithm proposed in this paper is universal and unify a lot of previous works. \n\nThe authors also introduce new score functions based on the Bregman information, and provide theoretical bounds on sample and computational complexity. Also, the authors give evidence that the algorithm in fact optimizes the score function globally in a lot of cases, while it is well-known that the optimization problem is hard in general. This paper is nicely written. The main contribution of this paper is theoretical. The authors provide solid and detailed proofs for their main results as well as experimental illustration. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a nice paper. As a very minor suggestion some more discussions and comparisons for other order-based algorithms would be better.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "I0596O6yUrX", "reviewer": "Reviewer_HdRs", "summary": "The paper studies the problem of learning the structure of Bayesian networks (DAGs) from fully observational data. The main contributions are:\n\n1. Authors propose a simple greedy algorithm that consists of two stages. The first stage aims to estimate the topological ordering of the DAG by greedily appending the node that minimizes a given score function. Thus, this phase is vertex-based and performs $O(d^2)$ score computations. The second stage consists of a pruning step, where edges, whose presence do not influence much the score of the structure, are deleted.\n\n2. Authors claim that *several* existing order-based algorithms are special cases of the algorithm described above. Thus, it is claimed that those methods are equivalently score-based methods.\n\n3. Authors propose the use of Bregman information as the score function for their algorithm. Using properties of this scoring function, authors derive statistical and computational guarantees for their proposed algorithm.\n\n4. Authors claim that their method recovers the ground-truth network by globally optimizing the score function, and provide experiments to support this argument.", "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": "Here I present my review along the axes from the NeurIPS reviewing guidelines. See my questions/comments at the end.\n\n**Originality**\n\n- Are the tasks or methods new? \n  - Yes. The approach of learning the BN structure in a score-based fashion is not new but the presented algorithm is. Also, while the proposed method has some similarities to existing greedy algorithms, authors show in Appendix A that their method is indeed different to edge-based greedy algorithms such as GES.\n  - The use of Bregman information as the score function and its analysis is also new to the best of my knowledge.\n\n- Is the work a novel combination of well-known techniques?\n  - The work is motivated by known approaches for learning BN structures but is not merely a combination of known techniques.\n\n- Is it clear how this work differs from previous contributions? \n  - Yes. Authors clearly state that their method is score-based, greedy, and how it differs from known greedy algorithms.\n\n- Is related work adequately cited?\n  - Yes, given the vast literature in BN structure learning. I think authors do a proper job in citing the most closest existing results.\n\n\n**Quality** \n\n- Is the submission technically sound? \n  - Yes.\n\n- Are claims well supported (e.g., by theoretical analysis or experimental results)? \n  - Yes, proofs are provided in the Appendix. Empirical evidence is also provided in Section 6.\n\n- Are the methods used appropriate? \n  - Yes.\n\n- Is this a complete piece of work or work in progress? \n  - This is a complete work.\n\n- Are the authors careful and honest about evaluating both the strengths and weaknesses of their work?\n  - More or less. There are a few statements that were confusing to me, see my comments below.\n\n\n**Clarity** \n\n- Is the submission clearly written? \n  - Mostly yes. It can be improved, see my comments below.\n\n- Is it well organized? \n  - Yes. I was able to follow the main results without issues.\n\n- Does it adequately inform the reader? \n  - Yes. E.g., experimental details are given in Appendix H.\n\n\n**Significance** \n\n- Are the results important? \n  - Yes. Learning the structure of BNs is long-standing problem in machine learning.\n\n- Are others (researchers or practitioners) likely to use the ideas or build on them? \n  - Perhaps. It might be interesting to see the performance of this method in real-world data.\n\n- Does the submission address a difficult task in a better way than previous work? \n  - Somewhat unclear. The experiments are mostly related to the scores obtained by their method and others. While that is relevant, I believe that the main experiments should be how well the method recovers the true DAG. Figures 4, 5, and 6 in the Appendix attempt to show this but the experimental setting is a bit unconvincing. See below. \n\n- Does it advance the state of the art in a demonstrable way? \n  - Unclear too. It seems that the method is competitive but more experiments are needed.\n\n- Does it provide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach?\n  - No.\n\n# Questions / Comments\n\n1. I spent some time figuring out Algorithm 1, to me, it is confusing. If this is the case, it is disappointing that the only algorithm in the paper is confusing despite being simple. At the first iteration of the forward phase, we have $T = []$ and so we are supposed to compute $\\arg\\min_{i \\in V} S(W[T \\to i])$. However, what is $W[T \\to i]$ when $T = []$? If I follow the notation, it says that no edges pointing to $i$ are added  but then for all $i \\in V$ we would have the same score $S(\\emptyset)$. Thus, my first confusion is what happens at the first iteration of the algorithm. Second, if I read correctly, $W$ is not being updated during the forward phase. Then, what edges are we deleting in the backward phase? My guess is that once $i$ is chosen, we do $W = W[T \\to i]$, but again I am just guessing. Third, I believe no comments are given regarding the order for deleting edges. Any iteration order will end up with the same final $W$? If so, why?\n\n2. In the abstract and introduction, it is claimed that *several* existing order-based methods are special cases of the proposed greedy algorithm for some score function. However, I think this is formally shown *only* for the method by Chen et al. [5]. If this is the case, then the claim for *several* order-based methods is an overstatement and weakens the contributions of the work.\n\n3. In line 238, it is stated that Assumption 4.3. will \"hold in most settings\" but no formal or empirical support is given. I actually find the assumption somewhat obscure, and will appreciate if more intuition is given. Also, can authors briefly comment on the pros/cons of this assumption to other known assumptions such as faithfulness? \n\n4. I also find Assumption 5.2. somewhat restrictive. Can authors comment on this?\n\n5. I find the experiments somewhat inconclusive regarding the recovery of the true DAG. \nI believe having the plot showing the probability of exact recovery vs number of samples for the proposed method would strengthen the manuscript, where Figure 2 only looks for the ordering and not the whole graph. In Figures 4, 5, and 6, it seems that the proposed method can outperform other existing methods. However, to have a better sense of this, the setting with larger number of nodes is needed. I think there is also an implicit sparsity assumption in the experimental setting. Have authors evaluated the performance in dense DAGs?\n\n", "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": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of learning directed acyclic graphs via a greedy score-based algorithm. Specifically their algorithm works in two stages, first by estimating the topological ordering of the nodes, and then by pruning edges that do not influence the score. Compared to earlier works, the main innovation is in using the Bregman information as the score function. This allows them to show their algorithm recovers the ground truth network under various assumptions. This is a nice contribution, but the main point of contention among the reviewers was whether these assumptions were natural and/or properly justified. In their response, the authors related it to causal minimality, however the reviewers felt that it seemed to be stronger. As a suggestion for the authors, it would be better if Assumptions 4.3 and 4.4 were discussed in more depth and made more of a focal point of the paper. 
Decision: Accept (Poster)