# Establishing Markov Equivalence in Cyclic Directed Graphs

arXiv: https://arxiv.org/abs/2309.03092 · HTML: https://mlsanity.com/paper/2309.03092/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 51 references that are in the map.
- First posted on arXiv 1 Sep 2023.

## Builds on (most cited first, 11 of 11)

- [Foundations of Structural Causal Models with Cycles and Latent Variables](https://mlsanity.com/paper/1611.06221/) (2016)
- [backShift: Learning causal cyclic graphs from unknown shift interventions](https://mlsanity.com/paper/1506.02494/) (2015)
- [Constraint-based Causal Discovery for Non-Linear Structural Causal Models with Cycles and Latent Confounders](https://mlsanity.com/paper/1807.03024/) (2018)
- [A Discovery Algorithm for Directed Cyclic Graphs](https://mlsanity.com/paper/1302.3599/) (2013)
- [Markov Properties for Graphical Models with Cycles and Latent Variables](https://mlsanity.com/paper/1710.08775/) (2017)
- [Constraint-Based Causal Discovery using Partial Ancestral Graphs in the presence of Cycles](https://mlsanity.com/paper/2005.00610/) (2020)
- [Directed Cyclic Graphical Representations of Feedback Models](https://mlsanity.com/paper/1302.4982/) (2013)
- [Cyclic Causal Discovery from Continuous Equilibrium Data](https://mlsanity.com/paper/1309.6849/) (2013)
- [A Constraint-Based Algorithm For Causal Discovery with Cycles, Latent Variables and Selection Bias](https://mlsanity.com/paper/1805.02087/) (2018)
- [Identifying Independencies in Causal Graphs with Feedback](https://mlsanity.com/paper/1302.3595/) (2013)
- [A Polynomial-Time Algorithm for Deciding Markov Equivalence of Directed Cyclic Graphical Models](https://mlsanity.com/paper/1302.3600/) (2013)

## Built on by (most cited first, 6 of 6)

- [The Causal Chambers: Real Physical Systems as a Testbed for AI Methodology](https://mlsanity.com/paper/2404.11341/) (2024)
- [Distributional Equivalence in Linear Non-Gaussian Latent-Variable Cyclic Causal Models: Characterization and Learning](https://mlsanity.com/paper/2603.04780/) (2026)
- [σ-Maximal Ancestral Graphs](https://mlsanity.com/paper/2507.00093/) (2025)
- [Causal Structure Learning in Hawkes Processes with Complex Latent Confounder Networks](https://mlsanity.com/paper/2508.11727/) (2025)
- [Design of Experiment for Discovering Directed Mixed Graph](https://mlsanity.com/paper/2509.01887/) (2025)
- [Characterizing and Identifying Separable Graphical Models](https://mlsanity.com/paper/2607.01057/) (2026)

## Abstract (arXiv)

We present a new, efficient procedure to establish Markov equivalence between directed graphs that may or may not contain cycles under the textitd-separation criterion. It is based on the Cyclic Equivalence Theorem (CET) in the seminal works on cyclic models by Thomas Richardson in the mid '90s, but now rephrased from an ancestral perspective. The resulting characterization leads to a procedure for establishing Markov equivalence between graphs that no longer requires tests for d-separation, leading to a significantly reduced algorithmic complexity. The conceptually simplified characterization may help to reinvigorate theoretical research towards sound and complete cyclic discovery in the presence of latent confounders. This version includes a correction to rule (iv) in Theorem 1, and the subsequent adjustment in part 2 of Algorithm 2.