Extendable and Iterative Structure Learning Strategy for Bayesian Networks

Learning the structure of Bayesian networks from a dataset of instances is a fundamental yet computationally intensive task, especially as the number of variables grows. Traditional algorithms require retraining from scratch when new variables are introduced, making them impractical for dynamic or large-scale applications. In this paper, we propose an extendable structure learning strategy that efficiently incorporates a new variable Y into an existing (P-map) Bayesian network graph G over variables X , resulting in an updated P-map graph Ḡ on X = X ∪ Y . By leveraging the information encoded in G, our method significantly reduces computational overhead compared to learning Ḡ from scratch. Empirical evaluations demonstrate runtime reductions of up to 1300× without compromising accuracy. Building on this approach, we introduce a novel iterative paradigm for structure learning over X . Starting with a small subset U ⊂ X , we iteratively add the remaining variables using our extendable algorithm to construct a P-map graph over the full set. This method achieves runtime advantages compared to common algorithms while maintaining similar accuracy. Our contributions provide a scalable solution for Bayesian network structure learning, enabling efficient model updates in real-time and high-dimensional settings.