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 …

… The treewidth of a DAG is the treewidth of its corresponding moral graph. The treewidth
of a Bayesian network is the treewidth of its underlying DAG. An elimination order is a linear
ordering of the nodes in a graph. We say that an elimination order is perfect if for every node
in the order its higher-ordered neighbors form a clique (ie, are pairwise connected). …
Constraint (3a) ensures M has treewidth at most w by bounding the number of higher-ordered
neighbors of every node i (which is an alternative way of defining the treewidth of chordal …