# A Compositional Atlas of Tractable Circuit Operations: From Simple Transformations to Complex Information-Theoretic Queries

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 51 references that are in the map.
- First posted on arXiv 11 Feb 2021.

## Builds on (most cited first, 13 of 13)

- [A Semantic Loss Function for Deep Learning with Symbolic Knowledge](https://mlsanity.com/paper/1711.11157/) (2017)
- [Expectation Propagation for approximate Bayesian inference](https://mlsanity.com/paper/1301.2294/) (2013)
- [Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2004.06231/) (2020)
- [SPFlow: An Easy and Extensible Library for Deep Probabilistic Learning using Sum-Product Networks](https://mlsanity.com/paper/1901.03704/) (2019)
- [Strudel: Learning Structured-Decomposable Probabilistic Circuits](https://mlsanity.com/paper/2007.09331/) (2020)
- [Joints in Random Forests](https://mlsanity.com/paper/2006.14937/) (2020)
- [Probabilistic Circuits for Variational Inference in Discrete Graphical Models](https://mlsanity.com/paper/2010.11446/) (2020)
- [On Tractable Computation of Expected Predictions](https://mlsanity.com/paper/1910.02182/) (2019)
- [Smoothing Structured Decomposable Circuits](https://mlsanity.com/paper/1906.00311/) (2019)
- [Cauchy-Schwarz Regularized Autoencoder](https://mlsanity.com/paper/2101.02149/) (2021)
- [What to Expect of Classifiers? Reasoning about Logistic Regression with Missing Features](https://mlsanity.com/paper/1903.01620/) (2019)
- [Scaling up Hybrid Probabilistic Inference with Logical and Arithmetic Constraints via Message Passing](https://mlsanity.com/paper/2003.00126/) (2020)
- [Handling Missing Data in Decision Trees: A Probabilistic Approach](https://mlsanity.com/paper/2006.16341/) (2020)

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

- [Tractable Regularization of Probabilistic Circuits](https://mlsanity.com/paper/2106.02264/) (2021)
- [Tractable Boolean and Arithmetic Circuits](https://mlsanity.com/paper/2202.02942/) (2022)
- [Probabilistic Integral Circuits](https://mlsanity.com/paper/2310.16986/) (2023)
- [Sum-Product-Set Networks: Deep Tractable Models for Tree-Structured Graphs](https://mlsanity.com/paper/2408.07394/) (2024)
- [Efficient and Reliable Probabilistic Interactive Learning with Structured Outputs](https://mlsanity.com/paper/2202.08566/) (2022)
- [GraphSPNs: Sum-Product Networks Benefit From Canonical Orderings](https://mlsanity.com/paper/2408.09451/) (2024)
- [Tractable Computation of Expected Kernels](https://mlsanity.com/paper/2102.10562/) (2021)

## Abstract (arXiv)

Circuit representations are becoming the lingua franca to express and reason about tractable generative and discriminative models. In this paper, we show how complex inference scenarios for these models that commonly arise in machine learning -- from computing the expectations of decision tree ensembles to information-theoretic divergences of deep mixture models -- can be represented in terms of tractable modular operations over circuits. Specifically, we characterize the tractability of a vocabulary of simple transformations -- sums, products, quotients, powers, logarithms, and exponentials -- in terms of sufficient structural constraints of the circuits they operate on, and present novel hardness results for the cases in which these properties are not satisfied. Building on these operations, we derive a unified framework for reasoning about tractable models that generalizes several results in the literature and opens up novel tractable inference scenarios.