Online GNN Evaluation Under Test-time Graph Distribution Shifts

Evaluating the performance of a well-trained <PRE_TAG>GNN model</POST_TAG> 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 <PRE_TAG>GNN evaluation</POST_TAG>, 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 <PRE_TAG>generalization errors</POST_TAG> of well-trained <PRE_TAG>GNN model</POST_TAG>s. Through a novel <PRE_TAG>GNN re-training strategy</POST_TAG> 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 <PRE_TAG>test errors</POST_TAG> on various well-trained <PRE_TAG>GNN model</POST_TAG>s.