Abstract
We present a new, efficient procedure to establish Markov equivalence between directed graphs that may or may not contain cycles. 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 explicit 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.
Introduction: The Challenge of Cyclic Causal Discovery
In causal discovery, graphs represent the influence variables exert on one another. A primary goal is identifying the "true" underlying graph from observational data. However, multiple graphs can represent the same set of conditional independence constraints; such graphs are termed Markov equivalent.
While Markov equivalence is well-defined for Directed Acyclic Graphs (DAGs), many real-world systems—such as biological pathways or economic markets—contain feedback loops or cycles. Determining equivalence in cyclic graphs is significantly more complex. The established standard, Thomas Richardson’s "Cyclic Equivalence Theorem" (CET), involves intricate definitions like "mutually exclusive conductors," making algorithms computationally expensive ($O(N^7)$ complexity) and difficult to extend to models with unobserved (latent) variables.
Methodology: An Ancestral Perspective
The authors propose a new framework: the Cyclic Maximal Ancestral Graph (CMAG). This approach shifts the focus from direct edges to ancestral relations (e.g., whether $X$ is a cause of $Y$ through any path). This "ancestral perspective" simplifies the original CET from five complex rules to four intuitive ones.
Key to this framework are "virtual v-structures" and "u-structures." In cyclic models, a set of nodes within a cycle can collectively act as a collider, creating dependencies even without a traditional v-structure. By abstracting these into local properties of the CMAG, the mathematical complexity of cycles is significantly reduced.
The proposed algorithm follows a two-step procedure:
- Graph-to-CMAG: Convert a cyclic graph into its ancestral representation.
- CMAG-to-CPAG: Transform the CMAG into a Cyclic Partial Ancestral Graph (CPAG) that represents the entire equivalence class.
Unlike previous methods that relied on exhaustive and expensive d-separation tests, this approach identifies equivalence through local structures and ancestral paths.
Experimental Results: Efficiency and Scalability
The algorithm was evaluated using synthetic collections of random directed cyclic graphs with up to 200 nodes and varying densities. To ensure rigor, the generation process was designed to produce complex cycle structures rather than trivial "giant cycles."
The results demonstrate a massive performance improvement. For a graph with 200 nodes (density 3.0), the new algorithm constructs the equivalence class in approximately 0.05 seconds, compared to 78 seconds for the previous state-of-the-art—a 1,000x speedup. Log-log plots indicate that the procedure scales much more gracefully ($O(N^5)$ complexity), making it viable for high-dimensional data.
Conclusion and Future Directions
By re-framing cyclic equivalence through an ancestral lens, this work provides a unified view that bridges linear and non-linear cyclic models. While the current implementation assumes no latent confounders, the authors suggest that the ancestral perspective is the ideal foundation for solving cyclic discovery in the presence of unobserved variables. Future work will focus on incorporating orientation propagation rules to maximize the causal information extracted from the resulting CPAGs.
Summary updated