Online GNN Evaluation Under Test-time Graph Distribution Shifts
Authors: Xin Zheng
Dongjin Song
Qingsong Wen
Bo Du
Shirui Pan
Venue: ICLR 2024 spotlight (2024)
Keywords: Graph neural networks
Model evaluation
Distribution shift
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: 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.

Published as a conference paper at ICLR 2024
ONLINE GNN EVALUATION GRAPH DISTRIBUTION SHIFTS
UNDER
TEST-TIME
Xin Zheng Monash University Melbourne, Australia xin. zhengemonash.edd
Dongjin Song
University of Connecticut
Storrs, USA dongjin wwwgsuconn. edu
Qingsong Wen
Bo Du
Shirui Pan"
Squirel AI Bellevue, USA @iiggoongedu@@mal com
Wuhan University
Griffith University Queensland, Australia s S.pan@griffith.
Wuhan, China
dubo@whe edu
ABSTRACT
Evaluating the performance of well-trained GNN models 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 per- formance metrics (e.g., test error) and measuring graph data-level discrepancies, particularly when the training graph used for developing GNNs remains unob- served during test time. In this paper. we study new research problem, online GNN evaluation, which aims to provide valuable insights into the well-trained GNNs' 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 general- ization errors of well-trained GNN models. Through novel GNN re-training strategy with a parameter-free optimality criterion, the proposed LEBED compre- hensively integrates learning behavior discrepancies from both node prediction and structure reconstruction perspectives. This enables the effective evaluation the well-trained GNNs ability capture node semantics and structural repre- sentations, making it an expressive metric for estimating the generalization error in online GNN evaluation. Extensive experiments on real-world test graphs un- der 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
INTRODUCTION
Recent advances in graph neural networks (GNNs) have achieved great success with promising learning abilities for various graph structural data related applications in the real world (Zhang et al.
2022 Jin al. 2023a; Zheng et al. 2022a b Jin al. 2022 Liu al. 2023c Zheng et al. 2022c 2023d Luo et al. [223a [224]] Zhang et al. (023a). The ultimate goal in developing GNN models to achieve practical deployment and serving, with the expectation that well-trained GNNs will show expressive generalization ability when applied to diverse real-world, unseen, and unlabeled graph data ZZhnng al.) (2023a hb): Wu et al. (2024a); /Zhang et al.) (2023b)c): Liu et al.) (023a); Tan et al. (2023). In this case, understanding and evaluating the performance of well-trained GNN models becomes an essential and pivotal step for reliable GNN deployment in practice. For example, in real-world financial transaction networks (Amazon 2021), model designers strive to enhance the capacity of their well-trained GNNs to identify newly emerging suspicious transactions. Meanwhile,
"Corresponding Author
Coode available at h htt.ub.com/AAaaaa hwwp://aannddda///////////

---

Published as a conference paper at ICLR 2024
Gruphh
[J) Minooraraa
Test Groph Gi
GNN4
NNg
Outine GNV Evaluntion
Graph
(a) Demonstration of Online GNN Evaluation
(b) Our Solution for Online GNN Evaluation
Figure 1: Illustration of the proposed online GNN evaluation problem and our solution.
users seek confidence in these well-trained GNNs to detect and flag potentially dubious transactions within their own financial networks.
Conventionally, model evaluation involves using a thoroughly annotated test graph with labels to assess the model's performance, and this assessment is accomplished by comparing the model's predicted labels to the provided ground-truth labels, allowing the calculation of accuracy (or test error) as pivotal metric. However, this strategy falls short in practical GNN model evaluation scenarios. Typically, test graph data lacks ground-truth node labels since annotating it could be pro- hibitively expensive and inefficient, making it infeasible compute the accuracy metric. Moreover, considering the natural non-independent and non-identically distributed characteristic of graph data, there could various unknown distribution shifts between the training graphs and real-world test graphs Wu et al.] (2024b). For instance, the practical test graph data might be collected with different procedures, domains, and time Liu et al. (203bb;; Luo et al. (2023b); Pan et al. (2024). leading to dis- tinct node contexts, graph structures, and scales, with diverse node feature shifts (Jin et al. 2023b), domain shifts (Wu et al. 2020), and temporal shifts (Wu et al. 2022). In light of this, one possible solution to model evaluation involves quantifying the training- test discrepancy in graph data level. This can be accomplished by employing distribution measurement functions, e.g., maximum mean discrepancy (MMD) (Deng & Zheng, (021), to calculate representation-leve differences between the training and test graphs, serving as essential features for evaluating the GNN's performance. However, more practical online GNN serving scenarios, the training graph utilized for developing the GNN models is often inaccessible due to privacy constraints, making it unfeasible to directly estimate the graph data-level disparity.
Given all these real-world circumstances involving: (1) unlabeled and unseen test graph data; (2) potential training-test graph distribution shifts; and (3) inaccessible training graph data for online scenarios, an intriguing problem emerges: Is it possible to estimate the performance of a well- trained GNN model on test gruph data affected by distribution shifts, without access to its ground truth labels and original training graph data?
In this work, we first provide a feasible solution to answer this question by identifying it as an online GNN evaluation problem shown in Fig. [ Concretely, given a well-trained GNN model, online GNN evaluation aims to accurately estimate the well-trained GNN's generalization error on real- world unlabeled test graphs under distribution shifts, without needing to access the training graph data. To this end, we propose to estimate the LEarning BEhavior Discrepancy score between the training and test graphs from the view of GNN model training, dubbed LEB.D. More specifically, we develop novel GNN re-training strategy with a parameter-free optimality criterion, to re-train a new GNN on the test graph for effectively modeling the training-test learning behavior discrepancy. With the guidance of both node prediction discrepancy and structure reconstruction discrepancy, the proposed LEBED score computes the distance between the optimal weight parameters of the test graph re-trained GNN vs. the training graph well-trained GNN, to evaluate the well-trained GNN's ability to capture node semantics and structural representations at test time. Consequently, the proposed LEBED score can serve as expressive generalization error metric of the well-trained GNN for online GNN evaluation. well-trained GNN models' performance, rather than developing new GNN models improve the generalization ability. Throughout the entire process of online GNN evaluation, the well- well-trained GNN models would remain fixed. In summary, the contributions of this work
important to note that the core of this work is to estimate
follows:
Problem. We study new research problem, online GNN evaluation, which aims to provide valuable insights into well-trained GNNs' ability to effectively generalize to real-world, unlabeled test graphs under test-time distribution shifts.
2

---

Published as a conference paper at ICLR 2024
Solution. We develop effective learning behavior discrepancy score, dubbed as LEBED, to estimate the test-time generalization eтror of a well-trained GNN model for online GNN eval- uation. Through novel GNN re-training strategy with parameter-fir free optimality criterion, LEBED comprehensively integrates training-test learning behavior discrepancies from both node prediction and structure reconstruction perspectives, enabling it an expressive metric for effective online GNN evaluation.
Evaluation. We evaluate the proposed method on real-world unseen, unlabeled test graphs under diverse graph distribution shifts. Extensive experimental results reveal strong correlations with ground -oound-truth test errors on various well-trained GNN models, providing compelling evidence for the efficacy of the proposed method.
Prior Works. Our research is related to existing studies on predicting model generalization er- ror (Deng & Zheng [222]] Garg al. [022] Yu al. 2022 Guillory et al. 2022 Deng et al. [021] eu al. 2022), which aims to estimate model's performance on unlabeled data from the unknown and shifted distributions. However, these researches are designed for data in Euclidean space (e.g. images) while research is specifically designed for graph structural data, with a particular focus on applications in online deployment scenarios. Our research also significantly differs from others in unsupervised graph domain adaption (Yang et al. 2021 Zhang et al.) 2019; [w et al. 2020),
-utto--distribution (OOD) generalization (Li et al. 2022 Zhu et al. 2021 More detailed related work can be found in Appendix A
THE PROPOSED METHOD
Preliminary. At the stage of GNN development, we have a fully-observed training graph Gir (Xa, Au, Y.) with the number of N nodes with C-classes of node labels, where Xxr E R xd is the d-dimension nodes feature matrix indicating node attribute semantics, Ag R is the adjacency matrix indicating whether nodes are connected or not by edges with A. (0. 1) E for i-th and j-th nodes, and Y, E R xC denotes the node labels.
Training Stage. A GNN model trained on Gir according to the following objective function for node classification:
0- min Lets (Yrr Yot) where e,
Zec, Y GNNØ (Xr: Ar))
The parameters of GNN trained on Gir is denoted by Op. Zr E RNNx is the output node embedding of graph Gi from GNN,, and Yr E NxX denotes the output node labels predicted by the trained GNNo,- By optimizing the node classification loss function Lets (e.g., cross-entropy loss) between GNN predictions Y, and ground-trute node labels Yu.. the GNN model that is well-trained on G can be denoted as GNN;; with optimal weight parameters or. Note that once obtain the optimal GNNØ: that has been well-trained on Gm. the GNN model would be fixed and Gn would not be accessible during test time for online evaluation.
Test Time. For online GNN deployment and serving, given a real-world unlabeled test graph Go (X1e: Are) including M nodes with its feature matrix X R and its adjacency matrix Arc E R RMMMM we assume that there are potential distribution shifts between Gn and Gie. which mainly lies in node contexts, graph structures, and scales, but the label space keeps consistent under the covariate shift, i.e., all nodes in G are constrained in the same C'-clasess as Gu. Generally, the test error of node classification produced by the well-trained GNN;; on can be calculated as:
M
Test Error Gie, GNN;;
1
Σ 1=1
1
+ vie)
M
which indicates the percentage of incorrectly predicted node labels between the GNN predicted la- bels bi E YI and 'ground truths' vic Y,e, where 1 {.} is the indicator function. However, during the practical test time, the true node labels Y,, for unseen test graphs are typically unavailable, making the computation of the test error infeasible. Consequently, there is urgent need to devise a metric or a score that can serve as a substitute for the test error, to assess the performance of a tell-trained GNN on unseen and unlabeled test graphs for real-world online GNN deployment.
3

---

Published as a conference paper at ICLR 2024
$1: Test Graph Online Inference.
Computation
Test Grophs Gip
welidrattedd & flved
GNNN,
Bixt
GNNo;
Gi
Lofled Store
Gngghe
GNN unttle!
Prod
ONNo,
GNN
Disrrgaacy
Guide GRW tearning & fpplate
uscil
Per
Diseropateyy
Restraining Receepruuted Grapk
Optimality
The overview of the proposed LEBED score for online GNN evaluation under test-time distribution shifts, including three steps, i.e., S1: Test graph online inference; S2: GNN re-training with parameter-free optimality criterion; S3: LEBED score computation. All superscripts indicate the corresponding variables would remain fixed for online GNN evaluation.
Figure 2:
2.1 PROBLEM FORMULATION
At the test time, given the model GNNe; that has been well-trained Gu. and real-world test graph G = (Xe: Aw) without node labels as the input, the goal of online GNN evaluation is to learn test error estimation model f-) parameterized by & for obtaining score as:
Score [Gp GNNo;) x Test Error,
where (G,e GNNo;) - and E IR is scalar score indicating the test error of the well-traines GNN on Gg. More specifically, the score should exhibit a direct correlation relationship x with the test eиrоr according Eq. (2)
is important to note that several critical elements govern the online GNN evaluation: (1) the test graph G remains unobserved during the training phase and it lacks node label annotations; (2) there are potential unknown graph data distribution shifts between G and G that could challenge GNNs' inference ability; (3) the training graph G used for training GNNØ; cannot be observed due to privacy constraints in online scenarios.
2.2 LEBED: LEARNING BEHAAVIOR DISCREPANCY SCORE
To achieve the goal of online GNN evaluation, in this work, we first comprehensively exploit three- fold informative aspects from both the well-trained GNN and the test graph: (1) GNN model ar- chitecture, with its well-trained model weight parameters; (2) oulpul node representations, which reflect the well-trained GNN's capacity to capture the test graph node semantics and graph struc- tures; (3) output node pseudo labels, which indicates the ability of the well-traines GNN to project the captured test graph contexts to the node class label space. By thoroughly utilizing such informa- tion, in this work, we develop a learning behavior discrepancy score, i.e., LEBED score, to estimate the test-time generalization error of a well-trained GNN model on real-world unseen, unlabeled, and potentially distribution-sshifed test graphs.
Concretely, we propose GNN re-training strategy with parameter-free optimality criterion sociate the graph data-level discrepancy, with the GNN model-level learning behavior discrepancy between the training and test graphs. To model the GNN learning behavior discrepancy compre- hensively, we incorporate two-fold distinct discrepancies: node prediction discrepancy, denoted as Drred, and structure reconstruction discrepancy, denoted as D More specifically, Dreed. quanti- fies the disparity between the pseudo-labels generated by GNN models trained on the training graph and those re-trained on the practical test graph. Meanwhile, Dsm.. evaluates the discrepancy in the quality of output node representations by observing their ability to reconstruct the structure of the test graph. Subsequently, we utilize Drred as the supervision signal for instructing the GNN re- training process the test graph, while D serves the self- supervied iteration stop criterion, signaling the potential optimal solution of the re- re-trained GNN. At last, we derive the LEBED score based on the distance between the optimal weight parameters of the test graph re-trained GNN
4

