Revisiting Bayesian network learning with small vertex cover

Juha Harviainen, Mikko Koivisto
Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, PMLR 216:819-828, 2023.

Abstract

The problem of structure learning in Bayesian networks asks for a directed acyclic graph (DAG) that maximizes a given scoring function. Since the problem is NP-hard, research effort has been put into discovering restricted classes of DAGs for which the search problem can be solved in polynomial time. Here, we initiate investigation of questions that have received less attention thus far: Are the known polynomial algorithms close to the best possible, or is there room for significant improvements? If the interest is in Bayesian learning, that is, in sampling or weighted counting of DAGs, can we obtain similar complexity results? Focusing on DAGs with bounded vertex cover number—a class studied in Korhonen and Parviainen’s seminal work (NIPS 2015)—we answer the questions in the affirmative. We also give, apparently the first, proof that the counting problem is $#$P-hard in general. In addition, we show that under the vertex-cover constraint counting is $#$W[1]-hard.

Cite this Paper

BibTeX
@InProceedings{pmlr-v216-harviainen23a, title = {Revisiting {B}ayesian network learning with small vertex cover}, author = {Harviainen, Juha and Koivisto, Mikko}, booktitle = {Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence}, pages = {819--828}, year = {2023}, editor = {Evans, Robin J. and Shpitser, Ilya}, volume = {216}, series = {Proceedings of Machine Learning Research}, month = {31 Jul--04 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v216/harviainen23a/harviainen23a.pdf}, url = {https://proceedings.mlr.press/v216/harviainen23a.html}, abstract = {The problem of structure learning in Bayesian networks asks for a directed acyclic graph (DAG) that maximizes a given scoring function. Since the problem is NP-hard, research effort has been put into discovering restricted classes of DAGs for which the search problem can be solved in polynomial time. Here, we initiate investigation of questions that have received less attention thus far: Are the known polynomial algorithms close to the best possible, or is there room for significant improvements? If the interest is in Bayesian learning, that is, in sampling or weighted counting of DAGs, can we obtain similar complexity results? Focusing on DAGs with bounded vertex cover number—a class studied in Korhonen and Parviainen’s seminal work (NIPS 2015)—we answer the questions in the affirmative. We also give, apparently the first, proof that the counting problem is $#$P-hard in general. In addition, we show that under the vertex-cover constraint counting is $#$W[1]-hard.} }
Endnote
%0 Conference Paper %T Revisiting Bayesian network learning with small vertex cover %A Juha Harviainen %A Mikko Koivisto %B Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2023 %E Robin J. Evans %E Ilya Shpitser %F pmlr-v216-harviainen23a %I PMLR %P 819--828 %U https://proceedings.mlr.press/v216/harviainen23a.html %V 216 %X The problem of structure learning in Bayesian networks asks for a directed acyclic graph (DAG) that maximizes a given scoring function. Since the problem is NP-hard, research effort has been put into discovering restricted classes of DAGs for which the search problem can be solved in polynomial time. Here, we initiate investigation of questions that have received less attention thus far: Are the known polynomial algorithms close to the best possible, or is there room for significant improvements? If the interest is in Bayesian learning, that is, in sampling or weighted counting of DAGs, can we obtain similar complexity results? Focusing on DAGs with bounded vertex cover number—a class studied in Korhonen and Parviainen’s seminal work (NIPS 2015)—we answer the questions in the affirmative. We also give, apparently the first, proof that the counting problem is $#$P-hard in general. In addition, we show that under the vertex-cover constraint counting is $#$W[1]-hard.
APA
Harviainen, J. & Koivisto, M.. (2023). Revisiting Bayesian network learning with small vertex cover. Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 216:819-828 Available from https://proceedings.mlr.press/v216/harviainen23a.html.

Related Material