Research map / Graph learning / GNN architectures
Graph Neural Networks with a Distribution of Parametrized 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 EMGNN, which models a GNN over a distribution of parametrized graphs and estimates that distribution with an EM algorithm using MCMC sampling and PAC-Bayesian Gibbs posteriors, evaluated on heterogeneous and homogeneous node classification and molecular graph regression.
Problem
Graphs used for GNN training are often noisy, have missing edges, or uninformative edge weights, so a single observed graph is only one possible realization; the paper targets robust GNN learning under graph uncertainty.
Approach
Parametrize multiple graphs by latent variables with an unknown distribution, reformulate training as maximum likelihood, and alternate EM steps in which the distribution over graph parameters is a PAC-Bayesian Gibbs posterior estimated via MCMC while the GNN is trained on sampled graphs weighted by (p_t - p_0)/q.
Key results
- On heterogeneous node classification, EM-GCN[PT] achieves the best Micro-F1 on IMDB (64.78) and DBLP (95.06) and Macro-F1 on IMDB (63.36), DBLP (94.41), and ACM (92.78).
- On limited-label homogeneous node classification, EM-GCN achieves the best results on Cora (20 labels, 82.24), Citeseer (10 and 20 labels) and all Pubmed settings, outperforming BGCN and DropEdge.
- On heterophilic graphs, EM-ACM reaches 88.38 on Texas and 87.06 on Wisconsin, above ACM-GCN+ (86.76 and 86.86).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| train EM-GCN with a distribution of parametrized graphs | GCN · heterogeneous node classification on IMDB | Micro-F1: 63.54 $\pm$ 1.10 -> 64.78 $\pm$ 1.24 | Helped |
| train EM-GCN with a distribution of parametrized graphs | GCN · heterogeneous node classification on ACM | Macro-F1: 92.68 $\pm$ 0.36 -> 92.78 $\pm$ 0.26 | Helped |
| train EM-GCN with a distribution of parametrized graphs | GCN · heterogeneous node classification on DBLP | Micro-F1: 94.86 $\pm$ 0.14 -> 95.06 $\pm$ 0.39 | Helped |
| use q=p_t instead of a uniform proposal q (ablation) | EM-GCN with uniform p_0 and p'_{0,t} · heterogeneous node classification, across IMDB, ACM, and DBLP | Micro-F1 and Macro-F1 | Mixed |
| use a uniform p_0 instead of delta_{lambda_0} (ablation) | EM-GCN[PT]/EM-GCN[PO] versus EM-GCN[PD]/EM-GCN[PH] · heterogeneous node classification | Micro-F1 and Macro-F1 | Helped |
| add loss increases for low-probability ('bad') graph parameters (ablation) | EM-GCN · heterogeneous node classification | Micro-F1 and Macro-F1 | Helped |
| train with a distribution of parametrized graphs | GCN · node classification on Pubmed, 5 labels | accuracy: 71.69 $\pm$ 0.50 -> 74.03 $\pm$ 0.55 | Helped |
| train with a distribution of parametrized graphs | GCN · node classification on Citeseer, 20 labels | accuracy: 72.11 $\pm$ 0.40 -> 72.13 $\pm$ 0.96 | No clear effect |
| use EM-GCN with ACM-GCN+ as backbone | ACM-GCN+ · heterophilic node classification, Texas and Wisconsin | accuracy: 86.76 $\pm$ 4.26 -> 88.38 $\pm$ 5.14; 86.86 $\pm$ 2.91 -> 87.06 $\pm$ 2.51 | Helped |
| use EM-GCN with ACM-GCN+ as backbone | ACM-GCN+ · heterophilic node classification on Cornell | accuracy: 85.40 $\pm$ 7.00 -> 85.14 $\pm$ 6.54 | Hurt |
| train EM-GCN* on multiple molecular graph realizations | GCN · FreeSolv, random split | test RMSE: 1.157 $\pm$ 0.215 -> 0.936 $\pm$ 0.162 | Helped |
| train EM-GCN* on multiple molecular graph realizations | GCN · ESOL, random split | test RMSE: 0.652 $\pm$ 0.073 -> 0.606 $\pm$ 0.041 | Helped |
Surprising findings
- EM-GCN[PT] often outperforms attention-based heterogeneous GNNs (GAT, Simple-HGN, SeHGNN, GTN) without using any attention mechanism.
- Plain GCN performs competitively with heterogeneous-graph-specific models under appropriate settings.
Limitations
- Relies on a discretized, small parameter space Λ so precomputed graphs and losses fit in memory; space complexity scales with |Λ|(|E|+|V|).
- Theoretical guarantees require convexity, Lipschitz, and smoothness assumptions on the loss, and the approximation of log C(θ) is only checked numerically.
Experimental setup
Datasets: IMDB ACM DBLP Cora Citeseer Pubmed Texas Cornell Wisconsin FreeSolv ESOL Lipophilicity
Benchmarks: IMDB ACM DBLP Cora Citeseer Pubmed Texas Wisconsin Cornell FreeSolv ESOL Lipophilicity
Metrics: Micro-F1 Macro-F1 RMSE
Baselines: GCN GAT GTN Simple-HGN SeHGNN BGCN DropEdge RSGNN ACM-GCN+ ACMP Weave MPNN
Builds on: GCN GAT BGCN DropEdge PAC-Bayesian framework
Closest papers by meaning
- Learning Latent Graph Structures and their Uncertainty (ICML 2025 · similarity 0.88)
- Improving Graph Neural Networks by Learning Continuous Edge Directions (ICLR 2025 · similarity 0.87)
- Accurate and Scalable Estimation of Epistemic Uncertainty for Graph Neural Networks (ICLR 2024 · similarity 0.87)
- Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory (ICML 2025 · similarity 0.87)
- Almost Surely Asymptotically Constant Graph Neural Networks (NeurIPS 2024 · similarity 0.86)
- Uncertainty Estimation on Graphs with Structure Informed Stochastic Partial Differential Equations (NeurIPS 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.