# Fast Causal Orientation Learning in Directed Acyclic Graphs

arXiv: https://arxiv.org/abs/2205.13919 · HTML: https://mlsanity.com/paper/2205.13919/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 33 references that are in the map.
- First posted on arXiv 27 May 2022.

## Builds on (most cited first, 13 of 13)

- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Permutation-based Causal Inference Algorithms with Interventions](https://mlsanity.com/paper/1705.10220/) (2017)
- [Learning Causal Graphs with Small Interventions](https://mlsanity.com/paper/1511.00041/) (2015)
- [ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery](https://mlsanity.com/paper/1902.10347/) (2019)
- [Cost-Optimal Learning of Causal Graphs](https://mlsanity.com/paper/1703.02645/) (2017)
- [A Transformational Characterization of Equivalent Bayesian Network Structures](https://mlsanity.com/paper/1302.4938/) (2013)
- [Budgeted Experiment Design for Causal Structure Learning](https://mlsanity.com/paper/1709.03625/) (2017)
- [An Algorithm for Deciding if a Set of Observed Independencies Has a Causal Explanation](https://mlsanity.com/paper/1303.5435/) (2013)
- [LazyIter: A Fast Algorithm for Counting Markov Equivalent DAGs and Designing Experiments](https://mlsanity.com/paper/2006.09670/) (2020)
- [Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications](https://mlsanity.com/paper/2205.02654/) (2022)
- [Counting and Sampling from Markov Equivalent DAGs Using Clique Trees](https://mlsanity.com/paper/1802.01239/) (2018)
- [Formulas for Counting the Sizes of Markov Equivalence Classes of Directed Acyclic Graphs](https://mlsanity.com/paper/1610.07921/) (2016)
- [Structure Learning of Linear Gaussian Structural Equation Models with Weak Edges](https://mlsanity.com/paper/1707.07560/) (2017)

## Abstract (arXiv)

Causal relationships among a set of variables are commonly represented by a directed acyclic graph. The orientations of some edges in the causal DAG can be discovered from observational/interventional data. Further edges can be oriented by iteratively applying so-called Meek rules. Inferring edges' orientations from some previously oriented edges, which we call Causal Orientation Learning (COL), is a common problem in various causal discovery tasks. In these tasks, it is often required to solve multiple COL problems and therefore applying Meek rules could be time-consuming. Motivated by Meek rules, we introduce Meek functions that can be utilized in solving COL problems. In particular, we show that these functions have some desirable properties, enabling us to speed up the process of applying Meek rules. In particular, we propose a dynamic programming (DP) based method to apply Meek functions. Moreover, based on the proposed DP method, we present a lower bound on the number of edges that can be oriented as a result of intervention. We also propose a method to check whether some oriented edges belong to a causal DAG. Experimental results show that the proposed methods can outperform previous work in several causal discovery tasks in terms of running-time.