2022/09/15 by Svante Linusson, Linusson, Svante, Petter Restadh +3 · 1 citation
Computer Science · #Bayesian Modeling and Causal Inference #Combinatorics (math.CO) #FOS: Mathematics #Machine Learning and Algorithms #Machine Learning and Data Classification #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2209.07579
openalex publication_date 2022/09/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The edges of the characteristic imset polytope, CIMp, were recently shown to have strong connections to causal discovery as many algorithms could be interpreted as greedy restricted edge-walks, even though only a strict subset of the edges are known. To better understand the general edge structure of the polytope we describe the edge structure of faces with a clear combinatorial interpretation: for any undirected graph G we have the face CIMG, the convex hull of the characteristic imsets of DAGs with skeleton G. We give a full edge-description of CIMG when G is a tree, leading to interesting connections to other polytopes. In particular the well-studied stable set polytope can be recovered as a face of CIMG when G is a tree. Building on this connection we are also able to give a description of all edges of CIMG when G is a cycle, suggesting possible inroads for generalization. We then introduce an algorithm for learning directed trees from data, utilizing our newly discovered edges, that outperforms classical methods on simulated Gaussian data.