Learning Bayesian Networks with the Saiyan algorithm

Some structure learning algorithms have proven to be effective in reconstructing hypothetical Bayesian Network (BN) graphs from synthetic data. However, in their mission to maximise a scoring function, many become conservative and minimise edges discovered. While simplicity is desired, the output is often a graph that consists of multiple independent graphical fragments or variables that do not enable full propagation of evidence. While this is not a problem in theory, it can be a problem in practice. This paper presents a novel unconventional heuristic local-search structure learning algorithm, called Saiyan, which returns a directed acyclic graph that enables full propagation of evidence. Forcing the algorithm to connect all data variables and to direct all of the edges discovered implies that the additional forced arcs are not expected to be correct at the rate of those identified unrestrictedly, and this evidently has a negative impact on the evaluation score of the discovered graph. Still, based on both synthetic and real-world experiments, the Saiyan algorithm demonstrates competitive performance relative to other state-of-the-art constraint-based, score-based, and hybrid structure learning algorithms