A Discovery Algorithm for Directed Cyclic Graphs

Thomas RichardsonUAI 1996

TL;DR

This paper introduces a novel algorithm for discovering causal relationships in systems that can exhibit feedback loops (directed cyclic graphs). It addresses the limitations of existing methods that assume acyclicity, enabling causal inference in more complex, real-world scenarios like those found in social sciences and economics.

What Problem Does This Paper Address?

Traditional causal discovery methods often rely on Directed Acyclic Graphs (DAGs) to represent causal structures. These DAGs assume that causes always precede effects, meaning there are no cycles in the causal relationships. However, many real-world systems, particularly in fields like sociology, economics, and biology, exhibit feedback loops where variables can influence each other in a cyclical manner. Linear structural equation models with independent errors are often used to represent these systems, but they cannot always be faithfully represented by DAGs. This paper tackles the challenge of inferring causal structure from observational data when these feedback loops are present, a problem that existing DAG-based methods cannot adequately address.

Methods

The core of the paper is the Cyclic Causal Discovery (CCD) algorithm. This algorithm takes as input an "oracle" that can tell us whether certain variables are conditionally independent given others in a distribution. This oracle is assumed to satisfy the Global Directed Markov and Faithfulness conditions with respect to the true, unknown causal graph (which can be cyclic).

The CCD algorithm works by first constructing a Partial Ancestral Graph (PAG). A PAG is a graphical object that represents features common to all possible causal graphs within a given Markov equivalence class. The algorithm iteratively refines this PAG by:

  1. Initial Edge Placement: Starting with all possible edges between variables.
  2. Edge Removal and Sepset Identification: Using conditional independence tests to identify pairs of variables that are not d-connected given certain subsets of other variables. These subsets are stored as "Sepsets."
  3. Orientation Rules: Applying a series of rules to orient the remaining edges in the PAG. These rules are derived from theoretical properties of d-separation and Markov equivalence, ensuring that the resulting PAG accurately reflects the common causal features of all graphs in the equivalence class.

The algorithm is designed to be "d-separation complete," meaning that the output PAG uniquely identifies a Markov equivalence class. It is also polynomial in complexity for sparse graphs.

Datasets

Not discussed in the paper. The paper focuses on the theoretical development of an algorithm and relies on a hypothetical "oracle" for conditional independence tests, rather than empirical data.

Key Insights and Ideas

  • Causality with Feedback is Possible: The paper demonstrates that causal inference is possible even in the presence of feedback loops, a significant extension beyond DAG-based methods.
  • Partial Ancestral Graphs (PAGs) as a Solution: PAGs are introduced as a powerful tool to represent the common causal features of an entire Markov equivalence class, effectively summarizing the uncertainty inherent in cyclic causal discovery.
  • d-Separation as the Core Mechanism: The algorithm leverages the concept of d-separation, extended to cyclic graphs, to infer conditional independencies and orient edges.
  • Soundness and Completeness: The paper rigorously proves that the CCD algorithm is sound (it always outputs a valid PAG for the true graph) and d-separation complete (it uniquely identifies the Markov equivalence class).
  • Efficiency for Sparse Graphs: The algorithm's polynomial complexity on sparse graphs makes it practically applicable to many real-world problems where the number of direct causal relationships is limited.

Key Results

The paper presents a theoretical algorithm (CCD) that, given an oracle for conditional independencies, correctly outputs a Partial Ancestral Graph (PAG) representing the common causal structure of a Markov equivalence class. The key result is the soundness and d-separation completeness of the CCD algorithm. This means:

  • Soundness: If the input distribution satisfies the Global Directed Markov and Faithfulness conditions for a graph G, the algorithm will produce a valid PAG for G.
  • d-Separation Completeness: If two graphs G1 and G2 are not Markov equivalent, the algorithm will produce different PAGs for them. Conversely, if G1 and G2 are Markov equivalent, the algorithm will produce the same PAG for both.

The paper also provides a complexity analysis, showing the algorithm is polynomial for sparse graphs.

Limitations and Future Work

  • Oracle Assumption: The algorithm relies on a perfect "oracle" for conditional independence. In practice, this oracle would be replaced by statistical tests on sample data, which are subject to sampling error and may not perfectly reflect true independencies. This is a significant practical limitation.
  • Hidden Variables: The current framework assumes no hidden variables. Extending the algorithm to handle latent confounders would be a valuable next step.
  • Parameterization: The paper focuses on structure discovery and does not address the estimation of causal effect magnitudes.
  • Algorithm Completeness: While the algorithm is "d-separation complete" in that it uniquely identifies a Markov equivalence class, the authors note that the output PAG may not always capture all common features of the equivalence class (i.e., it might not be the "most informative" PAG). Future work could explore algorithms that produce more informative PAGs.

Summary updated

BibTeX
@inproceedings{richardson1996discovery,
  author = {Thomas Richardson},
  title = {{A Discovery Algorithm for Directed Cyclic Graphs}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1996},
}
Figure