# Probabilistic Circuits for Variational Inference in Discrete Graphical Models

arXiv: https://arxiv.org/abs/2010.11446 · HTML: https://mlsanity.com/paper/2010.11446/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2020.

## Built on by (most cited first, 20 of 20)

- [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022)
- [Tractable Regularization of Probabilistic Circuits](https://mlsanity.com/paper/2106.02264/) (2021)
- [Subtractive Mixture Models via Squaring: Representation and Learning](https://mlsanity.com/paper/2310.00724/) (2023)
- [Scaling Up Probabilistic Circuits by Latent Variable Distillation](https://mlsanity.com/paper/2210.04398/) (2022)
- [Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics](https://mlsanity.com/paper/2502.08696/) (2025)
- [Tractable Uncertainty for Structure Learning](https://mlsanity.com/paper/2204.14170/) (2022)
- [HyperSPNs: Compact and Expressive Probabilistic Circuits](https://mlsanity.com/paper/2112.00914/) (2021)
- [Building Expressive and Tractable Probabilistic Generative Models: A Review](https://mlsanity.com/paper/2402.00759/) (2024)
- [Characteristic Circuits](https://mlsanity.com/paper/2312.07790/) (2023)
- [A Compositional Atlas of Tractable Circuit Operations: From Simple Transformations to Complex Information-Theoretic Queries](https://mlsanity.com/paper/2102.06137/) (2021)
- [Restructuring Tractable Probabilistic Circuits](https://mlsanity.com/paper/2411.12256/) (2024)
- [Rethinking Losses for Diffusion Bridge Samplers](https://mlsanity.com/paper/2506.10982/) (2025)
- [How to Square Tensor Networks and Circuits Without Squaring Them](https://mlsanity.com/paper/2512.17090/) (2025)
- [Efficient and Reliable Probabilistic Interactive Learning with Structured Outputs](https://mlsanity.com/paper/2202.08566/) (2022)
- [Tractable Computation of Expected Kernels](https://mlsanity.com/paper/2102.10562/) (2021)
- [Fair Inference for Discrete Latent Variable Models](https://mlsanity.com/paper/2209.07044/) (2022)
- [Approximate Bayesian Inference via Bitstring Representations](https://mlsanity.com/paper/2508.13598/) (2025)
- [How to Approximate Inference with Subtractive Mixture Models](https://mlsanity.com/paper/2604.16714/) (2026)
- [A canonical generalization of OBDD](https://mlsanity.com/paper/2604.05537/) (2026)
- [Amortized Bayesian Causal Discovery of Extended Factor Graphs](https://mlsanity.com/paper/2607.22934/) (2026)

## Abstract (arXiv)

Inference in discrete graphical models with variational methods is difficult because of the inability to re-parameterize gradients of the Evidence Lower Bound (ELBO). Many sampling-based methods have been proposed for estimating these gradients, but they suffer from high bias or variance. In this paper, we propose a new approach that leverages the tractability of probabilistic circuit models, such as Sum Product Networks (SPN), to compute ELBO gradients exactly (without sampling) for a certain class of densities. In particular, we show that selective-SPNs are suitable as an expressive variational distribution, and prove that when the log-density of the target model is a polynomial the corresponding ELBO can be computed analytically. To scale to graphical models with thousands of variables, we develop an efficient and effective construction of selective-SPNs with size O(kn), where n is the number of variables and k is an adjustable hyperparameter. We demonstrate our approach on three types of graphical models -- Ising models, Latent Dirichlet Allocation, and factor graphs from the UAI Inference Competition. Selective-SPNs give a better lower bound than mean-field and structured mean-field, and is competitive with approximations that do not provide a lower bound, such as Loopy Belief Propagation and Tree-Reweighted Belief Propagation. Our results show that probabilistic circuits are promising tools for variational inference in discrete graphical models as they combine tractability and expressivity.