mlsanityData to 7 Oct 2026

Learning Polytrees

arXiv 1301.6688 ↗First posted 23 Jan 2013cs.AI cs.LGcited by 14

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 1; 2023: 3; 2024: 3; 2025: 1; 2026: 3.

14 papers.

Sort:

  1. 2022Graph Neural Networks Designed for Different Graph Types: A Surveycited by 21
  2. 2021Efficient Bayesian network structure learning via local Markov boundary searchcited by 14
  3. 2021On the Parameterized Complexity of Polytree Learningcited by 6
  4. 2023Learning bounded-degree polytrees with known skeletoncited by 5
  5. 2024Optimal estimation of Gaussian (poly)treescited by 3
  6. 2026The Complexity of Bayesian Network Learning: Revisiting the Superstructurecited by 2
  7. 2021Learning Linear Polytree Structural Equation Modelscited by 1
  8. 2024Distribution Learning Meets Graph Structure Samplingcited by 1
  9. 2024Learnability of Parameter-Bounded Bayes Netscited by 1
  10. 2023Learning the Finer Things: Bayesian Structure Learning at the Instantiation Levelcited by 0
  11. 2023Learning Linear Gaussian Polytree Models with Interventionscited by 0
  12. 2025Optimal structure learning and conditional independence testingcited by 0
2 more
  1. 2026Exact and Approximate Algorithms for Polytree Learningcited by 0
  2. 2026Entropy Equivalence Testingcited by 0