Learning DAGs from Data with Few Root Causes

• URL: http://arxiv.org/abs/2305.15936v2
• Date: Tue, 23 Jan 2024 22:08:20 GMT
• Title: Learning DAGs from Data with Few Root Causes
• Authors: Panagiotis Misiakos, Chris Wendler, Markus P\"uschel
• Abstract summary: We present a novel perspective and algorithm for learning directed acyclic graphs (DAGs) from data generated by a linear structural equation model (SEM) For data with few root causes, with and without noise, we show superior performance compared to prior DAG learning methods.
• Score: 6.747934699209742
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a novel perspective and algorithm for learning directed acyclic graphs (DAGs) from data generated by a linear structural equation model (SEM). First, we show that a linear SEM can be viewed as a linear transform that, in prior work, computes the data from a dense input vector of random valued root causes (as we will call them) associated with the nodes. Instead, we consider the case of (approximately) few root causes and also introduce noise in the measurement of the data. Intuitively, this means that the DAG data is produced by few data-generating events whose effect percolates through the DAG. We prove identifiability in this new setting and show that the true DAG is the global minimizer of the $L^0$-norm of the vector of root causes. For data with few root causes, with and without noise, we show superior performance compared to prior DAG learning methods.

Related papers

• Analytic DAG Constraints for Differentiable DAG Learning [83.93320658222717]
  We develop a theory to establish a connection between analytic functions and DAG constraints. We show that analytic functions from the set $f(x) = c_0 + sum_i=1inftyc_ixi | forall i > 0, c_i > 0; r = lim_irightarrow inftyc_i/c_i+1 > 0$ can be employed to formulate effective DAG constraints.
  arXiv  Detail & Related papers  (2025-03-24T23:51:35Z)
• Learning Directed Acyclic Graphs from Partial Orderings [9.387234607473054]
  directed acyclic graphs (DAGs) are commonly used to model causal relationships among random variables. In this paper, we consider the intermediate problem of learning DAGs when a partial causal ordering of variables is available. We propose a general estimation framework for leveraging the partial ordering and present efficient estimation algorithms for low- and high-dimensional problems.
  arXiv  Detail & Related papers  (2024-03-24T06:14:50Z)
• Root Cause Explanation of Outliers under Noisy Mechanisms [50.59446568076628]
  Causal processes are often modelled as graphs with entities being nodes and their paths/interconnections as edge. Existing work only consider the contribution of nodes in the generative process. We consider both individual edge and node of each mechanism when identifying the root causes.
  arXiv  Detail & Related papers  (2023-12-19T03:24:26Z)
• Discovering Dynamic Causal Space for DAG Structure Learning [64.763763417533]
  We propose a dynamic causal space for DAG structure learning, coined CASPER. It integrates the graph structure into the score function as a new measure in the causal space to faithfully reflect the causal distance between estimated and ground truth DAG.
  arXiv  Detail & Related papers  (2023-06-05T12:20:40Z)
• Reinforcement Causal Structure Learning on Order Graph [18.344249064559087]
  We propose Reinforcement Causal Structure Learning on Order Graph (RCL-OG) to model different DAG topological orderings. RCL-OG first defines reinforcement learning with a new reward mechanism to approximate the posterior distribution of orderings. It computes the posterior probability of different orderings.
  arXiv  Detail & Related papers  (2022-11-22T10:29:25Z)
• Causal Fourier Analysis on Directed Acyclic Graphs and Posets [11.000499414131324]
  We present a novel form of Fourier analysis, and associated signal processing concepts, for signals (or data) indexed by edge-weighted directed acyclic graphs (DAGs) This means that our Fourier basis yields an eigendecomposition of a suitable notion of shift and convolution operators that we define. For a prototypical application we consider DAGs modeling dynamic networks in which edges change over time.
  arXiv  Detail & Related papers  (2022-09-16T14:37:09Z)
• Tearing Apart NOTEARS: Controlling the Graph Prediction via Variance Manipulation [17.103787431518683]
  We show that we can control the resulting graph with our targeted variance attacks. In particular, we show that we can control the resulting graph with our targeted variance attacks.
  arXiv  Detail & Related papers  (2022-06-14T22:53:05Z)
• MissDAG: Causal Discovery in the Presence of Missing Data with Continuous Additive Noise Models [78.72682320019737]
  We develop a general method, which we call MissDAG, to perform causal discovery from data with incomplete observations. MissDAG maximizes the expected likelihood of the visible part of observations under the expectation-maximization framework. We demonstrate the flexibility of MissDAG for incorporating various causal discovery algorithms and its efficacy through extensive simulations and real data experiments.
  arXiv  Detail & Related papers  (2022-05-27T09:59:46Z)
• Sequential Learning of the Topological Ordering for the Linear Non-Gaussian Acyclic Model with Parametric Noise [6.866717993664787]
  We develop a novel sequential approach to estimate the causal ordering of a DAG. We provide extensive numerical evidence to demonstrate that our procedure is scalable to cases with possibly thousands of nodes.
  arXiv  Detail & Related papers  (2022-02-03T18:15:48Z)
• BCDAG: An R package for Bayesian structure and Causal learning of Gaussian DAGs [77.34726150561087]
  We introduce the R package for causal discovery and causal effect estimation from observational data. Our implementation scales efficiently with the number of observations and, whenever the DAGs are sufficiently sparse, the number of variables in the dataset. We then illustrate the main functions and algorithms on both real and simulated datasets.
  arXiv  Detail & Related papers  (2022-01-28T09:30:32Z)
• Federated Causal Discovery [74.37739054932733]
  This paper develops a gradient-based learning framework named DAG-Shared Federated Causal Discovery (DS-FCD) It can learn the causal graph without directly touching local data and naturally handle the data heterogeneity. Extensive experiments on both synthetic and real-world datasets verify the efficacy of the proposed method.
  arXiv  Detail & Related papers  (2021-12-07T08:04:12Z)
• Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystr\"om method [76.73096213472897]
  We develop techniques which exploit spectral properties of the data matrix to obtain improved approximation guarantees. Our approach leads to significantly better bounds for datasets with known rates of singular value decay. We show that both our improved bounds and the multiple-descent curve can be observed on real datasets simply by varying the RBF parameter.
  arXiv  Detail & Related papers  (2020-02-21T00:43:06Z)

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.