Abstract

One of the most common ways of representing classes of equivalent Bayesian networks is the use of essential graphs. These chain graphs are also known in the literature as completed patterns or completed pdags. The name essential graph was proposed by Andersson, Madigan and Perlman (1997) who also gave a graphical characterization of essential graphs. In this contribution an alternative characterization of essential graphs is presented. The main observation is that every essential graph is the largest chain graph within a special class of chain graphs. More precisely, every equivalence class of Bayesian networks is contained in an equivalence class of chain graphs without flags (= certain induced subgraphs). A special operation of legal merging of (connectivity) components for a chain graph without flags is introduced. This operation leads to an algorithm for finding the essential graph on the basis of any graph in that equivalence class of chain graphs without flags which contains the equivalence class of a Bayesian network. In particular, the algorithm may start with any Bayesian network.

AMS classification 68T30, 62H05

Keywords

Bayesian network

chain graph

essential graphs

flag

legal merging

A pdf copy of a preprint (330kB) is available.

The paper partially builds on the work:

• S. A. Andersson, D. Madigan, and M. D. Perlman: A characterization of Markov equivalence classes for acyclic digraphs. Annals of Statistics 25 (1997), pp. 505-541.