Research map / Graph learning / Graph self-supervised learning
Nonparametric Teaching for Graph Property Learners
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 GraNT, a greedy example-selection teacher grounded in nonparametric teaching that selects graphs with largest GCN-vs-target discrepancy, cutting GCN training time by 31-47% on graph- and node-level tasks while keeping test performance.
Problem
Training graph property learners such as GCNs is expensive, especially on large graphs; existing nonparametric teaching theory ignores graph structure and assumes parameter-free gradient dynamics differ from GCN training.
Approach
Reinterpret GCN training through nonparametric teaching: show the parameter-space gradient with graph structure, via dynamic GNTK, converges to the structure-aware canonical kernel of functional gradient descent, then use a greedy teacher that selects graphs (or batches) with the largest prediction discrepancy.
Key results
- GraNT (B) reduces wallclock training time by 36.62% on ZINC (graph-level regression) and 38.19% on ogbg-molpcba (graph-level classification) relative to standard training, with comparable test MAE/AP.
- On node-level synthetic datasets, GraNT reduces training time by 30.97% (gen-reg) and 47.30% (gen-cls), with gen-cls ROC-AUC 0.9157 vs 0.9150 without GraNT.
- On QM9, GraNT (B) reached MAE 0.0051 in 6392s versus 9654.81s without GraNT and lower than AL-3DGraph variants in time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GraNT batch selection instead of training without GraNT | GCN · ZINC | training time: 33033.82 -> 20935.24; -36.62% | Helped |
| Use GraNT batch selection instead of training without GraNT | GCN · ogbg-molhiv | ROC-AUC: 0.7572$\pm$0.0005 -> 0.7676$\pm$0.0036 | Helped |
| Use GraNT batch selection instead of training without GraNT | GCN · ogbg-molpcba | AP: 0.3270$\pm$0.0000 -> 0.3358$\pm$0.0001 | Helped |
| Use GraNT batch selection instead of training without GraNT | GCN · gen-reg | MAE: 0.0007$\pm$0.0001 -> 0.0007$\pm$0.0001 | No clear effect |
| Use GraNT batch selection instead of training without GraNT | GCN · gen-cls | ROC-AUC: 0.9150$\pm$0.0024 -> 0.9157$\pm$0.0013 | No clear effect |
| Select individual graphs with the largest prediction discrepancies rather than batches | GraNT (S) · ogbg-molhiv | ROC-AUC: 0.7572$\pm$0.0005 -> 0.7705$\pm$0.0027 | Helped |
| Vary start-ratio from full to 0.05 (ablation) | GraNT (B) · QM9 | training time (s): 9654.81 -> 6392.26 | Helped |
| Vary start-ratio from full to 0.05 (ablation) | GraNT (B) · QM9 | MAE: 0.0051 -> 0.0051 | No clear effect |
| Vary start-ratio from full to 0.05 (ablation) | GraNT (B) · ogbg-molhiv | ROC-AUC: 0.7546 -> 0.7572 | No clear effect |
| Vary start-ratio from full to 0.05 (ablation) | GraNT (B) · ogbg-molhiv | training time (s): 2163.5 -> 1362.09 | Helped |
| Vary start-ratio from full to 0.05 (ablation) | GraNT (B) · gen-cls | ROC-AUC: 0.9150 -> 0.9157 | Helped |
| Vary start-ratio from full to 0.8 (ablation) | GraNT (B) · gen-cls | training time (s): 11662.25 -> 13153.81 | Hurt |
Surprising findings
- GraNT (B) at ogbg-molhiv reached ROC-AUC 0.7676 versus 0.7572 without GraNT while reducing training time by 32.64%.
Limitations
- Selection relies on access to target values f*(G) for all graphs in the dense training pool, which is assumed rather than tested in a realistic setting.
- Theoretical results rely on assumptions (convex loss, bounded kernel, infinite-width-like behavior) that are not fully verified in practice.
- Reported ROC-AUC curves are jagged due to label imbalance, so classification gains are less clear-cut.
Experimental setup
Datasets: QM9 ZINC ogbg-molhiv ogbg-molpcba gen-reg gen-cls
Benchmarks: QM9 ZINC ogbg-molhiv ogbg-molpcba gen-reg gen-cls
Metrics: training time (s) MAE ROC-AUC AP validation loss
Baselines: Without GraNT (standard GCN training) AL-3DGraph GCN+Virtual Node GMoE-GCN GMoE-GIN GDeR-GCN GDeR-PNA
Builds on: nonparametric teaching iterative machine teaching graph neural tangent kernel GCN
Closest papers by meaning
- Curriculum Learning for Graph Neural Networks: Which Edges Should We Learn First (NeurIPS 2023 · similarity 0.87)
- Distilling Graph Geometry: Knowledge Gap from GNNs to MLPs (NeurIPS 2026 · similarity 0.87)
- Beyond the Golden Teacher: Enhancing Graph Learning through LLM-GNN Co-teaching (NeurIPS 2026 · similarity 0.87)
- No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets (ICML 2025 · similarity 0.86)
- How Graph Neural Networks Learn: Lessons from Training Dynamics (ICML 2024 · similarity 0.86)
- On the Interplay between Graph Structure and Learning Algorithms in 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.