# Sparse Probabilistic Graph Circuits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 31 references that are in the map.
- First posted on arXiv 11 Aug 2025.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [MolGAN: An implicit generative model for small molecular graphs](https://mlsanity.com/paper/1805.11973/) (2018)
- [GraphAF: a Flow-based Autoregressive Model for Molecular Graph Generation](https://mlsanity.com/paper/2001.09382/) (2020)
- [GuacaMol: Benchmarking Models for De Novo Molecular Design](https://mlsanity.com/paper/1811.09621/) (2018)
- [Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations](https://mlsanity.com/paper/2202.02514/) (2022)
- [Molecular Sets (MOSES): A Benchmarking Platform for Molecular Generation Models](https://mlsanity.com/paper/1811.12823/) (2018)
- [Permutation Invariant Graph Generation via Score-Based Generative Modeling](https://mlsanity.com/paper/2003.00638/) (2020)
- [Fr'echet ChemNet Distance: A metric for generative models for molecules in drug discovery](https://mlsanity.com/paper/1803.09518/) (2018)
- [MoFlow: An Invertible Flow Model for Generating Molecular Graphs](https://mlsanity.com/paper/2006.10137/) (2020)
- [GraphDF: A Discrete Flow Model for Molecular Graph Generation](https://mlsanity.com/paper/2102.01189/) (2021)
- [Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2004.06231/) (2020)
- [SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators](https://mlsanity.com/paper/2204.01613/) (2022)
- [GraphEBM: Molecular Graph Generation with Energy-Based Models](https://mlsanity.com/paper/2102.00546/) (2021)
- [Autoregressive Diffusion Model for Graph Generation](https://mlsanity.com/paper/2307.08849/) (2023)
- [Message-passing neural networks for high-throughput polymer screening](https://mlsanity.com/paper/1807.10363/) (2018)
- [Sum-Product-Set Networks: Deep Tractable Models for Tree-Structured Graphs](https://mlsanity.com/paper/2408.07394/) (2024)
- [Large Generative Graph Models](https://mlsanity.com/paper/2406.05109/) (2024)
- [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)

## Abstract (arXiv)

Deep generative models (DGMs) for graphs achieve impressively high expressive power thanks to very efficient and scalable neural networks. However, these networks contain non-linearities that prevent analytical computation of many standard probabilistic inference queries, i.e., these DGMs are considered intractable. While recently proposed Probabilistic Graph Circuits (PGCs) address this issue by enabling tractable probabilistic inference, they operate on dense graph representations with O(n2) complexity for graphs with n nodes and m edges. To address this scalability issue, we introduce Sparse PGCs, a new class of tractable generative models that operate directly on sparse graph representation, reducing the complexity to O(n + m), which is particularly beneficial for m ll n2. In the context of de novo drug design, we empirically demonstrate that SPGCs retain exact inference capabilities, improve memory efficiency and inference speed, and match the performance of intractable DGMs in key metrics.