Enumerating Equivalence Classes of Bayesian Networks using EC Graphs


Eunice Yuh-Jie Chen, Arthur Choi Choi, Adnan Darwiche ;
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:591-599, 2016.


We consider the problem of learning Bayesian network structures from complete data. In particular, we consider the enumeration of their k-best equivalence classes. We propose a new search space for A* search, called the EC graph, that facilitates the enumeration of equivalence classes, by representing the space of completed, partially directed acyclic graphs. We also propose a canonization of this search space, called the EC tree, which further improves the efficiency of enumeration. Empirically, our approach is orders of magnitude more efficient than the state-of-the-art at enumerating equivalence classes.

Related Material