  This paper builds on recent developments in Bayesian network (BN) structure
learning under the controversial assumption that the input variables are
dependent. This assumption can be viewed as a learning constraint geared
towards cases where the input variables are known or assumed to be dependent.
It addresses the problem of learning multiple disjoint subgraphs that do not
enable full propagation of evidence. This problem is highly prevalent in cases
where the sample size of the input data is low with respect to the
dimensionality of the model, which is often the case when working with real
data. The paper presents a novel hybrid structure learning algorithm, called
SaiyanH, that addresses this issue. The results show that this constraint helps
the algorithm to estimate the number of true edges with higher accuracy
compared to the state-of-the-art. Out of the 13 algorithms investigated, the
results rank SaiyanH 4th in reconstructing the true DAG, with accuracy scores
lower by 8.1% (F1), 10.2% (BSF), and 19.5% (SHD) compared to the top ranked
algorithm, and higher by 75.5% (F1), 118% (BSF), and 4.3% (SHD) compared to the
bottom ranked algorithm. Overall, the results suggest that the proposed
algorithm discovers satisfactorily accurate connected DAGs in cases where other
algorithms produce multiple disjoint subgraphs that often underfit the true
graph.
