Design of Experiment for Discovering Directed Mixed Graph

• URL: http://arxiv.org/abs/2509.01887v1
• Date: Tue, 02 Sep 2025 02:24:55 GMT
• Title: Design of Experiment for Discovering Directed Mixed Graph
• Authors: Haijie Xu, Chen Zhang,
• Abstract summary: We study the problem of experimental design for accurately identifying the causal graph structure of a simple structural causal model (SCM)<n>The presence of cycles renders it impossible to recover the graph skeleton using observational data alone.<n>We develop two classes of algorithms, i.e., bounded and unbounded, that can recover all causal edges except for double adjacent bidirected edges.
• Score: 6.3850400710838615
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 $\sigma$ 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.

Related papers

• Distributional Equivalence in Linear Non-Gaussian Latent-Variable Cyclic Causal Models: Characterization and Learning [13.891913455492697]
  We argue that a core obstacle to a general, structural-assumption-free approach is the lack of an equivalence characterization.<n>Key to our approach is a new tool, edge rank constraints, which fills a missing piece in the toolbox for latent-variable causal discovery.
  arXiv  Detail & Related papers  (2026-03-05T03:57:14Z)
• Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought [56.71873693264532]
  We prove that a two-layer transformer with $D$ steps of continuous CoTs can solve the directed graph reachability problem.<n>In our construction, each continuous thought vector is a superposition state that encodes multiple search frontiers simultaneously.
  arXiv  Detail & Related papers  (2025-05-18T18:36:53Z)
• Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
  We consider the linear causal representation learning setting where we observe a linear mixing of $d$ unknown latent factors. Recent work has shown that it is possible to recover the latent factors as well as the underlying structural causal model over them. We provide a surprising identifiability result that it is indeed possible, under some very mild standard assumptions, to identify the set of shifted nodes.
  arXiv  Detail & Related papers  (2024-10-31T15:56:50Z)
• Collaborative non-parametric two-sample testing [55.98760097296213]
  The goal is to identify nodes where the null hypothesis $p_v = q_v$ should be rejected. We propose the non-parametric collaborative two-sample testing (CTST) framework that efficiently leverages the graph structure. Our methodology integrates elements from f-divergence estimation, Kernel Methods, and Multitask Learning.
  arXiv  Detail & Related papers  (2024-02-08T14:43:56Z)
• Learning Causal Graphs via Monotone Triangular Transport Maps [1.6752182911522522]
  We study the problem of causal structure learning from data using optimal transport (OT) We provide an algorithm for causal discovery up to Markov Equivalence with no assumptions on the structural equations/noise distributions. We provide experimental results to compare the proposed approach with the state of the art on both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-05-26T13:24:17Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Score-based Causal Representation Learning with Interventions [54.735484409244386]
  This paper studies the causal representation learning problem when latent causal variables are observed indirectly. The objectives are: (i) recovering the unknown linear transformation (up to scaling) and (ii) determining the directed acyclic graph (DAG) underlying the latent variables.
  arXiv  Detail & Related papers  (2023-01-19T18:39:48Z)
• A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models [32.88438123861557]
  We study experiment design for unique identification of the causal graph of a simple SCM, where the graph may contain cycles. We propose an experiment design approach that can learn both cyclic and acyclic graphs. We show that our approach is optimal in terms of the size of the largest experiment required for uniquely identifying the causal graph in the worst case.
  arXiv  Detail & Related papers  (2022-05-20T10:58:41Z)
• Identification in Tree-shaped Linear Structural Causal Models [4.751074059099236]
  We investigate models, whose directed component forms a tree, and show that missing cycles of bidirected edges can be used to identify the model. We show how multiple missing cycles can be combined to obtain a unique solution.
  arXiv  Detail & Related papers  (2022-03-03T16:59:49Z)
• BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery [97.79015388276483]
  A structural equation model (SEM) is an effective framework to reason over causal relationships represented via a directed acyclic graph (DAG) Recent advances enabled effective maximum-likelihood point estimation of DAGs from observational data. We propose BCD Nets, a variational framework for estimating a distribution over DAGs characterizing a linear-Gaussian SEM.
  arXiv  Detail & Related papers  (2021-12-06T03:35:21Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• Testing correlation of unlabeled random graphs [18.08210501570919]
  We study the problem of detecting the edge correlation between two random graphs with $n$ unlabeled nodes. This is formalized as a hypothesis testing problem, where under the null hypothesis, the two graphs are independently generated. Under the alternative, the two graphs are edge-correlated under some latent node correspondence, but have the same marginal distributions as the null.
  arXiv  Detail & Related papers  (2020-08-23T19:19:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.