Petter Restadh: Edges of the Characteristic Imset Polytope
Time: Wed 2022-09-14 10.15 - 11.15
Participating: Petter Restadh (KTH)
Abstract: The characteristic imset of a directed acyclic graph (DAG) D is a 0/1-vector that encodes the probabilistic model of D. The characteristic imset polytope (CIM_p) is the convex hull of all these vectors and was first introduced by Studený, Hemmecke and Lindner to transform causal discovery into a linear optimization problem. It was recently shown that many algorithms for causal discovery could be interpeted as greedy edge-walks on the faces of CIM_p. In this talk we will discuss these lower dimensional faces of this polytope and see their combinatorial interpretations. We will also showcase some recent results on the edge-structure and discuss what implication these edges can have on causal discovery algorithms. These new edges will also lead us to a connection between the stable set polytope and some particular faces of CIM_p.
This talk is based on the articles Greedy Causal Discovery is Goemetric (Linusson-R-Solus, 2021) and On the Edges of the Characteristic Imset Polytopes (Linusson-R-Solus, 2022).