M. Studeny: Characterization of inclusion neighbourhood in terms of the essential graph: lower neighbours. In Proceedings of WUPES'2003 (J. Vejnarova ed.), School of Economics Prague 2003, pp. 243-262.

Abstract
The topic of the contribution is to characterize the inclusion neighbourhood of a given equivalence class of Bayesian networks in terms of the respective essential graph so that it can be used efficiently in a method of local search for maximization of a quality criterion. One can distinguish two kinds of neighbours: upper and lower ones. This paper gives a characterization of the lower inclusion neighbourhood. It is shown that each lower inclusion neighbour is uniquely described by a pair ([a,b],C) where [a,b] is an unordered pair of distinct nodes which is not an edge in the essential graph and C a disjoint set of nodes. The second basic result is that, for given [a,b], the collection of those sets C which correspond to lower inclusion neigbours has a special form. More specifically, given [a,b], the respective collection of sets is the union of at most two tufts of sets. The least and maximal sets of these two tufts, which determine them, can also be read from the essential graph.

AMS classification 68T30, 62H05

Keywords
(Markov) equivalence of Bayesian networks
learning Bayesian networks
essential graph
inclusion neighbourhood
lower neighbours
tuft of sets

A pdf copy (converted postscript version) (312kB) is available.

The paper partially builds on the following papers: