GNNEvaluator: Evaluating GNN Performance On Unseen Graphs Without Labels
Authors: Xin Zheng
Miao Zhang
Chunyang Chen
Soheila Molaei
Chuan Zhou
Shirui Pan
Venue: NeurIPS 2023 poster (2023)
Keywords: graph neural networks
GNN model evaluation
node classification accuracy

Abstract: Evaluating the performance of graph neural networks (GNNs) is an essential task for practical GNN model deployment and serving, as deployed GNNs face significant performance uncertainty when inferring on unseen and unlabeled test graphs, due to mismatched training-test graph distributions. In this paper, we study a *new* problem, **GNN model evaluation**, that aims to assess the performance of a specific GNN model trained on labeled and observed graphs, by precisely estimating its performance (e.g., node classification accuracy) on unseen graphs without labels. Concretely, we propose a two-stage GNN model evaluation framework, including (1) DiscGraph set construction and (2) GNNEvaluator training and inference. The DiscGraph set captures wide-range and diverse graph data distribution discrepancies through a discrepancy measurement function, which exploits the GNN outputs of latent node embeddings and node class predictions. Under the effective training supervision from the DiscGraph set, GNNEvaluator learns to precisely estimate node classification accuracy of the to-be-evaluated GNN model and makes an accurate inference for evaluating GNN model performance. Extensive experiments on real-world unseen and unlabeled test graphs demonstrate the effectiveness of our proposed method for GNN model evaluation.

