Official Review · NEURIPS 2023

The paper studies algorithms for the marginal MAP (MMAP) problem in Credal networks that generalize Bayesian networks. The paper gives an overview of the problem, existing algorithms for Bayesian networks and generalizes the algorithms to credal networks. Overall, two exact and multiple heuristic approaches are presented. As the exact approaches were unable to deal with larger problems, the experiments are restricted to heuristic approaches. The paper is very well written and gives a good overview of the problem and related work. While Bayesian networks are an old topic, they remain relevant for probabilistic reasoning tasks that require analytical guarantees. However, one problem of Bayesian networks is that specifying the CPDs can be difficult. Credal networks are an interesting generalization that allows using probability intervals rather than point probabilities in order to capture the uncertainty about the encoded knowledge. To the best of my knowledge, there is not much literature on algorithms for Credal networks. The authors generalize state-of-the-art ideas for Bayesian networks to Credal networks and give an empirical evaluation. The paper is therefore an interesting contribution to the probabilistic reasoning literature. The code is attached in the supplementary material to reproduce the experimental results and is a useful resource for the probabilistic reasoning community. It could be discussed in more detail what the exact relationship between the proposed algorithms and the corresponding algorithms for BNs is. Are they generalizations in the sense that if the intervals in the Credal network are tight, then the Credal network algorithms correspond to the BN algorithms? Are there challenges in generalizing the algorithms to credal nets or is the generalization straightforward? And how do the runtime guarantees for Credal networks compare to those for Bayesian networks? Could you elaborate on the relationship between CN and BN algorithms (see weaknesses)?