  We develop a novel hybrid method for Bayesian network structure learning
called partitioned hybrid greedy search (pHGS), composed of three distinct yet
compatible new algorithms: Partitioned PC (pPC) accelerates skeleton learning
via a divide-and-conquer strategy, $p$-value adjacency thresholding (PATH)
effectively accomplishes parameter tuning with a single execution, and hybrid
greedy initialization (HGI) maximally utilizes constraint-based information to
obtain a high-scoring and well-performing initial graph for greedy search. We
establish structure learning consistency of our algorithms in the large-sample
limit, and empirically validate our methods individually and collectively
through extensive numerical comparisons. The combined merits of pPC and PATH
achieve significant computational reductions compared to the PC algorithm
without sacrificing the accuracy of estimated structures, and our generally
applicable HGI strategy reliably improves the estimation structural accuracy of
popular hybrid algorithms with negligible additional computational expense. Our
empirical results demonstrate the superior empirical performance of pHGS
against many state-of-the-art structure learning algorithms.
