Respecting Markov Equivalence in Computing Posterior Probabilities of Causal Graphical Features

Eun Yong Kang, Ilya Shpitser, Eleazar Eskin

Introduction

Identifying causal relationships from observational data is a fundamental challenge in data science. While randomized controlled trials are the gold standard, they are often impractical or unethical. Researchers are thus left with observational data, which typically cannot pinpoint a single "true" causal graph. Instead, such data identifies a Markov equivalence class—a set of distinct directed acyclic graphs (DAGs) that represent the same set of conditional independence constraints.

Examples of graphs within a Markov equivalence class.

Traditional methods often struggle with a "scale problem" when calculating the posterior probability of specific directed edges. Edges that are invariant across the equivalence class yield high probabilities, while those that vary yield ambiguous results, making it difficult to establish a reliable threshold for causal discovery.

Methodology: Shifting Focus to Invariant Features

To address these limitations, researchers at UCLA and Harvard propose focusing on features consistent across all members of a Markov equivalence class:

  1. Adjacencies: The existence of a link between two nodes, regardless of its direction.
  2. V-structures: Patterns where two non-adjacent nodes both influence a third node (e.g., $A \to C \leftarrow B$).

By computing the posterior probabilities of these features, the researchers avoid forcing arbitrary choices between equivalent directed edges. To implement this efficiently, they developed a novel Dynamic Programming (DP) algorithm. While computing these probabilities over all possible structures is generally super-exponential, the proposed algorithm utilizes the inclusion-exclusion principle to achieve a complexity of $O(n^3 3^n)$. This allows for exact calculations on networks with up to approximately 25-30 variables.

Experimental Evaluation

The approach was evaluated using synthetic datasets generated from 100 random causal diagrams, each with 5 variables. Data was simulated using linear functions with Gaussian noise across sample sizes of 50, 100, and 200.

The performance was compared against traditional directed edge approaches and Maximum Likelihood (ML) methods. The primary metric was the "distinguishing power"—the ability to separate true causal features (positive features) from false ones (negative features).

Key Results and Discussion

The proposed "Adjacency + V-structure" approach provided a significantly clearer signal than traditional methods. As shown in the posterior probability distributions, the results for the proposed method tend toward a bimodal distribution as sample size increases.

Posterior probability distributions for positive and negative features across different experimental settings.

In the proposed framework, "positive" features typically exhibit posterior probabilities exceeding 0.9, while "negative" features remain below 0.5. This clear separation allows researchers to set a confident threshold for feature existence, effectively reducing the ambiguity inherent in causal discovery from observational data.

Limitations and Future Directions

Despite the algorithmic improvements, the $O(n^3 3^n)$ complexity remains a bottleneck for very large networks. Additionally, the current model assumes "Faithfulness"—that statistical dependencies perfectly mirror the underlying causal structure—and the absence of latent variables. Future research may focus on scaling these DP techniques to larger systems and relaxing these structural assumptions to better accommodate complex real-world data.

Summary updated

Abstract

There have been many efforts to identify causal graphical features such as directed edges between random variables from observational data. Recently, Tian et al. proposed a new dynamic programming algorithm which computes marginalized posterior probabilities of directed edge features over all the possible structures in O(n3n) time when the number of parents per node is bounded by a constant, where n is the number of variables of interest. However the main drawback of this approach is that deciding a single appropriate threshold for the existence of the directed edge feature is difficult due to the scale difference of the posterior probabilities between the directed edges forming v-structures and the directed edges not forming v-structures. We claim that computing posterior probabilities of both adjacencies and v-structures is necessary and more effective for discovering causal graphical features, since it allows us to find a single appropriate decision threshold for the existence of the feature that we are testing. For efficient computation, we provide a novel dynamic programming algorithm which computes the posterior probabilities of all of n(n-1)/2 adjacency and n(n-12) v-structure features in O(n33n) time.
BibTeX
@inproceedings{kang2010respecting,
  author = {Eun Yong Kang and Ilya Shpitser and Eleazar Eskin},
  title = {{Respecting Markov Equivalence in Computing Posterior Probabilities of Causal Graphical Features}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7756},
}
Figure