Dissociation-Based Oblivious Bounds for Weighted Model Counting

We consider the weighted model counting task which includes important tasks in graphical models such as computing the partition function and probability of evidence as special cases. We propose a partition-based bounding algorithm that exploits logical structure and gives rise to a novel set of inequalities from which lower (and upper) bounds can be derived efficiently. The bounds come with correctness guarantees and are oblivious in that they can be computed by minimally manipulating the parameters of the model. We experimentally compare our bounds with the mini-bucket scheme (which is also oblivious) and show that they are often superior to the latter on a wide variety of benchmark networks.