Counting Markov Equivalence Classes by Number of Immoralities

Adityanarayanan Radhakrishnan, Liam Solus, Caroline Uhler
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:231-240, 2017.

Abstract

Two directed acyclic graphs (DAGs) are called Markov equivalent if and only if they have the same underlying undirected graph (i.e. skeleton) and the same set of immoralities. When using observational data alone and typical identifiability assumptions, such as faithfulness, a DAG model can only be determined up to Markov equivalence. Therefore, it is desirable to understand the size and number of Markov equivalence classes (MECs) combinatorially. In this paper, we address this enumerative question using a pair of generating functions that encode the number and size of MECs on a skeleton G, and in doing so we connect this problem to classical problems in combinatorial optimization. The first generating function is a graph polynomial that counts the number of MECs on G by their number of immoralities. Using connections to the independent set problem, we show that computing a DAG on G with the maximum possible number of immoralities is NP-hard. The second generating function counts the MECs on G according to their size. Via computer enumeration, we show that this generating function is distinct for every connected graph on p nodes for all p $\leq$10.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-radhakrishnan17a, title = {Counting {M}arkov Equivalence Classes by Number of Immoralities}, author = {Radhakrishnan, Adityanarayanan and Solus, Liam and Uhler, Caroline}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {231--240}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/radhakrishnan17a/radhakrishnan17a.pdf}, url = {https://proceedings.mlr.press/r15/radhakrishnan17a.html}, abstract = {Two directed acyclic graphs (DAGs) are called Markov equivalent if and only if they have the same underlying undirected graph (i.e. skeleton) and the same set of immoralities. When using observational data alone and typical identifiability assumptions, such as faithfulness, a DAG model can only be determined up to Markov equivalence. Therefore, it is desirable to understand the size and number of Markov equivalence classes (MECs) combinatorially. In this paper, we address this enumerative question using a pair of generating functions that encode the number and size of MECs on a skeleton G, and in doing so we connect this problem to classical problems in combinatorial optimization. The first generating function is a graph polynomial that counts the number of MECs on G by their number of immoralities. Using connections to the independent set problem, we show that computing a DAG on G with the maximum possible number of immoralities is NP-hard. The second generating function counts the MECs on G according to their size. Via computer enumeration, we show that this generating function is distinct for every connected graph on p nodes for all p $\leq$10.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Counting Markov Equivalence Classes by Number of Immoralities %A Adityanarayanan Radhakrishnan %A Liam Solus %A Caroline Uhler %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-radhakrishnan17a %I PMLR %P 231--240 %U https://proceedings.mlr.press/r15/radhakrishnan17a.html %V R15 %X Two directed acyclic graphs (DAGs) are called Markov equivalent if and only if they have the same underlying undirected graph (i.e. skeleton) and the same set of immoralities. When using observational data alone and typical identifiability assumptions, such as faithfulness, a DAG model can only be determined up to Markov equivalence. Therefore, it is desirable to understand the size and number of Markov equivalence classes (MECs) combinatorially. In this paper, we address this enumerative question using a pair of generating functions that encode the number and size of MECs on a skeleton G, and in doing so we connect this problem to classical problems in combinatorial optimization. The first generating function is a graph polynomial that counts the number of MECs on G by their number of immoralities. Using connections to the independent set problem, we show that computing a DAG on G with the maximum possible number of immoralities is NP-hard. The second generating function counts the MECs on G according to their size. Via computer enumeration, we show that this generating function is distinct for every connected graph on p nodes for all p $\leq$10. %Z Reissued by PMLR on 04 October 2026.
APA
Radhakrishnan, A., Solus, L. & Uhler, C.. (2017). Counting Markov Equivalence Classes by Number of Immoralities. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:231-240 Available from https://proceedings.mlr.press/r15/radhakrishnan17a.html. Reissued by PMLR on 04 October 2026.

Related Material