New metrics and search algorithms for weighted causal DAGs

• URL: http://arxiv.org/abs/2305.04445v2
• Date: Tue, 30 May 2023 03:17:26 GMT
• Title: New metrics and search algorithms for weighted causal DAGs
• Authors: Davin Choo, Kirankumar Shiragur
• Abstract summary: We study causal graph discovery via adaptive interventions with node-dependent costs. We define a new benchmark that captures the worst-case interventional cost for any search algorithm. We provide adaptive search algorithms that achieve logarithmic approximations under various settings.
• Score: 7.424262881242935
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recovering causal relationships from data is an important problem. Using observational data, one can typically only recover causal graphs up to a Markov equivalence class and additional assumptions or interventional data are needed for complete recovery. In this work, under some standard assumptions, we study causal graph discovery via adaptive interventions with node-dependent interventional costs. For this setting, we show that no algorithm can achieve an approximation guarantee that is asymptotically better than linear in the number of vertices with respect to the verification number; a well-established benchmark for adaptive search algorithms. Motivated by this negative result, we define a new benchmark that captures the worst-case interventional cost for any search algorithm. Furthermore, with respect to this new benchmark, we provide adaptive search algorithms that achieve logarithmic approximations under various settings: atomic, bounded size interventions and generalized cost objectives.

Related papers

• Causal Discovery under Off-Target Interventions [18.92683981229985]
  Causal graph discovery is a significant problem with applications across various disciplines. This work addresses the causal discovery problem under the setting of interventions with the natural goal of minimizing the number of interventions performed.
  arXiv  Detail & Related papers  (2024-02-13T05:43:49Z)
• Predictive Coding beyond Correlations [59.47245250412873]
  We show how one of such algorithms, called predictive coding, is able to perform causal inference tasks. First, we show how a simple change in the inference process of predictive coding enables to compute interventions without the need to mutilate or redefine a causal graph.
  arXiv  Detail & Related papers  (2023-06-27T13:57:16Z)
• Subset verification and search algorithms for causal DAGs [13.108039226223793]
  We study the problem of identifying the smallest set of interventions required to learn the causal relationships between a subset of edges (target edges) We prove several interesting structural properties of interventional causal graphs that we believe have applications beyond the subset verification/search problems studied here.
  arXiv  Detail & Related papers  (2023-01-09T06:25:44Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  We derive a likelihood characterisation for the overall data that leads us to extend a previous EM-based algorithm. The new algorithm learns to approximate the (unidentifiability) region of model parameters from such mixed data sources. It delivers interval approximations to counterfactual results, which collapse to points in the identifiable case.
  arXiv  Detail & Related papers  (2022-12-06T12:42:11Z)
• On Correlation Detection and Alignment Recovery of Gaussian Databases [5.33024001730262]
  Correlation detection is a hypothesis testing problem; under the null hypothesis, the databases are independent, and under the alternate hypothesis, they are correlated. We develop bounds on the type-I and type-II error probabilities, and show that the analyzed detector performs better than a recently proposed detector. When the databases are accepted as correlated, the algorithm also recovers some partial alignment between the given databases.
  arXiv  Detail & Related papers  (2022-11-02T12:01:42Z)
• Score matching enables causal discovery of nonlinear additive noise models [63.93669924730725]
  We show how to design a new generation of scalable causal discovery methods. We propose a new efficient method for approximating the score's Jacobian, enabling to recover the causal graph.
  arXiv  Detail & Related papers  (2022-03-08T21:34:46Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• Scalable Intervention Target Estimation in Linear Models [52.60799340056917]
  Current approaches to causal structure learning either work with known intervention targets or use hypothesis testing to discover the unknown intervention targets. This paper proposes a scalable and efficient algorithm that consistently identifies all intervention targets. The proposed algorithm can be used to also update a given observational Markov equivalence class into the interventional Markov equivalence class.
  arXiv  Detail & Related papers  (2021-11-15T03:16:56Z)
• Riemannian classification of EEG signals with missing values [67.90148548467762]
  This paper proposes two strategies to handle missing data for the classification of electroencephalograms. The first approach estimates the covariance from imputed data with the $k$-nearest neighbors algorithm; the second relies on the observed data by leveraging the observed-data likelihood within an expectation-maximization algorithm. As results show, the proposed strategies perform better than the classification based on observed data and allow to keep a high accuracy even when the missing data ratio increases.
  arXiv  Detail & Related papers  (2021-10-19T14:24:50Z)
• Improving Efficiency and Accuracy of Causal Discovery Using a Hierarchical Wrapper [7.570246812206772]
  Causal discovery from observational data is an important tool in many branches of science. In the large sample limit, sound and complete causal discovery algorithms have been previously introduced. However, only finite training data is available, which limits the power of statistical tests used by these algorithms.
  arXiv  Detail & Related papers  (2021-07-11T09:24:49Z)
• A Single Iterative Step for Anytime Causal Discovery [7.570246812206772]
  We present a sound and complete algorithm for recovering causal graphs from observed, non-interventional data. We rely on the causal Markov and faithfulness assumptions and recover the equivalence class of the underlying causal graph. We demonstrate that our algorithm requires significantly fewer CI tests and smaller condition sets compared to the FCI algorithm.
  arXiv  Detail & Related papers  (2020-12-14T13:46:01Z)

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.