Uncertainty Quantification over Graph with Conformalized Graph Neural Networks
Authors: Kexin Huang
Ying Jin
Emmanuel Candes
Jure Leskovec
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Graph Neural Networks
Conformal Prediction
Uncertainty Quantification
TL;DR: We study the theoretical condition for conformal validity in graph-structured data to produce guaranteed uncertainty estimates and design a topology-aware method to reduce inefficiency by up to 74%.

Abstract: Graph Neural Networks (GNNs) are powerful machine learning prediction models on graph-structured data. However, GNNs lack rigorous uncertainty estimates, limiting their reliable deployment in settings where the cost of errors is significant. We propose conformalized GNN (CF-GNN), extending conformal prediction (CP) to graph-based models for guaranteed uncertainty estimates. Given an entity in the graph, CF-GNN produces a prediction set/interval that provably contains the true label with pre-defined coverage probability (e.g. 90%). We establish a permutation invariance condition that enables the validity of CP on graph data and provide an exact characterization of the test-time coverage. Moreover, besides valid coverage, it is crucial to reduce the prediction set size/interval length for practical use. We observe a key connection between non-conformity scores and network structures, which motivates us to develop a topology-aware output correction model that learns to update the prediction and produces more efficient prediction sets/intervals. Extensive experiments show that CF-GNN achieves any pre-defined target marginal coverage while significantly reducing the prediction set/interval size by up to 74% over the baselines. It also empirically achieves satisfactory conditional coverage over various raw and network features.

Uncertainty Quantification over Graph with Conformalized Graph Neural Networks
Kexin Huang'
Ying Jin
Emmanuel Candès
Jure Leskovec'
Department of Computer Science, Stanford University
2 Department of Statistics, Stanford University
Department of Mathematics, Stanford University kexinh@cee stanford, edu, ing51@sstan edu, candes@stan edu, jureêcs. stanford.edu
Abstract
Graph Neural Networks (GNNs) are powerful machine learning prediction models graph-structured data. However, GNNs lack rigorous uncertainty estimates, limiting their reliable deployment in settings where the cost of errors is significant. We propose conformalized GNN (CF-GNN), extending conformal prediction (CP) to graph-based models for guaranteed uncertainty estimates. Given an entity in the graph, CF-GNN produces prediction set/interval that provably contains the true label with pre-defined coverage probability (e.g. 90%). We establish a permutation invariance condition that enables the validity of CP on graph data and provide an exact characterization of the test-time coverage. Besides valid coverage, it is crucial reduce the prediction set size/interval length for practical use. We observe key connection between non-conformity scores and network structures, which motivates us develop a topology- model that learns to update the prediction and produces more efficient prediction sets/intervals. Extensive experiments show that CF-GNN achieves any pre-defined target marginal coverage while significantly reducing the prediction set/interval size by up to 74% over the baselines. also empirically achieves satisfactory conditional coverage various raw and network features.
output correction
Introduction
Graph Neural Networks (GNNs) have shown great potential in learning representations for graph- structured data, which has led their widespread adoption in weather forecasting [29], drug discov- [31], and recommender systems [46], etc. As GNNs are increasingly deployed in high-stakes settings, is important understand the uncertainty in the predictions they produce. One prominent approach to uncertainty quantification is to construct prediction set/interval that informs plausible range of values the true outcome may take. A large number of methods have been proposed to achieve this goal [17, 49, 28, 44]. However, these methods often lack theoretical and empirical guarantees regarding their validity, i.e. the probability that the prediction set/interval covers the outcome [2]. This lack of rigor hinders their reliable deployment in situations where errors can be consequential.
Conformal prediction [43] (CP) is a framework for producing statistically guaranteed uncertainty estimates. Given user-specified miscoverage level a E (0, 1). it leverages a set of "calibration" data to output prediction sets/intervals for new test points that provably include the true outcome with probability at least 1 a. Put another way, the conformal prediction sets provably only miss the test outcomes most fraction of the time. With its simple formulation, clear guarantee and
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

