# Learning Linear Polytree Structural Equation Models

arXiv: https://arxiv.org/abs/2107.10955 · HTML: https://mlsanity.com/paper/2107.10955/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 51 references that are in the map.
- First posted on arXiv 22 Jul 2021.

## Builds on (most cited first, 13 of 13)

- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Causal Structure Learning](https://mlsanity.com/paper/1706.09141/) (2017)
- [Learning Equivalence Classes of Bayesian Networks Structures](https://mlsanity.com/paper/1302.3566/) (2013)
- [Structure Learning in Graphical Modeling](https://mlsanity.com/paper/1606.02359/) (2016)
- [Learning linear structural equation models in polynomial time and sample complexity](https://mlsanity.com/paper/1707.04673/) (2017)
- [The Recovery of Causal Poly-Trees from Statistical Data](https://mlsanity.com/paper/1304.2736/) (2013)
- [An Algorithm for Deciding if a Set of Observed Independencies Has a Causal Explanation](https://mlsanity.com/paper/1303.5435/) (2013)
- [Learning a Tree-Structured Ising Model in Order to Make Predictions](https://mlsanity.com/paper/1604.06749/) (2016)
- [Learning Polytrees](https://mlsanity.com/paper/1301.6688/) (2013)
- [Distributional Equivalence and Structure Learning for Bow-free Acyclic Path Diagrams](https://mlsanity.com/paper/1508.01717/) (2015)
- [Robust estimation of tree structured Gaussian Graphical Model](https://mlsanity.com/paper/1901.08770/) (2019)
- [Subspace Perspective on Canonical Correlation Analysis: Dimension Reduction and Minimax Rates](https://mlsanity.com/paper/1605.03662/) (2016)
- [Learning of Tree-Structured Gaussian Graphical Models on Distributed Data under Communication Constraints](https://mlsanity.com/paper/1809.08067/) (2018)

## Built on by (most cited first, 1 of 1)

- [Estimating large causal polytrees from small samples](https://mlsanity.com/paper/2209.07028/) (2022)

## Abstract (arXiv)

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.