Research map / Graph learning / Graph self-supervised learning
Online GNN Evaluation Under Test-time Graph Distribution Shifts
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 LeBed, a parameter-free learning-behavior discrepancy score that estimates a well-trained GNN's test error on unlabeled, distribution-shifted test graphs without access to the training graph, by re-training on the test graph with pseudo-labels and measuring weight distance.
Problem
Estimating the test error of a well-trained GNN on unlabeled real-world test graphs under unknown training-test distribution shifts, when the training graph is inaccessible at deployment time.
Approach
Re-train a fresh GNN on the test graph using the deployed model's pseudo-labels as supervision, stop re-training with a parameter-free structure-reconstruction criterion (cosine-similarity adjacency reconstruction discrepancy), and use the L2 distance between the re-trained and the well-trained weights as a score proportional to test error.
Key results
- On Amazon-Photo with GCN, LeBed reaches Spearman rho=0.90 and R^2=0.730 with ground-truth test error, outperforming all baselines.
- Averaged over GNNs, LeBed achieves rho=0.76 on Cora versus at most 0.52 for the best baseline's average, and rho=0.52 on Citationv2 and OGB-arxiv temporal shifts reported as 0.56.
- Many baseline methods (ATC, threshold-based) show negative correlations with test error on several settings, while LeBed remains positive across shift types.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the D_stru.-based parameter-free optimality criterion instead of 20 fixed retraining iterations (ablation) | LeBed with GCN · ACMv9 | Spearman's ρ: 0.27 -> 0.52 | Helped |
| Use the D_stru.-based parameter-free optimality criterion instead of 200 fixed retraining iterations (ablation) | LeBed with GCN · ACMv9 | Spearman's ρ: 0.13 -> 0.52 | Helped |
| Use the D_stru.-based parameter-free optimality criterion instead of 20 fixed retraining iterations (ablation) | LeBed with SAGE · ACMv9 | Spearman's ρ: 0.26 -> 0.61 | Helped |
| Use the D_stru.-based parameter-free optimality criterion instead of 200 fixed retraining iterations (ablation) | LeBed with SAGE · ACMv9 | Spearman's ρ: -0.55 -> 0.61 | Helped |
Surprising findings
- Several confidence-based baselines (ATC-MC, threshold-based) yield negative correlations with test error on some datasets, contrary to expectation.
- The parameter-free structure reconstruction criterion removes the need for a fixed iteration count; without it, correlations degrade for later iterations on ACMv9 (e.g., SAGE rho drops from 0.61 to -0.55 at 200 iterations).
Limitations
- Assumes label space is unchanged between training and test graphs (covariate shift only).
- Correlations are weaker under domain and temporal shifts (e.g., rho about 0.52 on Citationv2 and OGB-arxiv).
- Baselines are adapted from CNN image-evaluation methods, since no established graph baselines exist; test sets are synthetically expanded from raw graphs.
Experimental setup
Datasets: Cora Amazon-Photo ACMv9 DBLPv8 Citationv2 OGB-arxiv
Benchmarks: Cora Amazon-Photo ACMv9 DBLPv8 Citationv2 OGB-arxiv
Metrics: Spearman rank correlation rho R^2 linear fit
Baselines: ConfScore Entropy ATC-MC ATC-NE Threshold-based method (tau=0.7, 0.8, 0.9)
Builds on: ATC (average thresholded confidence) Predicting model generalization error (Deng et al.; Yu et al. projection norm) GCN GraphSAGE GAT GIN
Closest papers by meaning
- Improving GNN Calibration with Discriminative Ability: Insights and Strategies (AAAI 2024 · similarity 0.88)
- Test-Time Graph Neural Dataset Search With Generative Projection (ICML 2025 · similarity 0.88)
- Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification (NeurIPS 2024 · similarity 0.88)
- Learning to Reweight for Generalizable Graph Neural Network (AAAI 2024 · similarity 0.88)
- Generalization of Graph Neural Networks Is Robust to Model Mismatch (AAAI 2025 · similarity 0.88)
- Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence (ICML 2025 · 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.