Relating graphical frameworks : undirected, directed acyclic and chain graph models

Abstract: "Researchers have systematically explored the Markov equivalence relationships among models from three classes of graphical models; the undirected, the directed acyclic, and the chain graph or block- recursive models. This paper considers the Markov equivalence relationships between models of different classes of graphical models and gives conditions for the existence of a model from a given class which is 'almost Markov equivalent' to a given model from another class. An example of such a condition which is well known in the literature is the Wermuth condition. In addition, for each of the classes of models correct algorithms for learning models from conditional independence facts are given. While correct algorithms for learning undirected and directed acyclic graphs from only conditional independence facts exist in the literature, no such algorithms exists [sic] for chain graphs. This paper presents algorithms for learning undirected and directed acyclic graphs to highlight the relationship between the learning problems for these classes of models and the learning problem for chain graphs. The learning algorithms are proved correct and are shown to run in polynomial time in the number of vertices for fixed degree graphs except for one algorithm for learning undirected graphs which is polynomial in the number of vertices regardless of the degree of the graph."