Lower Bounds on the Size of Markov Equivalence Classes

Erik L Jahn, Frederick Eberhardt, Leonard Schulman
Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, PMLR 286:1819-1836, 2025.

Abstract

Causal discovery algorithms typically recover causal graphs only up to their Markov equivalence classes unless additional parametric assumptions are made. The sizes of these equivalence classes reflect the limits of what can be learned about the underlying causal graph from purely observational data. Under the assumptions of acyclicity, causal sufficiency, and a uniform model prior, Markov equivalence classes are known to be small on average. In this paper, we show that this is no longer the case when any of these assumptions is relaxed. Specifically, we prove exponentially large lower bounds for the expected size of Markov equivalence classes in three settings: sparse random directed acyclic graphs, uniformly random acyclic directed mixed graphs, and uniformly random directed cyclic graphs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v286-jahn25a, title = {Lower Bounds on the Size of Markov Equivalence Classes}, author = {Jahn, Erik L and Eberhardt, Frederick and Schulman, Leonard}, booktitle = {Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence}, pages = {1819--1836}, year = {2025}, editor = {Chiappa, Silvia and Magliacane, Sara}, volume = {286}, series = {Proceedings of Machine Learning Research}, month = {21--25 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v286/main/assets/jahn25a/jahn25a.pdf}, url = {https://proceedings.mlr.press/v286/jahn25a.html}, abstract = {Causal discovery algorithms typically recover causal graphs only up to their Markov equivalence classes unless additional parametric assumptions are made. The sizes of these equivalence classes reflect the limits of what can be learned about the underlying causal graph from purely observational data. Under the assumptions of acyclicity, causal sufficiency, and a uniform model prior, Markov equivalence classes are known to be small on average. In this paper, we show that this is no longer the case when any of these assumptions is relaxed. Specifically, we prove exponentially large lower bounds for the expected size of Markov equivalence classes in three settings: sparse random directed acyclic graphs, uniformly random acyclic directed mixed graphs, and uniformly random directed cyclic graphs.} }
Endnote
%0 Conference Paper %T Lower Bounds on the Size of Markov Equivalence Classes %A Erik L Jahn %A Frederick Eberhardt %A Leonard Schulman %B Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2025 %E Silvia Chiappa %E Sara Magliacane %F pmlr-v286-jahn25a %I PMLR %P 1819--1836 %U https://proceedings.mlr.press/v286/jahn25a.html %V 286 %X Causal discovery algorithms typically recover causal graphs only up to their Markov equivalence classes unless additional parametric assumptions are made. The sizes of these equivalence classes reflect the limits of what can be learned about the underlying causal graph from purely observational data. Under the assumptions of acyclicity, causal sufficiency, and a uniform model prior, Markov equivalence classes are known to be small on average. In this paper, we show that this is no longer the case when any of these assumptions is relaxed. Specifically, we prove exponentially large lower bounds for the expected size of Markov equivalence classes in three settings: sparse random directed acyclic graphs, uniformly random acyclic directed mixed graphs, and uniformly random directed cyclic graphs.
APA
Jahn, E.L., Eberhardt, F. & Schulman, L.. (2025). Lower Bounds on the Size of Markov Equivalence Classes. Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 286:1819-1836 Available from https://proceedings.mlr.press/v286/jahn25a.html.

Related Material