Fast Scalable and Accurate Discovery of DAGs Using the Best Order Score
  Search and Grow-Shrink Trees
Bryan Andrews Joseph Ramsey Ruben Sanchez-Romero Jazmin Camchong Erich Kummerfeld
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.