Linear Polytree Structural Equation Models: Structural Learning and Inverse Correlation Estimation

Over the past three decades, the problem of learning directed graphical models from data has received enormous amount of attention since they provide a compact and flexible way to represent the joint distribution of the data, especially when the associated graph is a directed acyclic graph (DAG). A directed graph is called a DAG if it does not contain directed cycles. DAG models are popular in practice with applications in biology, genetics, machine learning and causal inference (Sachs et al., 2005; Zhang et al., 2013; Koller and Friedman, 2009; Spirtes et al., 2000). There exists an extensive literature on learning the graph structure from data under the assumption that the graph is a DAG. For a summary, see the survey of Drton and Maathuis (2017); Heinze-Deml et al. (2018). Existing approaches generally fall into two categories, constrain-based methods (Spirtes et al., 2000; Pearl, 2009) and score-based methods (Chickering, 2002). Constraint-based methods utilize conditional independence test to determine whether there exists an edge between two nodes and then orient the edges in the graph, such that the resulting graph is compatible with the conditional independencies seen in the data. Score-based methods formulate the structure learning task as optimizing a score function based on the unknown graph and the data. A polytree is a DAG which does not contain any cycles even if the directions of all edges are ignored.