Lower Bounds on the Size of Markov Equivalence Classes

Erik Jahn, Frederick Eberhardt, Leonard J. Schulman · 2025

Read Lower Bounds on the Size of Markov Equivalence Classes by Erik Jahn, Frederick Eberhardt, Leonard J. Schulman (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-20933.txt.

Introduction

From data alone, causal discovery tools can usually narrow a cause-and-effect graph only to a family of look-alikes, its Markov equivalence class. Erik Jahn, Frederick Eberhardt, and Leonard Schulman ask how big those families must be, in a 2025 paper. Textbook results say the classes stay small on average, but only under a tidy set of assumptions.

Drop any one of those assumptions, and the picture flips. The authors prove exponential lower bounds on expected class size in three looser settings: sparse random acyclic graphs, random mixed graphs that allow hidden common causes, and random graphs with cycles. In plain terms, the range of causal stories that fit the same data can explode once the tidy world is left behind. The bounds mark hard limits on what observation alone can teach about cause.

Catalog record

CREATORErik Jahn, Frederick Eberhardt, Leonard J. Schulman
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-20933

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Lower Bounds on the Size of Markov Equivalence Classes Erik Jahn, Frederick Eberhardt, Leonard J. Schulman 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. 1]Engineering and Applied Science California Institute of Technology Pasadena, California, USA 2]Humanities and Social Sciences California Institute of Technology Pasadena, California, USA 1 Introduction One of the most powerful contributions of the theory of causal graphs [ Pearl 2009 , Spirtes et al. 2001 ] is a complete characterization of which causal relationships can be learned from observational data without conducting experiments. This characterization is given by the concept of Markov equivalence . Two causal models are Markov-equivalent if they encode the same conditional independence constraints. As a result, even a perfect causal discovery algorithm can only recover the true causal structure up to its Markov equivalence class, unless additional identifiable structure is assumed or happens to be present. Remarkably, Markov equivalence classes for directed acyclic graphs (DAGs) have a simple graphical characterization, due to Verma and Pearl 1991 . This is exploited by some of the most widely used causal discovery algorithms today, all of which return a Markov equivalence class as their output [ Spirtes et al. 2001 , Chickering 2003 , Raskutti and Uhler 2018 ] . Consequently, the size of these equivalence classes is a key measure for how informative the output of such algorithms is, making the challenge of counting the number of Markov equivalent graphs a subject of ongoing research [ He et al. 2015 , Radhakrishnan et al. 2017 , Wienöbst et al. 2023 ] . The largest Markov equivalence class of DAGs on n variables has size n! , consisting of all the fully connected DAGs. However, for small graphs, numerical simulations [ Gillispie and Perlman 2001 , Gillispie and Perlman 2002 ] and recursive enumeration [ Steinsky 2003 , Gillispie 2006 , Steinsky 2013 ] have shown that the average number of DAGs per Markov equivalence class is surprisingly small, even less than four. More recently, Schmid and Sly 2024 proved that for arbitrarily large n , the expected size of the Markov equivalence class of a uniformly random DAG on n variables is bounded by a constant. These results crucially rely on the uniformity assumption, effectively placing almost all the weight on dense DAGs. In practice, however, we expect useful real-world causal structures to be sparse. Indeed, many causal discovery algorithms work best under a sparsity assumption [ Kalisch and Bühlmann 2007 , Chickering 2020 ] and sparse priors for learning graphical models have been shown to improve practical performance [ Huang et al. 2013 , Eggeling et al. 2019 ] . Numerous researchers have posed the question of how large Markov-equivalence classes are for sparse graphs [ Chickering 2002 , Talvitie and Koivisto 2019 , Katz et al. 2019 ] . In this paper, we give a first theoretical answer to this question. We show that for a wide range of sparse random DAG distributions, the expected size of the Markov equivalence classes basically scales exponentially in the inverse edge density. In particular, when the expected degree of each vertex is bounded by a constant, the Markov equivalence classes are exponentially large in the number of vertices of the DAG in expectation. This result reveals a sharp contrast to the uniform setting and also has algorithmic implications: Many greedy search algorithms can be run either in the space of DAGs or in the space of equivalence classes, but with small equivalence class sizes the efficiency gain remained unclear [ Chickering 2002 ] . Our results suggest that the efficiency gap becomes larger as the input graphs are sparser. Moreover, we extend our analysis of Markov equivalence classes beyond DAGs. Causal models represented by DAGs inherently make two assumptions: causal sufficiency , meaning that there are no unobserved common causes, and acyclicity , implying the absence of causal feedback loops. Both assumptions may be violated in applications, motivating the study of more general graphical models: acyclic directed mixed graphs (ADMGs), which allow for unmeasured confounders, and directed cyclic graphs (DCGs), which permit cyclic causal relationships. Just as for DAGs, Markov equivalence has been characterized for both models [ Spirtes and Richardson 1997 , Richardson 1997 ] and corresponding causal discovery algorithms that output Markov equivalence classes have been developed [ Spirtes et al. 1999 , Richardson 1996b ] . The characterization of Markov equivalence classes is much more complex in both cases, and little is known about the sizes of these Markov equivalence classes. Here, we establish super-exponential lower bounds for the expected size of Markov equivalence classes of uniformly random ADMGs and DCGs. Our results exploit specific underdetermined substructures, leaving open the possibility that more restrictive model classes, such as maximal ancestral graphs [ Richardson and Spirtes 2002 ] , may exhibit smaller Markov equivalence classes by prohibiting such structures. In general, our results highlight the need to supplement causal discovery with stronger, possibly parametric assumptions, or to perform interventions if one wants to reduce the size of the set of plausible graphs, let alone find a unique causal graph that explains the data. 1.1 Our Results In this section, we provide formal statements of our results. For a parameter p\in[0,1) , consider the following natural sampling process for generating a random DAG on n vertices: • Include each possible directed edge independently with probability p ; • If the graph has any directed cycles, reject and repeat. We denote the distribution arising from this process by D(n,p) (see also Definition 4 for an alternative description). The parameter p directly controls the edge density of the sampled graph, and one can check that D(n,1/2) is equal to the uniform distribution on vertex-labeled DAGs. Heckerman et al. 1995 already used this distribution in the context of Bayesian networks and Eggeling et al. 2019 showed that it has desirable properties as a prior for Bayesian inference over causal structures. While the sampling process described above becomes impractical for large n due to a high rejection probability, a more efficient sampling algorithm for D(n,p) has been given by Talvitie et al. 2020 . We study the sizes of Markov equivalence classes of DAGs sampled from D(n,p) in the regime 6/n\leq p\leq o(1/\log n) . The graphs in this regime have expected vertex degree ranging from constant (whenever p=C/n ) up to o(n/\log n) . It turns out that the number of graphs that are Markov-equivalent to a DAG G sampled from D(n,p) scales at least almost exponentially in the inverse of p . Theorem 1 .

Read the complete text