Abstract
Learning the structure of causal Directed Acyclic Graphs (DAGs) from observational data is limited by Markov equivalence; observational data can only identify a graph up to its Markov Equivalence Class (MEC). To fully orient the remaining undirected edges, costly interventions are required. This paper presents a new universal lower bound on the number of single-node (atomic) interventions needed by any algorithm to orient an MEC. We prove this bound is within a factor of two of the optimal intervention set size. Our approach utilizes a novel combinatorial tool called Clique-Block Shared-Parents (CBSP) orderings for chordal graphs. Empirical results demonstrate that our bound significantly improves upon previous benchmarks and is often near-optimal in practice.
Introduction: The Challenge of Causal Structure Learning
In causal inference, Directed Acyclic Graphs (DAGs) are the standard language for representing causal relationships. A fundamental problem is structure learning: identifying the DAG from data. Observational data typically only identifies the DAG up to its Markov Equivalence Class (MEC), which consists of all DAGs sharing the same skeleton and v-structures (e.g., $A \to C \leftarrow B$). The edges that are not part of a v-structure remain undirected in the MEC representation, often referred to as the Essential Graph.
To resolve these ambiguities, researchers perform interventions—controlled experiments where a variable is fixed to a specific value, breaking its natural causal dependencies. Because interventions are often expensive, ethically constrained, or time-consuming, minimizing the number of interventions required to fully orient an MEC is a critical research objective. This paper focuses on establishing a "universal lower bound": a minimum number of interventions that any algorithm, whether active or passive, must perform to guarantee the identification of any ground-truth DAG within a given MEC.
Methods: CBSP Orderings and Chordal Graphs
The authors depart from previous approaches that relied on complex directed clique tree structures. Instead, they leverage the properties of chordal graphs and introduce a new combinatorial framework based on the theory of topological orderings.
The core of their proof relies on the concept of Clique-Block Shared-Parents (CBSP) orderings. For a DAG without v-structures (which corresponds to a chordal graph), a CBSP ordering is a topological ordering that satisfies specific structural constraints. The nodes are partitioned into "clique blocks" based on the maximal cliques of the graph's skeleton. Within these blocks, consecutive nodes must share the same set of parents.
By establishing that a CBSP ordering always exists for any DAG without v-structures, the authors can precisely count the interventions necessary to distinguish between different orientations within these cliques. This logic is then extended to general DAGs by decomposing the MEC into its chordal chain components and applying the bound to each component individually.
Key Results and Insights
The primary contribution is a lower bound approximately equal to $\lceil (n-r)/2 \rceil$, where $n$ is the number of nodes and $r$ is the number of maximal cliques in the chordal components.
- Superiority over Existing Bounds: The authors prove that their bound is strictly better than or equal to the previous state-of-the-art (Squires et al., 2020). In certain graph families, such as block graphs with large cliques, the improvement is substantial—specifically, a factor of $\Theta(\omega)$, where $\omega$ is the size of the largest clique.
- Factor-of-Two Tightness: A major theoretical milestone is the proof that this lower bound is within a factor of two of the absolute minimum. Specifically, they show that for any DAG, there exists a set of at most $n-r$ interventions that fully orients it. This provides a tight "envelope" for the complexity of the intervention problem.
- Empirical Performance: Using synthetic datasets generated via Erdős-Rényi models (with $n=5$ to $25$), the authors compared their bound against the true optimal intervention set size. The simulations showed that the bound is remarkably tight in practice, often matching the true optimum exactly.
- Multi-node Extensions: The techniques developed for atomic interventions were successfully adapted to the multi-node setting, where a single intervention can target a set of variables simultaneously.
Conclusion
This work provides a fundamental theoretical limit on the cost of causal discovery. By introducing CBSP orderings, the authors simplified the analysis of intervention sets while providing a tighter and more universal bound than previously possible. While the study assumes causal sufficiency (no hidden confounders), it sets a new benchmark for algorithm design in experimental causal discovery. Future work may focus on developing efficient algorithms to find the absolute minimum intervention set, closing the remaining factor-of-two gap.
Summary updated