---

Published as a conference paper at ICLR 2024
training graph well-trained GNN, that the proposed LEBED of the generalization error for the well-trained GNN on the test graph. The overall framework of computing the proposed LEBED score for online GNN evaluation is illustrated in Fig The detailed procedure the proposed method outlined as follows.
serve effective metric
S1: Test Graph Online Inference. Given well-trained GNN model with known initialization On. model architectures GNN,. and optimal model parameters f obtained on the training graph, for the first step, take the real-world unlabeled test graph Gie (Xie, At)) the input of the online- deployed model G so that we could obtain the output node representations Zie E R&Mxd, and node class pseudo labels Y MxC as
Zio Yi GNN;; (Xie:A Ate).
(4)
In this case, the following primary focus, for assessing the performance of GNNO; on the real-world test graph, should revolve around evaluating two critical aspects, iee,, the capacity of the output node representations z containing well-captured node semantics and structure information of the test graph, and the quality of output node pseudo labels Y
S2: GNN Re-training With Parameter-free Optimality Criterion. Given the obtained pseudo la- bels Y and node representations Zie for the second step, initialize new GNN model GNN 0o.e with the same model architectures as the well-trained GNN model, i.e., 0.. = 0..a- We use Og for simplification in the following. Then, we re-train the new GNNe, from scratch to fit the unseen test graph data. Importantly, the supervision signal comes from the pseudo labels Y to quantifies the
node prediction discrepancy, Le., Dpred = Lels (Y16- Yio as
0 min Lasss (Yre, Yie). where 8.
Zuo Y GNNo, (Xre Ard.
By minimizing the node classification loss in the re-training with Dpred, we could itera- tively optimize the re-trained model from GNN to optimal GNNę_; after q-step updates as (O,, , }o via stochastic gradient descent. However, due to lacking the ground-truth test node class annotations practice, it becomes challenging to ascertain whether specific iterations of GNN re- re-training in Eq. (5) can lead to optimal weight parameters on the test graph. In other words, it is difficult to determine the extent which P.c.4 2 O..
In light of this, we derive parameter-free optimality criterion that leverages the inherent structural property of graph data to facilitate the learning and updating of the re-trained GNN model. By re- constructing the test graph structure through the output node representations Ze = (zi E [dd A at each learning step, we could obtain the explicit and accurate self-supervision signals for guiding the optimization of GNN More specifically, the proposed parameter- free criterion computes the discrepancy in the ability of reconstructing graph structures, i.e., D between the reference node representations from the well-trained GNN and the updated node representations from the re-trained GNN in each step. This is expressed as:
Dsm.
Ig(s( Z Ar)) ((s( <=
where g(-) measures the ability of reconstructing graph structures from the node representations, with the hyper-parameter e controlling the degree of reconstruction discrepancy, and s(-) is the similarity based reconstruction function for node representations. Here use the cosine simi- larity function calculated as s sZne) = Zeo / Zee 1 |/ E MMM Taking the first item g(s (Ze),, Are) as the example, we have:
M
g(s(Znc), Are)
Σ (AL log (a (s(Zzz) + A log (1 (s(Zre)
M
This calculates the binary cross-entropy objective to measure the proximity of s (ZZee) to the discrete graph structures Age where i. denotes the i-th row of the matrix.
Note that the rationale behind employing the proposed parameter- free criterion is based on the fol- lowing considerations: firstly, the parameter-free approach eliminates the need to modify the loss
5

---

Published as a conference paper at ICLR 2024
function, i.e., Less in Eq. and does not impact the re-training process. This ensures consis- tent learning objective for both the re-trained GNN,, and GNNo, for fairly measuring the proposed learning behavior discrepancy; Secondly, the parameter-free pattern avoids introducing new param- eterized modules that need optimization, thereby simplifying the learning process.
S3: LEBED Score Computation. Given the node prediction discrepancy Drred the optimization objective in Eq. ( and the structure reconstruction discrepancy Dsm. based iteration stop criterion to indicate the optimal GNN the proposed learning behavior discrepancy score LEBED can be calculated as:
LEBED (GNN oi (OGE),GNN/)
1 0
where I--1|2 denotes the L2-norm for measuring the distance of optimal GNN model weights between that trained by the training graph and the test graph, respectively, that it measures GNN model- level discrepancy from the view of GNN training to effectively reflect the test error during test-time online evaluation. The overall algorithm of the proposed LEBED for online GNN evaluation under test-time graph data distribution shifts can be seen in Algo. Tin the Appendix D
EXPERIMENTS
In this section, we verify the effectiveness of the proposed LEBED score in terms of its correlation to the ground-truti test error for online GNN evaluation on various real-world graph datasets. Con- cretely, we aim to answer the following questions to demonstrate the effectiveness of the proposed LEBED: Q1: How does the proposed LEBED perform in evaluating well-trained GNNs on online node classification under various graph distribution shifts? Q2: How does the proposed LEBED per- form when conducting an ablation study regarding the parameter-free structure reconstruction dis- crepancy criterion Dsmu. ? Q3: How sensitive are the hyper-parameter for the proposed GNN re-training strategy? Q4: How is the correlation between our proposed LEBED and the ground- truth test error depicted? More experimental results, discussions, and implementation details of the proposed method are provided in Appendix D
3.1 EXPERIMENTAL SETTINGS
Datasets. We perform experiments on six real-world graph datasets with diverse graph data distri- bution shifts containing: node feature shifts (Wu et al. [2022] Jin et al. (2023b)), domain shifts (Wul a 2020), temporal shifts (Wu et al. 2022] Detailed statistics of all these datasets are listed in Ta- Ale in Appendix B. Note that the proposed LEBED is derived to model the statistical correlations with the ground- -trtth test error, so that it can be taken as the effective metric on practical unlabeled test graphs for our proposed online GNN evaluation problem. In this case, amount of test graphs with great diversity and complexity are required to observe such correlations. Hence, we propose to first adapt the raw distribution shifted graph datasets to the online GNN evaluation scenarios by extending the test graph sets in Table [A] with a blanket of 'Adapted'. More details can be found in Appendix B For all training graphs and validation graphs, we follow the process procedures and splits in works (Wu et al. 2022) and (Wu et al. 2020).
Online GNN Evaluation Protocol. We evaluate four commonly used GNN models for practical online GNN deployment and serving, including GCN (Kipf & Welling 2017), GraphS AGE (Hamil- ton al.) 2017) (abbr. SAGE), GAT (Veličković et al.) 2017), and GIN (Xu et al. 2019). well as the baseline MLP model that is prevalent for graph learning. For each model, we save its ini- tialization and train it on the observed training graph, until the model achieves the optimal node classification on its validation set following the standard training process, so that we can obtain the 'well-trained" GNN model that keeps fixed in the online GNN evaluation process. More details of these well-trained GNN models, including architectures, training syper-parameters. and ground- truth test error distributions, are provided in Appendix [D We report the correlation between the proposed LEBED and the ground-truth test errors under unseen and unlabeled test graphs with dis- tribution shifts, using R² and rank correlation Spearman's 's p. where R² ranges [0, 1], representing the degree of linear fit between two variables. The closer it is to 1, the higher the linear correlation. Spearman's 's p ranges [-1, 1). representing the monotonic correlation between two variables with indicating the positive correlation and -1 indicating the negative correlation.
6

---

Published as a conference paper at ICLR 2024
Table 1: Evaluation performance of well- GNNs on Cora and Amazon- Photo under node
feature shifts with Spearman rank correlation and linear fitting R2. The best results are in bold.
Cora
GCN
GAT
SAGE
GIN
MLP
an GNNs
Rt
R
P
Al
ConiScure
0.56
0.37
0.055
0.53
0.095
0.52
Entropy
0.50
0.070
0.62
0.121
0.51
0.084
0.69
0.234
0.63
0.154
0.59
0.134
ATC-MC
-0.45
0.034
-0.53
0,062
-0.36
0.035
-0.65
0.180
-0.56
0.051
-0.51
0.073
ATC-NE
-0.51
0.053
-0.61
0.087
-0.53
0.047
-0.69
0.223
-0.67
0.065
-0.60
0.095
Thres.
41.29
-0.45
0.057
Thres 0.89
-0.52
0.101
-0.33
0.048
-0.47
0.071
-049
0.101
Thres. ( 0.9)
-0.45
0.085
-0.56
0.143
-0.40
0.088
-0.68
0.272
-0.52
0.115
-0.52
0.141
LEBED (Ours)
0.82
0.640
0.87
0.745
0.69
0.519
0,66
0.410
0.74
0.663
0.76
0.595
GAT
SAGE
MLP
oog. GNNS
AmazznnPPhoo
R²
Rd
P
R2
ContScore
-0.55
0.251
-0.45
0.117
-0.70
0.376
11.94
0.870
-0.01
0.012
-0.15
0.336
Entropy
0.305
-0.48
0.193
-0.69
0,365
0.867
0.02
0.012
-0.15
0.348
ATC-MC
0.180
0.67
-0.33
0.015
ATC-NE
0:45
0.284
0.56
0.210
0.73
0.302
-0.92
0.800
-0.43
0.155
0.08
0.350
Thmes. (r = 0.7)
0.54
0.223
0.48
0.174
0.71
0.376
-0.94
0.859
0.01
0.008
0.16
0.328
Thres. (r 0.89
0.56
0.232
0:45
0.162
0.71
0.382
-0.94
0.876
0.05
0.014
0.16
0.331
Thres. 0.57
0.156
0.022
LRD (Oues)
0.90
0.78
0.616
0.79
0.705
0.62
00530
0.601
Baseline Methods. Since our proposed LEBED is the pioneering approach for online GNN evalu- ation under test-time graph distribution shifts, there are no established baseline methods for mak- ing direct comparisons. Therefore. we evaluate our proposed method by comparing it to several convolutional neural network (CNN) model evaluation methods applied to image data, specifically tailored to online evaluation scenarios. Note that existing CNN model evaluation methods are hard to directly apply to GNNs, since GNNs have entirely different convolutional architectures working on different data types. Therefore, we make necessary adaptations to enable these methods to work on graph-structured data for online GNN model evaluation. Specifically, we compare seven base- line methods in four categories, including averaged confidence score (ConfScore) (Hendrycks & Gimpel, 2016), Entropy (Guillory et al. 202I). average thresholded confidence (ATC) score (Garg it al.] (2022) with its two variants ATC-NE (negative entropy) and ATC-MC (maximum confidence), as well as threshold-based method (Deng ZZengg 2021] with three threshold values for Thres.
(r {0.7, 0.8, 0.9)). More details of these baseline methods can be found in Appendix D
3.2 ONLINE GNN MODEL EVALUATION PERFORMANCE
In this section, we aim answer Q1 and report the results of LEBED in evaluating well-trained GNNs on the online node classification task under various graph distribution shifts in Table [ Ta- ble [ and Table 3 In general, it can be observed that our proposed LEBED achieves consistent best performance on evaluating various well-trained GNNs under all node feature shifts, domain shifts, and temporal shifts, showcasing strong positive correlations p and outstanding R2 fitting- This significantly demonstrates the effectiveness of our approach in capturing the correlation be- tween LEBED and ground-truth test errors. For instance, for node feature shifts, our LEBED has 0.90 on Amazon-Phout for well-trained GCN online evaluation, significantly exceeding other comparison methods. Besides, many negative correlations are observed in ATC and Threshold- methods, contrary to the expected positive correlations, underscoring the limitations of straightfor- wardly adapting existing methods for online GNN evaluation. For example, the ATC-MC method exhibits predominantly negative correlations when applied to online GNN evaluation in the context of domain shifts on ACMv9. However, it demonstrates positive correlations when assessing GCN on Amazon- Photo under feature shifts. The underlying reason could be that such adaptation fails to consider the distinctive neighbor aggregation mechanisms of GNNs intrinsic to the inherent struc- tural characteristics of graph data. These inconsistent statistical correlations with ground truth test errors suggest that it is not a reliable metric for predicting generalization errors in online evalua- tion scenarios. Furthermore, our proposed LEBED demonstrates generally better performance under node feature shifts when compared to domain shifts and temporal shifts. For example, it achieves an average = 0.76 on Cora across all GNNs, whereas it reaches & = 0.52 on both Citationv2 and OGB- OGB-arxiv. This discrepancy can be primarily attributed to the increased complexity associated with domain shifts and temporal shifts, where multi-faceted distribution variances impact various aspects of node features, graph structure, and scales.
7

---

Published as a conference paper at ICLR 2024
Table 2: Evaluation performance of well-trained GNNs on ACMv9, DBLPv8, Citationv2 under
domain shifts with Spearman rank correlation p and linear fitting Rº The best results are in bold.
ACMv9
GCN
GAT
SAGE
GIN
MLP
an GNNs
R[
R
A
Entropy
0.49
0.48
0.221
0.38
0.285
0.000
0.36
0.364
0.33
0.219
ATC-MC
-0.48
0.117
-0:19
0.224
-0.37
0.140
-0.03
0.003
-0.35
0.211
-0.34
0.140
ATC-NE
-0.48
0.344
-0.48
0.245
-0.38
0.138
-0.04
0.004
-0.35
0.208
-0.35
0.148
0.303
Thres 0..0
0.280
0.002
-0.37
0.370
Thres. ( 0.90
-0.48
0.222
-0.48
0.344
-0.40
0.337
0.11
0.006
-0.37
0.437
-0.32
0.269
LEBED (Ours)
0.52
0.434
0.52
0.540
0.61
0.501
01.6
0.176
0.47
0.405
0.52
0.411
DRIPP
GAT
SAGE
MLP
oog
R
P
R2
R!
ContScore
0.34
0.299
0.29
0.391
01.25
0.426
0.11
0.211
0.25
0.5155
0.28
0.366
Entropy
0.37
0.369
0.42
0.468
0.23
0.475
0.226
0.23
0.580
0.29
0.424
ATC-NE
-0.34
0.275
-0.41
0.353
-0.27
0.324
-0.24
0.171
-0.22
0.267
-0.30
0.278
Thmes. (r = 0.7)
-0.31
0.271
-0.56
0.395
-0.22
0.445
-0.20
0.220
-0.27
0.575
-0.27
0.381
Thres. (r 0.89
-0.36
0 365
-0.38
01.477
-0.20
0.473
-0.30
0.236
-0.29
0.630
-0.29
01436
Thres.
40.19
0.669
(Oues)
0.276
0.551
Ciration22
GCN
GAT
SAGE
GIN
MLP
GINNs
P
R/
P
ConrSoare
0.0995
0.26
0.131
0.30
0.316
0.27
Entropy
0.40
0.077
0.45
0.138
0.29
0.137
-0.02
0.004
0.32
0.342
0.29
0.148
ATC-MC
-0.41
0.041
-0.42
0.065
-0.28
0.038
-0.07
0.003
-0.30
0.099
-0.30
0.047
ATC-NE
-0.43
0.061
-047
0,081
-0.29
0.035
-0.07
0.004
-0.34
0.093
-0.32
0.055
Thres. (?
-0.42
0.097
-0.27
0.171
0.003
-0.70
0.333
Thres. (r 0.8)
-0.35
0.083
-0.4
0.125
-0.31
0.197
0.04
0.004
-0.70
0.307
-0.35
0.137
Thres. (r 0.9)
-0.36
0.071
-0.45
0.167
-0.37
0.210
0.06
0.002
-0.68
0.272
-0.36
0.144
LEBED (Ours)
0,63
0,200
0.53
0.228
0.45
0.275
0.210
0.47
0.356
0.52
0.254
Table 3: Evaluation performance of well-trained GNNs on OGB-arxit under temporal shifts with The best results are in bold.
Spearman rank correlation p and linear fitting R
OGB-arxiv
SAGE
MLP
ove GNNs
P
11
1(
P
P
ConiNcure
0.09
0.111
0.09
0.109
0.21
0.226
0.51
0.362
0.52
0.551
0.28
0.273
Entropy
0.12
0.345
0.10
0.110
0.26
0.242
0.52
01.86
0.62
D.643
0.32
0.305
ATC-MC
-0.11
0.094
-0.21
0.224
-0.58
0.635
0.754
Thres. (r 0.7)
-0.07
0.124
-0.08
0.144
-0.19
0.231
-0.51
0.356
-0.43
0.484
-0.26
0.268
Thres. (r 0.8)
-0.05
0.133
-0.06
0.177
-0.17
0.237
-0.50
0.348
-0.38
0.126
-0.25
0.261
Thres. -0.04
-0.05
0.219
-0.14
0.245
0.339
40.28
0.364
0.262
(Our)
Table 4: Ablation study with (w/) and without (w/o) the proposed Dan. based parameter-free optimality criterion on ACMv9 under test-time domain shifts.
ACMv9
GCN
GAT
SAGE
GIN
MLP
Itens.
(w/o Dan )
R2
It'
R²
R²
R?
0.204
0.17
0.056
0.46
01.003
-0.10
0.028
0.25
0.118
0.42
80
0.30
0.136
0.16
0.59]
-0.45
0.140
-0.22
0.033
0.13
0.352
160
0.24
0.068
0.46
0.559
-0.53
0.170
-0.43
0.125
0.40
0.281
200
0.13
0.026
0.535
0.178
-0.46
0.140
0.42
LEBED (w) Das)
0.52
0.434
0.52
0.540
0.61
0.501
0.46
0.176
0.47
0.405
3.3 IN-DEPTH ANALYSIS OF THE PROPOSED LEBED
Ablation Study of Parameter-free Optimality Criterion. In Table we compare the performance with and without the proposed Dam. based criterion to verify its effectiveness on ACMv9 dataset under test-time domain shift (Q2). As can be observed, compared with using fixed q iterations, our proposed parameter-free Dam. criterion performs better indicator to reflect the optimality of GNN re-training, facilitating more accurate optimal weight parameter distance calculation for LEBED. More results the optimal iteration steps for all GNNs all datasets, along with the time com- plexity analysis, are provided in Appendix C The dominant factor affecting the time complexity is the number of re-training iterations q. This reflects the necessity and effectiveness of the proposed
8

---

Published as a conference paper at ICLR 2024
Renning Tee Coeperice en Clatines?
Hoye meater Serelis Ansoen Phok
Hoper por coplre Scediiayy cn IME P3
02-
180
0.47
417.8
8.1
13.0
2.70
0.00
0.18
Figure 3: Running time com- parisonon Citationv2 dataset w/ and w/o the proposed Dam. based criterion.
Figure 4:
sensitivity analysis on in the pro-
posed parameter-free optimality criterion. (left: Amazon-Phon Photo dataset with fixed constant setting; right: DBLPv8 dataset with fixed ratio (%) setting.)
ATC-0C
1450
31
00
11r
Lak0 (Far))
Figure 5: Correlation visualization for ATC-MC of GCN Cora, our LEBED of GCN on Cora, Thres.(r = 0.9) of GAT on Amazon-Photo, and our LEBED of GAT on Amazon-Photo.
Dam. based parameter-free optimality criterion through reducing q. The running time comparison on Citationv2 in seconds is shown in Fig. 3 with a single GeForce RTX 3080 GPU and 200 iterations for w/ Sanu can be seen that the proposed criterion could decrease the running time significantly, demonstrating its great efficiency for online GNN evaluation.
Hyper-parameter Sensitivity Analysis. We analyze the syper-parameter sensitivity of on the pro- posed method for answering Q3, and the results on various well-trained GNN models can be seen in Fig. 4
We consider two different types of strategies to set the c, i.e., fixed constant setting and fixed ratio setting, where the former sets as fixed constant for all test graphs on each to-be-evaluated GNN, e.g., 0.02 denotes constant distance, and the latter sets e as a fixed rations of differences be- tween two terms in Eq. (6) e.g., 3% discrepancy tolerance. The smaller the the less discrepancy tolerance is allowed, the performance would be better. The experimental results show that under certain ranges with different syper-parameter setting strategies, the proposed LEBED could achieve relatively consistent performance with low
sensitivity to e.
Correlation Visualization. In Fig. 5 we visualize the correlation relationship between the ground- truth test errors and our proposed LEBED under node feature shift datasets, and make comparisons with existing methods on rell-trained GCN and GAT for answering Q4. As can be observed, our proposed LEBED achieves stronger correlations compared with other baselines, verifying its effec- tiveness for associating with ground-truth test errors for online GNN evaluation.
4 CONCLUSION
In this work, we have studied new problem, online GNN evaluation, with an effective learning behavior discrepancy score, dubbed LEBED, to estimate the test-time generalization errors of well- trained GNNs on real-world graphs under test-time distribution shifts. A novel GNN re-training strategy with a parameter-free optimality criterion comprehensively incorporates both node predic- tion discrepancy and structure reconstruction discrepancy to precisely compute LEBED. Extensive experiments on real-world unlabeled graphs under diverse distribution shifts could verify the ef- fectiveness of the proposed method. Our method assumes that the class label space is unchanged across training and testing graphs though covariate shifts may exist between the two. We will look into relaxing this assumption and address a broader range of more complex real-world graph data distribution shifts in the future.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
Pan was supported in part by the Australian Research Council (ARC) under grants F1210100097 and DP240101547, and the CSIRO National Science Foundation (US) AI Research Collaboration Program.
ETHICS STATEMENT
Our research solely focused on tackling scientific research questions and does not entail the partic- ipation human subjects, animals, or environmentally sensitive materials. As result, we anticipate no ethical concerns or conflicts of interest in our study. We are committed to upholding the utmost standards of scientific integrity and ethical practice throughout our research, thereby guaranteeing the accuracy and dependability of our results.
REPRODUCIBILITY STATEMENT
We have carefully provided clear and comprehensive formalization of our proposed method in the main submission. Additionally, we delve into the dataset information and method implementation details in Appendix B and D to ensure reproducibility.
10

---

Published as a conference paper at ICLR 2024
REFERENCES
Amazon.
Real-time fraud detection with web services), 2021.
graph
neural
network on dgl
(amazon
petps://gittnnn com/ awaaawssass dc
realt mellttmm--ie me- fraud-
Weijian Deng and Liang Zheng. Are labels always necessary for classifier accuracy evaluation? In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 15069-15078, 2021.
Weijian Deng, Stephen Gould, and Liang Zheng. What does rotation prediction tell us about clas- sifier accuracy under varying testing environments? In International Conference on Machine Learning (ICMI.), pp. 2579-2589. PMLR, 2021.
Weijian Deng, Stephen Gould, and Liang Zheng. On the strong correlation between model invari- ance and generalization. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In International Conference on Learning Representations Workshop on Representation Learning on Graphs and Manifolds, 2019.
Saurabh Garg, Sivaraman Balakrishnan, Zachary Chase Lipton, Behnam Neyshabur, and Hanie Sedghi. Leveraging unlabeled data to predict out-of-distribution performance. In International Conference on Learning Representations (ICLR), 2022.
Devin Guillory, Vaishaal Shankar, Sayna Ebrahimi, Trevor Darrell, and Ludwig Schmidt. Predicting with confidence on unseen distributions. In Proceedings of the IEEE/CVF International Confer- ence on Computer Vision (ICCV), pp. 1134-1144, 2021.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems (NeurIPS), 2017.
Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and out-of-distribution examples in neural networks. arXiv preprint arXiv: 1610,0211 2016.
Ming Jin, Yuan-Fand Fang Li, and Shirui Pan. Neural temporal walks: Motif aware representation learn- ing on continuous- time dynamic graphs. Advances in Neural Information Processing Systems (NeurIPS), 2022.
Ming Jin, Huan Yee Koh, Qingsong Wen, Daniele Zambon, Cesare Alippi, Geoffrey I Webb, Irwin King, and Shirui Pan. A survey on graph neural networks for time series: Forecasting, classifica- tion, imputation, and anomaly detection. arXiv preprint arXiv:2307.0377
2023a.
Wei Jin, Tong Zhao, Jiayuan Ding, Yozen Liu, Jiliang Tang, and Neil Shah. Empowering graph rep- resentation learning with test-time graph transformation. In International Conference on Learning Representations (ICLR), 2023b.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
Haoyang Li, Xin Wang, Ziwei Zhang, and Wenwu Zhu. Out-of-distribution generalization graphs: A survey. arXiv preprint arXiv:2202.07987, 2022.
Yixin Liu, Kaize Ding, Qinghua Lu, Fuyi Li, Leo Yu Zhang, and Shirui Pan. Towards self- interpretable graph-level anomaly detection, Advances in Neural Information Processing Systems, 36, 2023a.
Yixin Liu, Kaize Ding, Jianling Wang, Vincent Lee, Huan Liu, and Shirui Pan. Learning strong graph neural networks with weak information. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2023b.
Yixin Liu, Yizhen Zheng, Daokun Zhang, Vincent Lee, and Shirui Pan. Beyond smoothing: Unsu- pervised graph representation learning with edge heterophily discriminating. In Proceedings of the Association for the Advanced of Artificial Intelligence (AAAI), 2023c.

---

Published as a conference paper at ICLR 2024
Linhao Luo, Jiaxin Ju, Bo Xiong, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan. Chatrule: Mining logical rules with large language models for knowledge graph reasoning. arXiv preprint 0rXf1:2300.00538, 2023a.
Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan. Normalizing flow-based neural process for few-shot knowledge graph completion. In The 46th International ACM SIGIR Con- ference on Research and Development in Information Retrieval, 2023b.
Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan. Reasoning on graphs: Faithful and interpretable large language model reasoning. In International Conference on Learning Repre- sentations, 2024.
Shirui Pan, Linhao Luo, Yufei Wang, Chen Chen, Jiapu Wang, and Xindong Wu. Unifying large language models and knowledge graphs: A roadmap. IEEE Transactions on Knowledge and Data Engineering (TKDE), 2024.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kaneza- shi, Tim Kaler, Tao Schardl, and Charles Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 5363-5370, 2020.
Oleksandr Shchur, Maximilian Mumme, Alcksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: /8/ 1.05868, 2018.
Xiao Shen, Quanyu Dai, Sitong Mao, Fu-lai Chung, and Kup-Sze Choi. Network together: Node classification via cross-network deep network embedding. IEEE Transactions Neural Networks and Learning Systems (TNNLS), (2(5)) 2020.
Yue Tan, Chen Chen, Weiming Zhuang, Xin Dong, Lingjuan Lyu, and Guodong Long. Is hetero- geneity notorious? taming heterogeneity handle test-time shift in federated learning. Advances in Neural Information Processing Systems, 36, 2023.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2017.
Bang Wu, He Zhang, Xiangwen Yang, Shuo Wang, Minhui Xue, Shirui Pan, and Xingliang Yuan. Graphguard: Detecting and counteracting training data misuse in graph neural networks. NDSS, 2024a.
Man Wu, Shirui Pan, Chuan Zhou, Xiaojun Chang, and Xingquan Zhu. Unsupervised domain adaptive graph convolutional networks. In Proceedings of The Web Conference (WWW), pp- 1457-1467, 2020.
Man Wu, Xin Zheng, Qin Zhang, Xiao Shen, Xiong Luo, Xingquan Zhu, and Shirui Pan. Graph learning under distribution shifts: A comprehensive survey on domain adaptation, out- of-distribution, and continual learning. arXiv preprint arXiv.2402.16374 2024b.
Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts on graphs: An invariance perspective. In International Conference on Learning Representations (ICLR), 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations (ICLR). 2019.
Shuwen Yang, Guojie Song, Yilun Jin, and Lun Du. Domain adaptive classification on heteroge- neous information networks. In Proceedings of International Conference International Joint Conferences on Artificial Intelligence (IJCAI), pp. 1410-1416, 2021.
Zhilin Yang. William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40-48. PMLR, 2016.
Yaodong Yu. Zitong Yang, Alexander Wei, Yi Ma, and Jacob Steinhardt. Predicting out-of- distribution enror with the projection norm. In International Conference on Machine Learning (ICML., pp. 25721-25746. PMLR, 2022.
12

---

Published as a conference paper at ICLR 2024
He Zhang, Bang Wu, Xingliang Yuan, Shirui Pan, Hanghang Tong, and Jian Pei. Trustworthy graph neural networks: Aspects, methods and trends. arXiv preprint arXiv:2205.0744 074444, 2022.
He Zhang, Bang Wu, Shuo Wang, Xiangwen Yang, Minhui Xue, Shirui Pan, and Xingliang Yuan. Demystifying uneven vulnerability of link stealing attacks against graph neural networks. In ICML, volume 202 of Proceedings of Machine Learning Research, pp. 41737-41752. PMLR, 2023a.
He Zhang, Xingliang Yuan, Quoe Viet Hung Nguyen, and Shirui Pan. On the interaction between node fairness and edge privacy in graph neural networks. CoRR, abs/2301. 12951, 2023b.
He Zhang, Xingliang Yuan, Chuan Zhou, and Shirui Pan. Projective ranking- -asee GNN evasion attacks. IEEE Trans. Knowl. Data Eng., 35(8):8402- 8416, 2023c.
Y Zhang, G Song, L Du, S Yang, and Y Jin. Dane: Domain adaptive network embedding. In Pro- ceedings of International Conference on International Joint Conferences on Artificial Intelligence (IJCAI), pp. 4362-4368, 2019.
Xin Zheng. Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. Graph neural networks for graphs with heterophily: A survey. arXiv preprint arXiv:2202.070 077020 2022a.
Xin Zheng. Miao Zhang, Chunyang Chen, Chaojie Li, Chuan Zhou, and Shirui Pan. Multi-relational graph neural architecture search with fine- fine-graines grained message passing. In 2022 IEEE International Conference on Data Mining (ICDM), pp. 783-792. IEFE, 2022b.
Xin Zheng, Yixin Liu, Zhifeng Bao, Meng Fang, Xia Hu, Alan Wee-Chung Liew, and Shirui Pan. Towards data-centric graph machine learning: Review and outlook. arXiv preprint arXiv:2309. 10979, 2023a.
Xin Zheng, Miao Zhang, Chunyang Chen, Soheila Molaei, Chuan Zhou, and Shirui Pan. Gnneval- uator: Evaluating gnn performance on unseen graphs without labels. Advances in Neural Information Processing Systems (NeurIPS), 2023b.
Xin Zheng, Miao Zhang, Chunyang Chen, Quoe Viet Hung Nguyen, Xingquan Zhu, and Shirui Pan. Structure-free graph condensation: From large-scale graphs to condensed graph-free data. In Advances in Neural Information Processing Systems (NeurIPS), 2023c.
Xin Zheng, Miao Zhang, Chunyang Chen, Qin Zhang, Chuan Zhou, and Shirui Pan. Auto-heg: Au- tomated graph neural network on heterophilic graphs. In Proceedings the (WWW), pp. 61 6116166666 1-600, 2023d.
the ACM Web Conference
Yizhen Zheng, Shirui Pan, Vincent Cs Lee, Yu Zheng, and Philip Yu. Rethinking and scaling up graph contrastive learning: An extremely efficient approach with group discrimination. In Advances in Neural Information Processing Systems (NeurIPS), 2022c.
Qi Zhu, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi. Shift-robust gnns: Overcoming the limitations of localized graph training data, Advances in Neural Information Processing Systems (NeurIPS), 34:27965-2777 27977, 2021.
13

---

Published as a conference paper at ICLR 2024
APPENDIX
This is the appendix of the work: *Online GNN Evaluation Under Test-time Graph Distribution Shifts". In this appendix, we present more additional method details, experimental results, and discussions regarding the proposed online CNN evaluation problem and the proposed LEBED score method.
A RELATED WORK
Predicting Model Generalization Error. Our work is relevant to the line of research on predicting model generalization error, which aims to develop a good estimator of source-domain well-trained
model's 's performance on unlabeled data from the unknown distributions in the target domain (Deng
& Zheng 2021 Garg et al.] 2022 Yu et al.) 2022] Deng et al.. 2022] Guillory et al., 2021] Deng
et al. 2021). Typically, Hendrycks et al. (Hendrycks & Gimpel 2016) and Guillory et al. (Guillory
al. (021) proposed estimate convolutional neural network (CNN) classifier's 's performance on image data with delicately designed metrics, i.e., averaged confidence score (ConfScore), aver- aged entropy (Entropy) score. and difference of confidences (DoC) score, to estimate and reflect the model accuracy by means of its classifier's 's softmax outputs. Garg et al. (Garg et al. (022) also proposed learn a softmax probability based average thresholded confidence (ATC) score by es- timating the fraction of unlabeled images above the threshold calculated by the validation dataset. In contrast, Deng et al. (Deng & Zheng 2021 Deng et al., 202I) directly predicted CNN classifier accuracy by deriving data distribution distance features between the training and test images with linear regression model. Compared with directly estimating the accuracy with the image data-level discrepancy, Yu et al. (Yu al. 2022 proposed to caleulate the well well-trained CNN models parameter space difference as projection norm, and took it as an estimation of -uttof-disttibution.
Note that, these existing methods mostly focus evaluating CNN model classifiers on image data in computer vision, and the formulation of evaluating GNNs for graph structural data still remains under-explored in graph machine learning. Concretely, conducting online GNN evaluation for graph structural data at test time has two critical challenges: (1) different from Euclidean image data, graph structural data lies in non-Euclidean space with complex and non-independent node-edge intercon- nections, so that its node contexts and structural characteristics significantly vary under wide-range graph data distributions, posing severe challenges for GNN model evaluation when serving on un- known graph data distributions. (2) GNNs have entirely different convolutional architectures from those CNNs, when GNN convolution aggregates neighbor node messages along graph structures. Such that GNNs trained on the observed training graph might well fit its graph structure, and due to the complexity and diversity of graph structures, serving well-trained GNNs on unlabeled test distributions that they have not encountered before would incur more performance uncertainty. Fur- thermore, in online GNN deployment scenarios where access to the training graph is restricted, the feasibility of measuring data-level discrepancies becomes unattainable.
Hence, in this work, we first investigate the online GNN evaluation problem for graph structural data with a clear problem definition and feasible solution, taking significant step towards under- standing and evaluating GNN models for practical online GNN deployment and serving. Besides, our proposed LEBED can be taken an extension of the work (Yu al.) (022) to GNN models on graph structural data. Differently, our method makes effective use of additional self-supervision signals derived from graph structures, thanks to the incorporation of the proposed parameter-free
optimality criterion, which clearly distinguishes our method from Yu et al. (2022).
Unsupervised Graph Domain Adaption. Our work is also relevant to the unsupervised graph do- main adaption (UGDA) problem, whose goal is to develop a GNN model with both labeled source graphs and unlabeled target graphs for better generalization ability on target graphs. Typically, ex- isting UGDA methods focus on mitigating the domain gap by aligning the source graph distribution with the target one. For instance, Yang et al. (Yang et al. 2021) and Shen et al. (Shen et al. 2020) optimized domain distance loss based on the statistical information of datasets, e,g., maximum mean discrepancy (MMD) metric. Moreover, DANE (Zhang et al., 2019) and UDAGCN (Wu et al. 2020) introduced domain adversarial methods to learn domain coomain-invriann invariant embeddings across the source do- main and the target domain. Therefore, the critical distinction between our work and UGDA is that work is primarily concerned with evaluating the GNNs' performance unseen graphs with-
14

---

Published as a conference paper at ICLR 2024
Table Al: Dataset statisties with various test-time graph data distribution shifts.
Distribution shifts
Datusets
#Nodes
#Edges
#Classes
#Train/ Val/Test Graphs (Adapted)
Cora (ang al_
2016
2,703
5,278
1/1/320 (8-artifices) 1/1/320 (8 artifices)
Node feature shifts
Amazon Photo SSnchur et al. 2018
7,650
119,081
10
ACMv9 (Wa et al.
2020
7,410
22,270
1/1/369 (3 d--oominn::: A, D, C)
Domain shifts
DBLPv8 WD
5,578
14.682
1/1/369 (3-domains: D, C)
Citation Wa el a. 2020
4,715
13,466
1/1/369 (3 (3-domains: A, D, C)
Temporal shifts
OGB-arniv Paareaa et al.
2020
169,343
1,166,243
40
1/1/360 (3-periods)
Table A2: Details of test graphs under diverse graph distribution shifts with adapted expansions.
Raw TestGs
Feat Perturbs
# Feat Masks
# Edge Perturbs
Distribution shift
Datasets
SubGs
Totals
Cora
8
20
20
320
Node feature shifts
Amazon-Photo
8
20
20
320
ACMv9
I
10
10
10
10
41, D: 164, C: 164 (369)
Domain shifts
DBLPv8
1
10
10
10
10
D: 41, A: 164, C: 164 (369)
Citationv2
1
10
10
10
C: 41, D: 164, A: 164 (369)
Temporal shifts
OGB-arxiv
3
30
30
30
30
360
out labels under test-time distribution shifts, rather than improving the GNNs' generalization ability when adapting to unlabeled target graphs.
Graph Out-of-distribution (OOD) Generalization. Out-of-distribure (OOD) generalization (Li et al. 2022: Zhu et al., 202T) on graphs aims to develop GNN model given several different but related source domains, so that the developed model can generalize well unseen target domains. Li et al. (Li et al. (022) categorized existing graph OOD generalization methodologies into three conceptually different branches, i.e., data, model, and learning strategy, based on their positions in the graph machine learning pipeline. We would like highlight that, even ODD generalization and our proposed online GNN evaluation both pay attention to the general graph data distribution shift issue, we have different purposes: our proposed online GNN evaluation aims evaluate well-trained GNNs' performance on unseen test graphs, while graph ODD generalization aims to develop new GNN model for improve its performance generalization capability unseen test graphs.
B TEST-TIME DATASET DETAILS
The dataset statistics and details of the adapted test graphs for all datasets under various distribution shifts are provided in Table/AI]and Table|A2] respectively. In general, we expand all raw test graphs with four types of strategies, including feature perturbation with Gaussian covariate shifts, feature masking, sub-graph sampling, and edge drop, with the default random range [0.1, 0.7] in uniform distribution sampling with different quantities.
More specifically, for node feature shifts, we use the artificial transformations of Cora with GAT- generation, and Amazon with GCN-generation according to the work (Wu et al.) (022). Each dataset has eight raw test graphs and we only impose feature-level expansion strategies on them. For domain shifts, we consider full/train/val/esst graphs for each domain under the inductive setting, and each is expanded with all four strategies. For each domain shift case, e.g., ACMv9, we use the training graph for well-training GNN models, and its online test set contains its test graph expansions, and all other domains' (DBLPv8 and Citationv2) all graph expansions for AAAA, D. C) cross-domain evaluation. For temporal shifts, we follow Wu et al. (2022) using the year range [1950, 2011] corresponded sub- graph as the training graph, [201I, 2014 for validation, and remain three year periods [2014, 2016), [2016, 2018), [2018, 2020) the raw test graphs involving all four-type expansion strategies.
15

---

Published as a conference paper at ICLR 2024
Table A3:
Hlper-parametee sensitivity analysis on in the proposed parameter-free optimality cri- terion on Mmazoon-Photo dataset with the fixed constant setting.
Amazon-Phoon Photo
GCN
GAT
SAGE
GIN
R²
p
p
R²
R
0,005
0.80
0.723
0.72
0.550
0.67
0.478
0.58
0.238
0,01
0.80
0.724
0.73
0,560
0.68
0.467
0,55
0.037
0,03
0.81
0.670
0.78
0.614
0.72
0,365
0.83
0.705
0.05
0.79
0.566
0.79
0.591
0.79
0.425
0.83
0.705
0.1
0.90
0.730
0.34
0.052
0.64
0.591
0.83
0.705
0.2
0.90
0.730
0.54
0.338
0.63
0.586
0.83
0.705
Table A4: sensitivity analysis on in the proposed parameter-free optimality cri- terion DBLPv8 dataset with the fixed ratio setting.
DBLPv8
GCN
GAT
SAGE
GIN
<(%)
R
R
P
R
p
R
0.5
0.79
0.784
0.76
0.607
0.78
0.604
0.81
0.650
0.78
0.768
0.568
0.78
0.601
0.81
0.672
0.76
0.706
0.430
0.81
0.623
0.80
0.727
0.71
0.581
0.276
0.83
0.687
0.79
0.763
0.30
0.120
0.296
0.83
0.779
0.71
0.796
0.77
0.798
0.72
0.767
0.76
0.737
0.48
0.529
C IN-DEPTH ANALYSIS AND MORE RESULTS
C.I TIME COMPLEXITY ANALYSIS.
The time complexity of the proposed LEBED can be analyzed along with its learning procedure. Taking T--layer GCN the example, for S1 test graph inference, there one-time computation complexity approximately OLLMd) + +EE), where E' is the number of edges on the test graph Gg, and we shorten it to ( OLMMd O(E). For S2 GNN re-training, the time complexity can be O(g * Q) highly related to the number of iterations q. Then, the parameter- freeerrr-eeeeeeee optimality criterion takes (M2). For S3 LEBED score computation, the time complexity can be about (ww) where is the number of GNN weight parameters. Overall, the time complexity of the proposed LEBED can approximated as ( + Oly 22) + O(M²) + O(w)) and the dominant factors affecting the time complexity are the number of re-training iterations and the size of the graph M. This reflects the necessity and effectiveness the proposed Dano. based parameter- free optimality criterion through reducing q.
C.2 MORE RESULTS ON THE PROPOSED PARAMETER-PREE OPTIMALITY CRITERION
We provide wider range hyper-parameter results for both fixed constant setting in Table A3 and fixed ration setting in Table It can be generally observed that could affect the online evaluation performance but it shows relatively low aapee-prrretter sensitivity in certain ranges.
Moreover, we present the average iteration stop epochs determined by the proposed Dam. parameter- free criterion, which indicate the point at which the re-trained GNN achieves optimality in Table A5 can be generally observed that our proposed criterion could constrain the GNN re-training process with Dum.. eeffssueervision signals to stop the over-retraining at early stages. Besides, more correla- tion visualization comparison results of different well-trained GNNs under diverse graph distribution
shifts are shown in Fig. A6 A7
A8
and A9
16

---

Published as a conference paper at ICLR 2024
Table A5; Average optimal iterations produced by the proposed stro. based parameter- free criterion.
# Avg.
Cora
Amazon-
ACMv9
DBLPv8
Citationv2
OGB-arxiv
Opt. Iters.
GCN
79
12
175
42
585
GAT
46
420
188
30
32
157
SAGE
73
166
7
161
14
377
GIN
110
5
23
131
33
197
MLP
9
254
13
57
20
344
Algorithm Learning Behavior Discrepancy (LEBED) Score Computation.
Require: Real-world unseen and unlabeled test graph Gee online-deployed GNN model GNNe; that has been well-trained with known initialization parameters G., number of re- re-training itera- tions q, structure reconstruction discrepancy nyper-parameterr
Ensure: LEBED score.
1:
Input Gie to well-trained GNN;; acquire unline-generated node representations Z and pseudo labels Y according to Eq. (4;
2: Let One 00:
3: while 0 < t <=== do
4: Re-train GNNo, with the prediction discrepancy Dreed. according to Eq. 5 where 6
Ou. -e. Ceis (GNNo,, (G.NNe. (Gı));;
5: Compute the parameter-free structure reconstruction discrepancy criterion Dsm. according to 6 and Eq. 7
6: if Suu. < 6 then
7: 0 re. and break;
8:
end if
9: end while
10: Until 0% Peggi
11: Calculate the proposed LEBED score according to Eq.
D IMPLEMENTATION DETAILS
D.1 OVERALL ALGORITHM AND IMPLEMENTATIONS
The overall procedure of the proposed method is provided in Algorithm T In our experiments, we Pytorch geometric library (Fey & Lenssen 2019) and four GeForce RTX 3080 GPUs for all implementations.
D.2 BASELINE METHODS DETAILS
We consider the baseline methods following Yu et (202))
Deng & Zheng (021). For adapting
to online GNN evaluation, we only compare with baselines that do not require accessing the original training graph when estimating the generalization emros the test graph.
ConfScore. This metric (Hendrycks & Gimpel 2016) utilizes the softmax outputs of classifiers of the well-trained CNNs on the unseen and unlabeled test images, which be calculated as:
1 M Σ max Softmax (fe- (x)))
ConfScore
where fe- (-) denotes the well-trained CNN's classifier with the optimal parameter 0*, and s(-) denotes the score function working on the softmax prediction fe- (-). When the context clear, we will use f()) for simplification.
Entropy This metric (Hendrycks & Gimpel 2016) caleulates the entropy of the softmax outputs of the well- well-trained CNN classifiers as:
Entropy
Σ
Ent (Softmax (fo- (x))))
(10)
17

---

Published as a conference paper at ICLR 2024
where Ent(f(x))) = =
= fx(x) (fx()))).
Average Thresholded Confidence (ATC) Its Variants. This metric (Garg et al. 2022) learns threshold on CNN's confidence to estimate the accuracy the fraction of unlabeled images whose confidence scores exceed the threshold as:
ATC E1 {s (Softmax (fe. (xx))) < <t). M 5=1
1
(11)
We adopted two different score functions, deriving two variants as: (1) Maximum confidence vari- ant ATC-MC with sf((x))) maxkey f& (xx); and (2) Negative entropy variant ATC-NE with
s s((()))) = Ex [x(xx) log (x)), where {1, 2,, : C} the label space. And for in Eq. it is calculated based on the validation set of the observed training set
E Swa:
iss (Softmax (fo. (xx)l)) <t}
1 (p val 0*) # y
(12)
N
where p(-) denotes the predicted labels of samples.
"Threshold-based Method. This is an intuitive solution introduced by (Deng & Zheng 2021), which not a learningbbased method. It follows the basic assumption that class prediction will likely be correct when it has a high softmax output score. Then, the threshold-based method would provide the estimated accuracy of model as:
M Test Error = 1i=1 {max (So- (x,() >r]
(13)
M
where 7 is the pre-defined thresholds as {0.7,00 0.8, 0.9} on the output softmax logits of CNNs. This metric calculates the percentage of images in the entire dataset whose maximum entries of logits greater than the threshold т, which indicates these images correctly classified.
D.3 WELL-TRAINED GNNs DETAILS
We use two-layer GNN models for all experiments. Except for OGB-arxiv dataset with the hid- den feature dimension 128 and the output embedding dimension 16, all other datasets are with hidden feature dimension 256 and the output embedding dimension 32. The well-trained GNNs performance on each dataset's 's validation is shown in Table A6 and the ground-truth test error
distributions for all datasets are provided in Fig. Al
A2
A3
A5
Table A6: GNN well-training hyper-parameter settings (LR: learning rate; WD: weight decay) and node classification accuracy ACCval (%) performance on validation set.
Datasets
Cora
Amazon-Phood Photo
OGB-arxiv
Models
LR
WD
ACC,u (%)
WD
ACC,,) (%)
WD
ACCap (%)
GCN
L00E-03
5.00E-04
88.44
L.00E-03
0.00E+00
95.37
1.00E-02
1.00E-03
57.78
GAT
L00E-03
5.00E-04
99.00
L00E-03
0.00E:00
98.25
2.00E-02
5.00E-04
58.04
SAGE
1.005-03
5.00E-04
99.45
1.00E-03
0.00E+00
99.88
1.00E-022
5.00E-04
59.35
GIN
5.00E-04
5.00E-04
89.29
5.00E-05
0.00E400
85.22
1.00E-02
5.00E-04
53.28
MIPP
1.00503
5.00E-04
1.00E:04
0.00F:000
5.00K-03
Datasets
ACMv9
DBLPx8
Citation22
Models
I.R
WD
ACC.a (%)
I.R
WD
ACC.al (%)
I.R
WD
ACCaa (%)
GCN
L00E-03
1.00E-05
76.65
1.00E-03
1.00E-04
75.94
1.00E-03
1.00E-04
100E-04
81.95
GAT
2.00E-03
L00E-04
75.17
2.00E-03
L00E-05
71.99
5.00E-04
1.00E-04
81.10
2.00E-03
1.00E-05
75.03
2.00E-03
5.00E-05
1.001:03
1.00E-04
GIN
5.00E-04
5.00E-05
70.18
2.00E-03
1. 1.00E-04
68.22
2.00E-03
5.00E-05
80.25
MLP
L.00E-04
1.00E-04
73.82
L.00E-04
L.00E-04
71.63
5.00E-04
1.00E-04
79.41
18

---

Published as a conference paper at ICLR 2024
Cor GCN
Amsrem thato GCN
ACMs GEN
CT Telt
G7 Tast m0
GT Toxt
Figure A1: Ground-truth test enror distributions of all test-time graphs on well-trained GCNs.
GAT
Ammers Pa GAT
ACMsPua GAT
1.8
1.0
C7 Tux orne
07 Teat 4010
CT Tuat
Figure A2: Ground-truth test error distributions of all test-time graphs on well-trained GATs.
19

---

Published as a conference paper at ICLR 2024
Cara IaAA
Amare-PPattaa SAGE
ACMec SAGE
2.
14
Tel
GT
CT Test
G7 Tast m0
GT Text
Figure A3: Ground-truth test error distributions of all test-time graphs on well-trained SAGEs.
GIN
Aumme- GEN
ACMd GIN
Dan00
34
CT Tux Arn
07 Text 4TA
07 Tax mis
Figure A4: Ground-truth test enor distributions of all test-time graphs well-trained GINs.
20

---

Published as a conference paper at ICLR 2024
12
0.5
DGL PAE MILP
Chudaee en MILP
DIGB-ardt MILP
16
Deaty
07
Figure A5: Ground-truth error distributions of all time graphs on well-trained MLPs.
OCN
Copa es OEN
Con OCX
Cara OCN
Figure A6: Correlation visualization comparisons between existing methods and our proposed LEBED on Cora with well-trained GCNs.
21

---

Published as a conference paper at ICLR 2024
Amtore-Phuss GXT
Aharss GAT
Amertiba GAT
Amaasefhe GAT
Aatemn/fottsa...o GAT
Arptree GAT
Amsooribala in GAT
5
Figure A7: Correlation visualization comparisons between existing methods and our proposed LEBED on Amazon-Photo with well-trained GATs.
100
GIN
Pvs
31 E2
ATCAB
5
GET MOTCOTE
ThmeAT
Thmool
Thmo
Libeb-0em
Figure A8: Correlation visualization comparisons between existing methods and our proposed LEBED on DBLPv8 with well-trained GINs.
Diikerdiree MLLP
OcBank MEP
OGE-arth NEP
DiBlardr ML
A7
83
ATDACC
ATCAE
130047
Lebub Louu
Correlation visualization comparisons between existing methods and our proposed LEBED on OGB-ar arxiv with well-trained MLPs.
Figure A9:
22


Reviews:
[{"review_id": "exC2A4vdH1", "reviewer": "Reviewer_83YC", "summary": "In this work, the authors proposed a new online GNN evaluation problem, which aims to provide the reference for practical GNN applications on real-world test graphs under test-time distribution shifts. To achieve the goal of estimating the test-time errors, the author proposed a novel GNN retraining strategy with a parameter-free optimality criterion, and this could lead to an effective LEBED score, as the output and the metric to evaluate well-trained GNNs in online setting. Experiments cover diverse distribution shifts, and on different gnn models, it also show correlation with true test error, demonstrating its effectiveness.", "questions": "See weaknesses.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "S1: Problem: online GNN evaluation is a relatively fresh research topic to me, I think the problem that the author identified is novel. And the evaluation definition, setting, and graph distribution shift types, are clear.\n\nS2: Methodology: the author retrained previously trained GNN on the test graph and used a criterion to indicate the GNN is well optimized in a parameter-free manner. Following this, the distance between GNN training parameters is utilized to calculate the LEBED score. I think the entire methodology looks clear and with soundness.\n\nS3: Experiments: the experiments are well designed, and the author attempted to cover different test graph distribution shift cases, which is good and looks convincing. The results in terms of Spearman rank correlation rou and linear fitting R2 well presents the effectiveness of LEBED. Different GNN models are covered in their evaluation. Ablation study, running time, hyperparameter sensitivity, correlation visualization are properly provided.", "weaknesses": "W1: in page 4, the authors argued that DPred. is used as the supervision signal for instructing the GNN retraining and DStru. as the self-supervison stop criterion, and according to my understanding, it might be not hard to use both of them to instruct GNN retraining, why only use the Dpred? \n\nW2: in page 5 stage2, it seems like the proposed method requires the retraining process have the same initialization GNN model parameters? how to make sure this point?\n\nW3: for the domain shift experiments, the author used 1/1/369 splits with three domains A, D, C in table.1, for example, does this mean, the training and validation implements on ACM dataset, but 369 test graphs from D and C? this part is not clearly clarfied enough.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aqolP9Xh6W", "reviewer": "Reviewer_CD29", "summary": "This paper studies the training-test graph data distribution shift problem along with GNN model evaluation problem. \nIts method contains a GNN retraining part and a parameter-free optimality criterion. It develops a metric LEBED to estimate the test-time errors of trained GNN models, and this proposed metric can be taken as an indicator to show the performance of GNN on real-world test graphs without labels. Its experimental parts involves many evaluation models and graph datasets with distribution shifts covering node feature, domain, and temporal, the experimental results could demonstrate the metric's effectiveness under the online test-time GNN evaluation scenario.", "questions": "see weakness", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed online GNN evaluation problem under test-time graph distribution shift is insightful. It attempts to understand the well-trained GNN models' performance in the practical GNN model deployment and service scenario, which could be useful to real-world GNN development.\n\n2. The introduction of the proposed evaluation metric is thoughtful with a relatively clear problem definition. The main idea of leveraging the GNN retraining discrepency to align the training-test graph discrepancy is comprehensible when the online scenario does not allow to access the training graphs.\n\n3. The paper tests and evaluates their proposed LEBED metric on a wide range of real-world potential graph distribution shift datasets, it could provide empirical evidence of its practical utility as they claimed. Their findings can be interesting in that some existing CNN evaluation metrics would not commit consistent performance for GNNs.", "weaknesses": "1. In the dataset part, could you provide more details about how the graph distribution shifts are simulated in the experiments? And can these test graph datasets be publicly released?\n\n2. Given the proposed GNN re-training process on test-time graphs, is the parameter-free criterion in Eq.(6) used for stopping the retraining but not being optimized in retraining? More explanations are needed here.\n\n3. How is the ground-truth performance (test error) of these distribution-shifted test graphs on the online GNN models?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LJBBzmmXCw", "reviewer": "Reviewer_sJ17", "summary": "This work proposed a metric named LEBED, learning behavior discrepancy score, for a new research problem \"online GNN evaluation\" in terms of the graph distribution shift issue during test time. By imitating the learning behavior in GNN training parameters, this metric could indicate the GNN model performance without the test graph labels through the parameter space distance between the training and test graphs. Moreover, this work contains a parameter-free optimality criterion which introduces graph structure information to guide GNN retraining on the test-time graphs. Experiments under different training-test graph shifts could verify its effectiveness.", "questions": "See above.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The strength of the work:\n\n(1) The overall idea and research topic of \"online GNN evaluation\" is interesting and novel for understanding the real-world GNN model performance, especially the graph distribution shift issue is also considered, making it more applicable.  This can be a new research direction that inspires future work on GNN model understanding and real-world deployment.\n\n(2) The solution with the proposed LEBED metric for estimating test-time generalization error on graph data appears logical to me. With retraining GNN on the test unlabeled graphs with distribution shifts, its parameter space metric with the context of learning behavior discrepency is reasonable for GNN model evaluation, especially given its graph structure discrepency-related criterion.\n\n(3) The experiments involve graphs with diverse distribution shift cases, domains, and scales, making this metric relatively convincing. And the performance of this method seems effective enough as they argued to indicate the test-time GNN performance.\n\n(4) The paper is well-structured, and easy to understand. Its logic and writing look good to me.", "weaknesses": "Q1: How to explain that some baseline methods with some cases positive values but other cases negative values, more explanations of the experimental results should be provided here.\n\nQ2: How easily can the proposed LEBED be integrated into existing GNN frameworks or pipelines, considering it seems a general GNN model evaluation method covering different models and test graph data?\n\nQ3: Does retraining the GNN on unlabeled test graphs introduce significant computational overhead, and what about the time complexity?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "abjsbfWZnk", "reviewer": "Reviewer_mCrw", "summary": "The paper explores the challenge of evaluating well-trained Graph Neural Network (GNN) models in real-world scenarios where test graph data lacks labels and may differ from the training data's distribution. To address this, the authors propose \"Learning Behavior Discrepancy\" (LEBED) as a score to assess a GNN's generalization ability under test-time distribution shifts. LEBED measures differences in learning behavior between a GNN trained on the training graph and one retrained on the test graph, considering both node prediction and structure reconstruction discrepancies. A novel GNN re-training strategy is introduced for this purpose. The paper's experiments demonstrate that the LEBED score strongly correlates with ground-truth test errors for various GNN models, offering an effective evaluation metric. The paper acknowledges certain assumptions and suggests addressing more complex distribution shifts in future research.", "questions": "See weaknesses.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1.\tNovel Research Problem: The paper addresses a novel research problem, online GNN evaluation. Previous works only consider test the GNN performance after training it. This paper proposes a new research problem that how to evaluate GNN’s performance under distribution shifts and no access to the original training data. From my perspective, it is an important and practical concern in the field of graph neural networks. This is a significant contribution as it explores the evaluation of GNNs under real-world conditions with distribution shifts and the absence of test node labels. It also paves the way to pre-training large-scale GNN models.\n\n2.\tProposed Metric (LEBED): The paper introduces a novel metric, LEBED (Learning Behavior Discrepancy), which aims to estimate the generalization error of well-trained GNN models under distribution shifts. It re-trains the GNN under test data and then calculate the discrepancy of optimal weights between training and test data. Fig 2 gives a clear framework.\n\n3.\tExperimental Validation: The paper conducts extensive experiments on real-world test graphs under diverse distribution shifts, demonstrating the effectiveness of the proposed method. Datasets of various distribution shifts scenarios are provided, including node feature shifts, domain shifts and temporal shifts.", "weaknesses": "1.\tTable 1 shows the test-time graph data. I wonder where did you get the pre-trained GNNs? What datasets were used for pre-training?\n2.\tIn S2, GNN is re-trained was test data. However, if the same training data is used during S2, it will also cause difference of the optimal weights due to the randomness. Will this affect the LeBed score? In other words, is part of LeBed score caused by the randomness of training process? \n3.\tEq. 4 shows that Psuedo label $\\mathbf{Y}_{\\mathrm{te}}^*$ is from pre-trained GNN with test-time data, which has distribution shifts from original training data. Why is it can be used for the supervision of re-training? More explanations are expected here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)