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

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
 Keywords
 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:
 D. M. Chickering: Optimal structure identification with greedy
search. Journal of Machine Learning Research 3 (2002),
pp. 507554.
 V. Auvray, L. Wehenkel: On the construction of the inclusion
boundary neighbourhood for Markov equivalence clases of Bayesian network
structures. In Uncertainty in Artificial Intelligence 18 (A. Darwiche,
N. Friedman eds.), Morgan Kaufmann (2002), pp. 2635.
 Chapter 8 in M. Studeny:
Probabilistic Conditional Independence Structures. SpringerVerlag,
London, 2005.