Online GNN Evaluation Under Test-time Graph Distribution Shifts

We sincerely appreciate your thoughtful review of our paper. We are glad to hear that you recognize the significance of online GNN evaluation problem under test-time graph distribution shifts. We have carefully considered your comments and suggestions, and the following are our detailed responses. We are expecting these could help answer your questions.

---

W1-[Datasets for Pretraining GNN]

We obtained the pre-trained GNNs with the "#Training Graph" for all datasets in Table 1 of our manuscript.

For instance, for the first row "Node feature shifts, Cora" with "#Train/Val/Test Graphs= 1/1/320 (8-artifices)", we use the 1 training graph of the original Cora dataset to pre-train the GNNs and 1 its validation graph to indicate the optimality of the pre-trained GNNs. Then, during the test time, we evaluate our proposed LEBED score on the 320 test graphs with 8 different distinct cases of artificial feature shifts on Cora.

Likewise, for "Domain shifts ACMv9", we also use a single training graph of original ACMv9 for pretraining GNNs with its validation graph, and during the test time, we evaluate our LEBED on 369 test graphs covering three domains of ACMv9, DBLPv8, Citationv2.

For "Temporal shifts OGB-arxiv", as mentioned in "Appendix B TEST-TIME DATASET DETAILS", the training graph for pre-trained GNNs is the year range [1950, 2011] corresponding subgraph of the original OGB-arxiv, [2011, 2014] subgraph for validation. During the test time, three-year periods [2014, 2016], [2016, 2018], [2018, 2020] with 360 test graphs are used for evaluating our LEBED.

---

W2-[Training Data Performance During S2]

We would like to address this concern from two aspects:

Theoretically, when the same training data is used in S2, generally, the "pseudo labels" of the training graph would be very similar to the ground-truth labels, since the pre-trained model has seen and used the label information. Hence, the optimal weights would be also similar when the model starts from the same initialization point without too much randomness.

Empirically, we test the potential randomness from 10 different random seeds with the same training data for S2 on "Cora" datasets on all GNN models. We report the average LEBED score with standard deviation in Table.Re-mCrw-1. As can be observed, the randomness of the training process has minimal impact on the LEBED score, as indicated by the very low standard deviation observed across the same training set.

Table.Re-mCrw-1. The proposed LEBED score on average with standard deviation (±STD) in the S2-Retraining stage over the same training set G_tr within 10 runs.

---

W3-[Psuedo Label Supervise Re-training]

In the context of "online GNN model evaluation", the evaluation of a pre-trained GNN's capabilities on an unseen and unlabeled test graph Gte relies on the outputs from the pre-trained GNN, including the pseudo labels $Y_{te}^{∗}$ and node embeddings $Z_{te}^{∗}$, as specified in Eq.(4). They serve as key reference information from the pre-trained GNN during the testing phase.

During the re-training stage, the meaning of "supervision" for online GNN model evaluation is a little different from model training. Here, the pseudo labels $Y_{te}^{∗}$ are not specifically for supervising GNN to achieve the optimal performance on the test graph, but as a reference guidance to quantify the divergence between the pseudo-labels $Y_{te}^{∗}$ generated by the pre-trained GNN models vs. the predicted labels $\hat{Y}_{te}$ by the re-trained GNN models.

In this case, it can be used for "the supervision of re-training", allowing for evaluating how well the re-trained models can adapt to and predict for the test graph, compared to the initial pre-trained models.

We sincerely appreciate your thoughtful review of our paper. We are so encouraged by your recognition of the “new research direction” for online GNN evaluation, and this means a lot to advancing the GNN deployment in real-world applications, especially under the graph distribution shift scenarios. We have carefully considered your comments and suggestions, and the following are our detailed responses. We are expecting these could be helpful in answering your questions.

---

Q1-[Numeric Values of Baseline Results]

As our proposed LEBED serves as an online GNN evaluation metric, we report all the results based on the correlation between our LEBED scores and the ground-truth test error, using two correlation metrics: the linear correlation R2 (ranging from 0 to 1) and Spearman’s rank correlation (ranging from -1 to 1). Negative values in Spearman’s rank correlation indicate a negative correlation with ground-truth test errors.

For example, as shown in Table 2 of our submission, the baseline method "ConfScore" has a negative correlation of -0.55 with the Amazon-Photo dataset when evaluating the GCN model, but shows a positive correlation of 0.94 when evaluating the GIN model.

These results just reflect the instability and inconsistency of current baseline methods and suggest they may not be ideal or optimal for online GNN evaluation under test-time graph distribution shifts. In contrast, our proposed LEBED achieves consistently positive correlations on all test-time online evaluations over all distribution shifts and well-trained GNN models, demonstrating its effectiveness.

---

Q2-[Ability of Integration into Existing GNN Frameworks]

The proposed LEBED metric is designed to be a versatile measurement for evaluating online GNN models, adaptable to various GNN architectures even under various test-time graph distribution shifts. Besides, our proposed test-time GNN retraining strategy is flexible, requiring only that the GNN architecture of the training and test stages be identical, regardless of the specific architecture used. This flexibility makes it straightforward to integrate LEBED into any existing GNN model framework.

---

Q3-[Computation Costs]

