Uncertainty Quantification over Graph with Conformalized Graph Neural Networks

Summary

Conformal Prediction (CP) outputs a prediction set that contains the true label with a certain likelihood given assumptions on exchangeability. It is a well-known and popular uncertainty quantification (UQ) technique. The authors propose a technique that unites GNNs and CP called conformalized GNN (CF-GNN). The technique is crucially permutation equivariant and topology aware.

Strengths

The paper tackles an interesting problem of unifying CP and GNNs. UQ is an important area of research and CP offers strong sound guarantees to tackle such a problem. The paper is well-written and I appreciated that the authors keep important considerations such as permutation equivariance, efficiency and topology in mind when developing their technique. The evaluation is extensive and shows good results.

Weaknesses

The technique focuses on a transductive setting only. While this is still a valid and interesting setting, the fact that the technique focuses on this setting only is a weakness.

Questions

Is there a reason for the focus on the transductive setting? Are there any clear challenges in inductive node-level or inductive graph-level tasks for instance. I believe inductive graph-level tasks to be an extremely interesting approach as doing UQ on molecular predictions may be a very important application. Another important application could also be link prediction.

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

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors address the transductive focus as a limitation which is an important consideration. I don't foresee potential negative societal impact.

Summary

The authors propose Conformalized Graph Neural Networks (CF-GNNs), which extends conformal prediction to graphs for uncertainty quantification. The framework allows a GNN to produce confidence intervals for its predictions, based on an uncertainty estimation on a withhold calibration set. Under permutation invariance condition, they provide theoretical guarantee for the coverage of test-time confidence intervals. Furthermore, a learnable correction model is introduced to empirically produce more efficient prediction intervals. Experiments show that CF-GNNs acheive a better coverage rate over baselines and meanwhile have a more efficient (smaller) confidence interval than a naive conformal prediction.

Strengths

- [originality] the authors extend conformal prediction to node-level task and give theoretical coverage guarantee. As far as I know, this adaption and theorical results are new. - [significance] this work makes solid theoretical and empirical contributions to uncertainty quantifications of graphs. The proposed method has a greater coverage rate and a smaller prediction intervals size.

Weaknesses

See Questions.

Questions

- At Line 276 the authors mention "As smaller coverage always leads to higher efficiency, for a fair comparison, we can only compare methods on efficiency that achieve the same coverage. Thus, we do not evaluate UQ baselines here since they do not produce exact coverage and are thus not comparable". Do you think there is a way to make some of the other UQ methods empirically reach $(1-\alpha)$ coverage so that we can get some senses of their size of prediction sets for comparison?

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

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

No limitation discussed. No potential negative social impact.

Summary

This paper presents a new approach, known as conformalized Graph Neural Networks (CF-GNN), designed to bring reliable uncertainty estimates to graph-structured data prediction models. The study's primary contribution is the innovative adaptation of conformal prediction (CP) to Graph Neural Networks (GNNs). The proposed CF-GNN model is capable of generating prediction sets or intervals that encapsulate the true label, with a level of coverage probability (90%) that can be predefined.

Strengths

The idea of extending conformal prediction to GNNs is quite interesting and timely. The authors establish a permutation invariance condition that justifies the application of CP on graph data and gives a precise outline of test-time coverage. The empirical evidence from numerous experiments validates the effectiveness of CF-GNN, demonstrating that it can meet any specified target marginal coverage while drastically reducing prediction set or interval size by up to 74% when compared to baseline models. The overall presentation is easy-to-follow, and the technical contribution is non-trivial.

Weaknesses

I don't see major flaws in this manuscript, but the introduction to how to construct correlation datasets can be more clear. In addition, the manuscript seems to miss a portion of works [1, 2, 3] on quantifying the uncertainty in GNN predictions. If the proposal of conformal prediction is to quantifying the uncertainty of GNN prediction, then other approaches on uncertainty quantification of node classification with GNNs should not be neglected. [1] Stadler, Maximilian, et al. "Graph posterior network: Bayesian predictive uncertainty for node classification." Advances in Neural Information Processing Systems 34 (2021): 18033-18048. [2] Zhao, Xujiang, et al. "Uncertainty aware semi-supervised learning on graph data." Advances in Neural Information Processing Systems 33 (2020): 12827-12836. [3] Gao, Jiayi, et al. "Topology Uncertainty Modeling For Imbalanced Node Classification on Graphs." ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2023.

Questions

Please refer to the Weakness section.

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

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

I am not seeing limitations.

Summary

This paper proposes a conformal prediction method tailored for graph-structured data. The proposed correction method is topology-aware and based on an empirical observation that inefficiencies correlate highly with network edges. The method updates node predictions based on its neighbors, and it is trainable alongside the GNN model. They also show how regular conformal prediction methods work under

Strengths

