# Tractable Probabilistic Graph Representation Learning with Graph-Induced Sum-Product Networks

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 72 references that are in the map.
- First posted on arXiv 17 May 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [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)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Aleatoric and Epistemic Uncertainty in Machine Learning: An Introduction to Concepts and Methods](https://mlsanity.com/paper/1910.09457/) (2019)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [Deep Learning on Graphs: A Survey](https://mlsanity.com/paper/1812.04202/) (2018)
- [Learning Convolutional Neural Networks for Graphs](https://mlsanity.com/paper/1605.05273/) (2016)
- [Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs](https://mlsanity.com/paper/1704.02901/) (2017)
- [Highway Networks](https://mlsanity.com/paper/1505.00387/) (2015)
- [Embracing Imperfect Datasets: A Review of Deep Learning Solutions for Medical Image Segmentation](https://mlsanity.com/paper/1908.10454/) (2019)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [A Gentle Introduction to Deep Learning for Graphs](https://mlsanity.com/paper/1912.12693/) (2019)
- [A Differential Approach to Inference in Bayesian Networks](https://mlsanity.com/paper/1301.3847/) (2013)
- [GMNN: Graph Markov Neural Networks](https://mlsanity.com/paper/1905.06214/) (2019)
- [On the Unreasonable Effectiveness of Feature propagation in Learning on Graphs with Missing Node Features](https://mlsanity.com/paper/2111.12128/) (2021)
- [ASGN: An Active Semi-supervised Graph Neural Network for Molecular Property Prediction](https://mlsanity.com/paper/2007.03196/) (2020)
- [GraphWorld: Fake Graphs Bring Real Insights for GNNs](https://mlsanity.com/paper/2203.00112/) (2022)
- [Graph Convolutional Networks for Graphs Containing Missing Features](https://mlsanity.com/paper/2007.04583/) (2020)
- [Learning on Attribute-Missing Graphs](https://mlsanity.com/paper/2011.01623/) (2020)

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

- [Cooperative Graph Neural Networks](https://mlsanity.com/paper/2310.01267/) (2023)
- [Tractable Representation Learning with Probabilistic Circuits](https://mlsanity.com/paper/2507.04385/) (2025)
- [Sum-Product-Set Networks: Deep Tractable Models for Tree-Structured Graphs](https://mlsanity.com/paper/2408.07394/) (2024)
- [GraphSPNs: Sum-Product Networks Benefit From Canonical Orderings](https://mlsanity.com/paper/2408.09451/) (2024)
- [Early-Exit Graph Neural Networks](https://mlsanity.com/paper/2505.18088/) (2025)
- [Rethinking GNNs and Missing Features: Challenges, Evaluation and a Robust Solution](https://mlsanity.com/paper/2601.04855/) (2026)
- [Probabilistic Graph Circuits: Deep Generative Models for Tractable Probabilistic Inference over Graphs](https://mlsanity.com/paper/2503.12162/) (2025)

## Abstract (arXiv)

We introduce Graph-Induced Sum-Product Networks (GSPNs), a new probabilistic framework for graph representation learning that can tractably answer probabilistic queries. Inspired by the computational trees induced by vertices in the context of message-passing neural networks, we build hierarchies of sum-product networks (SPNs) where the parameters of a parent SPN are learnable transformations of the a-posterior mixing probabilities of its children's sum units. Due to weight sharing and the tree-shaped computation graphs of GSPNs, we obtain the efficiency and efficacy of deep graph networks with the additional advantages of a probabilistic model. We show the model's competitiveness on scarce supervision scenarios, under missing data, and for graph classification in comparison to popular neural models. We complement the experiments with qualitative analyses on hyper-parameters and the model's ability to answer probabilistic queries.