# Fast Scalable and Accurate Discovery of DAGs Using the Best Order Score Search and Grow-Shrink Trees

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 30 references that are in the map.
- First posted on arXiv 26 Oct 2023.

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

- [On the Role of Sparsity and DAG Constraints for Learning Linear DAGs](https://mlsanity.com/paper/2006.10201/) (2020)
- [DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization](https://mlsanity.com/paper/2209.08037/) (2022)
- [Greedy Relaxations of the Sparsest Permutation Algorithm](https://mlsanity.com/paper/2206.05421/) (2022)
- [A Transformational Characterization of Equivalent Bayesian Network Structures](https://mlsanity.com/paper/1302.4938/) (2013)
- [Improving Accuracy of Permutation DAG Search using Best Order Score Search](https://mlsanity.com/paper/2108.10141/) (2021)

## Built on by (most cited first, 30 of 38)

- [Unitless Unrestricted Markov-Consistent SCM Generation: Better Benchmark Datasets for Causal Discovery](https://mlsanity.com/paper/2503.17037/) (2025)
- [Latent Variable Causal Discovery under Selection Bias](https://mlsanity.com/paper/2512.11219/) (2025)
- [Better Simulations for Validating Causal Discovery with the DAG-Adaptation of the Onion Method](https://mlsanity.com/paper/2405.13100/) (2024)
- [Are you doing better than random guessing? A call for using negative controls when evaluating causal discovery algorithms](https://mlsanity.com/paper/2412.10039/) (2024)
- [Arrow: A Foundation Model for Causal Discovery](https://mlsanity.com/paper/2605.07204/) (2026)
- [ProDAG: Projected Variational Inference for Directed Acyclic Graphs](https://mlsanity.com/paper/2405.15167/) (2024)
- [Embracing Discrete Search: A Reasonable Approach to Causal Structure Learning](https://mlsanity.com/paper/2510.04970/) (2025)
- [On Different Notions of Redundancy in Conditional-Independence-Based Discovery of Graphical Models](https://mlsanity.com/paper/2502.08531/) (2025)
- [Efficient Latent Variable Causal Discovery: Combining Score Search and Targeted Testing](https://mlsanity.com/paper/2510.04263/) (2025)
- [Higher-Order Causal Structure Learning with Additive Models](https://mlsanity.com/paper/2511.03831/) (2025)
- [Dynamic Expert-Guided Model Averaging for Causal Discovery](https://mlsanity.com/paper/2601.16715/) (2026)
- [Causal Ensemble Agent: Hierarchical Causal Discovery with LLM-guided Expert Reweighting](https://mlsanity.com/paper/2606.10607/) (2026)
- [Algorithmic Identification of Essential Exogenous Nodes for Causal Sufficiency in Brain Networks](https://mlsanity.com/paper/2403.05407/) (2024)
- [ExDAG: an MIQP Algorithm for Learning DAGs](https://mlsanity.com/paper/2406.15229/) (2024)
- [Choosing DAG Models Using Markov and Minimal Edge Count in the Absence of Ground Truth](https://mlsanity.com/paper/2409.20187/) (2024)
- [QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs](https://mlsanity.com/paper/2410.23155/) (2024)
- [Scalable Causal Discovery from Recursive Nonlinear Data via Truncated Basis Function Scores and Tests](https://mlsanity.com/paper/2510.04276/) (2025)
- [Causal-Aware Tabular GANs with Reinforcement Learning](https://mlsanity.com/paper/2510.24046/) (2025)
- [Counterfactual Fairness with Graph Uncertainty](https://mlsanity.com/paper/2601.03203/) (2026)
- [Effect-Level Validation for Causal Discovery](https://mlsanity.com/paper/2602.08340/) (2026)
- [Leveraging Large Language Models for Causal Discovery: a Constraint-based, Argumentation-driven Approach](https://mlsanity.com/paper/2602.16481/) (2026)
- [Fourier Feature Methods for Nonlinear Causal Discovery: FFML Scoring, TRFF Scoring, and FFCI Testing in Mixed Data](https://mlsanity.com/paper/2605.05743/) (2026)
- [CauTion: Knowing When to Trust LLMs for Ensemble Causal Discovery](https://mlsanity.com/paper/2606.03602/) (2026)
- [KG-SoftMAP: Soft Knowledge-Graph Priors for Bayesian Network Structure Learning from Sparse Discrete Data](https://mlsanity.com/paper/2606.10358/) (2026)
- [Membership Testing in Markov Equivalence Classes via Independence Query Oracles](https://mlsanity.com/paper/2403.05759/) (2024)
- [ExDBN: Learning Dynamic Bayesian Networks using Extended Mixed-Integer Programming Formulations](https://mlsanity.com/paper/2410.16100/) (2024)
- [Retrieving Classes of Causal Orders with Inconsistent Knowledge Bases](https://mlsanity.com/paper/2412.14019/) (2024)
- [An extensive simulation study evaluating the interaction of resampling techniques across multiple causal discovery contexts](https://mlsanity.com/paper/2503.15436/) (2025)
- [Differentiable Structure Learning and Causal Discovery for General Binary Data](https://mlsanity.com/paper/2509.21658/) (2025)
- [Causal Preference Elicitation](https://mlsanity.com/paper/2602.01483/) (2026)

## Abstract (arXiv)

Learning graphical conditional independence structures is an important machine learning problem and a cornerstone of causal discovery. However, the accuracy and execution time of learning algorithms generally struggle to scale to problems with hundreds of highly connected variables -- for instance, recovering brain networks from fMRI data. We introduce the best order score search (BOSS) and grow-shrink trees (GSTs) for learning directed acyclic graphs (DAGs) in this paradigm. BOSS greedily searches over permutations of variables, using GSTs to construct and score DAGs from permutations. GSTs efficiently cache scores to eliminate redundant calculations. BOSS achieves state-of-the-art performance in accuracy and execution time, comparing favorably to a variety of combinatorial and gradient-based learning algorithms under a broad range of conditions. To demonstrate its practicality, we apply BOSS to two sets of resting-state fMRI data: simulated data with pseudo-empirical noise distributions derived from randomized empirical fMRI cortical signals and clinical data from 3T fMRI scans processed into cortical parcels. BOSS is available for use within the TETRAD project which includes Python and R wrappers.