Parameterized complexity results for exact Bayesian network structure learning
From MaRDI portal
Abstract: Bayesian network structure learning is the notoriously difficult problem of discovering a Bayesian network that optimally represents a given set of training data. In this paper we study the computational worst-case complexity of exact Bayesian network structure learning under graph theoretic restrictions on the (directed) super-structure. The super-structure is an undirected graph that contains as subgraphs the skeletons of solution networks. We introduce the directed super-structure as a natural generalization of its undirected counterpart. Our results apply to several variants of score-based Bayesian network structure learning where the score of a network decomposes into local scores of its nodes. Results: We show that exact Bayesian network structure learning can be carried out in non-uniform polynomial time if the super-structure has bounded treewidth, and in linear time if in addition the super-structure has bounded maximum degree. Furthermore, we show that if the directed super-structure is acyclic, then exact Bayesian network structure learning can be carried out in quadratic time. We complement these positive results with a number of hardness results. We show that both restrictions (treewidth and degree) are essential and cannot be dropped without loosing uniform polynomial time tractability (subject to a complexity-theoretic assumption). Similarly, exact Bayesian network structure learning remains NP-hard for "almost acyclic" directed super-structures. Furthermore, we show that the restrictions remain essential if we do not search for a globally optimal network but aim to improve a given network by means of at most k arc additions, arc deletions, or arc reversals (k-neighborhood local search).
Recommendations
Cited in
(16)- Searching for better fill-in
- Positive definite completion problems for Bayesian networks
- Exact Bayesian structure discovery in Bayesian networks
- Large-sample learning of Bayesian networks is NP-hard
- Finding optimal Bayesian network given a super-structure
- Learning factor graphs in polynomial time and sample complexity
- On finding optimal polytrees
- Objective Bayesian Nets for Integrating Consistent Datasets
- Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
- Learning Bayesian Networks Does Not Have to Be NP-Hard
- Maximizing Social Welfare in Score-Based Social Distance Games
- Slim tree-cut width
- The complexity of optimizing atomic congestion
- A complexity-theoretic analysis of majority illusion in social networks
- Slim tree-cut width
- Polynomial-time derivation of optimal k-tree topology from Markov networks
This page was built for publication: Parameterized complexity results for exact Bayesian network structure learning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4913753)
