Searching Across Markov Equivalent Directed Acyclic Graph Models

Learning the structure of a process that can be represented by a directed acyclic graph (DAG) based on data alone can be a challenging problem because many graphs may encode the same conditional independence relations. However, searching across equivalence classes can greatly reduce the search space, thereby making the search more efficient. This paper presents the DECS algorithm, which is an extension of Edwards and Havernack’s EH-procedure (Edwards, 1995) for undirected graphs to DAG equivalence classes. We also provide necessary graphical criterion for the DAG submodel relation and prove its sufficiency in special cases. This criterion facilitates the moves made across equivalence classes in the search space. Finally, the DECS algorithm is demonstrated on real data sets.