Causal Discovery for Max-Linear Bayesian Networks

Directed acyclic graphical models, sometimes called Bayesian networks, are of critical importance in modern data science and statistics through their applications to causality and probabilistic inference. These statistical models use directed acyclic graphs (DAGs) to represent causal relationships between random variables and are often specified by a system of structural equations which is defined using the associated DAG. A fundamental related problem is that of causal discovery where one seeks to determine the causal relationships, i.e. the underlying DAG, from a given empirical distribution. While this problem is statistical in nature, many classical causal discovery algorithms which are used today are fundamentally combinatorial due to a strong link between conditional independence of the observed random variables and the structure of the underlying DAG. We will then show how the first causal discovery algorithm, typically known as the PC algorithm, fails to accurately reconstruct the true DAG if the observed data is generated by a max-linear Bayseian network due to the differences in the combinatorial criteria which govern conditional independence in these models. Lastly, we will discuss how the PC algorithm can be changed to yield a new algorithm which reconstructs the true underyling graph when the input data is generated by a max-linear Bayesian network.