Efficient Bayesian Network Structure Learning with Tsetlin Machine

Constraint-based Bayesian network structure learning relies on conditional independence (CI) testing. However, as the number of variables increases, the number of possible conditioning sets grows combinatorially, thereby making CI testing computationally expensive and rendering it difficult to scale up to large networks. We propose Weighted Tsetlin Machine-Bayesian Network learning (WTM-BN), a method that makes use of a WTM to reduce the search space. For each target variable, a WTM is trained, and its clauses are utilised to score the relevance of every other variable. A relative-drop cutoff is thereafter applied so as to select a reduced candidate set for CI testing. The resulting skeleton is oriented with the help of collider detection and Meek's rules, so as to obtain a Completed Partially Directed Acyclic Graph (CPDAG). Across five Bayesian networks from the bnlearn benchmark and eight real-world datasets, WTM-BN matches or comes close to the accuracy of state-of-the-art methods, while achieving substantial reduction in runtime. These results demonstrate that WTM-BN offers a favourable accuracy–runtime trade-off for constraint-based Bayesian network structure learning.