Local Markov Property for Models Satisfying Composition Axiom

Changsung Kang, Jin Tian

TL;DR

Verifying whether a complex causal model fits your data usually requires an overwhelming number of statistical tests. This paper proves that by assuming a simple property called the "composition axiom"—which is naturally satisfied by the common Gaussian distributions used in linear modeling—we can drastically reduce the number of required tests from an exponential explosion down to a manageable, often linear, amount.

What Problem Does This Paper Address?

In the world of causal inference, we often use Directed Acyclic Graphs (DAGs) to represent how variables influence one another. However, real-world data often has "latent" or hidden variables that we can't measure. To account for these, researchers use Acyclic Directed Mixed Graphs (ADMGs), which add bi-directed edges ($\leftrightarrow$) to represent correlated errors between observed variables.

The challenge lies in testing if a specific ADMG actually matches the patterns in our data. We do this by checking "local Markov properties"—a set of conditional independence (CI) relations that, if true, imply the entire model is valid. For standard DAGs, this is easy: you only need one test per variable. But for ADMGs, the number of required tests can grow exponentially with the number of variables. This makes testing large, complex models computationally impossible in practice.

Methods

The authors tackle this "exponential headache" by leveraging the composition axiom. This axiom states that if a variable $X$ is independent of $Y$ given $Z$, and $X$ is also independent of $W$ given $Z$, then $X$ must be independent of the combined set $\{Y, W\}$ given $Z$. While not true for all probability distributions, it is a hallmark of the normal (Gaussian) distributions used in linear Structural Equation Modeling (SEM).

The paper introduces three key technical contributions:

  1. Theorem 2: For a specific class of graphs that lack "mixed directed cycles," the authors prove that the local Markov property simplifies to a single CI test per vertex. This brings ADMGs on par with standard DAGs in terms of testing efficiency.
  2. Lemmas 1 & 2: For more complex graphs that do contain mixed directed cycles, the authors provide two mathematical rules to identify and prune redundant CI tests.
  3. A Reduction Procedure: They outline a step-by-step algorithm to generate a minimal set of CI relations. This involves transforming the ADMG into a simplified DAG to find an optimal ordering of variables, then systematically applying the lemmas to discard unnecessary tests.
Figure 3: An example ADMG.

Datasets

This is a theoretical paper focused on graph theory and probability axioms. As such, it does not use large-scale empirical datasets. Instead, the authors validate their approach using illustrative graph structures (like the one shown in Figure 3) and a specific linear SEM example to demonstrate the reduction in test requirements.

Key Insights and Ideas

  • The Power of Normality: The most significant "aha moment" is realizing that the common assumption of Gaussian noise in linear models isn't just a convenience—it's a powerful tool for structural simplification. Because Gaussian models satisfy the composition axiom, we can ignore a massive chunk of the CI tests previously thought necessary.
  • Structural Bottlenecks: The paper identifies "mixed directed cycles" (paths that combine directed and bi-directed edges in a specific way) as the primary source of complexity. If your model avoids these, testing becomes exponentially faster.
  • Local vs. Global: The authors advocate for local CI testing over traditional global "goodness-of-fit" tests. Local tests are often more robust and can pinpoint exactly where a model fails, rather than just giving a binary "pass/fail" for the entire system.

Key Results

The efficiency gains are substantial. In a sample linear SEM provided in the paper (based on Figure 2):

  • Standard Method: Required 7 distinct conditional independence tests.
  • Proposed Method: Required only 3 tests.

In a more complex graph (Figure 3), the standard "ordered local Markov property" required 13 tests, while the authors' reduced method required only 10. The paper demonstrates that as models grow in size, these savings prevent the testing process from becoming mathematically intractable.

Limitations and Future Work

The primary limitation is the reliance on the composition axiom. If a researcher is working with highly non-linear systems or non-Gaussian distributions that violate this axiom, the reduction techniques presented here may not be valid.

Furthermore, while the paper provides a procedure to reduce the number of tests, it does not claim to always reach the absolute minimum number of tests for every possible graph structure. Future research could focus on finding the theoretical lower bound for CI tests in ADMGs under various distributional assumptions.

Summary updated

Abstract

The local Markov condition for a DAG to be an independence map of a probability distribution is well known. For DAGs with latent variables, represented as bi-directed edges in the graph, the local Markov property may invoke exponential number of conditional independencies. This paper shows that the number of conditional independence relations required may be reduced if the probability distributions satisfy the composition axiom. In certain types of graphs, only linear number of conditional independencies are required. The result has applications in testing linear structural equation models with correlated errors.
BibTeX
@inproceedings{kang2005local,
  author = {Changsung Kang and Jin Tian},
  title = {{Local Markov Property for Models Satisfying Composition Axiom}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2005},
}
Figure