M. Studeny: Characterization of inclusion neighbourhood in terms of the essential graph. International Journal of Approximate Reasoning 38 (2005), n.3, pp. 283-309.

The question of efficient characterization of inclusion neighbourhood is crucial in some methods for learning (equivalence classes of) Bayesian networks. In this paper, neighbouring equivalence classes of a given equivalence class of Bayesian networks are characterized efficiently in terms of the respective essential graph. One can distinguish two kinds of inclusion neighbours: upper and lower ones. This paper reveals the hidden internal structure of both parts of the inclusion neighbourhood. It is shown here that each inclusion neighbour is uniquely described by a pair ([a,b],C) where [a,b] is an unordered pair of distinct nodes and C a disjoint set nodes in the essential graph. Upper neighbours correspond to edges in the essential graph, while lower neighbours correspond to pairs of nodes that are not edges in the essential graph. Given a pair [a,b] of distinct nodes in the essential graph, the class of those sets C that ([a,b],C) encodes an inclusion neighbour is characterized. The class has a special form; it is uniquely determined by certain distinguished sets. These distinguished sets of the class can be read directly from the essential graph.

AMS classification 68T30, 62H05

learning Bayesian networks
inclusion neighbourhood
essential graph

A scanned pdf copy (478kB) is available.

The paper is an extended version of two conference papers:

The paper partially builds on the following publications: