Counting Markov Equivalent Directed Acyclic Graphs Consistent with Background Knowledge

• URL: http://arxiv.org/abs/2206.06744v2
• Date: Tue, 13 Jun 2023 12:01:17 GMT
• Title: Counting Markov Equivalent Directed Acyclic Graphs Consistent with Background Knowledge
• Authors: Vidya Sagar Sharma
• Abstract summary: We consider the more general problem of counting the number of acyclic graphs in a Markov equivalence class when the directions of some of the edges are also fixed. In particular, our algorithm does emphnot depend upon the number of additional edges provided as input.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A polynomial-time exact algorithm for counting the number of directed acyclic graphs in a Markov equivalence class was recently given by Wien\"obst, Bannach, and Li\'skiewicz (AAAI 2021). In this paper, we consider the more general problem of counting the number of directed acyclic graphs in a Markov equivalence class when the directions of some of the edges are also fixed (this setting arises, for example, when interventional data is partially available). This problem has been shown in earlier work to be complexity-theoretically hard. In contrast, we show that the problem is nevertheless tractable in an interesting class of instances, by establishing that it is ``fixed-parameter tractable''. In particular, our counting algorithm runs in time that is bounded by a polynomial in the size of the graph, where the degree of the polynomial does \emph{not} depend upon the number of additional edges provided as input.

Related papers

• Random walks on simplicial complexes [0.9937132009954994]
  We show that the generator of our Markov chain is the upper Laplacian defined in the context of algebraic topology for discrete structure. We study the diffusive limits when the simplicial complexes under scrutiny are a sequence of ever refining triangulations of the flat torus.
  arXiv  Detail & Related papers  (2024-04-12T20:37:34Z)
• Sequence graphs realizations and ambiguity in language models [1.4732811715354455]
  We study the realizability and ambiguity of sequence graphs from a computational point of view. For a window of size at least 3, we prove hardness of all variants, even when w is considered as a constant. We conclude with an integer program to solve the realizability problem, and with dynamic programming to solve the enumeration problem.
  arXiv  Detail & Related papers  (2024-02-13T22:22:51Z)
• The Complexity of Envy-Free Graph Cutting [44.58084909019557]
  We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspond to the edges of a connected graph, and every agent must be assigned a connected piece of this graph. The problem is NP-complete, and we analyze its complexity with respect to two natural complexity measures: the number of agents and the number of edges in the graph.
  arXiv  Detail & Related papers  (2023-12-12T07:54:30Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the same Skeleton [0.0]
  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)
  arXiv  Detail & Related papers  (2023-10-06T13:05:07Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• Correlation Clustering in Constant Many Parallel Rounds [42.10280805559555]
  Correlation clustering is a central topic in unsupervised learning, with many applications in ML and data mining. In this work we propose a massively parallel computation (MPC) algorithm for this problem that is considerably faster than prior work. Our algorithm uses machines with memory sublinear in the number of nodes in the graph and returns a constant approximation while running only for a constant number of rounds.
  arXiv  Detail & Related papers  (2021-06-15T21:45:45Z)
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs [45.87981728307819]
  The ability to compare and align related datasets living in heterogeneous spaces plays an increasingly important role in machine learning. The Gromov-Wasserstein (GW) formalism can help tackle this problem.
  arXiv  Detail & Related papers  (2021-06-02T12:50:56Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)

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.