2012/06/02 by Jing Xi, Ruriko Yoshida, Xi, Jing +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Bayesian Modeling and Causal Inference #Combinatorics (math.CO) #Computational Drug Discovery Methods #FOS: Mathematics #Gene Regulatory Network Analysis #Statistics Theory (math.ST) #math.CO #math.ST #stat.TH
paper · pdf · doi:10.48550/arxiv.1206.0406
23 pages
openalex publication_date 2012/06/02 · arxiv created 2013/08/19 · arxiv updated 2013/08/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 2010, M. Studený, R. Hemmecke, and S. Linder explored a new algebraic description of graphical models, called characteristic imsets. Compare with standard imsets, characteristic imsets have several advantages: they are still unique vector representative of conditional independence structures, they are 0-1 vectors, and they are 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 (DAGs) whose nodes have a fixed order. This family includes diagnosis models which can be described by Bipartite graphs with a set of m nodes and a set of n nodes for any m, n ∈ \Z+. In this paper, 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.