Faithful graphical representations of local independence

Søren Wengel MogensenAISTATS 2024

Introduction

In the study of stochastic processes, understanding the directional influences between different components is crucial. While Directed Acyclic Graphs (DAGs) are the standard for static causal discovery, they are often insufficient for time-evolving systems. This research addresses the challenge of representing local independence—a concept akin to conditional Granger causality—through graphical models. Specifically, it explores the property of faithfulness, ensuring that a graph accurately and exhaustively captures all independence relations present in the underlying data.

The Problem of Faithfulness

A local independence graph uses directed edges to signify that the past of one process helps predict the future of another. While the Markov property guarantees that graph separations imply independences, the inverse—faithfulness—is not automatically satisfied. Without faithfulness, a model might include "spurious" edges that do not represent true direct influences, or it might fail to represent certain independences found in the data.

Example of a local independence graph illustrating directed influences and self-loops, typical of VAR(1) processes.

The paper bridges this gap by formalizing the relationship between abstract independence models and the graphical criterion of $\mu$-separation. Unlike standard $d$-separation in DAGs, $\mu$-separation is asymmetric, reflecting the inherent directionality of time in stochastic processes. This asymmetry means the definition of faithfulness must also account for the directionality of influence in a unique way.

Theoretical Framework and Hierarchy

The author introduces a set of four transitivity conditions (D0-D3) that characterize when an independence model is faithful to a graph under $\mu$-separation. A key contribution is the definition of a hierarchy of faithfulness assumptions, allowing researchers to choose the level of strictness appropriate for their application:

  1. Strict Faithfulness: The strongest assumption, where every independence matches a graph separation.
  2. Trek, Ancestor, and Parent Faithfulness: Intermediate levels that relax requirements based on specific path types.
  3. Causal Minimality: The weakest form, requiring only that no edges can be removed without violating the Markov property.
A complex graph structure used to test the limits of different faithfulness assumptions and the performance of discovery algorithms.

Algorithmic Contributions

To operationalize these theories, the paper proposes several methods:

  • The Edge-Transitive Graph: A method to construct a faithful graph directly from an "independence oracle."
  • Trimming Algorithm: A post-processing step that removes edges from a learned graph to ensure it satisfies the transitivity conditions, thereby "forcing" the output to be faithful to observed test results.

In simulations using Vector Autoregressive (VAR(1)) processes, the Causal Minimality (CM) algorithm performed remarkably well. Despite its simplicity—using only a single test per ordered pair—it rivaled more complex adaptive algorithms. This suggests that for sufficiently large samples, testing the largest possible conditioning set is a robust strategy for identifying direct influences.

Conclusion and Future Directions

This work provides a rigorous foundation for learning local independence graphs. While it highlights the effectiveness of constraint-based methods like the CM algorithm, it also points to limitations in statistical power as network size increases. Future research is encouraged in score-based methods, which might offer more global optimization benefits, and in extending these results to systems that are not causally sufficient (i.e., contain unobserved common causes).

Summary updated

BibTeX
@inproceedings{mogensen2024faithful,
  author = {Søren Wengel Mogensen},
  title = {{Faithful graphical representations of local independence}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
}
Figure