distribution- free nature, it has been successfully applied to various problems in computer vision [2, 4], causal inference [30, 22, 47], time series forecasting [11, 48], and drug discovery [21].
Despite its success in numerous domains, conformal prediction has remained largely unexplored in the context of graph-structured data. One primary challenge is that it is unclear if the only, yet crucial, assumption for CP- CP-exchangeability between the test and calibration samples-hoids for graph data. When applying conformal prediction, exchangeability usually ensured by independence among the trained model, the calibration data, and test samples (see Appendix B for more discussion). However, in the transductive setting, GNN training employs all nodes within the same graph-including test for message passing, creating intricate dependencies among them. Thus, to deploy conformal prediction for graph data, the first challenge to identify situations where valid conformal prediction is possible given a fitted GNN model that already involves test information.
Efficiency is another crucial aspect of conformal prediction for practical use: prediction set/interval with an enormous set size/interval length might not he practically desirable even though it achieves valid coverage. Therefore, the second major challenge is to develop a graph-specific approach to reduce the size of the prediction set or the length of the prediction interval (dubbed as inefficiency hereafter for brevity) while retaining the attractive coverage property of conformal prediction.
Present work. We propose conformalized GNN (CF-GNN). extending conformal prediction to GNN for rigorous uncertainty quantification over graphs. We begin by establishing the validity of conformal prediction for graphs. We show that in the transductive setting, regardless of the dependence among calibration, test, and training nodes, standard conformal prediction [43] is valid as long as the score function (whose definition will be made clear in Section 2) is invariant to the ordering of calibration and test samples. This condition is easily satisfied by popular GNN models. Furthermore, we provide an exact characterization of the empirical test-time coverage.
Subsequently, we present a new approach that learns to optimize the inefficiencies of conformal prediction. We conduct an empirical analysis which reveals that inefficiencies are highly correlated along the network edges. Based on this observation, that updates the node predictions based on their neighbors. This model is trained by minimizing differentiable efficiency loss that simulates the CP set sizes/interval lengths. In this way, unlike the raw prediction that is often optimized for prediction accuracy, the corrected GNN prediction is optimized to yield smaller/shorter conformal prediction sets/intervals. Crucially, our approach aligns with the developed theory of graph exchangeability, ensuring valid coverage guarantees while simultaneously enhancing efficiency.
add topology-awan correction model
We conduct extensive experiments across 15 diverse datasets for both node classification and regres- sion with 8 uncertainty quantification (UQ) baselines, covering wide range of application domains. While all previous UQ methods fail to reach pre-defined target coverage, CF-GNN achieves the pre-defined empirical marginal coverage. It also significantly reduces the prediction set sizes/interval lengths by up to 74% compared with a direct application of conformal prediction to GNN. Such improvement in efficiency does not appear to sacrifice adaptivity: we show that CF-GNN achieves strong empirical conditional coverage over various network features.
2 Background and Problem Formulation
Let G X) be graph, where V is a set of nodes, E is a set of edges, and X the attributes, where x. E Rd is a d-dimensional feature vector for node V. The label of node is yo E V. For classification, y is the discrete set of possible label classes. For regression, y IR.
bey is
Transductive setting. We focus on transductive node classification/reeressio problems with random data split. In this setting, the graph is fixed. At the beginning, we have access to {(xv: yo) hEED as the "training" data, well test data Prest with unknown labels {y, beEDes Here D and Disst are disjoint subsets of V. We work on the prevalent random split setting where nodes in D and Diest are randomly allocated from the entire graph, and the test sample size is m |Destl- The training node set D is then randomly split into Dirain/ /Dvatia/ Deatib of fixed sizes, the sidning/validation/cclbbb set, correspondingly. A perhaps nonstandard point here is that we withhold a subset Dealib as "calibration" " data in order to apply conformal prediction later on. During the training step, the data
'See Figure 1 for an overview. The code is available at https: / ///1//g// hhw..bb..bb..gggggggggg...b.b com/ snap- st staford// conformal i izd--nnn
2

---

1
Standard GNN Training
sware Conformal Correction
Standard Conformal Prediction
Classrication
Regression
Vrain
GNN
Calibrate
GNNO
Tost
No labal
]
PC ]e
((X.)
((X))
Coverage Guaranteed partuulaooe Jnowantee (Thwssees !)
VV &
Figure 1: Conformal prediction for graph-structured data. (1) GNN training. We first use standard GNN training to obtain a base GNN model (GNN)) that produces prediction scores (a(;) for node i. is fixed once trained. (2) Conformal correction. Since the training step is not aware of the conformal calibration step, the size/length of prediction sets/intervals (i.e. efficiency) are not optimized. We propose novel correction step that learns correct the prediction to achieve desirable properties such as efficiency. We use a topology- aware correction model GNN,, o that takes (X); as the input node feature and aggregates information from its local subgraph to produce an updated prediction (x).). 0 is trained by simulating the conformal prediction step and optimizing a differentiable inefficiency loss. (3) Conformal prediction. We prove that in transductive random split setting, graph exchangeability holds (Section given permutation invariance. Thus, standard CP be used produce a prediction sct/interval based on j that includes true label with pre-specified coverage rate 1-a.
{(x.. yo) BoD the attribute information in {x. (xeJeeDennn DD and the entire graph structure (V, E) are available to the GNN to compute training nodes representations, while {yo De are not seen.
Graph Neural Networks (GNNs). GNNs learn compact representations that capture network structure and node features. A GNN generates outputs through a series of propagation layers [12], where propagation at layer consists of the following three steps: (1) Neural message passing.
GNN computes message mad MsG(h! (f-1) he () for every linked nodes u, based on their
embeddings from the previous layer h. (1-1) and h (1-1) (2) Neighborhood aggregation. The messages
between node u and its neighbors N₁, are aggregated as f = AGG (moe) E No). (3) Update.
Finally, GNN uses a non-linear function to update node embeddings as h = UPD h b using the aggregated message and the embedding from the previous layer. The obtained final node representation is then fed to a classifier or regressor to obtain a prediction (X)).
Conformal prediction. In this work, we focus on the computationally efficient split conformal prediction method [43]. 2 Given a predefined miscoverage rate a E [o, 1]. it proceeds in three steps: (1) non-conformity scores. CP first obtains any heuristic notion of uncertainty called non-conformity score V: X' x y - R. Intuitively, V(z, y) measures how y "conforms" to the prediction at æ. An example is the predicted probability of class y in classification or the residual value V V(x, y) = ly [zx) in regression for predictor îi: X' + y. (2) Quantile computation. CP then takes the 1 a quantile of the non-conformity scores computed the calibration set. Let ((X,, Y;) be the calibration data, where n = [Deathh] and compute πÿ = quantile( (V(X,, Yi)...., ......,,.. V(X,, Yn),, (1 11)). (3) Prediction set/interval construction. Given new test point Xn+1, CP constructs a prediction set/interval C(X,+1) = (u y: V((n=1.3) S 7) [Z+ 1=+1 : {(x,, Y) are exchangeable," then Vn- == V (X 1 is exchangeable with (Vi)== since ç given. Thus, ((),-i) contains the true label with predefined coverage rate [43]: P(Y E C(x,+
P(VV+1 2 Quantile((Vi..... 1n a) > 1 1-6 a due to exchangeability of [V This framework works for any non-conformity score. CF-GNN is similarly non-conformity score-agnostic. However, for demonstration, we focus on two popular scores, described in detail below.
Adaptive Prediction Set (APS). For the classification task, we use the non-conformity score in APS proposed by [37]. takes the cumulative sum of ordered class probabilities till the true class. Formally,
given any estimator Po (x) for the conditional probability of Y being class j at X = x, 1,..,, we denote the cumulative probability till the k-th most promising class as V(x, k) Σ5 Pr,, (x).
"See Appendix B for discussion full and split conformal prediction. We refer to the split conformal prediction when we describe conformal prediction throughout the paper. "Exchangeability detinition: for any 21, Zn-41 and any permutation π of {l...., + 1}. it holds that P((Z. Lm(n+1)) = (Z1, (21....,22 (n+1)) P((Z...... Zn-1) (#1,..., En+1)).
3

---

where x is a permutation of 3/ so that (r(1)(2)) 2 (T (.) (T(D)))))). Then, the prediction set is constructed as C(x) = (T(1, ... , (T: where k* = =inf(k: 25-1 Pr() (x) 2 fj..
Conformalized Quantile Regression (CQR). For the regression task, use CQR in [36]. CQR is based on quantile regression (QR). QR obtains heuristic estimates (z)2(z)) and (1)a/2(x) for the a/2-th and - a//2-th conditional quantile functions of Y given X = z. The non-conformity score is V(z, y) max maxx(Fo/2(1)) y: y Fi / interpreted as the residual of true label projected to the closest quantile. The prediction interval is then C(x) (x)) 97. (x))//(x)) f7]
In its vanilla form, the non-conformity score (including APS and CQR) CP does not depend on the calibration and test data. That means, fx, Je PansUDes are not revealed in the training process of V. which is the key to exchangeability. In contrast, GNN training typically leverages the entire graph, and hence the learned model depends on the calibration and test attributes in complicated way. In the following, for clarity, we denote any conformity score built on a GNN-trained model as
(a, yi {ze heE IeeDDaDD V,E)
to emphasize its dependence on the entire graph, where 2n = (xx, Y,) for E V.
Evaluation metrics. The goal is to ensure valid marginal coverage while decreasing the ineffi- ciency as much as possible. Given the test set Deest the empirical marginal coverage is defined as Coverage := Dreet] ΣiED.... I(Y; E C(X,)). For the regression task, inefficiency is measured as the interval length while for the classification task, the inefficiency is the size of the prediction set: Ineff := Teawe]
|C((:)]. The larger the length/size, the more inefficient. Note that inefficiency of conformal prediction is different from accuracy of the original predictions. Our method does not change the trained prediction but modifies the prediction sets from conformal prediction.
3 Exchangeability and Validity of Conformal Prediction on Graph
To deploy CP for graph-structured data, we first study the exchangeability of node information under the transductive setting. We show that under general permutation invariant condition (Assumption 1), exchangeability of the non-conformity scores is still valid even though GNN training uses the calibration and test information; this paves the way for applying conformal prediction to GNN models. We develop an exact characterization of the test-time coverage of conformal prediction in such settings. Proofs of these results are in Appendix A.
Assumption 1. For any permutation π of Dealtt U Dresr the non-conformity score V obeys
VIx, y; (EUDDEDann {xe DeEDAuUDen V,E)
= =V(x, yi {2v DoE (xx(v)) (wv))w)eee DED Va Ex),
where (Vz, Ex) represents graph where D Dealib U D Duest nodes (indices) are permuted according to m.
Assumption imposes permutation invariance condition for the GNN training, i.e., model output/non-conformigg score invariant to permuting the ordering of the calibration and test nodes (with their edges permuted accordingly) on the graph. To put it differently, different selections of calibration sets do not modify the non non-conformity scores for any node in the graph. GNN models (including those evaluated in our experiments) typically obey Assumption I, because they only use the structures and attributes in the graph without information on the ordering of the nodes [24, 16, 12].
For clarity, we write the calibration data as {(x,, Yo) where X; = -x,, and U; E Deali is the i-th node in the calibration data under some pre-defined ordering. Similarly, the test data are f(Xn+j. En+;)) 1 where Xnt; Xuy, and v2 E Dies is the j-th node in the test data. We write }
V; = V(X,, Y;; (a))iED (x
V,E), i= 1, n1, 12 + 1,..., , n + m.
V. is a random variable that depends on the training process and the split of calibration and test data. The next lemma shows that under Assumption 1, the non-conformity scores are still exchangeable. Lemma 2. In the transductive setting described in Section 2, conditional on the entire unordered graph EV,E), all the attribute and label information {(x., yu)) and the index sets Duain and
De: == Dealit U DDen the unordered set of the scores [V]]==m are fixed. Also, the calibration
scores (V.)%_ are simple random sample from (V,) [Viee1 That is, for any subset (vi,..., vn) S
(V.) size n, P((V.) {V1...., vn) [V.)
(12.))

---

Based on Lemma 2, we next show that any permutation invariant non non-conformity score leads to valid prediction sets, and provide an exact characterization of the distribution of test-time coverage.
Theorem 3. Given any score V obeying A Assumption I and any confidence level a E (0, 1), we define the split conformal prediction set as C(x) = {y: (ax, y) & î) where
{ n Ei= ((, Yi) < n) 2 (1 - a1- +1/m)
i 7 i-f
Then P(Y+)) E ((Xx+t)) 21-a, -la,,j=-..... m. Moreover, define Cover = Ei=1 1(Yn+5 E Ö(Xn+s)}. If the V/'s, i E Dealib U Dresn have no ties almost surely, then.for any E (0, 1),
P(Cover I = -HG ([(n + 1)(1 - q)1 1: + n, n, [(1 9) + 1)] + [mtt):
where (: N,n, n. k) denotes the cumulative distribution function of hyper-geomens distribution with parameters N, n. (drawing k balls from an urn wherein out of N balls are white balls).
Figure 2 plots the probability density functions (p.d.f.) of Cover at a sequence of & E [0, 1] fixing
1000 while varying m. The exact
40-
100
distribution described in Theorem 3 is useful in determining the size of the calibration data in order for the test-time coverage concentrate sufficiently tightly around 1 - a. More discussion and visualization of Cover under different values of (n, m) are in Appendix A.2. Note that similar exchangeability and validity results are obtained in several concurrent works [15, 33], yet without exact characterization of the test-time coverage.
30-
230
500
20-
750
1000
2000
D-
0.85
0.50
0.55
1.00
coverage
Figure 2: P.d.f. of Cover for 1000 and a 0.05; curves represent different val- ues of test sample size m.
4 CF-GNN: Conformalized Graph Neural Networks
We now propose a new method called CF-GNN to reduce inefficiency while maintaining valid coverage. The key idea of CF-GNN is boost any given non-conformity score with graphical information. The method illustration is in Figure and pseudo-code is in Appendix C.
Efficiency-aware boosting. Standard CP takes any pre-trained predictor to construct the prediction set/interval (see Section 2). A key observation is that the training stage is not aware of the post-hoc stage of conformal prediction set/interval construction. Thus, it is not optimized for efficiency. Our high-level idea is to include an additional correction step that boosts the non-conformity score, which happens after the model training and before conformal prediction. To ensure flexibility and practicality, our framework is designed as a generic wrapper that works for any pre-trained GNN model, without changing the base model training process.
Inefficiency correlation. Our approach to boosting the scores is based on exploiting the correlation among connected nodes. Since the connected nodes usually represent entities that interact in the real world, there can be strong correlation between them. To be more specific, it is well established in network science that prediction residuals are correlated along edges [20]. Such result implies a similar phenomenon for inefficiency: taking CQR for regression as an example, the prediction interval largely depends on the residual of the truc outcome from the predicted quantiles. Hence, the prediction interval lengths are also highly correlated for connected nodes. We empirically verify this intuition in Figure 3, where connected/uncomectee node pairs in the Anaheim dataset using vanilla CQR for GCN. 4 In Figure 3, we observe that inefficiency has a topological root: connected nodes usually have similar residual scales, suggesting the existence of rich neighborhood information for the residuals. This motivates us utilize such information correct the scores and achieve better efficiency.
Motivation:
plot the difference in the prediction interval lengths for
Topology-awe aware correction model. Based on the motivation above, we update the model predictions using the neighbor predictions. However, the relationship in neighborhood predictions could be complex (i.c. beyond homophily), making hcuristic aggregation such as weraging/summing/et.cc overly simplistic and not generalizable to all types of graphs. Ideally, we want to design general and powerful mechanism that flexibly aggregates graph information. This requirement could be perfectly
'That is, we take the predicted quantiles from GCN and directly builds prediction intervals using CQR.
5

---

2.0-
Net Liked
Uniked
V(X,, Yi) V(X,. V(Kar, Yse)
DifiQuaniiee ()).a)
17
proauue:
Prediction Set Size Proxy
Porr-cath
1.0
j((x)) ((X2))
Limet Σ
((V( ///r) 20 kcy
GNNO
0.5-
Prediction Interval Length Proxy
xx(Xx)
Limen
Σ (ai-w/a(Xi) 1 () (aap(())) 8)
0.0
0.0
0.5
1/2
1.5
2.0
Veur-tat
Ineficlencyy Gap A A Nodes
v) L
Figure 3: Inefficiency is corre- lated in the network. Connected nodes have significantly smaller gaps in prediction interval length compared to unconnected nodes.
Figure 4: We simulate the downstream conformal step and optimize for inef- ficiency directly. We first produce differentiable quantile using V V(X;, Yi) from Veor-eal- We then construct a prediction set size/interval length proxy on Veor Veor-test and directly minimize inefficiency loss by updating GNNa.
fulfilled by GNN message passing as it represents a class of learnable aggregation functions over graphs. Therefore, we use a separate GNN learner parameterized by & for the same network G but with modified input node features; specifically, we use the base GNN prediction (X. = (x()) )) as input, and output (xX) o (x),,, G). We will then use (x() as the input for constructing conformal prediction sets/intervals. Note that this second GNN model a post-hoe process and only requires base GNN predictions, instead of access to the base GNN model.
Training with conformal-aware inefficiency loss. Given the hypothesis class, it remains to devise a concrete recipe for training the correction model GNN,, parameters. Recall that as with many other prediction models, a GNN model is typically trained to optimize prediction loss (i.e. (i.e.cross-ent) cross-entropy loss or mean squared error) but not geared towards efficiency for the post-hoe conformal prediction step. We design GNN, to be efficiency-aweee GNN, optimizes over; this allows integration of GNN message passing to exploit the neighborhood information and also ensures a good (=() that leads to efficient prediction sets in downstream steps.
by proposing a differentiable inefficiency loss that
We first withhold a small fraction 7 of the calibration dataset and use it for the correction procedure. The remaining data used as the "usual" calibration data for building the conformal prediction set. We then further split the withheld data into a correction calibration set Veor-cal and correction testing set test-
test. to simulate the downstream conformal inference step. Given (X) GNN, o (A)), G) and target miscoverage rate a, the framework follows three steps:
(1) Differentiable quantile: we compute smooth quantile î based on the Veur-cal by
n DiffQuantile( (V (X,, Yi E Veor-cal), } (1 ax 1/
Since the non-conformity score is usually differentiable, it only requires diffcrentiable quantile calculation where there are well-established methods available [6. 5].
(2) Differentiable inefficiency proxy: we then construct a differentiable proxy c of the inefficiency on Veor-test by simulating the downstream conformal prediction procedures. We propose general formulas to construct that are applicable for any classification and regression tasks respectively;
Inefficiency loss instantiation for Classification: The desirable proxy is to simulate the prediction set size using Door-test as the "test" data and Deor-calib as the "calibration" data. For class k and node in D Peor-test, the non-conforyity score is V(X,, k) for class k, where V(-), for instance, is the APS score in Section 2. Then, we define the inefficiency proxy
V(X,, k) 7
Ci =
where (xx) = I+e-r is the sigmoid function and T is a temperature hyper-paramerer [40]. It can be interpreted as soft assignment of class & to the prediction set. When 7 - 0. becomes a hard assignment. The per-sample inefficiency proxy is then readily constructed as c; [>)] Σxey C.
b. Inefficiency loss instantiation for Regression: The desirable proxy is to simulate the prediction inter- val length. For node i in Veor-tests the conformal prediction interval is [Aa/2(X,) - ;, P P1-a/2(Xx)
f. Thus, the per-sample prediction interval length could be directly calculated as C; (i1-a/2(X,) + ? (X,) 7)

---

Since GNN, maps intervals to intervals and do not pose constraint on the prediction, it may incur
trivial optimized solution where ji ( < Pa /x(). Thus, we pose an additional consistency regularization term: (#1-a/2(XX - /2 + (Ma/2(X)) (a))((X))² This regularizes the updated intervals to not deviate significantly to reach the trivial solution.
(3) Inefficiency loss: finally, the inefficiency loss is an average of inefficiency proxies Lineff
[Voor -caat Σ C.- The GNN, is optimized using backpropagation in an end-to-end fashion.
Conditional coverage. A natural question is whether optimizing the efficiency of conformal pre- diction may hurt its conditional validity. In Section 5, empirically demonstrate satisfactory conditional coverage across various graph features, which even improves upon the direct application of APS and CQR to graph data. We conjecture that it because we correct for the correlation among nodes. However, theoretical understanding is left for future investigation.
Graph exchangeability. The post-hoc correction model is GNN- thus, it is permutation- invariant. Thus, it satisfies the exchangeability condition laid out in our theory in Section 3. Empiri- cally, we demonstrate in Section 5 that CF-GNN achieves target empirical marginal coverage.
Computational cost. We remark that CF-GNN scales similarly as base GNN training since the correction step follows a standard GNN training procedure but with modified input attribute and loss function. Notably, as the input to the correction model usually has a smaller attribute size (the number of classes for classification and 2 for regression), it has smaller parameter size than standard GNN training. In addition, is also compatible with standard GNN hani-batching techniques.
General loss functions. Finally, we note that the choice of our loss function can be quite general. For instance, one may directly optimize for conditional validity by choosing proper loss function.
5 Experiments
We conduct experiments to demonstrate the advantages of CF-GNN over other UQ methods in achieving empirical marginal coverage for graph data, as well as the efficiency improvement with CF-GNN. We also evaluate conditional coverage of CF-GNN and conduct systematic ablation and parameter analysis to show the robustness of CF-GNN.
Evaluation setup. For node classification, we follow a standard semi-supervised learning eval- uation procedure [24], where we randomly split data into folds with 20%/10%/70% nodes as
U Drost- For the node regression task, we follow a previous evalua- tion procedure from [20] and randomly split the data into folds with 50%/10%//0%% nodes as Dirain /DD Vaalia/Dealll U Dtesst We conduct 100 random splits of calibration/testing sets to estimate the empirical coverage. Using the test-time coverage distribution in Figure 2 to ensure that coverage is concentrated tightly around 1-a, we modify the calibration set size to min { 1000, |Dealib U Dessl/22 2 and use the rest as the test sample. For fair comparison, we first train 10 runs of the base GNN model and then fix the predictions (i.e. the input to UQ baselines and CF-GNN), In this way, we ensure that the gain is not from randomness base model training. The hyperparameter search strategy and configurations for CF-GNN and baselines can be found in Appendix D.1.
Models & baselines to evaluate coverage. For classification, we first use general statistical calibra- tion approaches including temperate scaling [13], vector scaling [13], ensemble temperate scaling [49]. We also use SOTA GNN-specific calibration learners including CaGCN [44] and GATS [17]. The prediction set is the set of classes from highest to lowest scores until accumulative scores exceed 1-a.
For regression, we construct prediction intervals using quantile regression (QR) [25]. Monte Carlo dropouts (MC dropout) [9], and Bayesian loss to model both aleatoric and epistemic uncertainty [23].
More information about baselines can be found in Appendix D.2.
Models & baselines to evaluate efficiency. As smaller coverage always leads to higher efficiency, can only compare methods efficiency that achieve the same coverage.
for fair comparison, Thus, we do not evaluate UQ baselines here since they do not produce exact coverage and are thus not comparable. While any CP-based methods produce exact coverage, to the best of our knowledge,
'Conditional coverage asks for P(Yn45 E ((X,+))) X.., = x) = 1 - a for all x E X. Although exact conditional validity is statistically impossible [8]. approximate conditional validity is practically important property that APS and CQR are designed for. See Section 5 for common ways to assess conditional coverage.
7

---

Table I: Empirical marginal coverage of node classification (uperr table) and node regression tasks(lower table).
The result takes the average and standard deviation across 10 GNN runs with 100 calib/test splits. V/ means that the UQ method reaches the target coverage (i.c. coverage 0.95) while X means that it fails reach it. The last column "Covered" becomes
if UQ method reaches target coverage for all datasets and X vice versus.
Task
[UQ Model
Cora
DBLP
CiteSeer
PubMed
Computers
Photo
CS
Physics
Cowered7
Temp. Scale.
0996640009 x
0.920s.0m X 0.9524.944
m.890.me
0,929
0.962s
0.9577 ooe
0,9699.00
Vector Scale.
0.901+.004 X
0.921+000 X 0,951+0094
0.899
0.932 me x
0,963=
0,958= cca
0.969...oo
X
Node
Ensemble TS
0.9474..00 x
0.920+.00s X 0.953+.00
0.899
0.930= x
0.964
=.958
0.9694..o0
classif.
CaGCN
0.339
0
a.949
0.898 aw
0.926:
0.956
0.954:
2.
GATS
0.939
x
0.92
X 0.951
0.898
0.925
0.957
0.957
0.968
CF-GGNN
0.9522
0.9552:000
0.953
0.953 </ 0.9522 n0 v/ 00.953 no1
|..952
0.9552.00
Task
IUQ Model
Anaheim
Chicugo
Education
Election
Income
Unemploy:
Twitch
[Covered?
QR
0,943 x 0.583 102
0.950= son
0.959=
-.956=
0,960=mus
=.95 //
0,900=
Node
MC drapout
0.427 Dis
0,423
0.417
0.532 102
0.489 mo
0.448
regress.
[BaesianNN]
0.967
0.955
0.957
0.958_ rw
0.990_
0.9000
0,923
CF-GNNN
0,
0,954=
00.551=
0..950
0.951
0.951
0.954=
there are no existing graph-based conformal prediction methods for transductive settings. Thus, we can only compare with the direct application of conformal prediction (CP) to base GNN. In the main text, we only show results for GCN [24] as the base model; results of three additional popular GNN models (GraphSAGE [16], GAT [42], and SGC [45]) are deferred to Appendix D.4.
Datasets. We evaluate CF-GNN on 8 node classification datasets and 7 node regression datasets with diverse network types such as geographical network, transportation network, social network, citation network, and financial network. Dataset statistics are in Appendix D.3.
5.1 Results
CF-GNN achieves empirical marginal coverage while existing UQ methods do not. We report marginal coverage of various UQ methods with target coverage at 95% (Table 1). There are three key takcaways. Firstly, none of these UQ methods achieves the target coverage for all datasets while CF-GNN does, highlighting the lack of statistical rigor in those methods and the necessity for a guaranteed UQ method. Secondly, it validates our theory from Section 3 that CF-GNN achieves designated coverage in transductive GNN predictions. Lastly, CF-GNN achieves empirical coverage that is close to the target coverage while baseline UQ methods are not. This controllable feature of CF-GNN is practically useful for practitioners that aim for a specified coverage in settings such as planning and selection.
CF-GNN significantly reduces inefficiency. We report empirical inefficiency for 8 classification and 7 regression datasets (Table 2). We observe that we achieve consistent improvement across datasets with up to 74% reduction in the prediction set size/interval length. We additionally con- duct the same experiments for 3 other GNN models including GAT, GraphSAGE, and SGC in Appendix D.4 and we observe that performance gain is generalizable to diverse architecture choices. Furthermore, CF-GNN yields more efficient prediction sets than existing UQ methods even if we manually adjust the nominal level of them to achieve 95% empirical coverage (it however impossi- ble to do so in practice, here we do this for evaluation). For instance, the best calibration method GATS yields an average prediction size of 1.82 on Cora when the nominal level tuned to achieve 95% empirical coverage. In contrast, CF-GNN has an average size of 1.76, smaller than GATS. In Appendix D.5, we also observe that CF-GNN also reduces inefficiency for advanced conformal predictor RAPS for classification task. In addition, we find that CF-GNN yields little changes to the prediction accuracy of the original GNN model (Appendix D.7).
CF-GNN empirically maintains conditional coverage. While CF-GNN achieves marginal cover- age, it is highly desirable to have a method that achieves reasonable conditional coverage, which was the motivation of APS and CQR. We follow [37] to evaluate conditional coverage via the Worst-Slice (WS) coverage, which takes the worst coverage across slices in the feature space (i.e. node input features). We observe that CF-GNN achieves a WS coverage close to 1 a, indicating satisfactory conditional coverage (Cond. Cov. (Input Feat.) row in Table 3). Besides the raw features, for each node, we also construct several network features (which are label agnostic) including clustering
8

---

Table 2: Empirical inefficiency measured by the size/length of the prediction set/interval for node classification table). A smaller number has better efficiency. We show the relative improvement (%) of CF-GNN over CP on top of the -. The result uses APS for classification and CQR for regression with GCN as the base model. Additional results on other GNN models are at Appendix D.4, We report the average and standard deviation of prediction sizes/lengths calculated from 10 GNN runs, each with 100 calibration/test
(left (able)/regression
splits.
Task
Dataset
CP
-CF-GNN
Task
Dataset
CP
CFFGNN
Cora
3.
935.11%
1.76.
Anaheim
2.89
-25.00%
+2.1 17
DBLP
2.43 49.1%%
1.23
Chicago
2.05 00.4%% 2,04
Node classif.
PubMed
CiteSeer
3.86 -74-37%
1660
19.08%
00.99.00
1.29
regress.
Node
Education
2.56
0.90 +0.21%%,0.90:.....
26,40% 22.43
-6.07%
CS
Computers
Photo
3.79 13 -36.907
7.79 21 92.11%%
3,56 13 -49.0575
2.95
1.81
1.66
Unemploy
Income
Election
2.72 -10.83%
2.51 4.68%
22.40....
+2.43
Physios
0. -02.115
1.162.13
Twitch
2.43
1.30%, 22,99.2
Average Improvement
-53.75%
Average Improvement
-6.73%
Table 3: CF-GNN achieves conditional coverage, measured by Worse-Slice Coverage [37]. We Cora/Twitch an example glassifccation/reressson dataset. Results on other network features and results on target coverage of 0.9 can be found Appendix D.6.
Table 4: Ablation. For Size/length, we use Cora/Anaheim dataset with GCN backbone. Each experiment is with 10 independent base model runs with 100
Target: 0.95
Classification
Regression
conformal split runs.
Model
CP
CF-GNN
CP
CF-GNN
Topology -aware
Ineff: Loss
Size
Length
Marginal Cov.
0.95 i
0.95
0.96
0.96
Coad. Cov. (laput Feat.)
0.94
0.94=mm
0.95
0,94
1.762
2.17::11
Cond. Cov. (Cluster)
0.89- 1
0.93 M
0.96.2.0
0.962.
V
x
2.42a.as
2.23
Cond. Cov. (Between)
0.81=
0.95=
0.94
0,94
2.35
2.32 IK
Cond. Cov. (PageRank)
0.78 06
0.94 m
0.94
0.94
x
x
3.80
2.89:
coefficients, betweenness, PageRank, closeness, load, and harmonic centrality, and then calculate the WS coverage over the network feature space. We observe close to 95% WS coverage for various network features, suggesting CF-GNN also achieves robust conditional coverage over network properties. We also see that the direct application of CP (i.e. without graph correction) has much smaller WS coverage for classification, suggesting that adjusting for neigborhood information in CF-GNN implicitly improves conditional coverage.
Ablation. We conduct ablations in Table 4 to test main components in CF-GNN, topology-aware correction model, and inefficiency loss. We first remove the inefficiency loss and replace it with standard prediction loss. The performance drops expected, showing the power of directly modeling inefficiency loss in the correction step. Secondly, we replace the GNN correction model with an MLP correction model. The performance drops significantly. showing the importance of the design choice of correction model and justifying our motivation on inefficiency correlation over networks.
Parameter analysis. We conduct additional parameter analysis to test the robustness of CF-GNN. We first adjust the target coverage rate and calculate the inefficiency (Figure 5(1)). CF-GNN consistently beats the vanilla CP across all target coverages. Moreover, we adjust the fraction y of the holdout calibration data in building the inefficiency loss, and observe that CF-GNN achieves consistent improvement in inefficiency (Figure 5(2)). We also observe small fraction (10%) leads to excellent performance, showing that our model only requires a small amount of data for the inefficiency loss and leaves the majority of the calibration data for downstream conformal prediction.
6 Related Works
We discuss here related works that are closest to the ideas in CF-GNN and provide extended discussion on other related works in Appendix E.
(1) Uncertainty quantification (UQ) for GNN: Many UQ methods have been proposed to construct model-agnostic uncertain estimates for both classification [13, 49, 14, 27, 1] and regression [25, 41,

---

Prediction imrert Length
C assiiication
Pred Interall Longth
Regression
Classiliation
Prediction Interal Longth
Regression
Predicton Set 62ze
14
GNN
07
0.9
0.7
0.9
0,25
0.50
0,75
0,25
0.50
0,75
1-aipha: Pro specsppd Coverage
1-a pha: Pre-spaciled Coverage
Hokdout Caloration Set Fraction
Holdout Calbbaatin Sot Fraction
Figure (1) Parameter analysis inefficiency given different target coverage rate 1-a. (2) Parameter analysis
on inefficieney given calibration set holdout fraction, Analyses use Cora/ Anaheim for classficatton/eegrsssin.
38, 9, 28, 26, 35, 23, 19]. Recently, specialized calibration methods for GNNs that leverage network principles such as homophily have been developed [44, 17J. However, these UQ methods can fail to provide a statistically rigorous and empirically valid coverage guarantee (see Table 1). In contrast, CF-GNN achieves valid marginal coverage in both theory and practice.
(2) Conformal prediction for GNN: The application of CP to graph strph-structured data remains largely unexplored. [7] claims that nodes in the graph are not exchangaaale in the inductive setting and employs the framework of [3] to construct prediction sets using ncighborhood nodes as the calibration data for mitigating the miscoverage due to non-exchangeabiiltyy In contrast, we study the transductive setting where certain exchangeability property holds; thus, the method from [3] are comparable to ours. Concurrent with our work, [15] studies the exchangeability under transductive setting and proposes diffusion- method for improving efficiency, which can be viewed
instantiation of our approach where the GNN correction learns an identity mapping: [33] studies exchangeability in network regression for of non-conformity scores based on various network structures, with similar observations as our Theorem 3. Other recent efforts in conformal prediction for graphs include [32, 34] which focus on distinct problem settings.
(3) Efficiency of conformal prediction: How to achieve desirable properties beyond validity is an active topic in the CP community; we focus the efficiency aspect here. One line of work designs "good" non-conformity scores in theory such as APS [37] and CQR [36]. More recent works take another approach, by modifying the training process of the prediction model. CF-GNN falls into the latter case, although our idea applies to any non-coninn conformmt score. ConfTr [40] also modifies training for improved efficiency. Our approach differs from theirs in significant ways. First, we develop theory on CP validity on the graph data and leverage topological principles that are specialized to graph to improve efficiency while ConfTr focuses i.i.d. vision image data. Also, ConfTr happens during base model training using the training set, while CF-GNN conducts post-hoc correction using withheld calibration data without assuming access to base model training, making ConfTr not comparable to us. Finally, we also propose a novel loss for efficiency in regression tasks.
7 Conclusion
In this work, we extend conformal prediction to GNNs by laying out the theoretical conditions for finite-sample validity and proposing a flexible graph-based CP framework to improve efficiency. Potential directions for future work include generalizing the inefficiency loss to other desirable CP properties such as robustness and conditional coverage; extensions to inductive settings or transductive but non- non-random split settings; extensions to other graph tasks such as link prediction, community detection, and so on.
8 Acknowledgements
K.H. and J.L. gratefully acknowledge the support of DARPA under Nos. HR001 1211003990 (TAMI. N66001 1924033 (MCS); ARO under Nos. 191-12-11-1-0342 (MURD, 1911NF-16-1-0177 (DURIP); NSF under Nos. 18355885598 (CINES). OAC-1934578 (HDR), CCF-1918940 (Expe- ditions), NIH under No. 3U54HG010022-D45) (HuBMAP). Stanford Data Science Initiative, Wu Tsai Neurosciences Institute, Amazon, Docomo, GSK, Hitachi, Intel, JPMorgan Chase, Juniper Networks, KDDI, NEC, and Toshiba. The content is solely the responsibility of the authors and does not necessarily represent the official views of the funding entities.
10

---

References
[1] Moloud Abdar, Farhad Pourpanah, Sadiq Hussain, Dana Rezazadegan, Li Liu, Mohammad Ghavamzadeh, Paul Fieguth, Xiaochun Cao, Abbas Khosravi, U Rajendra Acharya, et al. A review of uncertainty quantification in deep learning: Techniques, applications and challenges. Information Fusion, 76:243-297 19143--97,,22 2021.
[2] Anastasios Angelopoulos, Stephen Bates, Jitendra Malik, and Michael I Jordan. Uncertainty sets for image classifiers using conformal prediction. ICLR, 2021.
[3] Rina Foygel Barber, Emmanuel Candès, Aaditya Ramdas, and Ryan J Tibshirani. Conformal prediction beyond exchangeability. arXiv:2202. 13415, 2022.
[4] Stephen Bates, Anastasios Angelopoulos. Lihua Lei, Jitendra Malik, and Michael Jordan. Distribution-free, risk-controlling prediction sets. Journal of the ACM (JACM), 68(6):1-34, 2021.
[5] Mathieu Blondel, Olivier Teboul, Quentin Berthet, and Josip Djolonga. Fast differentiable sorting and ranking. In ICML, pages 950-959. PMLR, 2020.
[6] Victor Chernozhukov, Iván Fernández- Val, and Alfred Galichon. Quantile and probability curves without crossing. Econometrica, 78(3): 1193--125, 2010.
[7] Jase Clarkson. Distribution free prediction sets for node classification. LoG, 2022.
[8] Rina Foygel Barber, Emmanuel Candès, Aaditya Ramdas, and Ryan Tibshirani. The limits of distribution--ir free conditional predictive inference. Information and Inference: A Journal of the IMA, 10(2):55-442, 2021.
[9] Yarin Gal and Zoubin Ghahramani. Dropout a bayesian approximation: Representing model uncertainty in deep learning. In ICML, pages 1050-1059, PMLR, 2016.
[10] Jayy Gao, Jiaxing Li, Ke Zhang, and Youyong Kong. Topology uncertainty modeling for imbalanced node classification on graphs. In ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1-5. IEEE, 2023.
[11] Isaac Gibbs and Emmanuel Candès. Adaptive conformal inference under distribution shift. NeurlPS, 34, 2021.
[12] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML, pages 1263-1272. JMLR. org. 2017.
[13] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In ICML, pages 1321-1330. PMLR, 2017.
[14] Kartik Gupta, Amir Rahimi, Thalaiyasingam Ajanthan, Thomas Mensink, Cristian Sminchis- escu, and Richard Hartley. Calibration of neural networks using splines. ICLR, 2021.
[15] Soroush H. Zargarbashi, Simone Antonelli, and Aleksandar Bojchevski. Conformal prediction sets for graph neural networks. In ICML, 2023.
[16] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. NeurIPS, 30, 2017.
[17] Hans Hao-Hsun Hsu, Yuesong Shen, Christian Tomani, and Daniel Cremers. What makes graph neural networks miscalibrated? NeurIPS, 2022.
[18) Vladislav Ishimtsev, Alexander Bernstein, Evgeny Burnaev, and Ivan Nazarov. Conformal k-nn anomaly detector for univariate data streams. In Conformal and Probabilistic Prediction and Applications, pages 213-227. PMLR, 2017.
[19] Pavel Izmailov, Sharad Vikram, Matthew D Hoffman, and Andrew Gordon Gordon Wilson. What are bayesian neural network posteriors really like? In ICML., pages 4629-4640. PMLR, 2021.
[20] Junteng Jia and Austion R Benson. Residual correlation in graph neural network regression. In KDD,, pages 588-598, 2020.
[21] Ying Jin and Emmanuel J Candès. Selection by prediction with conformal p-values. 10X.v:2210001408, 2022.
[22] Ying Jin, Zhimei Ren, and Emmanuel J Candès. Sensitivity analysis of individual treatment effects: robust conformal inference approach. Proceedings of the National Academy of Sciences, 120(6):e22143)) 14889120 2023.
11

---

[23] Alex Kendall and Yarin Gal. What uncertainties do we need in bayesian deep learning for computer vision? NeurIPS, 30, 2017.
[24] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ICLR, 2017.
[25] Roger Koenker and Kevin F Hallock. Quantile regression. Journal of Economic Perspectives, 1544)1143-156, 2001.
[26] Volodymyr Kuleshov, Nathan Fenner, and Stefano Ermon. Accurate uncertainties for deep learning using calibrated regression. In ICML, pages 2796-2804. PMLR, 2018.
[27] Meelis Kull, Miquel Perello Nieto, Markus Kängsepp, Telmo Silva Filho, Hao Song, and Peter Flach. Beyond temperature scaling: Obtaining well-calibrated multi-class probabilities with dirichlet calibration. NeurIPS, 32, 2019.
[28] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. NeurlPS, 30, 2017.
[29] Remi Lam, Alvaro
Matthew Willson, Peter Wirnsberger, Meire Fortunato, Alexander Pritzel, Suman Ravuri, Timo Ewalds, Ferran Alet, Zach Eaton-Rosen, al. Graphcast: Learning skillful medium-rang global weather forecasting. arXiv:2212. 127944 2022.
[30] Lihua Lei and Emmanuel J Candès. Conformal inference of counterfactuals and individual treatment effects. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2021.
[31] Michelle M Li, Kexin Huang, and Marinka Zitnik. Graph representation learning in biomedicine and healthcare. Nature Biomedical Engineering, pages 1-17, 2022.
[32] Robert Lunde. On the validity of conformal prediction for network data under non-uniform sampling. arXiv preprint WwXiv:2300.00252: 2023.
[33] Robert Lunde, Elizaveta Levina, and Ji Zhu. Conformal prediction for network-assisted regression. arXiv:2302.10092 2023.
[34] Ariane Marandon. Conformal link prediction to control the error rate. arXiv preprint arXiv:2306. 14693, 2023.
[35] Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan. and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. NeurlPS, 32, 2019.
[36] Yaniv Romano, Evan Patterson, and Emmanuel Candès. Conformalized quantile regression. NeurlPS, 32, 2019.
[37] Yaniv Romano, Matteo Sesia, and Emmanuel Candès. Classification with valid and adaptive coverage. NeurIPS, 33:3581-3591, 2020.
[38] Simon J Sheather and James Stephen Marron. Kernel quantile estimators. Journal of the American Statistical Association, 85(410):410-416 1990.
[39] Maximilian Stadler, Bertrand Charpentier, Simon Geisler, Daniel Zügner, and Stephan Gün- nemann. Graph posterior network: Bayesian predictive uncertainty for node classification. Advances in Neural Information Processing Systems, 34: 18033-18884, 2021.
[40] David Stutz, Ali Taylan Cemgil, Arnaud Doucet, et al. Learning optimal conformal classifiers. ICLR, 2022.
[41] Ichiro Takeuchi, Quoc Le, Timothy Sears, Alexander Smola, et al. Nonparametric quantile estimation. 2006.
[42] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. ICLR, 2018
[43] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world. Springer Science & Business Media, 2005.
[44] Xiao Wang, Hongrui Liu, Chuan Shi, and Cheng Yang. Be confident! towards trustworthy graph neural networks via confidence calibration. NeurIPS, 34:23768-23777 2021.
[45] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In ICML, pages 6861-6871. PMLR, 2019.
12

---

[46] Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recom- mender systems: survey. ACM Computing Surveys, 55(5):1-37, 2022.
[47] Mingzhang Yin. Claudia Shi, Yixin Wang, and David M Blei. Conformal sensitivity analysis for individual treatment effects. Journal of the American Stafistical Association, pages 1-14, 2022.
[48] Margaux Zaffran, Olivier Féron, Yannig Goude, Julie Josse, and Aymeric Dieuleveut. Adaptive conformal predictions for time series. In ICML, pages 25834-25866, PMLR, 2022.
[49] Jize Zhang, Bhavya Kailkhura, and T Yong- Jin Han. Mix-n-match: Ensemble and compositional methods for uncertainty calibration in deep learning. In ICML., pages 111 11117-11122 PMIR, 2020.
[50] Xujiang Zhao, Feng Chen, Shu Hu, and Jin-Hee Cho. Uncertainty aware semi-supervised learning graph data, Advances in Neural Information Processing Systems, 33:12827-12836, 2020.
13

---

A Deferred details for Section 3
A.1 Technical proofs for theoretical results
Proof of Lemma 2. Hereafter, we condition on the entire unordered graph, all the attribute and label information, and the index sets Parin and Des. We define the scores evaluated at the original node indices as
Up V(xo, yoi PEmn {xo De V,E); v E Dealih Drest V.
By Assumption for any permutation of Pa. always have
Up V (X,, Vui UE {x JeED VA Vx,ER) Ex).
That is, given Dat the evaluated score at any v E Da remains invariant no matter which subset of Dar is designated as Dealih. This implies that the scores are fixed after conditioning:
[V....,, Va+ml [Ve]eEDa:
where we use to emphasize unordered sets. Thus, the calibration scores {vi]== is subset of size n of (wlleED. Note that under random splitting in the transductive setting, any permutation æ of Da occurs with the same probability, which gives the conditional probability in Lemma 2.
Proof of Theorem 3. Throughout this proof, we condition on the entire unordered graph, all the attribute and label information, and the index sets Danin and Da By Lemma 2, after the conditioning. the unordered set of (Vi is fixed as [eolvED., and {Vi),= is simple random sample from [uplveR.. As a result, any test sample V(Xn+j. Yn+j), l..... ...... m is exchangeable with (Vi)==- By standard theory for conformal prediction [43], this ensures valid marginal coverage, i.e., PP(Yn+j C(X,+;))
a, where the expectation is over all the randomness.
We now proceed to analyze the distribution of Cover. For notational convenience, we write = m n, and view Det as the "population'. In this way, {Vi) is simple random sample from [vo]oED.. For every E E, we define the 'population' cumulative distribution function (c.d.f.)
F(n)
Σ (w,ss) DEDs
N
which is deterministic function. We also define the calibration e.d.f. as
(.(())
1 Σ 1( S -
1 <n),
Deaa
which is random, and its randomness comes from which subset of De is Dealib By definition,
= inf F.(1)) 2 (1 4) + 1/n)).
Since the scores have ties, we know
P. = [(1 -11-[11000 (n 1)1/n.
The test-time coverage can be written as
1
m
Cover
1 (V S
m
1
11 (w0 S
Σ
1/ 7
N
BEDa
VE Dain
N
N
[11 9) (n 1)]
F())
n
n
n
Now we characterize the distribution of n.. For any 17 E R, by the definition of i
P( $ n) = P(n (m) 1 0)) = P (m [(n + 1)(1 - g)1)
14

---

Note that (n) = EVE 1( S 7) is the count of data in Deami such that the score is below By the simple random sample (i.e., sampling replaceemmm (n) follows a distribution with parameter N, n, (F)).. That is,
(()Fa.()) k) (7) (N-NF())
n-k
0 ASkSNF(N)
Denoting the c.d.f. of hypergeometric distribution PHG (k; N, n, NF))), have
P( 5 n) = PHe (I(n + +)((1 - q)1 - 1; N, n, F())).
Then, for any & E [0, 1].
N N
[[1 - (m= 1)] N -
P(Cover I =
F(T)
tt
() + 1)] + (N - m]
-m]4
= F(ñ)= I
N
Since F()) is monotonely increasing,
P(Cover St) = F ((1-
+ 1)] + (N m)t
N
where (s) = inf(:: F(r) 2 83 for any 8 E [0, 1]. Plugging the previous results on the
distribution of 17, we have
P(Cover S t) = DH
[(n 1)(1) 9) - 1: NF F
[(1 ()+ (0togg/+++++((0000 +N
N
[(n 1)(1 4)1 - 1; N (((---)((+)))(N--)))))
1 DHG
1 PHG
[(n +) -)- - 1:N,n [[(1 (n + 1)] + (N nntt]
= 1 4H
[(n + 1)(1 4)1 - 1:N, [[1 (1 1)] + [[N n2)t]
where the second equality uses the fact that F(n) 10.1/N, ...,, (N 1), hence Fs)= = [Ns] /N for any 8 E [0. By tower property, such an equation also holds for the unconditional distribution, marginalized over all the randomness. This completes the proof of Theorem 3.
A.2 Additional visualization test-time coverage
In this part, we provide more visualization of the distributions of test time coverage Cover under various sample size configurations. We note that such results also apply to standard application of split conformal prediction when the non-conformity score function V is independent of calibration and test samples, so that Assumption is satisfied.
Figures 6 and plot the p.d.f. of Cover for a = 0.05 and a 0.1, respectively, when fixing n
and varying the test sample size m. The y-axis is obtained by computing P(t < Cover < ttt/(t tx-1)
(fx-1 + tx)/2 for sequence of evenly spaced {tx} 1]. All figures in this paper for f.d.f.s are obtained in the same way. We see that Cover concentrates more tightly around the target value a as m and increases.
Figures 8 and 9 plot the p.d.f. Cover for a 0.05 and a = 0.1, respectively, where we fix N m but vary the calibration sample size n. This mimics the situation where the total number of nodes on the graph is fixed, while we may have flexibility in collecting data as the calibration set. We observe tradeoff between the calibration accuracy determined by n and the test sample concentration determined by n. The distribution of Cover more concentrated around m and are relatively balanced.
when
15

---

50
m
m
m
30-
50
40
100
100
pdf.
20
100
pdf.
30
250
pdf.
40
250
250
500
10
500
750
20
10
1000
20
750
1000
1000
2000
2000
0
0.85
0.90
0.95
1.00
0.85
0.90
0.95 coverage
1,00
0.85
0.90
0.95
1.00
coverage
coverage
Figure P.d.f. test-time coverage Cover for 500 (left), 1000 (middle), 2000 (right) and a 0.05 with curves representing different values of m. the test sample size.
m
40
m
30
50
100
100
100
250
30
250
pd..
250
pd..f
20
pdf.
500
20
500
750
5
750
10
1000
10
1000
1000
2000
2000
0-
0-
0-
0.75
0.80
0.85
0.90
0.95
1.00
0.75
0,50
0.85
0.90 coverage
0.95
1,00
0.75
0.50
0.85
0.90
0.95
1.00
coverage
coverage
Figure P.d.f. test-time coverage Cover for n 500 (left), 1000 (middle), 2000 (right) and a = 0.1 with curves representing different values of m, the test sample size.
30
40
15-
20
100
30
pdf..
200
pdf.f
250
pdf.
1000
300
500
20
1250
10-
750
1500
5
10
150
900
1750
0-
0-
0-
0.85
0.90
0.95
1.00
0.85
0.90
0.95
1.00
0.85
0.90
0.95
1.00
coverage
coverage
coverage
Figure P.d.f. of test-time coverage Cover for = m n 500 (left), 1000 (middle), 2000 (right) and a 0.05 with curves representing different values of nı, the calibration sample size.
15-
30
10-
15
100
20
pdf.f
200
pdf.f.
250
pdf.
1000
300
10
500
1250
5
400
750
10
1500
900
1750
0-
0-
0-
0.75
0.80
0.85
0.90
0.95
1.00
0.75
0.50
0.85
0.90
0.95
1.00
0.75
0.50
0.85
0.90
0.95
1.00
coverage
coverage
coverage
Figure P.d.f. test-time coverage Cover m n 500 (left), (middle), 2000 (right) and
0.1 with curves representing different values of n, the calibration sample size.
16

---

B Discussion on full conformal prediction, split conformal prediction
In this part, we discuss the relation of our application of conformal prediction to full conformal prediction and split conformal prediction, two prominent conformal prediction methods proposed by Vovk and his coauthors in [43]. Split conformal prediction mostly widely used due to its computational efficiency, where exchangeabilityy is usually ensured by independence (which is not obvious for graph data) as we discussed briefty in the introduction.
Full conformal prediction (FCP) is arguably the most versatile form of conformal prediction. Given calibration data Z; (X,, Yi) E X x
I....,,e n, and given a test point Xa+1 E X whose outcome n ) is unknown, at every hypothesized value V, FCP uses any algorithm S to train the following scores
S SX,, Y;; Zi-1; -1, Zny (X++1,8)), i= 1=
where S is symmetric in the arguments Zl.... Zi-1, Zitl, Zno (Xn+1, y), well S S(X Zi...., Zn).
Here, for 1 < S n, Sy. intuitively measures how well the observation (X;, Y2) conforms to the observations Zi...., Zi-1, Z......... Zn (Xa+1. y) with the hypothesized value of y. For instance, when using linear prediction model, it can be chosen the prediction residual
S = |Y; X 0%,
where ØV the ordinary least squares coefficient by linear regression of Yi...., Y1-1. Y411.... Y, over X1..... 1; Xi+1,..+....... Xn,, Xnt1. More generally, one using Zi..... Zi-1, Zi+1..... Zn (Xn+1, 9), and set
may train a prediction model p X Sy 1 Tr (x,)). For confidence level a E (0, 1), the FCP prediction set is then
Ō(x++1):= := { (ST S sa).
n+1
Since the original form of FCP involves training n + 1 models at each hypothesized value y. its computation can be very intense. thus impractical directly apply FCP GNN models (i.e.. imagining S as the GNN training process on the entire graph with hypothesized outcome y).
Split conformal prediction (SCP) is computationallly-ffiiiii widely used for i..d. data. The idea is to set aside an independent fold of data to output a single trained model. To be specific, we assume access given non-conformity score V: X
special of FCP that is most
+ R. ii.d. calibration data Z; = (X,, Y and an independent test sample (Xn+1, Y Y2+1) from the same distribution with Ya+1 unobserved. Here by "given" score, we mean that is obtained without knowing the calibration and test sample; usually, it is trained on an independent set of data {(X,, Y,) before seeing the calibration and test sample. Then define V; V(X,, Y,) for i = =1..... n. The SCP prediction set is
Ō(X =
= {y: V+ < 3
The above set is usually convenient to compute, because we only need one single model to obtain V. The validity of SCP usually relies on the independence of V to calibration and test data as we mentioned in the introduction. However, the application of SCP to GNN model is also not straightforward: as we discussed in the main text, the model training step already uses the calibration and test samples, and the nodes are correlated.
Indeed, our method can be seen single prediction model as SCP does, but allows to use calibration and test data in the training step as FCP does. In our method introduced in the main text, there exists a fixed function V: y R (provided by APS and CQR) such that
middle ground between FCP and SCP: only requires one
S V(ū(X)) Y.), S = ((((X,,+11)
where T is the final output from the second GNN model whose training process does not utilize the outcomes Yi...., Yn and y, but uses the features X1...., and X
17

---

Algorithm 1: Pscudo-code for CF-GNN algorithm.
Input: Graph G (V, & X); a trained base GNN model GNN;; non-conformity score function V(X, Y); pre-specified mis-coverage rate a, Randomly initialized i) for the conformal correction model GNN,.
while not done do
for in (1, ... Voor- calib U Vcor-test do ((X.) GNN (XN, G)
// Base GNN output scores // Correction model output scores
(X:)) = GNN, (T(()), G)
end
T2, m = ccallbl /, Deor
11 Size of correction calib/test set // Finito-sample correction
ā =+ * a
7 DiffQuantile( (V, Yi)li V Veor-calih)) // Compute non-conformity scores
Classification then
Linoff #/2 Eievon toot [y] (
// Inefficiency proxy for classi fication tasks
end
if Regression then
Lineff 1 Eiev soot ( (f1-a/2(1))) (X); 7)) (X)) -
/1 Inefficiency proxy for regression tasks
Linett + x m EieVenr-tnt ( ( (Mo/2(X), (x)2(X);)² Consistency regularization term
end
4-4 V Lineff
// Optimizing to reduce inefficiency
end
C Algorithm overview
We describe the pseudo-code of CF-GNN in Algorithm 1.
D Deferred details for experiments
D.1 Hyperparameters
Table 5 reports our of hyperparameter ranges. We conduct 100 iterations Bayesian Optimization for CF-GNN with the validation set inefficiency proxy as the optimization metric. To avoid overfitting. each iteration only uses the first GNN run. The optimized hyperparameters are then used for all 10 GNN runs and we then reported the average and standard deviation across runs. Each experiment is done with a single NVIDIA 2080 RTX 1IGB GPU.
Table 5: Hyperparameter range CF-GNN.
Task
Param.
Range
GNNa Hidden dimension
[16.32.64.128.256|
Learning rate
[le-1, le-2, le-3, le-4]
Classification
GNN Number of GNN Layers
[1,2,3,4]
GNN Base Model
[GCN, GAT, GraphSAGE, SGCJ
[10, 1, le-1, 1e-2, le-3]
GNN Hidden dimension
[16,32,64, (2,,,,6,,,,266
Learning rate
[le-1, 1e-2, 1e-3, le-4]
Regression
GNN,, Number of GNN Layers
[1, 2, 4]
GNN Base Model
[GCN, GAT, GraphSAGE, SGC]
Reg. loss coeff. 7
[1, le-1]
18

---

D.2 Baseline Details
We report the details about baselines below and the hyperparameter range in Table
1. Temperature Scaling [13] divides the logits with learnable scalar. It is optimized over NLL loss in the validation set.
2. Vector Scaling [13] has scalar to scale the logits for each class dimension and adds an additional classwide bias. is optimized over NLL loss in the validation set.
3. Ensemble Temperature Scaling [49] learns an ensemble of uncalibrated, temperature-scat calibrated calibrators.
4. CaGCN [44] uses an additional GCN model that learns temperature scalar for each node based on its neighborhood information.
5. GATS [17] identifies five factors that affect GNN calibration and designs model that ac- counts for these five factors by using per-node temperature scaling and attentive aggregation from the local neighborhood.
6. QR [25] uses a pinball loss to produce quantile scores. is CQR without the conformal prediction adjustment.
7. MC dropout [9] turns on dropout during evaluation and produces K predictions. We then take the 95% quantile of the predicted distribution. We also experimented with taking 95% confidence interval but 95% quantile has better coverage, thus we adopt the quantile approach.
8. BayesianNN [23] model the label with normal distribution and the model produces two heads, where one corresponds to the mean and the second log variance. We then calculate the standard deviation the square root of the exponent of log variance. Then we take the [mean- 1aaun-1.6**stee standadd deviation, mean+1. 1eeet+..6**ttat stnndddd deviation] for the 95% interval.
Table 6: Hyperparameter range for baselines.
Baseline
Param.
Range
Temperature Scaling
No hyperparameter
Not Applicable
Vector Scaling
No hyperparameter
Not Applicable
Ensemble Temp Scaling
No hyperparameter
Not Applicable
Dropout
[0.3, 0.5, 0.7] [16, 32, 64, 128, 256] [1,2,3,4]
Hidden dimension
CaGCN
Number of GNN Layers
Weight Decay
[0. 1e-3, le-2, le-1]
Dropout
[0.3, 0.5, 0.7]
Hidden dimension
[16, 32, 64, 128, 256] [1,2,3,4]
GATS
Number of GNN Layers
Weight Decay
[0. 1e-3, 1e-2, 1e-1]
MC Dropout
Number of Predictions
[100, 1,000]
BayesianNN
No hyperparameter
Not Applicable
D.3 Dataset
For node classification, we use the common node classification datasets Pytorch Geometric package. For node regression, we use datasets in [20]. We report the dataset statistics at Table 7.
D.4 Marginal coverage and inefficiency across GNN architectures
We additionally conduct marginal coverage and inefficiency comparisons of CF-GNN over the vanilla CP across different GNN architectures: GCN, GAT, GraphSAGE, and SGC. The result for marginal
19

---

Table Dataset statistics.
Domain
Dataset
Task
# Nodes
Edges
# Features
Labels
Cora
Classification
2,995
16,346
2,879
DBLP
Classification
17.716
105,734
1,639
Citation
CiteSeer
Classification
4,230
10,674
602
6
PubMed
Classification
19,717
88,648
500
Computers
Classification
13.752
491,722
767
Co-purchase
Photos
Classification
7,650
238,162
745
8
CS
Classification
18,333
163,788
6,805
15
Co-author
Physics
Classification
34,493
495,924
8,415
Anahcim
Regression
914
3,881
4
Transportation
Chicago
Regression
2,176
15,104
Education
Regression
3,234
12,717
Election
Regression
3,234
12,717
6
Geography
Income
Regression
3,234
12,717
6
Unemployment
Regression
3,234
12,717
Social
Twitch
Regression
1,912
31,299
3,170
Empirical Coverage
1.0
CF-GNN Base
GCN
0.5
GraphSAGE
GAT
SGC
0.0
Cora
DBLP
CiteSeer
PubMed
Computers
Photo
CS
Physics
Anaheim
Chicago
Education Election
Income
Unemploy Twitch
Figure 10: Empirical coverage across 15 datasets with 10 independent runs of GNN, using CF-GNN.
coverage is in Figure 10. The result for inefficiency is in Table 8. We observe consistent improvement in inefficiency reduction across these architectures, suggesting CF-GNN is a GNN-agnostic efficiency improvement approach.
D.5 CF-GNN with Regularized Adaptive Prediction Sets
To further showcase that CF-GNN is a versatile framework that adapts to any advancement in non-conformity scores, experiment RAPS [2], which regularizes APS to produce smaller prediction set size. We report the performance using the GCN backbond Table 9. We observe that CF-GNN still obtains impressive inefficiency reduction compared the vanilla application of RAPS to GNN.
D.6 Conditional coverage on full set of network features
We report the full set of network features and calculate the worse-slice coverage in Table 10 for target coverage of 0.9 and Table 11 for a target coverage of 0.95. We observe that CF-GNN achieves satisfactory conditional coverage across wide range of diverse network features.
D.7 Prediction accuracy versus uncertainty calibration
As we discussed in the main text, the original GNN trained towards optimal prediction accuracy does not necessarily yield the most efficient prediction model; this is corrected by the second GNN in CF-GNN which improves the efficiency of conformal prediction sets/intervals. With our approach, one can use the output of the original GNN for point prediction while that of the second GNN for efficient uncertainty quantification, without necessarily overwriting the first accurate prediction model. However, natural question here still remains, which is that whether applying the second
20

---

Table 8: Empirical inefficiency measured by the size/tength of the prediction set/interval for node classifica- tion/regression. The result uses APS for classification and CQR for regression. We report average and standard deviation calculated from 10 GNN runs with each run of 100 conformal splits.
GNN Model
GCN
GraphSAGE
GAT
SGC
Task
Dutaset
CP
CCF-NNN
CP
.CF-GNN
CP
:CF-GNN
CP
:CT-GNN
Cora
3.80+
68.44%,
L5
6.73
76.50%
1.58
4.14
62,6312
1.55
3.88
1.47=
DBLP
mm
1m
3.91
-08.7%%
g.24g.0
2,02 cm
1.26.1.0
2.44
1.24
Node
CiteSoor
74.208 3.86+
00.99
5.88
88,07%
1.00=.01
3.18=a5-
68.06%
1.00=.01
3,79
73,4
1.01
classif.
PuhMed
1.601 -19.4
1.29
1.93
1.22
1.37
-00.54%5
1.23...0
1.60
1.21
Computers
3,56+ 60.22/8
1. 1.77
6.00e.10
16.748
33226..45
2.33
1616
12
3,44
45.9998
1.87
Photo
3.79 088,
1.63
4.52
2.84
2.24
10,38
1.81.im
3.81
1.
7.79 -5..55
33
14.68
-58 801%
1.67+.14
6.87
1.85+
7.76
2.02+
Physics
3.11
-5. 2035
11.08...
4.91
77.9978
11333.ox
2,00
45.23%%,
1.09
3.10
007. 1,32.
Average Improvement
-53.75%
-63.75%
-40.63%
-56.07%
Anaheim
2.89
25.0005
2.171
2.37 28.12%
1.82=.07
3.12
51,277
2. 241
2.94
24.90%
2.21
Chicago
2.05
17
1.02
1.95
,0.62..v
2.02
-1.am%
1.99..m
Node regress
Education
2.56+.00
2.56+.00-
5.00%
2.43
2.20
18.44%
2.38
2.48
2.70%
2.41+
2.55
2:8008
2.48
Election
0.90 +..21%%
.0.90
0.87
-1..005
.0.661.0 e.
0.89
-1.25%
0.90
1291
.0.90..
Income
2.51 -4.58%
2,40=.0
2.08+.04
189.2885 2.
2.35
0.388
2.34+
2.42=.0) 13.0048
2.49:
Unemplay.
2. -10
12.43
2.75
-12.90%
22.39
2,80
-4.50%
22.40
2,72.1.0
-11.05%, 22,42..m
Twitch
2.43 -1..0.1............... 22.39
2.48
-9.008 2,4.0m 22.40
2.50s.14
22.6
2.42
21.48 2.388
Average Improvement
-6.73%
-1.02%
-17.68%
-5.56%
Table Comparison with other non conformity scores that reduce inefficiency.
Size
CP - CF-GNN
Cora
1.67 1.67 15.35%
1 1,42
DBLP
1.39 5500%%
1.32+
1.30 -9.8551199933 19.85%
CiteSeer
1. 1.04
1.23 -240%
PubMed
1.26:t.02
Computers
1.58 4.58%
1.51
Photo
1.34 47.4%% 47%
1.20
CS
1.29+.04 6613%
1.21
GNN drastically changes the prediction accuracy. This question more relevant to the classification problem since for regression our method only adjusts the confidence band. For classification, we consider top-1 class prediction as the "point prediction". We present its accuracy "Before" and " "After" the correction in Table 12, which shows that this correction typically does not result in visible change accuracy. In addition, in a new experiment on Cora, we find that 100% of the top- class from the base GNN are in CF-GNN's prediction sets. The potential to develop steps that explicitly consider point prediction accuracy an exciting avenue for future research.
E Extended Related Works
Uncertainty quantification for graph neural networks. Uncertainty quantification (UQ) is a well- studied subject in general machine learning and also recently in GNNs. For multi-class classification, the raw prediction scores are often under//ove--oofident and thus various calibration methods are proposed for valid uncertainty estimation such as temperate scaling [13], vector scaling [13], ensemble temperate scaling [49], and so on [14, 27, 39, 1]. Recently, specialized calibration methods that leverage network principles such as homophily have been developed: examples include CaGCN [44] and GATS [17]. In regression, various methods have been proposed to construct prediction intervals, such as quantile regression [25, 41, 38), bootstrapping with subsampling, model ensembles, and dropout initialization [9, 28, 26, 35), and bayesian approaches with strong modeling assumptions on
parameter and data distributions [23, 19]. However, these UQ methods can fail to provide statistically
21

---

Table 10: CF-GNN achieves conditional coverage. We use Cora/Twitch an example classfiication/regrssioon
dataset.
Target: 0.9
Classification
Regression
Model
CP
CF-GNN
CP
CF-GNN
Marginal Cov.
0,90+.02
0,90=
0.91
0.91
Cond. Cov. (Input Feat.)
0.89
0.901.03
0.90.1.7
0.86..08
Cond. Cov. (Cluster)
0.82
0.89
0,90+ 06
0.88=.07
Cond. Cov. (Between)
0.82+ 06
0.89 03
0.86+ 08
0.88=
Cond. Cov. (PageRank)
0.71#.08
0.87
0.87
0.89
Cond. Cov. (Load)
0,83:.05
0,90
0.86:t.08
0.88
Cond. Cov. (Harmonic)
0.89:t.44
0,87
0.88
0.91
Cond. Cov. (Degree)
0.79
0.89
0.86
0.89 000
Table 11: CF-GNN achieves conditional coverage. We use Cora/Twitch an example classffication/regrssion dataset.
Target: 0.95
Classification
Regression
Model
CP
CF-GNN
CP
CF-GNN
Marginal Cov.
0.95..01
0.95
0.96
0.96=
Cond. Cov. (Input Feat.)
0.94
0.94
0.95+.04
0.94=
Cond. Cov. (Cluster)
0.89
0.93
0.964.03
0.96
Cond. Cov. (Between)
0.81+
0,95
0.94
0,94=00
Cond, Cov, (PageRank)
0.78+.066
0.94
0.94
0.94
Cond. Cov. (Load)
0..1
0,94
0.94
0,95=005
Cond, Cov. (Harmonic)
0.88
0.95 1.03
0.96.1.04
0.95 .04
Cond. Cov. (Degree)
0.83
0.88 1.06
0.94.1.04
0.94.:04 .04
rigorous and empirically valid coverage guarantee (see Table 1). In contrast, CF-GNN achieves valid marginal coverage in both theory and practice. Uncertainty quantification has also been leveraged to deal with out-of -iftr--diitribttion detection and imbalanced data in graph neural networks [50, 10]. While not the focus here, we remark that conformal prediction can also be extended to tackle such issues [18), and it would be interesting to explore such applications for graph data.
Conformal prediction for graph neural networks. As we discussed, the application of conformal prediction to graph-structree data remains largely unexplored. At the time of submission, the only work we awared of is [7], who claims that nodes the graph are not exchangeable in the inductive setting and employs the framework of [3] to construct conformal prediction sets using neighborhood nodes as the calibration data. In contrast, we study the transductive setting where certain exchangeablility property holds and allows for flexibility in the training step. We also study the efficiency aspect that is absent in [7]. In addition, there have been concurrent works [15, 33] that observe similar exchangeability and validity of conformal prediction in either transductive setting or other network models. In particular, [15) proposes a diffusion conformity scores of neighbor nodes to improve efficiency. while our approach learns the aggregation of neighbor scores, which is more general than their approach. [32] studies the exchangeability for node regression under certain network models instead of our transductive setting with GNNs, and without considering the efficiency aspect. With a growing recent interest in conformal prediction for graphs, there are even more recent works that focus on validity [32] and link prediction [34].
method that aggregates non-
Efficiency of conformal prediction. While conformal prediction enjoys distribution- coverage for any non-conforyity score based on any prediction model, its efficiency (i.e., size of prediction sets or length of prediction intervals) varies with specific choice of the scores and models. How to achieve desirable properties such as efficiency is a topic under intense research in conformal prediction. To this end, one major thread designs good non-confornity scores such as APS [37] and CQR [36]. More recent works take another approach, by modifying the training process of the prediction model to
22

---

Table 12: CF-GNN does not change the top-1 class prediction accuracy for classification tasks.
Dataset
Before
After
Cora
10.004
0.843.0000
DBLP
0.83510000
0.832
CiteSeer
0.913
0..02
further improve efficiency. This work falls into the latter case. Our idea applies to any non-conformity scores, demonstrated with APS and CQR, two prominent examples of the former case. Related to our work, ConfTr [40] also simulates conformal prediction so as to train a prediction model that eventually leads to more efficient conformal prediction sets. However, from theirs in significant ways. First, ConfTr modifies model training, while CF-GNN conducts post-hoc correction without changing the original prediction. Second, ConfTr uses the training set to simultaneously optimize model prediction and efficiency conformal prediction, while we withhold fraction of calibration data to optimize the efficiency. Third, approach specifically leverages the rich topological information in graph-structured data to achieve more improvement efficiency. Finally, also propose novel loss for efficiency in regression tasks.
approach differs
23


Reviews:
[{"review_id": "PKOdhy8AZH", "reviewer": "Reviewer_Wep3", "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. \n\nThe 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.\n\nTo 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.\n\nExperiments show better uncertainty estimates compared to well-known approaches such as MC dropout, although the baselines are not designed specifically for GNNs.", "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?\n\n- 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.", "limitations": "I do not see potential negative societal impact of the work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper formally justifies that conformal prediction can be used under the exchangeability assumption.\n\n- 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.\n\n- 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.\n\n- 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?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback, and for recognizing that our approach is simple yet effective. We appreciate the thoughtful questions posed and address them in detail below:\n\n> [1] Train a separate model for every $\\alpha$? \n\nThe reviewer recognizes a vital part of our approach, where CF-GNN does require a separate model for each $\\alpha$ because of the predefined nature of $\\alpha$ in conformal prediction. We acknowledge that an extension to accommodate multiple $\\alpha$s simultaneously could augment our method's flexibility; this is an area for future research.\n\nIn our calibration GNN, the chosen $\\alpha$ plays a role in the loss function. A solution to include multiple $\\alpha$s might be to aggregate the losses for these $\\alpha$s. This will make the calibration GNN universal for multiple $\\alpha$ values, but possibly suboptimal when compared to a model trained for a specific $\\alpha$ value.\n\nIt's crucial to note that in most real-world scenarios, the miscoverage level $\\alpha$ is often fixed (e.g., 5%), so training multiple models isn't typically a major concern, as only one or a limited number of $\\alpha$ values are usually explored. This makes our CF-GNN approach practical. This aspect will be thoroughly discussed in our revised manuscript.\n\n> [2] Tradeoff between uncertainty quantification and predictive performance?\n\nThank you for posing this insightful question. From our understanding, uncertainty quantification refers to the prediction set and its size, whereas predictive performance relates to the precision of the point estimate. We will explain based on this understanding, but please feel free to correct us if you meant something else. \n\nFor regression tasks using quantile regression, CF-GNN focuses on adjusting the $(\\alpha/2, 1-\\alpha/2)$ quantile band. Since the quantile bands are typically not used for point prediction, this adjustment does not influence the predictive performance of the model. \n\nIn classification tasks, the correction step within CF-GNN could indeed modify the top-1 class prediction (we view this as the “point prediction”). However, this correction typically does not result in a visible change in accuracy. We show this with newly conducted experiments below:\n\n|Data|Before|After|\n|-|-|-|\n|Cora|0.844 ± 0.004|0.843 ± 0.016|\n|DBLP |0.835 ± 0.001|0.832 ± 0.002|\n|CiteSeer|0.913 ± 0.002|0.911 ± 0.002|\n\nThe efficiency of prediction sets and the accuracy of point predictions are typically distinct goals requiring different optimal models. Our method employs a second calibration GNN to separate these goals, allowing the base GNN for point prediction and CF-GNN for uncertainty quantification. In a new experiment on Cora, we find that 100% of the top-1 class from the base GNN are in CF-GNN’s prediction sets. The potential to develop steps that explicitly consider point prediction accuracy is an exciting avenue for future research, and this will be discussed in the revised manuscript.\n\n> [3] Overfitting when the correction dataset is small? Possible to make all Vs trivially 0?\n\nThank you for raising this pertinent question!\n\n**On the Issue of Trivially 0 Vs**: In classification tasks, the APS employs a cumulative sum of class probabilities over the softmax score up to the ground truth class; as the summation is one, it ensures that Vs will not be close to zero. In regression, a consistency loss is applied such that quantile bands are close to the original prediction thereby ensuring that Vs will not diminish to zero. Thus, our design safeguards against Vs becoming trivially 0. \n\n**On the Risk of Overfitting**: Indeed, when the size of the correction set is exceedingly small, the $\\hat{\\eta}$ estimate may be less accurate or too variable, which potentially leads to a bias in the adjustment of prediction scores. However, our empirical studies in Figure 5 (2) show that CF-GNN's efficiency remains robust across different calibration set sizes:\n\n|Holdout Calibration Set Fraction|CF-GNN| \n|--|--|\n|10% (36 nodes)|2.05±0.06| \n|30% (109 nodes)|2.14±0.12|\n|50% (182 nodes)|2.16±0.11|\n\nIn addition, we emphasize that this does not impact the validity of conformal prediction. With a separate conformal prediction procedure that follows the correction step, we always guarantee valid coverage (this only relies on the exchangeability condition we derive), even in the face of potential overfitting in the correction step, and thus acts as an additional protection layer. \n\n> [4] What if the graph is large? \n\nThank you for this insightful comment! We can modify the mini-batching procedure when the graph is large as follows: in each step, in addition to the sampled training set batch, we also make separate predictions for the correction calibration/testing set. These predictions are used to estimate $\\hat{\\eta}$ and calculate the inefficiency loss. Since we set the correction set to be min(1000, (|D_calib| + |D_test|)/2), when the graph is large, the correction set is set to be 1000, which incurs little computational overhead. \n\nHere we demonstrate its performance on the OGB-arXiv dataset which has 169,343 nodes and 1,166,243 edges. We observe it achieves consistent improvement over base CP on efficiency. We will discuss the large graph issue in the updated paper.\n\n| Method | Size |\n|-|-|\n|CP| 8.79±0.19 |\n|CF-GNN| 4.60±0.15|\n\n> [5] What is the training cost? \n\nThanks for raising this. The calibration step scales similarly to standard GNN training, which is scalable with mini-batching and sampling. Also, CF-GNN has a small input node attribute size (# of classes for classification and 2 for regression), which is often much smaller than the node attributes in the original graph dataset (e.g. in OGB-arXiv, the node attribute size is 128). Using a single Nvidia 2080 Ti RTX 11GB and PyG, the time to train CF-GNN for the smallest graph Cora is ~3 minutes, and for the largest graph, OGB-arXiv is ~1 hour. We will discuss the scalability issue in the updated paper.\n"}, {"review_id": "ENOmXFIexp", "reviewer": "Reviewer_M4K7", "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 ", "questions": "(1) Why do authors not tackle with inductive node classification problem?\n\n(2) What happens if permutation invariance does not hold?\n\n(3) What is the reason for not using RAPS[1]?\n\n(5) In lines 133-134, while employing conformal prediction. is it even possible to change the trained prediction?\n\n(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.\n\n(7) In what circumstances does exchangeability not hold?\n\n\n[1] Angelopoulos, Anastasios, et al. \"Uncertainty sets for image classifiers using conformal prediction.\" arXiv preprint arXiv:2009.14193 (2020).", "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.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "[1] The well-motivated problem, clean writing, and detailed related works.\n\n[2] The first conformal prediction method for graph-structured data with exchangeability and validity assumptions is GNN agnostic and intuitive.\n\n[3] Rigorous proof and method to show exchangeability and validity of conformal prediction on graph-structured data for the first time in the literature.\n\n[4] Capable of achieving conditional coverage, which is a stronger version of marginal coverage.\n\n[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. \n\n[2] There could be ablation studies/experiments over the conformity score functions, such as testing with RAPS[1].\n\n[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.\n\n[4] Why is there no experimental comparison with DAPS[2] (ICML23), which is also a conformal prediction method for node prediction? \n\n[5] The paper's assumption of exchangeability is strict. What happens if exchangeability does not hold?\n\n\n[1] Angelopoulos, Anastasios, et al. \"Uncertainty sets for image classifiers using conformal prediction.\" arXiv preprint arXiv:2009.14193 (2020).\n\n[2[ Zargarbashi, Soroush H., Simone Antonelli, and Aleksandar Bojchevski. \"Conformal Prediction Sets for Graph Neural Networks.\" (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for insightful feedback and for noting that our paper tackles a well-motivated problem, that our method is rigorous and novel, and that our experiments are in-depth. Below, we address the excellent questions raised, with numbers corresponding to those in the review (e.g., [W1] refers to Weakness 1, [Q1] to Question 1, etc.) and we combine similar issues as needed.\n\n> [W1, Q1] Why focus on the transductive setting? How about the inductive setting?\n\nThank you for this great comment. The transductive setting is a widely used evaluation setup for graph machine learning [1]. In Section 3, we show in theory that graph exchangeability holds for transductive settings, which enables the application of conformal prediction to graph-structured data. However, in the inductive setting, freshly arrived testing nodes will be potentially connected to calibration nodes in the graph. Thus the non-conformity scores of calibration nodes are dependent on the ordering of testing nodes. In other words, different orderings of testing nodes that connect to the graph yield calibration nodes with different non-conformity scores. This violates the permutation invariance condition we laid out for graph exchangeability. This setting would be far from common conformal prediction approaches. Thus, in order to establish the foundation for graph conformal prediction, we focus on the transductive setting in this work and leave the extension to the inductive setting for future work.\n\n[1] Kipf and Welling. Semi-supervised classification with graph convolutional networks. ICLR 2016.\n\n> [Q2] What happens when the permutation invariance condition does not hold? \n\nThank you for raising this question. Without any further assumptions, violating the permutation invariance condition may violate exchangeability and make conformal prediction invalid. On the other hand, permutation invariance is a sufficient, but not necessary, condition for exchangeability (which is critical for the validity of conformal prediction). There might exist scenarios where permutation invariance is violated but exchangeability still holds; we believe that investigation on such cases is an exciting direction that requires considerable additional efforts. \n\n> [W5, Q7] When does exchangeability not hold and what will happen? \n\nThank you for this question. Exchangeability is a fundamental assumption for conformal prediction. In summary, there are two scenarios in the graph setting where exchangeability does not hold. One is the transductive setting with a non-random split. The second is the inductive setting. \n\nIf it is violated, then conformal prediction will generally be invalid. One direction is to extend to the “beyond exchangeability” framework [1] by reweighting conformity scores. But adapting this to non-exchangeable graph data remains a challenge since it does not allow for data-dependent weights (e.g. those based on network features). We believe that exploring graph conformal prediction beyond exchangeability is an important (and admittedly challenging) direction to pursue, which we leave for future research. \n\n[1] Barber et al. Conformal prediction beyond exchangeability. The Annals of Statistics 2023. \n\n> [W2, Q3] What is the result for non-conformity score RAPS?\n\nThanks for this suggestion. CF-GNN is agnostic to the choice of non-conformity score. We have picked CQR and APS since they are representative choices for regression and classification. Following the suggestion, we further experimented on RAPS and showed that CF-GNN can still obtain consistent improvement in efficiency reduction: \n\n|Size|CP|CF-GNN|%Improvement|\n|-|-|-|-|\n|Cora|1.67±0.11|1.42±0.05|-15.35%|\n|DBLP|1.39±0.02|1.32±0.01|-5.00%|\n|CiteSeer|1.30±0.07|1.04±0.04|-19.85%|\n\n> [W4] Comparison with DAPS.\n\nThank you for pointing out this interesting paper. We would like to first emphasize that the *DAPS is concurrent work, and that it was made public after we submitted our work to NeurIPS*. This is why we were not able to compare in our submission. We also note that DAPS employs diffusion to aggregate non-conformity scores, whereas CF-GNN introduces a learnable framework that optimizes efficiency through a specialized loss function. In fact, CF-GNN can be seen as a strict generalization of DAPS, becoming equivalent when employing a simple sum function over immediate neighbors. Our method's versatility also extends to regression tasks, highlighting further distinctions from DAPS. We’ll discuss it in the paper.\n\n> [W3, Q6] Redefining degree-weighted coverage?\n\nThank you for raising this intriguing question. We first note that modifying the coverage definition with degrees would incur substantial modifications to the theory underlying graph conformal prediction. However, even without changing the definition, conditional coverage based on node degree can give insights into what we would get for your \"weighted\" coverage. The idea is that if the conditional coverage is good across all values of node degree, then degree-weighted coverage is also valid. As shown in Supplementary Table 9, with base CP, the worst-slice conditional coverage (WSC) conditioned on degree decreases to 0.79 when the target is 0.9, supporting the reviewer’s claim that marginal coverage may neglect variation in node degrees. In contrast, our CF-GNN has 0.89 WSC, implying satisfactory degree-based coverage. We hypothesize that it is due to network smoothing, where the prediction of low-degree nodes is modified by connections to high-degree nodes. More theoretical and empirical analysis will be interesting and left for future work.\n\n> [Q5] Tradeoff between uncertainty quantification and predictive performance?\n\nWe thank the reviewer for bringing up this important question. Reviewer Wep3 has also expressed interest in this matter. Due to the constraints on the length of our response to individual reviewers, we direct the reviewer to our detailed answer provided in Reviewer Wep3's inquiries [Question 2]."}, {"review_id": "yVMuF64Cqg", "reviewer": "Reviewer_XvAj", "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. ", "questions": "Please refer to the Weakness section.", "limitations": "I am not seeing limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "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.\n\n[1] Stadler, Maximilian, et al. \"Graph posterior network: Bayesian predictive uncertainty for node classification.\" Advances in Neural Information Processing Systems 34 (2021): 18033-18048.  \n[2] Zhao, Xujiang, et al. \"Uncertainty aware semi-supervised learning on graph data.\" Advances in Neural Information Processing Systems 33 (2020): 12827-12836.  \n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for insightful feedback and for noting that our paper is interesting, timely, and easy to follow. The reviewer raises great questions and we respond to them below:\n\n> Clarification on the construction of the correction dataset\n\nWe thank the reviewer for raising this issue, which is helpful in improving the clarity of our manuscript. We shall clarify in the revision. The correction dataset was randomly sampled from the calibration dataset with a pre-specified sample size. It plays a crucial role in our approach, enabling the calculation of inefficiency loss by simulating the downstream conformal steps. \n\n> Inclusion of GNN-based uncertainty quantification methods. \n\nWe thank the reviewer for pointing us to these papers. We will discuss them in the expanded section on related works. Note that the methods in question are not directly comparable to our work since they produce an uncertainty score representing the model uncertainty per node, which aims at OOD/misclassification detection. As a result, these works do not construct uncertainty scores for all classes and do not produce prediction intervals/sets. In contrast, we aim to construct a prediction set/interval and require a score for every class. We also want to mention that conformal prediction could also be extended to these problems in non-graph settings [1,2] and we happen to be interested in extending it to graph OOD detections. However, this direction is out of the scope of this current work. \n\n[1] Kaur, Ramneet, et al. \"iDECODe: In-distribution equivariance for conformal out-of-distribution detection.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 7. 2022.\n\n[2] Ishimtsev, Vladislav, et al. \"Conformal $ k $-NN Anomaly Detector for Univariate Data Streams.\" Conformal and Probabilistic Prediction and Applications. PMLR, 2017.\n"}, {"review_id": "KVRe62ehRl", "reviewer": "Reviewer_y5h3", "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.", "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?", "limitations": "No limitation discussed. No potential negative social impact.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n- [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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for insightful feedback and for acknowledging that our paper is original and makes solid theoretical and empirical contributions. The reviewer has raised great questions and we respond to them below:\n\n> Ways to make baseline UQ methods empirically reach $1-\\alpha$ coverage? \n\nWe thank the reviewers for raising this great question! We want to emphasize that, first, these UQ methods cannot reach nominal coverage either in theory or empirically. In contrast, what is unique about CF-GNN is that it rigorously achieves any pre-specified coverage rate. Second, even if it is possible to tune the nominal level of previous UQ methods to achieve $1-\\alpha$ coverage and compare their efficiency with CF-GNN, in practice, it is impossible to know to which extent one should adjust the nominal level for those methods. On a side note, conformal methods could be used to calibrate the nominal level for these UQ methods to achieve valid coverage; however, it is beyond the original implementation of the UQ method and requires substantial effort in method development.\n\nHowever, for the sake of evaluating the methods with access to gold labels, it is possible to reach $(1-\\alpha)$ coverage by tuning the nominal coverage level of the previous methods and selecting the level when the empirical coverage reaches the target coverage. For our preliminary experiment, we used the Cora dataset with a target coverage of 95% and we studied Graph Attention Temperature Scaling (GATS) [NeurIPS 2022], which represents the most recent GNN-based UQ calibration method in our set of baselines. We conducted a grid search of nominal coverage from 90% to 100% with step size 0.1% and stopped when it reached the empirical target coverage. The stopping nominal coverage is adjusted to $1-\\alpha$ = 92.2%, which is far away from the pre-specified target 95% coverage. The prediction set size becomes 1.82 which is still larger (less efficient) than CF-GNN, which has size 1.76. We will discuss this interesting point in the revised manuscript.\n"}, {"review_id": "6IWWCLquQ4", "reviewer": "Reviewer_rkWb", "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. ", "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. ", "limitations": "The authors address the transductive focus as a limitation which is an important consideration. I don't foresee potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful feedback and for acknowledging that our paper tackles an interesting problem, that it is well-written, and that the evaluation is extensive. The reviewer raises great questions and we respond to them below:\n\n> Why focus only on transductive settings? Extension to inductive and graph-level tasks?\n\nWe thank the reviewer for this intriguing comment. The transductive setting is a widely useful evaluation setup for graph machine learning [1,2]. In Section 3, we show in theory that graph exchangeability holds for transductive settings, which enable the direct application of conformal prediction to graph-structured data. While other settings such as inductive learning are at least equally exciting, we start with the transductive setting to connect with the most standard conformal inference approach and establish the foundation for conformal prediction on graphs. \n\nThere are indeed nontrivial challenges for the inductive node-level setting: it may need a completely different setup, theoretical analysis, and methodology, which goes way beyond the scope of this paper. In the inductive setting, newly arrived testing nodes will be potentially connected to calibration nodes in the graph. Thus the non-conformity scores of calibration nodes are dependent on the ordering of testing nodes. In other words, different ordering of testing nodes that connect to the graph may imply that calibration nodes have different non-conformity scores. This violates the permutation invariance condition we laid out for graph exchangeability. We believe that the extension to the inductive setting needs significantly different techniques (the reviewer has pointed out that this is a very valuable future direction to pursue). A possibility is to extend the “beyond exchangeability” framework [3] by reweighting conformity scores by using certain predefined “similarity scores”. However, even the theory in [3] might not apply since it needs data-independent weights as input, and this precludes the use of network structures. \n\nFor the graph-level prediction task such as the prediction of molecule properties, each data point is a graph. Thus, there is no issue with graph exchangeability since there are no direct dependencies between calibration and testing graphs, as seen in the node-level prediction problem. In this problem, conventional conformal prediction methods can be directly applied. \n\nWe will expand the discussion on these points in the updated paper.\n\n[1] Kipf, T. N., & Welling, M. (2016). Semi-supervised classification with graph convolutional networks. ICLR.\n\n[2] Hamilton, W., Ying, Z., & Leskovec, J. (2017). Inductive representation learning on large graphs. NeurIPS.\n\n[3] Barber, R. F., Candes, E. J., Ramdas, A., & Tibshirani, R. J. (2023). Conformal prediction beyond exchangeability. The Annals of Statistics, 51(2), 816-845. "}]

Author rebuttal:
> Summary of main points

We thank the reviewers for their valuable feedback and constructive suggestions for improvement. Overall, all five reviewers considered our work well-written and well-motivated, and all appreciated the theoretical rigor and strong empirical performance of our proposed method. 

A few stimulating questions raised have motivated us to conduct additional numerical experiments, which strengthen the empirical evidence and the paper. In summary, we found the following properties through new experiments:  

- The training cost of calibration GNN is manageable as it scales well to large graphs using a mini-batching strategy (Wep3);
- Our framework consistently improves the efficiency for other nonconformity scores beyond APS and CQR (M4K7);
- Our framework has minimal impact on model accuracy (Wep3, M4K7);
- Our method is more efficient than other UQ methods when the latter is manually tuned to a specific coverage level (y5h3). 

We also added further discussion in response to the reviewers’ important suggestions for clarification, including 

- the motivation of the transductive setting (M4K7, rkWb)
- the importance of permutation invariance and exchangeability (M4K7)
- the coverage after weighting based on node degrees (M4K7) 
- the robustness to overfitting (Wep3) 
- the compatibility with mini-batch training (Wep3)
- the tradeoff between prediction accuracy and uncertainty quantification (Wep3, M4K7)
- relation with related works on GNN-based uncertainty quantification (M4K7, XvAj)
- efficiency of baseline UQ methods (y5h3)

Please see our point-by-point response to all questions raised by each reviewer’s comments below. 

Meta-review: The paper introduces an approach that utilizes conformal prediction under the exchangeability assumption for graph-structured data. The method optimizes uncertainty quantification, offering simplicity and effectiveness. The paper presents a well-motivated problem, clear writing, and extensive related work. Notably, it's the first GNN-agnostic conformal prediction approach for graphs with exchangeability and validity assurances, backed by rigorous proofs. The method achieves conditional coverage, surpassing marginal coverage, as demonstrated through thorough experiments and ablation studies. The reviewers are in agreement that the paper should be accepted. We ask the authors to incorporate the points raised during the discussion such as additional related work.
Decision: Accept (spotlight)