Counting Markov equivalence classes for DAG models on trees

DOI10.1016/J.DAM.2018.03.015zbMATH Open1387.05104arXiv1706.06091OpenAlexW2641483345MaRDI QIDQ1752602FDOQ1752602

Authors: Adityanarayanan Radhakrishnan, Liam Solus, Caroline Uhler 

Publication date: 24 May 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: DAG models are statistical models satisfying a collection of conditional independence relations encoded by the nonedges of a directed acyclic graph (DAG) $mathcalG$. Such models are used to model complex cause-effect systems across a variety of research fields. From observational data alone, a DAG model $mathcalG$ is only recoverable up to Markov equivalence. Combinatorially, two DAGs are Markov equivalent if and only if they have the same underlying undirected graph (i.e. skeleton) and the same set of the induced subDAGs $iojleftarrowk$, known as immoralities. Hence it is of interest to study the number and size of Markov equivalence classes (MECs). In a recent paper, the authors introduced a pair of generating functions that enumerate the number of MECs on a fixed skeleton by number of immoralities and by class size, and they studied the complexity of computing these functions. In this paper, we lay the foundation for studying these generating functions by analyzing their structure for trees and other closely related graphs. We describe these polynomials for some important families of graphs including paths, stars, cycles, spider graphs, caterpillars, and complete binary trees. In doing so, we recover important connections to independence polynomials, and extend some classical identities that hold for Fibonacci numbers. We also provide tight lower and upper bounds for the number and size of MECs on any tree. Finally, we use computational methods to show that the number and distribution of high degree nodes in a triangle-free graph dictates the number and size of MECs.

Full work available at URL: https://arxiv.org/abs/1706.06091

Recommendations

• Counting and exploring sizes of Markov equivalence classes of directed acyclic graphs
• The size distribution for Markov equivalence classes of acyclic digraph models.
• A characterization of Markov equivalence classes for acyclic digraphs
• Formulas for counting acyclic digraph Markov equivalence classes
• Reversible MCMC on Markov equivalence classes of sparse directed acyclic graphs

zbMATH Keywords

Bayesian networktreesMarkov equivalence classMarkov equivalenceDAG modelimmoralities

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Combinatorial probability (60C05) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

Cites Work

• Practical graph isomorphism. II.
• Title not available (Why is that?)
• A characterization of Markov equivalence classes for acyclic digraphs
• Title not available (Why is that?)
• The max-min hill-climbing Bayesian network structure learning algorithm
• A symmetric function generalization of the chromatic polynomial of a graph
• On distinguishing trees by their chromatic symmetric functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Enumeration of labelled chain graphs and labelled essential directed acyclic graphs.
• Causation, prediction, and search. With additional material by David Heckerman, Christopher Meek, Gregory F. Cooper and Thomas Richardson.
• Title not available (Why is that?)
• Unimodality, log-concavity, real-rootedness and beyond
• Title not available (Why is that?)
• Asymptotic enumeration of extensional acyclic digraphs
• Formulas for counting acyclic digraph Markov equivalence classes
• \(r\)-stable hypersimplices
• Counting Markov equivalence classes for DAG models on trees
• Counting and exploring sizes of Markov equivalence classes of directed acyclic graphs
• Bounds on the expected size of the maximum agreement subtree

Cited In (6)

• Counting Markov equivalence classes for DAG models on trees
• Counting and exploring sizes of Markov equivalence classes of directed acyclic graphs
• An efficient algorithm for counting Markov equivalent DAGs
• Causal structure learning: a combinatorial perspective
• A review of Gaussian Markov models for conditional independence
• Reversible MCMC on Markov equivalence classes of sparse directed acyclic graphs

Uses Software

• nauty
• Traces
• TETRAD

This page was built for publication: Counting Markov equivalence classes for DAG models on trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1752602)