Greedy causal structure learning of maximal arid graphs

Abstract

Causal knowledge is often modelled in directed acyclic graphs (DAGs) where an directed edge between variables, like A → B, indicates that one (A) influences another (B). Many algorithms attempt the difficult task of finding such DAG models given only data – causal discovery – though fewer attempt to do it in the presence of unmeasured confounding variables. To represent a confounder between A and B, we can use a bidirected edge: A ↔ B. This gives us acyclic directed mixed graphs (ADMGs). We develop three algorithms that are variants of greedyBAP, a causal discovery algorithm that greedily searches through the space of bow-free acyclic path diagrams (BAPs) which are acyclic ADMGs with no bows (variable pairs with both a directed and bidirected edge). The modified algorithms restrict the search space from BAPs to arid graphs, that are everywhere identifiable, and maximal arid graphs, which allow each ADMG to map to a unique nested Markov equivalent arid graph. Because these arid models are smooth, the asymptotic results of the BIC model score justifying its use on graphical models holds for them. This is not the case for BAPs or unmeasured variable models in general. However, we do not find empirical evidence of improved performance of these algorithms over greedyBAPs in our simulation studies, so we conclude that they offer little to no advantage in practice.