Causal structure learning in directed, possibly cyclic, graphical models

Abstract We consider the problem of learning a directed graph <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msup> <m:mrow> <m:mi>G</m:mi> </m:mrow> <m:mrow> <m:mo>⋆</m:mo> </m:mrow> </m:msup> </m:math> {G}^{\star } from observational data. We assume that the distribution that gives rise to the samples is Markov and faithful to the graph <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msup> <m:mrow> <m:mi>G</m:mi> </m:mrow> <m:mrow> <m:mo>⋆</m:mo> </m:mrow> </m:msup> </m:math> {G}^{\star } and that there are no unobserved variables. We do not rely on any further assumptions regarding the graph or the distribution of the variables. Particularly, we allow for directed cycles in <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msup> <m:mrow> <m:mi>G</m:mi> </m:mrow> <m:mrow> <m:mo>⋆</m:mo> </m:mrow> </m:msup> </m:math> {G}^{\star } and work in the fully nonparametric setting. Given the set of conditional independence statements satisfied by the distribution, we aim to find a directed graph, which satisfies the same <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>d</m:mi> </m:math> d -separation statements as <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msup> <m:mrow> <m:mi>G</m:mi> </m:mrow> <m:mrow> <m:mo>⋆</m:mo> </m:mrow> </m:msup> </m:math> {G}^{\star } . We propose a hybrid approach consisting of two steps. We first find a partially ordered partition of the vertices of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msup> <m:mrow> <m:mi>G</m:mi> </m:mrow> <m:mrow> <m:mo>⋆</m:mo> </m:mrow> </m:msup> </m:math> {G}^{\star } by optimizing a certain score in a greedy fashion. We prove that any optimal partition uniquely characterizes the Markov equivalence class of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msup> <m:mrow> <m:mi>G</m:mi> </m:mrow> <m:mrow> <m:mo>⋆</m:mo> </m:mrow> </m:msup> </m:math> {G}^{\star } . Given an optimal partition, we propose an algorithm for constructing a graph in the Markov equivalence class of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msup> <m:mrow> <m:mi>G</m:mi> </m:mrow> <m:mrow> <m:mo>⋆</m:mo> </m:mrow> </m:msup> </m:math> {G}^{\star } whose strongly connected components correspond to the elements of the partition, and which are partially ordered according to the partial order of the partition. Our algorithm comes in two versions – one that is provably correct and another one that performs fast in practice.