An efficient Bayesian network structure learning algorithm in the presence of deterministic relations

Faithfulness is one of the main hypotheses on which rely most Bayesian network (BN) structure learning algorithms. When some random variables are deterministically determined by others, faithfulness is ruled out and classical learning algorithms fail to discover many dependences between variables, hence producing incorrect BNs. Even state-of-the-art algorithms dedicated to learning with deterministic variables prove to be inefficient to discover many dependences/independences. For critical applications, e.g., in nuclear safety, such failure is a serious issue. This paper introduces a new hybrid algorithm, combining a constraint-based approach with a greedy search, that includes specific rules dedicated to deterministic nodes that significantly reduce the incorrect learning. Experiments show that our method significantly outperforms state-of-the-art algorithms.