Sunday , August 9 2020

Chain Graphs and Directed Acyclic Graphs Improved by Equivalence Classes and their Essential Graphs

Departamento de Matemáticas Fundamentales
Facultad de Ciencias, UNED, Madrid, Spain

To Prof. Dr. Eng. Neculai Andrei, great mathematician and friend, on his 60th birthday.

Abstract: There exists the possibility to improve the efficiency of Bayesian Network learning procedures, by selecting as search space the equivalence classes of Directed Acyclic Graphs (DAGs), or the more general of Chain Graphs (CGs), and from them we can select an essential graph as representative of each class. Furthermore, we describe and advance some new results, with efficient algebraic tools, as Imsets, Semigraphoids, Matroids and so on.

Keywords: A. I., Graph Theory, Bayesian Networks.

Angel Garrido is Full (time) Professor, belonging to the Department of Fundamental Mathematics, in the Faculty of Sciences of UNED (Universidad Nacional de Educación a Distancia), Madrid, Spain, where he imparts Mathematical Analysis for Physics to his students and does research by collaborating with the research Department of Artificial Intelligence, ETS Ingeniería Informática, also at UNED. He runs complete studies on Mathematics and Computation into the Faculty of Mathematics, at Universities Complutense, UNED and Polytechnic of Madrid; also gives lectures on different subjects of Computer Science, as Automata Theory, Complexity and Computability, A. I., Statistical Inference. Furthermore, on Mathematics in ETS of Architecture, at Polytechnic University of Madrid and distinct Institutes. Prof. Garrido runs also Summer Courses at UNED, on Art and Mathematics, with subjects as Geometry of Gaudi architectural work, or Analysis of the Cordobe Mosque and so on. Lately he’s been imparting Seminars on different research lines, as Causality, Probabilistic Graphical Models (PGMs), Essential Graphs and so on. His published works comprise until now forty-five research papers, which appeared in different prestigious international scientific journals. With active participation in more than forty international conferences, on Mathematics and Computation. Being member of Scientific Committee of many of such Congresses. And belonging to the Editorial Board of some scientific international journals, as AUA (Acta Universitatis Apulensis), IJOPMCS (International Journal of Open Problems on Mathematics and Computer Science), IJMA (International Journal of Mathematical Analysis), AS (Agora Studies), and so on. Prof. Garrido is the author of five books on  Mathematical Analysis, ODE, Physics of Sound and Acoustics. He also holds the First Birhäuser Prize to the Best Communication, at the ICM (International Congress of Mathematicians, Madrid, 2006).

>>Full text
Angel GARRIDO, Improved by Equivalence Classes and their Essential Graphs, Studies in Informatics and Control, ISSN 1220-1766, vol. 18 (1), pp. 39-40, 2009.

1. Bayesian Networks and Chain Graphs

Let S and S’ two structures of Bayesian Networks (abridged BNs) on V. Then, we say that S is equivalent to S’: S C S’, if S can represent every probability distribution which S’ represents and vice versa.

An essential graph of a structure of BN, S, is a PDAG such that their skeleton is the same that of S, and the essential edges (and only these) are directed.

Let C be a class of DAGs Markov equivalent among them. Then, their essential graph would be the smallest graph greater than every DAG that belongs to the class. If we denote the essential graph as G*, this is equivalent to saying G* = È { G: GÎ C} , where such graph union is reached by the union of the nodes and edges of G:

V (G*) = È V (G), E (G*) = È E (G)

So, G* will be the smallest of upper bound for all graphs of the represented class. A Chain Graph (denoted CG) is a generalization of both classical types: Undirected and Directed Graphs, that is, it includes UGs and DAGs, being represented by undirected and directed edges. Therefore, they are mixed graphs, composed by directed and undirected edges.

Two CGs are Markov Equivalent, if they represent the same statistical model.

3. Final Considerations

The first algebraic tool (Imset) is being developed and applied to more and more aspects of LBNs, searching new ways to improve their efficiency.

But in parallel works (and in some cases in the same paper), some other constructions are being introduced, as the aforementioned Graphoids, Semigraphoids, Pseudographoids and Matroids (see, for instance, the classic Oxley´s book). An advantage is that classic score criteria are linear functions of the standard imsets. There exists a relationship between both representations, by EGs.

But it remains some open problems, as the adequate characterization of neighbours in terms of standard imsets, and many others.


  1. Anderson, Madigan Perlman: A characterization of Markov equivalence classes for acyclic digraphs, Ann. Stat. 25, No. 2, 1997, pp. 505-541.
  2. Chickering, A transformational characterization of equivalent Bayesian Networks structures, UAI´95, pp. 87-98.
  3. Ibid.: Learning Equivalence Classes of Bayesian Network Structures, JMLR, 2, 2002, pp. 445-498.
  4. Gillispie, Perlman, Enumerating Markov Equivalence Classes of Acyclic Digraphs, UAI´2001, pp. 171-177.
  5. Oxley, Matroid Theory, Oxford University Press, New York, 1992.
  6. Roverato and Studený, A graphical representation of equivalence classes of AMP chain graphs, JMLR 7, 2006, pp. 1045-1078.
  7. Studený, Characterization of essential graphs by means of the operation of legal merging of components, Int. J. of Unc., Fuzziness and Knowledge – Based Systems 12, 2004, pp. 43-62.