In the "C.1 TIME COMPLEXITY ANALYSIS" section of Appendix in our submission, we outline the computational costs of retraining. These costs depend on various factors: $E$ (the number of edges), $L$ (the number of GNN layers), $q$ (the iteration number of retraining), $d$ (the input feature dimension), $M$ (the number of test graph nodes), and $w$ (the number of overall GNN parameters). The retraining computation costs can be represented as $O(\Omega) + O(q \cdot \Omega) + O(M^2) + O(w)$, where $O(\Omega) = O(LMd^2) + O(E).$ This process is primarily influenced by the size of the test graphs and the retraining iterations. Generally, the computation costs during test time are not excessive but are comparable to the original GNN training process on the training graph.

Thanks for your insightful and constructive review of our work. We especially appreciate your interest in online test-time distribution shift scenarios and our proposed online GNN evaluation problem. We are encouraged to know that our efforts on "GNN retraining discrepency to align the training-test graph discrepancy" have been recognized. Following are our responses, and we are expecting these could help answer your questions.

---

W1-[Graph Distribution Shift Simulation Details]

We have listed how we simulate the graph distribution shifts in "Appendix B TEST-TIME DATASET DETAILS" in the submission. Generally, we follow the same original dataset train/validation/test splits as Wu et al. (2022) for "node feature shifts" and "temporal shifts", and the inductive version of Wu et al. (2020) for "domain shifts".

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 detailed statistical information can be found in Table A1 of the Appendix in our submission.

We are happy to make these distribution-shifted test graphs publicly available for advancing the development of the new topic of "online GNN evaluation" after the review.

---

W2-[Role of Parameter-free Criterion in Retraining]

The parameter-free criterion in Eq.(6) is used for the stop criterion and does NOT participate in the retraining optimization during the test time. We would like to provide more explanations as follows (also Ref. Page-5 paragraph behind Eq.(7) in the manuscript).

The principle of our proposed LEBED score is to measure the learning behavior discrepancy in GNN model's parameter space. To ensure an accurate comparison of optimal parameters between $GNN_{tr}$ (the training GNN) and $GNN_{te}$ (the test-time GNN), it's essential to maintain consistent learning objectives.

Typically, the training of $GNN_{tr}$, which may not be available during online test time evaluation, is focused solely on a classification objective. This objective involves $D_{Pred.}$, represented by cross-entropy loss, and does not typically encompass a self-supervised objective like $D_{Stru.}$ Therefore, to maintain alignment with the original training objectives of $GNN_{tr}$, we opt to update the retrained GNN during test time using only $D_{Pred.}$ as the objective function.

---

W3-[Ground-truth Test Graph Performance Under Distribution Shifts]

We have included the ground-truth test error distribution histograms of all test graphs over all well-trained GNN models in Fig. A1 to Fig. A5 in the Appendix of our submission.

These figures demonstrate the extensive range of test error scenarios our evaluation protocol can encompass, when applied to online test graphs, particularly under various distribution shifts across different GNN models.

For example, Fig. A1 showcases that the online Cora test graphs with node feature shifts, exhibit a broad range of ground-truth test errors, from 0.1 to 0.7, on the well-trained GNN models. These wide variations in test errors reflect that our experimental results could cover comprehensive online GNN evaluation cases under test-time distribution shifts. We have added the corresponding analysis to Appendix D3 in the final version.

We sincerely appreciate your valuable suggestions and comments on our work, and we are pleased to learn that the practical value of our proposed LEBED score for online GNN evaluation is positively identified by the reviewer. The following are our detailed responses to the reviewer’s thoughtful comments. We are expecting these could be helpful in answering your questions.

---

W1-[$D_{Pred.}$ for GNN retraining]

We agree that it is possible and feasible to incorporate both $D_{Pred.}$ and $D_{Stru.}$ into the test-time GNN retraining optimization objective, but we still choose to only use $D_{Pred.}$ as learning objective and $D_{Stru.}$ as the stop criterion for the following reasons (Ref. Page-5 paragraph behind Eq.(7) in the manuscript):

The principle of our proposed LEBED score is to measure the learning behavior discrepancy in GNN model's parameter space. To ensure an accurate comparison of optimal parameters between $GNN_{tr}$ (the training GNN) and $GNN_{te}$ (the test-time GNN), it's essential to maintain consistent learning objectives.

Typically, the training of $GNN_{tr}$, which may not be available during online test time evaluation, is focused solely on a classification objective. This objective involves $D_{Pred.}$, represented by cross-entropy loss, and does not typically encompass a self-supervised objective like $D_{Stru.}$ Therefore, to maintain alignment with the original training objectives of $GNN_{tr}$, we opt to update the retrained GNN during test time using only $D_{Pred.}$ as the objective function.

---

W2-[Same GNN Initialization]

Yes, our proposed LEBED score necessitates that the $G_{te}$ retraining process during test time begin with the same GNN parameter initialization as used in the original $G_{tr}$ training process.

To achieve this, it's important to preserve the initialization parameters of the well-trained GNN models. These parameters should then be reapplied in the online test time evaluation to ensure the retraining process to be optimized from the same start point as that in the training stage.

---

W3-[Domain Shift Dataset Details]

For "Domain shifts ACMv9", we use a single training graph of original ACMv9 for pretraining GNNs, while a single validation graph of original ACMv9 for indicating its optimality.

During the test phase, we evaluated our LEBED score across 369 test graphs. These graphs spanned three distinct domains: ACMv9, DBLPv8, and Citationv2, thereby encompassing a wide range of domain shifts. And as provided details in Table A1 of the Appendix, we have test graphs with ACMv9=#41, DBLPv8=#164, and Citationv2=#164 (total: 369).