Shield-Induced Partitioning for Parallel Bayesian Network Structure Learning

Bayesian network structure learning is computationally challenging because conditional-independence testing and graph search scale poorly with the number of variables. We introduce Shield-Induced Partitioning (SIP), a recursive framework for scalable Bayesian network structure learning. SIP decomposes the variable set into two main blocks and a shield, then separates the shield into a conditioning component that d-separates the blocks and a residual component used during merging. This decomposition enables independent learning on smaller local domains of the form ${\mathbf{A}}_i\cup {\mathbf{C}}_0$, followed by a merge step that recovers the remaining shield-mediated dependencies. We provide a seed-and-expand procedure for discovering SIPs and show that the resulting recursive learning procedure recovers the target P-map class under standard Markov and faithfulness assumptions. Experiments on discrete Bayesian-network benchmarks show that an optimized implementation achieves substantial runtime improvements over a broad set of structure-learning baselines while maintaining competitive structural accuracy. These results suggest that shield-induced recursive partitioning is an effective principle for scalable Bayesian network structure learning.