J. Cussens, M. Studeny, D. Haws:
Polyhedral aspects of score equivalence in Bayesian network structure learning.
Mathematical Programming A
164 (2017), n. 1/2, pp. 285324.
 Abstract

This paper deals with faces and facets of the familyvariable polytope and
the characteristicimset polytope, which are special polytopes used
in integer linear programming approaches to statistically learn Bayesian network structure.
A common form of linear objectives to be maximized in this area leads to
the concept of score equivalence (SE), both for linear objectives and for faces of the
familyvariable polytope.
We characterize the linear space of SE objectives and establish a onetoone
correspondence between SE faces of the familyvariable polytope, the faces of
the characteristicimset polytope, and standardized supermodular
functions. The characterization of SE facets in terms of extremality of the
corresponding supermodular function gives an elegant method to verify whether an inequality
is SEfacetdefining for the familyvariable polytope.
We also show that when maximizing an SE objective one can eliminate
linear constraints of the familyvariable polytope that correspond to nonSE facets.
However, we show that solely considering SE facets is not enough as a counterexample shows;
one has to consider the linear inequality constraints that correspond to facets of the
characteristicimset polytope despite the fact that they may not define facets in the familyvariable mode.
 AMS classification 52B12 90C27 68Q32
 Keywords
 familyvariable polytope
 characteristicimset polytope
 score equivalent face/facet
 supermodular set function
 A
pdf version of a preprint (415kB) is available. Besides that,
a fulltext viewonly version of the paper is also available.
The paper builds on results from the following publications:
 J. Cussens:
Bayesian network learning with cutting planes.
In Uncertainty in Artificial Intelligence. Proceedings of the
27th Conference (F. Cozman, A. Pfeffer eds.),
AUAI Press, Corvallis 2011, pp. 153160.
 M. Bartlett, J. Cussens:
Advances in Bayesian network learning using integer programming.
In Uncertainty in Artificial Intelligence. Proceedings of the
29th Conference (A. Nicholson, P. Smyth eds.),
AUAI Press, Corvallis 2013, pp. 182191.
 R. Hemmecke, S. Lindner, M. Studeny:
Characteristic imsets for learning Bayesian network structure.
International Journal of Approximate Reasoning
53 (2012), n. 9, pp. 13361349.
 M. Studeny, D. Haws:
Learning Bayesian network structure: towards the essential graph by integer linear programming tools.
International Journal of Approximate Reasoning
55 (2014), pp. 10431071.
 G. Orlinskaya (2014)
Linear constraints on standard and characteristic imsets for learning Bayesian network structures.
Diploma thesis, TU Munich.
 T. Jaakkola, D. Sontag, A. Globerson, M. Meila.
Learning Bayesian network structure using LP relaxations.
In JMLR Workshops and Conference Proceedings
9 Proceedings of the 13th International Conference on Artificial Intelligence and Statistics [AISTATS 2010],
(Y.W. Teh, M. Titterington eds.), pp. 358365.
Moreover, the paper is related to the results presented in the following paper: