Learning Linear Polytree Structural Equation Model
Authors: Xingmei Lou
Yu Hu
Xiaodong Li
Venue: Accepted by TMLR ()

Abstract: We are interested in the problem of learning the directed acyclic graph (DAG) when data are generated from a linear structural equation model (SEM) and the causal structure can be characterized by a polytree. Under the Gaussian polytree models, we study sufficient conditions on the sample sizes for the well-known Chow-Liu algorithm to exactly recover both the skeleton and the equivalence class of the polytree, which is uniquely represented by a CPDAG. On the other hand, necessary conditions on the required sample sizes for both skeleton and CPDAG recovery are also derived in terms of information-theoretic lower bounds, which match the respective sufficient conditions and thereby give a sharp characterization of the difficulty of these tasks. We also consider the problem of inverse correlation matrix estimation under the linear polytree models, and establish the estimation error bound in terms of the dimension and the total number of v-structures. We also consider an extension of group linear polytree models, in which each node represents a group of variables. Our theoretical findings are illustrated by comprehensive numerical simulations, and experiments on benchmark data also demonstrate the robustness of polytree learning when the true graphical structures can only be approximated by polytrees.

Published in Transactions on Machine Learning Research (03/2025)
Learning Linear Polytree Structural Equation Model
Xingmei Lou Deportment of Statistics University of California, Davis Davis, CA 95616, USA
smlon@@uedaais. edu
Yu Hu
mahyChust.h
Department of Mathematics ond Division of Life Science The Hong Kong University of Science and Technology Clear Water Bay, Hong Kong S.A.R.
Xiaodong Li Department of Statistics University of California, Damis Davis, CA 95616, USA
zdgli@ucdavis. edu
Reviewed on OpenReview: https: // openreview. net/ forum? id- N28FdY02sH
Abstract
We are interested in the problem of learning the directed acyelic graph (DAG) when data are generated from a linear structural equation model (SEM) and the causal structure can be characterized by polytree. Under the Gaussian polytree models, we study sufficient conditions the sample sizes for the well-known Chow-Liu algorithm both the skeleton and the equivalence class of the polytree, which is uniquely represented by a CPDAG. On the other hand, necessary conditions on the required sample sizes for both skeleton and CPDAG recovery are also derived in terms of information-theoreti lower bounds, which match the respective sufficient conditions and thereby give a sharp charac- terization of the difficulty of these tasks. We also consider the problem of inverse correlation matrix estimation under the linear polytree models, and establish the estimation error bound in terms of the dimension and the total number of v-structures. We also consider tension of group linear polytree models, in which each node represents group of variables. Our theoretical findings are illustrated by comprehensive nunerical sinulations, and exper- iments on benchmark data also demonstrate the robustness of polytree learning when the true graphical structures can only be approximated by polytrees.
exactly recover
1 Introduction
Over the past three decades, the problem learning directed graphical models from i.id. observations of a multivariate distribution has received an enormous amount of attention since they provide a compact and flexible way represent the joint distribution of the data, especially when the associated graph is a directed acyclic graph (DAG), which is directed graph with directed cycles. DAG models popular in practice
with applications in biology, genetics, machine learning, and causal inference (Sachs et al. 2005 Zhang
ct al. 2013 Koller & Friedman 2009 Spirtes et al. 2000). There exists extensive litcrature on learning the graph structure from i.i.d. observation under DAG models. For a summary, see the survey papers by Drion & Maathuis (2017) and [einze- Deml et al. 2018). Existing approaches generally fall into two categories, constraint-based methods (Spirtes al. 20000 Pearl 2009) and scoro-based methods [Chickering 2002b). Constraint-basee methods utilize conditional independence tests to determine whether there exists an edge between two nodes and then orient the edges in the graph, such that the resulting graph is compatible

---

Published in Transactions on Machine Learning Research (03/2025)
with the conditional independencies determined in the data. Score-based methods formulate the structure learning task optimizing a score function based on the unknown graph and the data.
A polytree is a connected DAG that contains no cycles even if the directions of all edges are ignored. It is practically useful due to tractability in both structure learning and inference. To the best of our knowledge, structure learning of polytree models was originally studied in Rebane & Pearl (1987), ; in which the skeleton of the polytree is estimated by applying the Chow-Liu algorithm (Chow & Liu 1968) to pairwise mutual information quantities, a method that has been widely used in the literature of Markov random field to fit undirected tree models. Polytree graphical models have received significant amount of research interest
both empirically and thcoretically ever since, sec, o.g., Dasgupta (1999): Cheng ct al. (2002). and recent
efforts such as Chatterjee & Vidyasagar 20022; Tramontano et al. 2022).
This paper aims to study sample size conditions of the method essentially proposed in Rebane & Pearl (1987) for the recovery of polytrce structures by applying the Chow-Liu algorithm to pairwisc sample correlations in the case of Gaussian linear structure equation models (SEM). We establish sufficient conditions on the sample sizes for consistent recovery of both the skeleton and equivalence class for the underlying polytree structure. On the other hand, we will also establish the necessary conditions on the sample sizes for these pnormaaiin-thhoreti lower bounds. Our sufficient and necessary conditions match in
two tasks through order in a broad regime of model parameters, and thereby characterize the difficulty of these two tasks in polytree learning.
A relevant line of research is structure learning for tree-structured undirected graphical models, including both discrete cases (Heinemann & Globerson 2014 Bresler & Karzand, 2020; Netrapalli et al. 2010 Anand-
kumar al.] 2012b a) and Gaussian cases (Tan ct al. 2010 Tavassolipour et al.) 2018) Nikolakakis et al. Katiyar et al. 2019 In particular, conditions on the sample size for undirected tree structure learning via the Chow-Liu algorithm have been studied for both Ising and Gaussian models (Bresler & Karzand, 2020 Tavassolipour et al. 2018 Nikolakakis et al.] 2019). and the amalyses usually rely crucially on the so-called "correlation decay" property over the true undirected tree. The correlation decay properties can usually be explicitly quantified by the pairwise population correlations corresponding to the edges of the underlying true tree. Based on this result and some perturbation results of pairwise sample correlations to their population counterparts, sufficient conditions on the sample size for undirected tree recovery with the obtained.
2019
Chow-Liu algorithm can be
In order to apply the above technical framework to study the sample size conditions for polytree learning, a natural question is whether we have a similar correlation docay phenomenon for the polytree models. In fact, this is suggested in the seminal paper Rebane& & Pearl (1987). ). To be concrete, under some non-degeneracy assumptions, has been shown in Rebane & Pearl (1987) (sce their Eq. 13) that there holds a "mutual information decay" along the skeleton of the polytree. In broad terms, the mutual information decay is direct implication of the well-known "data processing incquality" in information theory (Thomas & Joy 2006). Restricted to the very special case of Gaussian linear SEM, the mutual information decay is indeed equivalent to the property of population correlation decay.
To obtain some meaningful sample complexity result, we need to quantify such correlation decay explicitly as what has been done in the study of the Chow-Liu algorithm for undirected tree models (Bresler & Karzand 2020 Tavassolipour et al.] [2188 Nikolakakis et al., 2019). The mutual information docay given in Rebane & Pearl (1877) holds for general polytree models, but one can expect. to further quantify such decay under more specific models. In fact, if we restrict the polytree model to linear SEM, by applying the well-known Wright's 's formula (Wright 1960 Nowzohour et al. 2017 Foygel et al. 2012), the population correlation decay property can be quantified by the pairwise correlations corresponding to the tree edges. With such quantification of correlation decay over the underlying polytree skeleton, we can apply the ideas from undirected tree structure learning to establish sufficient conditions on sample size for polytree skeleton recovery via the Chow-Liu algorithm. In broad terms, if the maximum absolute correlation coefficient over the polytree skeleton is uniformly bounded below 1, the Chow-Liu algorithm recovers the skeleton exactly with high probability if the sample size satisfics > ((log))/P Punn), where p is the number of variables and Pmin is the minimum absolute population correlation coefficient over the skeleton.
2

---

Published in Transactions on Machine Learning Research (03/2025)
To determine the directions of the polytree over the skeleton, the concept of CPDAG (Verma & Pearl captures the equivalence class of polytrees. We then consider the CPDAG recovery procedure introduced in Verma& & Pearl (1992) and Meek] (1995), which is a polynomial time algorithm based on identifying all the v- structures (Verma & Pearl 1991 Therefore, conditional on the exact recovery of the skeleton, recovering the a non-degenerale polytree model, a pair of adjacent odges form v-structure if and only if the two non-adjacent node variables in this triplet are independent, so we consider a natural v-structure identification procedure by thresholding the pairwise sample correlations over all adjacent pairs of edges with some appropriate threshold. In analogy to the result of skeleton recovery, we show that the CPDAG of the polytree can be exactly recovered with high probability if the sample size satisfies n > P(log))/PPaal necessary for skeleton recovery, while n > ((logp)) Pini)) is necessary for CPDAG recovery. This means that we have sharply characterized the difficulties for the two tasks. We briefly note studies on linear SEMs that do not assumc a polytree structure, such as Peters & Bühhmann (2014); Ghoshal & Honorio (2018). In these works, the authors make alternative assumptions to ensure the identifiability of the DAG, for instance, by assuming equal noise variances. For discussion of the general SEM literature, we refer the readers to Ghoshal & Honorio (2018).
1991
CPDAG is equivalent to recovering all v-structures.
Furthermore, by using Fano's method, we show that n > ((log)))(r))) p)/ is
The paper is organized as follows: In Section 2 we review the concepts of linear polytree SEM, Markov equivalence and CPDAG, and the polytree learning method based on the Chow-Liu algorithm. In Section 3 we give optimal sample size conditions for both the skeleton and CPDAG recovery, particularly in terms of the minimum correlation over the tree skeleton. In Section 4 we introduce version of PC algorithm adapted to the linear polytree models, and establish the same sample size conditions. In Section 5 we discuss method of estimating the inverse correlation matrix for lincar polytree models, and establish upper bound of estimation in the entry-wise & norm. Our theoretical findings are empirically demonstrated in Section 7 along with numerical results under some benchmark simulated data in the literature of DAG learning. A brief summary of our work and some potential future research are discussed in Section
2 Linear Polytree Models and Learning
This section aims to give an overview of the concepts of linear polytree SEM, equivalence classes characterized by CPDAG, and the Chow-Liu algorithm for polytree learning. Most materials are not new, but we give a self-contained introduction of these important concepts and methods so that our main results introduced in the subsequent sections will be more accessible to a wider audience.
2.1 Linear Polytree Models
Let G E) be a directed graph with vertex set V (1, and edge set F. We use i - E F to denote that there is a directed edge from node to node j in G. A directed graph with no directed cycles is referred to as a directed acyelic graph (DAG). The parent set of node j in G is denoted as Pa(j) = (i fieV: i i+je E E}. Correspondingly, denote by Ch(j) = (k: j + k E E} the children set of
Let æ i Xp! be a random vector where each random variable X; corresponds to node j V. The edge set E usually encodes the causal relationships among the variables. The random vector xr is said DAG G if its joint density function (or mass function) p(z) can be factorized according to G as p(x)= = IT = p(z)) where p(Z)|Ppa()) is the conditional moosity/probabilityy of X, given its parents X XPo(j) = [X,: : Pa(í)) We usually refer to (G)) as a DAG model.
to be Markov
Throughout this work, we restrict our discussion to an important sub-class of DAG models: linear structure equation models (SEM), in which the dependence of cach X, on its parents lincar with additive noise. The parameterization of the linear SEM with directed graph G = (V,E) would be
x,= Σ
+
Σ Bi + +G
for I,...,P. Ps
(1)
sEPa()
where
Big #0 if and only if i i E F,
3

---

Published in Transactions on Machine Learning Research (03/2025)
and all ej's are independent with zero mean. Let B [Byg] Rex and c ,e, cpl". can be represented as
Then the SEM
a = B' x + 6.
(2)
Denote Cov(z)= = E = [o,y E Rexp and Cov(c) Ω = Diag Upp) Here Z2 is diagonal since all additive noise variables are assumed to be mutually independent.
For any DAG, if we ignore the directions of all its directed edges, the resulting undirected graph is referred to as the skeleton of the DAG. A polytree is connected DAG whose skeleton does not possess any undirected cycles. The model (2) is referred to as a linear polytree SEM, if the underlying DAG is a polytree T == (V, E).
In this paper, we focus on the case of independent Gaussian noise 6i, so the model 2 can be also referred to as a Gaussian linear polytree SEM. A major purpose of this paper is to study the problem of polytree learning, i... the recovery of the equivalence class of the polytree T = (V, under the model (2) from
a finite sample of observations Z1. Ln, or equivalently the n x data matrix X = [.1,...., Fn We explain the concept of Markov equivalence classes in the next subsection.
2.2 Markov Equivalence and CPDAG
Let us briefly review the concept of Markov equivalence of DAGs. Note that each DAG entails a list of statements of conditional independence, which are satisfied by any joint distribution Markov G. Two DAGs are equivalent if they entail the same list of conditional independencies. In the present paper, the recovery of the equivalence class of DAG hinges on well-known result given in Verma & Pearl [199]] ): Two DAGs are Markov equivalent if and only if they have the same skeleton and sets of v-structures, where a v-structure is a node triplet i + k + j where and j are non-adjacent.
An important concept to intuitively capture equivalence classes of DAGs is the completed partially DAG (CPDAG): a graph K with both directed and undirected edges representing the Markov equivalence class of DAG G if: (1) K and G have the same skeleton; (2) K contains a directed edge + if and only if any DAG G' that is Markov equivalent to G' contains the same directed edge + j. The CPDAG of G is denoted as == Cc. Tt has been shown in Chickering [002a that two DAGs have the same CPDAG if and only if they belong to the same Markov equivalence class.
The following result provides some intuition on the CPDAG for polytree models.
Proposition 1. The undirected sub-graph containing undirected edges of the CPDAG of a polytree forms forest. All equivalent DAGs can be obtained by orienting each undirected tree of the forest into a rooted tree, that is, by selecting any node as the rool and selling all edges going away from it.
Proof. Each connected component of the undirected edges is sub-graph of the polytrce G's skeleton, thus is tree. If node of the tree also has directed edges, they must be oulgoing according to Line 6 of Algorithm 2 (Rule in Meek (. This means that when we convert each undirected tree into a rooted tree, it does not create any additional v-structures in the resulting DAG G'. So the original CPDAG is also the CPDAG of G", v.e. G' is equivalent to G. On the other hand, if G' is an equivalent DAG, for each undirected tree T in the CPDAG, let be a source node of T according to G'. Then T in G' must. be a rooted tree with i being the root to avoid having v-structures within T' (and hence contradicting with G' shares the same CPDAG), This shows that all equivalent class members can be obtained by orienting undirected trees into rooted trees and completes the proof.
j
2.3 Polytree Learning
The procedure of polytree learning we are considering in this paper has been in principle introdueed in Rebane & Pearl (1977). The key idea is to first recover the skeleton of the polytree by applying the Chow- Liu algorithm (Cho & Liu 1968) to the pairwise sample correlations of the data matrix. After the skeleton is recovered, we propose to recover the set of all v-structures via a simple thresholding approach to pairwise sample correlations. Finally, we recover the CPDAG by applying Rule introduced in Verma & Pearl (9922) and justified theoretically in Meek (1955).
4

---

Published in Transactions on Machine Learning Research (03/2025)
2.3.1 Chow-Liu Algorithm for Skeleton Recovery
The Chow-Liu tree associated with pairwise correlations, which is the estimated skeleton of the underlying polytree, defined below.
Definition 2 (Chow-Lie Liu tree associated pairwise sample correlations). Consider the linear polytree model
2 associated to polytree T (V, F),, whose skeleton is denoted as T (V, Let Tp denote the set of undirected trees over nodes. Given the data matrix X [xi,..., Fn. E Ruxp,
obtain the sample correation Pig between X, and X, for all 1 15 <i<s) S p. The Chow- Liu tree associated with the pairwise sample correlations is defined as the santiinuuu-reiighe spanning tree over the p nodes where the weights are absolute values of sample correlations:
arg max T=(V,8)ET, i-JE8
Σ lAol-
(3)
For treo-structured undirocted graphical models, it has been ostablished in Chow & Liu (1968) that the maximum likelihood estimation of the underlying tree structure is the Chow-Liu tree associated with the empirical mutual information quantities (which are used to find the maaiimm--wegght spanning tree). The rationale of applying Chow-Liu algorithm to polytree lcarning has been carcfully explained in Rebane & Pearl 1987.. to which interested readers are referred. The step of skeleton recovery can be summarized in
Al Algorithm
Algorithm Chow-Liu algorithm
Input:
The data matrix X = [2), [.l..... xn]]
Output:
Estimated skeleton T.
1: Compute the pairwise sample correlations Dig for all si<j
Construct maximum-weighh spanning tree using låtl as the edge weights, i.c., 7 defined in 3
It is noteworthy that Algorithm 1 can be implemented efficiently by applying Kruskal's algorithm Kruskal, 1956) to pairwise sample correlations |Aiý for the construction of maximum weight, spanning tree. The computational complexity for Kruskal's algorithm is known to be O(p² logp), which is generally no larger than that for computing the sample correlations, which is O(pPn).
2.3.2 CPDAG Recovery
In the second part of the procedure of polytree learning, we aim to estimate the CPDAG of the polytree model. Intuitively speaking, this amounts to figuring out all the edges whose orientations can be determined. The first step of this part is to identify all the v-structures. Under the polyiree model, any pair of non- adjacent nodes i and j with common neighbor form a v-structure + + j if and only if X; and Xj are mutually independent. We thus determine the existence of v-structure + + í when the sample correlation lβizl < Perit = T / /llog))/ /)/, where the choice of threshold or critical value is discussed in subsequent sections. After recovering all the v-structures, as aforementioned, it guaranteed in [eek (1995) that the CPDAG of the polytree can be recovered by iteratively applying the four rules originally introduced in Verma & Pearl (1992). However, given our discussion restricted to the polytree models, Rules 2, 3, and in Verma & Pearl (1992) and Meek (1995) do not apply. We only need to apply Rule 1 repeatedly. This rule can be stated as follows: Orient any undirected edge j - into j + k whenever there is a directed edge i + j coming from third node i.
These two steps in the second part of polytree structure learning are summarized as Algorithm
3 Main Results for Polytree Learning
In this section, we discuss sample size conditions for the recovery of skeleton and CPDAG under Gaussian linear polytree model T = E). We first establish a correlation decay property on the polytree skeleton (Temma 3 by applying the famous Wright's formula.
5

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 2 Extending the skeleton to CPDAG
Input: Estimated skeleton T, sample correlations P.y H,y's, tuning parameter Terit-
Output: Estimated CPDAG Cr.
for Each pair of non-adjacent variables i, with common neighbor k in T do if |pyl < Yerit (logp)/n then
3: replace k - with the v-structure - k j
4: end if
5: end for
In the resulting graph, orient many undirected odges as possible by repeatedly applying the rule: orient undirected edge j into j + whenever there is directed edge i - j for some i.
3.1 Preliminaries
First, the polytree learning method introduced in the previous section depends solely on the marginal corre- lation coefficients, and is thereby invariant to scaling. Therefore, without loss of generality, we can assume that Xý's have a unit variance all j E , Lee Σ is the correlation matrix. is obvious that the stan- dardized version of linear SEM is still a linear SEM, and they share the same polytree structure, In this case, by denoting the pairwise correlations as Ptj == corr(o,,r.... Xy),,
have dy = Pij for all 1 S.
Under the linear SEM, we know that B is permutationally similar to strictly upper triangular matrix, which implies that all eigenvalues of I - B are I's, and further implies that I - B is invertible. Then, e, (I - B) x implies æ (I B)TT, and further implies that æ is mean-zero, and has covariance
= (1 (I- - - B)
This suggests that we can represent the entries of Σ by (Big) and (wa). In fact, this can be conveniently achieved by using Wright's path tracing formula (Wright 1960). We first introduce some necessary definitions in order to obtain such expressions. A trek connecting nodes i and j a directed graph G (V, E) is a sequence of non-colliding consecutive edges connecting andd j of the form
i= - v/-1
+ of 20 + u
We define the left-hand side of r as Left(T) = of uR, and the head of as H, uo. A trek is said to be simple trek if Left(r) and Right(r) do not have common edges. In the polytree case, any two nodes (i,j) are connected by unique path. Also, Wright's famous formula has simple form:
+ vo, the right-hand side of T as Right(T) = to
Lemma 3. Consider the linear polytree model with the associated polytree T (V,E) p nodes. Also assume that Xj has unit variance for all j E Then, Pij Bij for all + E E. Furthermore, for each pair (i, the population correlation coefficient salisfies
II Pst e-tEEr
the palh connecting and j is simple brek
Pij
(4)
otherwise.
Also, the noise variances salisfy
=1
Σ Pigz j= j= SEPa()
(5)
Remark 4. The assumption that the variables XI,...,X, have unit variances is unnecessary for 44 alone, since correlation coefficients invariant under standardization.
Remark 5. Here Eqm.
5 can be derived by the following simple argument: Since T is polytree, all variables in Pa(j) are independent and also independent with E,. Evaluating the variance both sides of X, Σ Xi + ej leads to iEPal)

---

Published in Transactions on Machine Learning Research (03/2025)
We now introduce the following definitions.
Definition 6. In standardized linear polytree model (2) let Pmin and Piax be the minimum and marimum absolule corvelation over the bree skeleton, that is
Pmin = min lpsl
Pmax = max lpgl- 1ーjEE
It is noteworthy that in general we cannot assume that Pmin is independent of or p. In fact, Equ. 5 gives rise to the following relationship between the noise variance and the correlation coelficients with parents for each node: Σ Pīj < L, which further implies the following corollary.
iEPa(5)
Corollary 7. Let d. represent the highest in-degree for polytree. Then Pmnin VVa--
Remark 8. In contrast, it is reasonable to assume Pmin to be a positive constant independent of p under the undirected tree-structured Gaussian graphical model, since after transforming it to a rooted tree as in Section 2. the highest in-degree salisfies d. 1.
A key lemma the following well-known convergence rate for estimating the population correlation matrix: Lemma 9. Consider a Gaussian linear SEM (2 with 2 Co logp for some numerical constant. Co- Then, on an event with probability least
1/p², the following inequality holds for some absolute constant C:
logp
P - pllmax <CV
where p and p denote the population and sample correlation matrices, respectively, and || llmax represents the entrywise supremaum norm.
Proof. This is well-known result, which can be obtained by combining Remark 5.40 of Vershynin 2012 and Lemma 1 in Kalisch & Bühlman 2007) (reproduced in Appendix See also the proof of the generalized version of this result, Lemma 26
3.2 Skeleton Recovery
First, we introduce an important result in analyzing the Chow-Liu algorithm:
Lemma 10 (e.g. Bresler & Karzand (2020), Lemma 6.1 and Lemma 8.8). Let T be the skeleton of true polytree T = (V, E) and T be the estimated tree through Chow-Liu algorithm (3) If an edge (w, 1)) T and (w, i T, i.e. this edge incorrectly missed, then there ewists an edge (v, 8) T and (v, ū) $ T such that (w, @) pathT(u, 8) and (v, ü) E pathe(w, w. On such an error event, we have lèvel 2 pwwal.
We now introduce sufficient condition on the sample size for skeleton recovery under the Gaussian linear polytree model, in which the independent noise variables satisfy cj NN wjj) for j -,.... .. Then by x = (I- B)- we know that æ is also multivariate Gaussian. This fact will help quantify the discrepancy between population and sample pairwise correlations as characterized in Lemma 9
Theorem 11. Consider Gaussian linear SEM (2) associated to polytree T = (V, E) with Pmax < 1 1 8.
Denole by F the estimated skeleton by the Chow- Liu algorithm (Algorithm 1), and by T the brue polytree skeleton. Then, the event & with probability at least 1 - 1/p² defined in Lemma g we have exact polytree skeleton recovery T =T as long as
140
logp
(6)
82
P
where C is as defined Lemma
Proof. Consider any undirocted odge (w, w) T and any non-adjacent pair (u, ö) such that (w, () e (v, i),, where pathy (v, 8) is the path connecting and in the polytree T. If pathr(u, 0) is a simple trek, then the correlation decay property, Lemma implies that Pes consists of the product among several
7

---

Published in Transactions on Machine Learning Research (03/2025)
correlation coefficients containing Pwr. Hence lpuel S PPw |PwalPmax- |Pmax. On the other hand, if pathr (v, 8) is not simple trek, then we have Peá = 0. Overall, we can obtain an upper bound for |peal |Pwnl
ppel - IPwal - P (Pmax - 1) f 8pmin.
Then, on the event &, uniformly for any undirected edge (w, v)) E T and any non-adjacent pair (v,0) such that (w, u) pathT (v, i), there holds
|o - IPwnzl S Iios - Pool + 1pwr - Pwrl + |pool - |Pww
2C / (logg)/g 8pmin <
where the last inequality is due to the condition E.
Then, Lemma
10 implies that 7 = T on the event
Remark 12.
Our argument on skeleton recovery basically follows the standard arguments based on cor- relation decay over skeleton in the literature of undirected tree learning, e.g-, Niikolakaiis et al. (2019); Tavossolipour et al.) (2018); [rester E Karzand (2020). On the other hand, treating undirected tree models rooled polyiree models, our sample size condilion for skelelon recovery in Theorem 17 is O(log)), which is the optimal sample size condition for undirected tree recovery.
Remark 13. The above condition implies some dependence of the sample size on the marimum in-degree dy. In fact, together with Corollary 7 the sample size condition is essentially n 2 O(d, log if Pmin x 1/vd..
3.3 CPDAG Recovery
As described in Section 2.3.2 after obtaining the estimated skeleton, the next step is to identify all structures by comparing Psy for all node triplets i i- k - j in the skeleton with a threshold Perit Then the orientation propagation rule described in Algorithm 2 can be applied iteratively to orient as many undirected edges as possible. If both the skeleton and v-structures are correctly identified, the orientation rule will able to recover the true CPDAG, i.c. the equivalence class (Meck) 1995).
Theorem 14. Consider Gaussian linear SEM (2) associated to a polytree T -V, E) with Pmax Denote by T and Cr the estimated polytree skeleton from Algorithm 1 and CPDAG from Algorithm @ with threshold Yorit / /logg)//. Also, denote by T and Cr the true polytree skeleton and the true polytvee CPDAG, respectively. Then, on the event & with probability at least 1-1/p² defined in Lemma we have exact polytree skeleton recovery T T as well as exact polytree CPDAG recovery Cr C as long as
logg
Yorit C and Co(E))ere
Pmin
where C is as defined Lemma and Co( is a constant only depending on 6.
Proof. Since the skeleton recovery is guaranteed by Theorem II it suffices to show that under the condition
all v-structures are correctly identified on the event Let's consider all node triplets i h: in T. If the ground truth is k + j, we know that Psy 0. Then, by 7 on & we have
|pol S C (logp)/n < Nowv (logp)/n.
This means the v-structure is identified by Algorithm 2
In contrast, if the ground truth is i + & + j or i + + or i + k + j, the correlation decay property Lemma 3 implies that |pig = |pad layl 2 Paann Then, on E, there holds
|a 2 |pg| CVogoo 2 P CV > Ver' (logp//n,
where the last inequality is also due to 7 This means this triplet is correctly identified as a non-v-structure.
In sum, we identify all the v-structures exacctturussecccyy..y... Then the CPDAG of T can be exactly recovered by Algorithm as guaranteed in Meek (1955).
8

---

Published in Transactions on Machine Learning Research (03/2025)
Remark 15. It is noteworthy to observe the difference between the sample size conditions in Theorems 11 and 14 In particular, if Pmiin = x1/Vd,, the above sufficient. condition sample size for CPDAG recovery is essentially n 2 (dd, logp), while recall that the sample size condition for skeleton recovery is 2 Od,, logp). This dependence on marimum in-degree is probably a particulor property for polytree learning. given that most existing theory on general sparse. DAG recovery usually requires the sample size to be greater than the marimum neighborhood size, e.g., Theorem in Kalisch & Bühhman (007))
3.4 information-theoreee Lower Bounds on the Sample Size
In this subsection, we will establish the necessary conditions on the sample size for both skeleton and CPDAG recovery under Gaussian linear polytree models. In particular, we will use Fano's met to derive information-therrett bounds.
Theorem 16. Let T(pml)) be a collection of Gaussian linear polytree models, such that Pmin = min;-jjeF Pigl is fized and satisfies 0 < Pmin < 1/vP. In each model out of this class, assume that Pmax = + IPisl < 1/2. Assume 2 10. Suppose that T(mmi) is indezed by O, with correspond- ing polytree To, covariance matrix Eo, tree skeleton To, and CPDAG Cr.- Then for any skeleton estimator T, there holds
PE. (T(x) # To) 2 1/2
(Paii))
provided
<
- (logp=22] 2). Piin
Moreover, for any CPDAG eslimator C, there holds
sup PE, (C(()( # CT.) 2 1/2 (ET()m))
provided
1
1)(p (p-1)(p- - 2) -2) 22
(p
log
3p
2
Proof. The key idea is to apply Fano's method to appropriate sub-classes of (pminn) to establish the intended cooommation-theoetti lower bounds for both skeleton and CPDAG recovery. Generally speaking, let TM = (Ti...., Tar be a sub-class of polytree models T(Pmiu) whose respective covariance matrices are denoted as E(T))... ..., M. Let model index be chosen uniformly al random from {l,..., M). Given the observations X RRxx, the decoder v estimates the underlying polytree structure with maximal probability of decoding error defined
Perr (v)
max PI(TT) (V(X) * TT)). SSSM
Fano's incquality (Thmas & Joy 2006 shows that the maximal probability of error over TM, Pore (V), be lower bounded as
inf Perr (v) 2 I(0: I(0;X)+
x)
log M
Given all involved distributions are multivariate Gaussian, we will apply the following entropy-based bound of the mutual information that can be found in Wang et al. (2010):
I(0: x) < n F(T), where
2
M logdet (E(T))
F(T)) = logdet ( D
(8)
M
and the averaged covariance matrix Σ = 1 E3 E(T,).
9

---

Published in Transactions on Machine Learning Research (03/2025)
Lower Bound for Skeleton Recovery
In the following we consider a class of polytree models TM = (Ti,..., .,M) where M = p-22 These polytrees share p - common directed edges + (p - 1), + (p - 1), (p 2) + (p - 1). For the (p - 1)-th directed edge, we let p - in Ti, - in T2, .... p + (p- 2) in Tp-2. Also, we assume that all variables have variance one, and the correlation cocfficients
the skeleton are all p that satisfies 0 p < 1 vp"
Here
we write p p= Pmmin for simplicity. Note that the polytrees in this sub-class of T(p) (defined in the statement of Theorem 16 have distinct skeletons, 80
p=mmin
inf sup T (Emin)
Px (T(X) To) 2 inf max PE(T,) (x)( + T;)- I5JSM
We can easily obtain the formula for each covariance for Tj, we have
E(T,) for j l,... M by using Lemma 3 For example,
1 0
0
P P
0
1
0
0
:
A
B D
E(T))
=
B
0
0
1
0
7
P 0
0
p 0
0
p²
1
The Schur complement of A = I
is thereby
1
(p (p- 2p
0
D D D
1 1-
Then
det dct(E)(T)) (c)(A) -
B A (1 1101-p)11 p²) (p- 2)p²)
Similarly, for all j 1, ,......---- P- 2, there holds det [(T))) (1 (²) (1-1404 (p 2)2²) On the other hand, the average covariance is
0
0
p - 2) ]
P
p - 2)
2-2 E
Σ [TJ)) =
p- 5=1
P.
P/(p - 2)
P
P
1
1
p 2) pl(p 2)
p/(p 2)
p²
1
As with above, we can use Schur complement to obtain
dct Σ) (1 p²1(p 2)) (p 22)pp)
Plug these results into
8 we have
1p-3)p² F(TT) llog 1 (p- 2)(1 p22)
< 1)=3)p²
(p- 3)
S p²_ 2) 1/p)
(p 2) p2) (p
2). To ensure Perr 1/2, which is equivalent to (log(p- 2) 2)/p²
Then Perr 2
15 1)/ log(p-2).
1/2, we only need to require 1 1- (1p2+1)) log(p-gg)
Lower Bound for CPDAG Recovery
Let's now consider another class of polytree models Tm (T..... T where M = (2= All polytrees in this class are stars with hub node p, and p directed to all but two nodes in {1....,p 1}. In Ti the directed edges are 1 p. 2 P. p 3. p ... p (p 1). In T2, the directed edges P. P 2,
10

