Approximate Polytree Learning with Submodular Local Scores

Polytrees are a special case of Bayesian networks that seek to capture the conditional dependencies between variables as directed graphs whose underlying undirected graphs are acyclic. In the score-based approach to learning the structure of a polytree, we assign a score for each possible set of parents of each node to measure its quality, with the goal being to maximize the sum of the scores. As there is a variety of possible score functions, it is common to treat the scores as arbitrary blackbox functions, making structure learning NP-hard. At the other extreme, there has been research where additive scores have been assumed, which imposes a lot of structure on the score function but is an unrealistically strong assumption. We seek a middle ground and study the problem for submodular functions, to which the scores are empirically relatively close. We prove that the problem remains NP-hard for submodular scoring functions but also design a local-search algorithm that is guaranteed to find a structure whose score is within a factor of $2$ from the optimal one, and if the maximum in-degree of the polytree is bounded, then a single iteration of the algorithm takes polynomial time. Moreover, we show empirically, that the number of iterations of our algorithm is small. Further, we show that this result can be generalized to functions that are close to being submodular without significantly worsening the approximation guarantee.