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. skele- ton) and the same set of immoralities. When using observational data alone and typical identifiability assumptions, such as faithful- ness, a DAG model can only be determined up to Markov equivalence. Therefore, it is de- sirable to understand the size and number of Markov equivalence classes (MECs) combina- torially. In this paper, we address this enu- merative 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 generat- ing function is a graph polynomial that counts the number of MECs on G by their number of immoralities. Using connections to the inde- pendent set problem, we show that computing a DAG on G with the maximum possible num- ber of immoralities is NP-hard. The second generating function counts the MECs on G ac- cording to their size. Via computer enumera- tion, 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. skele- ton) and the same set of immoralities. When using observational data alone and typical identifiability assumptions, such as faithful- ness, a DAG model can only be determined up to Markov equivalence. Therefore, it is de- sirable to understand the size and number of Markov equivalence classes (MECs) combina- torially. In this paper, we address this enu- merative 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 generat- ing function is a graph polynomial that counts the number of MECs on G by their number of immoralities. Using connections to the inde- pendent set problem, we show that computing a DAG on G with the maximum possible num- ber of immoralities is NP-hard. The second generating function counts the MECs on G ac- cording to their size. Via computer enumera- tion, 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. skele- ton) and the same set of immoralities. When using observational data alone and typical identifiability assumptions, such as faithful- ness, a DAG model can only be determined up to Markov equivalence. Therefore, it is de- sirable to understand the size and number of Markov equivalence classes (MECs) combina- torially. In this paper, we address this enu- merative 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 generat- ing function is a graph polynomial that counts the number of MECs on G by their number of immoralities. Using connections to the inde- pendent set problem, we show that computing a DAG on G with the maximum possible num- ber of immoralities is NP-hard. The second generating function counts the MECs on G ac- cording to their size. Via computer enumera- tion, 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