A Unified Experiment Design Approach for Cyclic and Acyclic Causal
Models
- URL: http://arxiv.org/abs/2205.10083v3
- Date: Wed, 13 Dec 2023 23:46:06 GMT
- Title: A Unified Experiment Design Approach for Cyclic and Acyclic Causal
Models
- Authors: Ehsan Mokhtarian, Saber Salehkaleybar, AmirEmad Ghassami, Negar
Kiyavash
- Abstract summary: 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.
- Score: 32.88438123861557
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study experiment design for unique identification of the causal graph of a
simple SCM, where the graph may contain cycles. The presence of cycles in the
structure introduces major challenges for experiment design as, unlike acyclic
graphs, learning the skeleton of causal graphs with cycles may not be possible
from merely the observational distribution. Furthermore, intervening on a
variable in such graphs does not necessarily lead to orienting all the edges
incident to it. In this paper, we propose an experiment design approach that
can learn both cyclic and acyclic graphs and hence, unifies the task of
experiment design for both types of graphs. We provide a lower bound on the
number of experiments required to guarantee the unique identification of the
causal graph in the worst case, showing that the proposed approach is
order-optimal in terms of the number of experiments up to an additive
logarithmic term. Moreover, we extend our result to the setting where the size
of each experiment is bounded by a constant. For this case, 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.
Related papers
- Scalable Variational Causal Discovery Unconstrained by Acyclicity [6.954510776782872]
We propose a scalable Bayesian approach to learn the posterior distribution over causal graphs given observational data.
We introduce a novel differentiable DAG sampling method that can generate a valid acyclic causal graph.
We are able to model the posterior distribution over causal graphs using a simple variational distribution over a continuous domain.
arXiv Detail & Related papers (2024-07-06T07:56:23Z) - Graph Generation via Spectral Diffusion [51.60814773299899]
We present GRASP, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process.
Specifically, we propose to use a denoising model to sample eigenvectors and eigenvalues from which we can reconstruct the graph Laplacian and adjacency matrix.
Our permutation invariant model can also handle node features by concatenating them to the eigenvectors of each node.
arXiv Detail & Related papers (2024-02-29T09:26:46Z) - Differentiable Bayesian Structure Learning with Acyclicity Assurance [7.568978862189266]
We propose an alternative approach for strictly constraining the acyclicty of the graphs with an integration of the knowledge from the topological orderings.
Our approach can reduce inference complexity while ensuring the structures of the generated graphs to be acyclic.
arXiv Detail & Related papers (2023-09-04T06:44:46Z) - Spectral Augmentations for Graph Contrastive Learning [50.149996923976836]
Contrastive learning has emerged as a premier method for learning representations with or without supervision.
Recent studies have shown its utility in graph representation learning for pre-training.
We propose a set of well-motivated graph transformation operations to provide a bank of candidates when constructing augmentations for a graph contrastive objective.
arXiv Detail & Related papers (2023-02-06T16:26:29Z) - CLEAR: Generative Counterfactual Explanations on Graphs [60.30009215290265]
We study the problem of counterfactual explanation generation on graphs.
A few studies have explored counterfactual explanations on graphs, but many challenges of this problem are still not well-addressed.
We propose a novel framework CLEAR which aims to generate counterfactual explanations on graphs for graph-level prediction models.
arXiv Detail & Related papers (2022-10-16T04:35:32Z) - Typing assumptions improve identification in causal discovery [123.06886784834471]
Causal discovery from observational data is a challenging task to which an exact solution cannot always be identified.
We propose a new set of assumptions that constrain possible causal relationships based on the nature of the variables.
arXiv Detail & Related papers (2021-07-22T14:23:08Z) - Efficient Neural Causal Discovery without Acyclicity Constraints [30.08586535981525]
We present ENCO, an efficient structure learning method for directed, acyclic causal graphs.
In experiments, we show that ENCO can efficiently recover graphs with hundreds of nodes, an order of magnitude larger than what was previously possible.
arXiv Detail & Related papers (2021-07-22T07:01:41Z) - Deconfounded Score Method: Scoring DAGs with Dense Unobserved
Confounding [101.35070661471124]
We show that unobserved confounding leaves a characteristic footprint in the observed data distribution that allows for disentangling spurious and causal effects.
We propose an adjusted score-based causal discovery algorithm that may be implemented with general-purpose solvers and scales to high-dimensional problems.
arXiv Detail & Related papers (2021-03-28T11:07:59Z) - Structure Learning for Cyclic Linear Causal Models [5.567377163246147]
We consider the problem of structure learning for linear causal models based on observational data.
We treat models given by possibly cyclic mixed graphs, which allow for feedback loops and effects of latent confounders.
arXiv Detail & Related papers (2020-06-10T17:47:28Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs.
We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions.
Our methods are scalable to sparse graphs consisting of millions of nodes.
arXiv Detail & Related papers (2020-02-14T11:42:16Z) - The Power of Graph Convolutional Networks to Distinguish Random Graph
Models: Short Version [27.544219236164764]
Graph convolutional networks (GCNs) are a widely used method for graph representation learning.
We investigate the power of GCNs to distinguish between different random graph models on the basis of the embeddings of their sample graphs.
arXiv Detail & Related papers (2020-02-13T17:58:42Z)
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.