Parameterized Complexity Results for Exact Bayesian Network Structure Learning

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).

References in corpus (6)

• A Transformational Characterization of Equivalent Bayesian Network Structures
• A simple approach for finding the globally optimal Bayesian network structure
• Ordering-Based Search: A Simple and Effective Algorithm for Learning Bayesian Networks
• Finding a Path is Harder than Finding a Tree
• Advances in exact Bayesian structure discovery in Bayesian networks
• Algorithms and Complexity Results for Exact Bayesian Structure Learning

Cited by in corpus (5)

• Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
• Selective Greedy Equivalence Search: Finding Optimal Bayesian Networks Using a Polynomial Number of Score Evaluations
• Maximizing Social Welfare in Score-Based Social Distance Games
• Efficient Bayesian network structure learning via local Markov boundary search
• Lower Bounds for QBFs of Bounded Treewidth