Exact and Approximate Algorithms for Polytree Learning

Juha Harviainen, Frank Sommer, Manuel Sorge
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:40738-40747, 2026.

Abstract

Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of $n$ variables as a directed forest and are motivated by their more efficient inference and improved interpretability. Since the problem of learning the best polytree is NP-hard, we study which restrictions make it more tractable by considering for example in-degree bounds, properties of score functions measuring the quality of a polytree, and approximation algorithms. We devise an algorithm that finds the optimal polytree in time $\mathcal{O}((2+\epsilon)^n)$ for arbitrarily small $\epsilon > 0 $ and any constant in-degree bound $k$, improving over the fastest previously known algorithm of time complexity $\mathcal{O}(3^n)$. We further give polynomial-time algorithms for finding a polytree whose score is within a factor of $k$ from the optimal one for arbitrary scores and a factor of $2$ for additive ones. Many of the results are complemented by (nearly) tight lower bounds for either the time complexity or the approximation factors.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-harviainen26a, title = {Exact and Approximate Algorithms for Polytree Learning}, author = {Harviainen, Juha and Sommer, Frank and Sorge, Manuel}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {40738--40747}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/harviainen26a/harviainen26a.pdf}, url = {https://proceedings.mlr.press/v306/harviainen26a.html}, abstract = {Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of $n$ variables as a directed forest and are motivated by their more efficient inference and improved interpretability. Since the problem of learning the best polytree is NP-hard, we study which restrictions make it more tractable by considering for example in-degree bounds, properties of score functions measuring the quality of a polytree, and approximation algorithms. We devise an algorithm that finds the optimal polytree in time $\mathcal{O}((2+\epsilon)^n)$ for arbitrarily small $\epsilon > 0 $ and any constant in-degree bound $k$, improving over the fastest previously known algorithm of time complexity $\mathcal{O}(3^n)$. We further give polynomial-time algorithms for finding a polytree whose score is within a factor of $k$ from the optimal one for arbitrary scores and a factor of $2$ for additive ones. Many of the results are complemented by (nearly) tight lower bounds for either the time complexity or the approximation factors.} }
Endnote
%0 Conference Paper %T Exact and Approximate Algorithms for Polytree Learning %A Juha Harviainen %A Frank Sommer %A Manuel Sorge %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-harviainen26a %I PMLR %P 40738--40747 %U https://proceedings.mlr.press/v306/harviainen26a.html %V 306 %X Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of $n$ variables as a directed forest and are motivated by their more efficient inference and improved interpretability. Since the problem of learning the best polytree is NP-hard, we study which restrictions make it more tractable by considering for example in-degree bounds, properties of score functions measuring the quality of a polytree, and approximation algorithms. We devise an algorithm that finds the optimal polytree in time $\mathcal{O}((2+\epsilon)^n)$ for arbitrarily small $\epsilon > 0 $ and any constant in-degree bound $k$, improving over the fastest previously known algorithm of time complexity $\mathcal{O}(3^n)$. We further give polynomial-time algorithms for finding a polytree whose score is within a factor of $k$ from the optimal one for arbitrary scores and a factor of $2$ for additive ones. Many of the results are complemented by (nearly) tight lower bounds for either the time complexity or the approximation factors.
APA
Harviainen, J., Sommer, F. & Sorge, M.. (2026). Exact and Approximate Algorithms for Polytree Learning. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:40738-40747 Available from https://proceedings.mlr.press/v306/harviainen26a.html.

Related Material