Establishing Markov Equivalence in Cyclic Directed Graphs

Tom Claassen, Joris M. Mooij

TL;DR

This paper introduces a novel, ancestral perspective on establishing Markov equivalence for cyclic directed graphs, leading to a significantly more efficient algorithm. By reformulating the Cyclic Equivalence Theorem (CET) in terms of a simplified graphical representation (CMAGs), the authors bypass computationally expensive d-separation tests, achieving a speedup of up to three orders of magnitude. This work aims to revitalize research in causal discovery for systems with feedback loops, a crucial but challenging area.

What Problem Does This Paper Address?

Discovering causal relationships from data is a fundamental goal in many scientific fields. While significant progress has been made in causal discovery for acyclic directed graphs (DAGs), handling systems with feedback loops (cyclic directed graphs) and unobserved confounders remains a major challenge. Existing methods for cyclic graphs, particularly those relying on the d-separation criterion, are often computationally complex and conceptually intricate. This paper tackles the problem of efficiently establishing Markov equivalence between cyclic directed graphs, aiming to simplify the theoretical framework and develop a faster algorithm for identifying these equivalence classes. This is crucial because real-world systems, from biological networks to economic models, often involve feedback mechanisms.

Methods

The core contribution of this paper is a new, ancestral perspective on the Cyclic Equivalence Theorem (CET). Instead of directly working with directed graphs and d-separation tests, the authors introduce the concept of a Cyclic Maximal Ancestral Graph (CMAG). This CMAG acts as an intermediate, simplified graphical representation that captures the invariant structural features shared by all graphs within a Markov equivalence class.

The authors then reformulate the CET in terms of properties of these CMAGs. This new "ancestral CET" involves checking for:

  1. Same skeleton: The underlying undirected graph structure.
  2. Same v-structures: Specific patterns of converging arrows.
  3. Same virtual collider triples: A novel concept introduced to handle cycles.
  4. Invariant relationships between virtual collider triples and virtual v-structures: This rule addresses how certain ancestral relationships are preserved.

This ancestral formulation leads to a new algorithm, "Graph-to-CMAG," which first constructs the CMAG from a given directed graph and then derives a Cyclic Partial Ancestral Graph (CPAG) from the CMAG. Crucially, this procedure avoids explicit d-separation tests, relying instead on the properties of the CMAG. The authors also present a corrected version of the original CET and an adjusted algorithm based on this new perspective.

Datasets

Not discussed in the paper. The authors generate random cyclic graphs for their experiments.

Key Insights and Ideas

  • Ancestral Perspective Simplifies Complexity: By shifting the focus from direct d-separation tests to an intermediate graphical representation (CMAG), the authors reveal a conceptually simpler and computationally more efficient way to characterize Markov equivalence in cyclic graphs.
  • Virtual Colliders as Key to Cycles: The introduction of "virtual collider triples" is a novel concept that effectively captures the unique dependencies introduced by cycles, which are not present in acyclic graphs.
  • Bypassing d-Separation: The most significant practical insight is that Markov equivalence can be established without computationally expensive d-separation tests, by leveraging the structural properties of the CMAG. This is a major algorithmic breakthrough.
  • Theoretical Foundation for Cyclic Discovery: The simplified ancestral CET provides a clearer theoretical basis for future research into sound and complete causal discovery algorithms for cyclic systems, especially in the presence of latent confounders.

Key Results

  • Algorithmic Speedup: The new "Graph-to-CPAG" algorithm achieves a speedup of up to three orders of magnitude compared to the original CPAG-from-Graph algorithm. For instance, reconstructing a CPAG for a graph with 200 nodes and density 3.0 takes about 0.05 seconds on average with the new method, versus 78 seconds with the old one.
  • Reduced Complexity: The worst-case complexity of the new algorithm is reduced from O(N⁷) to O(N⁵), making it significantly more scalable.
  • d-Separation Completeness: The proposed algorithm is shown to be d-separation complete, meaning that two graphs are Markov equivalent if and only if their corresponding output CPAGs are identical.
  • Correction and Refinement: The paper includes a correction to a rule in the original CET and an adjustment to the algorithm, improving its accuracy and efficiency.

Limitations and Future Work

  • Maximally Informative CPAG: The current work focuses on obtaining a CPAG that uniquely identifies the Markov equivalence class, but not necessarily the "maximally informative" CPAG. This means some identifiable cycles might not be represented in the most explicit form. Future work could involve developing additional orientation propagation rules to extract all available information.
  • Latent Confounders: While the paper simplifies cyclic graph analysis, it primarily focuses on the case without unobserved confounders. The authors suggest that their ancestral perspective might pave the way for extending these methods to handle latent confounders, analogous to how MAGs are used for acyclic graphs.
  • σ-Separation and Non-linear Models: The paper mentions that for non-linear cyclic models, a different criterion (σ-separation) is needed. Future work could explore how the ancestral framework might be extended to these more general settings.
  • Merging Cyclic and Non-linear Concepts: The CMAG's treatment of strongly connected components is noted to be similar to the σ-separation approach for non-linear models, suggesting potential avenues for unifying these concepts.

Summary updated

Abstract

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.
BibTeX
@inproceedings{claassen2023establishing,
  author = {Tom Claassen and Joris M. Mooij},
  title = {{Establishing Markov Equivalence in Cyclic Directed Graphs}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=5ZTRfeywCB},
}
Figure