Faster algorithms for Markov equivalence

Journal article

Maximal ancestral graphs (MAGs) have many desirable properties; in particular they can fully describe conditional independences from directed acyclic graphs (DAGs) in the presence of latent and selection variables. However, different MAGs may encode the same conditional independences, and are said to be \emph{Markov equivalent}. Thus identifying necessary and sufficient conditions for equivalence is essential for structure learning. Several criteria for this already exist, but in this paper we give a new non-parametric characterization in terms of the heads and tails that arise in the parameterization for discrete models. We also provide a polynomial time algorithm (𝑂(𝑛𝑒2)O(ne2), where 𝑛n and 𝑒e are the number of vertices and edges respectively) to verify equivalence. Moreover, we extend our criterion to ADMGs and summary graphs and propose an algorithm that converts an ADMG or summary graph to an equivalent MAG in polynomial time (𝑂(𝑛2𝑒)O(n2e)). Hence by combining both algorithms, we can also verify equivalence between two summary graphs or ADMGs.

Authors: Hu, Z; Evans, R

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Journal of Machine Learning Research
• Pages: 739-748
• Series: Proceedings of Machine Learning Research
• Series number: 124
• Publication date: 2020-06-08
• Acceptance date: 2020-05-14
• Event title: 36th Conference on Uncertainty in Artificial Intelligence (UAI)
• Event location: Virtual event
• Event website: http://www.auai.org/uai2020/
• Event start date: 2020-08-03
• Event end date: 2020-08-06
• ISSN: 2640-3498
• Language: English
• Keywords: FFR