Stable structure learning with HC-Stable and Tabu-Stable algorithms
Neville Kenneth Kitson, Anthony Costa Constantinou · International Journal of Approximate Reasoning · 2025
Many Bayesian Network structure learning algorithms are unstable, with the learned graph sensitive to arbitrary dataset artifacts, such as the ordering of columns (i.e., variable order). PC-Stable [1] attempts to address this issue for the widely-used PC algorithm, prompting researchers to use the ‘stable’ version instead. However, this problem seems to have been overlooked for score-based algorithms. In this study, we show that some widely-used score-based algorithms, as well as hybrid and constraint-based algorithms, including PC-Stable, suffer from the same issue. We propose a novel solution for score-based greedy hill-climbing that eliminates instability by determining a stable node order, leading to consistent results regardless of variable ordering. The new Tabu-Stable algorithms achieve the highest overall performance in terms of mean BIC score, log-likelihood, and structural accuracy across networks. These results highlight the importance of addressing instability in structure learning and provide a robust and practical approach for future applications. This paper extends the scope and impact of our previous work presented at Probabilistic Graphical Models 2024 [2] by incorporating continuous variables, implementing new stable orders that improve performance further, and demonstrating that the approach remains effective in the presence of sampling noise. The implementations, along with usage instructions, are freely available on GitHub at https://github.com/causal-iq/discovery .