Divide-and-Conquer Strategy for Large-Scale Dynamic Bayesian Network
  Structure Learning
Hui Ouyang Cheng Chen Ke Tang
Dynamic Bayesian Networks (DBNs), renowned for their interpretability, have
become increasingly vital in representing complex stochastic processes in
various domains such as gene expression analysis, healthcare, and traffic
prediction. Structure learning of DBNs from data is challenging, particularly
for datasets with thousands of variables. Most current algorithms for DBN
structure learning are adaptations from those used in static Bayesian Networks
(BNs), and are typically focused on small-scale problems. In order to solve
large-scale problems while taking full advantage of existing algorithms, this
paper introduces a novel divide-and-conquer strategy, originally developed for
static BNs, and adapts it for large-scale DBN structure learning. In this work,
we specifically concentrate on 2 Time-sliced Bayesian Networks (2-TBNs), a
special class of DBNs. Furthermore, we leverage the prior knowledge of 2-TBNs
to enhance the performance of the strategy we introduce. Our approach
significantly improves the scalability and accuracy of 2-TBN structure
learning. Experimental results demonstrate the effectiveness of our method,
showing substantial improvements over existing algorithms in both computational
efficiency and structure learning accuracy. On problem instances with more than
1,000 variables, our approach improves two accuracy metrics by 74.45% and
110.94% on average , respectively, while reducing runtime by 93.65% on average.