mlsanityData to 7 Oct 2026

Establishing Markov Equivalence in Cyclic Directed Graphs

arXiv 2309.03092 ↗First posted 1 Sep 2023cs.AI cs.DM cs.LGcited by 5

Not on the map. Why?

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.

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

Builds on

11 of 51 references.

References · 11

  1. 2016Foundations of Structural Causal Models with Cycles and Latent Variablescited by 134
  2. 2015backShift: Learning causal cyclic graphs from unknown shift interventionscited by 37
  3. 2018Constraint-based Causal Discovery for Non-Linear Structural Causal Models with Cycles and Latent Confounderscited by 35
  4. 2013A Discovery Algorithm for Directed Cyclic Graphscited by 33
  5. 2017Markov Properties for Graphical Models with Cycles and Latent Variablescited by 32
  6. 2020Constraint-Based Causal Discovery using Partial Ancestral Graphs in the presence of Cyclescited by 31
  7. 2013Directed Cyclic Graphical Representations of Feedback Modelscited by 27
  8. 2013Cyclic Causal Discovery from Continuous Equilibrium Datacited by 21
  9. 2018A Constraint-Based Algorithm For Causal Discovery with Cycles, Latent Variables and Selection Biascited by 15
  10. 2013Identifying Independencies in Causal Graphs with Feedbackcited by 7
  11. 2013A Polynomial-Time Algorithm for Deciding Markov Equivalence of Directed Cyclic Graphical Modelscited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 1.

5 papers.

  1. 2024The Causal Chambers: Real Physical Systems as a Testbed for AI Methodologycited by 12
  2. 2026Distributional Equivalence in Linear Non-Gaussian Latent-Variable Cyclic Causal Models: Characterization and Learningcited by 4
  3. 2025σ-Maximal Ancestral Graphscited by 0
  4. 2025Causal Structure Learning in Hawkes Processes with Complex Latent Confounder Networkscited by 0
  5. 2025Design of Experiment for Discovering Directed Mixed Graphcited by 0