mlsanityData to 14 Oct 2026

Design of Experiment for Discovering Directed Mixed Graph

arXiv 2509.01887 ↗First posted 2 Sep 2025stat.ML cs.LGcited by 0

Not on the map. Why?

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.

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

20 of 48 references.

References · 20

  1. 2013Causal Inference in the Presence of Latent Variables and Selection Biascited by 166
  2. 2016Foundations of Structural Causal Models with Cycles and Latent Variablescited by 134
  3. 2015Learning Causal Graphs with Small Interventionscited by 63
  4. 2019ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discoverycited by 52
  5. 2022Interventions, Where and How? Experimental Design for Causal Models at Scalecited by 49
  6. 2017Cost-Optimal Learning of Causal Graphscited by 44
  7. 2017Budgeted Experiment Design for Causal Structure Learningcited by 38
  8. 2020Active Structure Learning of Causal DAGs via Directed Clique Treecited by 38
  9. 2020Constraint-Based Causal Discovery using Partial Ancestral Graphs in the presence of Cyclescited by 31
  10. 2020Efficient Intervention Design for Causal Discovery with Latentscited by 22
  11. 2020A Recursive Markov Boundary-Based Approach to Causal Structure Learningcited by 21
  12. 2022Verification and search algorithms for causal DAGscited by 18
8 more
  1. 2020Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGscited by 14
  2. 2023Subset verification and search algorithms for causal DAGscited by 12
  3. 2020LazyIter: A Fast Algorithm for Counting Markov Equivalent DAGs and Designing Experimentscited by 9
  4. 2022Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applicationscited by 9
  5. 2018Counting and Sampling from Markov Equivalent DAGs Using Clique Treescited by 8
  6. 2022A Unified Experiment Design Approach for Cyclic and Acyclic Causal Modelscited by 7
  7. 2023Adaptivity Complexity for Causal Graph Discoverycited by 7
  8. 2023Establishing Markov Equivalence in Cyclic Directed Graphscited by 6

Built on by

Not cited yet.