Markov equivalence of max-linear Bayesian networks

Carlos Améndola, Benjamin Hollering, Seth Sullivant, Ngoc TranUAI 2021

Abstract

Max-Linear Bayesian Networks (MLBNs) are specialized graphical models used to represent extreme value dependencies, such as cascading failures in financial or environmental systems. While MLBNs are governed by a more restrictive conditional independence criterion known as $*$-separation, this research demonstrates that their Markov equivalence classes are identical to those of standard Gaussian networks governed by $d$-separation. This finding bridges the gap between extreme value theory and classical causal discovery, confirming that the identifiability of these models remains consistent with established graphical modeling frameworks.

Introduction

In causal inference, Directed Acyclic Graphs (DAGs) serve as the primary tool for representing structural relationships between variables. A central challenge in structure learning is that data often cannot distinguish between different DAGs that imply the same set of conditional independence (CI) statements. Such graphs form a Markov equivalence class. In standard linear Gaussian models, CI is determined by the $d$-separation criterion. However, Max-Linear Bayesian Networks (MLBNs), which model outcomes as the maximum of weighted inputs, follow a stronger criterion called $*$-separation.

The Separation Paradox

Because $*$-separation yields a strictly larger set of CI statements than $d$-separation for any given graph, it was long suspected that MLBNs might possess more refined equivalence classes, potentially allowing for better model identifiability. This paper investigates this "Equivalence Paradox."

Figure 2: Graphical configurations illustrating the components of *-separation.

As shown in Figure 2, $*$-separation considers specific path structures that go beyond simple $d$-separation. Despite these differences at the individual graph level, the authors prove in Theorem 3.4 that the groupings of graphs into equivalence classes remain unchanged: $G \sim_d H$ if and only if $G \sim_* H$. This result is significant because it implies that existing algorithms for learning Gaussian DAGs can be directly applied to extreme value data without loss of generality.

Tropical Geometry and the Trek Rule

To prove these results, the authors employ tropical geometry, treating the "max" operator as addition in a max-times semiring. They derive a "Tropical Trek Rule" (Theorem 4.3), which allows for the calculation of a tropical covariance matrix ($\Sigma^{trop}$) based on max-weighted treks between nodes.

Figure 6: Construction of the graph $G^*_K$ used to analyze tropical rank drops under d-separation.

A key theoretical contribution is the link between graph topology and matrix algebra. Theorem 5.2 establishes that if a set of nodes $K$ $d$-separates two sets $I$ and $J$, the tropical rank of the sub-matrix $\Sigma^{trop}_{I,J}$ is constrained by the size of $K$. Figure 6 illustrates the graphical transformations used to prove these rank constraints, showing how $d$-separation in $G$ translates to structural properties in an augmented graph $G^*_K$.

Conclusion and Future Directions

The finding that MLBNs share Markov equivalence classes with Gaussian networks simplifies the landscape for causal discovery in extreme value statistics. However, challenges remain. MLBNs are typically non-faithful, meaning specific parameter choices can create "accidental" independencies. Furthermore, while $\Sigma^{trop}$ is a powerful theoretical construct, consistent estimators for it are still lacking. Future research will likely focus on the tail-dependence matrix as a more practical alternative for empirical structure learning.

Summary updated

BibTeX
@inproceedings{amendola2021markov,
  author = {Carlos Améndola and Benjamin Hollering and Seth Sullivant and Ngoc Tran},
  title = {{Markov equivalence of max-linear Bayesian networks}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
}
Figure