classes of Bayesian network structures may be

solved by searching for the maximum of a scor-

ing metric in a space of these classes. This paper

deals with the de?nition and analysis of one such

search space. We use a theoretically motivated

neighbourhood, the inclusion boundary, and rep-

resent equivalence classes by essential graphs.

We show that this search space is connected and

that the score of the neighbours can be evalu-

ated incrementally. We devise a practical way

of building this neighbourhood for an essential

graph that is purely graphical and does not ex-

plicitely refer to the underlying independences.

We ?nd that its size can be intractable, depend-

ing on the complexity of the essential graph of

the equivalence class. The emphasis is put on

the potential use of this space with greedy hill-

climbing search.

The problem of learning Markov equivalence classes of Bayesian network structures may be solved by searching for the maximum of a scoring metric in a space of these classes. This paper deals with the de?nition and analysis of one such search space. We use a theoretically motivated neighbourhood, the inclusion boundary, and represent equivalence classes by essential graphs. We show that this search space is connected and that the score of the neighbours can be evaluated incrementally. We devise a practical way of building this neighbourhood for an essential graph that is purely graphical and does not explicitely refer to the underlying independences. We ?nd that its size can be intractable, depending on the complexity of the essential graph of the equivalence class. The emphasis is put on the potential use of this space with greedy hillclimbing search.