Efficient Enumeration of Markov Equivalent DAGs


  • Marcel Wienöbst Universität zu Lübeck
  • Malte Luttermann Universität zu Lübeck
  • Max Bannach Universität zu Lübeck
  • Maciej Liskiewicz Universität zu Lübeck




RU: Causality, ML: Causal Learning, RU: Bayesian Networks, RU: Graphical Model


Enumerating the directed acyclic graphs (DAGs) of a Markov equivalence class (MEC) is an important primitive in causal analysis. The central resource from the perspective of computational complexity is the delay, that is, the time an algorithm that lists all members of the class requires between two consecutive outputs. Commonly used algorithms for this task utilize the rules proposed by Meek (1995) or the transformational characterization by Chickering (1995), both resulting in superlinear delay. In this paper, we present the first linear-time delay algorithm. On the theoretical side, we show that our algorithm can be generalized to enumerate DAGs represented by models that incorporate background knowledge, such as MPDAGs; on the practical side, we provide an efficient implementation and evaluate it in a series of experiments. Complementary to the linear-time delay algorithm, we also provide intriguing insights into Markov equivalence itself: All members of an MEC can be enumerated such that two successive DAGs have structural Hamming distance at most three.




How to Cite

Wienöbst, M., Luttermann, M., Bannach, M., & Liskiewicz, M. (2023). Efficient Enumeration of Markov Equivalent DAGs. Proceedings of the AAAI Conference on Artificial Intelligence, 37(10), 12313-12320. https://doi.org/10.1609/aaai.v37i10.26451



AAAI Technical Track on Reasoning Under Uncertainty