# Design of Experiment for Discovering Directed Mixed Graph

arXiv: https://arxiv.org/abs/2509.01887 · HTML: https://mlsanity.com/paper/2509.01887/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 48 references that are in the map.
- First posted on arXiv 2 Sep 2025.

## Builds on (most cited first, 20 of 20)

- [Causal Inference in the Presence of Latent Variables and Selection Bias](https://mlsanity.com/paper/1302.4983/) (2013)
- [Foundations of Structural Causal Models with Cycles and Latent Variables](https://mlsanity.com/paper/1611.06221/) (2016)
- [Learning Causal Graphs with Small Interventions](https://mlsanity.com/paper/1511.00041/) (2015)
- [ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery](https://mlsanity.com/paper/1902.10347/) (2019)
- [Interventions, Where and How? Experimental Design for Causal Models at Scale](https://mlsanity.com/paper/2203.02016/) (2022)
- [Cost-Optimal Learning of Causal Graphs](https://mlsanity.com/paper/1703.02645/) (2017)
- [Budgeted Experiment Design for Causal Structure Learning](https://mlsanity.com/paper/1709.03625/) (2017)
- [Active Structure Learning of Causal DAGs via Directed Clique Tree](https://mlsanity.com/paper/2011.00641/) (2020)
- [Constraint-Based Causal Discovery using Partial Ancestral Graphs in the presence of Cycles](https://mlsanity.com/paper/2005.00610/) (2020)
- [Efficient Intervention Design for Causal Discovery with Latents](https://mlsanity.com/paper/2005.11736/) (2020)
- [A Recursive Markov Boundary-Based Approach to Causal Structure Learning](https://mlsanity.com/paper/2010.04992/) (2020)
- [Verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2206.15374/) (2022)
- [Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs](https://mlsanity.com/paper/2012.09679/) (2020)
- [Subset verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2301.03180/) (2023)
- [LazyIter: A Fast Algorithm for Counting Markov Equivalent DAGs and Designing Experiments](https://mlsanity.com/paper/2006.09670/) (2020)
- [Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications](https://mlsanity.com/paper/2205.02654/) (2022)
- [Counting and Sampling from Markov Equivalent DAGs Using Clique Trees](https://mlsanity.com/paper/1802.01239/) (2018)
- [A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models](https://mlsanity.com/paper/2205.10083/) (2022)
- [Adaptivity Complexity for Causal Graph Discovery](https://mlsanity.com/paper/2306.05781/) (2023)
- [Establishing Markov Equivalence in Cyclic Directed Graphs](https://mlsanity.com/paper/2309.03092/) (2023)

## Abstract (arXiv)

We study the design of interventions for causal discovery in simple structural causal models whose causal graphs are directed mixed graphs (DMGs) that may contain directed cycles and bidirected edges representing latent confounding. In such case, observational conditional-independence (CI) information may not identify even the graph skeleton, while CI alone cannot generally detect a bidirected edge coexisting with a directed edge. To this end, we propose a stage-wise framework based on tailored separating systems. Separating-system interventions first recover descendant relations and strongly connected components (SCCs). The SCCs are then ordered by ancestry, and an SCC-Anc separating system recovers the directed subgraph. Given this subgraph, further systems use CI tests interpreted through d- or σ-separation to recover non-adjacent bidirected edges, whose endpoints share no directed edge, and do-see comparisons to recover those coexisting with exactly one directed edge. Under our assumptions, the framework recovers the directed subgraph and every bidirected edge except double-adjacent ones, whose endpoints are connected by a directed edge in each direction. We develop algorithms for unrestricted and M-bounded settings, with each experiment targeting at most M variables in the latter. For recovering the directed subgraph and non-adjacent bidirected edges, our upper bounds on the number and maximum size of experiments match corresponding worst-case lower bounds up to logarithmic factors.