Efficient Bayesian network structure learning via local Markov boundary search
Authors: Ming Gao
Bryon Aragam
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bayesian networks
structure learning
Markov boundary
sample complexity

Abstract: We analyze the complexity of learning directed acyclic graphical models from observational data in general settings without specific distributional assumptions. Our approach is information-theoretic and uses a local Markov boundary search procedure in order to recursively construct ancestral sets in the underlying graphical model. Perhaps surprisingly, we show that for certain graph ensembles, a simple forward greedy search algorithm (i.e. without a backward pruning phase) suffices to learn the Markov boundary of each node. This substantially improves the sample complexity, which we show is at most polynomial in the number of nodes. This is then applied to learn the entire graph under a novel identifiability condition that generalizes existing conditions from the literature. As a matter of independent interest, we establish finite-sample guarantees for the problem of recovering Markov boundaries from data. Moreover, we apply our results to the special case of polytrees, for which the assumptions simplify, and provide explicit conditions under which polytrees are identifiable and learnable in polynomial time. We further illustrate the performance of the algorithm, which is easy to implement, in a simulation study. Our approach is general, works for discrete or continuous distributions without distributional assumptions, and as such sheds light on the minimal assumptions required to efficiently learn the structure of directed graphical models from data.

Efficient Bayesian network structure learning via local Markov boundary search
Ming Gao The University of Chicago minggao@uchicaago edu
Bryon Aragam The University of Chicago bryon@chicagobooth
Abstract
We analyze the complexity of learning directed acyclic graphical models from observational data in general settings without specific distributional assumptions. Our approach is information-theorrtiic and uses local Markov boundary search procedure in order to recursively construct ancestral sets in the underlying graph- ical model. Perhaps surprisingly, we show that for certain graph ensembles, a simple forward greedy search algorithm (i.e. without backward pruning phase) suffices to learn the Markov boundary of each node. This substantially improves the sample complexity, which we show is at most polynomial in the number of nodes. This then applied learn the entire graph under novel identifiability condition that generalizes existing conditions from the literature. As matter of independent interest, we establish sampee guarantees for the problem recovering Markov boundaries from data. Moreover, we apply our results to the special case polytrees, for which the assumptions simplify, and provide explicit conditions under which polytrees are identifiable and learnable in polynomial time. We further illustrate the performance of the algorithm, which is casy to implement, in simulation study. Our approach is general, works for discrete continuous distributions without distributional assumptions, and as such sheds light on the minimal assumptions required to efficiently learn the structure of directed graphical models from data.
Introduction
Learning the structure of a distribution in the form of graphical model a classical problem in statistical machine learning. whose roots date back to early problems in structural equations and covariance selection 12 45 46). Graphical models such as Markov networks and Bayesian networks impose structure in the form of an undirected graph (UG, in the case of Markov networks) directed acyclic graph (DAG, in the case of Bayesian networks). This structure is useful for variety of tasks ranging from querying and sampling inference of conditional independence and causal relationships, depending on the type of graph used. In practice, of course, this structure is rarely known and we must rely on structure learning to first infer the graphical structure. The most basic version of this problems asks, given n samples from some distribution I that is represented by graphical model G E), whether not is possible reconstruct G.
In this paper, we study the structure learning problem for Bayesian networks (BNs). Our main contribution is fine-grained analysis of polynomial time and sample complexity algorithm for learning the structure of BNs with potentially unbounded maximum in-degree and without faithfulness. In particular, in our analysis attempt expose the underlying probabilistic assumptions that important for these algorithms to work, drawing connections with existing work on local search algorithms and the conditional independence properties of P.
35th Conference on Neural Information Processing Systems (NcurIPS 2021), virtual.

---

1.1 Contributions
One of the goals of the current work to better understand the minimal assumptions needed to identify and learn the structure of a DAG from data. Although this is well-studied problem, existing theoretical work (see Section I.2) relies on assumptions that, as we show, are not really necessary. In particular, our results emphasize generic probabilistic structure (conditional independence, Markov boundaries, positivity, etc.) as opposed to parametric or algehraic structure (linearity, additivity, etc.), and hence provide more concrete understanding of the subtle necessary conditions for the success of this approach.
With this goal in mind, we study two fundamental aspects of the structure learning problem: Identifia- bility and Markov boundary search. On the one hand, we provide weaker condition for identifiability compared to previous work, and on the other, we exhibit families of DAGs for which forward greedy search suffices to provably recover the parental sets of each node. More specifically, our contributions can be divided into several parts:
1. Identifabiility (Theorem
We prove new identifiability result on DAG learning. Roughly speaking, this condition requires that the entropy conditioned on an ancestral set (Xx A) of each node in is dominated by one of its ancestors. An appealing feature of this assumption is that it applies to general distributions without parametric or structural assumptions, and generalizes existing ones based on second moments a condition on the local entropies in the model. We also discuss in depth various relaxations of this and other conditions (Appendix C
2. Local Markov boundary search (Algorithm 2 Proposition 4.1 We prove finite-sample guar- antees for a Markov boundary learning algorithm that is closely related to the incremental association Markov blanket (IAMB) algorithm, proposed in Tsamardinos et al. 42 These results also shed light on the assumptions needed to successfully learn Markov boundaries in general settings; particular, we do not require faithfulness, which is often assumed.
3. Structure learning (Algorithm 1 Theorem 5.1). We propose an algorithm which runs in Od log d) time and O log d) sample complexity, to learn an identifiable DAG G from samples. Here, d the dimension and < d is the depth of the DAG G, defined in Section 2
4. Learning polytrees (Theorem 5.2). As an additional application of independent interest, we apply our results the problem of learning polytrees [10] 337.
5. Generalizations and extensions (Appendix C In the supplement, we have included an extensive discussion of our assumptions with many examples and generalizations illustrate the main ideas. For example, this appendix includes relaxations of the positivity assumption on P. the main identifiability condition (Condition [T.. the PPS condition (Condition D. and extensions to general, non-binary distributions. We also discuss examples of the conditions and a comparison to the commonly assumed faithfulness condition.
Finally, despite long history of related work on Markov blanket learning algorithms [e.g. 1 34, 40 to the best of our knowledge there has been limited theoretical work on the finite-sample properties of IAMB and related algorithms. It is our hope that the present work will serve to partially fill in this gap.
1.2 Related work
Early approaches to structure learning assumed faithfulness (for the definition, see Appendix B this concept not needed in the sequel), which allows one learn the Markov equivalence class of P 15 23
30 39). Under the same assumption and assuming additional access to a black-box query oracle, Barik and Honorio [ develop an algorithm for learning discrete BNs. Barik and Honorio 4 develop an algorithm for learning the undirected skeleton of G without assuming faithfulness. On the theoretical side, the asymptotic sample complexity of learning faithful BN has also been studied [14 Brenner and Sontag [5] propose the Sparsity score and prove a polynomial sample complexity result, although the associated algorithm relies on solving difficult integer linear program. Chickering and Meek [8] study structure learning without faithfulness, although this paper does not establish finite-sample guarantees. Zheng et al. [49 50 transform the score-based DAG learning problem into continuous optimization, but do not provide any guarantees. Aragam et al. 2

---

analyze the sample complexity of score-based estimation in Gaussian models, although this estimator based on a nonconvex optimization problem that is difficult to solve.
An alternative line of work, more in spirit with the current work, shows that G itself can be identified
without assuming faithfulness [24 36
48 although these methods lack finite-sample guarantees.
Recently, Ghoshal and Honorio 19 translated the equal variance property of Peters and Bühlmann
[3) into a polynomial-time algorithm for linear Gaussian models with polynomial sample complexity. Around the same time, Park and Raskutti 33 developed an efficient algorithm for learning a special family of distributions with quadratic variance functions. To the best of our knowledge, these algorithms were the first provably polynomial- time algorithm for learning DAGs that did not assume faithfulness. See also Ordyniak and Szeider [32] for an excellent discussion of the complexity of BN learning. The algorithm of Ghoshal and Honorio [9 has since been extended in many ways
6
Our approach is quite distinct from these approaches, although as we show, our identifiability result subsumes and generalizes existing work on equal variances. Additionally, we replace accond-momen assumptions with entropic assumptions, which are weaker and have convenient interpretations in terms of conditional independence. which is natural in the setting of graphical models. Since many of the analytical tools for analyzing moments and linear models are lost in the transition to discrete models, our work relies on fundamentally different (namely. approach also has the ad advantage of highlighting the important role of several fundamental assumptions that are somewhat obscured by the linear case, which makes strong use of the covariance structure induced by the linear model. Finally, we note that although infornation-theoreti ideas have long been used to study graphical models [e.g. 28) these works do not propose efficient algorithms with Anite-sample guarantees, which is the main focus of our work.
coarmatiinnthheoretee
tools in the analysis. Our
2 Preliminaries
Notation We use [d] = (1,..., to denote an index set. As is standard in the literature on
graphical models, we identify the vertex set of graph G = (V, E)) with random vector X = (Xi...., Xa). and in the sequel we will frequently abuse notation by identifying V X = [d]. For any subset S C V. G[S) the subgraph defined by S. Given DAG G (V, and a node X E V. pa(k) = {X; k) E E} is the set of parents, de(k) is the set of descendants, nd)): == V \ is the set of nondescendants, and an(k) is the set of ancestors. Analogous notions are defined for subsets of nodes in the obvious way. A source node is any node Xx such that an(k) = and a sink node is any node X₁ such that de(k) = 0. Every DAG admits unique decomposition into r layers, defined recursively as follows: L1 is the set of all source nodes of G and Lj is the set of all sources nodes of G(V \ U By convention, we let Lo = @ and layer width d, |Lyl. the largest width max, d, = w. An ancestral set any subset A C V such that an(A) C A. The layers of G define canonical ancestral sets by A, = TT I4. Finally, the Markov boundary of node X relative to subset S C the smallest subset m C S such that X₃ IL (S) \m) m, and denoted by MB(X, (Xx: 5) or msk for short.
The entropy of discrete random variable Z is given by H(Z) = =-E, P(Z log P(Z P(g z), the conditional entropy given Y is HZ YY- = Σ z.y P(Z = 2, Y 3) P(z = 2 y). and the mutual information between Z and Y is T( = H(Z) - -H YY) For more background on information theory, see Cover and Thomas 9
Graphical models Let (X,......... Xa) be a random vector with distribution P. In the sequel, for simplicity, we assume that X E 10, and that P is strictly positive, i.e. P(X = x) > 0 for all E {0, 13d, These assumptions are not necessary; see Appendix Cor extensions to categorical random variables and/or continuous random variables and nonpositive distributions.
A DAG G (V, is Bayesian network (BN) for P if P factorizes according to G, i.e.
d
P(X) II P(Xx pa(k))
(1)
k=1
Obviously, by the chain rule of probability, a BN is not necessarily unique-any any permutation of the variables can be used to construct valid BN according to ([). A minimal I-map of P is any BN such
3

---

that removing any edge would violate (T. The importance of the factorization ① is that it implies that separation in G implies conditional independence P, and a minimal I-map encodes as many such independences as possible (although not necessarily all independences). For more details, review of relevant graphical modeling concepts included, see Appendix [
The purpose of structure learning is twofold: 1) To identify unique BN G which can be identified from P. and 2) To devise algorithms learn G from data. This is our main goal.
3
Identifiability of minimal I-maps
In this section we introduce our main assumption regarding identifiability of minimal I-maps of P.
3.1 Conditions for identifiability
For X2 E V \ A5+1. define any(k) == am(X)) n Lj+1, i.e any (k) denotes the ancestors of X in Lj+1. By convention, we let Ag = 0. Finally, with some abuse of notation, let L(Xx) E [r] indicate which layer X3 is in, i.. L(Xx) j if and only if X2 Lj-
Condition 1. For each X₃ E V with L(Xx) 2 2 and for each j = 0, L(Xx) - 2, there exists X E any (R:) such that following two conditions hold:
(CI) H(X; | A₂) < H(xx Aj).
(C2) X; |A,) 0.
We refer X; an (k) (k)(k) satisfying (CI) and (C2) in Condition as the important ancestors for X₁. denoted by mky(k). Thus, another way stating Condition is that for each X₁ E V with L(Xx) and for each
, 2, there exists important ancestor, i.e. im,(k) & D.
The idea behind this condition is the following: Suppose we wish to identify the tth layer of G. Condition requires that for every node after Le (represented by Xg), there is at least one node X; in L, satisfying (CI) and (C2) The intuition the entropy (uncertainty) in the entire system is required
to increase time evolves.
Condition (CI) is the operative condition: By contrast, (C2) is just nondegeneracy condition that says X, A X Ay. which will be violated only when any (k) is conditionally independent of X given Aj. At the population level. (C2) is superficially similar faithfulness, however, a closer look reveals significant differences. One example of conditional independence between an entire layer of ancestors and descendants is path-cancellation. where effects through multiple paths are neutralized through delicate choices of parameters, whereas unfaithfulness occurs when there happens to be just one such path cancellation. Moreover, [C2] only applies
small set of ancestral sets, whereas faithfulness applies to all possible d-separating sets. Not only is this kind of nath-cancellation for all of any (k)) unlikely, we show Appendix G that this is essentially the only way (C2) can violated: If G is poly-forest, then C2) always holds, see Lemma G.1
In Section (.2] we will discuss this condition in the context of an algorithm and example, which should help explain its purpose better. Before we interpret this condition further, however, let us point why this condition is important: identifies G.
Theorem 3.1. If there is minimal I-map G satisfying Condition ! then G is identifiable from P.
In order better understand Condition D let us first compare to existing assumptions such as equal variances [19 36). Indeed, there is a natural generalization of the equal variance assumption to Shannon entropy:
(C3) H (Xx pa(k)) = h² is the same for each node k = 1,...,d. d.
One reason consider entropy is due the fact that every distribution with E oo for some > 0 has well-defined entropy, whereas not all distributions have finite variance. Though quoted here, we will not require (C3) in the sequel; it is included here merely for comparison. Indeed, the next result shows that this "equal entropy" condition is special case of Condition
Lemma 3.2. Assuming Condition 1
(C2)
C3 implies (CI) Thus, the "equal entropy" condition implies

---

Algorithm Learning DAG structure
Input: X (XI,..,, w
Output: G.
1. Initialize empty graph G = 0 and j = 0
2. Set L, 0, let A, = Io
3. While V \ Ag # 0:
(a) For A & A,, estimate conditional entropy (Xx A2) by some estimator hys-
(b) Initialize Lj+1 = 0. Sj+1 = 0. Sort h5z in ascending order and let f(0) be the corresponding permutation of V Az-
(c) For é 0,1,,, until [F(O| 0: ITAM step]
i. [j+1= = -1y+1 (71%).
ii For k & A, Lyp2 U US441 estimate 7( (A₂)
iii. Set Sj+1 = Sj+1 U {k: T/6 2 w).
iv. p((+1) 7(0) (Teg+1 U USj+1)
(d) For & E Li+1, set (aa(k) = MB(Xx;A,).
(e) Update j j +1.
4. Return G.
In fact, (C1) significantly relaxes (C3) The latter implies that all nodes in Lj+1 have smaller conditional entropy than Xg. whereas (C1) only requires this inequality to hold for at least one ancestor X; ak) Moreover, something even stronger true: The equal variance condition can be relaxed to unequal variances (see Assumption in (20). and we can derive a corresponding We can also construct explicit examples that satisfy Condition T but neither the equal nor unequal entropy condition. For details, see Appendix C.3
"unequal entropy" condition. This condition is also a special case of Condition |
Remark 1. Condition can be relaxed even further: See Appendix C.2 and Remark 3 for a discussion along with its corresponding algorithm.
3.2 Algorithmic interpretation
The proof of Theorem 3.1 motivates a natural algorithm to learn the DAG, shown in Algorithm!] [ This algorithm exploits the fact that given Ay. nodes within Ly+1 are mutually independent. Algorithm [ a layer-wise DAG learning algorithm. For each layer, it firstly sorts the conditional entropies in ascending order т, then runs a "Testing and Masking" (TAM) step to distinguish nodes in Lj+1 from remaining ones (X+): We use imy defined in (C1) to detect and mask X & Lj+1 by resting conditional independence. By masking, we mean we do not consider the nodes being masked when proceeding over the entropy ordering to identify Lj+1-
In order to see how Algorithm | works, consider the example shown in Figure Ia). the first step with 0, we use marginal entropy (i.e. since An 0) to distinguish L, from the remaining nodes. Let (Xx) := h and assume for simplicity that the nodes are ordered such that h < h2 <... < he (Step 3(b)). Apparently, the incqualities that f1 < |at1:s] and ht he imply (C3) does not hold here. Suppose there are no spurious edges, i.c. descendants and ancestors are dependent. Now we can see conditions in Theorem 3.1 are satisfied and the important ancestors for X2, Xg, .xs are X1, Xa respectively. The implementation of Algorithm is visualized in Figure Tbb): In the first loop, X1 is taken into L1 and X2, X3 are masked due to dependence (Step 3c(iii)). In the second loop, X₃ is added to L, and then X5 is masked. Finally, with X, put into L,, we have identified L,
It is worth emphasizing that the increasing order of marginal entropies in this example is purely for simplicity of presentation, and does not imply any information on the causal order of the true DAG. The marginal entropies of nodes need not be monotonic with respect to the topological order of G.
5

---

11
Entropy Ordar:
h1
hz
hg
h4
hs
h6
X
Loop 1:
X
X
X3
Loop 2
Xs
Unknown
X
Loop
Sj: Maskod
X1
X2
X3
X4
X5
X
(b)
Example for TAM algorithm: (a) True DAG with L1 outlined; (b) Status of the algorithm after each loop, denoted by different patterns of nodes.
Figure 1:
Algorithm 2 Possible Parental Set (PPS) procedure
Input: X (X1..... Xa), k, A, Output:
Conditional entropy h, Markov boundary m
1. Initialize m 0. loop until m does change:
(a) For é AA m, estimate conditional mutual information I(Xx; mi) by some estimator It.
(b) Let l arg max A. Le if Te. > set m m U {
2. Estimate conditional entropy (Xx m)) by some estimator h.
3. Return conditional entropy estimation and estimated Markov boundary m.
4 Local Markov boundary search
Algorithm Jasuumes that we can learn MB(X,; Aj), the Markov boundary Xx in the ancestral set Aj. This is well-studied problem in the literature, and variety of greedy algorithms have
been proposed for learning Markov boundaries from data [I] [6] 18 34 41 42). all based on same basic idea: Greedily add variables whose association with X₁ is the highest. In this section, we establish thcoretical guarantees for such a greedy algorithm. the next section, we apply this algorithm to reconstruct full DAG G via Algorithm
To present our Markov boundary search algorithm, we first need to set the stage. Let Xg E V be any node and A an ancestral set of Xg. We wish to compute MB(X;; A) and H(x, A). An algorithm for this is outlined Algorithm 2 In contrast to many existing local search methods for learning Markov boundaries, this algorithm is guaranteed to return the parents of X in G. More specifically, X E Li+1, then MB A,) = pa(X;) J. For this reason, we refer to Algorithm as possible parent selection, PPS for short. In fact, PPS is exactly the forward phase of the well-known IAMB algorithm for Markov blanket discovery [42 with conditional mutual information used both as an association measure and as conditional independence test.
Although PPS will always return valid Markov blanket, without a backward phase to remove unnecessary variables added by the forward greedy step, PPS may fail to return minimal Markov blanket, i.e. the Markov boundary. The following condition enough ensure no unnecessary variables are included:
Condition 2 (PPS condition). For any proper subset m Ç MB(Xs; A) and any node X E A MB(X;; A), there exists X, E MB(X2; A) m such that
I(Xx; m) > 1(Xxi m).

---

Condition 2 requires that nodes in [B A) always contribute larger conditional mutual infor- mation marginally than those that are not MB (Xx: (Xx:AA). A). Thus when we do greedy search to select parents in Algorithm 2 only the nodes in MB(X;; A) will be chosen. Therefore, with a proper threshold K, this set can perfectly recovered without incorporating any nuisance nodes.
We now present the sample complexity of using PPS to recover Markov boundaries under Condition 2 We will make frequent use of the Markov boundary and its size:
MAk MB(Xg; A), MA == mmak]-
(2)
In particular, by definition we have Xx 1L (A) (aa) mAk- Under Condition 2 following quantities:
we further define
A == min
max eEmAR
[[xx; Xx m²) - max 1Xxx; [m) mEAy
> 0,
EAk ==
min m CE Am
min
[(xx: X m2m22 O.
(3)
Â AN is the gap between the mutual information of nodes inside or outside of mAR- EAR is the minimum mutual information contributed by the nodes in mk- The larger these quantities, the easier the M A) is to be recovered.
Proposition 4.1. Fix k E V and let A be any set of ancestors of XN. Suppose Condition 2 holds. Algorithm 2 is applied for estimate mA and H (Xx A) with K Eak, we have with
t I min K., AA/2
oMa 12
P (mMA== - [Xx IA) H(Xx AA) <1) <1)= (MAr 2)[A|
where Man the estimation error of conditional entropy defined by ( in Appendix
which
depends on MA--
naive analysis of this algorithm would have a sample complexity that depends on the size of the ancestral set A; note that our more fine-grained analysis depends instead on the size of the Markov boundary MB(X;:A) A). We assume with sample size large enough, MM is small such that the right hand side remains to be positive and goes to 1. The proof of Proposition 4.1 is deferred to Appendix E.2
Condition 2 ensures the success of the greedy PPS algorithm. Although this assumption is not strictly necessary for structure learning (see Appendix CC5 for details), it significantly improves the sample complexity of the structure learning algorithm (Algorithm[] [T. Thus, it is worthwhile to ask when Condition 2 holds: We will take up this question again Section
5 Learning DAGs
Thus far, we have accomplished two important subtasks for learning a DAG: In Section we identified its layer decomposition L (LI...., L,). In Section we showed that the PPS procedure successfully recovers (ancestral) Markov boundaries. Combining these steps, we obtain a complete algorithm for learning G. In this section, study the computational and sample complexity of this algorithm; proofs are deferred to the appendices.
We adopt the notations for Markov boundaries as in (
m = MB(Xx;A) Mfx == |mja]
(4)
Therefore, X IL (Aj) \ (m3k) ) Myj. A critical quantity in the sequel will be the size of the largest Markov boundary Mijk which we denote by M:
M max Mfs - max |mzel- jk
(5)
jk
This quantity depends on the number of nodes d and the structure of the DAG. For example, if the maximum in-degree of I, then M = 1. related quantity that appears existing work the size of the largest Markov boundary relative to all of X, which may be substantially larger than M. The former quantity includes both ancestors and descendants, whereas m,k only contains ancestors. Analogously, let M, max; Myk.
7

---

5.1 Algorithm
we obtain complete algorithm for learning the DAG G, which we refer to as the TAM algorithm, short for Testing and Masking. It consists of two parts:
By combining Algorithms and 2
1. Learning the layer decomposition (L,....,,,) by minimizing conditional entropy and TAM step (Algorithm :
2. Learning the parental sets and reducing the size of conditioning sets by learning the Markov boundary myjk MB(X Aj) (Algorithm 2
Specifically, we use PPS (Algorithm 2 to estimate the conditional entropies (Step 3(a)), conditional mutual information (Step 3c(i)), and the Markov boundary (Step 3(d)). For completeness, the complete procedure is detailed in Algorithm 3 the supplement. More generally, Algorithm Carrrithh@aannnn be replaced with any Markov boundary recovery algorithm or conditional entropy estimator; this highlights the utility of Algorithm | as separate meta-algorithm for DAG learning.
One missing piece is the choice of estimators for conditional entropy and mutual information in steps (Ia) and (2) of the PPS procedure. We adopt the minimax entropy estimator from Wu and Yang 47 by treating (without loss of generality) the joint entropy the entropy of a multivariate discrete variable, although other estimators can be used without changing the analysis. The complexity of this estimator is exponential
M (i.e. since there are up M states to sum over in any Markov In addition, for the TAM step, there are at most max, d nodes in each layer to estimate conditional mutual information with remaining at most d nodes, thus this step has computational complexity maxx d, d,2**). Thus assuming M K log the overall computational complexity of Algorithm I is most O(r x (d x Md2 + x max, d, d,2*) = (d log d). Specifically, for layers, we must estimate the conditional entropy of at most d nodes, and call TAM step once.
boundary myk), so the computational complexity of Algorithm 2 is O(M
5.2 Main statistical guarantees
In order to analyze the sample complexity of Algorithm Junder Conditions] and 2 we introduce following positive quantities:
== min min
(H(X, A2) - H(,; |4,) 00 KEV
= min min KEV
I(X; X, Ay) > 0
where X, E im, (k) ik) is defined in Condition These two quantities are corresponding to the two conditions (CI) and (C2) which are used distinguish each layer with its descendants. Compared to strong faithfulness, which is needed on finite samples, we only require a much smaller, restricted set of information measures to be bounded from zero. We also adopt the quantities defined in by setting A A, and drop the notation such that 7,K == AAAK and Ejk- := EAyk-
Finally we are ready to state the main theorem about sample complexity of Algorithm I
Theorem 5.1. Suppose P satisfies Conditions and 2 and let G be the minimal I-map identified
by Theorem 3.1 Let G be output of Algorithm applied with w S n122 and k. S mings Esk- Denote
A mnin,a(A/22. A2x If M & log d and
rog d (At 226
2
then G = G with probability 1-6
Up to log factors, the sample complexity scales quadratically with the number of nodes d2 and linearly in the depth d. In the worst case, this is cubic in the dimension. For example, if G is Markov chain then M and d, thus it suffices to have sddd log" d). Comparatively, most of previous work 6 21 44 only consider linear or parametric models. One recent work that provides nonparametric guarantees without assuming faithfulness is [17], who show that in general, (((dr/e)* +dd/2) samples suffice recover the topological ordering under equal variance

---

F.2 we discuss the selection of assumption similar in spirit to (C3) Unlike the current work, which considers exact recovery of the full graph G, [77 does not include the reduction Markov boundary search that is crucial to our exact recovery results.
In fact, the proof indicates, the sample complexity of our result also depends exponentially M. This explains the assumption that M S log d; the logarithmic assumption is analogous to sparsity and results from not making any parametric assumptions on the model. Since our setting is fully nonparametric, exponential rates in the dimension d are to be expected. Under stronger parametric assumptions, these exponential rates can likely be avoided. detailed analysis of the dependency on M can be found in the proofs, which are deferred to Appendix
Finally, in practice the quantities 17, Eyk needed in Theorem 5.1 may not be known, which hinders the choice of tuning parameters w, k. In Appendix E.4 (see Theorem these tuning parameters in data-dependent way.
5.3 Application to learning polytrees
Learning polytrees is one the simplest DAG learning problems. This problem was introduced in Rebane and Pearl (37) and in a seminal work, Dasgupta [TO] showed that learning polytrees is NP-hard in general. In this section, we note that when the underlying DAG is a polytree (or more generally, polyforest), Condition 2 always satisfied, and therefore we have efficient algorithm for learning identifiable polyforests that satisfy Condition II
Recall that a polyforest is a DAG whose skeleton (i.e. underlying undirected graph) has cycles.
Theorem 5.2. If P satisfies ① for some polyforest G, then Condition 2 is satisfied.
The detailed proof can be found in Appendix F
As result, it follows immediately (by combining Theorems 5.1 and 5.2 with Lemma G. that any polytree satisfying (CT) is learnable.
The crucial property of poly-forest used in proving Theorem 5.2 is that there exists at most one directed path between any two nodes the graph. However, the existence of multiple directed paths between two nodes does not necessarily imply that Condition will fail: There are concrete examples of graphs satisfying Condition 2 with arbitrarily many paths between two nodes. An example is given by the DAG G = (V, E) with V (Z, X....... Xx. Y) such that Z + X₃ Y for each i. Thus, this assumption holds more broadly than suggested by Theorem 5.2 It is an interesting problem for future work to study this further.
6 Experiments
We conduct a brief simulation study to demonstrate the performance of Algorithm 1 and compare against some common baselines: PC (39]. GES (7). We focus on the fully discrete setting. All imple- mentation details can be found in Appendix [ The code implementing TAM algorithm is available at https://gtt thub. com/ www/ Miw.giinnnGga////o ATAMM We stress that the purpose of these experiments is simply to illustrate that the proposed algorithm can be implemented in practice, and successfully recovers the edges G as predicted by our theoretical results.
We evaluate the performance of aforementioned algorithms by Structural Hamming distance (SHD): This is standard metric for DAG learning that counts the total number of edge additions, deletions, and reversals needed to convert the estimated graph into the reference one. Since PC and GES both return a CPDAG that may contain undirected edges, we evaluate these algorithms favourably by assuming correct orientation for undirected edges wherever they are present.
We simulate DAGs from three graph types: Poly-trees (Tree), Erdös-Rényi (ER), and Scale-Free (SF) graphs. As discussed in Section 5.3] poly-tree models are guaranteed to satisfy Condition 2 whereas general DAGs such as ER SF graphs are not, this provides a test case for when this condition may fail. We generate data according to two models satisfying the "equal entropy" condition (C3)
As discussed in Appendix C.3
(C3) implies our main identifiability Condition
. "Mod" model (MOD): X (Sk mod 2) x (1 (Sx mod 2))2-2x where Sa Exepa(k) X, with Z ~ (0r(0.
Additive model (ADD): Xx+ ErEpa(N) Xe + Za with Zi Ber(0.2)

---

MOD model
ADD model e-ds
1-23
d-dc
6-00
6-c
10
@Smmpe sbe thousands)
(Sample soe thousands)
meltods
TAM
FC
C2S
SHD vs sample size for different dimensions and graph types. Left panel is for MOD model; Right panel is for ADD model.
Figure 2:
Figure 2 (left, right) illustrates the performance in terms of structural Hamming distance (SHD) between the true graph and the estimated graph. As expected, our algorithm successfully recovers the underlying DAG G and performs comparably to PC and GES, which also perform quite well. We stress that the current experiments are used for simple illustration thus not well-optimized compared to existing algorithms or fully exploited the main condition either. The relatively good performance of PC/GES partially comes from the fact that our synthetic models are all in fact faithful, see Appendix C.7 for further discussion.
7
Conclusion
The main goal of this paper has been better understand the underlying assumptions required for DAG models to be estimated from data. To this end, we have provided a new identifiability result along with learning algorithm, which turns out to generalize existing ones, and analyzed greedy, local search algorithm for discovering Markov boundaries. This local search algorithm can be used to provably learn the structure of minimal I-map in polynomial time and sample complexity long as the Markov boundaries are not too large. Nonetheless, there are many interesting directions for future work. Perhaps the most obvious is relaxing the logarithmic dependence in M. It would also interesting to investigate lower bounds on the sample complexity of this model, as well as additional identifiability conditions.
Acknowledgements
We thank the anonymous reviewers for their helpful comments in improving the manuscript. B.A. was supported by NSF IIS- 1956330, NIH 404671 and the Robert H. Topel Faculty Research Fund at the University of Chicago Booth School of Business. All statements made are solely due to the authors and have not been endorsed by the NSF.
References
[1] C. F. Aliferis, A. Statnikov, I. Tsamardinos, S. Mani, and X. D. Koutsoukos, Local causal and Markov blanket induction for causal discovery and feature selection for classification Part I: Algorithms and empirical evaluation. Journal of Machine Learning Research, 11:171-234 2010.
[2] B. Aragam, A. Amini, and Q Zhou. Globally optimal score-based learning of directed acyelic graphs in high-dimensions. In Advances in Neural Information Processing Systems 32, pages 4450-4462. 2019.
10

---

[3] A. Barik and J. Honorio. Learning bayesian networks with low rank conditional probability tables. In Advances in Neural Information Processing Systems, pages 8964-8973, 2019.
[4] A. Barik and J. Honorio. Provable efficient skeleton learning of encodable discrete bayes nets in poly-time and sample complexity. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2486-2491. IEEE, 2020.
[5] E. Brenner and D. Sontag. Sparsityboost: A new scoring function for learning bayesian network structure. In 29th Conference on Uncertainty in Artificial Intelligence, UAI 2013, pages 112-121, 2013.
[6] W. Chen, M. Drton, and Y. S. Wang. On causal discovery with an equal- assumption. Biometrika, 106(4):973-985 980, 09 2019. ISSN 0006-3444, doi: (0.1093/biomeetssz044.
[7] D. M. Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3:507-554, 2003.
[8] D. M. Chickering and C. Meek. Finding optimal Bayesian networks. In Proceedings of the Eighteenth conference on Uncertainty in artificial intelligence, pages 94-102. Morgan Kaufmann Publishers Inc., 2002.
[9] T. M. Cover and J. A. Thomas. Elements of information theory. John Wiley & Sons, 2012.
[10] S. Dasgupta. Learning polytrees. In Proceedings of the Fifteenth conference Uncertainty in artificial intelligence, pages 134-141, 1999.
[11] A. P. Dawid. Conditional independence for statistical operations. Annals of Statistics, pages 598-617, 1980.
[12] A. P. Dempster. Covariance selection. Biometrics, 28(1):157-175, 1972.
[13] M. Drton, B. Sturmfels, and S. Sullivant. Lectures algehraic statistics. Springer, 2009.
[14] N. Friedman and Z. Yakhini. On the sample complexity of learning bayesian networks. In Uncertainty in Artifical Intelligence (UAI), 02 1996.
[15] N. Friedman, I. Nachman, and D. Peér. Learning Bayesian network structure from massive datasets: The Sparse Candidate algorithm. In Proceedings of the Fifleenth conference on Uncertainty in artificial intelligence, pages 206-215. Morgan Kaufmann Publishers Inc., 1999.
[16] S. Fu and M. C. Desmarais. Fast markov blanket discovery algorithm via local learning within single pass. In Conference of the Canadian Society for Computational Studies of Intelligence, pages 96-107. Springer, 2008
[17] M. Gao, Y. Ding, and B. Aragam. polynomial-tin cirttomial--meeeeeee time algorithm for learning nonparametric causal graphs. In Advances in Neural Information Processing Systems, 2020.
[18] T. Gao and Q Ji. Efficient markov blanket discovery and its application. IEEE transactions on Cybernetics, 47(5):1 169-1179, 2016.
[19] A. Ghoshal and J. Honorio. Learning identifiable gaussian bayesian networks in polynomial time and sample complexity. Advances in Neural Information Processing Systems 30, pages 6457-6466. 2017.
[20] 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-Fins 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.
[21] A. Ghoshal and J. Honorio. Learning linear structural equation models in polynomial time and sample complexity. In International Conference on Artificial Intelligence and Statistics, pages 1466-1475. PMLR, 2018

---

[22] Y. Han, J. Jiao, T. Weissman, Y. Wu, et al. Optimal rates of entropy estimation over lipschitz balls. Annals of Statistics, 48(6):3228-322 -2500, 2020.
[23] D. Heckerman, D. Geiger, and D. M. Chickering. Learning Bayesian networks: The combination of knowledge and statistical data. Machine learning, 20(3):197-243, 1995.
[24] P. O. Hoyer, D. Janzing, J. M. Mooij. J. Peters, and B. Schölkopf. Nonlinear causal discovery with additive noise models. In Advances in neural information processing systems, pages 2009.
[25] D. Janzing and B. Schölkopf. Causal inference using the algorithmic markov condition. IEEE Transactions on Information Theory, (6610))5588-5144 2010.
[26] D. Janzing, J. Mooij. K. Zhang, J. Lemeire, J. Zscheischler, P. Daniušis, B. Steudel, and B. Schölkopf. Information-geomeet geometric approach inferring causal directions. Artificial Intelli- gence, 182:1-31, 2012.
[27] M. Kocaoglu, A. Dimakis, S. Vishwanath, and B. Hassibi. Entropic causal inference. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
[28] M. Kocaoglu, A. G. Dimakis, Vishwanath, and B. Hassibi. Entropic causality and greedy minimum entropy coupling. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 1465-1469. IEEE, 2017.
[29] D. Koller and N. Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
[30] W. Lam and F. Bacchus. Learning Bayesian belief networks: An approach based on the MDL principle. Computational intelligence, 10(3):269-293, 1994.
[31] S. L. Lauritzen. Graphical models. Oxford University Press, 1996.
[32] S. Ordyniak and S. Szeider. Parameterized complexity results for exact bayesian network structure learning. Journal of Artificial Intelligence Research, 46:263-302, 2013.
[33] G. Park and G. Raskutti. Learning quadratic variance function (QVF) dag models via overdis- persion scoring (ODS). The Journal of Machine Learning Research, 18( 11:83000-8442 2017.
[34] J. M. Pena, R. Nilsson, J. Björkegren, and J. Tegnér. Towards scalable and data efficient learning of markov boundaries. International Journal of Approximate Reasoning, 45(2):211 1-232, 2007.
[35] J. Peters. On the intersection property of conditional independence and its application to causal discovery. Journal of Causal Inference, 3(1):97-108, 2015.
[36] Peters and P. Bühlmann. Identifiability of Gaussian structural equation models with equal error variances. Biometrika, 101 228, 2013.
[37] G. Rebane and J. Pearl. The recovery of causal poly-trees from statistical data, arXiv preprint 1304 2013.
[38] S. Shimizu, P. O. Hoyer. A. Hyvärinen, and A. Kerminen. A linear non- Non-Gaussiian acyclic model for causal discovery. Journal of Machine Learning Research. 1-200-22030, 2006.
[39] P. Spirtes and C. Glymour. An algorithm for fast recovery of sparse causal graphs. Social Science Computer Review, (1):62-72, 1991.
[40] A. Statnikov, N. I. Lytkin, J. Lemeire, and C. F. Aliferis. Algorithms for discovery of multiple markov boundaries. Journal of Machine Learning Research, 14(Feb):499-566, 2013.
[41] I. Tsamardinos, C. F. Aliferis, and A. Statnikov. Time and sample efficient discovery of markov blankets and direct causal relations. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 673 678, 2003.
[42] Tsamardinos, C. F. Aliferis, Statnikov, and E. Statnikov. Algorithms for large scale markov blanket discovery. In FLAIRS conference, volume 2, pages 376-380, 2003.
12

---

[43] C. Uhler, G. Raskutti. P. Bühlmann, and B. Yu. Geometry of the faithfulness assumption in causal inference. Annals of Statisties, 41(2):436 463, 2013.
[44] Y. S. Wang and M. Drton. High-dimensional causal discovery under non-gaussianity. Biometrika, 107(1):41-59, 2020.
[45] S. Wright. Correlation and causation. Journal of agricultural research, 20(7):557-58,, 1921.
[46] S. Wright. The method of path coefficients. The Annals of Mathematical Statisticx, 5(3): 161-215, 1934.
[47] Y. Wu and P. Yang. Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Transactions on Information Theory, 62(6):3702- 013777222770,,, 2016.
[48] K. Zhang and A. Hyvärinen. On the identifiability of the post-nonlinear causal model. In Proceedings of the twenty-fith conference uncertainty in artificial intelligence, pages 647-
655. AUAI Press, 2009.
[49] X. Zheng, B. Aragam, P. K. Ravikumar, and E. P. Xing. Dags with no tears: Continuous optimization for structure learning. Advances in Neural Information Processing Systems, 31, 2018.
[50] 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.
[51] O. Zuk, S. Margel, and E. Domany. On the number of samples needed to learn the correct structure of bayesian network. 06 2012.
13


Reviews:
[{"review_id": "ux7qGxKby-Y", "reviewer": "Reviewer_Zh6d", "summary": "In this paper, the authors look at the problem of learning the structure of a Bayesian network from samples. In this line of work, equal variance has been a standard assumption, see for example the work by Ghoshal and Honorio. In this paper, the authors propose an entropic assumption, which they show is more general than the equal variance assumption, in recovering the true structure. In their algorithm, they learn the Bayes net layer after layer. In discovering each layer, they crucially use their entropic assumption to mask out vertices that do not belong to the current layer. Their technique is applicable also in continuous settings, using the differential entropy in place of Shannon entropy. In fact, that is how they claim to generalize the equal variance assumption. Therefore, at a high level, the authors claim that their entropic condition is much more fundamental. The authors also give a formal guarantee of the Markov boundary search procedure used to detect the parents of a given node among its Markov boundary, using a PPS condition. However, I did not find the later condition very realistic in practice.", "questions": "", "limitations": "", "rating": 7, "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": "Finally, the authors also give finite sample upper bounds for recovering the true structure from samples based on certain quantitative (stronger) versions of their assumptions. They also experiment against the current best algorithms and establish that their estimator performs as well and sometimes better than the current estimators. I think this is a good paper and vote for acceptance.", "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": "10"}, "extra_text": {}}, {"review_id": "tv5HGeCHOLd", "reviewer": "Reviewer_sG1J", "summary": "This paper considers learning DAGs from iid sampled data without specific distributional assumptions. The sample complexity is derived and is shown to be polynomial in the number of nodes. One advantage is that the faithfulness condition that is often assumed in this line of work is no longer required. ", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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+ Graphical model selection is an important problem in statistical learning. Deriving tight sample complexity bounds is of paramount interest in understanding the fundamental limits of this task.\n\n+ The algorithm seems natural and the analysis seems correct from what I checked. \n\nWeaknesses:\n\n- The assumptions appear to be too strong. In particular, Condition 2 requires that H(X_k | pa(k)) = h^* does not depend on k. The authors claim that their method works for models without specific distributional assumptions. However, this precise entropy condition violates the claim. This condition is just too strong for any real-world graphical model.\n\n- The sample complexity bound seems to be too weak. The dependence on d (as a quadratic term) is too strong and thus, the algorithm and results do not work well in the high-dimensional regime, a basic requirement. \n\n- This would have been mitigated if the authors attempted to derive a lower bound in the absence of the faithfulness condition as assumed the PC algorithm. However, the fact that there's no lower bound in the paper dilutes the overall contribution. \n\n- The numerical experiments are weak. We cannot observe the dependence of the sample complexity on d^2. The improvement in performance compared to PC is not evident. \n\n- As a suggestion to the authors for a future submission, the authors can consider a particular example that corroborates their claim that the algorithm herein works without the faithfulness assumption by running experiments such that PC fails but the algorithm herein works. This would be really illustrative and useful for the community, and a convincing empirical demonstration of the utility of the work. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None. Theory paper. ", "review_text": "", "extra_scores": {"ethical_concerns": "None. Theory paper. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "R6DoEhLIsYA", "reviewer": "Reviewer_E5SA", "summary": "The paper develops a new algorithm for structural learning of directed acyclic graph with specific reference to bayesian networks.\nA theoretical argument is developed from which a structural learning algorithms is presented. \nThe algorithm consists of two main parts, one which put the learning problem in a general framework and the scond algorithm which can eventually be replaced by other state of the art algorithms.\nResults of numeirical experiments witness that the proposed structural learning algorithm, which works for discrete or continuous distributions without any distributional assumptions, performs the same as state of the art algorithms in the case where the number of learning observations increases.", "questions": "", "limitations": "", "rating": 6, "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": "Originality: \nThe paper is original because it proposes a new algorithm to learn the structure of bayesian networks from available data. The originality stands by the fact that the paper is based on ancestral formulation of the learning prolem and uses a greedy strategy to achieve optimality.\n\nQuality: \nThe paper is well structured and written. Terms are properly introduced and defined before using them.\nTHe paper reads very well and the narration is sensible while each piece of information isappropriately presented and discussed.\nI did not check the proof of theorems but according to theoremes in the paper, the author/s convinced me that their algorithm works.\n\nClarity:\nThe paper is clear, in other terms it is is clear the theoretical problem which is tackled and it is also very clear how the problem has been solved.\n\nSignificance: \nThe paper is extremely significant to the community of machin learning with specific reference to bayesian networks and causal networks. I personally think that the results preseted in the paper will be very useful for other scholars in machine learning and artificial intelligence.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I was not able to find any discussion about limitations of the proposed approach. \nThe paper devotes some space to potential extensions and future works but no mentions to critics of the proposed approach.\nThe impact to the reseach community could be good but this strongly depends on the capacity to show what can concretely be obtained in practical applications.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "L2tS8XnjFgs", "reviewer": "Reviewer_g49G", "summary": "In this work, the authors propose a novel identifiability condition/assumption for learning Bayesian network (BN) structures. They then describe an approach for BN structure learning (BNSL) which first identifies nodes in each layer of the DAG structure of the BN; a second algorithm is then used to identify the parents of each node by identifying its Markov blanket among its candidate ancestors (namely, all nodes appearing in an earlier layer). The identifiability condition is then used to show that the algorithms identify a minimal I-map. Detailed complexity analysis shows that the time and sample complexity are exponential in the size of the largest Markov blanket in the DAG, rather than the number of nodes.", "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": "--- Originality\n\nThe main novelty of the proposed work is in the new identifiability condition/assumption. The algorithms themselves are quite similar (or exactly the same) as well-known algorithms in the field. The identifiability assumption itself seems reasonable enough, though more implications of this assumption could be considered. Still, it leads to meaningful proofs on algorithmic and sample complexity.\n\n--- Quality\n\nI am not an expert in this area, and I have not thoroughly evaluated the proofs in the appendix. Nevertheless, the intuitions given in the main text seem plausible, and the overall technical quality of the theoretical work appears sound. I read through the python code; it hews closely to the same notation and structure as the algorithms as well as follows standard coding styles.\nAs the authors acknowledge, the empirical experiments are very minimal and do little more than show a proof of concept; still, though, the results for the proposed approach are quite bad for modest sample sizes and numbers of variables.\n\n--- Clarity\n\nThe paper is well-written. Various quantities and concepts important in the text are succinctly described. As hinted above described in “Limitations” below, though, the implications of the new identifiability assumption, particularly (C1), and violations thereof, are not clear to me.\n\n--- Significance\n\nBNSL is a widely-studied problem that has also been applied in various domains. Especially in domains such as biomedical where accurate modeling and limited samples sizes are common, the proposed approach provides a practical way to alleviate uncertainty due to the choice of algorithm.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "--- Originality\n\nAlgorithm 1 is very similar in nature to searching for topological orders/permutations (e.g., [Teyssier and Koller, UAI 2005], but many others as well), while Algorithm 2 is exactly (the forward pass of) IAMB. The new identifiability assumption ensures the greedy algorithms find an optimal solution, but the algorithms themselves are well-known.\n\n--- Quality\n\nThe experimental results in Figure 2 are rather disappointing. The main theoretical contributions are polynomial guarantees on algorithmic and sample complexity. However, the size of the networks is relatively small (only up to 50 nodes) while the number of samples is modestly large (at least 1000 samples). Further, the performance of the proposed approach is rather bad compared to simple baseline algorithms in several settings. I appreciate that the theoretical work is the main contribution, but the experiments do not do a good job of highlighting any strengths of this approach.\n\n--- Clarity\n\nAs a non-expert, it is difficult for me to understand the implications of (C1). It is unclear to me in what kinds of situations such an assumption may not hold. The authors mention that faithfulness is not important for this approach to work, but it is unclear to me what happens when this condition does not hold. For example, can the algorithm detect such cases? possibly with access to an oracle for the independence tests?\n\n--- Significance\n\nThe limited and poor experimental results, combined with the lack of clarity on one of the main assumptions in the work, could limit its impact.\n\n--- Minor comments, typos, etc.\n\nThe references are not consistently formatted\n\n“d_6” -> “h_6” (Section 3.2)\n\n“\\hat{h}_{jk}” is not defined in Algorithm 1, though is presumably the respective conditional entropy\n\n--- Societal impact\n\nNo obvious, direct societal impact.\n", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The final reviewer scores are borderline, with the merits being valuable contributions to the ongoing literature on Bayesian network learning (e.g., generalising the "equal variance" condition, which was a recent success case), but also some concerns.  After carefully discussing and considering these concerns, my overall recommendation is "weak accept".  The reasons are as follows:
- One concern was that Condition 2 is too strong.  However, this was largely a misunderstanding, and the authors did indeed already point out in the paper that the condition is *sufficient* for Condition 1, but that the latter is more general.  Addressing this potential confusion should only be a minor change, e.g., Condition 2 could be labeled with (Sufficient Condition for Condition 1), or changed to regular text (instead of bold-headed environment), etc.
- Another concern was that the d^2 dependence seems high and there are no lower bounds to compare against. However, this dependence appears even in simpler settings (e.g., assuming linearity), and lower bounds are largely open, so insisting on these may be asking too much. Overall, this setup appears to be much more of a work in progress compared to learning undirected Markov Random Fields, so it is natural that more gaps still remain.  Having said this, the authors should carefully compare to the most related works (as they partly did in the discussion) in the revised paper, as currently the related work seems to be written without enough emphasis on the relevant sample complexities and assumptions.  Please also highlight the relevant limitations/gaps/open problems carefully.

Beyond these specific points, I ask the authors to carefully consider all reviewer comments when editing the paper.
Decision: Accept (Poster)