aiqbench analysis
This research proposes a stage-wise intervention framework for causal discovery within directed mixed graphs containing cycles and latent confounding. By combining separating systems with specific CI tests and do-see comparisons, the method recovers graph skeletons and bidirected edges where observational data alone fails. The work establishes theoretical bounds on experimental requirements for unrestricted and bounded variable settings, advancing the limits of identifiable causal structures in complex models.
Design of Experiment for Discovering Directed Mixed Graph
arXiv:2509.01887v2 Announce Type: replace-cross 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 $d$- or $\sigma$-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.
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 $d$- or $\sigma$-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.
Machine Learning (stat.ML); Machine Learning (cs.LG)
arXiv:2509.01887 [stat.ML]
(or arXiv:2509.01887v2 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2509.01887 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 307 words
