Estimating large causal polytrees from small samples

The problem of estimating causal structure from data is a central problem of causal inference. One of the earliest attempts at reconstructing causal structures, under the assumption that the underlying graph is a tree (such structures are called causal polytrees), was due to Rebane and Pearl [28], who repurposed an old algorithm of Chow and Liu [8] to give a method for consistent estimation of causal polytrees (a term that was coined in [28]). The Rebane-Pearl approach has several drawbacks in the modern context. First, it is based on mutual information, just like the original Chow-Liu algorithm. Estimating mutual information from data is notoriously time-consuming (see [6] for some numbers), and moreover, requires special assumptions on the distribution of the data. Second, it is not clear if the algorithm works in modern problems where the number of variables is far greater than the sample size.