A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the same Skeleton

• URL: http://arxiv.org/abs/2310.04218v5
• Date: Wed, 3 Jul 2024 04:41:05 GMT
• Title: A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the same Skeleton
• Authors: Vidya Sagar Sharma,
• Abstract summary: Causal DAGs (also known as Bayesian networks) are a popular tool for encoding conditional dependencies between random variables. It is possible, however, for two different causal DAGs on the same set of random variables to encode exactly the same set of conditional dependencies. Such causal DAGs are said to be Markov equivalent and equivalence classes of Markov equivalent DAGs are known as Markov Equivalent Classes (MECs)
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Causal DAGs (also known as Bayesian networks) are a popular tool for encoding conditional dependencies between random variables. In a causal DAG, the random variables are modeled as vertices in the DAG, and it is stipulated that every random variable is independent of its ancestors conditioned on its parents. It is possible, however, for two different causal DAGs on the same set of random variables to encode exactly the same set of conditional dependencies. Such causal DAGs are said to be Markov equivalent, and equivalence classes of Markov equivalent DAGs are known as Markov Equivalent Classes (MECs). Beautiful combinatorial characterizations of MECs have been developed in the past few decades, and it is known, in particular that all DAGs in the same MEC must have the same "skeleton" (underlying undirected graph) and v-structures (induced subgraph of the form $a\rightarrow b \leftarrow c$). These combinatorial characterizations also suggest several natural algorithmic questions. One of these is: given an undirected graph $G$ as input, how many distinct Markov equivalence classes have the skeleton $G$? Much work has been devoted in the last few years to this and other closely related problems. However, to the best of our knowledge, a polynomial time algorithm for the problem remains unknown. In this paper, we make progress towards this goal by giving a fixed parameter tractable algorithm for the above problem, with the parameters being the treewidth and the maximum degree of the input graph $G$. The main technical ingredient in our work is a construction we refer to as shadow, which lets us create a "local description" of long-range constraints imposed by the combinatorial characterizations of MECs.

Related papers

• Learning High-Dimensional Differential Graphs From Multi-Attribute Data [12.94486861344922]
  We consider the problem of estimating differences in two Gaussian graphical models (GGMs) which are known to have similar structure. Existing methods for differential graph estimation are based on single-attribute (SA) models. In this paper, we analyze a group lasso penalized D-trace loss function approach for differential graph learning from multi-attribute data.
  arXiv  Detail & Related papers  (2023-12-05T18:54:46Z)
• Identification for Tree-shaped Structural Causal Models in Polynomial Time [1.5151556900495786]
  Identifying causal parameters from correlations between nodes is an open problem in artificial intelligence. In this paper, we study SCMs whose directed component forms a tree. We present a randomized-time algorithm, which solves the identification problem for tree-shaped SCMs.
  arXiv  Detail & Related papers  (2023-11-23T15:26:29Z)
• iSCAN: Identifying Causal Mechanism Shifts among Nonlinear Additive Noise Models [48.33685559041322]
  This paper focuses on identifying the causal mechanism shifts in two or more related datasets over the same set of variables. Code implementing the proposed method is open-source and publicly available at https://github.com/kevinsbello/iSCAN.
  arXiv  Detail & Related papers  (2023-06-30T01:48:11Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  We introduce a new framework named Discrete Graph Auto-Encoder (DGAE) We first use a permutation-equivariant auto-encoder to convert graphs into sets of discrete latent node representations. In the second step, we sort the sets of discrete latent representations and learn their distribution with a specifically designed auto-regressive model.
  arXiv  Detail & Related papers  (2023-06-13T12:40:39Z)
• Generalized Precision Matrix for Scalable Estimation of Nonparametric Markov Networks [11.77890309304632]
  A Markov network characterizes the conditional independence structure, or Markov property, among a set of random variables. In this work, we characterize the conditional independence structure in general distributions for all data types. We also allow general functional relations among variables, thus giving rise to a Markov network structure learning algorithm.
  arXiv  Detail & Related papers  (2023-05-19T01:53:10Z)
• Efficient Enumeration of Markov Equivalent DAGs [6.288056740658763]
  In this paper, we present the first linear-time delay algorithm. On the theoretical side, we show that our algorithm can be generalized to enumerate DAGs represented by models that incorporate background knowledge. We also provide intriguing insights into Markov equivalence itself.
  arXiv  Detail & Related papers  (2023-01-28T14:35:39Z)
• 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)
• Causal Inference Despite Limited Global Confounding via Mixture Models [4.721845865189578]
  A finite $k$-mixture of such models is graphically represented by a larger graph. We give the first algorithm to learn mixtures of non-empty DAGs.
  arXiv  Detail & Related papers  (2021-12-22T01:04:50Z)
• Benchmarking Multivariate Time Series Classification Algorithms [69.12151492736524]
  Time Series Classification (TSC) involved building predictive models for a discrete target variable from ordered, real valued, attributes. Over recent years, a new set of TSC algorithms have been developed which have made significant improvement over the previous state of the art. We review recently proposed bespoke MTSC algorithms based on deep learning, shapelets and bag of words approaches.
  arXiv  Detail & Related papers  (2020-07-26T15:56:40Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
  We introduce the Anchor Energy (AE) and Anchor Wasserstein (AW) distances, which are respectively the energy and Wasserstein distances instantiated on such representations. Our main contribution is to propose a sweep line algorithm to compute AE emphexactly in log-quadratic time, where a naive implementation would be cubic. We show that AE and AW perform well in various experimental settings at a fraction of the computational cost of popular GW approximations.
  arXiv  Detail & Related papers  (2020-02-05T03:09:23Z)

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.