M. Studeny: How matroids occur in the context of learning Bayesian network structure. In Uncertainty in Artificial Intelligence. Proceedings of the 31th Conference (M. Meila, T. Heskes eds.), AUAI Press, Corvallis 2015, pp. 832-841.

It is shown that any connected matroid having a non-trivial cluster of BN variables as its ground set induces a facet-defining inequality for the polytope(s) used in the ILP approach to globally optimal BN structure learning. The result applies to well-known k-cluster inequalities, which play a crucial role in the ILP approach.

AMS classification 68T30 52B40 68T05

learning Bayesian network structure
integer linear programming
extreme supermodular function

A pdf version (144kB) is available.

The contribution builds on the following papers: