# On the Expressive Power of Tree-Structured Probabilistic Circuits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 39 references that are in the map.
- First posted on arXiv 7 Oct 2024.

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

- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [On the Expressive Power of Deep Polynomial Neural Networks](https://mlsanity.com/paper/1905.12207/) (2019)
- [Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks](https://mlsanity.com/paper/1610.09887/) (2016)
- [Context-Specific Independence in Bayesian Networks](https://mlsanity.com/paper/1302.3562/) (2013)
- [Probabilistic Generating Circuits](https://mlsanity.com/paper/2102.09768/) (2021)
- [A Unified Approach for Learning the Parameters of Sum-Product Networks](https://mlsanity.com/paper/1601.00318/) (2016)
- [Is Deeper Better only when Shallow is Good?](https://mlsanity.com/paper/1903.03488/) (2019)
- [Neural Networks Should Be Wide Enough to Learn Disconnected Decision Regions](https://mlsanity.com/paper/1803.00094/) (2018)
- [On the Expressive Efficiency of Sum Product Networks](https://mlsanity.com/paper/1411.7717/) (2014)
- [Sum-product networks: A survey](https://mlsanity.com/paper/2004.01167/) (2020)
- [On the Relationship between Sum-Product Networks and Bayesian Networks](https://mlsanity.com/paper/1501.01239/) (2015)
- [Polynomial Semantics of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2402.09085/) (2024)
- [Hierarchical Spatial Sum-Product Networks for Action Recognition in Still Images](https://mlsanity.com/paper/1511.05292/) (2015)

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

- [Restructuring Tractable Probabilistic Circuits](https://mlsanity.com/paper/2411.12256/) (2024)
- [On the Hardness of Approximating Distributions with Tractable Probabilistic Models](https://mlsanity.com/paper/2506.01281/) (2025)
- [Probabilistic Graph Circuits: Deep Generative Models for Tractable Probabilistic Inference over Graphs](https://mlsanity.com/paper/2503.12162/) (2025)

## Abstract (arXiv)

Probabilistic circuits (PCs) have emerged as a powerful framework to compactly represent probability distributions for efficient and exact probabilistic inference. It has been shown that PCs with a general directed acyclic graph (DAG) structure can be understood as a mixture of exponentially (in its height) many components, each of which is a product distribution over univariate marginals. However, existing structure learning algorithms for PCs often generate tree-structured circuits or use tree-structured circuits as intermediate steps to compress them into DAG-structured circuits. This leads to the intriguing question of whether there exists an exponential gap between DAGs and trees for the PC structure. In this paper, we provide a negative answer to this conjecture by proving that, for n variables, there exists a quasi-polynomial upper bound nO(log n) on the size of an equivalent tree computing the same probability distribution. On the other hand, we also show that given a depth restriction on the tree, there is a super-polynomial separation between tree and DAG-structured PCs. Our work takes an important step towards understanding the expressive power of tree-structured PCs, and our techniques may be of independent interest in the study of structure learning algorithms for PCs.