Iterative Causal Discovery in the Possible Presence of Latent Confounders and Selection Bias

• URL: http://arxiv.org/abs/2111.04095v1
• Date: Sun, 7 Nov 2021 14:04:46 GMT
• Title: Iterative Causal Discovery in the Possible Presence of Latent Confounders and Selection Bias
• Authors: Raanan Y. Rohekar, Shami Nisimov, Yaniv Gurwicz, Gal Novik
• Abstract summary: 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.
• Score: 7.570246812206772
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a sound and complete algorithm, called iterative causal discovery (ICD), 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. It starts with a complete graph, and consists of a single iterative stage that gradually refines this graph by identifying conditional independence (CI) between connected nodes. Independence and causal relations entailed after any iteration are correct, rendering ICD anytime. Essentially, we tie the size of the CI conditioning set to its distance on the graph from the tested nodes, and increase this value in the successive iteration. Thus, each iteration refines a graph that was recovered by previous iterations having smaller conditioning sets -- a higher statistical power -- which contributes to stability. We demonstrate empirically that ICD requires significantly fewer CI tests and learns more accurate causal graphs compared to FCI, FCI+, and RFCI algorithms.

Related papers

• Causal Discovery with Fewer Conditional Independence Tests [15.876392307650248]
  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.
  arXiv  Detail & Related papers  (2024-06-03T22:27:09Z)
• Causal Layering via Conditional Entropy [85.01590667411956]
  Causal discovery aims to recover information about an unobserved causal graph from the observable data it generates. We provide ways to recover layerings of a graph by accessing the data via a conditional entropy oracle.
  arXiv  Detail & Related papers  (2024-01-19T05:18:28Z)
• From Temporal to Contemporaneous Iterative Causal Discovery in the Presence of Latent Confounders [6.365889364810238]
  We present a constraint-based algorithm for learning causal structures from observational time-series data. We assume a discrete-time, stationary structural vector autoregressive process, with both temporal and contemporaneous causal relations. The presented algorithm gradually refines a causal graph by learning long-term temporal relations before short-term ones, where contemporaneous relations are learned last.
  arXiv  Detail & Related papers  (2023-06-01T12:46:06Z)
• Dynamic Causal Explanation Based Diffusion-Variational Graph Neural Network for Spatio-temporal Forecasting [60.03169701753824]
  We propose a novel Dynamic Diffusion-al Graph Neural Network (DVGNN) fortemporal forecasting. The proposed DVGNN model outperforms state-of-the-art approaches and achieves outstanding Root Mean Squared Error result.
  arXiv  Detail & Related papers  (2023-05-16T11:38:19Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• 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)
• Online Inference for Mixture Model of Streaming Graph Signals with Non-White Excitation [34.30390182564043]
  We study a mixture model of filtered low pass graph signals with possibly non-white and low-rank excitation. As a remedy, we consider an inference problem focusing on the node centrality of graphs. We propose a novel online EM algorithm for inference from streaming data.
  arXiv  Detail & Related papers  (2022-07-28T11:25:47Z)
• 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)
• Causal Expectation-Maximisation [70.45873402967297]
  We show that causal inference is NP-hard even in models characterised by polytree-shaped graphs. We introduce the causal EM algorithm to reconstruct the uncertainty about the latent variables from data about categorical manifest variables. We argue that there appears to be an unnoticed limitation to the trending idea that counterfactual bounds can often be computed without knowledge of the structural equations.
  arXiv  Detail & Related papers  (2020-11-04T10:25:13Z)
• Convergence and Stability of Graph Convolutional Networks on Large Random Graphs [22.387735135790706]
  We study properties of Graph Convolutional Networks (GCNs) by analyzing their behavior on standard models of random graphs. We first study the convergence of GCNs to their continuous counterpart as the number of nodes grows. We then analyze the stability of GCNs to small deformations of the random graph model.
  arXiv  Detail & Related papers  (2020-06-02T18:36:19Z)
• 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)

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.