Tractable Bayesian Network Structure Learning with Bounded Vertex Cover Number
Both learning and inference tasks on Bayesian networks are NP-hard in general. Bounded tree-width Bayesian networks have recently received a lot of attention as a way to circumvent this complexity issue; however, while inference on bounded tree-width networks is tractable, the learning problem remains NP-hard even for tree-width 2. In this paper, we propose bounded vertex cover number Bayesian networks as an alternative to bounded tree-width networks. In particular, we show that both inference and learning can be done in polynomial time for any fixed vertex cover number bound k, in contrast to the general and bounded tree-width cases; on the other hand, we also show that learning problem is W[1]-hard in parameter k. Furthermore, we give an alternative way to learn bounded vertex cover number Bayesian networks using integer linear programming (ILP), and show this is feasible in practice.
The paper describes a new class of Bayes nets for which inference and structure learning can be done in polynomial time.This is the class of Bayes nets with a bounded vertex cover number.So far, the only other class of Bayes nets for which inference and structure learning is tractable is the class of trees.Hence, this is an important contribution that advances our understanding of tractable probabilistic graphical models.The paper also describes two algorithms to find the best Bayes net structure for a bounded vertex cover k, however it is not clear whether practitioners would want to use those algorithms.For a fixed k, those algorithms are polynomial in the number of nodes n, but in practice it is not clear what k to use. So one would probably start with a small k and then increase k if there is some time left.Unfortunately, the algorithms scale exponentially with k, so the search would have to be restricted to small k's. It is not clear either why one would restrict the search to Bayes net with a bounded vertex cover.I understand that a bounded vertex cover implies that inference will be tractable, but this is also the case for Bayes nets with a bounded tree width. So it seems to me that practitioners would want to do the largest search possible in the space of Bayes nets that allow tractable inference. Since that space is too large for an exhaustive search, then it would make sense to focus on structures that are likely to arise in practice.It is not clear that Bayes nets with a bounded vertex cover are more likely to occur in practice than other types of tractable Bayes nets with an unbounded vertex cover.As explained in the paper, Bayes nets with a bounded vertex cover tend to have a star shape with a dense core, but I'm unaware of real problems with such a structure. To verify whether it is better to prioritize the search by increasing the bound on the vertex cover instead of the tree width, could you report two curves (one for prioritizing the search based on the vertex cover number and the other based on the tree-width) that show how the accuracy improves with time?   The paper is clear and well written.I noticed one minor typo. On the first line of page 3, the width of a tree decomposition should be *max_i* |X_i|-1.The experiments include many benchmarks, which is great.However it is difficult to tell what are the trends in those large tables of numbers.Can you bold the best result for each problem and then indicate how many problems each algorithm ended up winning?Can you also report the standard error for K-fold cross validation or some statistical test, otherwise it is not clear when some results are really better.