Practical Algorithms for Orientations of Partially Directed Graphical Models

• URL: http://arxiv.org/abs/2302.14386v1
• Date: Tue, 28 Feb 2023 08:15:49 GMT
• Title: Practical Algorithms for Orientations of Partially Directed Graphical Models
• Authors: Malte Luttermann, Marcel Wien\"obst, Maciej Li\'skiewicz
• Abstract summary: In observational studies, the true causal model is typically unknown and needs to be estimated from available observational and limited experimental data. In such cases, the learned causal model is commonly represented as a partially directed acyclic graph (PDAG) The main focus of this paper is on the maximal orientation task, which, for a given PDAG, aims to orient the undirected edges maximally.
• Score: 5.833272638548153
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In observational studies, the true causal model is typically unknown and needs to be estimated from available observational and limited experimental data. In such cases, the learned causal model is commonly represented as a partially directed acyclic graph (PDAG), which contains both directed and undirected edges indicating uncertainty of causal relations between random variables. The main focus of this paper is on the maximal orientation task, which, for a given PDAG, aims to orient the undirected edges maximally such that the resulting graph represents the same Markov equivalent DAGs as the input PDAG. This task is a subroutine used frequently in causal discovery, e. g., as the final step of the celebrated PC algorithm. Utilizing connections to the problem of finding a consistent DAG extension of a PDAG, we derive faster algorithms for computing the maximal orientation by proposing two novel approaches for extending PDAGs, both constructed with an emphasis on simplicity and practical effectiveness.

Related papers

• Matrix Completion with Graph Information: A Provable Nonconvex Optimization Approach [5.235925587710112]
  We consider the problem of matrix completion with graphs as side information depicting the interrelations between variables. We propose in this paper a graph regularized matrix completion algorithm called GSGD, based on preconditioned projected descent approach.
  arXiv  Detail & Related papers  (2025-02-12T16:21:01Z)
• Redefining the Shortest Path Problem Formulation of the Linear Non-Gaussian Acyclic Model: Pairwise Likelihood Ratios, Prior Knowledge, and Path Enumeration [0.0]
  The paper proposes a threefold enhancement to the LiNGAM-SPP framework. The need for parameter tuning is eliminated by using the pairwise likelihood ratio in lieu of kNN-based mutual information. The incorporation of prior knowledge is then enabled by a node-skipping strategy implemented on the graph representation of all causal orderings.
  arXiv  Detail & Related papers  (2024-04-18T05:59:28Z)
• 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)
• BOURNE: Bootstrapped Self-supervised Learning Framework for Unified Graph Anomaly Detection [50.26074811655596]
  We propose a novel unified graph anomaly detection framework based on bootstrapped self-supervised learning (named BOURNE) By swapping the context embeddings between nodes and edges, we enable the mutual detection of node and edge anomalies. BOURNE can eliminate the need for negative sampling, thereby enhancing its efficiency in handling large graphs.
  arXiv  Detail & Related papers  (2023-07-28T00:44:57Z)
• BayesDAG: Gradient-Based Posterior Inference for Causal Discovery [30.027520859604955]
  We introduce a scalable causal discovery framework based on a combination of Markov Chain Monte Carlo and Variational Inference. Our approach directly samples DAGs from the posterior without requiring any DAG regularization. We derive a novel equivalence to the permutation-based DAG learning, which opens up possibilities of using any relaxed estimator defined over permutations.
  arXiv  Detail & Related papers  (2023-07-26T02:34:13Z)
• Estimation of a Causal Directed Acyclic Graph Process using Non-Gaussianity [3.04585143845864]
  We propose a new approach to discover causal dependencies in machine learning and data mining. The CGP-LiNGAM has significantly fewer model parameters and deals with only one causal graph for interpreting the causal relations.
  arXiv  Detail & Related papers  (2022-11-24T21:09:55Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• 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)
• BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery [97.79015388276483]
  A structural equation model (SEM) is an effective framework to reason over causal relationships represented via a directed acyclic graph (DAG) Recent advances enabled effective maximum-likelihood point estimation of DAGs from observational data. We propose BCD Nets, a variational framework for estimating a distribution over DAGs characterizing a linear-Gaussian SEM.
  arXiv  Detail & Related papers  (2021-12-06T03:35:21Z)
• Learning Gaussian Graphical Models with Latent Confounders [74.72998362041088]
  We compare and contrast two strategies for inference in graphical models with latent confounders. While these two approaches have similar goals, they are motivated by different assumptions about confounding. We propose a new method, which combines the strengths of these two approaches.
  arXiv  Detail & Related papers  (2021-05-14T00:53:03Z)
• 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.