A Discovery Algorithm for Directed Cyclic Graphs

By Thomas S. Richardson. 1996

Directed acyclic graphs have been used fruitfully to represent causal structures (Pearl 1988). However, in the social sciences and elsewhere models are often used which correspond both causally and statistically to directed graphs with directed cycles (Spirtes 1995). Pearl (1993) discussed predicting the effects of intervention in models of this kind, so-called linear nonrecursive structural equation models. This raises the question of whether it is possible to make inferences about causal structure with cycles, from sample data. In particular do there exist general, informative, feasible and reliable procedures for inferring causal structure from conditional independence relations among variables in a sample generated by an unknown causal structure? In this paper I present a discovery algorithm that is correct in the large sample limit, given commonly (but often implicitly) made plausible assumptions, and which provides information about the existence or non-existence of causal pathways from one variable to another. The algorithm is polynomial on sparse graphs.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

CAM: Causal Additive Models, high-dimensional order search and penalized regression (2013, background): “Finally, it would be very interesting to extend (sparse) permutation search to (possibly nonidentifiable) models with hidden variables [7, 11, 23, 34] or with graph structures allowing for cycles [19, 20, 30, 33].”
Order-independent constraint-based causal structure learning (2012, methodology): “Section 4 introduces modiﬁcations of the PC-algorithm (and hence also of the (R)FCI-and CCD-algorithms) that remove part or all of the order-dependence.”
Causal feature learning: an overview (2017, unknown): “Like the majority of work in causal inference and discovery—notable exceptions being (Richardson 1996; Mooij et al. 2011; Lacerda et al. 2012; Hyttinen et al. 2012, 2014)—CFL assumes that the microvariable system is acyclic: in our toy example, hue has causal influence on eda, but we assumed (quite…”
Comorbidity: A network perspective (2010, background): “The theory of cyclic graphical models is difficult and underdeveloped, and for binary variables no adequate search procedure is available, but the target article does not engage what is known (e.g., Lacerda et al. 2008; Pearl & Dechter 1996; Richardson 1996).”
Learning the Structure of Linear Latent Variable Models (2006, methodology): “Richardson (1996) has developed a consistent constraint based search for cyclic graphical models of linear systems, and our procedures for identifying measurement models can be combined with it to search for such structure.”
SAM: Structural Agnostic Model, Causal Discovery and Penalized Adversarial Learning (2018, result): “SAM performs better than most methods, including CCD, which was speciﬁcally designed to address causal relationships in cyclic graphs, like SAM.”
On Causal Discovery with Cyclic Additive Noise Models (2011, background): “The basic assumption made in [7] is the so-called Global Directed Markov Condition , which relates (conditional) independences between the variables with the structure of the causal graph.”
Modeling Discrete Interventional Data using Directed Cyclic Graphical Models (2009, methodology): “…properties resulting from a graphical interpretation of these potentials (§4), modeling the effects of interventions under this representation (§5), interpreting the model and interventions in the model in terms of a data generating process involving feedback (§6), inference and…”
D’ya Like DAGs? A Survey on Structure Learning and Causal Discovery (2021, background): “, CCD [196], backshift [204], CCI [225]), there are relatively few such continuous optimization approaches.”
Causal Learning for Partially Observed Stochastic Dynamical Systems (2018, background): “Note that the same is true for the directed (cyclic) graphs with no loops considered by Richardson (1996, 1997) in another context.”
Structural Agnostic Modeling: Adversarial Learning of Causal Graphs (2018, methodology): “DAGL1 (Fu and Zhou, 2013), the LiNGAM algorithm (Shimizu et al., 2006) and the causal additive model CAM (Peters et al., 2014). When considering non-acyclic causal structures, we also compare to CCD (Richardson, 1996). Other methods such as BackShift (Rothenhausler et al.,¨ 2015), which require obse”
Structure Learning in Graphical Modeling (2016, background): “…structural equation modeling (Spirtes et al., 2000; Mooij & Heskes, 2013) and conditional independence can then be exploited in structure learning (Richardson, 1996), these models can generally not be described using solely conditional independence; see Example 3.6 and Appendix A in Drton (2009).”