# Probabilistic Graph Circuits: Deep Generative Models for Tractable Probabilistic Inference over Graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 57 of its 87 references that are in the map.
- First posted on arXiv 15 Mar 2025.

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

- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Glow: Generative Flow with Invertible 1x1 Convolutions](https://mlsanity.com/paper/1807.03039/) (2018)
- [Learning to Simulate Complex Physics with Graph Networks](https://mlsanity.com/paper/2002.09405/) (2020)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [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)
- [Deep Learning on Graphs: A Survey](https://mlsanity.com/paper/1812.04202/) (2018)
- [GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders](https://mlsanity.com/paper/1802.03480/) (2018)
- [GraphAF: a Flow-based Autoregressive Model for Molecular Graph Generation](https://mlsanity.com/paper/2001.09382/) (2020)
- [Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations](https://mlsanity.com/paper/2202.02514/) (2022)
- [Permutation Invariant Graph Generation via Score-Based Generative Modeling](https://mlsanity.com/paper/2003.00638/) (2020)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [Fr'echet ChemNet Distance: A metric for generative models for molecules in drug discovery](https://mlsanity.com/paper/1803.09518/) (2018)
- [Constrained Graph Variational Autoencoders for Molecule Design](https://mlsanity.com/paper/1805.09076/) (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)
- [Relational Pooling for Graph Representations](https://mlsanity.com/paper/1903.02541/) (2019)
- [NetGAN: Generating Graphs via Random Walks](https://mlsanity.com/paper/1803.00816/) (2018)
- [GraphNVP: An Invertible Flow Model for Generating Molecular Graphs](https://mlsanity.com/paper/1905.11600/) (2019)
- [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)
- [SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators](https://mlsanity.com/paper/2204.01613/) (2022)
- [A Systematic Survey on Deep Generative Models for Graph Generation](https://mlsanity.com/paper/2007.06686/) (2020)
- [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)
- [Generative Diffusion Models on Graphs: Methods and Applications](https://mlsanity.com/paper/2302.02591/) (2023)

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

- [Sparse Probabilistic Graph Circuits](https://mlsanity.com/paper/2508.07763/) (2025)

## Abstract (arXiv)

Deep generative models (DGMs) have recently demonstrated remarkable success in capturing complex probability distributions over graphs. Although their excellent performance is attributed to powerful and scalable deep neural networks, it is, at the same time, exactly the presence of these highly non-linear transformations that makes DGMs intractable. Indeed, despite representing probability distributions, intractable DGMs deny probabilistic foundations by their inability to answer even the most basic inference queries without approximations or design choices specific to a very narrow range of queries. To address this limitation, we propose probabilistic graph circuits (PGCs), a framework of tractable DGMs that provide exact and efficient probabilistic inference over (arbitrary parts of) graphs. Nonetheless, achieving both exactness and efficiency is challenging in the permutation-invariant setting of graphs. We design PGCs that are inherently invariant and satisfy these two requirements, yet at the cost of low expressive power. Therefore, we investigate two alternative strategies to achieve the invariance: the first sacrifices the efficiency, and the second sacrifices the exactness. We demonstrate that ignoring the permutation invariance can have severe consequences in anomaly detection, and that the latter approach is competitive with, and sometimes better than, existing intractable DGMs in the context of molecular graph generation.