GNNEvaluator: Evaluating GNN Performance On Unseen Graphs Without Labels
Xin Zheng', Miao Zhang", Chunyang Chen', Soheila Molaei Chuan Zhou', Shirui Pan MMonash University, Australia, Harrin Institute of Technology (Shenzhen), China 3 University of Oxford, UK, *Chinese Academy of Sciences, China, GGrfffth University, Australia xin zhengdmonash. edu, Mlangmiao@hie edu en, chunyang chen@monash edu soheila, www.mollemem.mm Ceng. ax.ac. uk, zhouchuan@amss ac. cn, s. s.pangrriffith. edu. au
Abstract
Evaluating the performance of graph neural networks (GNNs) is an essential task for practical GNN model deployment and serving, deployed GNNs face signifi- cant performance uncertainty when inferring on unseen and unlabeled test graphs, due to mismatched training-test graph distributions. In this paper, we study new problem, GNN model evaluation, that aims to assess the performance of a specific GNN model trained on labeled and observed graphs, by precisely estimating its performance (e.g., node classification accuracy) on unseen graphs without labels. Concretely, propose two-stage GNN model evaluation framework, including (I) DiscGraph set construction and (2) GNNEvaluator training and inference. The DiscGraph set captures wide-range and diverse graph data distribution discrep- ancies through a discrepancy measurement function, which exploits the outputs of GNNs related latent node embeddings and node class predictions. Under the effective training supervision from the DiscGraph set, GNNEvaluator learns precisely estimate node classification accuracy of the to-be-evaluated GNN model and makes an accurate inference for evaluating GNN model performance. Extensive experiments real-world unseen and unlaheled test graphs demonstrate the effectiveness of our proposed method for GNN model evaluation.
Introduction
As prevalent graph data learning models, graph neural networks (GNNs) have attracted much attention and achieved great success for various graph structural data related applications in the real world 36 38 35
46 In practical scenarios GNN model deployment and serving 37 40 43 understanding and evaluating GNN models' performance
14
vital step 3 13 22
where model designers need to determine well-trained GNN models will perform well in practical serving, and users want to know how the in-service GNN models will perform when inferring
their own test graphs [10]. Conventionally, model evaluation utilizes well-annotated datasets for testing to
calculate certain model performance metrics (e.g., accuracy and F1-score) [3 24 23 20) However,
may fail to work well in real-world GNN model deployment and serving, where the unseen test graphs usually annotated, making it difficult obtain essential model performance metrics without ground-truth labels [4 (5). As shown in Fig. (a-1), taking node classification accuracy metric as an example, it typically calculated the percentage of correctly predicted node labels. However, when ground- truth node class labels are unavailable, we can not verify whether the predictions of GNNs are correct, and thus cannot get the overall accuracy the model.
light of this, a natural question, referred to GNN model evaluation problem, arises: in the absence of labels in an unseen test graph, we estimate the performance well- GNN model?
"Coresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Unnoess Text Seuph
MAYY
GNN;
Grugh
[b-1] Conventional model evalnation
GGN
Urosees Text Graph
GraphSAGE
GNN
75
60.5%%
(+-2] propossed mudel evalusttion tncr
(b) applicshle propusse CNNDialaattr.
Figure 1: Illustration of conventional model evaluation the proposed GNN model evaluation with its applicable case. The symbol * indicates GNNs are and fixed during model evaluation.
In this work, we provide a confirmed answer together with an effective solution to this question, as shown in Fig (a-2). Given well-trained GNN model and an unseen test graph without labels, GNN model evaluation directly outputs the overall accuracy of this GNN model. This enables users to understand their GNN models at hand, benefiting many GNN deployment and serving scenarios 45 16 [5]. For example, given a GNN model in service (e.g., a GNN model trained and served with Amazon DGL and SageMaker (.. GNN model evaluation can provide users with a confidence score based on its estimated node classification accuracy, so that users know how much faith they should place in ENN-predicted node labels their unlabeled test graphs. Moreover, as shown in Fig. [ (b), given set of available well-trained GNNs in service, GNN model evaluation can provide users with reliable guidance make informed choice among these deployed GNN models on their own unlabeled test graphs.
in the real world 2 8 30
25
47
In this paper, we focus on the node classification task, with accuracy the primary GNN model evaluation metric. Developing effective GNN model evaluation methods for this task faces three- fold challenges: Challenge-1: The distribution discrepancies between various real-world unseen test graphs and the observed training graph are usually complex and diverse, incurring significant uncertainty for GNN model evaluation. Challenge-2: It is not allowed to re-train fine-tune the practically in-service GNN model to be evaluated, and the only accessible model-related information its outputs. Hence, how fully exploit the limited GNN outputs and integrate various training-test graph distribution differences into discriminative discrepancy representations is critically important. Challenge-3: Given the discriminative discrepancy representations of training test graph distributions, how to develop an accurate GNN model evaluator to estimate the node classification accuracy of an in-service GNN on the unseen test graph is the key to GNN model evaluation.
To address the above challenges, in this work, we propose a two-stage GNN model evaluation frame- work, including (1) DiscGraph set construction and (2) GNNEvaluator training and inference. More specifically, in the first stage, we first derive a set of meta- meta-graphs from the observed training graph, which involves wide-range and diverse graph data distributions simulate (ideally) any potential unseen test graphs in practice, so that the complex and diverse training-tess graph data distribution discrepancies can be effectively captured and modeled (Challenge-I), Based on the meta- artaa set, we build a set of discrepancy meta-graphs (DiscGraph) by jointly exploiting latent node embeddings and node class predictions of the GNN with a discrepancy measurement function, which comprehen- sively integrates GNN output discrepancies to expressive graph structural discrepancy representations involving discrepancy node attributes, graph structures, and accuracy labels (Challenge-2). In the second stage, we develop a GNNEvaluator composed of a typical GCN architecture and an accuracy regression layer, and we train it to precisely estimate node classification accuracy with effective supervision from the representative DiscGraph set (Challenge-3) During the inference, the trained GNNEvaluator could directly output the node classification accuracy of the in-service GNN on the unseen test graph without any node class labels.
In summary, the contributions of our work are listed follows:
We study a new research problem, GNN model evaluation, which opens the door for understanding and evaluating the performance of well-trained GNNs on unseen real-world graphs without labels in practical GNN model deployment and serving.
Problem.

---

Solution. We design an effective solution to simulate and capture the discrepancies of diverse graph data distributions, together with GNNEvaluator estimate node classification accuracy of the in-service GNNs, enabling accurate GNN model evaluation.
Evaluation. We evaluate our method on real-world unseen and unlabeled test graphs, achieving a low error (e.g., as small as 2.46%) compared with ground-truth accuracy, demonstrating the effectiveness of our method for GNN model evaluation.
Prior Works. Our research related existing studies on predicting model generalization error, which aims to estimate a model's performance on unlabeled data from the unknown and shifted distributions 6 9 34 T0 However, these researches are designed for data in Euclidean space (e.g., images) while our research is dedicatedly designed for graph structural data. Our research also significantly differs from others in unsupervised graph domain adaption
33
39 29 out-of-
distribution (OOD) generalization [18 48) and OOD detection [19 26 in the sense that we aim to estimate well -rained GNN models' performance, rather than improve the generalization ability of new GNN models. Detailed related work can be found in Appendix
2 Problem Definition
Preliminary. Consider that we have a fully-observed training graph = (X, A, Y), where X E Nxd denotes N nodes with d-dimensional features, R denotes the adjacency matrix indicating the edge connections, and Y E IRN denotes the C-classes of node labels. Then, training a GNN model on for node classification objective can be denoted as:
min Lass 0g
Y Y where Zs, Y GNNo, A).
where 0s denotes the parameters of GNN trained on S, Zg Nxd is the output node embedding of graph from GNNo and Y R.NCC' denotes GNN predicted node labels. By optimizing the node classification loss function Lets between GNN predictions Y and ground-trute truth node labels Y, i.e., cross-entropy loss, could obtain well-trained GNN with optimal weight parameters 0-x denoted as GNN"s Then, the node classification accuracy can be calculated to reflect GNN performance as: Acc(S) Σ .N i=1 (Ú: = y:/NN, which indicates the percentage of correctly predicted node labels between the GNN predicted labels i Y and ground truths y Y. Given an unseen and unlabeled graph T = (X', A') including M nodes with its features X' E IR M xd and structures A' E IR- xMM we assume the covariate shift between S and T, where the distribution shift mainly lies in node numbers, node context features, and graph structures, but the label space of T keeps the same with S, i.e., all nodes in T are constrained in the same C-classes. Due the absence of ground -trth node labels, we could NOT directly calculate the node classification accuracy to assess the performance of the well-trained GNN on T. In light of this, we present a new research problem for GNNs as:
Definition of GNN Model Evaluation. Given the observed training graph S, its well-trained model GNN and an unlabeled unseen graph T inputs, the goal of GNN model evaluation aims to learn an accuracy estimation model f-) parameterized by & as:
Acc(T) = f (GNN' T)
where fø (GNN's T) + and RR is scalar denoting the overall node classification accuracy Ace(T) for all unlabeled nodes of 'T. When the context clear, we will use (T) for simplification.
3 The Proposed Method
3.1 Overall Framework of GNN Model Evaluation
As shown in Fig. [ the proposed overall framework of GNN model evaluation contains two stages: (I) DiscGraph construction; and (2) GNNEvaluator training and inference.
Stage 1. Given the observed training graph S, we first extract a seed graph from it followed by augmentations, leading set of meta-graphs from it for simulating any potential unseen graph distributions in practice. Then, the meta-grape graph set Gmeu and the observed training graph S are fed into
the well-trained GNN for obtaining latent node embeddings, i.e., (f.*) and Z's, respectively. After,
3

---

Graph
Bherepanc Fasciion
Z
DiscGraph Sanc
D()
Xis
train
GNNEvaluater
entruct
@-0
0-6
Inferevve
Estinuttdd Accuracy (37
peotegraphhc Rours
Eburpperyy stmbary 1 Ammray
1 Crettery
Sugpr Etertrrgh
CXVEndlattr informer
Figure 2: Overall two-stage pipeline of GNN model evaluation with (1) DiscGraph set construction and (2) CNNEvaluator training and inference.
discrepancy measurement function (--) works on these two latent node embeddings, leading to ! discrepancy node attributes X Meanwhile, the output node class predictions of well-trained GNN on each meta-graph are used to calculate the node classification accuracy according to its ground- truth node labels, leading to the new @ scalar accuracy labels Vdise- Along with 3 graph structures A lise from each meta-graph these three important components composite the set of discrepancy meta-graphs (DiscGraph) in expressive graph structural discrepancy representations.
Stage 2. In the second stage, the representative DiscGraph set taken as effective supervi- sion to train a CNNEvaluator through accuracy regression. During the inference, the trained GNNEvaluator could directly output the node classification accuracy of the in-service GNN on the unseen test graph T without any node class labels.
3.2 Discrepancy Meta-graph Set Construction
The critical challenge developing GNN model evaluation methods complex and diverse graph data distribution discrepancies between various real-world unseen test graphs and the observed training graph. As the in-service GNN in practice fits the observed training graph well, making inferences on various and diverse unseen test graphs would incur significant performance uncertainty for GNN model evaluation, especially when the node classification accuracy can not be calculated due to label absence.
In light of this, we propose to construct set of diverse graphs to simulate wide-range discrepancies of potential unseen graph distributions. Specifically, such graph set should have the following characteristics: (1) sufficient quantity: should contain a relatively sufficient number of graphs with diverse node context and graph structure distributions; (2) represented discrepancy: the node attributes of each graph should indicate its distribution distance gap towards the observed training graph; (3) known accuracy: each graph should be annotated by node classification accuracy as its label.
To address the characteristic of (1) sufficient quantity, we introduce meta-graph simulation strategy to synthesize wide variety of meta meta-graphs for representing any potential unseen graph distributions that may be encountered in practice. Specifically, we extract seed sub- sub-graph Swod from the observed training graph S. The principle of seed sub-graph selection strategy is that Sweed involves the least possible distribution shift within Is from the observed training graph, and shares the same label space with S, satisfying the assumption of covariate shift. Then, Sweed is fed to pool graph augmentation operators
A [Ai (EdGEDRoP). A A2 (SUBGRAA))) A A4 (NoDEMIX)),
(3)
which belongs to the distribution PA(pe, |e) with {pr] (0, 1) represent the augmentation ratio on Swed for each augmentation type, and e determines the probability sampling a particular augmentation type. For instance, Pi 0.5 means dropping 50% edges in S In this way, we can obtain a set of meta-graphs Gueta = {gmera) with K numbers of graphs, and we have Gmeta IA Ps Soed Giveta For each meta-graph giveta {x A Y! ) where

---

Ximeta E RMx, A E R M: and Y meta E RRM have M, number of nodes, d-dimensional features, and known node labels from Ssee belonging C' classes.
To incorporate the characteristic of (2) represented discrepancy, we fully exploit the outputs of latent node embeddings and node class predictions from well-trained GNN and integrate various training-test graph distribution differences into discriminative discrepancy representa- tions. Specifically, given the GNN's learned latent node embeddings Zis (N, A), and Z (1+)) Y ((:-))
meta E RMMxxd, we derive a distribution discrepancy measurement function D--) to calculate the discrepancy meta-graph node attributes as:
meta meta = GNN's (X A where Z E Rxxx and Z ((++)
X disc = D(Z meta.
Zis)
metaa Z5
Z Z
I
where X disc RMM reflects the node-level distribution discrepancy between each gmeta and S with the well-trained GNN's Each element in x E X denotes the node embedding discrepancy gap between a certain node u in the i-th meta-graph and a node v in the observed training graph. Taking this representation node attributes could effectively integrate representative node-level discrepancy produced by well-trained GNN's s node embedding space.
Meanwhile, the characteristic of (3) known accuracy can be involved with the outputs of node class predictions produced by GNN's on meta-graph {((+)) (imentt..)) M. We calculate the J==1
node classification accuracy on the meta-graph given its ground-truth node class labels Y Y ()meta(()) MM, as:
Mi Ej=1 (fmeta(t,.)
Vaisc Acc(Ometa)
M,
where y ( and Vimeatti..) denote the ground truth label and GNN's predicted label of j-th node in the i-th graph of the meta-graph set, respectively. Note that yåise e R is a continuous scalar denoting node classification accuracy under specific GNN"s within the range of (0, 1).
In this way, by incorporating all these characteristics with the discrepancy node attributes (X the scalar node classification accuracy label V and the graph structure from meta-graph as A dise A for indicating discrepancy node interconnections, we could derive the final discrepancy meta-graph set, ie., DiseGraph set, as
(6) The proposed DiseGraph set Gaist contains a sufficient number of graphs with diverse node context and graph structure distributions, where each discrepancy meta-graph contains the latent node embedding based discrepancy node attributes and the node class prediction based accuracy label, according to the well-trained GNN's outputs, along with diverse graph structures. All these make the proposed DiscGraph set a discriminative graph structural discrepancy representation for capturing wide-range graph data distribution discrepancies.
Gdisc = (gusse 1=1 | where Jase = (Xise disc A Mase)-
3.3 GNNEvaluator Training and Inference
K Training. Given our constructed DiscCraph set Gusce = (gine i=1 and gine = (Xisse A dises Vinee) in Eq. (6). we use it to train a GNN regressor with fo : Páse + a for evaluating well-trained GNNs, which name as GNNEvaluator. Specifically, the proposed GNNEvaluator takes a two-layer GCN architecture as the backbone, followed by a pooling layer to average the representation of all nodes of each d and then maps the averaged embedding a scalar node classification accuracy on the whole graph. The objective function of our GNN regressor can be written as:
min Crey (Xo disec Alssc) Vdrse)
where Lreg is the regression loss, i.e., the mean square error (MSE) loss.
Inference. During the inference in the practical GNN model evaluation, we have: (1) to-be-evaluated GNN', and (2) the unseen test graph T (X', A') without labels. The first thing is to calculate
5

---

the discrepancy node attributes on the unseen test graph T towards the observed training graph S according Eq. ) so that we could obtain X 7 Ziz), where Zi G A'). Along with the unseen graph structure A disc A', the proposed GNNEvaluator could directly output the node classification accuracy of GNN's on ' as:
ACe(T) = Vha = fo- (X diset A
(8)
where Ø" denotes the optimal GNNEvaluator weight parameters trained by our constructed Disc-
Graph set Gms-
4 Experiments
This section empirically evaluates the proposed GNNEvaluator real-world graph datasets for node classification task. all experiments, to-be-evaluated GNN models have been well-trained on observed training graphs and keep FIXED in GNN model evaluation. We only vary the unseen test graph datasets and evaluate various different types and architectures of well-trained GNNs. Throughout our proposed entire two-stage GNN model evaluation framework, we unable to access the labels of unseen test graphs. We only utilize these labels for the purpose of obtaining true error estimates for experimental demonstration.
We investigate the following questions to verify the effectiivness of the proposed method. Q1: How does the proposed CNNEvaluator perform in evaluating well-trained GNNs' node classification accuracy (Sec. 4.2] Q2: How does the proposed GNNEvaluator perform when conducting an ablation study regarding the DiscGraph set component? (Sec. 4.3) Q3: What characteristics does our constructed DiscGraph set have (Sec. (44) ? Q4: How many DiscGraphs in the set are needed for the proposed GNNEvaluator to perform well (Sec. 4.5
4.1 Experimental Settings
Datasets. We perform experiments three real-world graph datasets, i.e., DBLPv8, ACMv9, and Citationv2, which are citation networks from different original sources (DBLP, ACM, and Microsoft Academic Graph, respectively) by following the processing of [29]. Each dataset shares the same label space with six categories of node class labels, including 'Database', 'Data mining'. 'Artificial intelligent', 'Computer vision', 'Information Security', and 'High-performance computing', We evaluate our proposed CNNEvaluator with the following six cases, ie.. A-D, A-C, C-AA, C-D,, D-*,, and D-*,, where A, C, and D denote ACMv9, DBLPv8, and Citationv2, respectively. Each arrow denotes the estimation of GNNEvaluator trained by the former observed graph and tested on the latter unseen graph. Note that, in all stages of GaNEvaluator training and inference, we do not access the labels of the latter unseen graph. More detailed statistical information of the used dataset can be found in Appendix
GNN Models and Evaluation. We evaluate four commonly-use GNN models, including GCN [17]. GraphSAGE [12 (abbr: SAGE), GAT (28), and GIN (31) as well the baseline MLP model that is prevalent for graph learning. For each model, we train it on the training set of the observed graph under the transductive setting, until the model achieves the best node classification on validation set following the standard training process, i.e., the well-trained" GNN model. To minimize experimental variability, we train each type of GNN with five random seeds. That means, for instance, we have five well-trained GCN models on the same fully-observed graph with the same hyper- prprr-parreeter space but only five different random seeds. More details of these well-trained GNN models are provided in Appendix[] D We report the Mean Absolute Error (MAE), the average absolute difference between the ground truth accuracy (in percentage) on the unseen graph and the estimated accuracy from ours and baselines on the same unseen graph, across different random seeds for each evaluated GNN. The smaller MAE denotes better GNN model evaluation performance.
Baseline Methods. As our method is the first GNN model evaluation approach, there is no available baseline for direct comparisons. Therefore, we evaluate our proposed approach by comparing it to three convolutional neural network (CNN) model evaluation methods applied to image data. Note that existing CNN model evaluation methods are hard to be directly applied to GNNs, since GNNs have entirely different convolutional architectures working on different data types. Compared with Fuclidean image data, graph structural data distributions have more complex and wider variations due to their non-independent node-edge interconnections. Therefore, make necessary adaptations to

---

Table 1: Mean Absolute Error (MAB) performance of different GNN models across different random
seeds. (GINSs are well-trained ACMv9 dataset evaluated and unlabeled Citation22 DBLPv8 datasets, A-+C and A AD respectively. Best resulls are in bold.)
ACMv9-CCiation CCtaaiinn2
ACMv9-IDBLPM
Methods
GCN
SAGE
GAT
GIN
MLP
Avg.
GCN
SAGE
GAT
GIN
MLP
Avg.
ATC-MC
4.49
8.40
4.37
18.40
34.33
14.00
21.96
24.20
30.30
24.06
26.62
25.43
ATC-MC-C
2
2.41
5.74
4.67
22.00
51.41
17.25
31.15
30.55
30.18
29.71
45.81
33,48
ATC-NE 9
3.97
8.02
4.28
17.35
38.87
14.50
22.93
24.78
30.50
23.74
31.13
26.62
ATC-NE-c 2
4.44
6.09
3.30
23.95
44.62
16.48
34.42
28.31
27.02
30.28
39.28
31,86
Thres. (r = 0.7) 6
32.64
35.81
33.63
50.76
35.28
37.63
9.59
12.14
14.30
32.67
39.72
21.68
Thres. (r = 0.8) G
26.30
29.60
26.18
49.25
35.87
33.44
2.63
7.44
14.47
32.20
40.31
19.41
Thres. 0.9)
17.56
21.34
16.38
46.53
08
27.58
8.20
7.42
16.07
31.47
40.56
20.74
AutoEval-G 6
18.94
26.19
26.12
50.86
32.40
30.90
2.77
2.54
7.25
48.68
29.95
18.24
GXMEvaluator (Ours)
4.85
4.11
12.23
10.14
22.20
10.71
11.80
14.88
6.36
13.78
17.49
12.86
Table 2: Mean Absolute Error (MAE) performance of different GNN models across different random
seeds. (GNNss are well-trained Citationv2 datasct evaluated on the unseon and unlabeled ACMv9 and DBLPv8 datasess, í.e., C-+A and C-+D respectively Best results bold.)
Citation2-AACM
C
Methods
GCN
SAGE
GAT
GIN
MLP
Avg.
GCN
SAGE
GAT
GIN
MLP
Avg.
ATC- 9
9.50
13.40
8.28
35.51
43.40
22.02
22.57
1.37
21.87
29.24
35.20
22.05
ATC-MC-c
6.93
11.75
6.70
38,93
57.43
24.35
33.67
4.92
28.23
30.89
52.59
30.06
ATC-NE 9
8.86
13.04
7.87
34.88
47.49
22.42
23.97
1.86
23.74
28.96
39.72
23.65
ATC-NE-C 9
7.73
13.94
7.63
41.17
62.96
26.69
37.16
4.66
29.43
31.66
58.95
32.37
Thres. 0.7) 6
37.33
36.61
31.68
58.91
34.33
39.77
10.70
23.05
12.74
34.60
38.29
23.88
Thres. (r= = 0.8) 0
29.62
28.95
22.77
57.48
34.53
34.67
5.65
15.01
7.61
34.36
38.43
20.21
Thres. (r 0.9)
19.59
19.06
11.37
55.72
34.56
28.06
10.65
8.28
8.07
34.00
38.44
19,89
AutoEval-Gi G 6
23.01
31,24
26.74
59.66
35.02
28.28
2,57
16.52
6.96
19.20
32.24
24.59
CXNEvaluator (Ours)
5,45
8.53
9.61
29.77
28.52
16.38
11.64
7.02
5,58
6.46
22.87
10.71
enable these methods to work on graph-structured data for GNN model evaluation. Specifically, we compare: (1) Average Thresholded Confidence (ATC) score 991 which learns a threshold on CNN's confidence to estimate the accuracy as the fraction of unlabeled images whose confidence scores exceed the threshold. We consider its four variants, denoting as ATC-NE, ATC-NE-c, ATC-MC, and ATC-MC-c, where ATC-NE and ATC-MC calculate negative entropy and maximum confidence scores, respectively, and '-c' denotes their confidence calibrated versions. In our adaptation, we use the training set of the observed graph under the transductive setting to caleulate these confidence scores, and use the validation set for their calibrated versions. (2) Threshold based Method, which is introduced by [6] and determines three threshold values for = {0.77, 0.8, 0.9} on the output softmax logits of CNNs and calculates the percentage of images in the entire dataset whose maximum entry of logits are greater than the threshold 7, which indicates these images are correctly classified. We make an adaptation by using the GNN softmax logits and calculating the percentage of nodes in a single graph. (3) AutoEval Method 66. which conducts the linear regression to learn the CNN classifier's accuracy based on the domain gap features between the observed training image data and unseen real-world unlabeled image data. We adapt it to GNN models on graph structural data by calculating the Maximum Mean Discrepancy (MMD) measurement as the graph domain gap features extracted from our meta-graph set, followed by the linear regression, which we name as AutoEval-G variant. More details of bascline methods can be found in the Appendix C
4.2
GNN Model Evaluation Results
In Table [ Table and Table we report MAE results of evaluating different GNN models across different random seeds. In general, we observe that our proposed GNNEvaluator significantly outperforms the other model evaluation baseline methods in all six cases, achieving the lowest average MAE scores of all GNN model types, i.e., 10.71 I and 12.86 in A-C and A-D cases, 16.38 and 10.71 in C-AA and C->D cases, and 6.79 and 7.80 in D A and D +C cases, respectively.
More specifically, we observe that some baseline methods achieve the lowest MAE for a certain GNN model type on a specific case. Taking GCN as an example in Table [ ATC-MC-c performs best with 2.41 MAE under A-C case. However, it correspondingly has 31.15 worst MAE under A-DD case. That means, for GCN model that well-trained by ACMv9 dataset, ATC-MC-C provides model evaluation results with significant performance variance under different unseen graphs. Such high-
7

---

Table 3: Mean Absolute Error (MAE) performance of different GNN models across different random
seeds. (GINss are well-trained DBLPv8 datasct and ovaluaatdd the unseen and unlabeled ACMV9 and Citation22 datasets, D-+A and D -C respectively. Best results are in bold.)
DBL DBL.v88- ACM99
DBLPP8 2itaatiio
Methods
GCN
SAGE
GAT
GIN
MLP
Avg.
GCN
SAGE
GAT
GIN
MLP
Avg.
ATC-MC
4.98
31.49
37.08
28.74
30.42
26.54
5.47
29.72
37.43
32.07
36.42
28.22
ATC-MC-C
P
3.42
32.83
40.31
37.68
34.72
29.79
4,66
28.67
43.89
38.13
41.64
31,40
ATC-NE 9
2.83
27.67
40.90
35.88
36.03
28.66
4.25
26.04
39.38
38.38
45.15
30.64
ATC-NE-C
12.95
20.86
39.34
43.41
38.85
31.08
16.87
15.77
40.26
67.64
47.61
33.63
Thres. (r = 0.7) 66
21.66
32.69
39.19
30.10
27.80
30.29
27.22
35.48
34.35
37.99
30.36
33.08
Thres. (r = 0.8) G
18.63
29.34
37.25
25.80
20.34
26.27
22.70
30.86
32.48
32.73
22.36
28.23
Thres. 0.9)
16.12
23.81
43.26
23,73
12.98
23.98
15.63
26.07
35.88
27.15
12.20
23.39
AutoEval-G 6
7.28
9.72
12.05
14.17
22.07
13.06
21.13
15.11
5.65
12.33
31.90
17.22
GXNEvaluator (Ours)
2.46
10.27
6.94
8,86
5.42
6.79
11.68
7.83
3.97
9.62
5.92
7.80
variance evaluation performance would significantly limit the practical applications of ATC-MC-c, as it only performs well on certain unseen graphs. incurring more uncertainty in GNN model evaluation. Similar limitations can also be observed in Table for ATC-MC-c on evaluating GAT model, with 6.70 lowest MAE in C->A but 28.23 high MAE in C->D. Moreover, terms of AutoEval-G method on GraphS AGE model evaluation in Table 3 it achieves the lowest MAE of 9.72 in D-A case, but high MAE of 15.11 in C-^A case. contrast, our proposed GNNEvaluator has smaller MAE variance for different unseen graphs under the same well-trained models. For instance, our GNNEvaluator achieves 4.85 MAE on GCN under A-C case, and 1 11.80 MAE on GCN in A-D case, which is better than ATC-MC-c with 2.41 and 31.15 on the same cases. All these results verify the effectiveness and consistently good performance of our proposed method on diverse unseen graph distributions for evaluating different GNN models.
4.3 Ablation Study
We conduct an ablation study to verify the effectiveness of the proposed DiseGraph set component for our proposed GNN model eval- uation pipeline. Concretely, we replace the DiscGraph set with the meta-graph set for GNNEvaluator training, which does not involve discrepancy node attributes calculated based specific well-trained GNNs' node embedding space with the discrepancy measurement func- tion. The output node classification accuracy (%) of the proposed GNNEvaluator for evaluating five GAT models under different seeds are shown in Fig. 3 with lines for the proposed DiscGraph set (w/ DiscAttr) in green and the meta-grap graph set (w/o DiscAttr) in blue, respectively. And we also list the ground-truth node classification accuracy in histograms for comparison.
Wetkrmane Seteeaarrreeeeeeeeeee Bhet
Figure 3: Ablation study of the proposed Disc- Graph set with discrepancy node attributes (w/ DiscAttr) in green lines vs. the meta-graph set without discrepancy node attributes (w/o Disc in blue lines. And the ground-truth node classifi- cation accuracy is in histograms for reference.
Generally, we observe that the proposed DiseGraph set (w/ DiscAttr) trained GNNEvaluator has better performance for GAT model evaluation than that trained by the meta-graph set (w/o DiscAttr), as all green lines are closer to the ground-truth histograms than the blue line, reflecting the effec- tiveness of the proposed the proposed DiscGraph set, especially the discrepancy node attributes with the discrepancy measurement function. Moreover, the meta-graph set (w/o Disc.Attr trained GNNEvaluator almost produces the same accuracy on a certain GNN type, i.e., its performance stays the same on all five GAT', making it fail to evaluate certain GNN model type under different optimal model parameters. That is because, compared with the proposed DiscGraph set, the meta-grape set lacks the exploration of the latent node embedding space of output node class predictions from the well-trained GNNs. contrast, the proposed DiscGraph set fully exploits both latent node embedding space and output node class predictions of well-trained GNNs for comprehensively modeling the discrepancy between the observed training graph and unseen test graph, enabling its superior ability for GNN model evaluation.
GNNs and only utilizes the
8

---

Nede Atinhetesta DevGrnghh A1A55 (1..N (G0N)
Madie Avte Bedtes DieeGreph 5006 PPite (SCM) (1 Made Mare-Weeeets Bittrrinph AL3ive groph (SCM)
Figure 4: Visualizations discrepancy node attributes in the proposed DiscGraph set for GCN model evaluation. Darker color denotes a larger discrepancy.
4.4 Analysis Diserepancy Meta-graph Set
We visualize the discrepancy node attributes in the proposed DiscGraph GCN model evaluation trained on ACMv9 and tested on unseen DBLPv88 in Fig. (a). Taking this as a reference, we present visualizations of discrepancy node attributes derived between ACMv9 and arbitrary from our created meta-graph set in Fig. (c) and (d). Darker color close to black indicates larger discrepancy in the output node embedding space of a well-trained GNN, and lighter color close to white indicates a smaller discrepancy. As can be observed, the discrepancy pairs of (ACMv9, unseen DBLPv8), (ACMv9, Meta-graph-I) 1), and (ACMv9, Meta-graph-2) generally show similar heat map patterns in terms of discrepancy. This indicates the effectiveness of the proposed meta-grat weta-graph set simulation strategy, which could capture potential unseen graph data distributions by synthesizing diverse graph data with various graph augmentations. More detailed statistical information about the proposed DiscGraph set, including the number of graphs, the average number of nodes and edges, and the accuracy label distributions are provided in Appendix F
meta-graphss
4.5 parameee Analysis of GNNEvaluator
We test the effeets of differrent numbers of discrep- ancy meta-graphs (K) for GNNEvaluator training in Fig. 5 Concretely, we utilize the number of Disc- Graphs for K [100, 200, 300, 400] to train the pro- posed GNNEvaluator for evaluating five GCN models that well-trained on Citationv2 dataset and make inferences on unseen ACMv9 and DBLPv8 datasets. Considering the average performance under trans- fer cases reflected in the line, despite K = 100 hav- ing higher MAE, the average MAE over two cases does not change much with the number K for train- ing the proposed GNNEvaluator, This indicates that the proposed MoNEvaluator can effectively learn to accurately predict node attributes by training on an ap- propriate number of DiscGraphs, without the need for significantly excessive amount training examples.
MAC Performance over GCMs (ShattewGE-RRMW/LLLLLL
Mura (1
Figure 5: Effects of different numbers of DiscGraphs (K) for GNNEvaluator train- ing. Histograms denote MAE for + A and C + D cases over five GCNs under different K, and the line indicates the aver- age MAE of such two evaluation cases.
5 Conclusion
In this work, we have studied a new problem, GNN model evaluation, for understanding and evaluating the performance of well-trained GNNs on unseen and unlabeled graphs. two-stage approach proposed, which first generates diverse meta-graph set to simulate and capture the discrepancies of different graph distributions, based on which GNNEvaluator is trained to predict the accuracy of well-trained GNN model on unseen graphs. Extensive experiments with real-world unseen and unlabeled graphs could verify the effectiveness our proposed method GNN model evaluation. 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 broader range of natural real-world graph data distribution shifts in the future.

---

Acknowledgment
In this work. S. Pan was supported by an Australian Research Council (ARC) Future Fellowship (FT210100097). M. Zhang was supported by National Natural Science Foundation of China (NSFC) grant (62306084), and C. Zhou was supported by the CAS Project for Young Scientists in Basic Research (YSBR-008).
References
[1] How AWS uses graph neural networks to meet customer needs.
https://ww.anng. amazon neural to
science/bloo hww.//hwwwaae asseussssssse-e--
uses- u-s--grasss-heeeeeee -raph-neural-neteeee
Accessed: 2023-05-16.
[2]
Real-time fraud detection with gnns.
fratii---raudddetecttiooo wwtth-hhh gnn- on dgl
[3] Mayee Chen, Karan Goel, Numat S Sohomi, Fatt Poms, Kayvon Fatahalian, and Christopher Ré, Mandoline: Model evaluation under distribution shift. In International Conference on Machine
Learning (ICML), pages 1617-1629, PMLR, 2021.
[4] Weijian Deng. Stephen Gould, and Liang Zheng. What does rotation prediction tell us about classifier accuracy under varying testing environments? In International Conference on Machine Learning (ICML). pages 2579-2589. PMLR, 2021.
[5] Weijian Deng, Stephen Gould, and Liang Zheng. On the strong correlation between model invariance and generalization. In Advances in Neural Information Processing Systems (NeurIPS),
2022.
[6] 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), pages 15069-15077 2021.
[7] DC Dowson and BV666117 Landau. The fréchet distance between multivariate normal distribu- tions. Journal of multivariate analysis, 12(3):450-455 1982.
[8] Lukas Galke, lacopo Vagliano, and Ansgar Scherp. Can graph neural networks go ,,online "?
an analysis of pretraining and inference. In Representation Learning on Graphs and Manifolds: ICLR 2019 Workshop, 2019.
[9] Saurabh Garg, Sivaraman Balakrishnan, Zachary Chase Lipton, Behnam Neyshabur, and Hanie Sedghi. Leveraging unlabeled data to predict distr--distiiuutinn performance. In International Conference Learning Representations (ICLR), 2022.
[10] Devin Guillory. Vaishaal Shankar, Sayna Ebrahimi, Trevor Darrell, and Ludwig Schmidt. Pre- dicting with confidence on unseen distributions. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 1134-1144, 2021.
[11] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International Conference Machine Learning (ICML), pages 1321-1330. PMLR, 2017.
[12] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems (NeuriPS), 2017.
[13] Yiding Jiang, Vaishnavh Nagarajan, Christina Back, and Zico Kolter. Assessing generalization of sgd via disagreement. In International Conference on Learning Representations (ICLR), 2022.
[14] Ming Jin, Yuan-Fang Li, and Shirui Pan. Neural temporal walks: Motif-aware representation learning on continuous-time dynamic graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[15] Ming Jin, Shiyu Wang, Lintao Ma, Zhixuan Chu, James Y Zhang, Xiaoming Shi, Pin- Yu Chen, Yuxuan Liang, Yuan-Fang Li, Shirui Pan, et al. Time-llm: Time series forecasting by reprogramming large language models. arXiv preprint arXiv:2310.0177
2023.
[16] Ming Jin, Qingsong Wen. Yuxuan Liang, Chaoli Zhang, Siqiao Xue, Xue Wang, James Zhang, Yi Wang. Haifeng Chen, Xiaoli Li, Shirui Pan, Vincent S. Tseng, Yu Zheng, Lei Chen, and Hui Xiong. Large models for time series and spatio-temporal data: A survey and outlook. arXiv preprint XrXiv:2310. 10t.:2310010090000
2023.
[17] Thomas N. Kipf and Max Welling. Semi- classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017. [18] Haoyang Li, Xin Wang, Ziwei Zhang, and Wenwu 7hu. Out-of-distributioo generalization on graphs: A survey, arXiv preprint arXiv:2202.00 202.09202..7987. 07987, 2022.
[19] Yixin Liu, Kaize Ding, Huan Liu, and Shirui Pan. Good-d: On unsupervised graph out-of- distribution detection. In Proceedings of the Sixteenth ACM International Conference Web
10

---

Search and Data Mining (WSDM), pages 339-347, 2023.
[20] 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), 2023.
[21] Yixin Liu, Yizhen Zheng, Daokun Zhang, Vincent Lee, and Shirui Pan. Beyond smoothing: Un- supervised graph representation learning with edge heterophily discriminating. In Proceedings of the Association for the Advanced of Artificial Intelligence (AAAI), 2023.
[22] Yuzhe Lu, Zhenlin Wang, Runtian Zhai, Soheil Kolouri, Joseph Campbell, and Katia P Sycara. Predicting
error with confidence optimal transport. In ICLR 2023 Workshop on Pitfalls of Limited Data and Computation for Trustworthy MI. 2023.
[23] 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 Conference on Research and Development in Information Retrieval, 2023.
[24] Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan. Reasoning on graphs: Faithful and interpretable large language model reasoning. arXiv preprint 2r 10.0 10.01061, 2023. [25] Shirui Pan, Linhao Luo, Yufei Wang. Chen Chen, Jiapu Wang, and Xindong Wu. Unifying large language models and knowledge graphs: A roadmap. arXiv preprint arxiv:2306. 08302, 2023. [26] Vikash Sehwag, Mung Chiang, and Prateek Mittal. Ssd: A unified framework for sulf-suuee outlier detection. In International Conference on Learning Representations (ICLR), 2021.
[27] 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 on Neural Networks and Learning Systems (TNNLS), 32(5): 2020.
[28] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations
(ICLR), 2017.
[29] Man Wu, Shirui Pan, Chuan Zhou, Xiaojun Chang, and Xingquan Zhu, Unsupervised domain adaptive graph convolutional networks. In Proceedings of The Web Conference (WWW), pages
1457-1467, 2020.
[30] 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.
[31] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR). 2019.
[32] Jingkang Yang. Kaiyang Zhou, Yixuan Li, and Ziwei Liu. Generalized detection: A survey, arXiv preprint arXiv:21 10.34.... 2021.
[33] Shuwen Yang. Guojie Song, Yilun Jin, and Lun Du. Domain adaptive classification on hetero- geneous information networks. In Proceedings of International Conference on International Joint Conferences on Artificial Intelligence (ICCAI), pages 1410-1416, 2021.
[34] Yaodong Yu, Zitong Yang. Alexander Wei, Yi Ma, and Jacob Steinhardt. Predicting out-of- distribution error with the projection norm. In International Conference on Machine Learning PMLR, 2022.
(ICML), pages
[35] 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 International Conference on Machine Learning (ICML), pages 41737-41752, PMLR, 2023. [36] 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.00 07444, 2022. [37] He Zhang, Xingliang Yuan, Quoe Viet Hung Nguyen, and Shirui Pan. On the interaction between node fairness and edge privacy in graph neural networks. arXiv preprint arXiv:2301.
2023.
[38] He Zhang, Xingliang Yuan, Chuan Zhou, and Shirui Pan. Projective panking-based gnn evasion attacks. IEEE Transactions on Knowledge and Data Engineering (TKDE), 2022.
[39] Y Zhang, G Song, L Du, S Yang, and Y Jin. Dane: Domain adaptive network embedding. In Proceedings of International Conference on International Joint Conferences on Artificial Intelligence (IJCAI), pages 4362-4368, 2019.
[40] 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, 2023.
[41] 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.07000
2022. [42] Xin Zheng, Miao Zhang, Chunyang Chen, Chaojie Li, Chuan Zhou, and Shirui Pan. Multi- relational graph neural architecture search with fine-grained message passing. In 2022 IEEE
11

---

International Conference on Data Mining (ICDM), pages 783-792. IEEE. 2022.
[43] Xin Zheng, Miao Zhang, Chunyang Chen, Quoc Viet Hung Nguyen, Xingquan Zhu, and Shirui Pan. Structure-free free graph condensation: From large-scale graphs to condensed graph-free data.
arXiv preprint arXi::2306, 02664, 2023.
[44] Xin Zheng, Miao Zhang. Chunyang Chen, Qin Zhang, Chuan Zhou, and Shirui Pan. Auto-heg: Automated graph neural network on heterophilic graphs. In Proceedings of the ACM Web Conference (WWW). pages 61 611-620, 2023.
[45] Yizhen Zheng, Vincent CS Lee, Zonghan Wu, and Shirui Pan. Heterogeneous graph atten- tion network for small and madium--sized enterprises bankruptey prediction. In Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKD)), pages 140-151. Springer, 2021.
[46] Yizhen Zheng, Shirui Pan, Vincent Cs Lee, Yu Zheng, and Philip S Yu. Rethinking and scaling up graph contrastive learning: An extremely efficient approach with group discrimination. In Advances Neural Information Processing Systems (NeurlPS). 2022.
[47] Yizhen Zheng, He Zhang, Vincent Lee, Yu Zheng, Xiao Wang, and Shirui Pan. Finding the missing-half: Graph complementary learning for homophily-pree prrnnne and heterophily-pront graphs. International Conference of Machine Learning (ICML), 2CML)
[48] Qi Zhu, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi. Shift-robust gnns: Overcoming the limitations of localized graph training data. Advances Neural Information Processing Systems (NeurIPS), 34:27965-2778 2021.
12

---

Appendix
This is the appendix of our work: 'GNNEvaluator: Evaluating GNN Performance On Unseen Graphs Without Labels'. In this appendix. we present additional information regarding the GNN model evaluation problem and corresponding solutions, including in-depth discussions that distinguish our method from related works, dataset statistics used in our experiments, comprehensive details about our compared baseline methods, training details with the performance of well-trained GNN models on both the test set of the observed graph and the unseen test graphs (for ground-truth reference), and more experimental results with detailed analysis.
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 model's classifier performance on unlabeled data from the unknown distributions in the target domain, when the estimated models' Typically, Guillory et al. [10] proposed to estimate a classifier's ' performance of convolutional neural network (CNN) models on image data based on designed criterion, named difference of confidences (DoC), that estimates and reflects model accuracy. And Garg et al. [9] proposed to learn a score-based Average Thresholded Confidence (ATC) by leveraging the softmax probability of CNN classifier, whose accuracy is estimated as the fraction of unlabeled images that receive a score above that threshold. In contrast, Deng et al. 6 4 directly predicted CNN classifier accuracy by deriving distribution distance features between training and test images with linear regression model.
classifier has been trained well in the source domain with labeled data c
However, these existing methods mostly focus on 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 the model evaluation on GNNs for graph structural data has two critical challenges: (1) different from Euclidean image data, graph structural data lies in mon-Euclidean space with complex and non-independent node-edge interconnections, so that its node contexts and structural characteristics significantly vary under wide-range graph data distributions, posing severer challenges for GNN model evaluation when serving on unknown graph data distributions. (2) GNNs have entirely different convolutional architectures from those of 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 ineur more performance uncertainty.
Hence, in this work, we first investigate the GNN model evaluation problem for graph structural data with clear problem definition and a feasible solution, taking a significant step towards understanding and evaluating GNN models for practical GNN deployment and serving. Our proposed two-stage GNN model evaluation framework directly estimates the node classification accuracy results of specific well-trained GNNs on practical unseen graphs without labels. Our method could not only facilitate model designers to better evaluate well-trained GNNs' performance in practical serving, but also provide users with confidence scores or model selection guidance, when using well-trained GNNs for inferring on their own test graphs.
Unsupervised Graph Domain Adaption. Our work is also relevant the unsupervised graph domain 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, existing UGDA methods focus on mitigating the domain gap by aligning the source graph distribution with the target one. For instance, Yang et al. [33] and Shen al. (27) optimized domain distance loss based on the statistical information of datasets, e.g., maximum mean discrepancy (MMD) metric. Moreover, DANE (39 and UDAGCN (29] introduced domain adversarial methods to learn nomain-invariann embeddings across the source domain and the target domain. Therefore, the critical distinction between our work and UGDA is that our work is primarily concerned with evaluating the GNNs' performance on unseen graphs without labels, rather than improving the GNNs' generalization ability when adapting to unlabeled target graphs. Besides, different from UGDA which uses the unlabeled target graphs in their model design and training stage, the GNN model evaluation problem
13

---

explored by our work is not allowed to access the unlabeled test graphs, i.e, unseen in the whole GNN model evaluation process.
Graph Out-of-distribution (OOD) Generalization & Detection. Out-ofddistribttion (OOD) generalization [8 on graphs aims develop GNN model given several different but related source domains, so that the developed model can generalize well to unseen target domains. Li al. [T8] categorized existing graph OOD generalization methodologies into three conceptually different branches, ie., data, model, and learning strategy, based their positions in the graph machine learning pipeline. We would like to highlight that, even ODD generalization and our proposed GNN model evaluation both pay attention to the general graph data distribution shift issue, we have different purposes: our proposed GNN model evaluation aims to evaluate well-trained GNNs' performance unseen test graphs, while ODD generalization aims to develop new GNN model for improve its performance or generalization capability on unseen test graphs. Morcover, OOD detection [3)]. aims to detect test samples drawn from distribution that is different from the training distribution, with the definition of distribution to be well-defined according to the application in the target domain. Hence, the primary difference between OOD detection and our GNN model evaluation is, OOD detection works on detecting OOD test samples at the data level and our GNN model evaluation works evaluating well-trained GNN's performance ODD data the model level.
B Dataset Statistics
We provide the details of dataset statisties used in our experiments in Table. A1 meet the covariate shift assumption between any pair of test cases.
where these datasets
Table A1: Statistical details of the experimental real-world datasets.
Dataset
# of Nodes
# of Edges
of Features
of Labels
ACMv9
7410
11135
7537
Citationv2
4715
6717
7537
DBLPv8
5578
7341
7537
C Baseline Methods Details
Average Thresholded Confidence (ATC) & Its Variants. This metric [9] learns threshold on CNN's confidence to estimate the accuracy as the fraction of unlabeled images whose confidence scores exceed the threshold as:
M 21(s (Softmax (fo- (xx))) < <t), M j=1
ATC
(9)
where so (-) denotes the well-trained CNN's classifier with the optimal parameter 0", and s(-) denotes the score function working on the softmax prediction of so- (-). When the context is clear, will use (() for simplification. We adopted two different score functions, deriving two variants as: (1) Maximum confidence variant ATC-MC with s( (x()) = max+Ey fx(x)); and (2) Negative
Entropy variant ATC-NE with s(f(xx)) = Ex fx(, log (x))), where y {1, ..... C} is the label space. And for t in Eq. (9), it is calculated based on the validation set of the observed training set (xc") x Syati
N.J
Now
1
i 1 (Softmax (fe- (xxa)))) < <t}
Σ
fp (x)))""0 + y
(10)
N
N
where p(-) denotes the predicted labels of samples. For all the calibration variants with '-c' in our experiments, they conduct standard Temperature Scaling [1]] with following equations:
Pu max Softmax (Z., (T)
(11)
14

---

Table A2: Hyperparameters of learning rate (Ir) and weight decay (wd) in training different GNNs
and MLP.
Datasets
ACMv9
Citationv2
DBLPv8
Models
Ir
wd
Ir
wd
Ir
wd
GCN
0.01
1.00E-05
0.01
1.00F-05
0.01
1.00F-05
SAGE
0.005
1.00E-06
0.005
1.00E-06
0.005
1.00E-06
GAT
0.005
1.00E-06
0.005
1.00E-06
0.005
1.00E-06
GIN
0.01
1.00E-06
0.01
1.00E-06
0.01
1.00E-06
MLP
0.001
1.00E-05
0.001
1.00E-05
0.001
1.00E-05
where Zu denotes the network output logits before softmax and the temperature scaling factor.
"hhreshold-basee Method. This is an intuitive solution introduced by [6. which is not learning- based method. It follows the basic assumption that a class prediction will likely be correct when has high softmax output score. Then, the threshold-basee method would provide the estimated accuracy of a model as:
En max (fo- (x,)) >r}
ACC
(12)
M
where T is the pre-defined thresholds as {0.7, 0.8, 0.9) the output softmax logits of CNNs. This metric calculates the percentage of images in the entire dataset whose maximum entry of logits greater than the threshold 7, which indicates these images correctly classified.
AutoEval Our Adaption AutoEval-G. This is a learning-basee -ased method of estimating classifier accuracy by utilizing dataset-level feature statistics (6). AutoEval synthesizes meta image dataset DD (a dataset comprised of many datasets) from the observed training dataset Doni and conducts the linear regression to learn the CNN classifier's s accuracy based on the dataset-level feature statistics between the observed training image data and unseen real-word world unlabeled image data. The accuracy linear regression with the dataset statistic feature flincar is written as:
finneur FD (Don, D) Monn 11l2 + Tr Euni + E ---2 2-2-222 2 x)+)
(13)
ACC = W1 ftinear + 10
where FD is the Fréchet distance 7 measure the domain gap with the mean feature vectors Mod and the covariance matrices Eon and E of Don and D, respectively. And Tr(-)) denotes the trace of the matrix, wi and wo denote the parameters of linear regression.
We make the following necessary adaptions to expand the AutoEval method to graph structural data on GNN model evaluation, deriving AutoEval-G by: (1) synthesize meta-graph set Gmeta as demonstrated in Sec. 3.2 of the main manuscript; (2) we calculate the Maximum Mean Discrepancy (MMD) distance as AutoEval-G's graph dataset discrepancy representation fíneur which measures the graph distribution gap between the observed training graph S and each meta-graph Jmeta E 9mera with their node embeddings from the well-trained GNNs as:
Kiear MMD(S, Imneta MMD(Zš. ((1 ).
(14)
where Z's = GNN'S (X, A), and Z (i.-) GNN (Xi metal A A
D Well-trained GNN Model Details
In this section, we provide the details of well-trained GNN models in terms of their architecture parameters and training details.
For all GNN and MLP models, the default settings are (a) the number of layers is 2; (b) the hidden feature dimension is 128; (c) the output feature dimension before the softmax operation is 16. The hyperparameters of training these GNNs and MLP are shown in Table A2 The five seeds for training each type of models (GCN, GraphSAGE, GAT, GIN, MLP) are (0, 1, 3, 4), and node classification performance (accuracy) on the test set of each observed training graph and the ground-truth accuracy on the unseen test graphs without labels are shown Table A3 Table A4 Table A5 Table A6 and Table A7 respectively.
15

---

Table A3: Node classification results in accuracy(%) of GCN with different seeds in terms of the test set of the observed graph and unseen test graphs.
GCN
Observed ACMv9
Observed Citationv2
Observed DBLPv8
Seeds
Arest
A->C
GT A->D
Ciest
C->A
GT C-D
Diest
GT D-
GT D-+C
0
83.13
45.51
63,88
88.98
46.86
60.18
97.58
70.81
57.65
I
83.74
49.01
68.09
88.45
40.76
61.60
98.30
68.43
57.90
2
82.73
55.08
69.29
88.45
45.51
60.95
98.57
70.04
53.36
3
83.40
48.89
69.85
89.09
46.09
60.58
98.57
68.11
52.85
83.87
55.63
68.75
88.24
37.25
58.62
98.66
70.61
58.37
Table A4: Node classification results in accuracy (%) of GraphSAGE with different seeds in terms of the test set of the observed graph and unseen test graphs.
SAGE
Observed ACMv9
Observed Citationv2
Observed DBLPv8
Sceds
Ajest
GT A-x
GTA-D
Cest
GT C->A
GT C-D
Diest
GT D->A
GT D-CC
82.32
45.49
63.54
88.98
50.59
59.90
98.66
42.24
42.27
83.54
48.97
69.67
88.14
48.87
58.03
98.84
39.41
35.21
83.67
52.56
71.15
88.45
41.17
54.61
98.39
45.82
55.99
82.79
66.22
88.03
42.20
53.96
98.48
31.30
27.25
47.04
66.67
88.35
37.46
55.70
98.84
36.99
35.14
Table A5: Node classification results in accuracy (%) of GAT with different seeds in terms of the test set of the observed graph and unseen test graphs.
GAT
Observed ACMv9
Observed Citationv2
Observed DBLPv8
Seeds
Agest
GT A C-
GT A-+
Ciss
GTC-A
GT C-+D)
Drest
GT D)
GT D-+C
0
83.00
44.84
72.53
87.82
41.55
57.94
97.85
64.10
51.77
I
82.73
44.18
57.08
88.67
48.80
60.40
98.84
57.03
42.18
2
81.65
45.07
69.59
88.77
45.74
59.04
98.48
39.65
63.99
3
82.79
43.82
60.18
88.98
41.48
61.03
98.93
62.33
58.43
4
81.71
42.04
57.62
87.50
37.04
60.06
98.30
63.64
52.64
Table A6: Node classification results in accuracy (%) of GIN with different seeds in terms of the test set of the observed graph and unseen test graphs.
GIN
Observed ACMv9
Observed Citationv2
Observed DBLPv8
Seeds
Agest
A->
GT
A-D
C
C-A
GT C-
Diest
GT
GT D-
0
82.19
50.37
74.94
88.24
33.35
59,47
98.48
35.13
40.78
I
82.52
43.12
51.58
86.97
35.40
64.83
66.70
35.37
28.14
2
82.86
42.93
58.21
81.57
39.28
65.04
98.93
53.91
30.56
3
82.46
47.93
69.79
87.92
44.59
69.72
63.47
30.61
21.53
82.39
47.04
78.13
88.56
40.23
65.72
98.93
59.39
45.56
Table A7: Node classification results in accuracy (%) of MLP with different seeds in terms of the test set of the observed graph and unseen test graphs.
MI.P
Observed ACMv9
Observed Citationv2
Ohserved DBL.P88
Seeds
Asest
GT A-C
GT A-D
Ciest
GT C-AA
GT C-D
Diest
GT D-+A
GT D-C
71.59
33.28
38.17
74.89
34.48
37.25
62.67
59.18
51.41
70.18
33.47
39.05
74.58
35.30
38.62
63.12
54.44
43.92
2
70.11
42.65
43.67
74.36
34.74
39.12
63.12
53.74
42.59
3
68.62
35.12
39.71
72.56
33.91
37.41
62.94
54.28
44.31
4
69.23
35.95
42.33
74.58
34.41
39.82
64.37
54.08
43.88
16

---

E More Experimental Analysis and Results.
E.1
DiscGraph Statistics
As vital component of our proposed two-stage GNN model evaluation framework, DiscGraph set captures wide-range and diverse graph data distribution discrepancies. By fully exploiting the latent node embeddings and node class predictions from well-trained GNNs, the DiscGraph set involves representative node attributes incorporating diverse discrepancies through a discrepancy measurement function, leading effective instructions for the training of GNNEvaluator, Hence, in the following, show the statistical information of our derived DiscGraph set in Table A8 Note that, each generated DiscGraph set is related specific dataset and a specific well-trained GNN, as it considers the outputs of node embeddings and predictions on well-trained GNN trained by specific graph dataset.
Table A8: Statistics of the proposed DiscGraph in terms GNNs on ACMv9, Citationv2, DBLPv8, where the accuracy label distributions calculate average minimum and maximum node classification accuracy on GNNs with five random seeds with standard deviations (std).
Statistics
DiscGraph-ACMy9
DiscGraph-Citationz
DiscGraph-DBLPPP
#Num of Graphs (K)
400
400
400
#Avg. Num of Nodes
2105
1340
1585
#Avg. Num Edges
1595
927
1205
GCN
39.95 oo 80.45 1.0
13.89
85.36
17.53 57 191.95_0.50
SAGE
39.9510.00) 77.76.2.22
21.29
10.44
19.07
177.27
Accuracy Label Distributions
GAT
39.50=1.01 79.67
19.53=12.271
16.13
19.58e1.3
187.266-3399
(Min. iax.
GIN
28.50=11.11 76.06622.7
13.48
81.50
19.0622.18
63.633116.89
MLP
39.92:10.01 71.91
33.65
177.41 1:0.75
17.71 2:.30 30
644.68 20.11
[i) Mode www.rrttrttttttccoooommm Stacrrpphecoo AOWA sraven DELPPO (SAT)
(1) Mode Attribeter StecGraph oTACM snaee DOLPVO (SAC)) Rode Attrbutt BweGrrgghhhh atADMe unreen DOLIN (GIN
Figure A1: Visualizations on discrepancy node attributes in the proposed DiscGraph set for (a) GAT, (b) GraphSAGE, and (c) GIN model evaluation. Darker color denotes larger discrepancy.
AE Performanes Ciaatien/2-AAC6600
Purformance -Datiom---DUUP
MAE Performance over GCNs (Diattomz -AM
104
200
209
489
106
204
204
469
169
280
300
490
BlusSrophe (1)
('Diairrsph (R)
HB-0201
-0-0201
Owtterrerrr -CELP mendrg
Figure A2; Effects of different numbers of DiscGraphs (K) for CNNEvaluator training with Absolute Error (AE) for each GCN model under C-+A and C-+ cases.
17

---

E.2 More Visualization Results of Discrepancy Node Attributes
In Fig. A1 we present more visualization results on discrepancy node attributes in the proposed DiscGraph set for different GNN models, i.e., (a) GAT, (b) GraphSAGE, and (c) GIN, under ACMv9-DDLPv8 case.
As can be observed, for different GNNs, the node attributes in the proposed DiscGraph set show significant differences, denoting the effectiveness of the proposed discrepancy measurement function, which could capture model-specific discrepancy representations effectively. And such discrepancy representations could instruct our proposed GNNEvaluator learn graph data distribution discrep- ancies with different well-trained GNNs for accuracy regression.
E.3
More Results on The Number of DiscGraphs
We provide more results for illustrating the effects of different numbers of discGraphs for training the proposed ANNEvaluator in Fig. A2 Along with the MAE results reported Fig. 5 in the main manuscript, report the Absolute Error (AE) results for each GCN model under C->A A and C-+D cases. Lower AE denotes better performance. can be observed that different GCN models have different appropriate K values for GNNEvaluator training, but they show similar trends for each unseen test graph in the left and the middle figures. For instance, the proposed GNNEvaluator has highest AE when it trained with K 100 DiscGraphs, and comparable ABs with K 300 and K 400 for evaluating all five GCNs under the C-D case. Nevertheless, in general, as shown in the red 'Avg.' line of the right figure, the performance of the proposed GNNEvaluator would not significantly vary along the number of DiscGraphs when evaluating all GCNs that are well-trained on Citationv2 dataset and served on unseen DBLPv8 dataset.
18


Reviews:
[{"review_id": "VSbMXbwcU2", "reviewer": "Reviewer_nFGD", "summary": "This work proposes a new research problem named GNN model evaluation, to evaluate well-trained GNNs on observed training graphs for testing on real-world unobserved test graphs without labels. To achieve this goal, this work (1)constructs a DiscGraph set to model the distribution differences of graph datasets, and (1) designs a GNNEvaluator to learn on the constructed DiscGraph set and directly output the overall node classification accuracy by a regression model.\nExperimental results on some shifted-distribution graph datasets verify the proposed method and questions' effectiveness.\n", "questions": "(1) How to obtain the seed graph for augmentation to generate the meta-graph? it would be better to show the difference between the observed graph used for training and the created meta-graph for constructing the DiscGraph set.\n\n(2) Do the results in each table (tables 1 2 and 3), share the same trained models? for instance, in table 2, a gcn model is well-trained on citationv2 but evaluated the same model on both acmv9 and dblpv8? \n\n(3) The authors should provide more experimental analysis and discussions to demonstrate why such a method design could benefit gnn model evaluation compared with other baselines. Besides, there might be a typo in table 1 first six columns? should be acmv9 to citationv2 dataset?\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) This work first defines the GNN model evaluation problem, which is a very practical problem in real-world gnn model deployment and selection for user sides. This work has good originality and explores a new research problem for real-world GNN deployment and applications. It could inspire some interesting explorations in terms of GNN model service and deployment.\n\n\n(2) The challenges of the GNN model evaluation, the corresponding technical solutions proposed by this work and experimental settings are clearly clarified. And the DiscGraph set constructed for capturing the graph dataset discrepancy is novel with sufficient quantity, represented discrepancy, and known accuracy. The calculated distance of two graph dataset distribution as the node attributes sound rational.\nAnd a new trained GNN regressor on this constructed DiscGraph set for predicting GNN's classification result over the whole dataset is reasonable. \n\n(3) The experimental setting could align with the real-world application scenario, and the result parts could support this work's claims. Appropriate ablation study, DiscGraph set analysis, and hyper-parameter analysis provides adequate information for verifying the method's effectiveness with small errors from the ground truth accuracy.\n\n(4) This work is well-structured and clearly written with logic.\n\n", "weaknesses": "See Questions", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer nFGD**\n\nWe sincerely appreciate your thoughtful review of our paper. We are glad to hear that you recognize the significance of GNN model evaluation problem proposed by our work. 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.\n\n**Q1-1: How to extract the seed subgraph**: \nThe seed subgraph is sampled from the observed graph S. For instance, in our experiments, for the observed ACM dataset, we use its 30% nodes to construct the subgraph as the seed subgraph. Thanks for your suggestion and we will add these details to the final version.\n\n**Q1-2:  Show the difference between the observed graph and the constructed meta-graph**: \nAs mentioned in Sec.E.2 and Fig. A1 of our Appendix, we have provided the visualizations on discrepancy node attributes in the proposed DiscGraph set for GAT, GraphSAGE, GIN model evaluations. As can be observed, for different GNNs, the node attributes in the proposed DiscGraph set show significant differences, denoting that our proposed discrepancy measurement function could effectively capture model-specific discrepancy representations effectively. \n\n**Q2:  Do the results in each table (tables 1 2 and 3), share the same trained models**: \nYes, the results in each table (tables 1 2 and 3) share the same trained models. For the GNN model evaluation problem, the well-trained GNN models on observed training graphs should be fixed on the stage of unlabeled real-world graph inference. Hence, a GCN model well-trained on Citationv2 is evaluated the same model on both ACMv9 and DBLPv8.\n\n**Q3: More experimental analysis and discussions to demonstrate why such a method design could benefit GNN model evaluation compared with other baselines**: \nThe good performance of our proposed GNNEvaluator that benefits GNN model evaluation could attribute to the following reasons according to our experimental results: (1) compared with other methods, we comprehensively simulate and capture the discrepancies of diverse graph data distributions within the constructed DiscGraph set (Results in Fig.3, 4, 5 in the main submission); (2) we design a GNNEvaluator to directly and effectively estimate node classification accuracy of unseen and unlabeled real-world graphs (Results in Table 1, 2, 3  in the main submission). Thanks for your valuable suggestions and we will add more discussions and analysis in the final version. In the first six columns of Table.1, it should be acmv9 to citationv2 dataset, and we will correct this typo in the final version.\n"}, {"review_id": "tLRiN6P9fq", "reviewer": "Reviewer_3iA3", "summary": "This paper studies the problem of evaluating a GNN model, to estimate the accuracy on unseen unlabeled data for a well trained model. The goal of this paper is not to improve the generalization error of a GNN model, rather estimate the well-trained model error. This is a novel track for model generalization error, where before only studied in Euclidian data. It contains two parts, DiscGraph, that extracts a set of meta-graphs from the original training graph to simulate and capture the discrepancies of diverse graph data distributions for the aforementioned unseen test graphs. In addition, it proposes GNNEvaluator, a model to estimate the trained model accuracy  on the unseen test data set.", "questions": "- Related to the problem mentioned above, how we can be certain about the number of DiscGraph generated for first stage?\n- What is the time and memory requirement for these additional stages for GNN training? Given the limited and small evaluated graphs, how scalable is current approach?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is a very well written paper, and it is aiming at a new domain of research for GNNs. The proposed idea is very well presented, in addition to detailed analysis of each part of the GNNEvaluator. Due to lack of related work for GNN model, the authors introduced and adapt recent works from recent CNN algorithm. Overall, I found this paper very novel.", "weaknesses": "I found the paper very interesting, however, the experimental studies is very limited (understandable due to the novelty of the problem). However it is not very convincing to see the result only on one set of application (for limited number of labeled class).\nAlso it would be beneficial to see the performance on different architectures (deeper GNN) as right now the GNNEvaluator only uses 2 layers GCN.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer 3iA3**\n\nWe sincerely appreciate your thoughtful review of our paper. We are so encouraged by your recognition of the “new domain of research for GNNs” on GNN model evaluation, and this means a lot to advancing the GNN model inference and deployment in real-world applications. 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.\n\n**W1:  The experimental studies is very limited (understandable due to the novelty of the problem), and clarification of the results on  limited number of labeled class application**:\nThanks for your valuable comments. Due to the complexity and diversification of unobserved and unlabeled test graphs in real-world GNN model evaluation, in our experiments, we have tried our best to involve more experimental cases, for instance, testing 5 typical GNN models on 6 transfer inference cases over 3 datasets,  with totally 5$\\times$6=30 evaluation scenarios (Table 1-3 in the main submission); as well as ablation studies and more discussion (in Fig. 3-5 of the main submission and Table A1-A8, Fig. A1-A2 in Appendix). We are committed to continuous efforts for more comprehensive future studies to advance and explore this new research topic of GNN model evaluation. \n\nFor the label class setting, we assume the observed training graph and the potential unseen and unlabeled test graph has the same number of label classes, for instance, both C-classes. This setting could align with the ability of current well-trained GNN models to be evaluated. When the to-be-evaluated GNN model is well-trained with C-classes on the observed training graph, it can not be directly used for inferring the unlabeled and unseen test graphs with unknown label classes (for example, C+1 classes) since its model architecture has only C-class prediction outputs.\nWe appreciate your insightful comments, and we believe this is a very interesting question.\nAs mentioned at the end of our main submission (Lines 359-361), we are happy to further explore this in the future. \n\n**W2: It would be beneficial to see the performance on different architectures (deeper GNN) as right now the GNNEvaluator only uses 2 layers of GCN**:\nAs shown in following Table.Re-3iA3-1, we compared the results of GCN-Predictor (3-layers) with GCN-Predictor (**2-layers, ours**) on DBLPv8$\\rightarrow$ACMv9 (D$\\rightarrow$A) and DBLPv8$\\rightarrow$Citationv2(D$\\rightarrow$C) on GCN, SAGE, and GAT evaluations. As can be observed, the 2-layer setting in our main submission still achieves generally better performance compared with 3-layer GCN evaluator. \nThe reason behind this might be that the deeper GNN might have an over-smoothing issue when the node features might be too similar to discriminate. Thanks for your thoughtful suggestions and we will add this to the final version.\n\n**Table.Re-3iA3-1. Mean Absolute Error (MAE) performance on different GNNEvaluator layers (the lower, the better).**\n| Datasets |  | D$\\rightarrow$A |  |  |\n| :--- | :--- | :--- | :--- | :--- |\n| Models | GCN | SAGE | GAT | *Avg.* |\n| GCN-Predictor (3-layers) | 4.85 | 11.89 | **5.65** |7.46 |\n| GCN-Predictor (**2-layers, ours**) | **2.46** | **10.27** | 6.94 | **6.56** |\n| **Datasets** |  | **D$\\rightarrow$C** |  |  |\n| Models | GCN | SAGE | GAT | *Avg.* | \n| GCN-Predictor (3-layers) | 17.57 | 11.97 | 5.44 |11.66 |\n| GCN-Predictor (**2-layers, ours**) | **11.68** | **7.83** | **3.97** | **7.83** |\n\n**Q1: How we can be certain about the number of DiscGraph generated for first stage?**: \nAt the first stage, we can not be very certain about the number of DiscGraphs, we can only study the effects by empirical experiments as mentioned in Sec. 4.5 of our main submission. As can be observed, the results slightly change with the number of DiscGraph, but not too sensitive over certain numbers (over 200) on average. \n\n**Q2-1: What is the time and memory requirement for these additional stages for GNN training?**:\nWe test the run time and memory usage on a single NVIDIA GeForce RTX 3080 GPU on GCN model evaluation that is well trained on DBLPv8 dataset, and the running time is only 44.60 seconds per 10 training epochs and the overall dynamic memory usage is only 1990MB. Thanks for your valuable questions, and we will add this to our final version.\n\n**Q2-2 Given the limited and small evaluated graphs, how scalable is current approach?**:\nThe largest graph (ACMv9) used in our experiments contains 7k nodes with 11k edges, and it can still be modeled with the 2-layer GCN evaluator used in our main submission.\nFor the larger scale of unseen test graphs in the real world, we might consider using graph sampling techniques or changing the backbone of the GNN evaluator to make it adapt to super-large graphs, such as GraphSage backboned evaluator, or GraphSAINT backboned evaluator. Thanks for your insightful question and we are happy to explore more on this point in the future.\n"}, {"review_id": "CA4KZYrWss", "reviewer": "Reviewer_jBkz", "summary": "The paper presents a novel problem called GNN model evaluation, aiming to assess the performance of a Graph Neural Network (GNN) on unseen graphs without labels. The authors propose a two-stage GNN model evaluation framework, which includes DiscGraph set construction and GNNEvaluator training and inference. The DiscGraph set is designed to capture diverse graph data distribution discrepancies using a discrepancy measurement function that exploits GNN outputs. The GNNEvaluator, composed of a GCN architecture and an accuracy regression layer, learns to estimate node classification accuracy with effective supervision from the DiscGraph set. The method demonstrates effectiveness in evaluating GNN performance on real-world, unlabeled test graphs, achieving low errors compared to ground-truth accuracy.", "questions": "To enhance the manuscript, the authors may consider addressing the following points:\n\n1. Although the proposed method outperforms the baselines, the prediction error remains high. For example, in ACMv9 -> DBLPv8, the performance of GCN, SAGE, GAT, GIN, and MLP are 45.51%, 45.49%, 44.84%, 50.37%, and 33.28%, respectively, and the evaluation errors are 4.85%, 4.11%, 12.23%, 10.14%, 22.20%, respectively. The relative evaluation errors for various GNNs are quite significant. With such high relative errors, it is challenging for GNNEvaluator to distinguish the performance of any two GNNs. In light of this, what are the practical applications of the proposed method? Including a discussion of compelling real-world applications could make this paper more appealing.\n\n2. While the paper focuses on node classification settings, which is an important application of GNNs, the experiments only evaluate inductive node classification on citation networks. To make the experiments more comprehensive, I suggest that the authors investigate (1) inductive node classification on heterophilous graphs, and (2) transductive node classification.\n\n3. The paper employs a two-layer GCN as a predictor, but detailed ablation studies are missing. For example, (1) what is the variance of the GCN predictor? (2) could a simpler model (e.g., SGC) or a more complex model achieve better performance? It would be beneficial to include such analysis in the paper.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "This paper is the first to evaluate GNN performance on out-of-distribution (OOD) graphs, which may inspire future studies. The meta-graph set construction and the three characteristics are intriguing and useful. Additionally, the proposed method demonstrates significant performance improvements over the baselines.", "weaknesses": "This paper has a few areas that could be improved upon. I would consider raising the score if the authors addressed the first two points. \n1. The paper lacks a discussion of the use cases for the proposed method, considering the prediction error remains relatively high (Please refer to Question 1).\n2. The experiments involve only four datasets, and there is a lack of comprehensive study on node classification in different settings (Please refer to Question 2).\n3. The paper does not provide ablation studies for the predictor in GNNEvaluator (Please refer to Question 3).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer jBkz**\n\nThanks for your insightful and constructive review of our work. We especially appreciate your interest in more exploration experiments of our proposed GNNEvaluator, and we are encouraged to know that our efforts on \"the meta-graph set construction and the three characteristics\" have been recognized. Following are our responses, and we are expecting these could help answer your questions.\n\n**Q1-What are the practical applications of the proposed method?**:\n*Recap*: Our proposed GNNEvaluator aims to provide a feasible solution to know the potential performance of existing well-trained GNNs on real-world unseen graphs “without labels”, by directly predicting accuracy. *Application*: The most straightforward practical application is our GNNEvaluator aids in selecting relatively well-performing GNNs from model collections, enabling us to have confidence in their performance on new, unseen, and unlabeled graphs.  While relatively high prediction errors in mentioned cases (ACMv9 $\\rightarrow$Citationv2, there are 6 classes) in Table 1 of our main submission, we list the rank of different GNN models between the Ground-Truth ACC (%) and our GNNEvaluator predicted ACC (%) in following Table.Re-jBkz-1.  We could observe that our predicted ACC could have a consistent ranking of different GNN models even with different prediction errors.  In this case, we can still place greater trust in the \"GIN\" model although there is still a gap between our prediction and the Ground-Truth. Due to the unexplored research field on \"GNN model evaluation\", we would like to emphasize that our proposed GNNEvaluator achieves this goal by predicting performance on unseen and unlabeled data with classification accuracy. While this is still an early exploration,  our experimental results could shed light on the promising potential for practical model selection applications. We are committed to continuous efforts, and hopefully inspiring future research to reduce the prediction error and further explore this research direction. \n\n**Table.Re-jBkz-1. Rank comparison of different  GNN models between the Ground-Truth ACC (%) and our GNNEvaluator predicted ACC (%).**\n| Models | Prediction error | GT target ACC (%) | Ours predict ACC (%) | Rank-GT-ACC | Rank-Ours-ACC |\n| :---:| :---: | :---: | :---: | :---: | :---: |\n| GCN | 10.09 | 45.51 | 55.61 | 2 | 2 |\n| SAGE | 7.19 | 45.49 | 55.44 | 3 | 3 |\n| GAT | 9.11 | 44.84 | 53.94 | 4 | 4 |\n| GIN | 6.11 | 50.37 | 56.49 | 1 | 1 |\n\n**Q2: Investigate (1) experiments on heterophilous graphs, and (2) transductive node classification.**\nFor **(1) experiments on heterophilous graphs**, we have conducted experiments on two typical webpage heterophilous graphs, Cornell and Texas with heterophily degrees of 0.11 and 0.16, respectively. The MAE experimental results are shown in **Table.Re 1 of the response PDF file**, with Cornell$\\rightarrow$Texas case and Texas$\\rightarrow$Cornell case (the lower, the better). All detailed settings are consistent with our main submission. As can be observed, our proposed GNNEvaluator generally achieves superior performance for all GNN models than other baselines, further demonstrating the effectiveness of our method.\n\nFor **(2) transductive node classification**, it means the test nodes can be seen in the model training process by leveraging their neighbor structure information even without using node labels.\nHowever, this setting is not aligned with the proposed GNN model evaluation scenario, where the unlabeled test graphs are usually unseen for real-world practical applications. For instance, consider a citation network, where new paper nodes continually emerge over time. These new nodes are strictly unavailable during the model's training phase, making the transductive setup unfeasible.\n\n**Q3-1: What is the variance of the GCN predictor?**:\nIn the following Table.Re-jBkz-2, we list the results of Mean Absolute Error (MAE)$\\pm$standard deviation (STD) of different GNN models across five runs to illustrate the variance of our proposed GNNEvaluator (GCN predictor). Compared with baseline method AutoEval-G, our proposed method could achieve better MAE results with comparable even better variance with smaller STD on some cases, for example, for Citationv2$\\rightarrow$DBLPv8 case on GAT model, we have only 0.76 variance, better than 3.17 variance of  AutoEval-G.\n\n**Table.Re-jBkz-2. Mean Absolute Error (MAE)$\\pm$standard deviation (STD) of different GNN models for Citationv2$\\rightarrow$DBLPv8.**\n| Citationv2$\\rightarrow$DBLPv8 | GCN | SAGE | GAT | GIN | MLP |\n| :--- | :---: | :---: | :---: | :---: | :---: |\n| AutoEval-G | 2.57$\\pm$2.24 | 16.52$\\pm$1.88 | 6.96$\\pm$3.17 | 19.20$\\pm$15.36 | 32.24$\\pm$1.92 |\n| GNNEvaluator (**Ours**) | 11.64$\\pm$5.35 | 7.02$\\pm$1.38 | 5.58$\\pm$0.76 | 6.46$\\pm$5.17 | 22.87$\\pm$2.42 |\n\n\n**Q3-2: Could a simpler model (e.g., SGC) or a more complex model achieve better performance?**:\nWe tested the effectiveness of different backbone architectures in terms of GNN predictor in **Table.Re 2 of the response PDF file**. Compared with the GCN-backboned evaluator used in our main submission, we evaluate the simper model SGC-backboned evaluator and a more complex GPRGNN-backboned evaluator with a complex aggregation scheme. \nAccording to the results, the simpler SGC-backboned evaluator fails to achieve satisfactory performance when it is too simple to effectively model complex and diverse graph discrepancies. Although the complex GPRGNN-backboned evaluator could have a relatively good performance in certain SAGE evaluation (although still comparable to our GCN-backboned evaluator), it could not achieve consistently better performance for all GNNs.  In contrast, our proposed GCN-backboned evaluator could be a good and general choice with relatively consistent performance, considering the diversity of real-world application scenarios. We will add these discussions to the final version.\n\n\n"}, {"review_id": "bV7oz8B9CV", "reviewer": "Reviewer_ZAqu", "summary": "This paper addresses the problem of evaluating the performance of well-trained Graph Neural Networks (GNNs) on unseen test graphs without ground-truth labels. Traditional evaluation methods that rely on annotated datasets are not applicable in real-world scenarios where test graphs are unlabeled. The paper proposes a two-stage evaluation framework: DiscGraph set construction and GNNEvaluator training and inference. The framework effectively captures the distribution discrepancies between training and test graphs, models graph structural discrepancies, and estimates node classification accuracy without labeled data. Experimental results indicate the success of the proposed method. ", "questions": "See the above weakness", "limitations": "The authors have adequately addressed the limitations", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. I really appreciate the practical value of this paper since it often requires a long time for evaluation a model in the real-world scenario. The paper introduces the novel problem of evaluating GNN models on unseen test graphs without labels, which is essential for real-world GNN deployment and serving. \n\n2. The proposed framework first constructs a set of meta-graphs to simulate potential unseen test graphs, captures graph data distribution discrepancies, and models graph structural discrepancies using latent node embeddings and node class predictions. The GNNEvaluator is then trained to estimate node classification accuracy based on the representative DiscGraph set. \n\n3. The paper evaluates the proposed method on real-world unlabeled test graphs and demonstrates its effectiveness in estimating node classification accuracy. ", "weaknesses": "1.  In section 3.3, the author introduces extracting a seed sub-graph Sseed from the observed training graph S, Nonetheless, the details about how to extract the seed subgraph lack of introduction. \n\n2.  The estimation of the represented discrepancy is too simple. I am concerned that not be generalized to larger graph in more domains, especially those larger datasets, e.g., ogbn-arxiv, ogbn-products. Those graphs show more diverse patterns and the proposed method may not work in this scenario. \n\n3. The graph argumentation method is to provide sufficient quantity. Nonetheless, the graph argumentation algorithms seem to only disturb the graph very small. I am wondering how those methods can be generalized to other scenarios with larger gap. Moreover, I am wondering whether it can help to predict the performance on the model trained with those graph argumentation techniques, e.g., dropedge.\n\n4.  I am wondering why the GNN evaluator can have the transferability, e.g., the learned GNN evaluator on SAGE can also help to predict the performance of the GCN. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer ZAqu**\n\nWe sincerely appreciate your valuable suggestions and comments on our work, and we are pleased to learn that the practical value of our proposed GNNEvaluator 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.\n\n**W1: How to extract the seed subgraph**:\nThe seed subgraph is sampled from the observed graph S. For instance, in our experiments, for the observed ACM dataset, we use its 30% nodes to construct the subgraph as the seed subgraph. Thanks for your suggestion and we will add these details to the final version.\n\n**W2: Generalize to the larger graph in more domains for represented discrepancy estimation**:\nFor GNN model evaluation, our core idea is to construct a set of discrepancy meta-graphs for modeling complex and diverse graph discrepancies. And in each discrepancy meta-graph, we measure the node-level represented discrepancy by fully leveraging the output node embeddings from well-trained GNN models.\nHence, for larger graphs in more diverse domains (e.g., ogbn-arxiv, ogbn-products), a possible solution is to create more discrepancy meta-graphs to comprehensively cover more diverse patterns with various represented discrepancies.  However, it's worth noting that constructing a thorough, extensive, and diverse discrepancy meta-graph set for more complex and larger graph domains is still a challenging task, and we are happy to further explore this point in the future.\n\n**W3-1: The graph argumentation algorithms seem to only disturb the graph very small, and how those methods can be generalized to other scenarios with larger graph gaps**:\nWe introduce 4 types of graph augmentation methods, and each has 100 random disturbations when the disturbing rate is sampled from a uniform distribution (0,1).  For example, the total 400 disturbations could make the GCN’s node classification accuracy varies in a minimum 17.53% to a maximum 91.95% on DBLPv8 dataset. These results illustrate that the graph argumentation methods could disturb the graph in a relatively large range. Hence, it could generalize to other scenarios with larger graph gaps by involving more graph augmentation methods and more diverse disturbing rates.\n\n**W3-2: Whether GNNEvaluator can help to predict the performance on the model trained with those graph argumentation techniques, e.g., dropedge**:\nYes, our proposed GNNEvaluator can be used to predict the performance of the model trained with graph argumentation techniques. That is because, in the model evaluation stage, the well-trained model is fixed and our proposed GNNEvaluator only leverages its output node embeddings and node class predictions. That means, even the model trained with graph argumentation, our proposed GNNEvaluator could still directly leverage its outputs to predict its performance for its evaluation.\n\n**W4: Why the GNN evaluator can have the transferability**:\nWe would like to clarify the potential misunderstanding here. In our experiments, the “transferability” is reflected in the well-trained GNNs* (e.g, GAT model trained on ACMv9 but used for inference on DBLPv8) *across datasets*. And we use our proposed GNNEvaluator to estimate these well-trained GNNs* transferred node classification accuracy. Hence, our proposed GNNEvaluator should NOT be expected to have the transferability *across models*, since the GNNEvaluator is a model evaluator, so it should be model-specific and driven by different GNN models. If it is learned on SAGE, our whole evaluation process is based on the SAGE’s outputs of node embeddings and class predictions, so that it can only be used for evaluating SAGE, rather than GCN. \n"}]

Author rebuttal:
**Common response to all reviewers**:

We thank all reviewers for their thorough review and valuable suggestions. We are delighted that our contributions have been positively acknowledged, including:

**(1) Novel research question for new domain exploration of GNN model evaluation problem ( @All Reviewers!)**;

**(2) Practical application value for real-world GNN deployment and serving (Reviewer nFGD, Reviewer ZAqu)**;

**(3) Novel, intriguing, and useful discrepancy meta-graph set construction (Reviewer nFGD, Reviewer jBkz, Reviewer ZAqu)**;

**(4) Reasonable GNNevaluator design  (Reviewer nFGD, Reviewer ZAqu)**;

**(5) The experimental setting aligns with the real-world application scenario (Reviewer nFGD), thorough analysis and well-support results (Reviewer nFGD, Reviewer 3iA3, Reviewer ZAqu), significant performance improvements (Reviewer jBkz).**

We greatly appreciate the positive comments on our work. These comments encourage us to continue our efforts in advancing this very young research area of GNN model evaluation. We are expecting this work can be beneficial to advance the GNN model inference and deployment in real-world applications.
More detailed responses are as follows. We hope our responses address all weaknesses and questions! Please let us know if there is any concern. We have considered your valuable suggestions, and have modified accordingly to improve the manuscript in the final version.


Meta-review: This paper studies the important problem of evaluating a GNN model, i.e., to estimate the accuracy on unseen unlabeled data for a well trained model. The methodology presented is interesting and inspiring. The paper is well written, the ideas are novel and the experimental results are convincing.
Decision: Accept (poster)