Causal Structure Learning With Momentum: Sampling Distributions Over Markov Equivalence Classes

Moritz Schauer, Marcel WienöbstPgm 2024

TL;DR

This paper introduces a novel, continuous-time Markov chain Monte Carlo (MCMC) sampler called the "Causal Zig-Zag sampler" designed to efficiently explore the space of Markov equivalence classes of causal Bayesian networks. By incorporating a momentum variable and leveraging efficient algorithms for graph operations, this sampler significantly improves mixing times and offers a practical approach for causal discovery, especially in scenarios with uncertainty.

What Problem Does This Paper Address?

Inferring causal relationships from observational data is a fundamental challenge in many scientific fields. Bayesian networks, represented as directed acyclic graphs (DAGs), are a powerful tool for this, but observational data alone is often insufficient to uniquely determine the underlying causal DAG. This is because multiple DAGs can imply the same set of conditional independencies, forming a "Markov equivalence class" (MEC). Representing these MECs as completed partially directed acyclic graphs (CPDAGs), the paper addresses the problem of efficiently sampling from the posterior distribution over these MECs. Traditional MCMC methods for this task can suffer from slow mixing, making it difficult to explore the complex space of possible causal structures.

Methods

The core contribution is the "Causal Zig-Zag sampler," a non-reversible, continuous-time Markov jump process. It operates on the space of MECs (represented by CPDAGs) and incorporates a "momentum" variable, inspired by Hamiltonian Monte Carlo, to improve exploration. The sampler utilizes operators (inserting and deleting edges) originally proposed by Chickering for the Greedy Equivalence Search (GES) algorithm.

Key methodological innovations include:

  • Non-reversible continuous-time sampler: Unlike many reversible MCMC methods, this sampler's non-reversibility, achieved through directed moves (inserting vs. deleting edges), leads to better mixing.
  • Momentum variable: This variable helps balance random walk behavior with systematic exploration, further enhancing mixing.
  • Efficient graph operations: The paper introduces novel, linear-time algorithms for applying GES operators (inserting/deleting edges and completing PDAGs to CPDAGs). This is crucial for the sampler's efficiency, as these operations are performed repeatedly.
  • Lifted state space: The sampler operates on an extended state space that includes the MEC (CPDAG) and a direction variable, enabling the "Zig-Zag" behavior.

Datasets

The paper uses two main illustrations:

  • Synthetic data: The first illustration involves sampling CPDAGs with 100 vertices uniformly. This is used to demonstrate the sampler's faster equilibrium attainment compared to a reversible counterpart.
  • Alzheimer's Disease Neuroimaging Initiative (ADNI) database: This real-world dataset is used to reproduce findings from Shen et al. (2020). The variables extracted include demographic information (age, sex, education), diagnosis of Alzheimer's disease, and genetic factors (APOE ε4 alleles), as well as PET scan data (FDG, amyloid beta). This application showcases the sampler's ability to handle real-world data and quantify uncertainty in causal discovery.

Key Insights and Ideas

  • Non-reversibility for better mixing: The paper empirically demonstrates that a non-reversible MCMC approach, by allowing for directed exploration of the MEC space, can significantly outperform reversible methods in terms of mixing time.
  • Momentum as a general MCMC enhancement: The successful application of a momentum variable, borrowed from Hamiltonian Monte Carlo, to the space of MECs highlights its potential for improving MCMC samplers in various complex state spaces.
  • Algorithmic efficiency is key: The development of linear-time algorithms for fundamental graph operations (like applying GES operators) is not just an implementation detail but a critical enabler for the overall efficiency of the causal discovery process.
  • GES as a limiting case: The paper shows that under specific conditions (high "coldness" parameter $\beta$ and a specific balancing function), the Causal Zig-Zag sampler converges to the behavior of the Greedy Equivalence Search (GES) algorithm, providing a theoretical link and validation.

Key Results

  • Faster mixing: Figure 1 shows that the Causal Zig-Zag sampler reaches equilibrium considerably faster than a reversible sampler when targeting a uniform distribution on CPDAGs.
  • Efficient operator application: The paper presents algorithms that reduce the time complexity of applying GES operators to linear time ($O(n+m)$), a significant improvement over previous $O(n^3)$ methods.
  • Efficient operator counting: The number of locally valid Insert and Delete operators can be computed in polynomial time ($O(n^2 \cdot m)$), enabling uniform sampling of operators.
  • Practical application: The sampler is applied to the ADNI dataset, demonstrating its ability to infer causal structures and quantify uncertainty, as shown in Figures 2 and 3.

Limitations and Future Work

  • Computational complexity for operator counting: While polynomial, the $O(n^2 \cdot m)$ complexity for counting operators might still be a bottleneck for very large graphs.
  • Tuning parameters: Although the paper mentions that their sampler requires no further choice of tuning parameters beyond the balancing function $g$, the choice of $g$ and the target distribution $\pi$ can still influence performance.
  • Future work: The authors suggest that their algorithmic improvements for graph operations are general and can benefit other score-based causal discovery algorithms. Further exploration of the sampler's behavior with different scoring functions and its application to more complex causal discovery scenarios are implied. The paper also notes that the proof of Theorem 4 regarding irreducibility is provided in the supplement, suggesting potential areas for deeper theoretical investigation.

Summary updated

BibTeX
@inproceedings{schauer2024causal,
  author = {Moritz Schauer and Marcel Wienöbst},
  title = {{Causal Structure Learning With Momentum: Sampling Distributions Over Markov Equivalence Classes}},
  booktitle = {Pgm},
  year = {2024},
}
Figure