Variance Computation for Weighted Model Counting with Knowledge Compilation Approach

AI summary

Overview

• Research area: Knowledge compilation and probabilistic inference — specifically the tractability (complexity) of computing the variance of weighted model counting (WMC) when the weights themselves are random variables.
• Technical level: Advanced. The paper is a theory-heavy study combining knowledge compilation theory, complexity analysis, and an application to Bayesian network inference.
• Scope in one sentence: The paper defines a new query (variance of WMC), gives a polynomial-time algorithm for structured d-DNNF inputs, proves hardness for several other representations, and demonstrates an application to uncertainty analysis in Bayesian networks.

What This Paper Is About

Weighted model counting is the workhorse query behind probabilistic inference: once a Boolean function is compiled into a tractable form, its WMC typically equals an inference outcome such as a marginal probability. In practice, however, model parameters are learned from limited data and are therefore uncertain, so users want to know how much that uncertainty propagates into the inference result — that is, the variance of the WMC value. This paper formalizes that variance computation problem (and a companion covariance computation problem) and asks a tractability question: for which knowledge compilation representations can the variance be computed in polynomial time, and for which is it intractable?

Key Contributions

1. A polynomial-time algorithm for structured d-DNNFs. The authors derive an algorithm that computes the covariance of the WMCs of two Boolean functions given as st-d-DNNFs respecting the same vtree in O(|α||β| + |𝒱|²) time, which specializes to O(|α|² + |𝒱|²) time for the variance of a single st-d-DNNF α.
2. Hardness results for supersets. They prove that the variance cannot be computed in polynomial time unless P = NP when the Boolean function is given as a structured DNNF, a d-DNNF, or an FBDD — all strict supersets of structured d-DNNFs. The last two are notable because ordinary WMC is tractable for them.
3. An application to Bayesian network inference. They show that the variance of the marginal probability can be obtained in polynomial time for a Bayesian network with constant treewidth, and empirically demonstrate the algorithm on real-world Bayesian networks.
4. An uncertainty-analysis tool. They demonstrate that one can identify parameters whose variances have the greatest impact on the variance of the marginal probability — useful for deciding which parameters to learn further in order to reduce inference uncertainty.

Main Findings

• Variance is tractable on st-d-DNNFs: Theorem 7 states that CVC (covariance computation) for st-d-DNNFs α, β respecting the same vtree runs in O(|α||β| + |𝒱|²), and VC (variance computation) for a single st-d-DNNF runs in O(|α|² + |𝒱|²). Since structured d-DNNFs subsume sentential decision diagrams (SDDs), this covers a widely used representation.
• Hardness beyond structured d-DNNFs: For structured DNNFs, d-DNNFs, and FBDDs, no polynomial-time algorithm exists unless P = NP. This is the paper's most intriguing result because d-DNNFs and FBDDs admit polynomial-time WMC.
• The key technical obstacle is variable-set management: Because the WMC value changes when the variable set changes, the algorithm must track which variables are in scope at each recursive step; the authors solve this by using the vtree, decomposing covariance according to the lowest common ancestor (LCA) of the decomposition vnodes d(α) and d(β).
• Three decomposition cases drive the algorithm: (I) d(α) and d(β) in no ancestor-descendant relation, (II) d(α) is an ancestor of d(β) and α is a ∨-node, and (III) d(α) is an ancestor of d(β) and α is a ∧-node. These yield Lemmas 8, 9, and 10 respectively, which are combined in Algorithm 1 with memoization.
• Brute force is exponential: Explicit enumeration costs O(|𝒱||𝒜_f|²) time for variance and O(|𝒱||𝒜_f||𝒜_g|) for covariance, where |𝒜_f| and |𝒜_g| are generally exponential in |𝒱|.
• Improvement over prior reliability analysis: A previous study (Nakamura et al., 2022) computed the variance of network reliability in polynomial time in the size of an OBDD for networks of constant pathwidth. Because treewidth subsumes pathwidth but not vice versa, this paper's treewidth result is a theoretical improvement.
• Contrast with credal networks: Marginal inference for credal networks is NP-hard even for constant-treewidth networks (De Campos and Cozman, 2005), whereas this approach computes the variance of the marginal in polynomial time for constant-treewidth networks.
• Empirical demonstration: The authors report that the algorithm can evaluate the variance of the marginal probability on real-world Bayesian networks and can analyze the impact of parameter variances on the variance of the marginal. The specific network names, dataset sizes, and runtime measurements are not reported in the provided content.

Methodology in Plain English

