Design of Experiment for Discovering Directed Mixed Graph

2025/09/02 by Haijie Xu, Chen Zhang, Xu, Haijie +1
Computer Science · Mathematics · #Advanced Causal Inference Techniques #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.2509.01887

openalex publication_date 2025/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the problem of experimental design for accurately identifying the causal graph structure of a simple structural causal model (SCM), where the underlying graph may include both cycles and bidirected edges induced by latent confounders. The presence of cycles renders it impossible to recover the graph skeleton using observational data alone, while confounding can further invalidate traditional conditional independence (CI) tests in certain scenarios. To address these challenges, we establish lower bounds on both the maximum number of variables that can be intervened upon in a single experiment and the total number of experiments required to identify all directed edges and non-adjacent bidirected edges. Leveraging both CI tests and do see tests, and accounting for d separation and σ separation, we develop two classes of algorithms, i.e., bounded and unbounded, that can recover all causal edges except for double adjacent bidirected edges. We further show that, up to logarithmic factors, the proposed algorithms are tight with respect to the derived lower bounds.

Citations

• Adaptivity Complexity for Causal Graph Discovery
• Causal Structure Learning in Directed, Possibly Cyclic, Graphical Models
• Subset verification and search algorithms for causal DAGs
• Verification and search algorithms for causal DAGs
• A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models
• Interventions, Where and How? Experimental Design for Causal Models at Scale
• Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs
• Active Structure Learning of Causal DAGs via Directed Clique Tree
• A Recursive Markov Boundary-Based Approach to Causal Structure Learning
• LazyIter: A Fast Algorithm for Counting Markov Equivalent DAGs and Designing Experiments
• Efficient Intervention Design for Causal Discovery with Latents
• ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery
• Counting and Sampling from Markov Equivalent DAGs Using Clique Trees
• Cost-Optimal Learning of Causal Graphs
• Learning Causal Graphs with Small Interventions
• On the Identifiability of the Post-Nonlinear Causal Model
• Discovering Cyclic Causal Models by Independent Components Analysis
• On the Number of Experiments Sufficient and in the Worst Case Necessary to Identify All Causal Relations Among N Variables
• Causal Inference in the Presence of Latent Variables and Selection Bias

Related

• A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models
• Mixed Graphical Models for Causal Analysis of Multi-modal Variables
• Causal Discovery with Fewer Conditional Independence Tests
• A Single Iterative Step for Anytime Causal Discovery
• Distinguishability of causal structures under latent confounding and selection