Learning Treewidth-Bounded Bayesian Networks with Thousands of Variables
We present a method for learning treewidth-bounded Bayesian networks from data sets containing thousands of variables. Bounding the treewidth of a Bayesian network greatly reduces the complexity of inferences. Yet, being a global property of the graph, it considerably increases the difficulty of the learning process. Our novel algorithm accomplishes this task, scaling both to large domains and to large treewidths. Our novel approach consistently outperforms the state of the art on experiments with up to thousands of variables.
This paper uses k-trees to learn bounded tree-width Bayesian networks. The proposed method is built on Nie et al. 2016, which incrementally grows the k-tree and the BN as the subgraph of the k-tree. The parent set of a variable in the BN is restricted by the clique of k nodes that the variable is connected to in the k-tree. To find this clique of k nodes, the authors use A* algorithm similar to Nie et al. 2016 but with a different score function that is consistent with the overall objective function.  They also propose a greedy search approach instead of A* to increase the scalability.   
  The proposed method is very similar to previous work by Nie et al. -- both use k-trees to search for low-treewidth Bayesian networks, both start with a randomly chosen initial clique, and both propose using an A* method for finding the best tree.  The differences are that Nie et al. score k-trees using a mutual information score and use BDeu for choosing the final consistent Bayesian network, while this paper proposes using BIC and incrementally building the Bayesian network along with the k-tree, using the BN to score the k-tree.  This paper also includes the additional restriction that the complete variable (partial) order is chosen randomly, while in Nie et al. only the initial clique is chosen randomly.  The main justification for these differences is the ability to scale to large treewidths.  However, in the experiments, the previous S2 algorithm also can scale to large treewidths.  The experimental results look promising, showing that the new method can optimize BIC better (given a treewidth constraint and a particular bound on running time).                Comments: - Why use BIC instead of BDeu, as in previous work?  As the authors note, this makes their results incomparable to previous results; what are the advantages that outweigh this obvious disadvantage? - The score function in g(S) (line 135) is not explicitly defined. Do you mean BIC? - It would be helpful to see the performance of all methods with different time limits (e.g., 1 minute, 1 hour, 10 hours). - Many bounded-treewidth methods exist in the literature, some for learning chain graphs and some for learning BNs; the results would be more convincing with additional baselines. (I would be interested in seeing test set log-likelihood as well, though I understand that the stated goal of these algorithms is to optimize a particular criterion as well as possible, not to evaluate generalization.) - The paper is clear for the most part, but the presentation could be improved.  For example, it would help to show the full table of results for the large datasets, not just a boxplot and counts of which algorithm was better.  Supplementary material could be used for this if it will not fit in the main paper.  Minor: - The sentences at line 45 and 46 are redundant.  Maybe authors want to merge them together. - The space of learnable DAGs is not well explored. It would be interesting to see some experiments that show the edge recovery potential of the proposed algorithm by generating samples from a different set of synthetic graphs.