Abstract

We study a broad class of graphical models whose independencies correspond to vertex separation in mixed graphs with directed, undirected, and bidirected edges, that are capable of encoding independence structures arising from feedback, latent and selection mechanisms. We introduce separable graphs, in which each missing edge implies the existence of a separating set for its endpoints, and essentially separable graphs, those graphs separation equivalent to a separable graph. We provide characterizations of separable graphs and essentially separable graphs and show that essentially separable graphs are essentially acyclic graphs, that is, they are separation equivalent to an acyclic graph. We provide two characterizations of the separation equivalence of separable graphs. The first is a direct generalizations of previous characterizations for subfamilies of separable graphs. This characterization requires both adjacency and orientation information about the graphs. The second characterization, however, only depends on adjacency and separation properties of the graphs. In particular, we use separation properties to define arrowhead inducing pairs of vertices. Such pairs of vertices guarantee the existence of an arrowhead on any edge between them. Our characterization is then given in terms of adjacency and edges with arrowhead inducing endpoints. We use arrowhead inducing pairs of vertices to provide a representation of the equivalence classes of essentially separable graphs and to develop an algorithm that, under suitable assumptions, identifies the equivalence class of any essentially separable graphical model. This talk is based on the manuscript ``Characterizing and identifying separable graphical models’’ by Christopher Meek and Kayvan Sadeghi.