Causal Discovery with Fewer Conditional Independence Tests

• URL: http://arxiv.org/abs/2406.01823v1
• Date: Mon, 3 Jun 2024 22:27:09 GMT
• Title: Causal Discovery with Fewer Conditional Independence Tests
• Authors: Kirankumar Shiragur, Jiaqi Zhang, Caroline Uhler,
• Abstract summary: Our work focuses on characterizing what can be learned about the underlying causal graph with a reduced number of conditional independence tests. We show that it is possible to learn a coarser representation of the hidden causal graph with a number of tests. As a consequence, our results offer the first efficient algorithm for recovering the true causal graph with a number of tests.
• Score: 15.876392307650248
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many questions in science center around the fundamental problem of understanding causal relationships. However, most constraint-based causal discovery algorithms, including the well-celebrated PC algorithm, often incur an exponential number of conditional independence (CI) tests, posing limitations in various applications. Addressing this, our work focuses on characterizing what can be learned about the underlying causal graph with a reduced number of CI tests. We show that it is possible to a learn a coarser representation of the hidden causal graph with a polynomial number of tests. This coarser representation, named Causal Consistent Partition Graph (CCPG), comprises of a partition of the vertices and a directed graph defined over its components. CCPG satisfies consistency of orientations and additional constraints which favor finer partitions. Furthermore, it reduces to the underlying causal graph when the causal graph is identifiable. As a consequence, our results offer the first efficient algorithm for recovering the true causal graph with a polynomial number of tests, in special cases where the causal graph is fully identifiable through observational data and potentially additional interventions.

Related papers

• CausalGraph2LLM: Evaluating LLMs for Causal Queries [49.337170619608145]
  Causality is essential in scientific research, enabling researchers to interpret true relationships between variables. With the recent advancements in Large Language Models (LLMs), there is an increasing interest in exploring their capabilities in causal reasoning.
  arXiv  Detail & Related papers  (2024-10-21T12:12:21Z)
• Scalable and Flexible Causal Discovery with an Efficient Test for Adjacency [48.769884734826974]
  We build a scalable and flexible method to evaluate if two variables are adjacent in a causal graph. The Differentiable Adjacency Test replaces an exponential number of tests with a provably equivalent relaxed problem. We also build a graph learning method based on DAT, DAT-Graph, that can also learn from data with interventions.
  arXiv  Detail & Related papers  (2024-06-13T14:39:40Z)
• Adaptive Online Experimental Design for Causal Discovery [9.447864414136905]
  Causal discovery aims to uncover cause-and-effect relationships encoded in causal graphs. We focus on data interventional efficiency and formalize causal discovery from the perspective of online learning. We propose a track-and-stop causal discovery algorithm that adaptively selects interventions from the graph separating system.
  arXiv  Detail & Related papers  (2024-05-19T13:26:33Z)
• Towards Self-Interpretable Graph-Level Anomaly Detection [73.1152604947837]
  Graph-level anomaly detection (GLAD) aims to identify graphs that exhibit notable dissimilarity compared to the majority in a collection. We propose a Self-Interpretable Graph aNomaly dETection model ( SIGNET) that detects anomalous graphs as well as generates informative explanations simultaneously.
  arXiv  Detail & Related papers  (2023-10-25T10:10:07Z)
• 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)
• Effect Identification in Cluster Causal Diagrams [51.42809552422494]
  We introduce a new type of graphical model called cluster causal diagrams (for short, C-DAGs) C-DAGs allow for the partial specification of relationships among variables based on limited prior knowledge. We develop the foundations and machinery for valid causal inferences over C-DAGs.
  arXiv  Detail & Related papers  (2022-02-22T21:27:31Z)
• Iterative Causal Discovery in the Possible Presence of Latent Confounders and Selection Bias [7.570246812206772]
  We present a sound and complete algorithm for recovering causal graphs in the presence of latent confounders and selection bias. ICD relies on the causal Markov and faithfulness assumptions and recovers the equivalence class of the underlying causal graph. We demonstrate empirically that ICD requires significantly fewer CI tests and learns more accurate causal graphs compared to FCI, FCI+, and RFCI algorithms.
  arXiv  Detail & Related papers  (2021-11-07T14:04:46Z)
• 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)
• Collaborative Causal Discovery with Atomic Interventions [12.18848217289866]
  We model a common scenario in which we have multiple independent entities each with their own causal graph. The goal is to simultaneously learn all these causal graphs. We study this problem without the causal sufficiency assumption.
  arXiv  Detail & Related papers  (2021-06-06T04:30:29Z)
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
  We tackle the problem of exactly recovering an unknown ground-truth binary labeling of the nodes from a single corrupted observation of each edge. We apply a hierarchy of relaxations known as the sum-of-squares hierarchy, to the problem. We show that the solution of the dual of the relaxed problem is related to finding edge weights of the Johnson and Kneser graphs.
  arXiv  Detail & Related papers  (2021-02-16T08:36:19Z)
• 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.