stat.MLSep 2, 2025

Design of Experiment for Discovering Directed Mixed Graph

Authors: Haijie Xu, Chen Zhang

Organizations: Department of Industrial Engineering Tsinghua University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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 dd- 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 MM-bounded settings, with each experiment targeting at most MM 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.

Figures & tables

Edge classResult typeMax experiment sizeNumber of experiments
Directed edgesUnbounded alg.n−1n-1Corollary 55
Bounded alg.MM in Remark 71Corollary 77
Lower boundTheorem 20Theorem 22
Non-adjacentUnbounded alg.n−1n-1Propositions 57 and 59
bidirected edgesBounded alg.MM in Remark 71Theorem 78
Lower boundTheorem 26Theorem 32
Table 1 : Main contributions of this paper. It provides the lower bound and the upper bound of the bounded or unbounded algorithm of the maximum size experiment and number of experiments for discovering each part of the DMG G\mathcal{G} . Here nn is the number of nodes in G\mathcal{G} , MM is a certain upper bound of experiment size in Remark 71 and RD(G)\mathcal{RD}(\mathcal{G}) is the G\mathcal{G} without the double adjacent bidirected edges which is defined in Section 3.5 . Since the CI test fails when identifying adjacent bidirected edges, the lower bound is not well-defined in this case and thus is not discussed further.
Figure 1 : DMG of Example 8 .
Figure 2 : Examples of DMG G\mathcal{G} and the corresponding RB(G)\mathcal{RB}(\mathcal{G}) , RA(G)\mathcal{RA}(\mathcal{G}) , RD(G)\mathcal{RD}(\mathcal{G}) .
Figure 3 : DMG of Examples 19 and 52 .
Figure 4 : Examples of DMG G\mathcal{G} and its corresponding Guc\mathcal{G}^{uc} , Gu\mathcal{G}^{u} . In (b), different colors denote different cliques in the edge clique covering. Since a node may belong to multiple cliques, it can be assigned multiple colors. In (c), different colors denote different colors of edges in the strong edge coloring.
Figure 5 : DMGs of Examples 39 and 45 . In (c), different colors denote different colors of nodes in the vertex coloring.

Explore similar work

CardsList
May 26, 2026stat.ML

Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the 1+K1+K Lower Bound

Causal-discovery algorithms return a directed graph, yet provide no principled means of distinguishing edge directions identified by the data from those assigned without an identifying assumption. Under the standard Markov and faithfulness conditions, the observational distribution identifies only a Markov equivalence class; orientations within that class are not determined by the joint distribution and cannot be recovered from additional samples alone, but require either a functional restriction or an intervention. We introduce a protocol for observational causal discovery on continuous data that attaches to each candidate edge a discrete impossibility certificate: a RESOLVED code records the identifiability theorem under which the direction was committed, while an IMPOSSIBLE code records the failure mode together with the specific question a domain expert must answer to resolve it. The bivariate cascade is extended with five gated identifiability tiers LSNM, IGCI, Stein, MDL, and PEIT that abstain when their precondition test rejects. Two oracle primitives, the meta-hub query and the node-children query, jointly establish an upper bound of 1+K1+K expert interactions sufficient to recover any DAG, where KK denotes the number of non-leaf vertices. Under an ideal-oracle assumption, the bound is met exactly on the asia, sachs, child, and alarm benchmarks.

Eichi Uehara

aflo, Inc., Tokyo, Japan

Causal Discovery MethodsIdentifiabilityFinite-Sample CertificatesImpossibilityOraclesLower Bounds+2
AskPDF
Sep 16, 2026cs.LG

Provable Guarantees and Efficient Learning of Structural Equation Models with Latent Confounders

Causal discovery aims to recover causal relationships from observed data. In various fields, exploring causal relationships among variables remains an important topic, but this task becomes challenging due to the existence of latent confounders. Ignoring such confounders can lead to false associations and incorrect edge directions. In this paper, we study the linear structural equation model with latent confounders. We propose an algorithm that iteratively identifies terminal (observed) nodes and reconstructs the directed acyclic graph of the observed variables. To do this, we recover the precision matrix of the observed variables as a sparse plus low-rank matrix: a sparse matrix captures the conditional dependencies among observed variables, while a low-rank matrix captures the combined influence of a few latent confounders. We establish that for pp observed variables, rr latent confounders and ss edges, our procedure correctly identifies the directed causal relationship among observed variables, for n≳max⁡{slog⁡p, rp}n \gtrsim \max\{s\log p,\ r p\} samples. Experimental results validate our theoretical contributions.

Weijian Yu, Jean Honorio

CIS, The University of Melbourne

Linear Structural Equation ModelsLatent ConfoundersCausalProvable Guarantees
AskPDF
Jul 13, 2026cs.LG

Relaxing Faithfulness with Intervention-Only Causal Discovery

Causal discovery algorithms learn a network that describes the causal dependencies among random variables. A common workflow involves first utilizing conditional independence properties on observational data to determine partially directed causal relationships, then applying interventions to orient the unknown causal directions. A critical assumption for the first step is faithfulness: a requirement that causally linked variables exhibit statistical dependence. Many natural systems include buffering and stabilizing pathways that cancel out to achieve systemic robustness. This cancellation of pathways violates faithfulness, leading causal discovery algorithms to incorrectly remove causal dependencies. In this paper, we argue that hard interventions contain information about the presence/absence of causal linkage that is overlooked in the first stage of structure discovery. We show that a mild assumption -- called intervention-immediacy faithfulness -- that allows cancellations, is sufficient to nonparametrically identify causal structures with hard interventions. These results position interventions as the primary carriers of information about causal structure, which should take precedence over conditional independence testing. To flip the paradigm, we also specify equivalence classes when the identification criteria are not met due to limitations in the scope of interventions.

Bijan Mazaheri, Jiaqi Zhang, Caroline Uhler

Thayer School of Engineering, Dartmouth College, Hanover, New Hampshire, USA · Schmidt Center, Broad Institute of MIT and Harvard, Cambridge, Massachusetts, USA · Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA

Causal Discovery MethodsConditional Independence
AskPDF