Abstract

In 2010, M. Studený, R. Hemmecke, and S. Lindner explored a new algebraic description of graphical models, called characteristic imsets. Compared with standard imsets, characteristic imsets have several advantages: they are still unique vector representatives of conditional independence structures, 0-1 vectors, and more intuitive in terms of graphs than standard imsets. After defining a characteristic imset polytope (cim-polytope) as the convex hull of all characteristic imsets with a given set of nodes, they also showed that a model selection in graphical models, which maximizes a quality criterion, can be converted into a linear programming problem over the cim-polytope. However, in general, for a fixed set of nodes, the cim-polytope can have exponentially many vertices over an exponentially high dimension. Therefore, in this paper, we focus on the family of directed acyclic graphs whose nodes have a fixed order. This family includes diagnosis models described by bipartite graphs with a set of m nodes and a set of n nodes for any m, n ∈ Z+. We first consider cim-polytopes for all diagnosis models and show that these polytopes are direct products of simplices. Then we give a combinatorial description of all edges and all facets of these polytopes. Finally, we generalize these results to the cim-polytopes for all Bayesian networks with a fixed underlying ordering of nodes with or without fixed (or forbidden) edges.

Document Type

Article

Publication Date

2015

Notes/Citation Information

Published in SIAM Journal on Discrete Mathematics, v. 29, no. 2, p. 697-715.

First Published in SIAM Journal on Discrete Mathematicsin v. 29, no. 2, published by the Society of Industrial and Applied Mathematics (SIAM). © 2015, Society for Industrial and Applied Mathematics. Unauthorized reproduction of this article is prohibited.

Digital Object Identifier (DOI)

http://dx.doi.org/10.1137/130933848

Download

Share

COinS