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": "odzSem-cdD6", "reviewer": "Reviewer_aYyX", "summary": "The paper studies the problem of learning the Bayesian network structure of $d$ random variables in the fully observational case.\n\nAmong the main contributions, the authors propose:\n\n1. A novel identifiability condition for BN structure learning which does not require the typical faithfulness condition. This new condition is based on conditional entropies of the random variables given their ancestors.\n\n2. Motivated by the proposed conditions in Theorem 3.1, authors show Algorithm 1 to learn the BN structure, which is based on estimating the Markov boundary of each node with respect to its ancestor set. \n\n3. Computational and statistical complexities are discussed, and they are polynomial when the maximum Markov boundary size is $O(\\log d)$.\n\n4. Some synthetic experiments are provided and the proposed method is compared against the classical PC and GES algorithms.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Here I present my review along the axis of the NeurIPS reviewing guidelines:\n\n**Originality**\n\n- Are the tasks or methods new? \n  - The most novel contribution relates to Theorem 3.1, which is the identifiability condition based on conditional entropies. Under this condition, faithfulness is not required which I find appealing.\nThe proposed algorithm for learning the structure is not quite novel  on its own in the sense that there are existing work that also learn the network in a layer-wise fashion; similarly, as stated by the authors, learning the Markov boundary has also been studied before.\n\n- Is the work a novel combination of well-known techniques?\n  - Given the new identifiability condition, I think Algorithm 1 can be regarded as a novel combination of known ideas for learning the BN structure. Moreover, the algorithm requires several estimations of conditional entropies, for which the authors use existing estimation techniques.\n\n- Is it clear how this work differs from previous contributions? \n  - Yes. The main contrast to previous work is with regards to the identifiability condition. \n\n- Is related work adequately cited?\n  - Yes, although I believe there are some lines of work that have not been commented whatsoever. For instance, learning BN structures from continuous optimization has gained much attention in recent years but they are not been mentioned.\n\n\n**Quality** \n\n- Is the submission technically sound? \n  - Yes, claims are sound. \n\n- Are claims well supported (e.g., by theoretical analysis or experimental results)? \n  - Yes, proofs are provided in the appendix. I have checked most of them and could not find major issues.\nSynthetic experiments are also provided although I do not find them convincing.\n\n- Are the methods used appropriate? \n  - Yes.\n\n- Is this a complete piece of work or work in progress? \n  - Complete work.\n\n- Are the authors careful and honest about evaluating both the strengths and weaknesses of their work?\n  - Yes. Although some important discussion could be missing. See my questions at the end.\n\n\n**Clarity** \n\n- Is the submission clearly written? \n  - Yes. I was able to follow the contributions without any problems. Can be improved, see last section of my review.\n\n- Is it well organized? \n  - Yes.\n\n- Does it adequately inform the reader? \n  - Yes.\n\n\n**Significance** \n\n- Are the results important? \n  - I believe the identifiability condition is interesting and important. The algorithm is also compelling; however, I do have some questions that would like to be addressed. See below.\n\n- Are others (researchers or practitioners) likely to use the ideas or build on them? \n  - Maybe. There are open questions that some researchers might find interesting to study.\n\n- Does the submission address a difficult task in a better way than previous work? \n  - Unclear. The experiments are not convincing on this.\n\n- Does it advance the state of the art in a demonstrable way? \n  - No. Relying in the experiments shown, the proposed seems to be at best comparable.\n\n- Does it provide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach?\n  - The work is mainly theoretical with a small set of experiments.\n\n# Questions / Comments\n\n1. One of the main arguments of the new identifiability condition is that it applies to general distributions without parametric assumptions. However, the conditions are given in the population case. I believe that the set of unfaithful distributions has Lebesgue measure 0 in the population case. What would be the advantage of the new condition against faithfulness if it is given in the population setting?\n\n2. In Lines 92-93 it is stated that the proposed approach highlights the role of fundamental assumptions obscured in the linear case. Can authors elaborate on this? I could not find a proper discussion of this claim in later sections of the paper.\n\n3. It is not until page 7, line 261, where one notices that there is a \"sparsity\" assumption of $M \\leq \\log d$. I believe this is an important assumption that should be stated in the abstract and contributions section. If this assumption does not hold, the sample and time complexity are exponential.\n\n4. Right before line 835, the error bound is confusing to me. Does it decay?\n\n5. The experiments are unconvincing. First, the method seems to work worse than PC and GES in the low sample complexity regime, which is an important drawback. Also, as the number of samples increases, the proposed method is at best comparable. Both reasons undermine the usability of the method in practice. Second, given the sample and time complexity results, it would be interesting to see the log-dependence/phase-transitions plots. Finally, it would help to compare against methods that provide guarantees such as that of Ghoshal & Honorio.\n\nMinor typos/comments:\n\nLine 135: it would perhaps help to define $\\lceil a \\rceil^+ \\equiv \\max (a,0)$, and use $\\lceil L(X_k) - 2 \\rceil^+$ to avoid $L(X_k) - 2$ being negative. \n\nLine 191: it says \"we use apply...\"\n\nLine 254: it says \"...any any..\"\n\n---\nI thank the authors for their response. I feel more positive about the paper and will increase my score to 6. I think that the paper could benefit by adding some points of this discussion.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors have discussed some limitations of their methods. Being the work of theoretical nature, I do not foresee any negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Vp5BPQUNNje", "reviewer": "Reviewer_YmV1", "summary": "Learning Bayesian networks is a notoriously difficult task, considering the fact that the search space for all possible graphs scales exponentially with the potential arcs. In the paper, authors propose a heuristic search algorithm which reduces the time complexity of well-known exact algorithms such as PC. PC is a constraint-based algorithm which recovers Bayesian networks based on the conditional independencies entailed by the nodes of the graphs. Whereas the methodology proposed in the paper makes an additional information theoretical assumption for the structure of the graph, i.e. the conditions stated in the paper, which effectively reduces the search space of valid graphs for the given nodes and enables us to make use of a greedy search algorithm.", "questions": "", "limitations": "", "rating": 5, "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": "Paper is easy to read and very well written in general. Assumptions, theorems, derivations, and algorithms are stated in full clarity. Authors also demonstrate their algorithm on a toy example, which is very helpful for understanding the main principles of the algorithm. I think such a paper will be of interest to NeurIPS community.\n\nThe main contribution of the paper is the information theoretical conditions that are proposed to narrow down the overall search space of graphs. In the first phase of the proposed methodology, a topological ordering of the nodes, i.e. the layers of the underlying graph, is found using these conditions. Once the topological ordering is found, the rest of the graph search becomes straightforward, Namely, the edges between the layers of the graph are searched using the conditional independence properties.\n\nHowever, any topological ordering enforced on a graph would yield a search procedure with the same efficiency as the methodology in the paper. Indeed, one could change the conditional H with any functional F, say negative H, and would still come up with a unique DAG, because there is nothing specific to H in the proposed methodology. So, I believe the selection of H needs further justification, e.g. how does the selected criteria relate to the actual topological ordering of the nodes? What are the advantages of choosing H for narrowing down the search space rather than a more general functional F?\n\nAdditionally, it is not perfectly clear to me that why the size of largest markov boundary can be assumed less than logarithm of the number of nodes. This is a critical assumption for calculation of the polynomial time complexity stated in the paper, and I think an addittional justification for this would be helpful, too.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I haven’t seen a part where the limitations and the social impact of the work are mentioned.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "OguwdBU8Dn", "reviewer": "Reviewer_Wj5d", "summary": "The authors present several novel results regarding learning of discrete graphical models.  They introduce a conditional entropy-based identifiability condition that allows one to decompose an unknown directed acyclic graph (DAG) structure into different layers.  They introduce another entropy based measure to allow them to efficiently locate the markov boundary of nodes in each layer without backtracking or pruning.  These two results are combined to develop a novel algorithm for learning a DAG from sample data.  The authors demonstrate the correctness of the proposed algorithm by empirically verifying that the procedure recovers the expected graphs when the required assumptions are met.  Finally, they introduce a sample complexity result for how quickly one can recover the minimial IMAP G, as a function of the number of nodes and number of layers in the DAG.  \n\nThese contributions seem significant and, to the best of my knowledge, are novel.", "questions": "", "limitations": "", "rating": 7, "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": "My main question/criticism for the authors is how likely are conditions 1 and 3 to be met in practice and what happens to the proposed procedure when these conditions are not satisfied? Do you empirically get sensible results, or results on par with other learning algos, when running on graphs that don't satisfy this criteria?  If condition 3 is relaxed, do you simply lose the sample complexity guarantee?\n\nThe proposed algorithm seems to perform worse than PC and GES for small sample size and larger number of nodes. Can you provide any color as to why this is the case?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "97Cfx7IbFXw", "reviewer": "Reviewer_kVE1", "summary": "It analyzes the complexity of learning directed acyclic graphical (DAG) models from observational data.  It proposes an algorithm that uses a local Markov boundary search to learn an identifiable DAG G from samples. They prove an identifiability result on DAG learning. Roughly speaking, this condition requires that the entropy conditioned on an ancestral set of each node in G is dominated by one of its ancestors (Condition 1). They, also derive sample complexity of their algorithm and further illustrate its performance in a simulation study. ", "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": "It studies an interesting and important problem in causal structure learning. \n\nThe paper is well-written but more explanation about the role of Masked set in Algorithm 1 would improve its readability. \n\nThe theoretical results especially the sample complexity results are quite valuable and could be beneficial\n to the researchers in this field. \nHowever, my main concern is about the conditions under which the results are presented and also the performance of the proposed algorithm. \n\nAlthough, it is discussed that C1 is a generalization of equal entropy condition but having C1 or PPS condition heavily depends on the underlying structural equation model (SEM) that generates the data. Moreover, how verifiable are these conditions given observational data? \nWhat type of systems would satisfy conditions 1 and 2? For instance, linear with non-Gaussian systems etc. \n\nAlthough the authors claim that their approach does not directly assume faithfulness but having conditions 1 and 3 somewhat encourages similar phenomena (I do not suggest that these conditions and faithfulness are equivalent). It would be educational to see an example that violates faithfulness but satisfies the conditions 1 and 3. Is MOD model in the experimental section an example?\n\nA brief discussion about the result of proposition 4.1. is required. For instance, when does the right-hand-side of the equation in this proposition is positive? It seems that often (e.g., for Erdos-Renyi graphs) this bound is trivial, i.e., it is negative. Clearly, it depends on the parameters.  \n\nGiven the experimental results, the proposed algorithm performs often as good as PC and GES in large sample sizes but for smaller sample size (1000) it often performs poorly. How does Algorithm 1 compare to the others in terms of run-time and computational complexity? Also, it is important to see (e.g., empirically) how tight is the proposed sample complexity in Theorem 5.1.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. Please see my comments.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "7ii2c6N2KLr", "reviewer": "Reviewer_WuUC", "summary": "The paper proposes a polynomial time algorithm for learning very sparse DAGs (constant maximum Markov blanket size) from observational data under a new identifiability condition that generalizes some of the existing identifiability condition (especially for the linear Gaussian case). The authors also derive sample complexity of their algorithm which has logarithmic dependence on the number of variables but unfortunately exponential dependence on the maximum MB size. The strengths of the paper are that the authors make no distributional (e.g. Gaussian) or functional (e.g. linear additive model) assumptions for deriving their identifiability condition and the associated algorithm. The algorithm learns a DAG layer-wise and there is a novel masking strategy due to which they identify the layers without requiring that all the nodes have the same conditional entropy. The paper advances the identifiability theory of general Bayesian networks and proposes a novel algorithm. However, even though the method is general and the assumptions are purely information-theoretic, it is not clear if the identifiability condition is useful beyond the linear Gaussian case — non-linear additive noise models and linear non-Gaussian (LinGAM) models are identifiable without any stringent conditions. Furthermore, the exponential dependence of the sample and computational complexity on the MB size is problematic, the experiments are not very strong, and lastly the presentation is too dense and unintuitive. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\n\n1. General algorithm and no distributional assumptions. The authors do not even assume additive models. The conditions are fully information-theoretic.\n2. The core idea is novel: that once you have identified 0 to j layers, in order to identify the (j+1)-th layer we don't need every node after the (j+1)-th layer to have larger conditional entropy than the nodes in the (j+1)-th layer (whose parents have been identified and hence the conditional entropy is the entropy of the exogenous/noise variable in an additive model). As long as there is one node in the (j+1)-th layer for which this condition is satisfied, we can mask out it's descendants.\n\n## Weakness\n\n- Why not just use the PC algorithm to first estimate the skeleton ? Then, for a node $X_i$, the intersection of its neighbors (in the skeleton) with the layers identified so far should give its parents.\n- The current algorithm's computational and sample complexity is exponential in the maximum size of a node's ancestral Markov blanket (M). Whereas the PC algorithm's computational complexity is exponential in the tree-width and sample complexity is polynomial in the maximum neighborhood size (\"Estimating High-Dimensional Directed Acyclic Graphs\nwith the PC-Algorithm\", Kalisch and Buhlmann). In addition the PC algorithm doesn't need Condition 3. The PC algorithm doesn't make any distributional or functional assumptions and only requires faithfulness to identify the skeleton.\n- How does the identifiability condition fit with existing identifiability results ? We know it generalizes the identifiability condition of Ghoshal and Honorio 2018 (GH2018) and equal variance condition for linear Gaussian case. But we know that linear non-Gaussian (LinGAM) models are identifiable and non-linear additive noise models are identifiable. Polynomial time algorithms exist for both these cases (ICA based method for LinGAM and RESIT for non-linear ANM). For LinGAM and non-linear ANM models the proposed identifiability condition is very strong and is only sufficient but not necessary. In spite of making no distributional and parametric assumptions, looks like the only case where it is useful is linear Gaussian case.\n- The presentation can be significantly improved. Notation is too dense and confusing\n    - Rather than saying 'the \"$X_i$\" for \"$X_k$\"' introduce a term for their relationship and use that.\n    - Say what \"testing and masking\" means\n    - Line 176: $d_6$ should be $h_6$.\n    - Line 177: \"$h_3 < h_{[4:6]}$ and $h_5 < h_6$  imply condition 2 doesn't hold here\". Why ? Condition 2 is about conditional entropy of a node given parents, where $h_3, ..., h_6$ are marginal entropies.\n- Somehow identifiability condition doesn't significantly relax the identifiability condition of GH2018 for linear SEMs. For a fully connected DAG (i.e. whose skeleton is a complete graph) it looks like the two identifiability condition are the same. The identifiability condition is significantly weaker than GH2018 only for very sparse graphs.\n- Experiments: running time comparison with PC and GES (surprisingly GES does well even in spite of returning a local optima).\n- Experiments: no experiments when identifiability condition is not satisfied. So it is not clear if how often the condition is satisfied for sparse and dense graphs.\n- Experiments: Even when the identifiability condition is satisfied the algorithm doesn't significantly out-perform PC or GES. Why ? This is in spite of the fact that the proposed algorithm specifically exploits the condition. Does the SHD go to zero as the number of samples is further increased ?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

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

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