Establishing Markov Equivalence in Cyclic Directed Graphs
Tom Claassen Joris M. Mooij
We present a new, efficient procedure to establish Markov equivalence between
directed graphs that may or may not contain cycles under the
\textit{d}-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.