# Learning Polytrees

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2013.

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

- [Graph Neural Networks Designed for Different Graph Types: A Survey](https://mlsanity.com/paper/2204.03080/) (2022)
- [Efficient Bayesian network structure learning via local Markov boundary search](https://mlsanity.com/paper/2110.06082/) (2021)
- [On the Parameterized Complexity of Polytree Learning](https://mlsanity.com/paper/2105.09675/) (2021)
- [Learning bounded-degree polytrees with known skeleton](https://mlsanity.com/paper/2310.06333/) (2023)
- [Optimal estimation of Gaussian (poly)trees](https://mlsanity.com/paper/2402.06380/) (2024)
- [The Complexity of Bayesian Network Learning: Revisiting the Superstructure](https://mlsanity.com/paper/2602.10253/) (2026)
- [Learning Linear Polytree Structural Equation Models](https://mlsanity.com/paper/2107.10955/) (2021)
- [Distribution Learning Meets Graph Structure Sampling](https://mlsanity.com/paper/2405.07914/) (2024)
- [Learnability of Parameter-Bounded Bayes Nets](https://mlsanity.com/paper/2407.00927/) (2024)
- [Learning the Finer Things: Bayesian Structure Learning at the Instantiation Level](https://mlsanity.com/paper/2303.04339/) (2023)
- [Learning Linear Gaussian Polytree Models with Interventions](https://mlsanity.com/paper/2311.04636/) (2023)
- [Optimal structure learning and conditional independence testing](https://mlsanity.com/paper/2507.05689/) (2025)
- [Exact and Approximate Algorithms for Polytree Learning](https://mlsanity.com/paper/2605.03622/) (2026)
- [Entropy Equivalence Testing](https://mlsanity.com/paper/2605.23225/) (2026)

## Abstract (arXiv)

We consider the task of learning the maximum-likelihood polytree from data. Our first result is a performance guarantee establishing that the optimal branching (or Chow-Liu tree), which can be computed very easily, constitutes a good approximation to the best polytree. We then show that it is not possible to do very much better, since the learning problem is NP-hard even to approximately solve within some constant factor.