Conformal Prediction: A Theoretical Note and Benchmarking Transductive Node Classification in Graphs
Authors: Pranav Maneriker
Aditya T. Vadlamani
Anutam Srinivasan
Yuntian He
Ali Payani
srinivasan parthasarathy
Venue: Accepted by TMLR ()

Abstract: Conformal prediction has become increasingly popular for quantifying the uncertainty associated with machine learning models. Recent work in graph uncertainty quantification has built upon this approach for conformal graph prediction. The nascent nature of these explorations has led to conflicting choices for implementations, baselines, and method evaluation. In this work, we analyze the design choices made in the literature and discuss the tradeoffs associated with existing methods. Building on the existing implementations for existing methods, we introduce techniques to scale existing methods to large-scale graph datasets without sacrificing performance. Our theoretical and empirical results justify our recommendations for future scholarship in graph conformal prediction.

Published in Transactions on Machine Learning Research (05/2025)
Conformal Prediction: A Theoretical Note and Benchmarking Transductive Node Classification in Graphs
Pranav Maneriker
pmane@dolby.com com
Dolby Laboratories
Aditya T. Vadlamani"
vadlomoni. 120osu edu
Deportment of Computer Science and Engineering The Ohio State University
Anutam Srinivasan
srinioasan @osu.edu
Department of Electrical and Computer Engineering The Ohio State University
Yuntian Hel Meta
heyuntian.cc&@gmaal.co www.wnnnwwmam.mmmmmmmmmmmmmm com
Ali Payani Cisco Systems
apoyanii@cisoo.com com
Srinivasan Parthasarathy
srini www.seee.hiiottttttte edu
Deportment of Computer Science and Engineering The Ohio State University
Reviewed on OpenReview: https: openreview. net/ forum? Ed11BB3333
Abstract
Conformal prediction has become incrcasingly popular for quantifying the uncertainty associated with machine learning models. Recent work in graph uncertainty quantification has built upon this approach for conformal graph prediction. The nascent nature of these explorations has led to conflicting choices for implementations, baselines, and method ovaluation. In this work, we analyze the design choices made in the literature and discuss the tradeoffs associated with existing methods. Building on the existing implementations, we introduce techniques to scale existing methods to large-scale graph datasets without sacrificing performance. Our theoretical and empirical results justify recommendations for future scholarship in graph conformal prediction.
1 Introduction
Modern machine learning models trained on losses based on point predictions are prone to be overconfident in their predictions (Guo et al. 2017). The Conformal Prodiction (CP) framework (Vovk et al.) 2005 provides a mechanism for generating statistically sound post hoc prediction sets (or intervals, case continuous outcomes) with coverage guarantees under mild assumptions. Usually, the assumption made in CP is that the data is exchangeable, i.e., the joint distribution of the data is invariant to permutations of the data points. CP's guarantees distribution-fret and can be added post hoc to arbitrary black-box prodictor scores, making lhem ideal candidates for quantilying uncertainty in complex models, such as neural networks.
Network-structuree data, such as social, transportation, and biological networks, is ubiquitous in modern data science applications. Graph Neural Networks (GNNs) have been developed to model vector representations
"Equal Contribution. This work done while the author was student The Ohio State University

---

