Combinatorial Methods for Learning Max-Linear Bayesian Networks

• Applicants: Dr. Carlos Améndola Cerón; Benjamin Hollering, Ph.D.
• Subject Area: Mathematics
• Term: since 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 539875257

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. In this proposal, we focus on a relatively new family of directed graphical models which are called max-linear Bayesian networks (MLBN). These models excel at modeling cascading failure and have seen many applications in areas where this is common such as financial risk and water contamination. Unlike many other classical families of graphical models, they are not faithful to the well-known d-separation criterion and thus they exhibit very different conditional independence structures. This means that many standard algorithms for learning graphical models from data cannot be applied to data which is generated by a max-linear Bayesian network. While MLBNs are not faithful to d-separation, Amendola et. al. recently developed a new graphical separation criterion, called *-separation which characterizes conditional independence in these models. The major goal of our proposal is to develop combinatorial algorithms which reconstruct a directed acyclic graph which best represents data generated by a max-linear Bayesian network which only require faithfulness to *-separation. Many of the classical algorithms which were designed for d-separation are built on combinatorial results which characterize when two graphs are Markov equivalent (meaning they satisfy the same conditional independence statements), which type of conditioning sets are necessary for a d-separation to hold, and the manner in which edge deletions and additions affect the CI statements exhibited by the graph. By developing analogous results for the new *-separation criterion, we will be able to design algorithms which are able to reconstruct a Markov equivalence class (MEC) of MLBNs from data. With such an algorithm for recovering MECs of MLBNs, a natural next step for causal inference is to understand which graph in the equivalence class encodes the correct causal structure. This is typically done with interventions where one collects additional data by affecting a single random variable in the model. For graphs which are faithful to d-separation, it is known how interventions break up the MECs but these results do not hold for MLBNs. The next major goal of our proposal will be to characterize the so-called interventional MECs for MLBNs and from that deduce how many interventions are required to determine the true causal structure.

• DFG Programme: Priority Programmes
• Subproject of: SPP 2458: Combinatorial Synergies