Comprehensive robustness bounds for discrete Bayesian networks: combining total-variation diameter bounds with local DeRoberts prior robustness

The diameter framework of Leonelli, Smith and Wright bounds how much the distribution of a target variable in a discrete Bayesian network can change when conditional probability table (CPT) entries are perturbed, using the total variation distance and a new dependence measure — the diameter of a stochastic matrix. The source paper explicitly leaves open an acknowledged extension: it did not consider robustness to the choice of the probability distribution placed on the CPT entries, and proposes combining its variation-distance bounds with the local DeRoberts-distance prior-robustness methodology (Smith–Daneshkhah 2010, Smith–Rigat 2012) into a single comprehensive robustness analysis. The open problem is therefore to formalize a joint perturbation class covering both CPT-entry misspecification and prior/parameter-distribution misspecification, and to prove explicit total-variation bounds on target and posterior distributions under both error sources simultaneously, with consistency with the existing single-source bounds as limiting cases.

Background

A Bayesian network (BN) is a probabilistic graphical model in which a joint distribution over categorical variables factorizes, over a directed acyclic graph, into conditional probability tables (CPTs): each CPT is a stochastic matrix whose rows are the conditional distributions of one variable given a configuration of its parents. Because BNs are widely used for risk assessment and decision support — often with CPTs filled in by expert elicitation — a central methodological question is sensitivity analysis: how much do inferences about designated target variables change when the model's numbers are wrong. The most traditional approach studies sensitivity functions, the functional relationship between individual CPT entries and an output probability, and is usually restricted to one-at-a-time perturbations; robustness is also commonly scored with Kullback–Leibler divergences (an information-theoretic measure of how one probability distribution differs from another). The total variation distance between two probability mass functions $p$ and $p'$ on the same finite sample space is $d_V(p,p') = (1/2)\sum_{x}|p(x)-p'(x)|$, taking values in $[0,1]$; it is often closer than divergence measures to the absolute errors one expects from elicitation mistakes or misestimation. Leonelli, Smith and Wright (2024), published in extended form by Leonelli and Smith (2025), built a robustness methodology on $d_V$. Its core object is the (upper) diameter of an $n \times m$ stochastic matrix $P$ with rows $p_1,\dots,p_n$: $d^+(P) = \max_{i,j} d_V(p_i,p_j)$, the largest total variation distance between any two rows of a CPT, measuring how strongly a variable depends on its parents' configuration (the lower diameter $d^-(P)$ uses the minimum and detects partial conditional independence). A first main result bounds single-step propagation: if two joint distributions share the same CPT $P_{Y|X}$, then $d_V(p(y),p'(y)) \le d^+(P_{Y|X})\,d_V(p(x),p'(x))$ — uncertainty about a child cannot exceed uncertainty about the parent, attenuated by the diameter. Chaining this along the cliques of a junction tree (the clique graph used for exact BN inference) yields product bounds on the change of a target variable's distribution in terms of the diameters of the CPTs encountered along the path. From the diameter the authors also derive an edge strength $\delta_{ji}$ (the maximum diameter of sub-CPTs in which all parents but $X_j$ are fixed), node-influence measures, and elicitation heuristics; the methods are implemented in the bnmonitor R package. A separate, older strand addresses a different source of error: instead of perturbing CPT entries deterministically, it treats the assumed probability model itself as uncertain. DeRoberts and Hartigan (1981) introduced Bayesian inference with intervals of measures, replacing a single prior/data measure by upper and lower bounds; the associated local DeRoberts distance (often spelled DeRobertis) is defined, for two positive densities $f$ and $g$ on a measurable set $A$ of the parameter space, as the oscillation of their log-density ratio over $A$, $d^{L}_{A}(f,g) = \sup_{\theta,\phi \in A}\bigl(\log\{f(\theta)/g(\theta)\} - \log\{f(\phi)/g(\phi)\}\bigr)$, so that the densities lying within a neighbourhood of radius $\Delta$ of $f$ are those $g$ with $\exp\{d^{L}_{A}(f,g)\} \le 1 + \Delta$. Smith and Daneshkhah (2010) studied robustness of Bayesian networks when learning from non-conjugate sampling in terms of this local DeRoberts distance, and Smith and Rigat (2012) used their isoseparation framework — a duality between priors and posteriors under which posterior distances control prior distances — to bound posterior variation distances in parametric Bayesian inference. These two strands are disjoint: the diameter bounds cover misspecification of individual CPT entries but assume the distributional assumptions behind the entries are fixed, while the DeRoberts strand covers distributional misspecification but predates and does not use the diameter. The source paper's discussion section explicitly acknowledges the gap and proposes closing it: combining the new variation-distance bounds with the local DeRoberts distance to provide a comprehensive robustness analysis, calling this a reasonably straightforward but not yet performed extension.

Problem Statement

For a finite discrete Bayesian network with specified CPTs and a designated target variable, develop the comprehensive robustness analysis requested by Leonelli, Smith and Wright (2024; journal version Leonelli and Smith, 2025): formal definitions and proved explicit bounds on the total variation distance between the target-variable distributions of the nominal network and a jointly misspecified model — both the marginal distribution before evidence and the posterior distribution after conditioning on evidence — in which two error sources act simultaneously: (i) perturbation of the conditional probability table entries, as quantified by the diameter machinery ($d^+(P)$, edge strengths, junction-tree product bounds), and (ii) misspecification of the choice of probability distribution on the CPT entries (the prior/parameter-distribution assumptions), as quantified by the local DeRoberts distance in the sense of DeRoberts and Hartigan (1981) and Smith and Daneshkhah (2010), building on the posterior variation-distance bounds of Smith and Rigat (2012). Define the joint perturbation class precisely enough that well-definedness, and its behaviour under conditioning and marginalization, can be checked; state and prove explicit total-variation bounds on target and posterior distributions under the joint class, in the spirit of the single-step and junction-tree bounds of the diameter paper; and prove consistency with the constituent strands — when the prior-misspecification term vanishes the bounds collapse to the published diameter bounds, and when CPT perturbations vanish they collapse to DeRoberts-type robustness bounds.

References

1. Leonelli, M., Smith, J.Q., Wright, S.K., 2024. The diameter of a stochastic matrix: A new measure for sensitivity analysis in Bayesian networks. arXiv:2407.04667. https://arxiv.org/abs/2407.04667
2. Leonelli, M., Smith, J.Q., 2025. The diameter of a stochastic matrix: A new measure for sensitivity analysis in Bayesian networks. International Journal of Approximate Reasoning 185, 109470. doi:10.1016/j.ijar.2025.109470. https://doi.org/10.1016/j.ijar.2025.109470
3. Smith, J.Q., Daneshkhah, A., 2010. On the robustness of Bayesian networks to learning from non-conjugate sampling. International Journal of Approximate Reasoning 51, 558–572. doi:10.1016/j.ijar.2010.01.013. https://doi.org/10.1016/j.ijar.2010.01.013
4. Smith, J.Q., Rigat, F., 2012. Isoseparation and robustness in parametric Bayesian inference. Annals of the Institute of Statistical Mathematics 64, 495–519. doi:10.1007/s10463-011-0334-9. https://doi.org/10.1007/s10463-011-0334-9
5. DeRoberts, L., Hartigan, J.A., 1981. Bayesian inference using intervals of measures. The Annals of Statistics 9, 235–244. doi:10.1214/aos/1176345391. https://doi.org/10.1214/aos/1176345391
6. Ballester-Ripoll, R., Leonelli, M., 2025. Global sensitivity analysis of uncertain parameters in Bayesian networks. International Journal of Approximate Reasoning 180, 109368. arXiv:2406.05764. doi:10.1016/j.ijar.2025.109368. https://arxiv.org/abs/2406.05764
7. Bales, W., Rovi, C., 2026. A stable distance persistence homology for dynamic Bayesian network clustering. arXiv:2605.11226. https://arxiv.org/abs/2605.11226
8. Drury, K., Smith, J.Q., 2024. Dynamic Bayesian networks, elicitation and data embedding for secure environments. Entropy 26(11), 985. arXiv:2409.07389. doi:10.3390/e26110985. https://arxiv.org/abs/2409.07389
9. Garcia Murga, A., Leonelli, M., 2026. Disentangling spatial and structural drivers of housing prices through Bayesian networks: A case study of Madrid, Barcelona, and Valencia. Cities 174, 107063. arXiv:2506.09539. doi:10.1016/j.cities.2026.107063. https://arxiv.org/abs/2506.09539
10. Maciejowski, J., Leonelli, M., 2026. Uncovering drivers of EU carbon futures with Bayesian networks. Applied Energy 403, 127034. arXiv:2505.10384. doi:10.1016/j.apenergy.2025.127034. https://arxiv.org/abs/2505.10384
11. Leonelli, M., Ramanathan, R., Wilkerson, R.L., 2021. bnmonitor: An implementation of sensitivity analysis in Bayesian networks. CRAN package. doi:10.32614/cran.package.bnmonitor. https://doi.org/10.32614/cran.package.bnmonitor