Published in Transactions on Machine Learning Research (05/2025)
of network-struchured data and be effective in variety of tasks such as node classification, link prediction, and graph classification (Hamilton 2020: Wu et al. 2022). As the network structure introduees possible dependencies between the data points, uncertainty quantification approaches built for independent and identically distributed (iid) data cannot be directly applied to graph data. However, recent work (Clarkson 2023: Zargarbashi el. al. 2023: Huang et al. 2023 has demonstrated that, in specific settings, CP can be applied to graph data to generate statistically sound prediction sets for the node classification task, similar other classification tasks. These methods were designed to leverage the graph structure and homophily to improve upon baseline non-graph CP methods. Variations of CP, ranging from most to least computationally
expensive, include (1) Full-CP (Vovk et al. 2005), (2) Cross-CP /CV+ /Jackknife-+ [Vovk] 2015 Barber
et al. 2021), and (3) Split (or Anductive)-CP (Papadoppulos et al.) 2002 Papadopoulos 2008). Prior
work on graph CP has mainly focused on the Split-CP setting due to its computational efficiency and the distribution-Fi guarantees with black-box models. Thus, we also focus on Split-CP for our work.
Key Contributions: This work makes the following contributions:
We perform comprchensive analysis of the existing graph split-CP litcrature (c.g., CFGNN, DAPS) for transductive node classification. This analysis aims to understand the choices made in method implementation (i.e., scalability) and method evaluation (i.e., dataset preparation and baseline selection). We also extend this analysis to include analysis of when these graph-based approaches improve over non-graph CP methods, such as TPS and APS.
2. We present theorem for evaluating the efficiency (set size) of different conformal prediction methods prior to deployment.
3. We develop a Python library that implements our analysis, enabling practitioners to efficiently apply and evaluate conformal prediction for graph data, with scalability enhancements for large graphs, particularly for conpute-intensive methods like CFGNN.
2 Conformal Prediction
Conformal prediction is used to quantify model uncertainty by providing prediction sets/intervals with rigorous coverage guarantees. We will focus conformal prediction in the classification setting. Given a calibration dataset Dealib= = W))= where æ; X Rd and yi E E = {l,..., K}, conformal prediction can be used to construct prediction set C for an unseen test point (æn-11 Un+1) such that
Pr [r[ E C(#n+1)) 1-a
where 1 - a E (0,1) is a user-specified coverage level. The only assumption required for the coverage guarantee is that Dealih U ((( 11) exchangeable. The following theorem provides general recipe for constructing a prediction set with a coverage guarantee.
Theorem 2.1 (ook et al., 2005; Angelopoulos & Bates 2023 ). Suppose {1a )+ are erchangeable, X x + IR is score function measuring the non-conformity of point (x,y), y), with higher scores indicating lower conformity, and a target miscoverage level a E [0, Let ((a) = Quantile [[n-1)(1-a]], (:) be the conformal quandile. Define C(x) = [u E
- {(a))- Then,
1 a + m+1 2 Pr (y E C(xn+1)) 21
(1)
The upper bound assumes that the scores are unique that suitably random tie-breaking method exists.
The function s is the non-conformity score function, and it measures the degrec of non-agreement between an input & and the label y, given exchangeability with the calibration data Dealiby i.e., larger scores indicate worse agreement. between x and yy- While Theorem 2.1 does not restrict the choice of s, this choice can significantly impact the size the prediction set.
The setup of Theorem 2.1 is called Split-CP, as the score function remains fixed for the calibration split. In other versions of CP, the score function is usually more expensive to compute it requires some
2

---

Published in Transactions on Machine Learning Research (05/2025)
< k S calibration points in addition to the unseen test point. For Full-CP, we have k = n, whereas for Cross-CP CCoss-C/CV--LC Duain U Dvalid U Dealib Drest.
& < n. When applying Split-CP, the dataset is partitioned into D =
2.1 Conformal Prediction in Graphs
The usual tasks of interest with graph data include node classification, link prediction, and graph classification. This work focuses on node classification and its extensions to conformal prediction. Consider an attributed homogeneous graph 9 = (V, X), where the set of nodes, & is the set of edges, and X is the set of node attributes. Let A denote the adjacency matrix for the graph. Further, let y (I...., K} denote the set of class labels associated with the nodes. For v E V, By X Rd denotes its features and yo y denotes its true class label. The task of node classification is to learn model that predicts the label for each node given node features and the adjacency matrix, i.e., (X, v) + Vo. Corresponding to the CP partitions, we denote the nodes in the training set as Virain: the validation set as Vialid, the calibration set as Vealib, and the test set as Viest- We denote Vdev = Vtrain U Villd as the dovelopment set for the basc model. Note that labels are available only for nodes Virain; Veatid; and Vealib, and must be predicted for nodes in Viest. The model cycle will involve four phases, viz. training, validation, calibration, and testing, Next, we discuss the different scttings for node classification in graphs and the applicability of conformal prediction.
Transductive setting In this setting, the model has access to the fixed graph G during the model cycle. The nodes used in the model cycle are split into Virain, Vvalid. and Vealtb U Veest. The specific Vealib and Veest are subsets of Yeali U Vest- This is the setting considered by Zargarbashi et al. (2023) and Huang et al. (2023). Note that the labels for Veatib are not available for training and validation of the base model; however, all the neighborhood information of G and the features B. and labels Ve, for v E Vaev are available. During the calibration phase, the (z., ye) for Vealib and all the neighborhood information are used to compute the non-conformity scores. This split ensures that the base model cannot distinguish between the calibration and test nodes, and hence exchangeability holds for E Vealib U Veest.
Inductive sctting In this setting, the model is only trained and calibrated on fixed graph G during the model cycle. Once the calibration phase is complete, G changes to include new unseen test points, breaking the exchangeability assumption as nodes arriving later in the sequence will have access to neighbors that came earlier. This setting is infrequently studied as it requires making specific assumptions about graph structure and the data generation process (Clarkson 2023 Zargarbashi & Bojchevski (024).
In line with previous work, focus on the transductive setting. The following theorem states that scoring model trained on the calibration set will generate scores exchangeable with the test set in the transductive setting, thus allowing for conformal prediction.
Huang et al. )023 Let g = (V,E, be an attributed graph, and - AIVIK be any permulation equivariant model on the gruph V as the oulput probability matric for a model trained on only Va- Then any score function s(v, 3) = s(Il. y, 9) is exchangeable for all u E Veati U Vteet-
Theorem 2.2 ( (Zargarbashi et al. 2023
Venta U Veest be exchangeable. Lef F;
X
(e.g., GNNs). Define F(G)- = 1l A
The intuition for this theorem that if the underlying model does not depend on the order of the nodes in the graph, then the outputs will also be exchangcable. This holds for most standard GNNs. The formal proof for this theorem is available in (Zargarbashi al.) 2023 Huang et al., 2023 This theorem paves the way for using conformal prediction for transductive node classificaton..
For the following sections, we will assume that the base model f : X' + Ay, where Ay is the probability simplex over }/ is learned using the training and validation sets Dirain U Dvalidd The calibration set Deatih is used to determine the q(a) from Theorem 2.1 and the test set Dreat is the set for which we want to construct our prediction sets. Note that D=- {(x,, Vo) u E V₂} for graph datascts. Note that the scores need not lie over a simplex, but instead be in RR However, this greatly simplifies the exposition for the following sections and is standard practice in prior work.
3

---

Published in Transactions on Machine Learning Research (05/2025)
2.2
Conformal Prediction Methods
Several conformal prediction methods are discussed in the CP for transductive node classification literature, including the following general and graph-specific methods.
2.2.1 General Methods Applied to Transductive Node Classification
Threshold Prediction Sets (TPS) (Sadinle et al., 2019) In TPS the score function is s(x, y) 4(x)y, where f())g is the class probability for the correct class. This is the simplest method, which is also shown to be optimal with respect efficiency, thus making essential to include as a baseline. However, TPS known achieve this efficiency by under-covering hard examples and over-covering easy examples (Angelopoulos et al. 2021 Zargarbashi al. 2023) We note that this discrepancy is claimed to occur as the TPS scores are not adaptive, and consider only dimension of the score for each calibration sample. However, Sadinle Srdweve,,Sadinle... et al. (2019) also proposed a classwise controlled version of TPS. Instead of defining single threshold for all classes, they separately compute the threshold for each class for a corresponding a. Thus, we define classwise quantile thresholds for each y E E
[(n + 1)(1 agy] 11)1-aa))]] {s(x,, vi) i== I......................... n. = y}
i(ay, y) = Quantile
(2)
and the corresponding prediction sets as
C(x) by E E s(0, S (()
Note that this version achieves coverage for each class label, making it more adaptive (i.c., Pr(un+1 E C(x) 1 = 2 1-1aa a, Vy E y). The version defined by (adinle et al. (2019) allows con- trolling By for each class, though we set ay = a for class-adaptability. The trade-off with the adaptive version is that we have fewer calibration samples for each quantile threshold dimension, which may lead to higher variance in the distribution of coverage \ovk 2012). We refer to this variation TPS-Classwiss
Adaptive Prediction Sets (APS) (Romano et al., 2020) APS is the most popular CP baseline for classification tasks. For APS, the softmax logits sorted in descending order, and the score is the cumulative sum of the class probabilities until the correct class. For tighter prediction sets, randomization can be introduced through a uniform random variable. Formally, if (()) 2 #())(2) 2 ... +()) u ~ (0, 1), and Ty is the rank of the correct label, then
Fvy Σ a())())
s(x, 3)
-uf(x)y
Regularized Adaptive Prediction Sets (RAPS) (Angelopoulos et al.) 2021 One drawback APS is that it can produce large prediction sets. RAPS incorporates a regularization term for APS. Given the same setup as APS, define () lfc y A(x)y 2 [x)))). Then,
(1 y)
#(x) - un (x), + v max[(o(x, y) kreg); 0),
where v and kyey 2 0 are regularization hyperparameters.
2.2.2 Graph Methods
Graphs are rich in structure and network homophily, and recent works in graph CP leverage these propertics when developing graph-specific methods. Intuitively, network homophily suggests that non-conformity scores and efficiencies of connected nodes related.
4

---

Published in Transactions on Machine Learning Research (05/2025)
Diffusion Adaptive Prediction Sets (DAPS) (Zaggarbashi et al., 2023 To leverage network
homophily, DAPS performs one-step diffusion update on the non-conformity scores. Formally, if s(x; y) is a point-wise score function, then the diffusion step gives a new score function
8( u) = (1 - 6)s(2, v) +
Σ WEN
s(u, y);
where d E [0, 1] is diffusion hyperparamter and N₂ is the 1-hop neighborhood of æ. More details and results DAPS can be found in Appendix C.I.
Diffused TPS-Classwise (DTPS) In the case of DAPS, is chosen to be APS; however, any adaptive score function can be used. In this work, we consider applying diffusion to the scores from OPS-Classwise (the adaptive variation of TPS). More details and results on DTPS can be found in Appendix C.1
Neighborhood Adaptive Prediction Sets (NAPS) (Clarkson, 2023 NAPS leverages the neighbor- hood information of a test point to compute a weighted conformal quantile for constructing the prediction set. Tt is the only method the study that can work with non-exchangeable data, but loosens the standard bounds of conformal prediction. The weighting functions used with NAPS are uniform, hyperbolic, and exponential. A detailed explanation of NAPS, the weighting functions, and how it is adapted to the transductive setting is in Appendix C.2
Conformalized GNN (CFGNN) Huang et al. 2023 CFGNN is model-based approach to graph CP. Similar to ConfTr (Stutz et al. 2021). CFGNN uses second model and an inefficiency-basey loss function to correct the scores from the base model. This is feasible as all the steps of the conformal prediction framework (i.c., non-conformity score computation, quantile computation, thresholding) can be expressed as differentiable operations (Stutz et al. 2021). The underlying observation for CFGNN that the inefficiencies are correlated between nodes with similar neighborhood topologies, hence, the socondary model used is a GNN. The inefficiency loss includes point-wise score function that differs for training and validation. In our work, set the score function to be APS with randomization between training and validation. More details can be found in Appendix C.3
2.3 A Theoretical Note on Randomization.
Recall that APS (Romano et al.] 2020) can be implemented in both randomizod and a deterministic manner (see Appendix for derivations), by using uniform random variable determine if the correct.
class is included not in the prediction set, during the calibration phase. Both versions of APS provide conditional coverage guarantees; however, the deterministic version has simpler exposition. so this version is implemented in the popular monographs on conformal prediction by Angelopoulos & Bates 2023).. However, the lack of randomization may result in larger prediction sets. This modification affects computing the conformal quantile during the calibration phase and the prediction set construction during the test phase.
We will formally present the conditions that impact (prediction) efficiency, and later apply it APS with and without randomization. Let A(x, y) be any non-conformity score function, and let,
a Quantile ([nn+ 1)(11)111 a)1, {A(z;, (i).,,))?1 wi)
n
Consider the exchangeable sequence, (A(z, v/ |-1 where w randomly selected incorrect labe now define az E [0, such that:
We
i Quantile [[m++1)(1 1)(1+ 1)(1- {A(o,, v. 1i²1))))))
(3)
For an explanation why this exchangeable see Appendix

---

Published in Transactions on Machine Learning Research (05/2025)
Table Summary statistics for datasets. Predefined splits from the original sources are noted.
Dataset
Nodes
Edges
Classes
Features
# Train
# Valid
# Test
Amazon Computers
13,752
491,722
10
767
Cora
19, 19,793
126,842
8,710
Coauthor
CS
18,333
163,78 788
15
6,805
Flickr
89,250
899,756
44,625
22,312 29,799
22,313 48,603
ogbu-arxiv
169,343
1,166,243
40
128
90,941
In other words, ag is the miscoverage level for the random incorrect label when using QA to construct the prediction set. By leveraging recent result in the literature (Vadlamani et al. 2025), we can compute oz and see that the following result holds (see Appendix B
1 - de s Priyat1 E Ca( 5 - a n+
(4)
Let A(æ, y) be another non-conformity score and define {A(z; v,") } theorem gives a sufficient condition for when A more efficient than A.
nutl } and a similarly. The following
Theorem 2.3. a a. 2 (nf then score function produces a more efficient prediction set than Å. Formally, ( [Ca (=)(==+1)]
With Theorem 2.3 we can further determine the expected efficiency improvement as the calibration set size gets arbitrarily large, as seen in the following corollary. Proofs for both results are available in Appendix
Corollary 2.3.1. As co, (x [CA(#))))]] (K (at az
Corollary 2.3.1 allows practitioners to gauge the expected efficiency (i.e., set size) benefits prior to the inference phase.
3 Empirical Analysis and Insights
Key Research Questions: the subsequent, sections, this work will answer the following key questions raised when ovaluating the litcrature on CP for transductive node classification.
1. TPS-Classwise is largely overlooked in the recent literature, given the popularity of APS and TPS not being adaplive. Is TPS-Classwise a viable baseline? (Discussed in Section 3.1
2. Thcorem 2.3 provides framework for evaluating when a method is more efficient (that is, produces smaller sets) than another. What are the empirically observed implications of Theorem 2.3 on APS? (Discussed in Sections 3.2 and 3.3
3. Can we scale the computationally intensive CFGNN to handle large-scale graphs, such as ogbn-arxiv, and at what cost to efficiency and coverage, if any? (Discussed in Sections 3.3 and 3.4
4. Given the thalretical, experimental, and methodological analysis, what are some key insights and guidelines for future scholarship in this area? (Discussed in Sections 3.5
Datasets. Table contains representative set of datasets of varying sizes (i.e., number of nodes/edgen and the number of classes evaluated in this section. The Appendix contains the list of all the datascts used
in this study. We used the dataset versions available on the Deep Graph Library (Wang el al. 2019 and Open Graph Benchmark (Hu et al. 2020).
Methods. Scction 2.1 includes all of the bascline methods considered in the experiments.
Metrics. For evaluation, used the following standard metrics (Shaerr & Vovk 2008):

---

Published in Transactions on Machine Learning Research (05/2025)
(i) Coverage is the proportion of test points where the true label is in the prediction set, ie.,
1 DieD Ii E C(x:))-
Dreat
(ii) Efficiency is the average prediction set size, i.e, Pewer DieD C(x)))
(iii Label (or Class) Stratified Coverage (Sadille et al. 2019) is the mean of the coverage for each
class, iee, |Dicus| EieDome ( Ex= [yv E C((:), y = kl)
Dataset Splits and Training. There are several methods of partitioning D into Dirains Dvalid, Dealib, and Duest Two methods used in existing works on graph conformal prediction for node classification are:
(i) Full-Split (FS) Partitioning (Huang et al. 2023 ). In this split style, D is partitioned based on a size constraint. For example, CFGNN (Huang et al. 2023) the authors split the datasets in their experiments randomly, satisfying a 20%/10%/38 35555/555//55 /3% constraint for Derain/ /aaai//Daai///i Peallib/Deess Note that large portion (65%) of the full dataset has labels provided (i.e., in the development or calibration set). This style is ideal for methods with numerous trainable (or tunable) parameters, as more calibration data is available for training. We consider the following splits: (Dtrain, Dvalid, Dealib; Drest) (00.2, 0.1, 0.35, 0.35), (0.2, 0.2, 0.3, 0.3), (0.3, 0.1, 0.3, 0.3), and (0.3, 0.2, 0.25, 0.25).
iii) Label-Count (LC) Sample Partitioning Zargarbashi et al. 2023). In this split style, the data is partitioned to ensure an equal mumber of samples of each label is present in Drrain, Dvalid, and Deatib- The remaining nodes are Drest. This setting is common when only a small proportion of labeled nodes are available (e.g,, semi-supervised learning). Intuitively, this setting is ideal for methods that do not have many parameters to train. We explore setting the number of samples per class to 10, 20, 40, and 80. Note that we assign nodes of each class sequentially, so it is feasible in this setup to have some classes with no representative samples in some data subset. Finally, we note that this is biased sampling scheme which may violate the exchangeability assumption; however, we include this scheme as it is used in the literature (Zargarbashi et al. 2023 2024) for completeness of our analysis.
If the dataset has predefined splits (e.g., Flickr, ogbn-arxiv), we ensure that Drrain and Doalid come solely from the training and validation splits, while Dealib U Dusst come from the test split.
3.1. Proposed Baseline using TPS with Adaptability. From Figure I we see that using TPS- Classwise successfully provides label-stratified coverage in both the FS and LC split settings. This additional adaptability comes at a cost to efficioncy as seen in Figure 7 a standard tradcoff in conformal prediction. One factor that impacts adaptability the dataset's 's label distribution, particularly because of labels with little representation, as seen in Figure for ogbn-arxiv. Because TPS is not adaptive, has been ignored as bascline; however, TPSS-Claswisst adaptability makes it viable bascline for future scholarship.
3.2. Empirical Observations on Randomization for APS. Applying Theorem 2.3 to randomized APS (A) and deterministic APS (A), intuitively, as each score in A gets shifted by small uл term to the left, would be lower than gū- Thus, the miscoverage levels we would search for in the complementary scores o² would be less than 1 - ad. 1 1 ad < 11-a. ad randomized prediction set is more efficient than the non-randomized one.
af add 0. If the shift is sufficiently large, the
In Figure 3 we show what this looks like for a practical example over the Cora dataset. In Figure 3 (right), the normalized sorted index at which the lower threshold 9A is reached when considering the incorrect classes is lower, i.e., 1 - a is lower, and hence a is higher. As a part of the proof, we show dependencies on (Λ+T) and (K- -)- which indicates the improvements are more pronounced for larger Dealib and many classos.
Figure 4 provides box plots that compare the elficiency of randomized and non-randomized versions of APS across different datasets. We observe that the randomized version consistently provides a more efficient prodiction set for each split type. This effect most pronounced for datasets with many potential classes in the FS split, which aligns with the intuition from Theorem 2.3 described above and Corollary 2.3.1 Overall, the empirical results show that the effect of randomized APS is more pronounced for larger values of K. This
7

---

Published in Transactions on Machine Learning Research (05/2025)
tps, casswise
tps, casswise
Ups classwise
classwise
0.7
0.8
0.9
1.0
0.7
0.8
0.9
1.0
0.7
0.8
0.9
1.0
0.7
0.8
0.9
1.0
label wwt.ssttttttecccoom coverage
label wwt.ssttttttecccommm coverage
label stratiteedd coverage
label label_stratiifeee htt_ssstttieedceeeeeeeee coverage
(a) Amazon Computers
(b) ogbn-arxiv
Figure 1: We set the target coverage rate 0.1. The boxplots present the Label Stratified Coverage for (a) Amazon Computers and (b) ogbn-arxiv for both the FS split (left) and LC split (right). We want the means (white triangle) to be around 1 - a 0.9. For Labeled Stratified Coverage, IPS-Classwiie is comparable to or better than TPS.
ogbn-arxiv
15.0
12.5
10.0
7.5
35
Figure 2: Label Distribution for ogbn-arxiv
randomized
1- of
4a
non-randomized
1 1-
0.8
Denaity
0.6
0.4
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Score
Sorted Index
Figure 3: Scores for the Cora dataset using the randomized and non-randomized versions of APS. In the left plot, the vertical lines show the shift in the standard conformal quantiles for A (randomized APS) and Á (non-randonized APS) for 0.9 coverage. In the right plot, the vertical lines show the shift in the ag value for A and À using scores for the incorrect classes, We have (1 - =²) - (1 - a > n+1 + a o > nt1 which satisfies the condition for Theorem 2.3 Thus, A is more efficient. as seen in the left plot since QΛ < q
2
2
observation suggests that APS with randomization should be the default implementation of APS for future scholarship when looking to optimize (prediction) efficiency.

---

Published in Transactions on Machine Learning Research (05/2025)
aps
ap5, rasdrandddded
aps
aps randomized
Amazon_Cone Computers
Amazon
Amazon_Computie Saann__oomupete
Coauthor_CS CS
Coauthor CS
dataset
dalaset
Cora
Cora
Flickr
Flickr
ogbn-arxiv
ogbn-arxiv
0
10
0
10
20 efficiency
30
efficiency
Figure 4: We sct the target coverage rate a = 0.1. Box plots depicting the efficiencies of APS and Randomized APS across different dalasets and multiple runs in both the FS split (left) and LC split (right). Using randomization (the lower box plot for each dataset) consistently improves over the non-randomized version as the efficiencies are distributed around smaller values.
3.3 Impact of Bascline and Scoring Function in CFGNN Inefficiency Loss. The choice of non- conformity score in the inefficiency loss during calibration and testing plays vital role in determining the overall performance of GNN-based conformal prediction. To illustrate, we replicate an experiment by Huang let al. 2023) who use TPS for the inefficiency loss during the calibration stage and non-randomized APS for the testing stage, which gives a significant improvement in efficiency over the bascline (Figure right). However, randomized APS used instead (Figure left), we observe that the baseline is competitive across various coverage thresholds. It worth noting that CFGNN appears robust to this choice, although the gains in efficiency not as dramatic in the randomized sctting. We also note that the confidence bars are narrower in the randomized setting. Similar results were observed other datasets (see Appendix B
Based on these insights, we use an improved version of CFGNN, which uses APS with randomization for both training and evaluation, labeled as 'efgnn aps.' The original implementation is labeled as "cfgun orig' Our library implementation of CFGNN allows for either TPS or APS to be used for calibration and testing and is extensible to other conformal prediction methods. We extend our results more datasets and compare against 'aps randomized" (i.e., the baseline without applying the topology-aware correction via CFGNN). Figure 6 presents the results for both the FS and LC split styles. We observe that 'cfgnn_ __aass' is as good 'cfgnn orig' and can even improve upon 'aps randomized' in terms of efficiency. In the LC split setting, CFGNN is seen to be quite brittle because there may not be enough data to train second GNN.
3.4 Scaling CFGNN for Large Graphs. The original CFGNN implementation uses full batch training. While this approach has merits, it also poses challenges, particularly when dealing with larger graphs. The evident need for a more scalable solution lod us to implement modifications. We implemented a batched version of CFGNN to ensure can be used for larger graphs (e.g,, ogbn-arxiv). To further scale CFGNN, we cache the outputs from the base model to be treated as features for CFGNN training rather than having to sample neighbors for both the base model and CFGNN, significantly speeding up the computation in training and evaluation.
We compare three CFGNN implementations to demonstrate the impact of batching and caching on the runtime. Across all comparisons, we use the FS split, with /04/22%/5%%///// data split. We use the best base GNN (w.rtt accuracy) and best CFGNN (wr.t, efficiency) architecture from hyperparameter tuning. The baseline implementation follows the setup by Huang et. al. 2023 where the CFGNN is trained with

---

Published in Transactions on Machine Learning Research (05/2025)
Cora [r_
APS
CFGNN Baseline
Randomized APS
Non-Randomized APS
4.5
3.5
Efficiency
3.0
2.0
1.5
0.70
0.75
0.80
0.85
0.90
0.95
0.70
0.75
0.80
0.85
0.90
0.95
Target Coverage
Target Coverage
Figure 5: The plot the right replicates experiment (Huang et al. coverage rates for the Cora_ ML dataset (a subset of the Cora dataset) for both CFGNN and baseline model. The plot on the left uses APS with randomization when constructing the final prediction sets. These plots illustrate the benefits of using randomization on baseline performance.
2023
plotting efficiency various
jourrandomized
cfgnn_aris orig
cfgnn_aps
aps_ rendranddeieedd
cfgnn_orig
cfgnn_aps
Amazon_ Computtsss
Amazon_Computers
Amazon, Computers
Coauthor_co
Coauthor
dalaset
dataset
Cora
Flickr
Flickr
agbn-arxiv
ogbn-anxiv
5
10
10
20
efficiency
efficiency
Figure 6: Bar charts denoting efficiency for 'efgnn aps', 'cfgnn _orig, and gaps_randomizer for the FS split (left) and LC split (right) at a = 0.1. We see that 'cfgnn aps' improves or matches efficiency in most cases.
full batch gradient descent for 1000 epochs. Our mini-batch implementation achieves comparable efficiency within 50 epochs without any batch size tuning (we set the batch size to 64 for consistent comparison) cache the output probabilities from the base GNN on top of the batched
shown in Table 2 Finally, implementation, reducing the runtime further. Table 2 compares the batching and the combined batching + caching improvements. Our implementation can achieve improvements ranging from 3.69x (ogbn-arxiv) to 20. 101 (Coauthor CS) in runtime over the baseline implementation ?
3.5. Summary of Key Insights For Graph Conformal Prediction. Tn Figure we present, overall comparison of the different methods on the Flickr dataset in terms of efficiency and label-stratified coverage (i.c., adaptability) using the full-split data partitioning style. Similar figures for the other datascts can be
We provide config files for the best. base GNN and CFGNN architectures attached cade for every dataset type.
10

---

Published in Transactions on Machine Learning Research (05/2025)
Table 2: Impact of different CFGNN implementations between the original, batching, and batching+cccching
Used the best CFGNN architecture (w..t. validation efficiency) for each dataset. We run trials for cach setup and report a 95% confidence interval. Amzn Comp Amazon Computers
method(-+)
original
batching
batching+caching
(Lt
Runtime
Efficiency
Runtime
Efficiency
Runtime
Efficiency
Aman Comp
664.98 + 10.90
1.29 + 0.05
205.29
3.96
1.15 0.01
73.85
1.56
1.14 + 0.01
Cora
1378.01
13.35
6.81 + 1.07
203.61
2.52
8.34
1.12
73.60 + 1.53
7.96 + 0.59
Coauthor CS
638.56 + 6.14
1.10
+ 0.01
88.49
+ 1.14
1.15 + 0.01
31.67 + 0.53
1.14 + 0.01
Flickr
868.87
9.98
4.23
+ 0.07
567.39
6.50
4.23 + 0.04
56.71 + 1.30
4.24 + 0.03
ogbn-arxiv
410.91 + 8.29
7.07 + 0.05
373.19 + 3.64
7.28 + 0.06
111.38 = 1.95
6.91 + 0.01
found Appendix The following sections will analyze some of these methods more detail, while a discussion on others can be found in Appendix
aps
daps
sps_classwise
naps_ eepsseexpentall
aps_rame randomizzed
dtps
gaps_uniform
raps
cfgnn_aps
tps
@aps_hyperbolic
Flickr
label, stratified coverage
0.8
efficiency
0.6
0.0
0.1
0.2
0.3
0.4
0.1
0.2
0.3
0.4
alpha
alpha
Figure 7: Efficiency (left) and Label Stratified Coverage (right) for all the conformal methods for the Flickr dataset. This uses the FS split style with multiple values for The dashed black line indicates the desired label-stratified coverage. Other NAPS variants (i.e., exponential, hyperbolic) are discussed in Appendix C
We analyze several general and graph-specific CP methods proposed the recent literature for transductive node classification. Based on our theoretical, empirical, and methodological results, we encourage practitioners to be precise and careful when developing and evaluating conformal prediction methods for graphs. We analyze the efficiency of all the methods considered in different datasets. Some key insights report include:
TPS is Efficient. TPS is consistently the most efficient method for cach dataset, regardless of the data split. However, this often comes a to adaptability, shown in Figure for the Flickr dataset.
TPS- Classwise a viable baseline. While TPS provably optimal for efficiency, the classwise version has largely been ignored in the literature as a bascline. Our results demonstrate that TPS-Classwise achieves label-stratffied coverage stemming from its classwise quantile procedure making it an 'adaptive' method that is a competitive baseline. This adaptability usually comes at small cost to efficiency, though this is not the case with all datasets (see PubMed in Figure E5
Diffused Classwise TPS. We also explored an alternative to classwise TPS where we apply the diffusion operator from Zargarbashi et al. (2023) on top of the 'adaptive' TPS-Classwise discussed earlier. As with
11

---

Published in Transactions on Machine Learning Research (05/2025)
other datasets, DTPS also provides label-stratified coverage for Flickr (sce Figure 7 More discussions DTPS and Diffusion Adaptive Sets (DAPS) (Zargarbashi et al. 2023 can be found in Appendix C.1
APS with randomization is provably more efficient than APS without randomization and should be the default setting for future evaluations involving APS. From Theorem 2.3 we observe that the randomization term in APS Randomized decreases the incorrect label scores substantially less than the conformal quantile, meaning these incorrect labels are less likely to be included when constructing the prediction set, therefore improving efficiency. This result is further pronounced for datasets with many classes because most incorrect labels shift less than the correct label, suggesting that APS Randomized should be a default baseline in the future.
NAPS provides a balanced tradeoff (and applies to the non-exchangeable setting). Using the NAPS (Clarkson 2023) scoring function achieves a balance between efficiency and label-stratified coverage. Before computing a quantile, NAPS uses neighbor distances to assign weights to non-conformity scores. In the original paper and our implementation, NAPS has a hyperparameler k, which is the maximum distance considered when assigning a weight, and everything beyond that is given zero weight. A unique characteristic of NAPS is that it is the only method discussed that provides guarantees for the non-exchangeable setting. More details on NAPS and its variations can be found in Appendix Appendix y has similar plots for the other datasets.
Randomization in CFGNN. As noted in Figure 0 randomization within the inefficiency loss function can improve the efficiency of the original CFGNN implementation, particularly for datasets with many classes (e.g., Cora). It is also worth reiterating that the perceived efficiency gains of the original CFGNN are not as significant compared to APS with randomization (see Figure
Scaling up CFGNN. We reimplement CFGNN using batching and caching to scale the method for larger graphs (e.g., ogbn-arxiv). We observe runtime improvements (see Table 2 and, in some cases, batching with caching is the only method that can run CFGNN (c.g., ogbn-products in Table Clab Moreover, Figure i shows that APS Randomized is slightly less efficient than CFGNN without the same computational demands. Thus, scaling makes CFGNN more viable for settings with limited resources.
Impact of Label Distribution. We observe that the dataset's label distribution impacts the difference in adaptability between TPS and TPS- TPS-Classwise. In Figure [ we find an increase in the adaptability of TPS when using LC split instead of FS split for ogbn-arxiv compared to Amazon Computers. The shift in performance is exacerbated when many classes have little representation (highly imbalanced), as seen in Figure 2 The difference in adaptability is also observed in other non-conformity scores and is particularly pronounced for the products dataset (see Figure D1
Incorrect label miscoverages are important. Conformal prediction is concerned with the true label miscoverage; however, since prediction sets also include incorrect labels, the miscoverage levels of incorrect labels are important to account for when considering method's efficiency. With Theorem 2.3 we prove that sufficient condition for when CP method is more efficient than another method depends the incorrect label miscoverage. Theorem 2.3 applies to other domains outside the graph space. We also see in Corollary 2 that the incorrect label miscoverages determine how much the efficiency improves with large calibration sets. This improvement is pronounced for datasets with many classes.
The Benefit of RAPS is not as significant for Transductive Node Classification. In the general CP literature, RAPS has demonstrated improvements to (prediction) efficiency over APS consistently, however, these same improvements aren't as evident for graph datasets seen in Figure / where RAPS does not beat out APS Randomized in terms of (prediction) efficiency. Similar results for other datascts can be found in Appendix E and Zargarbashi el al. (023)
To conclude this analysis, if computational resources are not a limiting factor, CFGNN with the appropriate loss functions (c.g., APS randomized) has demonstrable success improving efficiency, while being comparable to other methods in terms of adaptability. When deciding which method is more efficient in general, Theorem 2.3 can be applied to the calibration set to determine this prior to deployment. If
Guidelines.
12

---

Published in Transactions on Machine Learning Research (05/2025)
adaptability is critical, then methods such as TPS--Clsswist and DTPS are both viable and the only methods that provide a guarantee while not being as computationally expensive. APS and APS Randomized are good middll-ground methods, and NAPS is the only method that provides guarantees for non-exchangeable settings. Lastly, we provide a Python library 2 which can be used to implement these methods.
4 Concluding Remarks
We present a comprehensive benchmarking study of conformal prediction for node classification. We provide novel insights related design choices that impact efficiency, adaptability, and scalability. Along the way, we offer new theoretical rationale for the importance of randomization and discuss improvements and directions for future work. One future direction pertains to the space of fairness auditing. Several works have dealt with the auditing fairness of ML models through measuring uncertainty in fairness definitions (Ghosh et al. 2021 Maneriker et al. 2023 Yan & Zhang 2022), but they rely on the assumption of IID. While conformal prediction works with the notion of miscoverage, more relevant notions of error can be considered using the generalized framework of conformal risk control (Angelopoulos al. 2024
novel methodological
Acknowledgments
The authors acknowledge support from National Science Foundation (NSF) grant #2112471 (AI-EDGE) and grant from Cisco Research (US202581249). Any opinions and findings are those of the author(s) and do not necessarily reflect the views of the granting agencies. The authors also thank the anonymous reviewers for their constructive foedback on this work.
References
Moloud Abdar, Farhad Pourpanah, Sadiq Hussain, Dana Rezazadegan, Li Liu, Mohammad Ghavanzadeh, Paul Fieguth, Xiaochun Cao, Abbas Khosravi, U. Rajendra Acharya, Vladimir Makarenkov, and Saeid Nahavandi. A review of uncertainty quantification in deep learning: Techniques, applications and challenges. Inf. Fusion, 76(C):243 297, December 2021. ISSN 1566-2535. doi: 10.1016/j.inffus in006//iifffu..222..00. 2021.05.008. URL https://doi.org 10. 10.160000001111111 inffus 2021 05.055.008
Anastasios N. Angelopoulos and Stephen Bates. Conformal prediction: A gentle introduction. Found.
Trends Mach. Learn., 16(4):494-591 March 2023. ISSN 1935-8237. doi: 00.1561/2000001001. URL
https://doi.
Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncertainty sets for image classifiers using conformal prediction. In International Conference Learning Representations, 2021.
Anastasios Nikolas Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster. Conformal risk control. In The Twelfth International Conference Learning Representations, 2024.
Rina Foygel Barber, Emmanuel J Candès, Aaditya Ramdas, and Ryan J Tibshirani. Predictive inference with the jackknife+. The Annals of Statistics, 49(1):486-500) 2021.
Rina Foygel Barber, Emmanuel J. Candès, Aaditya Ramdas, and Ryan J. Tibshirani. Conformal prediction beyond bxchangeability. The Annals of Statistics, (1(2):816 845, 2023. doi: 10.1214/23-A052276. URL
https://doi.org org/ 10. 1214/23
Jase Clarkson. Distribution free prediction sets for node classification. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 6268 6278. PMLR, 23 23-29 Jul 2023. URL hta.tpp://proceediggs......eeee v205 clarkson23a. 1htmm
3Code: http::///....t..cccocoaomaoea/ar
13

---

Published in Transactions on Machine Learning Research (05/2025)
Ed Davis, lan Gallagher, Daniel John Lawson, and Patrick Rubin-Delanchy. Valid conformal prediction for dynamic CNNs. In The Thirleenth International Conference on Learning Represenlations, 2025. URL httpps//ppeeeerrrrrrr/e/c////tea werf
Bishwamittra Ghosh, Debabrota Basu, and Kuldeep S Meel. Justicia: A stochastic sat approach to formally verify fairness. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7554-7563, 2021.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pp. 1321 1330. PMLR, 2017.
Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using networkx. In Gaël Varoquaux, Travis Vaught, and Jarrod Millman (eds.), Proceedings of the 7th Python in Science Conference, pp. 11 - 15, Pasadena, CA USA, 2008.
William L Hamilton. Graph representation learning. Morgan & Claypool Publishers, 2020.
Hans Hsun Hsu, Yuesong Shen, Christian Tomani, and Daniel Cremers. What makes graph neu- ral networks miscalibrated? In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 13775 13786. Cur- ran Associates, Inc., 2022. URL ittps::/ neur.ss...........p... cc/paper 557775777760a0002000000222222222
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: datasets for machine learning graphs. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
Kexin Huang, Ying Jin, Emmanuel Candes, and Jure Leskovec. Uncertainty quantiffication over graph with cc/
conformalized graph noural networks. 36:26699-26777 2023. URL http///ss///pcccedinn..eeee
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. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Garnett (cds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL httpps:/
neurips. http:///ww....aaaoo.oooooooooooa
pdf
Richard Liaw, Eric Liang, Robert Nishihara, Philipp Moritz, Joseph E Gonzalez, and lon Stoica. Tune: A research platform for distributed model selection and training. arXiv preprint arXio:1807.05118, 2018.
Clémence Magnien, Matthieu Latapy, and Michel Habib. Fast computation of empirically tight bounds for the diameter of massive graphs. ACM J. Eap. Algorithmics, 13, February 2009. ISSN 1084-6654. doi: 0111445/111222.4455222 URL https://doi.
1145/1412228, 1455266
Pranav Maneriker, Codi Burley, and Srinivasan Parthasarathy. Online fairness auditing through iterative refinement. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, KDD '23, pp. 1665-1676, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400001030.. doi: 10. 01144/355803553599445 URL https://doi.. org/10 1145/3580005 3599454
Ariane Marandon. Conformal link prediction for false discovery rate control. TEST, 33 (3(4 1083, Dec 2024. ISSN 1863-8260.
doi: 10.1007/5117449-044-0939
URL htttps://doi.org/1000
811749-024-00934-w
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Imago-based recommendations on styles and substitutes. In Proceedings of the 38th international ACM SIGIR conference on research and development. in information retrieval, pp. 43 13-52, 2015.
14

---

Published in Transactions on Machine Learning Research (05/2025)
M. Newman. Networks. OUP Oxford, 2018 ISBN 9780192527493. URL attps://bbokss.googll books"'dd=Ya2DDAAADP
Jerzy Neyman and Egon Sharpe Pearson. On the problem of the most efficient tests of statistical hypotheses.
Philosophical Transactions of the Royal Sociely of London. Series A, Comlaining Papers of Mathemationl or Physical Character, (314 706) 222 337, February 1933. ISSN 2053-9258. doi:
URL http::/dx..oo doi. www. 1098/ rsta. 1909.0009 0009
Harris Papadopoulos. Inductive conformal prediction: Theory and application to neural networks. In Tools in artificial intelligence. Citesecr, 2008.
Harris Papadopoulos, Vladimir Vovk, and Alex Gammerman. Qualified predictions for large data sets in the case of pattern recognition. In M. Wani, H. Arabnia, K. Cios, K. Hafecz, and G. Kendall (ods.), Proceedings of the International Conference on Machine Learning and Applications, pp. 159 163. CSREA Press, 2002. Proceedings of the International Conference on Machine Learning and Applications, CSREA Press, Las Vegas, NV, pages 159-163, 2002.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. CoRR, abs/2002.05287, 2020. URL https://arxiy.. .rg/ abs/22022.00588
Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive coverage. Advances in Neural Information Processing Systems, 33:3581-3591, 2020.
Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, (14(525):223- 234, 2019.
Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network cvaluation. Relational Representation Learning Workshop, NewrIPS 2018, 2018.
David Stutz, Krishnamurthy Dj Dvijotham, Ali Taylan Cemgil, and Arnaud Doucet. Learning optimal conformal classifiers. In International Conference on Learning Representations, 2021.
Aditya T Vadlamani, Anutam Srinivasan, Pranav Maneriker, Ali Payani, and Srinivasan Parthasarathy. A generic framework for conformal fairness. In The Thirteenth International Conference Learning Representations, 2025.
Vladimir Vovk. Conditional validity of inductive conformal predictors. In Asian conference machine learning, pp. 475 490. PMLR, 2012.
Vladimir Vovk. Cross-conformal predictors. Annols of Mathemotics and Artificial Intelligence, 74:9 28, 2015.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algoritlomic learning in a random world, volume 29. Springer, 2005.
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft. Academic Graph: When experts not enough. Quantitative Science Studies, 1(1):396 413, 02 2020. ISSN 2641-3337. doi: 10. 10.1162/qss a_ 00020. URL https:///oo..or/100000 wwt.:/1122ssssee ___2221
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong Hc, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, highly-performant package for graph neural networks. ar preprinl NNiv:1909.0133 2019.
Xiao Wang, Hongrui Liu, Chuan Shi, and Cheng Yang. Be confident! towards trustworthy graph neural networks via confidence calibration. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 23768- 23779. Curran Associates, Inc., 2021. URL / httpo//nnnnnouris.cceeeeeeeee fitepp/prrtee//pperr/ p22/:hhhhhaaaaaaccee77777777r022
15

---

Published in Transactions on Machine Learning Research (05/2025)
Lingfei Wu, Peng Cui, Jian Pei, Liang Zhao, and Le Song. Graph neural networks. Graph Neural Networks: Foundations, Pronlãers, and Applications, pp. 27-37, 2022.
Tom Yan and Chicheng Zhang. Active fairness auditing. In International Conference on Machine Learning, pp. 24929 24962. PMLR, 2022.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40 48. PMLR, 2016.
Soroush H. Zargarbashi and Aleksandar Bojchevski. Conformal inductive graph neural networks. In The Twelfth International Conference on Learning Representations, 2024. URL
forum?id=han 100I5
Soroush H. Zargarbashi, Simone Antonelli, and Aleksandar Bojchevski. Conformal prediction sets for graph neural networks. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.). Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 12292 12318. PMLR, 23 29 Jul 2023. URL
petts::/prrceeedin mlr. ppess/v202/1 wawgaraasggaaaaaaaaa.aaaaaaaaa http:///////////rararaaaaaaaaaaa html
Soroush H. Zargarbashi, Mohammad Sadegh Akhondzadeh, and Aleksandar Bojehevski. Robust yet efficient conformal prediction sets. In Forty-first International Conference on Machine Learning, 2024. URL
Hanqing Zeng. Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. GraphSAINT: Graph sampling based inductive learning method. In International Conference Learning Representations, 2020. URL https:// htt.ppppwerriiio.oooooooooooooaa
Tianyi Zhao, Jian Kang, and Lu Cheng. Conformalized link prediction on graph neural networks. In Proceedings of the 30th ACM STGKDD Conference on Knowledge Discovery and Dala Mining, KDD '24, pp. 4490 4499, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400704901. URL attps://dol org/10. 110..144/363758 36720661
doi:
16

---

Published in Transactions on Machine Learning Research (05/2025)
A Optimal for APS
The most popular bascline in the graph conformal prediction literature is Adaptive Prediction Sets (APS). Rooaao et al. 2020) introduces APS by defining an optimal prediction set construction mechanism under oracle probability. Suppose we estimate prediction function f that correctly models the oracle probability Pr[Y = Xest = = = (x)) for each E E in descending order. For any т E [0, 1], define the generalized conditions ional quantile funciton al 7 as
Let (z)) (()(()) be the sorted probabilities
& L(x; n, min E (1..... K}.
Σ j=1
(T) 27
(5)
The corresponding prediction set, (x)) is constructed as
Ca (a: = (u E y (y(a)) 2 [((0=x1--))
where or indicates the usage of the oracle probability. Further, they define tighter prediction sets a randomized fashion using an additional uniform random variable u Uniform(0,) 1) as a parameter construct a generalized inverse. This idea draws upon the idea of uniformly most powerful tests the Neyman-Pearson Pearson lemma for level-a sets (Neyman & Pearson 1933). Define
{u E V (2) )( (x)) u < V(a;T,T)
5(o,
(6)
{vEy) :/ (xx 2 T(((mn))) (x)) otherwise
T.e., the class at the TT rank included in the prediction set with probability 1 - (a;;t, where
{[
{
[(w:n,7)
V(=: ((L(=)),)))
Σ
(T)(Z)
The corresponding randomized prediction sets are (x) S(x, Ui U (O0, Note, the coverage guarantees provided in conformal prediction hold only in expectation over the randomness in (x,, M)) i 1,..., + 1. The randomized prediction ion sets continue to provide the guarantee with additional randomness over u, To make this work for non-oracle probability f(x),, they define a non-conformity score
A
A(x, y, ft = min(r E [0,1]: ry u(
Assume that â are all distinct, for ease of defining rank. Suppose the rank the true class amongst the K sorted be ry. i.c. Σ (x) 2 ; = Solving for T as function of á (sce Appendix for proof),
A(x, y, u)
Σ (1) un
(8)
Instead, if deterministic set is used to define the conformal score instead (i.e., the randomized set construction is not carried out), then we could add the probabilitics until the true class is included:
Á(æ, f)
Σ + (x)
(9)
This version of APS still provides the same conditional coverage guarantocs and has a simpler exposition, as the prediction are constructed by greedily including the classes until the true label is included. Thus, this version is implemented in the popular monographs conformal prediction (Angelopoulos & Bates 2023
17

---

Published in Transactions on Machine Learning Research (05/2025)
However, the lack of randomization may sacrifice efficiency. This modification of the score function affects both the quantile threshold computation during the calibration phase and the prediction set during the test. phase, We will now show the conditions that impact the efficiency more formally. For simplicity, assume that the probabilities are distinct.
From the definition of A equation
A u. = e
E [0, : S(æ,
Define
m
(x m)
Σ ( (a)
From the definition of S(x,, u; R) from equation 6 conisder the following cases:
Case 1: T= Ex(x, rw), then L(,;f,,)) r) = y and thus, TT) 0. Thus Pr/u > V(a r)] = 1 and hence, Ply E (( =
Case 2: T (x, ryy 1), then y E S(x, u, f) in either case, since only classes with (; (y(x) could be included.
Case 3: 2' (2x, ry) sat. Then we have (xx;t, 7) y again, and
V(
Σ (x)
-
Fy (x)
(x)
(a)( sty)
Ry (a:)
For y to be included in S(æ, u; f. T), would require that u 2 (,; ie., u 2 We want the minimal T (or the maximal E). Thus, = (x) - uny is the required solution.
A.1 Non-randomized set
The inclusion criterion for the score given the threshold 7 is vip) ST ST
To include the correct label y while minimizing the chosen threshold we would require Σ (x)
18

---

Published in Transactions on Machine Learning Research (05/2025)
B Proofs
B.1 Proof of Theorem 2.3
For sclf-containment, we will restate some of the notation used in proving Theorem 2.3 Let A(x, y) be any non-conformity score function and
[(n + 1)(1 a)], (
i = Quantile
n
Define Ar(v) == A(x,; y) where y and C% Ca(x,) for brevity. Let 3 = 3 {iu be the set of incorrect labels and 1/ E 3% be any incorrect class label for each 2;s We can consider the exchangeable sequence {A(,; y/ ) where vf denotes a randomly sampled from V, and define a² E [0, 1] such that:
[In 1)(1 - -)((1=a"))) {A(a,, "( v()1
4 Quantile
(10)
Particularly, if we set À = 4A in the following lemma, then we can compute a. En 1(A(ws.))) )=de))"))+++++ to satisfy the guarantee given in Equation 4
Lemma B.1 (Vadlamani et al. (025 ). For X E [0, and (Dauubl, let Cx(x) {u E ): s(x, A Then,
Dm [ss y:) > Al
E 1[s( ( Ui) Al +1
Pr(jnti & C2(xn+1)) S
(11)
1
+1
On the exchangeability of {A(x,, y To understand why (A(o, yf B is exchangeable we first consider Lemma B.2
Lemma B.2. The random variable vf U(!).
Proof. To prove the lemma, we will show that the PMF that Vl,(.))) follows is identical to U(?) Lot y be an arbitrary label in V. First observe for yd (V!) that Pr(y v/l R-T because it is uniformly sampled. Now consider via the law of total probability,
Pr(v),(w.) = v/1 =
Pr(v),(.)) 1/luu Pr|m: []
Pr|M = vil Prrlu,
1
Pr|s/,0) = 1/l K
=
Pr(vk. vll
K
Sum of PMF
1
K
K-1
(12)
Thus, the PMFs identical and of U(Y)..
19

---

Published in Transactions on Machine Learning Research (05/2025)
Recall (z); V1 assumed to be exchangeable, thus (x);) 2+1 must also be exchangaable since ) is the complement of {us}- Lastly, consider an ITD sequence U(1....., K 1}) for i = 1,..., n + 1. Since 1 is IID, we can adjoin it to the covariates and produce an exchangeable sequence of triples [u]h=]
n+1
(z,, V u))==
m+
From this exchangeable sequence, we can compute the non-conformity scores, and (fA(z,, 1/4 1/ Vi u Lastly, to get pointwise representative for each set, let y Vi(a,) such that A(x,, Vi(1)) I A(a (2) I ... S A(z ((( assuming there is a suitably random tic-breaking method for identical scores. Then, {A(x, of"h H necessary. However, it concretely demonstrates the procedure to form {A(z,, ) ensures the sequence is exchangeable where vffh ~ U(?)) using Lemma B.2
is an exchangeable sequence. In practice, the process of ordering the 3 labels is not
Now, we will prove Theorem
2.3
Theorem 2.3. If a - -a 2 (m+1)
2
then score function A produces a more efficient prediction set than A.
Formally, E [[[41( [Ca (2
Proof. Let Cia- Ca(x,) for brevity, First consider, E E| []
E
C|
E
1y 1/y E 1 Σ MEY
E [1[vn+1 E CCt +E
Σ
1|24 E c
W EYa
=E [E E Cxtl]]+ +
Σ
E
[1 E ECat1]]
Vo-IEV
= Pr[yn+1 E C
Σ
Pr|ya4t E c
(13)
Vo+IEV.
Now using Lemma B.2 we have that y1th ~ U(%). Then, using the law of total probability and the fact that label is in C*+1 iff A(xn+1.8)) QA:
Pr|A(ex+1,, v S 9
Σ
Pr[A(an+is witz) S Quluit1 shuall Pr(yntt = shutl
Σ
P[(A(an+isaan S 9n] Pr[yati = whttl
Vht E.I.
Σ
Pripa+i E P = Vn-1l
Vn+1 E.Y.
Σ
Pr E &CatT].
K
Vo+ EV
(K - Priy E c
Σ
Pr(yh41 E CCat1)
(14)
b. ED
Then substituting Equation
into Equation 13
we arrive at,
E S[[c++1 [] Pr(ya41 E CCtt) +K Pr E CAt1)
(15)
20

---

Published in Transactions on Machine Learning Research (05/2025)
Then we compute upper bound and lower bound for E B|(c**1) []]
E| E| S 1 a+ +
n n+1 + (K 1)
1
11-
+
1
n +1
K
= =1- - a + (K 1) (1 a²¹) +
n2 n+1
and
E| c a (K 1) (1- -
(16)
similar bounds can be derived for E c=+1 Thus,
c + | - 1c 1
2 (1-a+ (K 1) (1-a!)) - 1 (K -1
K
n2 + 1
lower bound for B
8[(cxt]) []
upper hound for 12|(02 ||att11 []
K
(K - 1)
a
1
a
(K 1)
a
ac
A
K
(K 11m+1 +1
2 (K - 1)
a
ag
1
2
20
(17)
n + 1
with the last inequality holding because og
a
2
2
This completes the proof for the general case.
m+I
21

---

Published in Transactions on Machine Learning Research (05/2025)
B.2 Proof of Corollary 2.3.1
Corollary 2.3.1. As n + 20, [ (xx+ 1)1 - -CC = (K -1) (a - -at)
Proof. Observe using Equation
17 E
A
1 - |Ca
(K - -1) (at - ar² m+t)
Similarly by swapping
A and A:
2
cc ca+1 - -0
2 (K - 1)
a
0
11 +
Cn+t| ca |
$ (K - 1)
oe
A
2
n
+
|cc +1 |Ca
|
converge to (K-1) (a. - -a.)
Then observe as n + oo both the lower and upper bound of
Thus E ||ctt1 - |cx+1| | = (K 1) (a az
0
22

---

Published in Transactions on Machine Learning Research (05/2025)
C Method Details and Innovations
C.1 Diffusion Adaptive Prediction Sets (DAPS)
The Diffusion Adaptive Prediction Scts (DAPS) approach for conformal node classification on graphs was roducee by (Zargarbashi et al. 2023). The intuition behind DAPS follows the prevalence of homophily graphs, which suggests that non conformit scores for two connected nodes should related. DAPS uses a diffusion step to capture this relationship and uses the non-conformity scores modified by diffusion generate the prediction sets. Formally, suppose s(v, y) point wise non-conformity score for node v and label (e-g., TPS APS)
s(u,y) = ()) + Well uEN,
A
Σ s(u,y)
where N₂ is the 1-hop neighborhood of v and X E [0. is hyperparameter controlling the diffusion.
Zargarbashi et al. 20233 uses the APS score as the point-wise score in the diffusion process, as it is adaptive and uniformly distributed in [0, 1] under oracle probability. However, as noted earlier, using classwise thresholds provides a mechanism produce adaptive scores from TPS. Thus, we create DTPS, variation of DAPS using TPS scores the point-wise scores in the diffusion process.
We compare our proposed method of using diffusson lop of CTPS-Classwise (DTPS) against DAPS, which was proposed by ZZrgarbashi et al. [0023]. From Figure CT (left), we see that DTPS can be competitive with DAPS in efficiency while providing better label-stratified coverage. However, for some of the larger datasets (Cora, Flickr, ogbn-arxiv, agbn-products), DTPS suffers from poorer efficiency compared to DAPS. This can partially explained by the worse performance of the pre-diffusion TPS-classwise (Figure E2 which is
forced to sacrifice efficiency on these datasets to achieve label-stratified coverage (Figure E1
However, when control the number of samples per class with LC splits (Figure C1 right), see that DTPS label stratified coverage deteriorates significantly compared to DAPS. Based on these results, we can conclude that DTPS is not universally better method than DAPS, and its performance is sensitive to the calibration set size and the number of classes. It may be viable candidale over DAPS in scenarios when there is a sufficiently large calibration set, which is when cassclasswise has competitive efficiency to TPS.
23

---

Published in Transactions on Machine Learning Research (05/2025)
daps
dips
Amazon Computers
efficiency
coverage
straaifidd coverage
0.0
0.2
0.6
1.0
Amazon Photos
efficiency
coverage
label_strase aere__sraaffeed_ceeeeeeeee
0.0
0.2
0.4
0.6
0.8
1.0
1.2
1.4
0.0
0.5
1.0
1.5
2.0
value
CiteSeer
efficiency
coverage
gaal_stracifedd_ooe coverrgg
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5 value
2
2.5
va
Coauthor_co _CS
officioncy
coverage
abee__sracifled_cooeeleee coverage
0.0
0.2
0.6
1.0
1.2
0.2
0.6
0.8 value
1.2
vaa ue
Coauthor Coayshor_Physics
efficiency
coverage
[tbe__stratffeddccom coveragge
value
value
Cora
efficiency
coverage
beeel_straiifeeddcoooo coverage
8
10
Flickr
efficiency
coverage
label_ sttelssstiiiiedeecco coverage
3
5
6
value
value
PubMed
efficiency
coverage
label saal__sracfied__eom
0.0
0.2
0.4
0.6
0.8
1.0
0.00
0.25
0.30
0.75
1.00
1.25
1.50
value
value
ogbn-arxiv
efficiency
coverage
abaa__traciffed_cooeeeee coverageeeeeeeeeeeeeeee
value
value
ogbn-products
efficiency
abbe__sraaiifeddcoooe coverage
value
value
Figure C1: Bar charts denoting different. metrics associated with DAPS and DTPS across all datasets for FS split (left) and LC split (right) at 0.1.
24

---

Published in Transactions on Machine Learning Research (05/2025)
C.2 Notes on Transductive NAPS
Neighborhood Adaptive Prediction Sets (NAPS) constructs prediction sets under relaxed exchangeability (or non-exchangeability assumptions [Barber et al. 2023 and was initially implemented for the inductive setting [Clarkson 2023). However, NAPS can also be used in the transductive setting (Zargarbashi et al. 2023). To compute scores for Dealib nodes, NAPS uses APS. Using these scores, Equation 18 is used to compute a weighted quantile for the score threshold to be used when constructing the prediction sets. The weighted quantile is defined by placing a point mass, da. for each calibration point's score, 8/1 as well as a point mass 00 to represent the test point, Un+1's ss, score. The point mass at 8420 is needed because the score for un+1 is unknown, and polentially unbounded, due to non-exchangeaaillty
NAPS h++1
Quantile
1 a-a, Σ
Wy dos + Øn+1 0+00
(18)
LiE
For NAPS to produce viable prediction sets, the weights, w; E [0, I]; for the calibration nodes must chosen in dadeenndenn fashion, i.e. they cannot leverage the associated node features (Barber et al. 2023 NAPS leverages the graph structure to assign these weights, assigning non-zero weights nodes within a k-hop neighborhood, N of a test node tn For nodes that in N let d, be the distance from the node lo Un+1 to E Vealib. The three implemented weight. functions are uniform: wa(d,) [d, < k), hyperbolic: (d:))) = d; [d, S k). and exponential: w. (d+)= 2 2- 1(s S k). The weights are then normalized, ú; such that EieD,m úh + Wn+1 =1 (Barber et al. 2023
NAPS Implementation NAPS is computationally expensive terms of time and memory since the k-hop intersection is computed for each test node. To allow for scalability, our implementation of NAPS, uses batching to ensure sufficient memory is available and uses sparse-tensor multiplication to reduce memory and time costs.
shown in Algorithms ! and 2
To ensure scalability for large graphs, all the computations until the quantile computation step were done via sparse tensors. Algorithm illustrates how the distance to each calibration node in the k-hop neighborhood can be computed via sparse tensor primitives.
Algorithm NAPS Quantile Implementation
procedure NAPS QUANTILE(W, (w, k. Dealib, Deesi D. Sealih, b, a) (BI, B2,..,, Br} t SPLIT(Drest, b)
Split test nodes into b batches
9 + ZEROOS(Deest 1)
R PPeall
4: for B, {Bi, B2...., B.) do
5: k hop +- SPARSE_ K. _HP(K, B,, Dealib. D)
> k hop E B |x/, b weights E B 12 Pean
6: weights + COMPUTE WEIGHTSS(W, k hop)
7: (BB,]] +- COMMUTEE_QANTTLLLS - a, Seaghts,Seallb)
end for return q 10: end procedure
Return the quantiles for each test node
25

---

Published in Transactions on Machine Learning Research (05/2025)
Algorithm Sparse K Hop Neighborhood Implementation
procedure SPARSE K HOP(k, B, Dealib: D)
2: A <- GET ADJACENCY(D)
D Adjacency of D, A E RR D
3: path n + :
b path E | k hop E | Palib
4: k khhpp f- path path_al::22 Deatib]
5: for n E 32.3...., k} do
path - (path_ n)A neg if 4 k hop (pa( n|; Pealib)) in hop t (neg if n < 0) x n
negative value - hops away P Nodes that are min distance of n
k hop k hop in hop
10: end for
11: return k hop
D Vey If dist < k then k hopli, 3) = dist((t, else k hop[i,j] = 0
12: end procedure
Parameter Analysis: Apart from the particular weighting function, the main parameter in the NAPS algorithm the number of hops to consider, k. Figure C2 shows the trend between efficiency and coverage we increase & from 1 to D, where D is lower bound the diameter of the largest strongly connected component of the dataset, computed using the NetworkX Hagberg et al. (008). For each dataset, we observe value of k after which the efficiency does not improve, while still achieving the desired coverage. This behavior can suggest a heuristic akin to the 'elbow method used in clustering analysis to determine the number of clusters for choosing the value of NAPS.
26

---

Published in Transactions on Machine Learning Research (05/2025)
naps uniuurfffr
expeeeeenetiall
Amazon Computers
0.96
coverage
0.94
efficiency
0.93
0.91
0.89
6
k
Amazon Photos
5.0
0.97
4.5
0.96
4.0
0.95
effiiencyy
3.5
0.91
0.93
2.5
0.92
2.0
0.91
1.5
1.0
0.89
K
CiteSeer
1.00
0.99
0.98
effidincy
5.0
0.97
0.96
4.5
4.0
0.94
0.93
3.5
5
10
15
20
25
10
15
20
k
Coauthor CS
1.00
14
12
0.98
10
efficiecy
coverage
0.94
0.92
0.90
5
10
15
20
5
10
15
20
Figure C2: Plotting the Efficiency and Coverage when using NAPS for & from D. The above results are with FS split and 0.1.
27

---

Published in Transactions on Machine Learning Research (05/2025)
uniifom
nap=_hy hyp.hpprrrllcccccc
exp.oneniiool
Coauthor Coauthor_Physics
4.5
4.0
3.5
3.0
coverage
2.5
2.0
1.5
12
16
2
12
k
K
Cora
70
60
0.98
50
coverage
0.96
40
0.94
30
0.92
20
10
0.90
10
20
10
15
20
Flickr
7.0
1.00
6.5
coverage
5.5
5.0
0.92
0.90
4.0
0.88
2
3
4
5
2
3
k
k
PubMed
1.00
2.50
2.25
coverage
0.96
2.00
0.94
1.75
1.50
0.90
10
12
10
12
14
16
ogbn-arxiv
40
1.000
0.950
30
25
0.900
0.875
0.850
15
0.825
10
40
Figure C2: Plotting the Efficiency and Coverage when using NAPS for k from to D. The above results with FS split and 0.1 (cont.). The ogon-products datasct is omitted due size and lack of data points. 28

---

Published in Transactions on Machine Learning Research (05/2025)
C.3
Conformalized GNN
C( =(1,2,4)
11I
Base GN Na
Conformal GNN,
GNN,
ONN
ONN,
|
(1 - 8) coverage
OKA
Development
Leffieimac
Base model training
Topology aware CF-GNN training
Conformal Prediction
Figure C3: Procedure for training CFGNN. First (left), the base model is trained on the training set. Then, (middle) CFGNN trained to maximize efficiency over the calibration set. Finally, (right) the non-conformity scores from the combined models used to generate the prediction sets.
Huang et al. (0223 introduces CFGNN conformal prediction method specific for graphs. Figure shows the end-to-end CFGNN procedure split into three steps. The first is to train base GNN model, GNN,, on the development nodes, Vdev, normally using label-based loss function such as Cross Entropy Loss. Using the outputs of GNN, as inputs, a second GNN, GNN,, trained using an efficiency-based loss function proposed by Huang al. (2023). Equation 19 presents the elficiency-based loss function for node classification, where a is the sigmoid function and
C3
temperature hyperparameter. The calibration nodes, Vealib, split into two sets, Veor-cal and Veur-test for training and validation, rospoctively. The fully trained GNN, is then used for the conformal prediction and prediction set construction.
n DiffQuuntilee( (s(x,, (x),, (1 a) (/ooocr)))l))
s(x,,, k) - -
Less |eor-call VEVeor-eat key
Σ Σ
(19)
Impact of Inefficiency Loss: Figure comparcs the efficicncy of 'cfgnn 'cfgnn_aps" aps', 'cfgnn_orrs orig,' and "aps_rrai rop__randomized for all the other datasets. For the FS split, we see that 'cfgnn_ayy aps" improves upon "efgnn__or orig' for all datasets and can improve upon 'aps randomized" for most datasets. We that CFGNN is still quite brittle for all datasets for the LC Split. CFGNN can still improve upon 'aps randomized" for datasets with larger number of classes, seen with Cora and ogbn-products.
present the runtime improvements (see Table Cla) as well as the efficiencies (see Table Clbp for each CFGNN implementation using the best CFGNN archilecture found through hyperparameler luning (see Section D4). We observe that our improved implementation achieves comparable efficiency to the original in only 50 epochs opposed to 1000 used in the original.
Scaling CFGNN:
Expanding on Table 2 from Section 3 Table CI
29

---

Published in Transactions on Machine Learning Research (05/2025)
Table Cl: Impact different CFGNN implementations between the original, batching, and batching+caching Used the best CFGNN architecture (w.r.t. validation efficiency) for each dataset. We run trials for each setup and report 95% confidence interval. OOM Out of Memory
(a) Impact Runtime
dataset(() / method(-+)
original
batching
Batching-ccchhnng
CiteSeer
379.28 + 9.36
36.36 0.97
27.45 +:2 0.80
Amazon Photos
496.36 + 4.92
102.92 + 0.95
54.44 + 1.36
Amazon C_mp_ttom
664.98 + 10.90
205.29 + 3.96
73.85 + 1.56
Cora
1378.01 + 13.35
203.61 = 2.52
73.60 + 1.53
PubMed
571.60 + 12.09
219.63 + 5.23
109.68 + 1.64
Coauthor CS
638.56 + 6.14
88.49 1.14
31.67 + 0.53
Coauthor Physics
5942.30 176.90
3918.38 17.16
1585.26 6.84
Flickr
868.87 + 9.98
567.8 6.50
56.71 + 1.30
ogbn-arxiv
410.91 + 8.29
373.19 19 + 3.64
111.38 + 1.95
ogbn-products
0OM
OOM
8709.16 + 55.00
(b) Impact on Efficiency
dataset(4) method(-)
original
batching
batching+
CiteSeer
2.52 = 0.27
2.45 + 0.19
2.42 + 0.37
Amazon Photos
1.06 = 0.01
1.06 + 0.02
1.12 + 0.02
Amazon Computers
1.29 = 0.05
1.15 0.01
1.14 0.01
Cora
6.81 1.07
8.34 + 1.12
7.96 + 0.59
PubMed
1.17 0.00
1.16 0.00
1.17 = 0.00
Coauthor CS
1.10 0.01
1.15 0.01
0.01 1.14 0.01
Coauthor_ Physics
0.97 = 0.01
1.01 0.03
0.99 0.01
Flickr
4.23 = 0.07
4.23 + 0.04
4.24 + 0.03
ogbn-arxiv
7.07 = 0.05
7.28 + 0.06
6.91 1 0.01
ogbn-products
00M
00M
1.86 0.06
30

---

Published in Transactions on Machine Learning Research (05/2025)
randomized
cfgnn_orig
cfgnn_en aps
aps_ ranadomizzeddd
cfgnn_orf orig
cfgnn _pps
Amazon_
Amazon_Computen Computers
Amazon Amazon_Complinn Computers
Amazon_ Photos
Amazon_ Shazto
CiteSeer
CiteSeer
Coauthor_CS CS
Coauthor_et __
dataset
Coauthor Physics
dataset
Seauthor_Physicce
Cora
Cora
Flickr
Flickr
PubMed
PubMed
ogbn-arxiv
ogbn-arxiv
ogbn-products
ogbn-products
5
10
10
20 efficiency
efficiency
(a) FS split style
(b) L.C split style
Figure C4: Bar charts denoting efficiency for 'cfgnn orig', and 'aps randomized' for both split styles at = 0.1. We see that 'cfgun aps' improves matches efficiency in most cases.
31

---

Published in Transactions on Machine Learning Research (05/2025)
D Datasets and Hyperparameter Tuning Details
D.1 Datasets
We selected datasets of varying sizes and origins to evaluate the performance of the graph conformal prediction methods. The first. calegory of datasets is citation datasels, where the nodes are publications and the edges denote citation relationships. Nodes have features that are bag-of-words representations of the publication. The task to predict the category of each publication. The citation networks we use are CiteScer (Yang et al. 2016), CoraFull (Shchur et. al. 2018), an exlended version of the common Cora (Yang al., 2016) citation network dataset, and Pubmed (Yang et al. 2016). The second category comes from the Amazon Co-Purchase graph (McAuley et al. 2015 where nodes represent goods, edges represent goods frequently bought together, and node features are bag-of-words representations of product reviews. The task is to predict the category of a good. We use the Amazon Photos and Amazon Computers datasets. The last. category is co-authorship networks extracted from the Microsoft Academic Graph (Wang et al. 2020 used for KDD Cup' '6. The nodes are authors, edges represent coauthorship, and node features represent paper keywords of the author's publications. The task is predict the author's most active field of study. We use Physics, which both come from the Microsoft. Academic Graph (Wang et al. 2020 Other datasets that were use include Flickr (Zeng et al. 2020), ogbn-arxiv, and ogbn-products Hu et al. (220)). These last three datasets have predefined splits for train/ train/validar validatt ion/test, shown in Table D2 which we used when constructing our train/vaer validationn callattiionaaabaattioo /calibration /ttoonttttttttt ttst splits for the different split styles. We
Coauthor_CC and
used the version given by the Deep Graph Library (Wang et al. 2019) for all the datasets. DGL uses an Apache 2.0 license, and OGB uses an MIT license.
Table D1 presents summary statistics for each dataset. These include the average local clustering coefficient (Avg CC), global clustering cocfficient (Global CC) (Newman) 2018). approximate lower bound the diameter (D) given by Magnien et al. (2009). node homophily ratio (H) (Pei et al. 2020), and expected node
homophily ratio (Hrand). Figure D1 shows the label distribution for each dataset.
Table D1: Summary statistics for all datasets evaluated.
Dataset
Nodes
Edges
Classes
Features
Avg CC
Global CC
H
Hrand
CiteSeer
3,327
9,228
6
3,703
0.141
0.130
28
0.722
0.178
Amazon Mnazon_Photoo
Photos
7,650
238,163
8
745
0.404
0.177
10
0.836
0.165
Amazon Commutters
13,752
491,722
10
767
0.344
0.108
0.785
0.208
Cora
19,793
126,842
70
8,710
0.261
0.131
23
0.586
0.022
PubMed
19,717
88,651
3
500
0.060
0.054
0.792
0.357
Coauthor CS
18,333
163,788
15
6,805
0.343
0.183
0.832
0.112
Coanthor Physics
34,493
495,924
5
8,415
0.378
0.187
0.915
0.321
Flickr
89,250
899,756
7
500
0.033
0.004
0.322
0,267
ogbn-arxiv
169,343
1,166,243
40
128
0.118
0.115
0.567
0.077
ogbu-producet
2,449,029
61,859,140
47
100
0.411
0.130
27
0.817
0.106
Table D2: Predefined splits from original source noted.
Datasct
# Train
# Valid
# Test
Flickr
44,625
22,312
22,313
ogbn-arxiv
90,941
29,799
48,603
ogbu-products
196,615
39,323
2,213,091
32

---

Published in Transactions on Machine Learning Research (05/2025)
Amazon Computers
35
30
25
20
15
10
Amazon Photos
20
15
10
CiteSeer
17.5
12.5
7.5
5.0
2.5
0.0
Coauthor CS
20
15
Coauthor Physics
50
40
30
20
Figure D1: Plots of label distribution for each dataset. Each class for each dataset has at least one occurrence.
33

---

Published in Transactions on Machine Learning Research (05/2025)
Cora
10
30
50
Flickr
35
30
25
20
10
PubMed
40
25
20
ogbn-anxiv
16
14
10
ogbn-praducts
25
20
15
10
20
Figure DI: Plots of label distribution for each dataset. Each class for each dataset has al least one occurrence (cont.).
34

---

Published in Transactions on Machine Learning Research (05/2025)
D.2 Hyperparameter Tuning
Hyperparameter luning done using Ray Tune (Liaw et al. 2018 The hyperparameters for the base model were tuned via random search using Table D3 for each model type (e.g., GCN, GAT, and GraphSAGE), for each datasct, except for the OGB (Hu et al. 2020) datasets, and cach splitting scheme (FS vs LC and different value settings). For the OGB datasets, we took the hyperparameters and architectures from the corresponding leaderboard for all splitting schemes.
Once we got the best base model for each dataset and splitting scheme, we tune the hyperparameters for the CF-GNN model via random search using Table D4 for each model type (e.g., GCN, GAT, and GraphSAGE), for each datasel [T For the F$ splitting schemes, we enfore [Dealib] = [Dtest] = (1 - DDeraill - (Dand ()/2. For the ogbn-products dataset, due to its size, we used batch size of 512 for the CF-GNN training and also used a NeighborSampler with fanouts [10, 10,5] rather than a Muttilayyrfullleeghooaaaapp
All experiments with the ogbn-products datasets were run on a single A100 GPU, while the remaining experiments for the other datasets run on a single P100 GPU.
Table D3: Hyperparameter search space for the base GNN model for non-OGB datasels. The last two rows are layer-type specific for GAT and GraphSAGE, respectively.
Hyperparameter Search Space
batch size
64
Ir
Dgguniform1101 10-1) [16, 32, 64, 128} (1,2,4) uniform(0.1,0..)
hidden channels
layers
dropout
heads
(2, 4,8) (mean, gen, pool, Istm)
aggr fn
Table D4: Hyperparameter scarch space for the CF-GNN model. The last rows are layer-type specific for GAT and GraphiAGEE, respectively.
Hyperparameter
Search Space
batch size
64
Ir
loguniform( (10-4, (1-11 (16, 32, 64, 128] (1,2,3, 4]
hiddon channols
layers
dropout
uniform 0.8)
loguniform 10a)
heads
(2, 428
aggr
(mean, gen, pool, lstm)
"The configuration files for all the experiments and best architectures available codebase: https://github.com pranasaaerrrre//gggggoooooommmm
35

---

Published in Transactions on Machine Learning Research (05/2025)
E
Additional Empirical Results, Analysis, and Insights
This section expands the figures and tables in the main body for all datasets considered. Figure E1 compares TPS and TPS-Classwise for all the datasets. We observe that TPS-Classwise achieves the desired label- stratified coverage of 0.9 while TPS doesn't necessarily for the FS split. For the T.C split, we observe that UPS-Classwise slightly improves on TPS in terms label-stratified coverage; however, neither method necessarily achieves the target label-stratifidd coverage. In Figure we find TPS-Classwise generally is less efficient than TPS for FS and LCC splitting. Figure p3 compares the label-stratified coverage for APS with and without randomization. We observe that randomization does sacrifice the label-stratified coverage for both FS and LC splitting, Noticeably, the change in coverage is smaller for the LC split. Figure E4 compares the efficiency of APS with and without randomization at a 0.1. For both split types (FS & LC), we observe that the randomized version of APS produces more efficient prediction sets, in line with Theorem 2.3 The efficiency improvements come with a sacrifice label-stratified coverage since smaller prediction set sizes are preferred over covering every class, particularly if the classes are rare. To visualize this trade-off, we observe that both Figure E and [X the difference in label stratified coverage for ogbn-productt with FS splitting is more extreme than with other datasets and with LC splitting. This is because ogbn-products has lot of classes that have almost representation (see Figure D1 Datasets with near-unilorm label distribution (e.g., PubMed, CiteSeer) or when using LC split, which controls for label counts we observe that label-stratified coverage isn't 't sacrificed as much in the name of efficiency.
36

---

Published in Transactions on Machine Learning Research (05/2025)
tps
pos_claswise
Split_Style FS
Split_Style LC
Amazon Computers
Amazon Photos
CiteSeer
Coauthor CC
Coauthor Physics
dataset
cora
Flickr
PubMed
ogbn-andiv
ogbn- products
0.5
0.6
0.9
1.0
0.4
0.5 0.6
0.8 0.9 1.0
label_ stratified_cooeragee
label label_ straatified_ooverrgee
Figure E1: Plots for TPS vs TPS-Classwise for all the data sets at a 0.9 coverage (green dotted line). TPS-Classwise, average, meets label-stratified coverage for FS split (left). For the L.C split, the label stratified coverage slightly improves with SPS-Classwise but does not necessarily meet the - coverage.
37

---

Published in Transactions on Machine Learning Research (05/2025)
tps
tps_ classwise
aps_ rs_raddddmizedd
Split Style = FS
Split Style LC
Amazon Computers
Amazon Photos
dataset
CiteSeer
Coauthor Physics
Flickr
+
+
PubMed
4
5
6
7
4
5
6
7
efficiency
efficiency
tps
cls_slassieee
aps randomizeed Split Style LC
Split Style
FS
Coauthor CS
dataset
Cora
ogbn-arxiv
ogbn-products
5
10
15 efficiency
20
25
30
0
5
10
15
20
25
30
efficiency
Figure E2: Plot for TPS TPS-classwise more inefficient compared to TPS for larger graph sizes, but is competitive in other settings. To maintain label-stratified coverage, TPS-classwis may be forced to overcover certain classes at the cost of elficiency.
0.1. For the FS split type, TPS-classwise becomes
38

---

Published in Transactions on Machine Learning Research (05/2025)
aps
aps_randomized
Split_Style FS
Split_Styles LC
Amazon Computers
Amazon Photos
CiteSeer
Coauthor CS
Coauthor Physics
dataset
Cora
Fllckr
PubMed
agbn-arxiv
ogbn- products
0.5
0.6
0.8
1.0 0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
label
Figure E3: Plots for APS APS Randomized for all the data sets 1 line). For the FS split type, APS-Randomized has lower label-stratified coverage. However, with the LC split type, the decrease in label-stratified coverage is not as significant.
0.9 coverage (green dotted
39

---

Published in Transactions on Machine Learning Research (05/2025)
aps
aps_ rasddindee
Split_ Style FS
Split_Style Style LC
Amazon Computers
Amazon Photos
CiteSeer
dataset
Coauthor Physics
Flickr
PubMed
2
4
2
efficiency
efficiency
aps
aps_ ran_omizdd
Split_Style = FS
Split_Style LC
Coauthor C5
dataset
Cora
ogbn-arxiv
ogbn-products
10
20
10
20
30
efficiency
efficiency
Figure E4: Plots for APS APS-randomized at a 0.1. For both split types (FS & LC), the randomized version of APS produces more efficient sets for all the datasets.
40

---

Published in Transactions on Machine Learning Research (05/2025)
E.1 Overall Results
In Figure E5
we provide plot of all the different methods discussed in this work for each dataset across different values of a. If applicable, for each method, we show the best-performing version, e.g., APS with randomization vs without and CFGNN with APS training ('efgnn aps") rather than TPS training ('efgnn_orti) _org"). We present the results for & = 5 for the different NAPS variations, since almost all datasets except for CiteSeer and ogbn-arxiv achieved their best efficiencies at or before that point.
Saps
Ips, rieeow on nape, on frem
Tape, exporeetis
rundomized
stpc
ctgnn, aps
up
nape, Soperbolic
Amazon, Computerss
8.8
0.5
0.2
5.
-lpha
Amazon Photos
3.5
266
stratfied
1.5
0.4
0.0
0.2
0.4
0.3
5.4
apha
atoha
1.0
emeleegy
0.6
0.4
Coauthor, CS
Sitelfeed AR
8.0
0.2
0.2
0.3
0.4
03
0.2
0.3
044
aihha
agpa
Coauthor Physics
entrerg
0.3
5.0
apha
3b5
Figure E5: Plots for efficiency vs a for all the major methods (with best parameters) across all the datasets (cont.). Among the baseline methods, TPS consistently has the best efficiency. The results are for the FS split style. The dashed black line indicates the desired label-stratified coverage.
41

---

Published in Transactions on Machine Learning Research (05/2025)
ap4
daps
tos classwise uniform
naps, exporeenial
randomized
efgnnnaap paps
tps
naps_ hyperbolic
Cora
Iabel strebifted coveroge
0.8
amiclency
0.6
0.4
0.2
0.0
0.1
0.2
0.3
0.4
0.1
0.2
0.3
0.4
alpha
alpha
Flickr
label stratitic coverage
effciinccy
0.0
alpha
alpha
PubMed
1.4
1.2
coverogge
0.9
1.0
officience ency
0.1
0.2
0.3
0.4
0.1
0.2
0.3
0.4
alpha
alpha
ogbn-arxxiv
1.0
label strabifted coverage
0.8
efficeency
0.4
0.0
0.1
0.4
0.1
0.2
0.3
0.4
alpha
alpha
ogbn-products
17.5
15.0
lobel stratilied coverage
0.0
emclencc
12.5
0.4
5.0
0.2
2.5
0.0
0.0
Figure E5: Plots for efficiency for all the major methods (with best parameters) across all the datasets (cont.). J. Among the baseline methods, TPS consistently has the best efficiency. Results are for the FS split style. The dashed black line indicates the desired label-stratifedd coverage. NAPS results for the ogbn-products dataset are omitted due to size and lack of data points with existing hardware.
42

---

Published in Transactions on Machine Learning Research (05/2025)
F Related Works
In this work, we focus on the prominent methods of graph conformal prediction for the node classification lask under a transductive setting. These included standard conformal prediction methods, like TPS and APS, and graph-specific methods, like DAPS and CFGNN. Some works consider other graph-based scenarios and tasks. Within node classification, we can also consider the inductive setting, where podes//egeer arrive in sequence, thus violating the exchangeability assumption. One such method is Neighborhood Adaptive Prediction Sets (NAPS), which we consider a transductive variation in this work. Beyond node classification static graphs, very recently, there has been some work in link prediction (Zhao et al.
2024
Marandon
2024). Our work can potentially be adapted to these recent ideas (especially ZZhao et al.
2024
although
they make additional assumptions beyond the scope of the current work. Additionally, how these ideas would expand for dynamic graphs would be an interesting future direction to pursue (Davis et al. 2025
Beyond conformal prediction, many works propose ways to construct model-agnostic uncertainly estimates for classification tasks (Abdar et al. 2021 Guo al. 2017: Kull al., 2019). There are also methods specific to GNNs (Hsu al. 2022 Wang et al. 2021 that leverage network principles (e.g., homophily). However, unlike conformal prediction these methods fail to provide the desired coverage guarantees. For
empirical comparison of popular UQ methods for GNN, please reference Huang et al. (2023
43


Reviews:
[{"review_id": "J1NzU7tjGt", "reviewer": "Reviewer_TeCC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n- **S1**: The authors do a good job of summarizing prior work and explaining conformal prediction.\n- **S2**: The paper includes a number of experiments where the nonconformity score and sample partitioning strategy are varied systematically, which seems valuable for understanding the tradeoffs between the methods.\n- **S3**: The authors include code to reproduce their experiments, which also includes their efficient implementation of CFGNN.\n\n## Weaknesses\n\n- **W1**: I found Theorem 3.1 difficult to understand and am not sure that it is correct. See my comments in the \"requested changes\" section below.\n- **W2**: The \"Label-Count Sample Partitioning\" strategy described in Section 3 seems to break exchangeability requirement from Section 2.1. I'm not sure if this is a fundamental issue or an error in describing the strategy.\n- **W3**: I do not have a clear sense of what the major claims and takeaways are from this work. I'm not sure what the empirical findings mean in practice (other than that there are a lot of choices of algorithm and that they have various dataset-dependent tradeoffs).\n- **W4**: The contributions in this work seem somewhat unrelated to each other,  making the paper feel less cohesive. Most of the comparisons between nonconformity scores seem to be properties of conformal prediction in general, rather than being graph specific. On the other hand, the efficient implementation of the CFGNN approach is very specific to a particular method. I don't have a clear sense of who the intended audience is.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies a few design choices involved when using conformal prediction for graph classification. The authors review some of the literature on conformal prediction (including TPS, adaptive TPS, and randomized and non-randomized APS). They then present a general theorem (not specific to graphs) analyzing in which circumstances one nonconformity score function produces more efficient results than another. Additionally, they discuss the conformalized GNN (CFGNN) from Huang et al. (2023) and provide an implementation that is more efficient and allows varying the nonconformity score function used, and also discuss a  variant DTPS of the previously proposed DAPS algorithm (H. Zargarbashi et al. 2023). These results are each accompanied by empirical findings on graph classification datasets, focusing on the efficiency and label-stratified coverage of each method.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "## Fix clarity and possible correctness issues in Theorem 3.1 [W1]\nI found Theorem 3.1 difficult to follow and am not sure the definitions make sense. I think this should be clarified and fixed if necessary.\n\nIn particular, before Theorem 3.1 the authors define:\n\n> Let $\\alpha\\_c^A$ be the significance level of incorrect labels being in the prediction set, i.e \n>\n> $$\n> 1-\\alpha\\_c^A \\leq \\Pr[A(\\mathbf{x}\\_{n+1}, y\\_{n+1}') < q\\_A] < 1-\\alpha\\_c^A + \\frac{1}{n+1}\n> $$\n> $$\n> \\text{ for } y\\_{n+1}' \\in \\\\{1,2,\\ldots,K\\\\}\\backslash\\\\{y\\_{n+1}\\\\}\n> $$\n\nIt's not clear to me that this is a valid definition of $\\alpha_c^A$. In the multi-class case, $y\\_{n+1}'$ is not a single value but instead an element of a set of values. But then it is not obvious that there is a single value of $\\alpha_c^A$ for which the desired inequality holds. Additionally, it does not seem trivial to \"invert\" the result of Theorem 2.1, which shows how to compute $q$ from $\\alpha$ but not the reverse. (In fact I'm not sure if Theorem 2.1 makes sense if $y\\_{n+1}'$ is an arbitrary element of a set rather than a fixed label.)\n\nA similar issue arises in the derivation after \"For $K$ classes\", where we take a sum of probabilities for each value of $y\\_{i}'$ and turn that into $(K-1)\\Pr[y_i' \\in C_A^{n+1}]$. This seems incorrect, because at this point $y_i'$ is not bound and could take multiple different values.\n\nBeyond this, the notation $C\\_A^{n+1}$ also does not seem to be explicitly defined, although it may be equivalent to $C\\_A(x_{n+1})$?\n\n## Fix issue with \"Label-Count Sample Partitioning\" [W2]\nPage 4 describes \"Label-Count (LC) Sample Partitioning\" as:\n> The data is split to ensure an equal number of samples for each class label is present in Dtrain, Dvalid, and Dcalib. The remaining nodes are Dtest.\n\nHowever, this seems like it would break exchangeability. If data is split to ensure some property is true about Dcalib, this implies that Dcalib and Dtest are chosen via different processes, so conformal prediction results should not apply.\n\nThis also seems to contradict the statement in Section 2.1 that \"The specific Vcalib and Vtest are randomly sampled from Vcalib ∪ Vtest.\"\n\nI think this should be fixed.\n\n## Clarify the overall findings and takeaways [W3, W4]\nAs it currently stands, the paper is not very clear about what the contributions, main claims, and takeaways are. The abstract and introduction are quite vague, and the organization of the paper does not make it clear what parts of the paper are the main contributions. Additionally, many of the contributions seem somewhat unrelated, and I am not sure if there is a central idea that ties them together. Finally, although the set of experiments seems fairly thorough, the paper does not seem to have much discussion about the interpretation of the results, and so it is not clear to me what these results actually tell us about the design choices and tradeoffs involved.\n\nOverall I think this paper would be improved if it was more explicit about these and made some more specific claims or recommendations about what the results mean. Although less important than the correctness issues above, I think this is also important to address.\n\n---\n\nBeyond these main issues, I also found a few more minor issues and had a few questions:\n- Section 2.1 denotes dataset subsets with $V\\_{\\text{split}}$, but section 3 denotes them with $D\\_{\\text{split}}$. Should these match?\n- Section 2.1 states \"Next, we discuss the different settings for node classification in graphs\" but as far as I can tell it only discusses a single setting.\n- $V\\_{\\text{test}}$ appears twice in the second line of \"Transductive setting\", I assume one of these should be \"train\".\n- It's a bit confusing to me that a *smaller* value of \"efficiency\" means that the method is *more* efficient rather than less. Is this common in the literature? If not, could you call it \"inefficiency\" or similar instead?", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WIAiF6OQzo", "reviewer": "Reviewer_1Kwg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n- Comparison between APS and randomized APS: Rich empirical results verify the advantage of randomized APS over APS.\n- Results show the advantage of conformalized training over randomized APS is not that significant, which is a new observation compared to previous work.\n- It improved the efficiency of conformalized training to handle larger graphs.\n\nWeakness\n- Although the experiments are performed on graph data (node classification). The conformal prediction methods such as APS and randomized APS, and the theorem 3.1 are not specifically designed for graph data.\n- The paper is a benchmark paper but it does not contribute a general tool for benchmarking any conformal prediction method for node classification. It does not contribute new datasets either. I wonder if the significance of the contribution is good enough.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper mainly performed experiments to compare different conformal prediction methods for node classification. It also introduced Theorem 3.1, however, it seems irrelevant to node classification.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- This paper only studies node classification, therefore, it is better to modify the title to reflect this.\n- The comparison of randomized, non-randomized APS, and conformalized GNN is a good contribution. However, I wonder if the authors can add what is special about these comparisons w.r.t. node classification. For example, how is the result different from that for i.i.d. data (e.g., image classification)?\n- A crucial aspect of conformal prediction for node classification is the selection of calibration data to satisfy the exchangeability assumption. For example, when given a test set, selecting which nodes as the calibration set can make the exchangeability assumption hold? Should each test node have a unique calibration set? This work can be improved by taking the design choice of the calibration set into consideration.\n- Label stratified coverage is not formally defined.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "pOQMBsYHBe", "reviewer": "Reviewer_KytH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Some of CFGNN's and DAPS' design choices -- e.g. in terms of data splitting or employed conformal scoring methods -- are thoroughly discussed, and the authors seem to have spent time understanding the methods well. However, the overall obtained insights and interest in contributions remain unclear to me. In sec. 2 the background follows the referenced works (while making some notational mistakes, see below), and Thm 2.2. is essentially a direct copy from (Huang et al. 2023), which is fine. \n\nIn sec. 3 some time is spent discussing experimental design including different data partitioning schemes, which can also be inferred from the respective papers directly. Then TPS (Sadinle et al. 2019) as a conformal scoring method is discussed, and its class-wise version is introduced following (Sadinle et al. 2019). The approach is motivated as more 'adaptive', but it remains unclear why TPS or TPS-classwise are of particular interest in the first place for graph data, since existing approaches comment on TPS and opt to use improved APS (Romano et al. 2020) or RAPS (Angelopoulos et al. 2021) instead. In particular, the comparison between TPS (which provides marginal guarantees) and TPS-classwise (which provides stronger class- or partition-conditional guarantees, also called mondrian CP) seems insufficient, and the fact that they address different coverage targets and thus are not necessarily directly comparable is not properly discussed. In Fig. 1, it is unclear to me what the x-axis symbolizes -- is the visible coverage distribution across class labels? Then I would expect TPS-classwise to exactly match target coverage for every class, and TPS should still marginally achieve target coverage. The fact that for the considered LC data split only sample counts of {$10, 20, 40, 80$} are considered *per class* also casts doubt on the robustness of obtained class-wise results. \n\nNext, an extended section discusses the randomization or tie-breaking component of APS, and how APS with tie-breaking provides more efficient prediction sets than without. The insight is fairly trivial and has been discussed before in both the APS and RAPS papers, since it simply suggests a randomized decision on inclusion of one additional label in the set (versus inclusion every time), and thus naturally will sometimes produce label sets with one less label. The inclusion of an own theorem and proof seems unnecessary for this intuition. More specifically relating to graph data, it is again unclear why APS and the randomization step are of such particular importance, except that randomization expectedly improves some results and seems to have been ignored by CFGNN. Yet, the standard APS approach includes randomization and thus trivially provides the obtained benefits, if followed correctly.\n\nAfter that, training improvements for CFGNN in terms of runtime are suggested by introducing batching and caching. Again, not really interesting from a CP perspective and the training changes do not provide any other benefits (e.g. performance improvements), so I struggle to call this an \"insight\" for either CP or the graph application. \n\nFinally, an overall comparison of methods is done across datasets. Personally, I find Fig. 7 the most interesting results and closest in line with claims on \"benchmarking\". However, the different employed scoring methods are not properly explained and it is hard to draw personal conclusions. Furthermore, the considered datasets (aside from Flickr) are all not novel for this task, and have been used in most parts both by (Huang et al. 2023) and (Zargarbashi et al. 2023). So technically, the obtained insights are quite limited. I would have expected extensive comparisons across more datasets and settings of this sort in the paper, e.g. to the scope of (Dheur and Taieb 2023, https://proceedings.mlr.press/v202/dheur23a/dheur23a.pdf) who did a proper benchmarking study for calibration. The related works section afterwards is extremely limited and seems to only focus on the three aforementioned papers, whereas I would expect a thorough literature search and discussion of any related papers. \n\nOverall, the different proposed insights are either very limited in their insight or seemingly unrelated to conformal prediction for graph data. (Huang et al. 2023) explore both classification and regression tasks, while (Zargarbashi et al. 2023) do in-depth experiments for classification across most of the datasets considered here. This paper proposing to benchmark and draw new insights is experimentally more limited than either one of the approaches, and it is hard to draw a conclusive summary of obtained interesting insights.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper attempts to investigate recent methods of conformal prediction for graph-structured data, and specifically for the node classification task. Particular focus is placed on two key papers in that direction, CFGNN (Huang et al. 2023) and DAPS (Zargarbashi et al. 2023), and to a lesser extent NAPS (Clarkson 2023). Some background is provided, and then more general conformal scoring approaches for classification are discussed, including class-wise quantiles and randomization in APS, and some additional experiments w.r.t. to the graph-based methods are done. Finally, CFGNN's training time is improved by batching and some general comparison of methods is done.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "Personally I think the work needs a substantial overhaul and more extensive comparison experiments in order to qualify as an interesting benchmarking paper.\n\nOn a more detailed note, some remarks on notation in the background:\n- The miscoverage level $\\alpha$ is usually restricted to $(0,1)$ rather than $[0,1]$ in order to avoid edge cases and thus similarly $1-\\alpha \\in (0,1)$\n- $x_{n+1}$ should be specified as being a previously unseen test sample \n- Another implicit assumption is that the scoring function $s$ is applied point-wise to each sample in order to ensure that data exchangeability translates to exchangeability of the nonconformity scores (which are used in practice to construct the quantile)\n- In Thm. 2.1 the upper coverage bound $1-\\alpha+\\frac{1}{n+1}$ is exact (i.e. $\\geq$ not >) and requires an additional assumption on uniqueness of the scores\n- The set $C_{\\alpha}(X)$ is denoted using what I assume is a random variable $X$, but is then defined using observation $x$\n- Even in full CP the scores are still computed point-wise or per sample but simply include a predictor retrained on the dataset with candidate $(x_{n+1}, y)$ so I don't see why the score function there is deemed \"more expensive as it maps $\\mathcal{X}^k$ ...\"\n- The classification task is defined as the map $(\\mathbf{X}, \\mathbf{A}, v) \\mapsto y_v$, but perhaps given the notation before $(x_v, \\mathbf{A}) \\mapsto y_v$ is more suitable (since the map is now specific -> specific rather than general -> specific)\n- The distinction between transductive and inductive (especially since used differently in standard conformal literature) for the graph setting should be discussed\n- for the class-wise TPS quantiles $\\hat{q}(\\alpha, y_j)$ the way they are defined an in particular how the subsetted score set is defined seems mathematically confusing. Also I assume $j$ is some targeted class label $j = 1, \\dots, K$?", "broader_impact_concerns": "I do not believe there are any ethical concerns with this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "A4KmeDmIoP", "reviewer": "Reviewer_JtiA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nS1. The paper is well-written and provides a clear summary of conformal prediction for graphs, focusing on the task of node classification. \n\nS2. The paper presents several experimental results that provide insight into the behaviour of conformal prediction in graph learning. \n\nS3. The paper describes a useful scalable implementation (and makes code available). \n\nWeaknesses\n\nW1. There is a concern that the claims (description of what the paper provides, at the end of the introduction and in the abstract) are too vague and are thus not clearly supported by the evidence, either experimental or theoretical, later in the paper.\n\nW2. Although the theoretical result is a welcome contribution, it is currently presented in a confusing fashion. Due to confusion about key definitions, it is not clear to me what the theorem statement means and whether the proof is correct. Aside from this, I struggle to understand the utility of the theorem, as detailed below in “Requested Changes”.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper investigates conformal prediction for the node classification task in graphs, focusing on the Split-CP technique. The paper makes the following contributions:\n\n(1)\tThe paper provides a theoretical result that clarifies sufficient conditions to guarantee that one score function will produce a more efficient prediction set than another score function.\n\n(2)\tThe paper discusses Threshold Prediction Sets (TPS), focusing on the issue of adaptability. The paper contrasts the standard version of TPS with a classwise version (TPS-classwise) that provides coverage for each label at the potential cost of increased variance. The paper experimentally compares the performance of TPS and TPS-classwise under Full-Split and Label-Count sample partitioning, showing that for some datasets TPS-classwise can provide improved adaptability in the Full-Split sample partitioning, especially in cases where the number of samples from each class can vary substantially. \n\n(3)\tThe paper discusses Adaptive Prediction Sets (APS), focusing on the issue of randomized versus deterministic non-conformity scores. The paper provides experimental results showing that randomized APS consistently achieves better efficiency than deterministic APS. \n\n(4)\tThe paper investigates a conformalized GNN (CFGNN), (i) replicating an experiment from a past work that used deterministic APS and showing that the efficiency improvement effectively disappears if randomized APS is used instead; (ii) showing that a small but consistent performance improvement can be achieved if randomized APS is used during calibration; (iii) demonstrating that the CFGNN’s performance in the Label-Count sample partitioning setting is considerably worse; and (iv) reporting on a scalable implementation using batching and caching.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "(1)\tIt’s important that the claims of the paper match what is demonstrated by experiment and theory. Currently the claims are relatively vague and general, and they are not completely supported. Please rewrite the final paragraph of the introduction (and revisit the abstract) to ensure that there is a match between the summary description (claims) and the provided evidence. Most importantly, the paper only presents results for node classification. This should be very clearly specified in the abstract and introduction. Currently, the paper just talks about “graph conformal prediction”, but it does not provide any evidence to support its claims for graph level tasks. Aside from this, the paper claims to provide a “deeper theoretical understanding of some design choices”. In terms of theory, the paper really provides only one theoretical result that clarifies sufficient conditions for when one score function will outperform another. \n\nFinally, the paper claims to provide “intuition on when and how to evaluate CP for graph data”. It is difficult to match this claim to a specific part of the text. I presume that Section 3.4 is supposed to serve this purpose. But it does not really provide clear recommendations concerning “when and how”. Currently it is a collection of relatively random observations that do not form a coherent whole. After reading this, and being presented with a graph dataset, I would really struggle to know what the authors suggest I do and why. Please rewrite Section 3.4 to make the conclusions and practical guidelines much clearer.\n\n(2)\tTheorem 3.1 is currently very difficult to understand – both in terms of the proof and its application. \n\n(a)\tHow are we supposed to interpret “significance level”? My understanding of this is that it is the level at which one accepts that something is statistically significant – hence reporting such as “at the 5 percent significance level”. This is decided by the researcher/scientist as a threshold. However, Theorem 3.1 involves score-specific “significance levels” – am I to interpret $\\alpha_c$ as a function of the score function and the data/distribution? Is it really then a significance level? \n\n(b)\tIs it clear that “the significance level $\\alpha_c^A$” should be common to all incorrect classes? This confusion is related to my struggle to understand how the significance level is defined. Later, there appears to be a sum over classes, which is simplified to be a multiplication by (K-1). But if this is a probability defined for a specific incorrect class (and if it is not, then I don’t understand why there is a sum), then it is difficult to see why it should be the same for every class. Class 1 may be very easy to distinguish, so it is never incorrectly included in the set. On the other hand, class 2 may be very similar to 3 other classes, so it is often incorrectly included. The probabilities (and hence “significance levels”) would therefore have to be different for these classes, because you are providing both upper and lower bounds.\n\n(c)\tIn the proof of Theorem 3.1, for the step to K classes, there is an appearance of $y_i$. What is $i$ in this equation? For the two class case, it is $y_{n+1}$. Why does it change to $i$? If it is an application of exchangeability, then that is fine, but there is a need to at least specify what $i$ is. \n\n(d)\tIn the proof of Theorem 3.1, there is a sum over $y^’_i$ - what is the nature of this sum? It doesn’t seem to make sense that it is over $i$. But there is no other indexing variable. Based on the subsequent appearance of $K-1$, it would seem that it is a sum over the incorrect classes. But the notation does not correctly indicate that it is a sum over classes. Please fix the notation. \n\n(e)\tThe intended application of this theorem is hard to understand. Again, it may all stem from my difficulty in understanding the definition of a “significance level”. But, as best as I can interpret it, the significance level for each score function is being determined from the data. These are then compared, and one can judge whether the prediction set is more efficient. But at this point, the prediction sets are themselves available, so one can directly judge whether one is more efficient than the other. What is the value of the theorem?\n\n(3)\tThe caption of Figure 3 and the associated description in the text are hard to understand. Please rewrite both (the caption and the paragraph) so that it is clear what is being shown and what point is being made by the figure. In its current form, it is hard to see the support for the claim that “This demonstrates the scenario that is a condition for Theorem 3.1”. \n\nMinor Points:\n\nM1. What does the following sentence mean (Section 3.4)?: “This particular dataset comes at the cost of efficiency, though this is not the case with all datasets.” How can a dataset “come at the cost of efficiency”? Please rephrase so that it is easier to understand.\n\nM2. I don’t understand the following sentence in the caption of Figure 1: “For Labeled Stratified Coverage, TPS-Classwise can provide comparable performance to TPS.” All the figures are labelled as “label-stratified coverage”. It is very clear that the performance is not comparable for ogbn-arxiv under the Full-Sample split. \n\nM3: Please number more equations – preferably all. None of the equations in the proof of Theorem 3.1 are numbered. This makes it challenging for me as a reviewer to ask questions or point to issues. It also makes it difficult for readers who may wish to build upon your work and refer, either amongst themselves or in writing, to specific steps or developments. \n\nM4. Typo: “adapatability” – p4.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper was reviewed by four reviewers [1Kwg,JtiA,KytH,TeCC]. They appreciate aspects of the paper, such as summarizing prior work and explaining conformal prediction [TeCC], thorough discussion of some design choices [KytH], a theoretical result of sufficient conditions for producing an improved prediction set [JtiA], and experiments helping to understand tradeoffs between methods [TeCC] and showing advantages of randomized adaptive prediction sets [1Kwg,JtiA].

However, originally, the reviewers had strong concerns as well: they identified concerns of vague and unsupported claims [JtiA], correctness issues including for one theorem [TeCC] and suitability of the methods and theorem for graph data [1Kwg]. Reviewers also found the claims unclear [TeCC] and the contributions not cohesive [TeCC] and had concerns of limited insight [KytH], overall significance/amount of the contributions [1Kwg] as a benchmarking paper. More comparison experiments were desired [KytH]. M

Authors provided responses, and there was also in-depth discussion between some reviewers and the authors.

The reviewers appreciated the revision work by the authors, and all four reviewers ultimately leaned towards acceptance, although one remained borderline in their evaluation of the interestingness of the paper:
- The reduction in the scope of the claims was appreciated, and the claims were now considered clearly specified, with adequate supporting discussion, theorem, and results. 
- Some concern about organization of the paper, cohesiveness of the claims/takeaways, and thoroughness of the findings remained. 
- However, the paper was considered better structured than before. 
- The paper was seen to at least reaffirm claims of previous papers and provide some practical advice, and some findings about the baselines challenging previous assumptions were appreciated.

Overall, I lean slightly towards acceptance.
Decision: Accept (poster)