[1] The well-motivated problem, clean writing, and detailed related works. [2] The first conformal prediction method for graph-structured data with exchangeability and validity assumptions is GNN agnostic and intuitive. [3] Rigorous proof and method to show exchangeability and validity of conformal prediction on graph-structured data for the first time in the literature. [4] Capable of achieving conditional coverage, which is a stronger version of marginal coverage. [5] In-depth experiments and ablation studies show the efficacy and efficiency of the proposed method.

Weaknesses

[1] Inductive settings for GNN problems are more realistic compared to transductive settings. It is also not motivated why authors start with a transductive setting. [2] There could be ablation studies/experiments over the conformity score functions, such as testing with RAPS[1]. [3] Even though the original coverage definition is used to measure inefficiency, for graph-structured data, there is an inherent non-IIDness in the data. Therefore each sample having equal weights in the coverage calculation is not appropriate. Weighting based on the degree of a node could be a great idea. Would love to discuss this part during the rebuttals. [4] Why is there no experimental comparison with DAPS[2] (ICML23), which is also a conformal prediction method for node prediction? [5] The paper's assumption of exchangeability is strict. What happens if exchangeability does not hold? [1] Angelopoulos, Anastasios, et al. "Uncertainty sets for image classifiers using conformal prediction." arXiv preprint arXiv:2009.14193 (2020). [2[ Zargarbashi, Soroush H., Simone Antonelli, and Aleksandar Bojchevski. "Conformal Prediction Sets for Graph Neural Networks." (2023).

Questions

(1) Why do authors not tackle with inductive node classification problem? (2) What happens if permutation invariance does not hold? (3) What is the reason for not using RAPS[1]? (5) In lines 133-134, while employing conformal prediction. is it even possible to change the trained prediction? (6) My intuitive understanding is that if inefficiency is correlated with the network edges, why degree does not affect the coverage? I feel that coverage for graph data should be redefined for graph-structured data. For example, each sample could be weighted based on the degree of the node. (7) In what circumstances does exchangeability not hold? [1] Angelopoulos, Anastasios, et al. "Uncertainty sets for image classifiers using conformal prediction." arXiv preprint arXiv:2009.14193 (2020).

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors have addressed limitations perfectly. As they also mentioned, this method is valid for transductive settings, but it will not be optimal for inductive settings. Authors also plan to extend it for inductive settings and link prediction tasks. Also, this method is heavily based on the exchangeability assumptions. It is unclear how to modify the algorithm because exchangeability assumptions do not hold.

Summary

This paper studies the problem of providing faithful and "efficient" uncertainty estimates for GNNs. Here faithful means the unknown groundtruth is contained in the prediction set with a probability higher than a threshold; efficient means the prediction set should be as small as possible. Specifically, the proposed method is based on the conformal prediction method, which uses a separate calibration set to determine the threshold used to decide whether a class (for classification) is included in the prediction set. The authors first show that conformal prediction can be applied to GNNs as long as the samples in the calibration and test sets are exchangeable. This further leads to the observation that the test time coverage of the predictions fluctuates a lot when the number of test samples is small. The authors term this problem as the "inefficiency" during conformal prediction. To improve both faithfulness and efficiency of the uncertainty estimates, the authors propose to train a new GNN that uses the original GNN's predictions as input and adjusted predictions as output. Instead of employing the original predictive loss, the paper proposes a loss that is a differentiable proxy of the efficiency metric. This model is trained with a pseudo calibration and test set split from the original validation set. Experiments show better uncertainty estimates compared to well-known approaches such as MC dropout, although the baselines are not designed specifically for GNNs.

Strengths

- The paper formally justifies that conformal prediction can be used under the exchangeability assumption. - The proposed method is simple yet effective: directly optimizing for better uncertainty quantification on a potentially much smaller model.

Weaknesses

- It seems that the calibration GNN needs to be trained for every $\alpha$ separately if we want to have multiple calibration thresholds. It would be nice to show whether it is possible to train a model that adapts to multiple $\alpha$s. - It would be useful to show the tradeoff between the predictive performance and the uncertainty quantification performance. For example, the change in top-1 accuracy of the calibrated and original prediction. - Could the calibration GNN suffer from overfitting? In an extreme case, if $\mathcal{V}_{\mathrm{cor \_cal}}$ and $\mathcal{V}_{\mathrm{cor \_test}}$ are both small, it might be possible that the calibration GNN minimizes its loss by overfitting the labels and make all Vs trivially 0? Maybe this is one reason for only giving the calibration GNN the output of the base GNN?

Questions

- To evaluate $\hat{\eta}$, all samples from the calibration set are needed. If the graph is too large to be processed in a single batch, is it possible to train the calibration GNN in a mini-batch fashion? How would this affect the performance? - It would be nice to show the training cost of the proposed method. I would expect training the calibration GNN could be much faster, but it is better to have more quantitative results.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

3 good

Presentation

3 good

Contribution

3 good

Limitations

I do not see potential negative societal impact of the work.