Advances in Learning Bayesian Networks of Bounded Treewidth

Siqi Nie, Denis Deratani Mauá, Cassio Polpo de Campos, Qiang Ji

TL;DR

This paper introduces new exact and approximate algorithms for learning Bayesian networks with a bounded treewidth. The exact method uses mixed-integer linear programming (MILP) to simultaneously learn the network structure and enforce the treewidth constraint, outperforming existing methods on moderately sized problems. For larger domains, an approximate method based on sampling k-trees offers a scalable solution.

What Problem Does This Paper Address?

Bayesian networks are powerful tools for representing complex probabilistic relationships between variables. However, performing exact inference (like calculating probabilities or finding the most likely configuration) on these networks is computationally expensive, with complexity often scaling exponentially with the network's "treewidth." Treewidth is a graph-theoretic measure of how "tree-like" a graph is; lower treewidth means simpler structure and faster inference. While learning Bayesian networks without treewidth constraints is a well-studied problem, learning networks with a bounded treewidth is crucial for enabling efficient and reliable inference, especially in the presence of missing data. Existing methods for bounded treewidth learning either struggle with larger networks or are less efficient. This paper aims to bridge this gap by developing both exact and approximate algorithms that can learn Bayesian networks with a hard constraint on their treewidth, handling larger problems than previously possible.

Methods

The paper presents two main approaches:

  • Exact Method (MILP Formulation): This method combines existing mixed-integer linear programming (MILP) formulations for structure learning and treewidth computation. The novel aspect is a unified MILP formulation that directly encodes the treewidth constraint alongside the structure learning objective. This allows for finding the optimal Bayesian network structure that satisfies a given treewidth bound. A key advantage is that this formulation generates problems of polynomial size in the number of variables, avoiding the need for complex techniques like cutting planes used in some prior MILP approaches. The MILP formulation also naturally supports "anytime" algorithms, providing approximate solutions and error bounds that improve over time.
  • Approximate Method (k-tree Sampling): For larger domains where the exact MILP becomes intractable, the authors propose an approximate method. This approach leverages the fact that the moral graph of a bounded treewidth Bayesian network must be a subgraph of a k-tree (a maximal graph of treewidth k). The method involves:
  • Sampling k-trees: Using a technique based on "Dandelion codes," they efficiently sample k-trees uniformly at random.
  • Learning within k-trees: For each sampled k-tree, they then search for the best Bayesian network structure whose moral graph is a subgraph of that k-tree. This search can be done exactly (using a dynamic programming approach) or approximately (using a greedy method guided by sampled partial orders). This "double sampling" strategy (sampling k-trees and then sampling partial orders) allows for exploring a much larger space of potential structures than exact methods.

Datasets

The authors evaluate their methods on a collection of public datasets from the UCI repository. These datasets vary in dimensionality, ranging from 9 to 100 variables. The specific datasets used include: nursery, breast, housing, adult, zoo, letter, mushroom, wdbc, audio, hill, and community. The data was pre-processed by discretizing variables over their median value when necessary, and some variables with constant values or missing data were removed.

Key Insights and Ideas

  • MILP for Treewidth is Tractable (for moderate sizes): The paper demonstrates that a well-designed MILP formulation can effectively learn Bayesian networks with bounded treewidth, outperforming existing exact methods on moderately sized problems. This suggests that MILP is a powerful tool for this constrained learning task.
  • k-trees as a Foundation for Approximation: The insight that the moral graph of a bounded treewidth network must be a subgraph of a k-tree is central to the approximate method. This provides a structured way to sample candidate graph structures that are guaranteed to be compatible with the treewidth constraint.
  • Double Sampling for Scalability: The combination of sampling k-trees and then sampling partial orders within those k-trees is a clever way to overcome the limitations of exact methods. It allows for exploring a vast search space efficiently, leading to good approximate solutions for larger and more complex problems.
  • Trade-off between k-tree quality and structure search: Empirical results suggest that spending more effort on finding good k-trees (as in Version 2 of Algorithm 1) is more beneficial than optimizing the structure within a single k-tree (as in Version 1), especially when computational time is limited.

Key Results

  • Exact MILP Outperforms State-of-the-Art: The proposed MILP formulation for exact learning significantly outperforms a previous dynamic programming approach (K&P) in terms of computational time, solving problems with more variables and higher treewidth bounds. For instance, on the "adult" dataset with treewidth 4, the MILP approach finds a solution in seconds, while K&P takes minutes.
  • Approximate Method Scales Better: The approximate sampling-based method (Algorithm 1, Version 2) is shown to be much faster per iteration than the exact MILP and can handle larger datasets (up to 100 variables) where the MILP fails.
  • Version 2 Superior to Version 1: Algorithm 1, Version 2 (sampling k-trees and partial orders) consistently outperforms Version 1 (sampling k-trees and exact structure search within) in terms of solution quality within a fixed time budget, likely due to its faster iteration time allowing for broader exploration.
  • MILP Struggles with Large Domains: While effective for moderate problems, the MILP formulation becomes computationally prohibitive for datasets with over 50 variables due to the cubic number of constraints.

Limitations and Future Work

  • MILP Scalability: The primary limitation of the exact MILP approach is its inability to scale to large numbers of variables (beyond ~50) due to the cubic complexity of certain constraints.
  • Approximate Method's Trade-offs: While the approximate method is scalable, it does not guarantee optimality. The quality of solutions can degrade for very large domains, and the MILP formulation is unable to find reasonable solutions for datasets with 100 variables within the given time limits.
  • Future Work: The authors suggest exploring other search methods that can be integrated with their sampling approach, such as local search or local permutations of orderings. They also highlight the need for empirical comparisons with other recent works that independently developed similar MILP formulations. Further research could also focus on improving the efficiency of the MILP formulation itself or exploring more advanced sampling strategies.

Summary updated

Abstract

This work presents novel algorithms for learning Bayesian networks of bounded treewidth. Both exact and approximate methods are developed. The exact method combines mixed integer linear programming formulations for structure learning and treewidth computation. The approximate method consists in sampling k-trees (maximal graphs of treewidth k), and subsequently selecting, exactly or approximately, the best structure whose moral graph is a subgraph of that k-tree. The approaches are empirically compared to each other and to state-of-the-art methods on a collection of public data sets with up to 100 variables.
BibTeX
@inproceedings{nie2014advances,
  author = {Siqi Nie and Denis Deratani Mauá and Cassio Polpo de Campos and Qiang Ji},
  title = {{Advances in Learning Bayesian Networks of Bounded Treewidth}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure