# Online GNN Evaluation Under Test-time Graph Distribution Shifts

arXiv: https://arxiv.org/abs/2403.09953 · HTML: https://mlsanity.com/paper/2403.09953/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 49 references that are in the map.
- First posted on arXiv 15 Mar 2024.

## Builds on (most cited first, 30 of 39)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [A Baseline for Detecting Misclassified and Out-of-Distribution Examples in Neural Networks](https://mlsanity.com/paper/1610.02136/) (2016)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Unifying Large Language Models and Knowledge Graphs: A Roadmap](https://mlsanity.com/paper/2306.08302/) (2023)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [Graph Neural Networks for Graphs with Heterophily: A Survey](https://mlsanity.com/paper/2202.07082/) (2022)
- [Handling Distribution Shifts on Graphs: An Invariance Perspective](https://mlsanity.com/paper/2202.02466/) (2022)
- [Leveraging Unlabeled Data to Predict Out-of-Distribution Performance](https://mlsanity.com/paper/2201.04234/) (2022)
- [A Survey on Graph Neural Networks for Time Series: Forecasting, Classification, Imputation, and Anomaly Detection](https://mlsanity.com/paper/2307.03759/) (2023)
- [Predicting with Confidence on Unseen Distributions](https://mlsanity.com/paper/2107.03315/) (2021)
- [Are Labels Always Necessary for Classifier Accuracy Evaluation?](https://mlsanity.com/paper/2007.02915/) (2020)
- [Out-Of-Distribution Generalization on Graphs: A Survey](https://mlsanity.com/paper/2202.07987/) (2022)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training Data](https://mlsanity.com/paper/2108.01099/) (2021)
- [Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data](https://mlsanity.com/paper/2306.02664/) (2023)
- [Rethinking and Scaling Up Graph Contrastive Learning: An Extremely Efficient Approach with Group Discrimination](https://mlsanity.com/paper/2206.01535/) (2022)
- [Empowering Graph Representation Learning with Test-Time Graph Transformation](https://mlsanity.com/paper/2210.03561/) (2022)
- [What Does Rotation Prediction Tell Us about Classifier Accuracy under Varying Testing Environments?](https://mlsanity.com/paper/2106.05961/) (2021)
- [Beyond Smoothing: Unsupervised Graph Representation Learning with Edge Heterophily Discriminating](https://mlsanity.com/paper/2211.14065/) (2022)
- [Predicting Out-of-Distribution Error with the Projection Norm](https://mlsanity.com/paper/2202.05834/) (2022)
- [DANE: Domain Adaptive Network Embedding](https://mlsanity.com/paper/1906.00684/) (2019)
- [Towards Self-Interpretable Graph-Level Anomaly Detection](https://mlsanity.com/paper/2310.16520/) (2023)
- [ChatRule: Mining Logical Rules with Large Language Models for Knowledge Graph Reasoning](https://mlsanity.com/paper/2309.01538/) (2023)
- [Learning Strong Graph Neural Networks with Weak Information](https://mlsanity.com/paper/2305.18457/) (2023)

## Built on by (most cited first, 12 of 12)

- [A Label-Free Heterophily-Guided Approach for Unsupervised Graph Fraud Detection](https://mlsanity.com/paper/2502.13308/) (2025)
- [BiMark: Unbiased Multilayer Watermarking for Large Language Models](https://mlsanity.com/paper/2506.21602/) (2025)
- [A Survey of Deep Graph Learning under Distribution Shifts: from Graph Out-of-Distribution Generalization to Adaptation](https://mlsanity.com/paper/2410.19265/) (2024)
- [Dynamic Graph Unlearning: A General and Efficient Post-Processing Method via Gradient Transformation](https://mlsanity.com/paper/2405.14407/) (2024)
- [A Survey of Generalization of Graph Anomaly Detection: From Transfer Learning to Foundation Models](https://mlsanity.com/paper/2509.06609/) (2025)
- [Shapley-Guided Utility Learning for Effective Graph Inference Data Valuation](https://mlsanity.com/paper/2503.18195/) (2025)
- [Wide & Deep Learning for Node Classification](https://mlsanity.com/paper/2505.02020/) (2025)
- [M2LLM: Multi-view Molecular Representation Learning with Large Language Models](https://mlsanity.com/paper/2508.08657/) (2025)
- [Test-time GNN Model Evaluation on Dynamic Graphs](https://mlsanity.com/paper/2509.23816/) (2025)
- [Does Homophily Help in Robust Test-time Node Classification?](https://mlsanity.com/paper/2510.22289/) (2025)
- [From Subtle to Significant: Prompt-Driven Self-Improving Optimization in Test-Time Graph OOD Detection](https://mlsanity.com/paper/2602.17342/) (2026)
- [GFMate: Empowering Graph Foundation Models with Test-time Prompt Tuning](https://mlsanity.com/paper/2605.14809/) (2026)

## Abstract (arXiv)

Evaluating the performance of a well-trained GNN model on real-world graphs is a pivotal step for reliable GNN online deployment and serving. Due to a lack of test node labels and unknown potential training-test graph data distribution shifts, conventional model evaluation encounters limitations in calculating performance metrics (e.g., test error) and measuring graph data-level discrepancies, particularly when the training graph used for developing GNNs remains unobserved during test time. In this paper, we study a new research problem, online GNN evaluation, which aims to provide valuable insights into the well-trained GNNs's ability to effectively generalize to real-world unlabeled graphs under the test-time graph distribution shifts. Concretely, we develop an effective learning behavior discrepancy score, dubbed LeBeD, to estimate the test-time generalization errors of well-trained GNN models. Through a novel GNN re-training strategy with a parameter-free optimality criterion, the proposed LeBeD comprehensively integrates learning behavior discrepancies from both node prediction and structure reconstruction perspectives. This enables the effective evaluation of the well-trained GNNs' ability to capture test node semantics and structural representations, making it an expressive metric for estimating the generalization error in online GNN evaluation. Extensive experiments on real-world test graphs under diverse graph distribution shifts could verify the effectiveness of the proposed method, revealing its strong correlation with ground-truth test errors on various well-trained GNN models.