---

For example, for Published in Transactions on Machine Learning Research (03/2025)
3 - .... (p 1). And so until in TM. the directed edges p 1, p + ... p- (p 3). (p-2) (p - p. Also, assume that all variables have variance one, and the correlation coefficients on the skeleton are all that satisfies 0 < < 1. Again, we write p = Pmin for simplicity. Although the polytrecs in this sub-class of T(p) have the same skeletons, but they have distinct CPDAGs since they have distinct sels of v-structures. Therefore,
inf sup PED (C()) + CTo) inf max PX(T,) (v(X) # T3).
C BET(pmi))
ISSSM
Again, we have the formula for each covariance [T₃) for j = 1..... M by using Lemma 3 Ti, we have
1 p
P
p²
P
p p
P
E(T)) =
1
P
P
P
P
P
Recall that in linear polytree model there holds E (I-
BII (I-B)-
B). Since B can be transformed to
strict upper triangular matrix by permuting the p nodes, know that det B) 1. Then
det(E) = det( = II
II
1
Σ tEPaif)
p
2=1
5=1
Then for j == I,..., M, there holds det(E(T))) (1 32)p-3(11 (1-11111))) -2p²); which implies that
logdet (E(T)) (p 3) log(1 (1- p²) + log(11 -2p²).
On the other hand, we have
M-1
0
M-1
p² p²
M
Mr
M-1
M
M
Mf
A
B D
M E(T))=
Σ
B T
J=1
M 1
1
1
15
M
The Schur complement of D is
1 1²
2
1² /M
-0² /M
p²
/M
Σ/D = A BD- ==
P2/M P
p M
1- p²
11

---

