Bayesian Network Structure Learning: The NewCalibrated Minimum Uncertainty Criterion andDiscriminative Power Evaluation Framework

Bayesian network (BN) structure learning (BNSL) from heterogeneous data is a classical problem in probabilistic machine learning and knowledge discovery. A variety of computational methods exist for score-based BNSL, but all inherit limitations imposed by the underlying model selection paradigms. With finite, often scarce data, imperfect conversion of observations into structural evidence can lead to miscalibration, structural bias, amplification of statistical errors, and unstable or poorly interpretable learned networks. The recently introduced Minimum Uncertainty (MU) principle was proposed to mitigate these problems for discrete BNSL, but its scoring criterion remained a preliminary prototype requiring generalization and calibration. Here, we derive a resolution-aware, calibrated MU criterion under broad perturbation assumptions and develop a framework for evaluating the discriminative power of BN scoring criteria. Across parameter regimes and dependence modes, comparison with MDL, BDeu, and K2 shows that the calibrated MU criterion maintains balanced operating characteristics and improves structure recovery performance, with negligible computational overhead; these gains are also confirmed on real biomedical data. The evaluation framework additionally provides edge-level specificity, sensitivity, and evidence-quality estimates, supporting both practical interpretation of learned networks and principled comparison of scoring criteria. Together, the calibrated MU criterion and the discriminative power evaluation framework provide a general approach for more robust, interpretable, and statistically calibrated score-based structure learning across diverse settings and domains.