GNNEvaluator: Evaluating GNN Performance On Unseen Graphs Without Labels

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.

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. 2. 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. 3. 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. 2. 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. 3. 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. 4. 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.

Questions

See the above weakness

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

The authors have adequately addressed the limitations

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.

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. 1. 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). 2. 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). 3. The paper does not provide ablation studies for the predictor in GNNEvaluator (Please refer to Question 3).

Questions

To enhance the manuscript, the authors may consider addressing the following points: 1. 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. 2. 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. 3. 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.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

Yes

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.

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). Also it would be beneficial to see the performance on different architectures (deeper GNN) as right now the GNNEvaluator only uses 2 layers GCN.

Questions

- Related to the problem mentioned above, how we can be certain about the number of DiscGraph generated for first stage? - 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?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

N/A

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. Experimental results on some shifted-distribution graph datasets verify the proposed method and questions' effectiveness.

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. (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. And a new trained GNN regressor on this constructed DiscGraph set for predicting GNN's classification result over the whole dataset is reasonable. (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. (4) This work is well-structured and clearly written with logic.

Weaknesses

See Questions

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. (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? (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?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Response

Thanks for your response. I would like to keep the score since this method is still not of practical use without results on larger datasets.