New Compilation Languages Based on Restricted Weak Decomposability

Petr IllnerAAAI 2025 · DOI

Abstract

This paper introduces two novel circuit languages, positive weak DNNF (pwDNNF) and negative weak DNNF (nwDNNF), designed to bridge the gap between the highly succinct but less functional wDNNF and the more functional but larger DNNF. By restricting the polarity of shared variables in conjunctions, these languages enable efficient linear-time computation of cardinality queries, which are critical for solving Most Probable Explanation (MPE) problems in Bayesian networks. We present a compiler, Bella, enhanced with a novel isomorphism caching technique called Cara. Our experimental results demonstrate that pwDNNF and nwDNNF are strictly more succinct than DNNF and that our compilation approach significantly outperforms state-of-the-art DNNF compilers on complex, large-domain networks.

Introduction

Knowledge Compilation (KC) is a paradigm in which hard reasoning problems are solved by translating them into a target language where specific queries can be answered in polynomial time. A central challenge in KC is the trade-off between succinctness (the size of the compiled circuit) and tractability (the set of queries supported). The language of weak Decomposable Negation Normal Form (wDNNF) is known for its extreme succinctness but fails to support cardinality queries, such as finding the minimum or maximum number of true variables in a satisfying assignment. This limitation makes wDNNF unsuitable for MPE tasks. This paper proposes pwDNNF and nwDNNF as a "Goldilocks" solution: languages that maintain much of wDNNF's succinctness while gaining the tractability required for MPE.

The pwDNNF and nwDNNF Languages

The core contribution of this work is the definition of two restricted variants of wDNNF. In pwDNNF, any variable shared between the children of a conjunction must appear only as a positive literal. Conversely, in nwDNNF, shared variables must appear only as negative literals. These structural constraints allow for the efficient computation of minimum and maximum cardinality via simple graph traversals.

The hierarchy of NNF languages, illustrating the succinctness relationship between wDNNF, the new restricted variants, and DNNF.

As illustrated in the hierarchy above, these new languages occupy a strategic position in the Knowledge Compilation Map. Their tractability profile is compared with other common languages in the table below, highlighting their unique support for cardinality queries (MinCard/MaxCard) relative to wDNNF.

Tractability comparison of circuit types, showing that pwDNNF and nwDNNF support cardinality queries.

Compilation and Isomorphism Caching

To evaluate these languages, we extended the Bella compiler to enforce the pwDNNF and nwDNNF properties. A significant performance bottleneck in compilation is redundant sub-problem solving. While most compilers use component caching to identify identical sub-problems, we introduce Cara, an isomorphism caching scheme. Cara uses statistical "sample moments" to detect when two sub-problems are structurally identical even if their variable sets differ. When a match is found, the compiler reuses the existing subcircuit through renaming, leading to substantial speedups.

Experimental Evaluation

We tested our approach on various Bayesian network topologies, including two-layer networks and dense DQMR networks with large variable domains. The results show that nwDNNF circuits are consistently smaller than standard decision-DNNF circuits produced by tools like D4 and C2D. Furthermore, the Bella+Cara compiler demonstrated superior performance, particularly as problem density and domain size increased, achieving speedups of over 14x in specific benchmarks.

Conclusion

By introducing pwDNNF and nwDNNF, we have expanded the Knowledge Compilation Map with languages that are optimized for MPE tasks. The combination of these restricted languages and isomorphism-aware compilation provides a powerful toolset for probabilistic reasoning in complex domains. Future research will focus on optimizing variable ordering for more diverse network topologies and extending these techniques to other types of probabilistic queries.

Summary updated

BibTeX
@inproceedings{illner2025new,
  author = {Petr Illner},
  title = {{New Compilation Languages Based on Restricted Weak Decomposability}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i14.33643},
}
Figure