The authors start from a simple observation: the WMC of a Boolean function is a sum over its models of products of weights, so if each positive and negative weight is a random variable, the WMC itself becomes a random variable. They assume that the weight pairs (P_x, N_x) and (P_y, N_y) for different variables x ≠ y are independent, while P_x and N_x for the same variable need not be independent — so covariances between a variable's positive and negative weights are allowed as input.

Rather than enumerating models (exponential), they work directly on the compiled circuit. They design a recursive procedure that expresses the covariance of two WMCs in terms of the covariances and expectations of the WMCs of the circuits' children, using two standard identities: the linearity of covariance for sums, and a product formula for Cov[AX, BY] when (A,B) is independent of (X,Y). The recursion cases are dictated by how the two circuits' variable scopes sit relative to each other in the shared vtree. To avoid redundant work, computed covariances are cached by node pair. Expectations of WMC for every node are precomputed with a standard WMC algorithm. The result is an algorithm whose running time is proportional to the product of the circuit sizes rather than the number of models.

Why This Matters

Impact on research. The paper expands the knowledge compilation map with a new query — variance (and covariance) of WMC — and pins down exactly where it sits in terms of tractability. Perhaps most importantly, it shows a case where a query is tractable on structured d-DNNFs but intractable on d-DNNFs and FBDDs, even though those representations support the underlying WMC query. That separation is a fresh data point about the value of structuredness.

Real-world applications (as identified in the paper):

• Bayesian network inference: quantifying how uncertain parameters translate into uncertain marginal probabilities, and prioritizing which parameters to learn more about.
• Communication network reliability: the WMC of a connectivity Boolean function equals network reliability when links fail stochastically; the paper's result extends variance-of-reliability computation from constant-pathwidth to constant-treewidth networks.
• Factor graph inference: WMC is the standard query technique for these models, so variance computation applies directly.
• Probabilistic programming: WMC-based inference is used there as well, so the variance query carries over.

Industry relevance. In decision-making systems that depend on inference outcomes, a computed variance signals when a result should be treated as unreliable — the paper explicitly frames this as the motivation. The parameter-prioritization use case also speaks directly to practitioners who must budget data collection or additional learning effort.

Future Directions

• Relaxing the independence assumption. The paper states that the independence assumption between (P_x, N_x) and (P_y, N_y) for x ≠ y "is reasonable for some applications" and that it is "slightly relaxed for a specific application," with details deferred to Appendices B and C. Generalizing this further is a natural next step.
• Other uncertainty measures. The paper focuses on variance and covariance; whether other uncertainty measures (such as higher moments or bounds) admit similarly tractable algorithms on structured d-DNNFs is left open.
• Extending the empirical study. The paper's provided content does not report specific benchmark networks, dataset sizes, or running times; a broader empirical comparison across real-world Bayesian networks would clarify practical scalability.
• Other tractable representations. Given the hardness for structured DNNFs, d-DNNFs, and FBDDs, an open question is whether any other representation class (beyond st-d-DNNFs and its subsets, such as OBDDs and SDDs) supports polynomial-time variance computation.

Target Audience

Researchers and graduate students in artificial intelligence working on knowledge compilation, weighted model counting, probabilistic inference, and Bayesian networks — particularly those interested in complexity classifications of queries over compiled representations. Practitioners building uncertainty-aware inference systems for Bayesian networks, reliability analysis, factor graphs, or probabilistic programming will also find the application section relevant. The paper is theory-first, so readers should be comfortable with Boolean functions, NNF variants, vtrees, and complexity-theoretic arguments.

Authors’ abstract

One of the most important queries in knowledge compilation is weighted model counting (WMC), which has been applied to probabilistic inference on various models, such as Bayesian networks. In practical situations on inference tasks, the model's parameters have uncertainty because they are often learned from data, and thus we want to compute the degree of uncertainty in the inference outcome. One possible approach is to regard the inference outcome as a random variable by introducing distributions for the parameters and evaluate the variance of the outcome. Unfortunately, the tractability of computing such a variance is hardly known. Motivated by this, we consider the problem of computing the variance of WMC and investigate this problem's tractability. First, we derive a polynomial time algorithm to evaluate the WMC variance when the input is given as a structured d-DNNF. Second, we prove the hardness of this problem for structured DNNFs, d-DNNFs, and FBDDs, which is intriguing because the latter two allow polynomial time WMC algorithms. Finally, we show an application that measures the uncertainty in the inference of Bayesian networks. We empirically show that our algorithm can evaluate the variance of the marginal probability on real-world Bayesian networks and analyze the impact of the variances of parameters on the variance of the marginal.