Research map / Graph learning / GNN architectures
Graph Classification via Reference Distribution Learning: Theory and Practice
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 GRDL, which classifies graphs by treating GNN node embeddings as discrete distributions and measuring squared MMD to learned per-class reference distributions (no global pooling), and derives generalization bounds showing it beats GIN with global pooling.
Problem
Graph classification relies on global pooling that loses structural/semantic information, while graph kernels and optimal-transport graph models are computationally expensive.
Approach
Treat each graph's node embedding matrix as an empirical discrete distribution and classify it by negative squared MMD (Gaussian kernel with learnable bandwidth) to K learned reference distributions, trained end-to-end with cross-entropy plus a reference-discrimination loss; the first generalization analysis for this type of model.
Key results
- GRDL reaches 77.9% average accuracy over eight benchmarks, top among compared methods (GMT/SEP ~75.8, GIN 73.6).
- On large imbalanced datasets GRDL reports AUC-ROC 85.1 (PC-3), 81.4 (MCF-7), 79.8 (ogbg-molhiv), above GIN (84.6, 80.6, 77.8).
- GRDL is reported to be roughly 10x faster than OT-GNN and TFGW per epoch and per-graph prediction (average 1.4e-3 s vs 21.6e-3 s and 64.6e-3 s).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace GIN global pooling with GRDL reference distributions | GIN graph classifier · PROTEINS | testing accuracy: 76.2 -> 82.6 | Helped |
| replace GIN global pooling with GRDL reference distributions | GIN graph classifier · IMDB-B | testing accuracy: 64.3 -> 74.8 | Helped |
| replace GIN global pooling with GRDL reference distributions | GIN graph classifier · NCI1 | testing accuracy: 82.2 -> 80.4 | Hurt |
| replace MMD with Wasserstein distance (ablation) | GRDL · eight graph classification benchmarks | accuracy (%): MUTAG 92.1$\pm$5.9 -> 90.8$\pm$4.6; PROTEINS 82.6$\pm$1.2 -> 82.1$\pm$0.9; IMDB-M 52.9$\pm$1.8 -> 53.1$\pm$0.9 | Mixed |
| replace MMD with Sinkhorn divergence (ablation) | GRDL · eight graph classification benchmarks | accuracy (%): NCI1 80.4$\pm$0.8 -> 81.2$\pm$1.5; PTC-MR 68.3$\pm$5.4 -> 64.2$\pm$3.2; BZR 92.0$\pm$1.1 -> 91.6$\pm$1.3 | Mixed |
| increase from 1 to 2 references per class (ablation) | GRDL · MUTAG | accuracy (%): 92.1$\pm$5.9 -> 91.5$\pm$4.8 | Hurt |
| increase from 1 to 3 references per class (ablation) | GRDL · PROTEINS | accuracy (%): 82.6$\pm$1.2 -> 81.3$\pm$2.9 | Hurt |
| fix θ at 10⁻² instead of learning it (ablation) | GRDL · IMDB-B | accuracy (%): 74.8$\pm$2.0 -> 72.8$\pm$1.8 | Hurt |
| remove the reference discriminativeness constraint (ablation) | GRDL · BZR | accuracy (%): 92.0$\pm$1.1 -> 89.5$\pm$2.3 | Hurt |
| sum-pool node embeddings and remove the reference discriminativeness constraint (ablation) | GRDL · PROTEINS | accuracy (%): 82.6$\pm$1.2 -> 78.4$\pm$0.6 | Hurt |
| regularize reference norms (ablation) | GRDL · IMDB-M | accuracy (%): 52.9$\pm$1.8 -> 48.3$\pm$1.6 | Hurt |
| set Gaussian-kernel θ to 1 instead of learning it (ablation) | GRDL · MUTAG | accuracy: 0.9113 -> 0.8254 | Hurt |
Surprising findings
- Using one reference per class was empirically best; multiple references per class (GRDL-2, GRDL-3) reduced accuracy.
- Regularizing the reference norm hurt accuracy, contrary to the expectation that it would tighten generalization.
Limitations
- On some benchmarks such as NCI1, GRDL does not outperform the baseline (e.g., GIN and WL kernels).
- Generalization bound is loose in practice and relies on Lipschitz and norm-constraint assumptions; the bound uses assumptions (fixed theta) that differ from the learned-theta training.
- Theory covers GIN-style message passing; other GNNs are only claimed to be adaptable.
Experimental setup
Datasets: MUTAG PROTEINS NCI1 IMDB-B IMDB-M PTC-MR BZR COLLAB PC-3 MCF-7 ogbg-molhiv
Benchmarks: MUTAG PROTEINS NCI1 IMDB-B IMDB-M PTC-MR BZR COLLAB PC-3 MCF-7 ogbg-molhiv
Metrics: classification accuracy AUC-ROC training time per epoch prediction time per graph
Baselines: GIN DropGIN DIFFPOOL PATCHY-SAN SEP GMT MinCutPool ASAP WitTopoPool OT-GNN TFGW WEGL
Builds on: GIN maximum mean discrepancy optimal transport graph classification (OT-GNN)
Closest papers by meaning
- OpenGSL: A Comprehensive Benchmark for Graph Structure Learning (NeurIPS 2023 · similarity 0.91)
- Exploring Consistency in Graph Representations: from Graph Kernels to Graph Neural Networks (NeurIPS 2024 · similarity 0.90)
- Core Knowledge Learning Framework for Graph (AAAI 2025 · similarity 0.89)
- Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification (NeurIPS 2024 · similarity 0.89)
- On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective (NeurIPS 2025 · similarity 0.89)
- Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence (ICML 2025 · similarity 0.89)
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.