mlsanityData to 7 Oct 2026

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

arXiv 2310.17679 ↗First posted 26 Oct 2023cs.LG cs.AI stat.MEcited by 38

Not on the map. Why?

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.

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

Builds on

5 of 30 references.

References · 5

  1. 2020On the Role of Sparsity and DAG Constraints for Learning Linear DAGscited by 186
  2. 2022DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterizationcited by 135
  3. 2022Greedy Relaxations of the Sparsest Permutation Algorithmcited by 63
  4. 2013A Transformational Characterization of Equivalent Bayesian Network Structurescited by 41
  5. 2021Improving Accuracy of Permutation DAG Search using Best Order Score Searchcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 10; 2025: 10; 2026: 18.

38 papers.

Sort:

By area:

  1. 2025Unitless Unrestricted Markov-Consistent SCM Generation: Better Benchmark Datasets for Causal Discoverycited by 7
  2. 2024Better Simulations for Validating Causal Discovery with the DAG-Adaptation of the Onion Methodcited by 6
  3. 2025Latent Variable Causal Discovery under Selection Biascited by 6
  4. 2024Are you doing better than random guessing? A call for using negative controls when evaluating causal discovery algorithmscited by 5
  5. 2024ProDAG: Projected Variational Inference for Directed Acyclic Graphscited by 4
  6. 2025Embracing Discrete Search: A Reasonable Approach to Causal Structure Learningcited by 4
  7. 2026Arrow: A Foundation Model for Causal Discoverycited by 4
  8. 2025On Different Notions of Redundancy in Conditional-Independence-Based Discovery of Graphical Modelscited by 3
  9. 2025Efficient Latent Variable Causal Discovery: Combining Score Search and Targeted Testingcited by 2
  10. 2025Higher-Order Causal Structure Learning with Additive Modelscited by 2
  11. 2026Dynamic Expert-Guided Model Averaging for Causal Discoverycited by 2
  12. 2026Causal Ensemble Agent: Hierarchical Causal Discovery with LLM-guided Expert Reweightingcited by 2
26 more
  1. 2024Algorithmic Identification of Essential Exogenous Nodes for Causal Sufficiency in Brain Networkscited by 1
  2. 2024ExDAG: an MIQP Algorithm for Learning DAGscited by 1
  3. 2024Choosing DAG Models Using Markov and Minimal Edge Count in the Absence of Ground Truthcited by 1
  4. 2024QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMscited by 1
  5. 2025Scalable Causal Discovery from Recursive Nonlinear Data via Truncated Basis Function Scores and Testscited by 1
  6. 2025Causal-Aware Tabular GANs with Reinforcement Learningcited by 1
  7. 2026Counterfactual Fairness with Graph Uncertaintycited by 1
  8. 2026Leveraging Large Language Models for Causal Discovery: a Constraint-based, Argumentation-driven Approachcited by 1
  9. 2026Fourier Feature Methods for Nonlinear Causal Discovery: FFML Scoring, TRFF Scoring, and FFCI Testing in Mixed Datacited by 1
  10. 2026CauTion: Knowing When to Trust LLMs for Ensemble Causal Discoverycited by 1
  11. 2024Membership Testing in Markov Equivalence Classes via Independence Query Oraclescited by 0
  12. 2024ExDBN: Learning Dynamic Bayesian Networks using Extended Mixed-Integer Programming Formulationscited by 0
  13. 2024Retrieving Classes of Causal Orders with Inconsistent Knowledge Basescited by 0
  14. 2025An extensive simulation study evaluating the interaction of resampling techniques across multiple causal discovery contextscited by 0
  15. 2025Differentiable Structure Learning and Causal Discovery for General Binary Datacited by 0
  16. 2026Causal Preference Elicitationcited by 0
  17. 2026Effect-Level Validation for Causal Discoverycited by 0
  18. 2026Learning Causal Structure of Time Series using Best Order Score Searchcited by 0
  19. 2026Can Causal Discovery Algorithms Help in Generating Legal Arguments?cited by 0
  20. 2026PACER: Acyclic Causal Discovery from Large-Scale Interventional Datacited by 0
  21. 2026Stable Causal Discovery via Directed Acyclic Graph Aggregationcited by 0
  22. 2026Causal Modeling of Selection in Evolutioncited by 0
  23. 2026KG-SoftMAP: Soft Knowledge-Graph Priors for Bayesian Network Structure Learning from Sparse Discrete Datacited by 0
  24. 2026Causal Discovery in the Era of Agentscited by 0
  25. 2026SVI-DAG: A Structured Variational Inference Approach to Bayesian Causal Discoverycited by 0
  26. 2026LLM as Detector: An In-context Learning Approach for Tabular Anomaly Detectioncited by 0