# Robustness Guarantees for Credal Bayesian Networks via Constraint Relaxation over Probabilistic Circuits

arXiv: https://arxiv.org/abs/2205.05793 · HTML: https://mlsanity.com/paper/2205.05793/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 35 references that are in the map.
- First posted on arXiv 11 May 2022.

## Builds on (most cited first, 9 of 9)

- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Detecting and Correcting for Label Shift with Black Box Predictors](https://mlsanity.com/paper/1802.03916/) (2018)
- [A Differential Approach to Inference in Bayesian Networks](https://mlsanity.com/paper/1301.3847/) (2013)
- [Reachability Analysis of Deep Neural Networks with Provable Guarantees](https://mlsanity.com/paper/1805.02242/) (2018)
- [Verifying Properties of Binarized Deep Neural Networks](https://mlsanity.com/paper/1709.06662/) (2017)
- [Structural Causal Models Are (Solvable by) Credal Networks](https://mlsanity.com/paper/2008.00463/) (2020)
- [Provable Guarantees on the Robustness of Decision Rules to Causal Interventions](https://mlsanity.com/paper/2105.09108/) (2021)
- [Tractable Inference in Credal Sentential Decision Diagrams](https://mlsanity.com/paper/2008.08524/) (2020)
- [CREPO: An Open Repository to Benchmark Credal Network Algorithms](https://mlsanity.com/paper/2105.04158/) (2021)

## Built on by (most cited first, 1 of 1)

- [Tight Verification of Probabilistic Robustness in Bayesian Neural Networks](https://mlsanity.com/paper/2401.11627/) (2024)

## Abstract (arXiv)

In many domains, worst-case guarantees on the performance (e.g., prediction accuracy) of a decision function subject to distributional shifts and uncertainty about the environment are crucial. In this work we develop a method to quantify the robustness of decision functions with respect to credal Bayesian networks, formal parametric models of the environment where uncertainty is expressed through credal sets on the parameters. In particular, we address the maximum marginal probability (MARmax) problem, that is, determining the greatest probability of an event (such as misclassification) obtainable for parameters in the credal set. We develop a method to faithfully transfer the problem into a constrained optimization problem on a probabilistic circuit. By performing a simple constraint relaxation, we show how to obtain a guaranteed upper bound on MARmax in linear time in the size of the circuit. We further theoretically characterize this constraint relaxation in terms of the original Bayesian network structure, which yields insight into the tightness of the bound. We implement the method and provide experimental evidence that the upper bound is often near tight and demonstrates improved scalability compared to other methods.