Advances in Marginal Inference for Chain-Graph Logical Credal Networks

Logical Credal Networks (LCNs) are an expressive probabilistic logic framework that combines propositional formulas with imprecise probability bounds to represent sets of probability distributions. While LCNs support cyclic dependencies and impose few syntactic restrictions, inference remains computationally challenging. Existing exact methods scale exponentially with the number of propositions, and the only available approximate approach is the ARIEL message-passing algorithm. In this paper, we exploit the chain graph structure underlying LCNs and reformulate inference as a credal network problem. Building on this formulation, we propose three approximate inference algorithms based on variable elimination, interval-valued message passing, and coordinate descent for computing posterior probability bounds. We also introduce an exact inference method that leverages a junction tree decomposition of the chain graph to construct and solve a substantially smaller nonlinear program. We establish theoretical properties of the proposed methods and evaluate them on synthetic and realistic LCN instances. The results show substantial speedups over existing approaches while maintaining high-quality probability bounds and enabling exact inference on significantly larger problems.