Research map / Graph learning / GNN architectures
Sum-Product-Set Networks: Deep Tractable Models for Tree-Structured Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes sum-product-set networks, a tractable probabilistic circuit extension using random finite sets to model variable-size tree-structured graphs (JSON-like data) with exact marginal inference.
Problem
Learning probability distributions over tree-structured graphs with variable numbers of nodes and edges, while keeping exact and efficient probabilistic inference, which neural graph generative models lack.
Approach
Extends sum-product networks to tree-structured data by adding a set unit, built from random finite set theory (i.i.d. cluster model with Poisson-like cardinality), that models homogeneous nodes as random sets, enabling exact marginal queries over missing parts of the data graph.
Key results
- SPSN achieves average rank 2.38 across eight CTU datasets, versus 1.62 for GRU and HMIL, with accuracy close to the intractable NN models (e.g., 0.86 on cora, 0.84 on mutagenesis).
- On missing-value experiments, SPSN outperforms or matches NNs and keeps its accuracy longer on cora and webkp, using a single marginalization pass.
- SPSN is lower than the best NN on genes (0.95 vs 1.00 for GRU/HMIL).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SPSN instead of GRU | Tree-structured graph classifier · chess | test accuracy: 0.41$\pm$0.05 -> 0.39$\pm$0.03 | Hurt |
| Use SPSN instead of HMIL | Tree-structured graph classifier · citeseer | test accuracy: 0.75$\pm$0.01 -> 0.75$\pm$0.01 | No clear effect |
| Use SPSN instead of GRU | Tree-structured graph classifier · cora | test accuracy: 0.86$\pm$0.01 -> 0.86$\pm$0.01 | No clear effect |
| Use SPSN instead of GRU | Tree-structured graph classifier · genes | test accuracy: 1.00$\pm$0.01 -> 0.95$\pm$0.01 | Hurt |
| Use SPSN instead of GRU | Tree-structured graph classifier · hepatitis | test accuracy: 0.88$\pm$0.01 -> 0.88$\pm$0.02 | No clear effect |
| Use SPSN instead of MLP | Tree-structured graph classifier · mutagenesis | test accuracy: 0.84$\pm$0.02 -> 0.84$\pm$0.02 | No clear effect |
| Use SPSN instead of GRU | Tree-structured graph classifier · uwcse | test accuracy: 0.87$\pm$0.03 -> 0.84$\pm$0.02 | Hurt |
| Use SPSN instead of GRU | Tree-structured graph classifier · webkp | test accuracy: 0.82$\pm$0.01 -> 0.81$\pm$0.02 | Hurt |
| Use SPSN rather than NN models when test graphs contain missing values | Tree-structured graph classifier · cora and webkp with missing values | test accuracy robustness | Helped |
Surprising findings
- A sparse, tractable SPSN performs comparably to much denser, highly nonlinear tree-RNNs and HMIL despite having fewer connections.
Limitations
- The i.i.d. assumption on set elements ignores correlations among set members.
- SPSN has a small performance gap to the best NN models due to sparse connectivity within blocks.
- Experiments are limited to graph classification and missing-value robustness on eight relational datasets converted to JSON.
Experimental setup
Datasets: chess citeseer cora genes hepatitis mutagenesis uwcse webkp
Benchmarks: chess citeseer cora genes hepatitis mutagenesis uwcse webkp
Metrics: test accuracy average rank
Baselines: MLP GRU LSTM HMIL
Builds on: sum-product networks random finite sets hierarchical multiple-instance learning
Closest papers by meaning
- Tractable Probabilistic Graph Representation Learning with Graph-Induced Sum-Product Networks (ICLR 2024 · similarity 0.91)
- Maximum A Posteriori Inference in Sum-Product Networks (AAAI 2018 · similarity 0.88)
- Probabilistic Circuits for Variational Inference in Discrete Graphical Models (NeurIPS 2020 · similarity 0.87)
- Probabilistically Rewired Message-Passing Neural Networks (ICLR 2024 · similarity 0.87)
- On the Expressive Power of Tree-Structured Probabilistic Circuits (NeurIPS 2024 · similarity 0.87)
- Fine-grained Expressivity of Graph Neural Networks (NeurIPS 2023 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.