Learning Directed Acyclic Graphs from Partial Orderings

Directed acyclic graphs (DAGs) are widely used to capture causal relationships among components of complex systems (Spirtes et al., 2001; Pearl, 2009; Maathuis et al., 2018). They also form a foundation for causal discovery and inference (Pearl, 2009). Probabilistic graphical models defined on DAGs, known as Bayesian networks (Pearl, 2009), have thus found broad applications in various scientific disciplines, from biology (Markowetz and Spang, 2007; Zhang et al., 2013) and social sciences (Gupta and Kim, 2008), to knowledge representation and machine learning (Heckerman, 1997). However, learning the structure of DAGs from observational data is very challenging due to at least two major factors: First, it may not be possible to infer the direction of edges from observational data alone. In fact, unless the model is identifiable (see, e.g., Peters et al., 2014a), observational data only reveal the structure of the Markov equivalent class of DAGs (Maathuis et al., 2018), captured by a complete partially directed acyclic graph (CPDAG) (Andersson et al., 1997). The second reason is computational--learning DAGs from observational data is an NPcomplete problem (Chickering, 1996). In fact, while a few polynomial time algorithms have been proposed for special cases, including sparse graphs (Kalisch and Bühlmann, 2007) or identifiable models (Chen et al., 2019; Ghoshal and Honorio, 2018; Peters et al., 2014b; Wang and Drton, 2020; Shimizu et al., 2006; Yu et al., 2023), existing general-purpose algorithms are not scalable to problems involving many variables. In spite of the many challenges of learning DAGs in general settings, the problem becomes very manageable if a valid causal ordering among variables is known (Shojaie and Michailidis, 2010). In a valid causal ordering for a DAG G with node set V, any node j can appear before another node k (denoted j k) only if there is no directed path from k to j.