# Sum-Product-Set Networks: Deep Tractable Models for Tree-Structured Graphs

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

## Key facts

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

## Builds on (most cited first, 30 of 39)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [MolGAN: An implicit generative model for small molecular graphs](https://mlsanity.com/paper/1805.11973/) (2018)
- [GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders](https://mlsanity.com/paper/1802.03480/) (2018)
- [Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks](https://mlsanity.com/paper/1503.00075/) (2015)
- [Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations](https://mlsanity.com/paper/2202.02514/) (2022)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [GraphDF: A Discrete Flow Model for Molecular Graph Generation](https://mlsanity.com/paper/2102.01189/) (2021)
- [NetGAN: Generating Graphs via Random Walks](https://mlsanity.com/paper/1803.00816/) (2018)
- [Graphite: Iterative Generative Modeling of Graphs](https://mlsanity.com/paper/1803.10459/) (2018)
- [Graph Normalizing Flows](https://mlsanity.com/paper/1905.13177/) (2019)
- [Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2004.06231/) (2020)
- [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022)
- [A Differential Approach to Inference in Bayesian Networks](https://mlsanity.com/paper/1301.3847/) (2013)
- [Directed Acyclic Graph Neural Networks](https://mlsanity.com/paper/2101.07965/) (2021)
- [GraphGDP: Generative Diffusion Processes for Permutation Invariant Graph Generation](https://mlsanity.com/paper/2212.01842/) (2022)
- [A Unified Approach for Learning the Parameters of Sum-Product Networks](https://mlsanity.com/paper/1601.00318/) (2016)
- [Bayesian Learning of Sum-Product Networks](https://mlsanity.com/paper/1905.10884/) (2019)
- [Tractability through Exchangeability: A New Perspective on Efficient Probabilistic Inference](https://mlsanity.com/paper/1401.1247/) (2014)
- [Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures](https://mlsanity.com/paper/1312.7857/) (2013)
- [Visualizing and Understanding Sum-Product Networks](https://mlsanity.com/paper/1608.08266/) (2016)
- [DAG-Recurrent Neural Networks For Scene Labeling](https://mlsanity.com/paper/1509.00552/) (2015)
- [Discriminative models for multi-instance problems with tree-structure](https://mlsanity.com/paper/1703.02868/) (2017)

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

- [GraphSPNs: Sum-Product Networks Benefit From Canonical Orderings](https://mlsanity.com/paper/2408.09451/) (2024)
- [Probabilistic Graph Circuits: Deep Generative Models for Tractable Probabilistic Inference over Graphs](https://mlsanity.com/paper/2503.12162/) (2025)
- [Sparse Probabilistic Graph Circuits](https://mlsanity.com/paper/2508.07763/) (2025)

## Abstract (arXiv)

Daily internet communication relies heavily on tree-structured graphs, embodied by popular data formats such as XML and JSON. However, many recent generative (probabilistic) models utilize neural networks to learn a probability distribution over undirected cyclic graphs. This assumption of a generic graph structure brings various computational challenges, and, more importantly, the presence of non-linearities in neural networks does not permit tractable probabilistic inference. We address these problems by proposing sum-product-set networks, an extension of probabilistic circuits from unstructured tensor data to tree-structured graph data. To this end, we use random finite sets to reflect a variable number of nodes and edges in the graph and to allow for exact and efficient inference. We demonstrate that our tractable model performs comparably to various intractable models based on neural networks.