在含环与混杂的因果图中，设计高效实验以准确识别因果结构。
Design of Experiment for Discovering Directed Mixed Graph
- 结合条件独立与干预观测测试，区分因果方向与混杂关系。
- 证明单次实验最多可干预变量数及总实验次数的理论下界。
- 算法可恢复除双邻接混杂边外的所有因果边，逼近最优效率。
我们研究简单结构性因果模型（SCM）中因果图结构的实验设计问题，其底层图可能包含循环和由潜在混杂引起的双向边。循环的存在使得仅凭观测数据无法恢复图骨架，而混杂可能在某些情况下使传统条件独立（CI）检验失效。为应对这些挑战，我们建立了单次实验最多可干预变量数及总实验次数的理论下界。利用条件独立测试与干预观测测试，并结合d-分离与σ-分离，我们提出了两类算法——有界与无界算法，能够恢复所有有向边及非相邻双向边，但无法识别双邻接双向边。进一步证明，所提算法在对数因子范围内紧致于所推导的下界。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。