Research map / Graph learning / GNN architectures
Tractable Probabilistic Graph Representation Learning with Graph-Induced Sum-Product Networks
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 Graph-Induced Sum-Product Networks (GSPNs), hierarchies of tractable SPNs built on graph-induced computation trees that give a probabilistic, message-passing-style model for graph representation learning and missing-data queries.
Problem
Graph representation learning models typically cannot answer probabilistic queries, handle missing vertex attributes via marginalization, or exploit unlabeled data, while probabilistic graph models are intractable on cyclic graphs.
Approach
Build a hierarchy of Naive Bayes sum-product networks over each vertex's graph-induced computation tree, where each parent SPN's mixture priors are learnable transformations of its children's posterior sum-unit probabilities; trained by maximizing a pseudo log-likelihood, giving tractable marginals and message-passing-like end-to-end learning.
Key results
- On scarce supervision (0.1% labels), GSPN_U+DS is competitive with or better than GAE, DGI and GIN on the seven chemical regression tasks, ranking first or second on all.
- On missing-data NLL, GSPN_U beats the GMM on six of seven chemical datasets (e.g., benzene 4.17 vs 4.31); uracil is the exception where GMM is better (3.11 vs 3.17).
- On TU graph classification, GSPN_U+DS reaches 90.5 on REDDIT-B and 78.1 on COLLAB, improving over CGMM on all four datasets, but does not beat the best baselines (iCGMM, GIN) consistently.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use graph structure with GSPN_U instead of structure-agnostic GMM | GSPN_U · benzene (missing data) | NLL: 4.31 -> 4.17 | Helped |
| use graph structure with GSPN_U instead of structure-agnostic GMM | GSPN_U · ethanol (missing data) | NLL: 3.81 -> 3.77 | Helped |
| use graph structure with GSPN_U instead of structure-agnostic GMM | GSPN_U · malonaldehyde (missing data) | NLL: 3.93 -> 3.88 | Helped |
| use graph structure with GSPN_U instead of structure-agnostic GMM | GSPN_U · naphthalene (missing data) | NLL: 3.31 -> 3.18 | Helped |
| use graph structure with GSPN_U instead of structure-agnostic GMM | GSPN_U · salicylic acid (missing data) | NLL: 3.21 -> 3.06 | Helped |
| use graph structure with GSPN_U instead of structure-agnostic GMM | GSPN_U · toluene (missing data) | NLL: 3.59 -> 3.35 | Helped |
| use graph structure with GSPN_U instead of structure-agnostic GMM | GSPN_U · uracil (missing data) | NLL: 3.11 -> 3.17 | Hurt |
| add shortcut connections to the unsupervised embeddings (ablation) | GSPN_U+DS · NCI1 | accuracy: 76.5 -> 76.6 | Helped |
| add shortcut connections to the unsupervised embeddings (ablation) | GSPN_U+DS · REDDIT-BINARY | accuracy: 88.9 -> 90.5 | Helped |
| add shortcut connections to the unsupervised embeddings (ablation) | GSPN_U+DS · REDDIT-5K | accuracy: 52.3 -> 55.3 | Helped |
| add shortcut connections to the unsupervised embeddings (ablation) | GSPN_U+DS · COLLAB | accuracy: 75.7 -> 78.1 | Helped |
| use supervised global readout instead of unsupervised embeddings with DeepSets | GSPN graph classification · NCI1, REDDIT-BINARY, REDDIT-5K, COLLAB | accuracy | No clear effect |
Surprising findings
- GSPN_S global-pooling variant does not bring significant gains over GSPN_U+DS on graph classification, attributed to limited expressiveness of the global aggregation.
- GIN training was unstable with large batch sizes under scarce supervision, and GAE/DGI embeddings sometimes prevented DeepSets from converging.
Limitations
- Conditioning on the same realization of an observable variable in cyclic graphs may slightly bias the pseudo-likelihood.
- Neighborhood aggregation is kept simple (mean-type linear transform), limiting expressiveness for distinguishing non-isomorphic graphs.
- Cannot model edge types or edge attributes.
Experimental setup
Datasets: benzene ethanol naphthalene salicylic acid toluene malonaldehyde uracil ogbg-molpcba NCI1 REDDIT-BINARY REDDIT-MULTI-5K COLLAB
Benchmarks: benzene ethanol naphthalene salicylic acid toluene malonaldehyde uracil ogbg-molpcba NCI1 REDDIT-BINARY REDDIT-MULTI-5K COLLAB
Metrics: MAE AP NLL accuracy
Baselines: GIN GAE DGI GMM Gaussian DGCNN DiffPool ECC GraphSAGE CGMM E-CGMM iCGMM
Builds on: sum-product networks contextual graph Markov model DeepSets Deep Graph Infomax Graph Auto-Encoder
Closest papers by meaning
- Sum-Product-Set Networks: Deep Tractable Models for Tree-Structured Graphs (ICLR 2024 · similarity 0.91)
- Maximum A Posteriori Inference in Sum-Product Networks (AAAI 2018 · similarity 0.87)
- Almost Surely Asymptotically Constant Graph Neural Networks (NeurIPS 2024 · similarity 0.87)
- Probabilistically Rewired Message-Passing Neural Networks (ICLR 2024 · similarity 0.87)
- Learning Graph Representation via Graph Entropy Maximization (ICML 2024 · similarity 0.86)
- Covered Forest: Fine-grained generalization analysis of graph neural networks (ICML 2025 · similarity 0.86)
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.