Published in Transactions on Machine Learning Research (03/2025)
It's easy to obtain all the eigenvalues of Σ D: -
p+1 p-Ip" with multiplicity and 1
1p-1)lp 2) with
p(p-3)
multiplicity p p- 2. Plug these results into 8 we have
F(T) log
1 p 1
p² + (p (p-2p)
2) log
1
plp 3)
(p - 1)(p 2)
log(1 - 2p¹)
- (p- - 3) log(1
- 12))
log
p
1²)
+ (p- 2) log
+
6
+ log
1 - 2p²
p²
(p- 1) 2) 1 p2
++1
2
p²
p²
+
+
p
1
11
p2
1
2p²
p+1
2
p
2p
P
+
1 p²
1 2p
2
0²
2p
+
x5p"
p 11-
2p²
where the first inequality due to log(1 + x) S x, and the second inequality due to the assumption that p² < 1/4 and p 2 10. As with the case of skeleton recovery, know that Perr > 1/2 as long as we require that
1 5p4
log (p 1)(p 2) -22) 2)
we can conclude that our derived sufficient conditions on the sample sizes for the recovery of both skeleton and CPDAG are sharp.
Compare Theorem I6 with Theorems I and 14
4 PC Algorithm Adapted to Polytree Models
In this section, we introduce another algorithm to recover the skeleton and CPDAG of the polytree, which is adapted from the PC algorithm but amenable linear polytree structure.
To implement PC algorithm that is adapted to polytree structures, consider early stopping version of the hm explained in Kalisch & Bühlman (2007). The following lemma demonstrates important properties of marginal and conditional probabilities on polytree.
Lemma 17. Consider Gaussian linear SEM associated to polytree T = (V, E) with Pruax < 1 - 5.
Then we have the following:
1. For any (i.j) E TT, |pigl 2 Pmin and |Pojal 2 8pmin for any k & {i,j).
For any (i.j) $ T, if the path connecting and j not trek, then Pij = 0.
For any (i,1) & T, if the path connecting i and j is a trek, then there exists some h E adj(i, T) U adjli, Mi such that Pijik = O.
Proof. We discuss these three cases separately:
1. In this case, we have |ptl 2 Pmin by definition. For any l & {i,j}, since (i.j) E T, by the tree structure, we know either lies in the path connecting j and k or lics in the path connecting and k. WLOG, we can assume the former is true. Then by the correlation decay property Lemnma
3 there holds lp,al S Punax PPtyl which implies |Pij - -P 2 |p.j((1 p Then
|pssial
Pis PikPjk
2 Pmin (1 (1-Paxx) 2 8pmin-
V(1
P1
12

---

Published in Transactions on Machine Learning Research (03/2025)
2. This is directly implied by Lemma B
3. When the path connecting i and is a trek, there exists some k E adj(,, Uadiji M) on this path. Lemma implies Pij = PikPik, which implies Pijlk O.
Besides the population correlations Pij, for any distinct i, j, and k, the population and sample partial correlations can be represented by marginal correlations through the following equations:
Pij PAPPjR
Púj PIuPER
PUlk (( - Pi.) P3)
and Pulk Va (1-P)))(1 17
Note that although the concept of partial correlations will not be used in this section, we need it in later sections. The relationship between population and sample marginal and conditional correlations can be characterized by the following lemma, which is simplified version of Corollary in Kalisch Bühlman (2007).
Lemma 18. Consider Gaussian linear SEM ( with n 2 Co log for some numerioal constant Co. Then, on an event with probability least 1/p". the follownng inequality holds for some absolute constant C:
logg 1Ogp
1 pllmax <CV <CV=
n
and
log
Payjk - Pajikl <
C
Vi Vi<j, k {i,g}.
Proof. This is easy generalization of Lemma by the relationship between sample partial correlation and sample correlation cumulative distribution functions under multivariate normal distributions established in Fisher 1924
From the above lemma, is natural to consider the carly-stopping PC algorithm with tuning parameter Terit that is described in Algorithm The estimated skeleton is denoted as T.
Algorithm 3 Estimating the polytree skeleton by the simplified PC algorithm
Input: The p data matrix X; tuning parameter Yerit Estimated skeleton T.
Output:
1: Compute the sample correlations Pij for all
2: Compute the sample partial correlations Pijli for all 1 iisjjss <isspp and any & & (1,j):
The complete undirected graph over the p nodes is denoted as Go;
for Each pair of non-ordered (i,j) do
if |Ptyl "errt (log p)/n then
6: remove (i,5) from Go
7: else if |pojul < Yerit / (log p)/n for some ls & {i,j} then
8: remove (i,j) from Go
9: end if
10: end for
11: The resulting graph denoted as F.
Our consistency result for polytree skeleton recovery by the simplified PC algorithm demonstrated in Algo- rithm consists of two parts. In the first part, we show that T T as long as the tuning parameter Yorit in the threshold chosen large enough; in the second part, we show that T T if we assume further that Pmin satisfies some lower bound condition.
13

---

Published in Transactions on Machine Learning Research (03/2025)
Theorem 19. Consider Gaussian linear SEM (2) associated to polytree T (V, E) with Pmax < - 8. Let T be the estimated skeleton from the simplified PC algorithm given in Algorithm & with the threshold "erit / (log /).. If the tuning parameter satisfies "lerit > C, where C is defined in Lemma 18 then, the event & defined in Lemma 18 with probability at least 1 - 1/p², we have T T.T.
In addition, if
logp
(10)
82
Pinin
we have T =T on E, ie. the exact recovery of the polytree skeleton.
Proof. Let the event & be defined as Lemina
18 Consider any (i.J) $ T. If the path connecting and j is Terit v (log p)/n,
not trek, we have Pij = 0 by Lemma 17 Then Lemma 18 implies |Ayl < C (lo(lo
(i,j) is excluded from Go by Algorithm
On the other hand, if the path connecting i and is
trek, Lemma 17 implies that there exists some k & {i,j} such that Pijlk O. Then Lemma
18 implies
Aujill < C CV VCV(log (logp//n < Perut/(logp))/ so (i,j) also excluded from Go. This implies any (i,j) j) $ T is
removed from Go, matter whether the path connecting them is trek not. Thus, we have T T.T.
Further, the condition
10 implics Pmiu
2yori
logp for any (1, T, Lemmas 18 and 17 imply
log z Pmin C
-c
log n
logg
A 2 pasl C2
Yorit
and for any k $ {i,j},
log 8 8pmnn CV
log
log
Aulkl 2 |pssIl -C
Yorit V
n
n
This implies that (i,j) 50 7 TT
Remark 20. Here we show that the skeleton T can be eractly recovered with high probability under the sample size condition 100 which is comporable to the condition (G) for skeleton recovery by the Chow- algorithm.
Note that our simplified PC algorithm is only aimed at recovering the skeleton rather than identifying all independence relationships among the variables. This is the reason why the sample size condition (TOp can be smaller than the necessary condition for CPDAG recovery established in Theorem This the crucial difference between Theorem 19 and standard CPDAG recovery result by PC algorithm
16 for sparse DAG learning, e.g. Kalisch & Bühlman (0077).
To understand why Algorithm may lead to consistent skeleton recovery even without identifying the wenginal/conditionn independence relationships correctly, one can take trek i + k + j in the true polytree with |axl = lpsul = Pmin as an example. In this case, Algorithm 3 could possibly remove the edge i-j j simply due to |pyl Yerie (logp)/n long |pyl = |psllppjæ| Piiin is sufficiently small. Following the idea of the PC algorithm, one may record (X,, Xj) as an independent pair of variables incorrectly. However, this may still lead to correct skeleton recovery.
To recover the CPDAG, we can naturally apply Algorithm 2 following Algorithm The following result is obvious and we omit the proof.
Theorem 21. Under the assumptions Theorem 19 if we further assume the sample size condition holds, then Algorithms and recover the true CPDAG exactly with probability at least 1/p².
5 Inverse Correlation Matrix Estimation
In this section, we are interested in recovering the inverse correlation matrix of the polytree model un- der recovered CPDAG. This is particularly useful for likelihood calculation; see, e.g. van de Geer &
14

---

Published in Transactions on Machine Learning Research (03/2025)
Bühlmann (2013). This could be useful for choosing the value of tuning parameters with tkeeihhodd-bsse
cross- cross-va validation.
To estimate the inverse correlation matrix, due to the scaling invariance of population and sample correla- tions, without loss generality, we assume that all X,'s have unit variances. Then the inverse correlation matrix + = -- (I B) ). The major goal this subsection to study how well we can estimate + It may be noteworthy that the error bound we obtained (Theorem 24 depends on the total
number of v-structures in addition to the usual dimension and sample size.
5.1 Inverse Correlation Matrix and CPDAG
At first, let's choose one realization from the equivalence class represented by this CPDAG, and still refer to it as T with no confusion. By θ = (I BIQ- BT), and the fact. Bij = Pij for each - j E T, By due to unit variances, we can represent the entries of the inverse correlation matrix by the correlation coefficients over the polytree as
Ppy/wys -pjs/wH PukPsk/ wwkk
fi
iÿiiiT if fi=k+jeT otherwise,
O:j
for i ij
(11)
Pjk for j = 1....p.
0z5
+
(12)
Wij
Wkkk
kECh())
where Wyj = -1 Σ &E Pa())
py for j = 1, ,.....p. Notice that the + k + E must be unique in a polytree.
A natural question is whether This question is important given we can only hope to recover Cr by the algorithms introduced in Sections We first give a useful lemma, which explains for what kind of node j, the noise variance ph is well-defined on the CPDAG Cr, ie., invariant to any particular polytree chosen from iEPalf)
represent the inverse correlation matrix only through the CPDAG Cr.
2.3.1 and 2.3.2
Σ
the equivalence class.
Lemma 22. Denote by Cr the true CPDAG of the polytree T. We denote by Vn the collection of nodes j such that there is at least one undirected edge i-j in Cr. On the other hand, we denote Va the collection of nodes such that all its neighbors are connected to with a directed edge Cr. This means that V.. and Va form a partition of all nodes. Then, we have the following properties:
1. For each j E Vm, there is no salisfying i j j E Cr-
2. For each Vn and any polytree T within the equivalence class Cr j has at most porent in T².
For each j E Va, since the of parents of j determined by the CPDAG Cr, the corresponding noise varionce Wiy = Σ Pt is well-defined.
iEPa())
4. Combinéng the third property and the contrapositive of the first property, we know for each - j Cr, we have j E Va, and the corresponding noise variance Wia is thereby well-defined.
We omit the proof since this result can be directly implied by the fact that v-structures are kept unchanged in all polytrees within the equivalence class determined by Cr. Then the following result shows that the inverse correlation matrix can be represented by the pairwise correlations on the skeleton well as the CPDAG.
15

---

Published in Transactions on Machine Learning Research (03/2025)
Lemma 23. Let Vm and Va be the partition of all nodes defined in Lemma 22 matrix can be represented
Then, the inverse correlation
Pis/wps
ifi + j E Cr
Pis/wa
if + E Cr
Ozs
Pigl(L pity)
if - j E CT
for i +
PikPih wwkk
if + + j E CT
0
otherwise,
and
1 +
Σ
pi WaN"
Va.
Wis
0ji
j-kEET
BR
1 1+
Σ
Σ J-kECr
j E mm
1-p
j-kECr
Here Wij =1
p is well-defined in all of the above formulas, since Pa(j) is well-define for any iEPa(j)
Σ
j E Va.
Proof. Let T be a polytree in the equivalent class of Cr. For 0zg, the possible cases listed in the lemma are exhaustive by Lemma 23 the only case need chocking is j-j E Cr. If the edge oriented + TV. Pb/ -.y.. By Eq. 12). 0, - (1 přj) It is easy to that the result is identical if the undirected edge is - j in some polytree.
By point in Lemma 23 is the only parent of j thus wjj
For Ojj and the non-obvious case of j E Vn, the undirected edges j - k connected to in Cr are either all, or except for one, oriented as j + k in any polytree T" (Lemma 23 For the first case, wys = 1, Eq. 12 in T' becomes
OjN 1+
Σ
P
Σ
jk
Σ
Σ
Pjk
Wek
Wirk
PSR
Wikk
j k-k
j-tkEr
j j-keCr
k-E
Note that Wkk = 23 according to the result derived above for undirected edges.
In the second case, suppose hı is the single parent of j in T', We have wij = 13 and Eq. 112 is
Pik f3 = 1 Pjks
Σ
Σ
1-
Pjk
Wikk
j-RECT
It is easy to see that Ojj are identical in the two cases and this completes the proof.
5.2 Inverse Correlation Matrix Estimation
By Lemma 23 we can give an estimate of the inverse correlation matrix by the estimated CPDAG č,, sample correlations over the estimated tree skeleton, and estimated noise variance for each j E Va:
Pus/ Po/ Peg/(1 p(z)) PuePste /
if i + j E Er if j E čτ if j E Cr
0.
for i +
(13)
if + + j E Cr otherwisc,
and
+ Σ
P WEE
j E Van
Wsi
j
(14)
e Was
E Vmn
1
J-kECr
j-kE
Here, Va and Dm similarly defined through the estimated CPDAG Êr in Lemma 22
16

---

Published in Transactions on Machine Learning Research (03/2025)
The CPDAG can be estimated through Algorithms and 2
The sample correlations the estimated skeleton can also be naturally defined. The remaining question is how to estimate noise variances in Va- One natural method is to estimate Wjj based on 5 W3
=1
Σ
Pij for each j E Va, where Pa(j) is the
<EPo(s)
corresponding estimated parent set. However, the statistical property of this estimator is not easy to derive.
Instead, we propose to estimate the noise variance through the standard unbiased mean squared error, denoted as ررز = MSEj, of the least squares fit for the linear model
X, = Σ X,
tEPa())
Under the Gaussian assumption, if Cr Cr, have Va Va and Pa(j) Pa(j) for each j Va. Then, it is well-known that the least-squares MSE Wjj is an unbiased estimate of wjj- In fact, there holds
Xn- n dj
Wis Wsj
Aj vjeV. Va
(15)
where din the in-degree of node i.e. dz IPa(i)).
Finally, we introduce our result regarding the estimation error bounds of inverse correlation matrix estimation defined above.
Theorem 24. Consider the linear polytree SEM (2 associated with polytree T (V, where all variables have unit variances. Denote the minimum noise variance as
Wmin = min(wy : Va) A min pig: -
Denote the total number of u-structures. It is easy to verify that all of these concepts only depend the CPDAG Cr. We make the assumption that
Pmax S 11 8 and Wain
for consland 8 3>0 0.
Assume that the estimated CPDAG čr is obtained by Algorithms and with threshold Torit (log If we assume 7 in Theorem 14 holds, i.e.
logg p
Yerst > C and > δ
where C is defined in Lemma 0 Then, with probability at least 1 p- the estimated inverse correlation matrix defined in 13) and [14] salisfies
logp n
- - < (p++v)
(16)
In the above, Ō represents some constant that only depends on 5 and Yerit, whose value changes from line to line.
Proof. In the following, we use Ò to represent a constant that only depends on and Teris whose value can change from line to line. On the other hand, C' represents some absolute constant whose value changes from line to line.
Given 7 in Theorem 14 holds, with probability al least 1 1- p-3 we have | pal
logg and the CV
true CPDAG is exactly recovered by, i.e. e, Cr. Consequently, the estimated noise variances satisfy (15
17

---

Published in Transactions on Machine Learning Research (03/2025)
Denote the maximum in-degree
d. max jeVa
From Corollary have Pmin <//dd, Then the assumption > Č ((lgg))) (min)) implics Čd. logp. Then, based on concentration inequalities for Chi-square random variables, 15 implies that with probability at least 1 -
ررش Wاوو S CV logp JEV
max
n
for some absolute constant C.
With the above concentrations of Wyy's and Piy 's, based on the formula we have for any # j.
13 and the assumption Wmin 2 6,
{
10:- 011 - CV
loge if (f, + CT for some k
(17)
10.1 11 0
otherwise,
which further implies
10 0yl Oppti( Σ ifj
log
Further,
14 implics, for each j = ,.....,. there holds
0 0,1 S Õ(1 d)) n
log
where dj is the degree of node j in the skeleton T. This implics
log
Σ 1, ,, s Öpp
Putting the above results together, we get 16
6 Extension to Group Polytree Linear Structural Equation Models
In this section, we consider an extension of the linear polytree structural equation model 1 to the case of variable groups. It will become clear that this is an natural and straightforward extension of our theory, where substituting correlation with a multivariate counterpart to establishes the correlation decay property needed to proving the sufficient sample size for the correct graph recovery. Such group polytree or DAG models describe below may arise when certain variables are closely related driven by common latent variables. Assume the random vector [1 (X,...,,Xp) Xp] is partitioned into groups:
[ ... 2.1.
where 2; is a 4--dimensional random vector. We consider the following group linear polytree structural equation model over = EV;
P X, = Σ X Σ
B, + cj, for j = I.....P.
(18)
iEPa(j)
where the 4 X4 matrix Bij * 0 if and only if + +jj E. Also, assume all en's are independent multivariate normal random vectors. If we denote
0
B
Bip
B21
B2p
B
B,1
Bpp
0
18

---

Published in Transactions on Machine Learning Research (03/2025)
e ,T,,..,,, Then the SEM can still be represented
c.
B Denote the covariance matrices
E
12
Eip
0
Σ21
Σ2
Egp
0
A22
Cov(x)= =
and Cov(e) =
Ep
p2
Epp_
S2p
still have == (I- -I-B) TT B)- Again, our goal is still to recover the polytree structural T (V, E)
from ii.d observation of x: 31....; Tn.
Our algorithm for group polytree learning is similar to that introduced in Section 2 with the pairwise sample correlations Pij replaced with the leading sample canonical correlations between X; and Xj. To be specific, denote Ruj- = R En E IR!ix,, then Pij = | is the leading population canonical correlation coefficient between X; and Xj- Correspondingly, denote the sample version R.j- E Σ with the leading sample canonical correlation coefficient Ai = Rajll- Then we apply Algorithm to recover the polytree skeleton and Algorithm 2 to recover the CPDAG, where Piy's represent leading sample canonical correlations.
In analogy, we also denote "hj min RRj)) as pairwise least population canonical correlation coefficients. These quantities will not be employed in the algorithms, but will be used in our theoretical result of CPDAG recovery.
In the sequel, we aim to extend the consistency results Theorems 11 and 14 to the case of group polytree SEM. Since the sample canonical correlations are linear invariant, in theory, we can assume X; ~ I.)
for each = ,,...,p without loss of generality. In fact, if we replace æ; with X 2 X;, then
X,
Σ
E B B X - for j I,...,
iEPa(j)
which shares the same polytree structure.
Before presenting our consistency results, we also need two lemmas. The first lemma is an extension of the correlation decay property, Lemma 3
Lemma 25. Consider the Gaussion group linear polytree model (18) with the associated polytree T (V, E). For each pair (i,j), if the path connecting and j is not a trek, we have Pij = 0; if the poth connecting and is a trek, we have
II (a.0)
II
Net Pus I
Pet.
(s.1)
Proof. Since population canonical correlations are linearly invariant, we can assume X; N(0, It) for each ,p WT.OG. Then, for each i - j E F,, one can easily obtain
R Bij,
RS. = B.J.
Further, one can easily use argument of induction to show that for each pair (i.j), if the path connecting and j is not a trek, we have Raj- = and thereby Pij = 0; if the path connecting i and j is a trek, denoted as
Tij : = vf + v/-1 f- f- of 0o vf
up-1
we have
Ri B B
of 2
BT wor
Benef
B P
B
B
which further implics
Ry Byffot Rygh 1/1 R/ ... Rofin Reguf ... R 2 R ptt.
The fact Pij = RRyl implies Pij S II Pst-
(s.
19

---

Published in Transactions on Machine Learning Research (03/2025)
Another lemma is extension of Lemma
9
Lemma 26. Consider Goussian group linear SEM (18) with 2 ColImax + logp) for some absolule
constant Co, where lmax maxigi<pl. Then, an event & with probability at least 1 - 1-/p", the following inequality holds for some absolute constant C:
Imaz + logp
max ISiCJSP
liij - PPisl < CV.
(19)
where Pij and Pij are sample and population leading canonical correlation coefficients between X; and Xj respeclively-
Proof. Again, since population and sample canonical correlations are lincarly invariant, we can assume X, ~ (O, I for each = I.....P WLOG. By the Remark 5.40 in Vershynin (2012) (reproduced in Appendix A), with n 2 Co(Imax log for some sufficiently large constant Co, one can show that with probability at least 1 1/p", have
Ima + logp
max E5 I1,1 < <CV. 15i5p
n
and
Ima + logp
Eij Eigll CV
max ISKJSP
n
which further implies
Iaa + log
max ISKjSP
Rij- - Riyl
< CV
n
Similar arguments can also be found in Ma & Li 2020
Then 19
follows from the fact
Pos Pis- = Ray Ray |ll S Rag Rayl-
With the above lemmas, the consistency of the recovery of polytree skeleton and CPDAG by Algorithms and with sample correlations replaced with sample leading canonical correlation coefficients can be straightforwardly established.
Theorem 27. Consider Gaussian group linear SEM 18 associated to a polytree T = (V, F.. Denote
the minimum population leading canonical correlation coefficient, marimum population leading canonical correlatton coefficient, and minimum population least canonical correlation coefficient over the tree skeleton
as
Pmni = min |pills iJjE
=-min
Puax
max (ptjls and Mmiin i-jEE
min i+JEE
|myl-
Assume Pmax 11-8 for some constant 8. Denote by T the estimated skeleton by the Chow- Liu algorithm (Algorithm 1,, and by T the true polytree skeleton. Then, with probability at least 1 - 1/p3, have cract polytree skedelon recovery T TT as long as
(max + log P
n > Co(o)
where Co( is conslant only depending on 8.
Further, denote by Cr the true polytree CPDAG, and by Čr the estimated CPDAG from Algorithm with threshold Terit / (Imax + logp)/n. If Maain O, then, with probability at least 1 1/p², we have Ör Cr as long
(mmxx + log
Yeris C and n Co(d)
where C is absolute constant, and Co( is conslant only depending on 8-
20

---

Published in Transactions on Machine Learning Research (03/2025)
Proof. The proof is exactly the same those of Theorems and 14 Note that the sample size condition for CPDAG recovery relies on the minimum least population canonical correlation coefficient. In fact, if the ground truth is c k + j or i k or i i k + j. Lemma 25 only implies that |pyl 2 miii
Remark 28. Our CPDAG recovery result for group polytree SEM relies on the assumption Quin > 0. At this moment, we don't know whether this is a necessary condition, and we plan to invesligale this in fulure work.
7 Numerical Experiments
To illustrate the feasibility and quantitative performance of the polytree learning method based on the Chow- Liu algorithm, we implement Algorithms I and 2 in Python and test on simulated data (Section 7.1 J. We further test on commonly used benchmark datasets (Section 7.2) to assess the robustness and applicability to real-world data. In all experiments, we set the threshold Perit (Algorithm 2 for rejecting a pair of nodes being independent based on the testing zero correlation for Gaussian distributions. Specifically, Perit
V -1 1+12 4/2/ (n-2) where 1a/2 is the a/2 quantile of a t-distribution with df n 2, and we use a = 0.1. For comparisons, we run these same data using two basic and representative struetural learning PC algorithm (Spirtes eet al., 2000) along with its stopy-stopping adaptation polytree (Algorithm 3). We use implementations of the hill climbing and the PC algorithm from bnlearn and pcalg packages, respectively, along with all the default options and parameters. We implemented the polytreo-adapted PC algorithm in Python. An a = 0.01 is used for the PC algorithın as recommended in Kalisch & Bühlman (2007). All codes are available at https://githi: should be taken when interpreting algorithm results in practical applications, as they represent potential causal interactions rather than definitive proofs.
methods: the score-based hill climbing (Gámez et al., 2011], and the constraint-
hwwpaauuoooiiaaaaoooreeeeeeeeeee SEM. As is the case with all SEMs, caution
We assess the results by comparing the true and inferred CPDAGs C and c. On the skeleton level, there can be edges in C that are missing in C, and vico versa C can have extra edges. For the CPDAG, consider directed edge to be correct if it occurs with the same direction in both CPDAGs. For undirected edge, it needs to be undirected in both CPDAGs to be considered correct. Any other edges that occur in both CPDAGs are considered to have wrong directions. With these notions, we can calculate the False Discovery Rate (FDR)
for the skeleton as |extral and for the CPDAG [extra|+|wrong direction! Here |extra| is the number of extra
[CI
[C]
edges, [C] is the number of edges in č, and so on. To quantify the overall similarity and take into account the true positives, we calculate the Jaccard index (JI), which correct + wwrong direction! |correct| |wrong direction |missing +[C]
[CUC]
for the skeleton, and [corec]]
[correct|
for the CPDAG.
7.1 Testing on Simulated Polytree Data
Here we briefly describe how we generate linear polytree SEMs. Additional implementation details can be found in Section 7.3 First, we generate a polytree by randomly assigning directions to random undirected tree. Next, the standardized SEM parameters Bij's are randomly chosen within a range, which in turn determine Wis (Eq. (5). Motivated by the theoretical results (Theorems 11 14 and 16), we make sure that in the above procedures, the generated SEM satisfies Pmin S |8,y1 S Pmax: the maximum in-degree d, = do, and Whiin I Wh for all E V. Here Pmin: Pamax; dº, Wmin are pre-specified constants (values usod are listed in Fig. caption).
I and 2 show the performance for p 100 and ranging from 50 to 1000. We see that the Chow-Liu algorithm performs much better than hill climbing, and overall has an accuracy similar to or better than that of PC and early-stopping PC. At small sample sizes of less than 400, PC and early-slopping PC have a smaller FDR for skeleton recovery than Chow-Liu, but this is likely at the expense of the true positive rate, as reflected by the similar or lower JI of PC compared to Chow-Liu (Panels BD of Figs. [ and 2 At larger sample sizes, Chow-Liu has a better accuracy in recovering the CPDAG. The carly-stopping PC has similar accuracy in recovering the skeleton as the regular PC and better accuracy in recovering the
Figures
21

---

Published in Transactions on Machine Learning Research (03/2025)
CPDAG (Panels CD of Figs. andd This is likely due to the algorithm only applying Meek's Rule 1 (which is all needed for polytree) to orient the edges (Section 2.3.2p. As Puni becomes smaller d, increases. the accuracy of Chuw-Liu decreases, which is consistent with the theory (Theorems climbing and PC, the accuracy less affected by Punin or d, (Fig. vs Fig. 2
14 and 16 For hill
When comparing skeleton recovery (Panels A, B Figs. 1 and with CPDAG recovery (panels C, D Figs. and the accuracy of skeleton recovery higher, which is consistent with our theoretical results
Theorems
11 14 and 16
A 1.0
B 1.0
Chow-Liu
0.8
climbing
0.8
PC
FDR skeleton
stopped
skeleton
0.6
0.4
= 0.05
Pain 0.10
0.2
Pnin
0.2
0.0
200
400
600
800
1000
D
0.0
200
400
600
800
1000
0.8
0.8
FDR CPDAG CPDAG
CPDAG
0.4
0.4
0.2
0.2
200
400
600
800
1000
200
400
0
600
800
1000
Figure 1: Performance on the polytree simulated data at p = 100 and the maximum in-degree d, 10. The results from the algorithms are represented by solid lines and dot markers (polytree), dash lines and triangle markers (hill elimbing), solid lines and square markers (PC), and dash-dot lines and square markers (PC carly stopped). Colors correspond to three diflerent values of Pmin- The rest of the SEM parameters are Pmax = 0.8, and Wmin = 0.1. Panels A,C show the FDR (the smaller the better) for skeleton and CPDAG recovery. Panels B,D show the Jaccard Index (the larger the bettor). For each combination of SEM paramcters, we randomly generate a polytree, the detailed generation of the Biy's 's and Wis 's are described Section 7.3 Then we draw iid samples from the SEM of different sizes (the x-axis, n 50, 100, 200, 400, 600, 800, 1000). This entire process is repeated 100 times. Each point on the curves shows the average over the 100 repeats and the error bars are 1.96 times the standard error of the mcan (many smaller than the marker).
7.1.1 Running Time Comparison
Interestingly, the running time of the PC algorithm is significantly affected by d.: the running time increases 40 folds when d, changes from 10 to 20 (Table [ and the code may even fail to stop (rumning for more than hours) when d. = 40 (data not. shown). This phenomenon can be explained by the relationship between the maximal number of neighbors and the maximal number iterations the PC algorithm; see Proposition 1 of Kalisch & Bühlman (2007). On the other hand, Chow-Lin is significantly more favorable in terms of running time, similar the carly-stopped PC which avoids the issue of maximal number of neighbors above. The Chow-Liu algorithm is up to 80 times faster than the slowest alternative algorithm
22

---

Published in Transactions on Machine Learning Research (03/2025)
A 1.0
Chow-Lii climbing
0.8
FDR skeleton
PC weryy stupped
Jl skeleton
0.6
Pais 0.05
Pais
0.2
Pisie
0.15
200
400
600
800
1000
200
1000
C
D
1.0
0.8
FDR CPDAG
CPDAG
0.6
0.4
0.2
0.0
200
400
1000
200
400
600
800
1000
Figure 2: Same as Fig. but for a maximum in-degree of d, 20.
(Table [ and, importantly, has a running time that is constant across the SEM parameters (this is also true for other experiments described later).
Polytree == 100,
Polytree p = 100,
(Unit: sec)
din
ASIA p
ALARM
Chow-Liu
0.01
0.01
0.0003
0.01
Hill climbing
0.87
1.00
0,012
1.48
PC
0.53
PC early stopped
0.03
0.03
0.001
0.38
Table 1: Running time comparison. The columns correspond to the SEM data in Figs. 1 and 2 (polytree), Table (ALARM) and Table 3 (ASIA). 5000 for the AISA and ALARM. The running time is for one inference (averaged across trials wials/bootstraps when applicable). All computation is done 2019 Intel i7 quad-core CPU desktop computer.
7.2 Testing on DAG Benchmark Data
The ALARM dataset (Beinlich al. 1989p is a widely used benchmark data. The truc DAG (Fig. 3 is not polytree and has 37 nodes and 46 edges. In fact, three-phase algorithm initialized by Chow-Liu has this data (Cheng et al. 2002). We simply conducted the Chow-Liu algorithm (aathhmm(Aggnnn (Algorithms) 1 [and 2), and found that it still performs better than hill climbing and PC (including the early-stopping version) in terms of the metrics (Table 2 as well as intuitively by the inferred graph (Fig. At n = 5000, it even achieves the best possible accuracy for skeleton recovery as Chow-Liu can achieve (there has to be at least 46 (37 - 1) = 10 edges missing in an inferred polytree).
been demonstrated to be effective
Another benchmark we test is the ASIA dataset (Lauritzen Spiegelhalter 1988), which is simulated DAG dataset with eight nodes. Note that the ground truth is sparse but not. exactly polytree. At 500
23

---

Published in Transactions on Machine Learning Research (03/2025)
500
Correct
Wrong d.
Missing
Extra
FDR sk.
JT ak.
FISR CPDAG
JI CPDAG
Chow-Liu
28
14
4
0.11
0.64
0.22
0.52
Hill climbing
60
PC
14
17
15
13
0.3
0.53
0.68
0.18
early stapped
5000
Correct
Wrong
Missing
Extra
FDR sk.
sk.
FDR CPDAG
JI CPDAG
Chow-Lit
25
11
10
0
0.0
0.78
0.31
0.44
climbing
27
62
0.21
PC
24
5
12
0,23
0.71
0.55
0.32
PC early stopped
42
39
0.48
0.51
0.49
0.49
Performance ALARM data. See text for the details of the accuracy measures: the number of correct, missing, extra, and wrong direction edges, FDR, and Jaccard index for skeleton and CPDAG. The best results across the algorithms are in bold.
Table 2:
True CPDAG
Chow-Liu
PC
Hill-climbing
PC early stopped
correct
missing
extra
wrong direction
Figure 3: Comparing the true CPDAG of the ALARM data and the inferred one from the four algorithms at n = 5000. There are 37 nodes and 46 edges in the true CPDAG.
samples, the performance of Chow-Liu is comparable to that of hill climbing and PC algorithm, while the hill climbing gives the best result at 5000 (Table We illustrate the comparison intuitively by plotting the most likely inference outcome of each algorithm across the bootstrap trials in Fig. (where we re-sample n observations from the original 5000 samples). Note the graph inferred by Chow-Lau (occurs at. 23%) is the best possible result can achicve. This bocause at least one edge must be missing as the output a polytree, and the v-structure involving B, E, and D can no longer be identified leading to BD being undirected.
missing the edge ED,
Lastly, we study benchmark simulated dataset, EARTHQUAKE Korb & Nicholson 2010 whose ground truth graph is polytree (Fig. At n 500 samples, the performance of Chow-Liu is comparable to that of hill climbing and PC algorithm, while Chow-Liu performs the best in the overall recovery of the skeleton and the CPDAG at n 2000 (FDR and Jaccard index in Table 4). Similar to previous data, we plot the most likely inference outcome for each algorithm across trials Fig. At 2000, the Chow-Lii algorithm perfectly recovers the true DAG in 90% of trials.
24

---

Published in Transactions on Machine Learning Research (03/2025)
500
Correct
Wrong d.
Missing
Extra
Chow- Liu
4.001.11
[8((126)
2.2(0.6)
1.2(0.6)
Hill climbing
4.2(1.55)
2.3(1.35)
1.5(0.67)
L.5(1.5))
PC
3.3(1.19)
1.7(0.9)
3.0(0.63)
0.1(0.3)
carly stopped
2.0(1.3)
2.1(1.1))
3.0(0.63)
0.1(0.3)
5000
Correct
Wrong d.
Missing
Extra
Chow- Liu climbing
4.19(1.49)
2.3(1.47)
L51(0.55)
0.51(0.51)
6.96(0.9)
0.34(0.69)
0.7(0.57)
0.87(0.93)
PC
1.59(1.06)
1.79(1.04)
1.6((0.6))
0.15(0.39)
PC early stopped
3.82(0.83)
3.53(1.09)
0.65(0.54)
1.05(0.37)
(continue)
N = 000
FDR sk.
Jl
FDR CPDAG
JI CPDAG
Chow-Liu
0.17(0.09)
0.64(0.11)
0.13(0.16)
0.38(0.14)
Hill climbing
0.17(
0.7(0.14)
0.46(0.22)
(.39()
PC
0.02(0.06)
0.62(0.09)
0.36(0.23)
0.35(0.14)
PC early stopped
0.02(0.06)
0.62(0.09)
0.44(0.25)
0.3(0.16)
5000
FDR sk.
JI sk.
FDR CPDAG
JI CPDAG
Chow-Liu
0.07(0.07)
0.77(0.11)
0.4(0.21)
0.41(0.19)
Hill elimbing
0.1(0.1)
0.83(0.11)
0.13(0.15)
0.78(0.18)
PC
0.02(0.05)
0.78(0.08)
0.29(0.17)
0.18(0)14)
PC early stopped
0.12(0.06)
0.82(0.08)
0.54(0.11)
0.31(0.09)
Table 3: Performance on ASIA data. The accuracy measures (the number of correct, missing, extra, and wrong direction edges, FDR and Jaccard index for skeleton and CPDAG; see text) are averaged over 1000 bootstraps (resampling observations of 100,000) and the standard deviations are in the parentheses. The best results across the algorithms in bold.
True CPDAG
Chow-Liu
PC
Hill-climbing
PC early stopped
correct
missing
extra
wrong direction
Figure The true CPDAG and the typical inferred CPDAG for the ASLA data with 5000 samples. We plot the most likely inferred graph across 1000 bootstraps for each algorithm, which occurs at 23% (Chow-Liu), 44% (hill climbing), 42% (PC), 50% (early-stoppin PC), respectively.
7.3 Details on polytree data generation
simulated polytree data, we draw iidd. samples from a Gaussian linear SEM with a polytree structure. First, we generate an undirected tree with p nodes from random Prufer sequence. The Prufer sequence which has one-to-one correspondence to all the trees with p nodes obtained by sampling p numbers with replacement from (1,2...., P). Next, a polytree is obtained by randomly orienting the edges of the
25

---

Published in Transactions on Machine Learning Research (03/2025)
600
Correct
Wrong d.
Missing
Extra
Chow-Liu
2.87(1.66)
0.83(1.27) 0.16(1.07)
0.3(0.67)
0.3(0.67)
Hill climbing
3.38(1.29)
0.17().48)
(0.7(
PC
2.52(1.45)
1.16(1.13)
0.32(0.56)
0.66()
early stopped
2.63(1.53)
1.09(1.22
0.28(0.57)
0.76(0.74)
2000
Correct
Wrong d.
Missing
Extra
Chow-Liu
3.62(
0.38(1.16)
0.01(0.08)
0.01().08)
elimbing
3.88(0.64)
0.12(0.64)
0.0(0.0)
0.61(0.61)
PC
3.80(0.47)
0.14(0.47)
0.0(0.0)
0.62(0.61)
PC early stopped
3.68(0.78)
0.32(0.78)
0.0(0.0)
0.79(0.79)
(continue)
N = 000
FDR sk.
JT
FDR CPDAG
JI CPDAG
Chow-Liu
0.08(0.17)
0.89().22)
0.28(0.39)
0,68(0.4)
Hill climbing
0.17(..14)
0.81(0.17)
0.26(0.3)
0.72(0.31)
PC
0.14(0.13)
0.81(0.18)
0.43(0.33)
0.51(0.35)
PC early stopped
0.15(0.14)
0.8(0.18)
0.42(0.35)
0.54(0.36)
2000
FDR sk.
sk.
FDR CPDAG
JI CPDAG
Chow-Liu
0,0(0.02)
1.0(0.04)
0.08(0.27)
0.91().27)
Hill elimbing
0.13(0.11)
0.87(0.11)
0.16(0.19)
0.84(0.19)
PC
0.13(0.11)
0.87(0.11)
0.16(0.14)
0.81(0.16)
PC early stopped
0.17(0.14)
0.83(0.14)
0.24(0.24)
0.74(0.26)
Table 4: Performance on EARTHQUAKE data. The accuracy measures (the number correct, missing, extra, and wrong direction edges, FDR and Jaccard index for skeleton and CPDAG; see text) are averaged over 1000 bootstraps (resampling observations from total of 100,000 samples) and the standard deviations are in the parentheses. The best results across the four algorithms in bold.
True CPDAG
Chow-Liu
PC
Hill- Hill-climbing
PC early stopped
correct
missing
extra
wrong direction
Figure The true CPDAG and the most frequently inferred CPDAG for the EARTHQUAKE data with 2000 samples over 1000 trials. The graph shown occurs 90% for Chow-Liu, 47% for hill climbing, 46% for PC, and 41% for early-stopping PC, respectively.
undirected tree. We also ensure that one the nodes has specified large in-degree d. This done by making a node occur at least de times in the Prufer sequence, so the node will have degree at least de the undirected tree. We then orient all edges connected by selecting d of them to be incoming edges. The rest of the edges in the tree oriented randomly before.
26

---

Published in Transactions on Machine Learning Research (03/2025)
In the next step; we choose the value of the standardized By corresponding to the correlations. Note that once Biy s are given, Wis are determined by Eq. ( Motivated by the theoretical conditions on n,P such as those in Theorems II and 14 we choose Big according to some pre-specified values Puiin and Pmax and study the effects of these parameters on the recovery accuracy. To avoid ill-conditioned cases, we require that wis 2 Wmin: where Wmin is another parameter. This adds constraints on Big, Σ₁= L3 S - -min: in addition to Pmiin I |p,y1 S Pmax. We sample 82 uniformly among the set of non-negative values satisfying the above inequality constraints. This sampling is implemented by drawing Biy (corresponding to all the edges in the polytree) sequentially in a random order as min Piuin + Uyr), where is drawn from the beta distribution B(1, (.)) Here dy is the number of incoming edges to node j whose (iy has not yet been chosen, and Bi = 1 Wmin d. Pmin Sky where the sum over all edges k j whose S2, have already been chosen, d' is the total number of incoming edges to j. The use of beta distribution here is based on the fact of the order statistics of independent uniformly distributed random variables. As an exception, we first set two |S,yl values to attain equality in the constraints by Puin and Pmax before choosing the rest of Big's according to the above sampling procedure. For Pmax: we randomly choose node that satisfies Pmin (d.t -1) -1)+ Prmxx S 1mii dit 0 (always exists if pimax Wmmin S I and the minimum nonzero in-degree is 1), and set one of its incoming edges to have 1s = Pmax. For Pmin: we choose node among the rest of nodes with di > 0 and set |Sul = Puin for one of its incoming edges. Lastly, a positive or negative sign is given to each Biy with equal probability. After the Bey's (i.e., matrix B) are chosen (and hence Ω), the samples TI,..., In are drawn according to æ = (I- - B) e, where are zero mean Gaussian variables with covariance 5
8 Discussion
This paper studies the problem of polytree learning, special case of DAG learning where the skeleton of the directed graph is a tree. This model has been widely used in the literature for both prediction and structure learning. We consider the linear polytree model, and consider the Chow-Liu algorithm (Chow & Liu 1968) that has been proposed in Rebane & Pearl (1987) for polytree learning. Our major contribution in this theoretical paper is study the sample size conditions under which the polytree learning algorithm recovers the skeleton and the CPDAG exactly. Under certain mild assumptions on the correlation coefficients over the polytree skeleton, we show that the skeleton can be exactly recovered with high probability if the sample size satisfies > (()og))// P)/min)); and the CPDAG of the polytree can be exactly recovered with high probability if the sample size satisfies n > ((logg))/tt. sample size for both skeleton and CPDAG recovery, which are consistent with the sufficient conditions and thereby give a sharp characterization of the difficultics for these two tasks. In addition, we also study inverse correlation mairix estimation under the linear polytree SEM. Under the component & metric, we give an estimation error bound that is characterized by the dimension, the sample size, and the total number of v-structures.
We also establish necessary conditions on
There are number of remaining questions to study in the future. It would be interesting to study how to relax the polytree assumption. In fact, the benchmark data analysis (Section 7.2) is very insightful, since it shows that the considered Chow-Liu based CPDAG recovery algorithm, which seemingly relies heavily on the polytree assumption, could lead to reasonable and accurate structure learning result when the ground truth deviates from a polytree to some degree. This inspires us to consider the robustness of the proposed approach against such structural assumptions. For example, if the ground truth can only be approximated by a polytree, can the structure learning method described in Sections and 2.3.2 lead to an approximate recovery of the ground truth CPDAG with theoretical guarantees? Similarly, if the sample size is not large enough and the CPDAG is thereby unable to be recovered exactly, can we still obtain an accurate estimate of the inverse correlation matrix? As aforementioned, polytree modeling is usually used in practice only as initialization, and poos--rrcessing could give better structural recovery results. A well-known method of this type is given in Chong et al.] (2002) without thcoretical guarantees. An interesting future rescarch direction is to include such post-processing steps into our theoretical analysis, such that our structural learning results (e.g., Theorems 14p hold for more general sparse DAGs.
27

---

Published in Transactions on Machine Learning Research (03/2025)
Acknowledgment
X. Li and X. Lou acknowledge support from the NSF via the Career Award DMS-1848575. Y. Hu was partly supported by an Early Career Scheme grant 26303921 from the Hong Kong Research Grants Council. We would like to thank Peng for helpful discussions.
References
Animashree Anandkumar, Daniel J Hsu, Furong Huang, and Sham Kakade. Learning mixtures of tree graphical models. NIPS, pp. 1061-1069, 2012a.
Animashree Anandkumar, Vincent YF Tan, Furong Huang, Alan S Willsky, et al. High-dimensional structure estimation in ising models: Local separation criterion. The Annals of Statistics, 40(3):1346-1375, 2012b.
I. Beinlich, H. J. Suermondt, R. M. Chavez, and G. Cooper. The ALARM Monitoring System: A Case Study with two Probabilistic Inference Techniques for Belief Networks. Proc. 2nd Europeon Conference on Arlificial Intelligence in Medicine, pp.
1989.
Guy Bresler and Mina Karzand. Learning a tree-structured ising model in order make predictions. Annals of Slatistics, 48(2):713 737, 2020.
Sourav Chatterjee and Mathnkumalli Vidyasagar. Estimating large causal polytrees from small samples. 9 2022. URL http:///aaxivv..aabb/////ss
07028
Jie Cheng, Russell Greiner, Jonathan Kelly, David Bell, and Weiru Liu. Learning bayesian networks from data: An information-theory based approach. Artificial intelligence, 137(1-2))43-900 2002.
David Maxwell Chickering. Learning equivalence classes of bayesian-network structures. The Journal of Machine Learning Research, 2:445-498, 2002a.
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, ((Nov)5507-554 2002b.
CKČN Chow and Cong Liu, Approximating discrete probability distributions with dependence trees. 1EEE transactions on Information Theory, 14(3):462-467, 1968.
Sanjoy Dasgupta. Learning polytrees. In Proceedings of the Fifteenth conference on Uncertainty in artificial intelligence, pp. 134-141, 1999.
Mathias Drton and Marloes H. Maathuis. Structure learning in graphical modeling. Annual Review of Statistics and Its Application, 4:365-392. 2017.
RA Fisher. The distribution of the partial correlation coefficient. Melron, 3:329 332, 1924.
Rina Foygel, Jan Draisma, and Mathias Drton. Half-trek critcrion for generic identifiability of lincar struc- tural equation models. The Annals of Stalistics, pp. 1682 1713, 2012.
José A. Gámez, Juan L. Mateo, and José M. Puerta. Learning Bayesian networks by hill climbing: Efficient methods based on progressive restriction of the neighborhood. Data Mining and Knowledge Discovery, 22 (1-2):106-148; 2011. ISSN 13845810. doi: 10.1007 1.11077/100188-0000017..1
Asish Ghoshal and Jean Honorio. Learning linear structural equation models in polynomial time and sam- ple complexity. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Slatistics, PMLR, 84, 2018.
Uri Heinemann and Amir Globerson. Inferning with high girth graphical models. In International Conference on Machine Learning, pp.
PMLR, 2014.
Christina Heinze- Marloes Maathuis, and Nicolai Meinshausen. Causal structure learning. Annual Review of Statistics and Its Application, 5:371-30 1911,,9,15 2018.
28

---

Published in Transactions on Machine Learning Research (03/2025)
Markus Kalisch and Peter Bühlman. Estimating high-dimensional directed acyclic graphs with the pe- algorithm. Journal of Machine Learning Research, 8(3), 2007.
Ashish Katiyar, Jessica Hoffmann, and Constantine Caramanis. Robust estimation of tree structured Gaus- sian graphical models. Proceedings of the 36th International Conference on Machine Learning, 97:3292 3300, 09-15 Jun 2019. URL httpp::/pproceeedngg mlr wwt..//e///////./arrrrreeee html
Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
Kevin B Korb and Ann E Nicholson. Bayesian artificial intelligence. CRC press, 2010.
Joseph B Kruskal. On the shortest spanning subtree graph and the traveling salesman problem. Pro- ceedingg of the American Mathematical sociely, 7(1):48-5p) 50, 1956.
S. L. Lauritzen and D. J. Spiegelhalter. Local computations with probabilities graphical structures and their application to expert systems. Journal of the Royal Statistical Society, Series B (Methodological), 50 (2):157-224, 1988. ISSN 00359246. URL http: //tt: http::///wwwwj.o.rroo jsttrr arg/stable/2345722
Zhuang Ma and Xiaodong Li. Subspace perspective on canonical correlation analysis: Dimension reduction and minimax rates. Bernoulli, 26(1):432-44) 470, 2020.
Christopher Meek. Causal inference and causal explanation with background knowledge. In Proceedings of the Eleventh conference on Uncertainty in artificial intelligence, pp. 403 410, 1995.
Praneeth Netrapalli, Siddhartha Banerjee, Sujay Sanghavi, and Sanjay Shakkottai. Greedy learning of markov network structure. In 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1295-1302, IEEE, 2010.
Konstantinos Nikolakakis, Dionysios S Kalogerias, and Anand D Sarwate. Learning tree structures from noisy data. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1771-1782.
PMLR, 2019.
Christopher Nowzohour, Marloes H Maathuis, Robin J Evans, Peter Bühlmann, et al. Distributional equiv- alence and structure learning for bow-free free acyelic path diagrams. Electronic Journal of Statistics, 11(2): 5342-5374, 2017.
Judea Pearl. Causality. Cambridge university press, 2009.
J Peters and P Bühlmann. Identifiability of gaussian structural equation equal error variances. Biometrika. pp. 219 228, 2014. URL htttp:://bout. jstor. org//erms
George Rebane and Judea Pearl. The recovery of causal poly-trees from statistical data. Proceedings of the Third Conference on Uncertainty in Artificial Intelligence, pp. 222 2222 1987.
Karen Sachs, Omar Perez, Dana Pe'er, Douglas A Lauffenburger, and Garry P Nolan. Causal protein- signaling networks derived from multiparameter single-cell data. Science, 308(6721):533-522) 2005.
Peter Spirtes, Clark N Glymour, Richard Scheines, and David Hockerman. Causation, prediction, and search. MIT press, 2000.
Vincent YF Tan, Animashree Anandkumar, and Alan Willsky. Learning gaussian tree models: Analysis of error exponents and extremal structures. IEFE Transactions on Signal Processing, (77::27701 2010.
Mostafa Tavassolipour, Seyed Abolfazl Motahari, and Mohammad-Taghi Manzuri Shalmani. Learning of troe-structured gaussian graphical models on distributed data under communication constraints. JEEE Transactions on Signal Processing, 67(1):17-28, 2018
M. CoverJ Thomas and A Thomas Joy. Elements of information theory, 2006.
29

---

Published in Transactions on Machine Learning Research (03/2025)
Danicle Tramontano, Anthea Monod, and Mathias Drton. Learning linear non non-gaussian polytree models. Proceedings of the Chirly-Righull Conference on Uncertainly in Artificial Intelligence, PMLR, pp. 1960- 1969, 2022.
Sara de Geer and Peter Bühlmann. cO-penalized maximum likelihood for sparse directed acyclic graphs. The Annals of Statistics, 41(2):336-667, 2013.
Thomas Verma and Judea Pearl. Equivalence and synthesis of causal models. UCLA, Computer Science Department, 1991.
Thomas Verma and Judea Pearl. An algorithm for deciding if a set of observed independencies has causal explanation. In Uncertainly in artificial intelligence, pp. 323 330. Elsevier, 1992.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. Compressed Sensing, pp. 210-268, 2012.
Wei Wang, Martin Wainwright, and Kannan Ramchandran. Information--heorrlic bounds on model selec- tion for gaussian markov random fields. In 2010 IEEE International Symposium on Information Theory, pp. 1373 1377- IEEE, 2010.
Sewall Wright. Path coefficients and path regressions: alternative or complementary concepts? Biometrics, 16(2):189 202, 1960.
Bin Zhang, Chris Gaiteri, Livin-Gabriel Bodca, Zhi Wang, Joshua McElwee, Alexci A Podtelezhnikov, Chunsheng Zhang, Tao Xie, Linh Tran, Radu Dobrin, et al. Integrated systems approach identifies genetic nodes and networks in late-onset alzheimer's disease. Cell, 153(3):707-72)) 2013.
A Preliminaries
Lemma in Kalisch & Bühlman (007) Let Pig and Psy are sample and population correlation between X, and X, as in Section Consider the Gaussian linear polytree SEM with supn,iti Pig < M 1. Then for any 0 < 7 S 2, the following inequality holds:
2) exp (nn 4) log
44 (4-92)
sup ((pss Posl 27
5 Cinn
4 44
*41
where < Ci < 0o depends only on M.
Remark 5.40 in Vershynin (2012) Assume that is an x n matriz whose rows A, are independent sub-gaussian random vectors R with second moment matrix E. Then for every 2 0, the following inequality holds with probability at least 1 exxp(-c12)
1 N
I الل S max(6, 82), where 8 = C
VN
Here C = Cx and c = cg > 0 depend only on the sub- sub-gaussian norm max, |Alll of the rows.
30


Reviews:
[{"review_id": "mSuG37vROg", "reviewer": "Reviewer_kpqu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The topic is important as it focuses on determining the necessary sample size to reliably recover the true underlying graph structure\n\n2. It extends the convergence analysis from tree-structured undirected graphical models to directed polytrees, which enable the modeling of directional causal relationships. By leveraging the unique structural properties of polytrees, it bridges the gap between undirected dependency structures and directed causal inference frameworks. \n\n3. It derives sample size bounds for both accurate recovery and failure probabilities in skeleton and CPDAG estimation. These bounds are sharp, offering valuable insights into the trade-off between sample complexity and estimation reliability.\n\nWeaknesses:\nThe Chow-Liu algorithm, on which the proposed method is based, is more sensitive to data assumptions compared to other methods and exhibits a slower convergence rate.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates conditions on the sample size for polytree learning under the linear SEM model. It provides sample size conditions for recovering the skeleton and CPDAG using the Chow-Liu algorithm, where the conditions are related to the correlation bounds between variables and the estimation error for finite sample sizes. Additionally, it establishes sufficient conditions for the sample size and derives probability bounds for recovery failure when the sample size is insufficient. Furthermore, it examines the estimation error bounds of the inverse correlation matrix in the linear polytree SEM and validates the theoretical findings through numerical experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "(1) I think the structure of the theoretical section is very clear, but the experimental section is somewhat confusing. First, it would be better to considering adjusting the placement of the figures to make them closer to the corresponding text. It is a bit hard to follow when the text and the figure are separated by 5 pages (e.g., Figure 5).\n\n(2) In the experimental section, it would be better to make the content intended for analysis more distinct and independent. For example, consider separating the running time comparison in Section 7.1 into its own subsection for more focused analysis.\n\n(3) Please consider citing and discussing the following paper.\n\nTramontano D, Monod A, Drton M. Learning linear non-Gaussian polytree models, UAI 2022.", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3HtybwEsiF", "reviewer": "Reviewer_WnuG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThe authors clearly state that they are analyzing an existing classical algorithm. For this, they present novel theoretical results that help shed light on the algorithm’s behavior. They also  present experimental results showing that the algorithm is on par with more modern alternatives.\n\n**Weaknesses**\n\nI would like to see a paragraph describing why polytree models are meaningful, for example describing applications or examples where they arise. Saying that DAG models are popular seems a little bit too general.\n\nMy main concerns lies with the experimental results. I was expecting to see studies showing a phase transition when the number of samples reaches the theoretical prediction. If the bounds are sharp, we should be able to clearly see a qualitative change in the behavior of the algorithm when the number of samples is sufficient or not. The current experiments showing that the Chow-Lou algorithm is effective, but they fail to support the specific contributions of this paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an analysis of a classical algorithm to recover the causal structure from data under a particular case of the structural equation model (SEM) with polytree dependencies. The authors characterize the number of samples needed to recovering such structure successfully under different regimes. They also include other extensions such as the estimation of the inverse correlation matrix. Along with the theoretical study, they present numerical experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please add a description of the importance of studying DAG recovery under the polytree model.\n- Please add experiments showing that the bounds predicted by the theory are realized in practice.\n\nEditorial comments:\n- In paragraph 1 of the introduction: “For a summary, see the survey papers Drton…” -> “For a summary, see the survey papers by Drton…” In general, revise the sentences where the citation is inlined (\\citet) they should treat it as if they are talking about the authors and not about the paper.\n- In paragraph 2 of the introduction, towards the end, the authors state “[these] models have received a significant amount of research interest” and proceed to cite to papers that are more than 20 years old. Adding newer references would be useful.\n- The authors use the phrase “roughly speaking” twice in the introduction. I think that using an alternative like “in broad terms” would be more appropriate for a written format.\n- In paragraph 5 of the introduction, I do not understand the sentence “it has been shown in Rebane & Pearl (1987) that there holds the “mutual information decay”…”\n- At the beginning of Section 2.2, “Let’s” -> “Let us”\n- Section 3, first paragraph: “the famous Wright’s formula” -> “Wright’s famous formula”\n- Throughout section 3 and beyond, I found confusing that C is used as a scalar constant and also as a CPDAG. For example, C_0 in Lemma 9 and C_T in Theorem 14.\n- In Theorem 11, do the authors mean that “C is defined in Lemma 18”? Should it not be Lemma 9?\n- In the first paragraph of the proof of Theorem 11, “Corollary 3” -> “Lemma 3”\n- In the title of section 8, I think it is more standard the use if the singular “Discussion”.", "broader_impact_concerns": "Practical applications of algorithms for detecting causal structure might pose ethical challenges. Even if this work is theoretical and does not delve into particular applications, a cautionary note about extracting causal meaning out of DAG recovery would be beneficial for practitioners that may use this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "uvCFwWUBOn", "reviewer": "Reviewer_xRcG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Following up on my comments from the previous paragraph: The paper is well-written with great clarity and clean flow. The results are not surprising, the proofs mostly build on existing results and do not contain much novelty — which can be considered a weakness. However, not every paper needs to be very novel, especially for TMLR. I believe this paper can be a very helpful reference for the overall community as it ties up many aspects of the linear Gaussian polytree structure learning problem -- from sufficient and necessary sample sizes, distinctions between skeleton recovery and v-structure recovery, and adaptation of the PC algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the structure learning of directed polytree with linear Gaussian SEM. The main focus is on analyzing the well-known Chow-Liu algorithm for learning polytrees. To this end, some other well-known properties of linear Gaussian SEMs are leveraged for establishing\n- sufficient sample complexity of learning the skeleton (Theorem 11) and CPDAG (essentially, Markov equivalence class) (Theorem 14),  and extension of these results to group polytree linear SEMs (Section 6)\n- lower bounds for the structure learning (Theorem 16),\n- an adaptation of the PC algorithm to linear Gaussian polytrees (Theorem 19).\n- specializing the known precision matrix estimation results to polytrees (Theorem 24).\n\nThe proofs are rather straightforward and follow by specializing the existing results to linear Gaussian polytrees setting. That being said, to my knowledge, no other paper has taken this initiative. By investigating several aspects of the problem (e.g., relating the necessary and sufficient sample sizes, adapting the PC algorithm etc.), the paper does a good job of analyzing and cleaning up the analysis of Chow-Liu algorithm for linear Gaussian polytrees.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- I’d recommend authors expand the related work discussion to include structure learning of linear SEMs without polytree restriction. Some relevant references can be Peters and Bühlmann (2014) and Ghoshal and Honorio (2018), though I’m sure there are more recent relevant results as well. A brief discussion of these results, with a possible comparison with the results in the polytree setting, can be useful to position the paper and highlight the refinement achieved by assuming a polytree structure. \n\n- I believe the authors aimed the paper to be mostly self-contained. To achieve this, I think some of the existing results that are crucial for the results in this paper can be given in the appendix. For instance, the results of Vershynin (2012) and Kalish and Bühlmann (2007) are repeatedly leveraged in the proofs. Explicitly stating those results in the appendix can make the paper more self-contained. Similarly, the supposedly trivial omitted proofs (e.g. proof of Lemma 23) can be added to the appendix.\n\n- Correlation decay: This is overly emphasized in the introduction, but is not discussed in detail in the main sections. I feel like there can be a better discussion on its role and why it’s necessary (using references and/or examples).\n\n- Section 6: Some explanation on the motivation and importance of this extension would have been nice. I am not aware of much work in this line (group polytree linear SEMs), so it may be worth it to explain *why* it’s an extension that’s worthy of attention in this paper.\n\n- On experiments, it might be worth it to further explore non-polytrees via synthetic graphs, e.g., what happens when the graph to be learned is not exactly a polytree but differs from the nearest polytree by only a few edges. \n\nThe following points are mostly minor nitpicks. I simply suggest the authors consider the following points when revising the paper, but they are not crucial for the acceptance of the paper.\n\n- Page 3: Before eq.(3), it is said that $\\epsilon_j$’s are usually with different variances. In principle, I agree with it. However, despite being a limitation, structure learning literature commonly assumes that noise variances are equal (e.g., Peters and Bühlmann (2014)). \n\n- Theorem 11: Isn’t $C$ used here already defined in Lemma 9? So instead of Lemma, it should be Lemma 9 in Theorem 11 statement.\n\n- Section 5 intro: Perhaps this can be more upfront and mention the subsequent results. I think the importance of this section is the nice connection between precision matrix estimation and the graph via v-structures. Considering $\\Theta_{ij}$ in eq. (12), this is not surprising. Nevertheless, to my knowledge Theorem 24 is novel, and the appearance of v-structures in the estimation guarantees can be mentioned at the beginning of the section to prepare the reader. \n\n- $\\gamma_{\\rm crit}$. Does $crit$ refer to critical? It appears a little bit out of context when first introduced on Page 5. It says that the choice of threshold is discussed in subsequent sections, but perhaps it warrants one more sentence to discuss its role on Page 5. Also, see typo in $\\rho_{cirt}$, and inconsistency of $\\gamma_{\\rm crit}$ vs. $\\gamma_{crit}$. Also, I’m not sure whether using *both* $\\rho_{crit}$ and $\\gamma_{crit}$ is intentional.\n- Page 6: $\\mathbf{B}$ is permutationally similar to a *strictly* upper triangular matrix.\n- Remark 28: missing period at the end of sentence.\n- Section 7.2: Perhaps mention earlier that ALARM is not a polytree. \n\nPeters, J., & Bühlmann, P. (2014). Identifiability of Gaussian structural equation models with equal error variances. Biometrika, 101(1), 219-228.\n\nGhoshal, A., & Honorio, J. (2018). Learning linear structural equation models in polynomial time and sample complexity. In International Conference on Artificial Intelligence and Statistics (pp. 1466-1475).", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper examines the required sample size conditions for polytree learning within the linear SEM model. It establishes conditions for recovering the skeleton and CPDAG using the Chow-Liu algorithm, linking them to the correlation bounds between variables and the estimation error in finite sample scenarios. The theoretical finds are verified by the experiments. While the results in this paper are not very novel and surprising, all the reviewers believe this is a solid work. Based on the review comments, I recommend acceptance of this paper.
Decision: Accept (poster)