Eliminating Variable Order Instability in Greedy Score-Based Structure Learning

Abstract

Many Bayesian Network structure learning algorithms are unstable in that the learnt graph is sensitive to arbitrary artefacts of the dataset, such as the ordering of columns (i.e., variable order). PC-Stable, developed by \cite{colombo2014order}, 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 suffer from the same issue and that PC-Stable, although less sensitive than most of the score-based algorithms tested, is not completely stable. We also present a solution to score-based greedy hill-climbing that completely eliminates this instability, and provide two implementations: the HC-Stable and Tabu-Stable algorithms, the latter of which learns more accurate graphs than all the well-known algorithms we compared it to.