Abstract
A well-studied challenge that arises in the structure learning problem of causal directed acyclic graphs (DAG) is that using observational data, one can only learn the graph up to a "Markov equivalence class" (MEC). The remaining undirected edges have to be oriented using interventions, which can be very expensive to perform in applications. Thus, the problem of minimizing the number of interventions needed to fully orient the MEC has received a lot of recent attention, and is also the focus of this work. We prove two main results. The first is a new universal lower bound on the number of atomic interventions that any algorithm (whether active or passive) would need to perform in order to orient a given MEC. Our second result shows that this bound is, in fact, within a factor of two of the size of the smallest set of atomic interventions that can orient the MEC. Our lower bound is provably better than previously known lower bounds. The proof of our lower bound is based on the new notion of clique-block shared-parents (CBSP) orderings, which are topological orderings of DAGs without v-structures and satisfy certain special properties. Further, using simulations on synthetic graphs and by giving examples of special graph families, we show that our bound is often significantly better.
Introduction
In causal discovery, researchers aim to move from mere correlation to understanding cause-and-effect. Using only observational data, we can usually only narrow down the true causal structure to a Markov Equivalence Class (MEC)—a set of graphs that look identical statistically but differ in the direction of some edges. To "orient" these remaining undirected edges, we must perform interventions (like randomized controlled trials). However, interventions are often expensive, time-consuming, or unethical. This paper focuses on atomic interventions (targeting a single variable at a time) and asks: What is the absolute minimum number of interventions any algorithm needs to fully resolve an MEC into a single DAG?
Specifically, the authors seek a universal lower bound: a value $L$ such that for any set of interventions smaller than $L$, there is at least one "ground truth" DAG in the MEC that will remain unresolved.
Methodology: CBSP Orderings
The authors move away from the complex "directed clique tree" machinery used in prior work. Instead, they introduce a new combinatorial tool called Clique-Block Shared-Parents (CBSP) orderings. These are special topological orderings of DAGs without v-structures (unshielded colliders).
CBSP orderings satisfy two key properties:
- Clique Block Property: Nodes are grouped into blocks that form cliques in the graph's skeleton.
- Shared Parents Property: Consecutive nodes in the ordering within the same block must share the same parents.
The proof relies on the properties of chordal graphs. Since any MEC can be decomposed into chordal chain components, the problem reduces to orienting these components. The authors prove their bound is "almost optimal" by showing that for any DAG, there exists an intervention set no larger than twice their lower bound that fully orients the MEC.
Key Insights and Results
The core of the new bound is based on $n$ (number of nodes) and $r$ (number of distinct maximal cliques). Their lower bound is $\lceil \frac{n-r}{2} \rceil$.
- Surpassing Previous Bounds: Previous state-of-the-art bounds were based on the size of the largest clique ($\omega$). This paper proves that their $(n-r)/2$ bound is always as good as or better than the $\omega/2$ bound, especially in graphs with many small, interconnected cliques.
- Factor of Two Optimality: Being within a factor of two of the "true" minimum is a significant achievement, providing a near-perfect target for algorithm designers.
- Empirical Performance: In simulations, the new bound was sometimes five times higher (and thus tighter) than previous benchmarks. For many random chordal DAGs, the lower bound was even closer to the true optimal intervention size than the theoretical "factor of 2" would suggest.
Conclusion
This work establishes a tighter universal lower bound for causal structure learning with atomic interventions. By shifting the perspective to topological orderings (CBSP), the authors simplified the proof process while achieving a more robust result. Future work remains in extending these results to non-atomic interventions, settings with latent confounders, and the development of specific active learning algorithms that achieve these bounds.
Summary updated