# Novel Ordering-based Approaches for Causal Structure Learning in the Presence of Unobserved Variables

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 54 references that are in the map.
- First posted on arXiv 14 Aug 2022.

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

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [DAG-GNN: DAG Structure Learning with Graph Neural Networks](https://mlsanity.com/paper/1904.10098/) (2019)
- [Gradient-Based Neural DAG Learning](https://mlsanity.com/paper/1906.02226/) (2019)
- [Learning Sparse Nonparametric DAGs](https://mlsanity.com/paper/1909.13189/) (2019)
- [Causal Discovery with Reinforcement Learning](https://mlsanity.com/paper/1906.04477/) (2019)
- [Score matching enables causal discovery of nonlinear additive noise models](https://mlsanity.com/paper/2203.04413/) (2022)
- [Masked Gradient-Based Causal Structure Learning](https://mlsanity.com/paper/1910.08527/) (2019)
- [Ordering-Based Causal Discovery with Reinforcement Learning](https://mlsanity.com/paper/2105.06631/) (2021)
- [Learning Sparse Causal Models is not NP-hard](https://mlsanity.com/paper/1309.6824/) (2013)
- [High-dimensional consistency in score-based and hybrid structure learning](https://mlsanity.com/paper/1507.02608/) (2015)
- [Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias](https://mlsanity.com/paper/2110.12036/) (2021)
- [Ordering-Based Causal Structure Learning in the Presence of Latent Variables](https://mlsanity.com/paper/1910.09014/) (2019)
- [A Recursive Markov Boundary-Based Approach to Causal Structure Learning](https://mlsanity.com/paper/2010.04992/) (2020)
- [Learning Bayesian Networks in the Presence of Structural Side Information](https://mlsanity.com/paper/2112.10884/) (2021)
- [Direct Learning with Guarantees of the Difference DAG Between Structural Equation Models](https://mlsanity.com/paper/1906.12024/) (2019)
- [Accelerating Recursive Partition-Based Causal Structure Learning](https://mlsanity.com/paper/2102.11545/) (2021)

## Built on by (most cited first, 10 of 10)

- [Recursive Causal Discovery](https://mlsanity.com/paper/2403.09300/) (2024)
- [Local Causal Structure Learning in the Presence of Latent Variables](https://mlsanity.com/paper/2405.16225/) (2024)
- [Efficient Ensemble Conditional Independence Test Framework for Causal Discovery](https://mlsanity.com/paper/2509.21021/) (2025)
- [s-ID: Causal Effect Identification in a Sub-Population](https://mlsanity.com/paper/2309.02281/) (2023)
- [QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs](https://mlsanity.com/paper/2410.23155/) (2024)
- [Consistency evaluation of benchmarks used for causal discovery](https://mlsanity.com/paper/2606.01789/) (2026)
- [Learning Linear Gaussian Polytree Models with Interventions](https://mlsanity.com/paper/2311.04636/) (2023)
- [Exact discovery is polynomial for certain sparse causal Bayesian networks](https://mlsanity.com/paper/2406.15012/) (2024)
- [A Recursive Decomposition Framework for Causal Structure Learning in the Presence of Latent Variables](https://mlsanity.com/paper/2605.10651/) (2026)
- [Decoupled Causal Discovery](https://mlsanity.com/paper/2609.23535/) (2026)

## Abstract (arXiv)

We propose ordering-based approaches for learning the maximal ancestral graph (MAG) of a structural equation model (SEM) up to its Markov equivalence class (MEC) in the presence of unobserved variables. Existing ordering-based methods in the literature recover a graph through learning a causal order (c-order). We advocate for a novel order called removable order (r-order) as they are advantageous over c-orders for structure learning. This is because r-orders are the minimizers of an appropriately defined optimization problem that could be either solved exactly (using a reinforcement learning approach) or approximately (using a hill-climbing search). Moreover, the r-orders (unlike c-orders) are invariant among all the graphs in a MEC and include c-orders as a subset. Given that set of r-orders is often significantly larger than the set of c-orders, it is easier for the optimization problem to find an r-order instead of a c-order. We evaluate the performance and the scalability of our proposed approaches on both real-world and randomly generated networks.