Similarity-Navigated Conformal Prediction for Graph Neural Networks
Authors: Jianqing Song
Jianguo Huang
Wenyu Jiang
Baoming Zhang
Shuangjie Li
Chongjun Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Neural Networks
Node Classification
Conformal Prediction
Uncertainty Estimation
Primary area: graph_neural_networks

Abstract: Graph Neural Networks have achieved remarkable accuracy in semi-supervised node classification tasks. However, these results lack reliable uncertainty estimates. Conformal prediction methods provide a theoretical guarantee for node classification tasks, ensuring that the conformal prediction set contains the ground-truth label with a desired probability (e.g., 95\%). In this paper, we empirically show that for each node, aggregating the non-conformity scores of nodes with the same label can improve the efficiency of conformal prediction sets while maintaining valid marginal coverage. This observation motivates us to propose a novel algorithm named $\textit{Similarity-Navigated Adaptive Prediction Sets}$ (SNAPS), which aggregates the non-conformity scores based on feature similarity and structural neighborhood. The key idea behind SNAPS is that nodes with high feature similarity or direct connections tend to have the same label. By incorporating adaptive similar nodes information, SNAPS can generate compact prediction sets and increase the singleton hit ratio (correct prediction sets of size one). Moreover, we theoretically provide a finite-sample coverage guarantee of SNAPS. Extensive experiments demonstrate the superiority of SNAPS, improving the efficiency of prediction sets and singleton hit ratio while maintaining valid coverage.

Similarity-Navigateed Conformal Prediction for Graph Neural Networks
Jianqing Song', Jianguo Huang Wenyu Jiang?1, Baoming Zhang',
Shuangjje Li', Chongjun Wang
State Key Laboratory of Novel Software Technology, Nanjing University
e Department of Statisties and Data Science, Southern University of Science and Technology Coolegee of Computing and Data Science, Nanyang Technological University
Abstract
Graph Neural Networks have achieved remarkable accuracy in semi-supervised node classification tasks. However, these results lack reliable uncertainty estimates. Conformal prediction methods provide a theoretical guarantee for node classifi- cation tasks, ensuring that the conformal prediction set contains the ground ground-truth label with a desired probability (e.g.. 95%). In this paper, we empirically show that for each node, aggregating the non-conformity scores of nodes with the same label improve the efficiency of conformal prediction sets while maintaining valid marginal coverage. This observation motivates us to propose a novel algorithm named Similarity-Navigater Adaptive Prediction Sets (SNAPS), which aggregates the non-conformity scores based on feature similarity and structural neighborhood. The key idea behind SNAPS is that nodes with high feature similarity or direct connections tend to have the same label. By incorporating adaptive similar nodes in- formation, SNAPS can generate compact prediction sets and increase the singleton hit ratio (correct prediction sets of size one). Moreover, we theoretically provide a finite-sample sample coverage guarantec of SNAPS, Extensive experiments demonstrate the superiority of SNAPS, improving the efficiency of prediction sets and singleton hit ratio while maintaining valid coverage.
1 Introduction
Graph Neural Networks (GNNs), which process graph-structured data by the message-passing manner (Kipf and Welling, 2017: Hamilton et al., 2017: Velickovic al., 2018; Xu et al., 2019), have achieved remarkable accuracy in various high-stakes applications, e.g., drug discovery (Li al., 2022), fraud detection (Liu al., 2023) and traffic forecasting (Jiang and Luo, 2022), where any erroneous prediction can be costly and dangerous (Amodei et al., 2016; Gao et al., 2019). To improve the reliability of prediction results, many methods have been investigated to quantify the model uncertainty (Gal and Ghahramani, 2016; Guo et al., 2017; Kendall and Gal, 2017; Wang et al., 2021; Hsu al., 2022; Tang al., 2024), while these methods lack theoretical guarantees of quantification. Conformal prediction (CP). on the other hand, offers systematic approach to construct prediction sets that contain ground-trute -rrth labels with a desired coverage guarantee (Vovk al., 2005; Romano et al., 2020; Angelopoulos et al., 2021; Huang et al., 2023a; Xi et al., 2024).
CP algorithms utilize non-conformity scores to measure dissimilarity between the training instances. The lower the score of a new instance, the more likely it belongs to the same distribution space as the training instances, thereby included in the prediction set. To improve the efficiency of prediction sets for GNNs, DAPS (Zargarbashi et al., 2023) smooths node-wise non- conformity scores by incorporating neighborhood information based on the assumption of network
instance and
"Correspondng author (chjvangenju.c cn)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

homophily. Similar to DAPS, CF-GNN (Huang et al., 2023b) introduces a topology- aware output correction model that learns to update prediction and then produces more efficient prediction sets or intervals with the inefficiency as the optimization objective. However, they only consider structural neighbors and ignore the effect of other nodes that are far from the ego node, This motivates us to analyze the influence of global nodes on the size of prediction sets.
In this work, we show that aggregating the information of global nodes with the same label as the ego node benefits the performance of CP methods, We provide an empirical analysis by randomly selecting nodes with the same label as the ego node from an oracle perspective, where the ground ground-truth labels of all nodes are known, and then aggregating their non-conformity scores into the ego node. The results indicate that aggregating scores these nodes can significantly reduce the average size of prediction sets. This suggests that the information of nodes with the same label could correct the non-conformity scores, thereby prompting the efficiency of prediction sets. Detailed analysis is presented in Subsection 3.1. However, during the testing phase, the ground-truth label of every test node unknown. Inspired by the analysis, our key idea is to accurately identify and select as many nodes with the same label as the ego node possible and aggregate their non-conformity scores.
To this end, we propose novel algorithm named Similarity-Navigatee Adaptive Prediction Sets (SNAPS), which could self-adaptively aggregate the non-conformity scores of other nodes into the ego node. Specifically. SNAPS gives the higher cumulative weight for nodes with higher probability of having the same label as the ego node while preserving its own and the one- neighbors. We utilize the feature similarity between nodes and the adjaceney matrix to calculate the aggregating weights. In this way, the corrected scores could achieve compact prediction sets while maintaining the desired coverage.
To verify the effectiveness of our method, we conduct thorough empirical evaluations on 10 datasets, including both small datasets and large-scale datasets, e.g., OGBN Products (Bhatia al., 2016). The results demonstrate that SNAPS not only achieves the pre-defined empirical marginal coverage but also achieves better performance over the compared methods. For example, on OGBN Products, our method reduces the average size of prediction sets from 14.92 of APS to 7.68. Moreover, we adapt SNAPS to image classification problems. The results demonstrate that SNAPS reduces the average size of prediction sets from 19.639 to 4.079 only of the prediction set size from APS on ImageNet (Deng et al., 2009). Code available at https: // thub. com/ /SASS.
We summarize our contributions as follows:
We empirically explain that non-conformity scores of nodes with the same label as the ego node play a critical role their non-conformity scores.
We propose novel algorithm, namely SNAPS that aggregates basic non-conformity scores of nodes obtained through node feature similarity and one-hop structural neighborhood. We provide theoretical analysis show the marginal coverage properties of SNAPS and the validity of SNAPS.
Extensive experimental results demonstrate the effectiveness of our proposed method. We show that SNAPS not only maintains the pre-defined coverage but also achieves great performance in efficiency and singleton hit ratio.
2 Preliminary
In this paper, we focus on split conformal prediction for semi-supervised node classification with transductive learning an undirected graph.
Notation. Graph is represented as g = (V,E), where := (u; [ denotes the node set and E denotes the edge set with |8| = E. Let E (0, NNN be the adjacency matrix, where A.j = 1 there exists edge between nodes 0; and Uj. and A.j = 0 otherwise, and D be its degree matrix, where D,, E; A.j. Let X == _ N" be the node feature matrix, where n, E Rd is d- d-dimensional feature vector for node 2 The label of node v, is y: y, where y denotes the label space.
K}
Transductive setting. In transductive setting, we have access to two node sets, Viasel with labels and Vunlabel without labels, where Vasee Vuntahel = 0 and Viater Vuntahel = V. Viatel is then randomly split node set, correspondingly.
into V Vasin/ Veatia/ Vealib with fixed size, the training/validdaioon/albinn

---

Vunlabel is used as the testing node set Vist- The classifier f(.) is trained on { 3/ To Moit { Jue-vevv and the entire graph structure G (V.E), and is chosen through { yi hv.eVau Then we can get the predicted probability P (r,e for each node through P. ((())) where P, E [0, 1jK and is activation function such as softmax. We usually choose the label with the highest probability as the predicted label, i.e., 0g argmax,Pia-
Graph neural networks. GNNs aim at learning representation vectors for nodes in the graph by leveraging graph structure and node features. Most modern GNNs adopt a series of propagation layers following message passing mechanism (Gilmer et al., 2017). The 1-th layer of the GNNs takes the following form:
h = COMMINE") (n.- (GG ((MSG"(A (n h ) E Nii))
(I)
where h is the hidden representation of node o at the I-th layer with initialization of h (00) x; and N; is a set of nodes adjacent to node MSG AGG and COMBINE denote the functions for message computation, message aggregation, and message combination, respectively, {h JUEE is then fed
After an iteration of the last layer, the obtained final node representation H to classifier to obtain the predicted probability P.
Conformal prediction. CP is promising framework for generating prediction sets that statistically contain ground-true -ruth labels with a desired guarantee. Formally, given calibration data Dealib = {(r, yt) ]_ can generate prediction set C( S Y for unseen instance xx++1 with the coverage guarantee TP Plya+1 E 1() 2 1 - a, where a is the pre-defined significance level. The best characteristic of CP is that it is distribution-free and only relies exchangeability. This means that every permutation of the instances is equally likely, i.c., Dealib U (In+1, Bn+1) is exchangeable, where (I 1, 11++1 an unseen instance.
Conformal prediction is typically divided into two types: full conformal prediction and split conformal prediction. Unlike full conformal prediction, split conformal prediction treats the model as a black box, avoiding the need to retrain or modify the model and sacrificing efficiency for computational efficiency (Vovk et al., 2005; Zargarbashi al., 2023). In this paper, we focus on the computationally efficient split conformal prediction method, thus "conformal prediction" " in the following denotes split conformal prediction.
Theorem (Vovk et al., 2005) Let calibration data and a test instance, i.e., (1),,))) U
(xo+1. Bn+1)} be exchangeable. For any non-conformity score function s X x y 7 R and any significance level a E (0,1), define the 1 quantile of scores
Quantile (I(-a)(a+1)) {s(x;, B)) and prediction sets as (T(n1))) = (yls((n S g)
We have
1 1 < Plyn+1 (a(xn+1) <
(2)
n n+
Theorem statistically provides a marginal coverage guarantee for all test instances. Currently, there are already many basic non-conformity score methods (Romano et al., 2020; Angelopoulos et al., 2021; Huang et al., 2023a). Here we provide the definition of Adaptive Prediction Sets (Romano et al., 2020) (APS).
Adaptive Prediction Sets. In the APS method, the non-conformity scores are calculated by accu- mulating the softmax probabilities in descending order. Formally, given a data pair (x, y) and a predicted probability estimator T for (æ, y), where <(w), is the predicted probability for class y, the non-confornity scores can be computed by:
s(x, v)
Σ <<)); x(x))) + <<())
where & J0, 1] is uniformly distributed random variable. Then, the prediction set is constructed as C(x) = {v)s((,))) y) < q).
Evaluation Metries. The goal is to improve the efficiency of conformal prediction sets as much as possible while maintaining the empirical marginal coverage guarantee. Given the testing nodes set Viea. the efficiency is defined as the average size of prediction sets: Size Maal Er,evin. (C(x:)).
3

---

2.75
100
64:40
60.00
16:00
75.90
2.50
0.95
20
different label
6000
50.00
73.0
2.25
Coverage
17-
2.00
Coverage
0.85
6..0
$2.02
66.20
57.00
57.40
02.00
15-
1.75
20.00
02.00 53.32
57.00
10
05.00
12-
1.50
0.75
10
15.00
M:63
57.40 81
5220
10:
68.32
00.50
20
40
0
3 Label
20
40
The number of nodies
(a) Oracle Performance
(b) Feature Similarity"
Same/Diff. Label Count
The motivation for SNAPS. (a) The trend of Coverage and Size the number of nodes with the same label as the ego node increases. (b) The average of node feature cosine similarity between same different labels. (c) The number statisties of nodes with the same label and with different labels as the ego node with increasing k that denotes k--N with feature similarity.
Figure 1:
The smaller the size, the more efficient CP is. The empirical marginal coverage defined as Coverage := - Ev,ev H| C(x,)]. Although efficiency a common metric for evaluating CP, singleton ratio (SH), defined as the proportion of prediction sets of size one that contains the ground-truth label, is also important (Zargarbashi et al., 2023). The formula of SH is defined as: SH
Pani Ex,evior [[::)) = {v:
3 Motivation and Methodology
In this section, we begin by outlining our motivation, substantiating its validity and feasibility through experimental evidence. Then, propose method, SNAPS. Finally, we demonstrate that SNAPS satisfies the exchangeability assumption required by CP and offer proof of its improved efficiency compared to basic non-conformity score methods.
3.1 Motivation
In this subsection, empirically show that nodes with the same label the ego node may play critical role in the non-conformity scores of the ego node. Specifically, using the scores nodes with the same label to correct the scores of the ego node could reduce the average size of prediction sets.
To analyze the role of nodes with the same label as the ego node, assuming we have access to an oracle graph, i.e., the ground-truth labels of all the nodes are known. Then, we randomly select nodes with the same label as the ego node and aggregate their APS non-conformity scores into the ego node. We conduct experiments by Graph Convolutional Network (GCN) (Kipf and Welling, 2017) on CoraMI. (McCallum al., 2000) dataset and choose APS the basic score function of CP. Then, we conduct 10 trials and randomly select 100 calibration sets for each trial to evaluate the performance of CP at a significance level a 0.05.
In Figure ((a), we can find that the average size of prediction sets drops sharply as the number of nodes being aggregated increases, while maintaining valid coverage. When the number of selected nodes is 0, the results shows the performance of APS. Therefore, if the non-conformity scores of the ego node are corrected by accurately selecting nodes with the same label, Size can be reduced to large extent. Moreover, aggregating the scores of these nodes still achieves the coverage guarantee.
3.2 Similarity-Navigater Adaptive Prediction Sets
In our previous analysis, we show that correcting the scores of the ego node with the scores of nodes having the same label leads to smaller prediction sets and valid coverage. However, the above experiment is based on the oracle graph. In the real-world application. the ground-truth label of each test node is unknown. To alleviate this issue, our key idea is use the similarity approximate the
VValues of feature similarity multiplied by 1000.

---

Train Val modes
Calli modes
Tenk modes
Gmund--ruth label
Fales Bebel
Other label
Queiitle scure
Festure similarity
Feature X
Scores correction
SNAPS scores
quantile-
GNN
Nop-conformity soures
Nen-oonformity score function
c(2,)
(x,,)
Graph G
structure
Basic non-sonformity fumetion
(2) SNAPS function method)
Conformal Prediction
Figure 2: The overall framework SNAPS. (1) Basic non-conformity score function. We first use basic non-conformity score functions, e.g.. APS, to convert node embeddings into non-conformity scores. (2) SNAPS function. We then aggregate basic non-conformity scores of k-NN with feature similarity and one-hop structural neighbors to correct the non-conformity scores of nodes. (3) Conformal Prediction. Finally, we use conformal prediction to generate prediction sets, significantly reducing their size compared to the basic score functions.
potential label. Specifically, the nodes with high feature similarity tend to have a high probability of belonging the same label.
Several studies (Jin et al., 2021b;a; Zou et al., 2023) have demonstrated that matrix constructed from node feature similarity can help with the homophily assumption, i.e., connected nodes in the graph are likely to share the same label. Additionally, the network homophily can also help us to find more nodes whose labels are likely be the studies have demonstrated the effectiveness of this (Clarkson, 2023; Zargarbashi et al., 2023; Huang al., 2023b). Therefore, we consider feature similarity and network structure select nodes that may have the same label as the ego node.
as the ego node (Kipf and Welling, 2017), and several
Feature similarity graph construction. We compute the cosine similarity between the node features in the graph. For a given node pair (ve, U3), the cosine similarity between their features can be calculated by:
Sim(i,
x
where i * vj E V and ej E Vr,i. Here, "y E Vr,i represents set of nodes for which we calculate the similarity with v. Then, we choose k nearest neighbors for each node based on the above cosine similarity, forming the k-NN graph. We denote the adjacency matrix of k-NN graph A, and its degree matrix as Da. where (i, = Sim(i.j) and (i, = E, (i, For large graphs, we randomly select M >> nodes to put into Vr,s, whereas for small graphs, we include nodes into 2/y Ve,i-
To verify the effectiveness feature similarity, we provide an empirical analysis. Figure 1(b) presents the average of node feature cosine similarity between the same or different labels on the CoraML dataset. We can find that the average of node feature similarity between the same label is higher than those between different labels. We analyze experimentally where using feature similarity to select k-NN meets our expectation of selecting nodes with the same label as the ego node. Figure ((c) shows the number statistics of nodes with the same label and with different labels at k-th nearest neighbors. The result shows that we can indeed select many nodes with the same label when not very large.
SNAPS. We propose SNAPS that aggregates non-conformity scores of nodes with high feature similarity to ego node and one-hop graph structural neighbors. Formally, for a node with a label the score function of SNAPS shown as
M
H Σ s(z,,)), (5) [ RyEN
8 8(x,, v) = (1 - A p)s(2r,)) y) + D
A,
5

---

where s(,,-) ) is the basic non conformiyy score function and s(:,-) is the SNAPS score function. Both À and μ are hyperparameters, which are used measure the importance of three parts of non-conformity scores. The framework of SNAPS is shown in Figure 2 and the pseudo-code is in Appendix B.
3.3 Theoretical Analysis
To deploy CP for graph-structured data, the only assumption we should satisfy is exchangeability. i.e. the joint distribution of calibration and testing sets remains unchanged under any permutation. Several studies have demonstrated that non-confore non-conformity scores based on the node embeddings obtained by any GNN models are invariant to the permutation of nodes while permuting their edges correspondingly in the calibration and testing sets. This invariance arises because GNNs models and non-conformity score functions only use the structures and attributes in the graph, without dependence on the order of the nodes (Zargarbashi et al., 2023; Huang et al., 2023b). Under this condition, we prove that SNAPS non-conformity scores are still exchangeable.
Proposition 1 Let S u,y) be basic non-conformity scores of nodes, where 8, R.K Assume that S exchangeable for all ih E (Ventih U Viss). Then the aggregated S = 11 u)S A μAS, where A, = = A, and Å = AA, is also exchangeable for 1/ E (Ventib U Vien).
D-1
The corresponding proof is provided in Appendix A. We then demonstrate the validity of our method theoretically.
Proposition 2 Assume that all the nodes aggregated by SNAPS are the same label as the ego node. Given a data pair (x. y) and predicted estimator x xxx)y for (xx, y), where (2)) is the predicted probability for class y. Moreover, Egi reflects the model's 's error in misclassifring the ground- label i as label i. Let S be APS scores of nodes, where S.s E [0, 1] is the score corresponding to node with label i. Let Eg (x((T(()))) and [S be the average of predicted probability and scores corresponding to label of nodes whose ground-truth, labels are k, respectively. Let nj be 1 -aa quantile of basic non-conformity scores with significance level a. If [x[Suu] < and En [S.] 2 (1 - Exx) Ex [TT (W)) + Ex(e (xxx);, where Ex T (Zu)man) denotes the maximum predicted probability of nodes whose ground-truth labels are k and & E [0, 1] is uniformly distributed random variable, then
El[Č(=)]] s E[[C(=)]],
where C(-) and C()) represent the prediction set from the APS score function and SNAPS score function, respectively.
In other words, SNAPS consistently generates a smaller prediction set than basic non-conformity scores functions and maintains the desired marginal coverage rate. It is obvious that can't ignore a very important thing, which is to select nodes with the same label as the ego node as correctly as possible, otherwise, will lead decrease in the efficiency of SNAPS.
4 Experiments
In this section, we conduct extensive experiments on semi-supervised node classification to demon- strate the effectiveness of SNAPS on graph-structure data. We also adapt SNAPS for image clas- sification problems. Furthermore, we perform ablation studies and parameter analysis to show the importance of different components in SNAPS and evaluate its robustness, respectively.
4.1 Experimental Settings
Datasets. In our experiments, we consider ten datasets with high homophily, where connected
nodes in the graph are likely to share the same label. These datasets include the common citation graphs: CoraML (McCallum et al., 2000), PubMed (Namata et al., 2012), CiteSeer (Sen et al., 2008), CoraFull (Bojchevski and Günnemann, 2018), Coauthor Physics (Physics) and Coauthor CS (CS) (Shchur et al., 2018) and the co-purchase graphs: Amazon Photos (Photos) and Amazon Computers (Computers) (MeAuley et al., 2015; Shchur et al., 2018). Moreover, we consider two large-scale graph datasets, i..., OGBN Arxiv (Arxiv) (Wang al., 2020) and OGBN Products (Products) (Bhatia

---

Table I: Results of Coverage, Size and SH on different datasets. For SNAPS we use the APS score as the basic score. We report the average calculated from 10 GCN runs with each run of 100 conformal splits at a significance level a = 0.05. Bold numbers indicate optimal performance.
Coverage
Sizel
SH%1 f
Dutasets
APS
RAPS
DAPS
SNAPS
APS
RAPS
DAPS
SNAPS
APS
RAPS
DAPS
SNAPS
CoraML
0,950
0.950
0.950
0.950
2.42
2.21
1.92
1.68
44.89
22.19
52.16
56.30
PubMed
0,950
0.950
0.950
0.950
1.79
1.77
1.76
1.62
33.67
30.83
35.25
42.95
CiteSeer
0.950
0.950
0.950
0.950
2.34
2.36
1.94
1.84
50.41
38.99
59.75
59.08
CoraFull
0.950
0.950
0.950
0.950
17.54
10.72
11.81
9.80
10.23
2.13
8.67
5.76
CS
0,950
0.950
0.950
0.950
1.91
1.20
1.22
1,08
66.17
78.34
79.80
87.92
Physics
0.950
0.950
0.950
0.950
1.28
1.07
1.08
1.04
76.74
88.89
88.40
91.21
Computers
0.950
0.950
0.950
0.950
3.95
2.89
2.13
1.98
27.67
15.85
43.03
45.48
Photo
0,951
0.950
0.950
0.951
1.89
1.64
1.41
1.31
54.31
56.63
74,57
78,51
Arxiv
0.950
0.950
0.949
0.950
4.30
3.62
3.73
3.62
22.55
14.52
19.19
23.53
Products
0.950
0.951
0.950
0.950
14.92
13.67
10.91
7.68
15.51
11.51
19.29
22.38
Average
0.950
0.950
0.950
0.950
5.23
4.12
3.79
3.17
40.22
36.00
48.01
52.31
al., 2016). Particularly, for CoraFull which is highly class-imbalanced, we filter out the classes with fewer than 50 nodes. The transformed dataset is dubbed as CoraFull* (Zargarbashi et al., 2023). Detailed statistics of these datasets shown in Appendix F. In addition to the datasets mentioned above, we discuss two heterophilous graph datasets in Appendix C.I, namely Chameleon and Squirrel, both of which are two Wikipedia networks (Rozemberczki et al., 2021).
Baselines. Since our SNAPS is a general proc-proessiing method for GNNs, here we choose GCN (Kipf and Welling, 2017), GAT (Velickovic et al., 2018) and APPNP (Gasteiger al., 2018) as structure- awaree models and MLP as a structure- innttuur--idepeddeem model. Moreover, our SNAPS can be based on general conformal prediction non-conformity scores, here choose APS (Romano et al., 2020) and RAPS (Angelopoulos et al., 2021). For comparison, we compare not only with the basic scores, i.e., APS and RAPS, but also with DAPS (Zargarbashi et al., 2023) for GNNs.
CP Settings. For the basic model GCN, GAT, APPNP and MLP, we follow parameters suggested by (Zargarbashi et al., 2023). For DAPS, we follow the official implementation. Since GNNs are sensitive to splits, especially in the sparsely labeled setting (Shchur et al., 2018), we train the model over ten trials using varying train/validation splits. For per class in the training/validation validation set, randomly select 20 nodes. For Arxiv and Products dataset, we follow the official split in Py PyTorch Geometric (Fey and Lenssen, 2019). Then, the remaining nodes are included in the calibration set and the test set. The calibration set ratio is suggested by (Huang et al., 2023b), i.e., modifying the calibration set size to Vaamnl = min (1000, Vealih UViest l/ee)/2). For each trained model, random splits of calibration/test set. Thus, we totally conduct 1000 trials to evaluate the effectiveness of CP. For the non-conformity score function that requires param--arameters, we split the calibration set into two sets, one for tuning parameters, and the other for conformal calibration (Zargarbashi al.. 2023). For SNAPS, we choose X and μ increments of 0.05 within the range 0 to and ensure that À + μ <= 1. Each experiment is done with a single NVIDIA V100 32GB GPU.
conduct 100
4.2 Experimental results
SNAPS generates smaller prediction sets and achieves a higher singleton hit ratio. Table 1 shows that Coverage of all conformal prediction methods is close to the desired coverage 1 - a. At significance level 0.05, Size and SH exhibit superior performance. For example, when evaluated on Products, SNAPS reduces Size from 14.92 of APS to 7.68. Overall, the experiments show that SNAPS has the desired coverage rate and gets smaller Size and higher SH than APS, RAPS, and DAPS. Detailed results for other basic models and SNAPS based on RAPS are available in Appendix D.
SNAPS generates smaller average prediction sets for each label. We conduct additional experi- ments to analyze the average performance of APS and SNAPS on nodes belonging to the same label at a significance level a 0.05. Figure 3(a) shows that the distribution of the average non-conformity
scores for nodes belonging to the same label aligns with the assumptions made in Proposition 2, i.e.,
FA [Swk] < 1) and E& [s[S..] 77 2 -A, where A = ? (1 - -xx) F [T (T)())) mar]
F& [ x (ar,).., O, then it is very small. Size of prediction sets corresponding APS is 3.29. Figure 3(b) shows
7

---

Ground-truth label
False label
Other label
Quantile
APS scores
0.4-
0.2
0123466
0123456
0123456
0 0123456 Node Labels
0123456 012345
(a) APS: Size = 3.29
SNAPS scores
0.8-
0.4
0.2
6
0123456
0123456
0 Node Labels
0 0123456
0 4124456
(b) SNAPS: Size = 1.29
Figure 3: The average non-conformity scores of nodes belonging each label based on the model GCN for dataset CoraML.
Table 2:
Ablation study in terms of Size. Overall, three parts of our method are critical, and removing any of them results in a general decrease in performance.
Orig.
Neigh.
Feat.
CoraMI.
PubMed
CiteSeer
CoraFull"
CS
Physics
Computers
Photo
arxiv
products
2.42
1.79
2.34
17.54
1.28
3.95
1.89
4.30
14.92
2.18
1.94
2.07
17.50
1.37
1.09
2.15
1.42
4.75
11.25
2,40
1.65
2.52
18.07
1,33
3.26
2.60
9.45
13.89
1.87
1.72
1.91
12.10
1.22
1.07
2.22
1.37
3.76
10.81
1.78
1.63
1.94
11.54
1.13
1,05
2.37
1.46
3.82
8.46
x
1.72
1.63
1.86
10.51
1.09
1.04
1.94
1.31
4.44
7.65
168
1.62
1.84
9.80
L.0
1.44
198
1.31
3,62
7.68
that only few other labels different from real labels have average scores lower than the quantile of scores. Size of prediction sets corresponding to SNAPS is 1.29. Overall, for basic non-conformity scores that match this distribution our assumptions, SNAPS can achieve superior performance based these scores. The results of CiteSeer and Amazon Computers datasets are available in Appendix D.
Ablation study. To understand the effects of three parts of method, i.c., original scores (Orig.), neighborhood scores (Neigh.), and feature similarity node scores (Feat.), we conduct a thorough ablation experiment using GCN when all three parts are included. Moreover, for the remaining dataset on which SNAPS exhibits comparable performance, all those better cases contain the Feat. part. Overall, each part plays critical role in CP for GNNs, and removing any will general decrease performance.
0.05. In Table 2, SNAPS performs best on most datasets
Parameter analysis. We conduct additional experiments to analyze the robustness of SNAPS. We choose GCN as the GNNs model and APS as the basic non-conformity score function.
Figure 4(a) and Figure 4(b) demonstrate that the performance of SNAPS significantly improves as gradually increases from 0. This improvement occurs because the increasing nodes with the same label are selected to enhance the ego node. Subsequently as & continues to increase, the performance of SNAPS tends to stabilize. On the other hand, we find that when k is extremely large, appears that nodes with the same label cannot be selected with high accuracy only by feature similarity. Thus, when & is extremely large, performance will decline slightly. Figure 4(c) and Figure 4(d) show that as the values of parameter and change, the most areas in the heatmaps of Size and SH display similar colors. Overall, SNAPS is robust to the parameter & and is not sensitive to parameters À and To further explore the sensitivity of À and to the performance of SNAPS, we set X / =0=1p 1/3. which indicating that three components of SNAPS are equally weighted. The experimental results in Table 3 demonstrate that SNAPS performs well with these default hyperparameters most datascts.

---

SMAPS with ko0
Staps
56
24
185
0 1.00-
52
2.0
40
1.70-
48
SNAPS
SMAPS with k-0
18
50
100
150
200
1.0 200
0.8
00
(a) Size with param. k (b) SH with param. k
(c) Size with param. X,
(d) SH with param. X,
Figure 4: Parameter analysis. The results for Size and SH on SNAPS (based on APS) for CoraML
dataset with 0.05.
Table Results of Coverage, Size and SH on different datasets. For SNAPS we use the APS score as the basic score and set À 1/3. We report the average calculated from 10 GCN runs with each run of 100 conformal splits at a significance level a 0.05. Bold numbers indicate optimal performance.
Coverage
Sizel
SH%f
Datasets
APS
RAPS
DAPS
SNAPS
APS
RAPS
DAPS
SNAPS
APS
RAPS
DAPS
SNAPS
CoraML
0.950
0.958
0.957
0,951
2.50
2.62
2.32
1.74
43.09
27.34
44.52
54.11
PubMed
0.950
0.968
0.967
0.950
1.82
2.10
2.09
1.61
33.39
14.66
23.27
44.11
CiteSeer
0.951
0,950
0.952
0.950
2.41
2.69
2.16
1.90
48.53
35.37
55.40
58.22
CS
0.950
0.954
0,950
2.04
1.33
1.13
64.32
66.91
74.91
85.21
Physics
0.951
0.962
0.962
0,950
1.39
1.44
1.28
1.07
72.44
62.22
77.65
88.58
Computers
0.950
0.950
0.951
0.950
3.01
3.04
2.30
2.01
29.21
9.87
42.19
45.98
Photo
0.949
0.950
0.950
0,950
1.90
1.81
1.56
1.30
54.86
47.27
67.57
79.50
Table 4: Results on Imagenet. The median-of-meant is reported over 10 different trials. Bold numbers indicate optimal performance.
APS/SNAPS
Accuracy
= 0.1
= 0.05
Model
Top1
Top5
Coverage
Size 4
SSCV J
Coverage
Sizel
SSCV
ResNeX:101
79.32
94.58
0.899/0.900
19.64/4.08
0.088/0.059
0.950/0.950
45 80.8441
0.047/0.033
ResNet101
77.36
93.53
0.900/0.90 900
10.82/3.62
0.075/0.078
0.950/0.950
22.90/9.83
0.039/0.029
DenseNet161
77.19
93.56
0.900/0.900
12.04/3.80
0.077/0.067
0.951/0.950
27.99/10.66
0.039/0.026
VIT
81.02
95.33
0.899/0.899
10.50/2.33
0.087/0.133
0,949/0.950
31.12/10.47
0.042/0.040
CL.PP
60.53
86.15
0.899/0.899
17.46/10.32
0.047/0.032
0.950/0.949
34.93/24.53
0.027/0.017
Average
0.899/0.900
14.09/4.83
0.075/0.074
0.950/0.950
32.55/13.99
0.039/0.029
Adaption to image classification problems. In the node classification problems, SNAPS achieves better performance than standard APS, which was proposed for image classification problems. Therefore, we employ SNAPS for image classification problems. Since there are no links between different images, we utilize the cosine similarities image features to correct the APS. Formally, the corrected APS, i.e., SNAPS, is defined as
8(x, v) (1 ()) +
Σ REN
s(ē y),
W
where sax y) is the score of standard APS, Ng. te is the k nearest neighbors based on image features in the calibration set and ry is a corrected weight. We conduct experiments on ImageNet, whose test dataset is equally divided into the calibration set and the test set. For SNAPS, we set A 5 and 7 = 0.5. We report the results of Coverage. Size and size-stratified coverage violation (SSCV) (An- gelopoulos al., 2021). The details of experiments and SSCV are provided in Appendix E.
As indicated in Table 4, SNAPS achieves smaller prediction sets than APS. For example, on 10sNeXt101 model and = (NAPS reduces Size from 19.639 to 4.079 only & of the prediction set size from APS and achieves the smaller SSCV than APS. Overall, SNAPS could improve the efficiency of prediction sets while maintaining the performance of conditional coverage.

---

5 Related Work
Uncertainty Quantification for GNNs. Many uncertainty quantification (UQ) methods have been proposed to quantify the model uncertainty for classification tasks in machine learning (Gal and Ghahramani, 2016; Guo et al., 2017; Zhang et al., 2020; Gupta et al., 2021). Recently, several calibration methods for GNNs have been developed, such as CaGCN (Wang et al., 2021), GATS (Hsu al., 2022) and SimCalib (Tang et al., 2024). However, these UQ methods lack statistically rigorous and empirically valid coverage guarantee (Huang et al., 2023b). In contrast, SNAPS provides valid coverage guarantees both theoretically and empirically.
Many conformal prediction (CP) methods have been developed to provide valid uncertainty estimates for model predictions in machine learning classification tasks (Romano et al., 2020; Angelopoulos et al., 2021; Liu et al., 2024; Wei and Huang, 2024). Although several CP methods for GNNs have been studied, the use of CP in graph-structured data still largely underexplored. ICP (Wijegunawardana et al., 2020) is the first to apply CP framework on graphs, designs margin conformity score for labels of nodes without considering the relation between nodes. NAPS (Clarkson, 2023) use the non-exchangeable technique from (Barber et al., 2023) for inductive node classification, not applicable for the transductive setting, while we focus on the transductive setting where exchangeability property holds. Our method is essentially an enhanced version of the DAPS (Zargarbashi et al., 2023) method, which proposes a diffusion based method that incorporates neighborhood information by leveraging the network homophily. Similar to DAPS, CF-GNN (Huang al., 2023b) introduces a aopology-waar output correction model, akin to GCN, which employs conformal-awan inefficiency loss to refine predictions and improve the efficiency of post-hoc CP. Other recent efforts in CP for graphs include (Lunde, 2023; Marandon, 2023; Zargarbashi and Bojchevski, 2023; Sanchez-Martin et al., 2024) which focus on distinct problem settings, In this work. SNAPS takes into account both network topology and feature similarity. This method can be applied not only to graph-structured data but also to other types of data, such image data.
Conformal Prediction for GNNs.
6 Conclusion
In this paper, we propose SNAPS, a general algorithm that aggregates the non-conformity scores of nodes with the same label as the ego node. Specifically, we select these nodes based on feature similarity and structural neighborhood, and then aggregate their non-conformity scores to the ego node. As result, our method could correct the scores of some nodes. Moreover, we present theoretical analyses to certify the effectiveness of this method. Extensive experiments demonstrate that SNAPS not only maintains the pre-defined coverage, but also achieves significant performance in efficiency and singleton hit ratio. Furthermore, we extend SNAPS to image classification, where SNAPS shows superior performance compared to APS.
Limitations. Our work focuses node classification using transductive learning. However, in real- world scenarios, many classification tasks require inductive learning. In the future, we aim to apply method to the inductive setting. Additionally, the method the ego node is both computationally inefficient and lacking accuracy. Future work will explore more efficient and accurate methods for node selection. Moreover, while our focus is primarily on datasets with high homophily, many heterophilous networks are prevalent in practice. Consequently, further investigation is essential to enhance the adaptability of SNAPS to these networks.
select nodes with the same as
Acknowledgments
This paper is supported by the National Natural Science Foundation of China (Grant No. 62192783, 62376117), 17), the National Social Science Fund of China (Grant No. 23BJLO35), the Science and Technology Major Project of Nanjing (comprehensive category) (Grant No. 202309007), and the Collaborative Innovation Center of Novel Software Technology and Industrialization Nanjing University.
10

---

References
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Concrete problems in ai safety. arXiv preprint arXiv: (.X,:6660606665,, 2016.
Anastasios Nikolas Angelopoulos, Stephen Bates, Michael I. Jordan, and Jitendra Malik. Uncertainty sets for image classifiers using conformal prediction. In 9th International Conference on Learning Representations, 2021.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. Conformal prediction beyond exchangcability. The Annals of Statistics, 51(2): (122):86-845, 2023.
K. Bhatia, K. Dahiya, H. Jain, P. Kar, A. Mittal, Y. Prabhu, and M. Varma. The extreme classification repository: Multi-label datasets and code, 2016. URL XC/ CC/XMLRepository .tmll.
org/ downloads/
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. In 6th International Conference on Learning Representations, 2018.
Jase Clarkson. Distribution free prediction sets for node classification. In International Conference on Machine Learning, pages 6268-6278, 2023.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 248-255, 2009.
Wei Dong, Moses Charikar, and Kai Li. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th International Conference on World Wide Web, pages 577-586, 2011.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: /903. 1et..02232.2.. 02428, 2019.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In International Conference Machine Learning, pages 1050-1059, 2016.
Jinyang Gao, Junjie Yao, and Yingxia Shao. Towards reliable learning for high stakes applications. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3614-3621, 2019.
Johannes Gasteiger, Aleksandar Bojehevski. and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv: 1810005911 2018.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 1263-1272, 2017.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning, pages 1321-1330, 2017.
Kartik Gupta, Amir Rahimi, Thalaiyasingam Ajanthan, Thomas Mensink, Cristian Sminchisescu, and Richard Hartley. Calibration of neural networks using splines. In 9th International Conference on Learning Representations, 2021.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in Neural Information Processing Systems, pages 1024-1034, 2017.
Hans Hao-Hsun Hsu, Yuesong Shen, Christian Tomani, and Daniel Cremers. What makes graph neural networks miscalibrated? In Advances in Neural Information Processing Systems, 2022.
Jianguo Huang, Huajun Xi, Linjun Zhang, Huaxiu Yao, Yue Qiu, and Hongxin Wei. Conformal prediction for deep classifier via label ranking, arXiv preprint arXiv:2310.06433 2023a.
11

---

Kexin Huang, Ying Jin, Emmanuel J. Candès, and Jure Leskovec. Uncertainty quantification over graph with conformalized graph neural networks. In Advances in Neural Information Processing Systems, 2023b.
Weiwei Jiang and Jiayun Luo. Graph neural network for traffic forecasting: A survey. Expert Systems with Applications, 207:117921, 2022.
Di Jin, Zhizhi Yu, Cuiying Huo, Rui Wang, Xiao Wang, Dongxiao He, and Jiawei Han. Universal graph convolutional networks. Advances in Neural Information Processing Systems, 34:10654- 10664. 2021a.
Wei Jin, Tyler Derr, Yiqi Wang, Yao Ma. Zitao Liu, and Jiliang Tang. Node similarity preserving graph convolutional networks. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pages 148-156, 2021b.
Alex Kendall and Yarin Gal. What uncertainties do we need in bayesian deep learning for computer vision? Advances in Neural Information Processing Systems, 30, 2017.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks In 5th International Conference on Learning Representations, 2017.
Michelle M Li, Kexin Huang, and Marinka Zitnik. Graph representation learning in biomedicine and healthcare. Nature Biomedical Engineering, (11))1333-1136) 2022.
Kangdao Liu, Tianhao Sun, Hao Zeng, Yongshan Zhang, Chi-Man Pun, and Chi-Man Vong. Spatial- aware conformal prediction for trustworthy hyperspectral image classification. arXiv preprint arXiv:2409.01236. 2024.
Yajing Liu, Zhengya Sun, and Wensheng Zhang. Improving fraud detection via hierarchical attention- based graph neural network. Journal of Information Security and Applications, 72: 2023.
Robert Lunde. On the validity of conformal prediction for network data under non-uniform sampling. arXiv preprint 2rXiv:2306.07252, 2023.
Ariane Marandon. Conformal link prediction to control the error rate. arXiv:2306. 14693, 2023.
arXiv preprint
Sumil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. Simplifying approach to node classification in graph neural networks. J. Comput. Sci., 62:101695, 2022.
Julian J. McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel. Image-based recommendations on styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 43-52, 2015.
Andrew McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore, Automating the construction of internet portals with machine learning. Inf. Reir, 3(2):127-163, 2000.
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and U Edu. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, volume 8, page 1, 2012.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, 32, 2019.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In 8th International Conference on Learning Representations, 2020.
Yaniv Romano, Matteo Sesia, and Emmanuel J. Candès. Classification with valid and adaptive coverage. In Advances in Neural Information Processing Systems, 2020.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Complex Networks, 9(),, 2021.
12

---

Pablo Sanchez-Martin, Kinaan Aamir Khan, and Isabel Valera. Improving the interpretability of gnn predictions through conformal-basee graph sparsification. arXiv preprint arXiv:2404.12356 2024.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al Magazine, 29(3)993, 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arxiv: /8/ 1.05868, 2018.
Boshi Tang. Zhiyong Wu, Xixin Wu, Qianchu Huang. Jun Chen, Shun Lei, and Helen Meng. Simcalib: Graph neural network calibration based on similarity between nodes. In Thirty-Eighth AAAI Conference on Artificial Intelligence, pages 15267-15275, 2024.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liō, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, 2018.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic Learning in Random World. Springer Science & Business Media, 2005.
Kuansan Wang. Zhihong Shen, Chiyuan Huang, Chieh-Har Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1): 396-413, 2020.
Xiao Wang. Hongrui Liu, Chuan Shi, and Cheng Yang. Be confident! towards trustworthy graph neural networks via confidence calibration. In Advances in Neural Information Processing Systems, pages 23768 23779, 2021.
Hongxin Wei and Jianguo Huang. Torchep: A library for conformal prediction based on pytorch. arXiv preprint arXiv:2402.12663 2024.
Pivithuru Wijegunawardana, Ralucca Gera, and Sucheta Soundarajan. Node classification with bounded error rates. In Complex Networks XI: Proceedings of the 11th Conference Complex Networks CompleNet 2020, pages 26-38. Springer, 2020.
Huajun Xi, Jianguo Huang, Lei Feng, and Hongxin Wei. Delving into temperature scaling for adaptive conformal prediction. arXiv preprint arXiv:2402.04344 2024.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, 2019.
Soroush H Zargarbashi and Aleksandar Bojchevski. Conformal inductive graph neural networks, In The Twelfth International Conference on Learning Representations, 2023.
Soroush H. Zargarbashi, Simone Antonelli, and Aleksandar Bojchevski. Conformal prediction sets for graph neural networks. In International Conference Machine Learning, volume 202, pages 12292-12318, 2023.
Jize Zhang, Bhavya Kailkhura, and Thomas Yong-Jin Han. Mix-n-match: Ensemble and composi- tional methods for uncertainty calibration deep learning. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pages 11117-11128 2020.
Minhao Zou, Zhongxue Gan, Ruizhi Cao, Chun Guan, and Siyang Leng. naviiatity-aviigtted graph neural networks for node classification. Information Sciences, 633:41-69, 2023.
13

---

A Proofs
In this section, we provided the proofs that were omitted from the main paper.
A.1 Proof of Proposition
(Zargarbashi et al., 2023) have proved that (1- 4)S + μÂS is exchangeable for V E (Veltth U Vies). So we only need prove that Á,S also exchangeable for us (Veath U Viea). Å, obtained by calculating the feature similarity between two nodes from global perspective. Before obtaining this matrix, we can not distinguish between labeled and unlabeled nodes, so we just build new graph structure using node features without considering the order of nodes. So when aggregating non-conformity, we do not break the permutation equivariant. Therefore, S = - - -u. + XÁ.S + μAS is special case of message passing GNNs layer. It follows that $ is invariant permutations of the order of the calibration and testing nodes on the graph. Through the proof above,
Proof.
conclude that S is also exchangeable for U; (Veatab U Vieu).
A.2 Proof of Proposition? 2
Lemma stated in Proposition 2, we have
Uu 2 (1 Eg(
EsIE (xxw)a))
maz) denotes the maximum predicted probability of nodes whose ground-truth labels k tgi reflects the model's 's error in misclassifying the ground-truth label &. as label and & E [0, is a uniformly distributed random variable.
where E& (
Proof of Lemma 1. Here, APS non-conformity scores the basic non-conformity scores. Then we have,
S., Σ
T T(mu))I(T<Rw)) > (( + TTx.).
Suppose T is the number of nodes whose ground-truth label is label k. Below discuss two cases of π (x:.):
Case a. If (xxx); ; is the largest predicted probability for node then [S.. = E π (x.)))
Eg [ (xxw)aal Eg (xx.) Fg [TT (mr))aa)) Suppose the number nodes satisfying this case is A.
Case b. Otherwise, [S mi > Eg [T(T(( [ITT( + E&[e (x))))). Suppose the number of nodes satisfying this case is B, where A + B = TT
Therefore, summing up S ui] for both cases, have
A [S.r + B F. s.d] 2 (A + B mar)] + Ex T (x.)d) - A E& (x.))mas)
This simplifies to: E& (S.)) 2 Ex |T ma)) + E& [S (xx));) - 4 (x mmz)
Let εii A, which reflects the model's error in misclassifying the ground-truth label as label i. Therefore, conclude that: E& [..) 2 (1 Bx maz] Ex (x).).).
Proof of Proposition 2. conformity scores in the calibrated set" as "the quantile score". Let S and denote APS and SNAPS non-conformity scores, respectively. For node v whose label is k; S, can be be expressed as
For the sake of description, we denote "1 - a quantile of basic non-
=
A
Σ S..
(6)
VE
NEV.
where V& denotes the nodes set where nodes' ground-trumt label ks because regardless of whether high feature similarity nodes or one-hop structural neighbors, the purpose of aggregating these nodes' scores actually to aggregate, as much as possible, non-confornity scores of nodes with the same label as the ego node.
14

---

In order to prove Proposition 2, we only need to prove the following: 1) SNAPS is efficient for the score corresponding to the ground-truth label k of node 1, i.e., S. Suk or S.k S 2) SNAPS is efficient for the score corresponding to the other label i of node u, i.e, S. 2 S or S. 2 1) The key idea behind this is as follows. We try to ensure that scores corresponding to the ground-trute label are below the quantile score or decrease compared to the before and scores corresponding to the other label are above the quantile score or increase compared to the before.
Firstly SNAPS is efficient for the score corresponding to the ground-truth label of node v, i.e.
Suk S Sok S.k S 1). Here we have
Suk = -1- -) + [Su)
If Sf 2 (rt( then
Suk Sbk = -1-A)Ssux + A Sek
--A(S Ex(S
5..
Thus, Suk S Sok. This means that SNAPS can decrease some scores corresponding to the ground- truth label, bringing them from above the quantile score to below it. Since false scores corresponding ground-trume labels will decrease, r) 1). where v denotes a quantile of SNAPS scores in the calibrated set.
2) If S.k E& (.t)) then
S = - A)S + +EE
< (1 - [Sk + XE
Eg [uk
17.
Thus, S.x < This means that for original scores less than the quantile score, they are still less than the quantile score after aggregation.
Secondly SNAPS is efficient for the score corresponding to the other label of node e, i.e., S.. 2 Sws or S.t 2 1). Here we have
- -1- + [Su]
1) If S.. S [ui). then
S Sui (1 A)S v2 + XE [un) Sus
~ - [.().,))
2 0.
Thus, S.s 2 Sps- This means that SNAPS can increase some scores corresponding to the other labels, bringing them from below the quantile score to above it.
2) If S.. > [ then
Sm (1 - A)S + [S.s]
Et[Sut] 17
2 (1 c+:) Eg iT (Z manl + Es [ (T
LE π (x.)).) A S O, then S., - > 0. Otherwise, since εд: reflects the model's is error in misclassifying the ground-truth label label and n, A is very small, which implies that the probability of S., is very low. Therefore, scores corresponding to other false labels may be corrupted, the probability of S., n is very high.
Let A = 1- - -1- (1_()_))))
though some
Finally [[[((=)]] < [[[(())]].
15

---

B Algorithm overview
The pseudo-code for SNAPS presented in Algorithm First, we preprocess the feature matrix to obtain the similarity graph. Then, treat the GNNs model as black box to generate node embeddings. Finally, we perform conformal prediction using SNAPS.
Algorithm 1 Conformal prediction with SNAPS for GNNs pseudo-code
Input:
Graph 9 = {V, J feature matrix X, label set V adjacency matrix A GNNs Model activation function
basic score function 8, SNAPS score function 3
Calibration data set Daalib {2,, 1,)] test node Un++
Significance level
1: Preprocessing:
construct similarity graph A, based node features
Train GNNs model f(g. X)
2: Ve; V. P;
(x++)
3: Ve; E V, vk E V/ compute Sik = s(P k)
4: Ve, E Venth U {Pa+th. compute S; = S(S;, A.)
5: Sort all SNAPS scores S = ( 1.
6: Set q == Quantile( [[1 [11-a)n+1]l.
7: vk V. compute Sut1k = ((s(Int1,k), A.)
8: return (mn+1)) (k|S $}
B.1 Time Complexity
The time complexity of SNAPS primarily determined by the computation of corrected scores. In this work,
one-hop nodes and nodes with high feature similarity to correct the ego node. In the transductive setting, this complexity applies to the entire graph. Consequently, one-hop generalization requires (EE) runtime, while k-NN generalization requires O(N (MN,M, where E the number of edges, N is the number of test nodes, M is the number of nodes sampled to correct the scores of test nodes, with M < N for large graphs. For example, we randomly sample M 80, 000 nodes from the original set of 2,449,029 nodes in the OGBN Products dataset. Finally, the time complexity of SNAPS is OEE M).
Time complexity of k-NN. Calculating pairwise similarities is inherently parallelizable, which significantly enhances the efficiency of k--N. Furthermore, there have been some approximation methods that could be used to significantly speed up the computation for large graphs, such as NN-Descent (Dong et al., 2011) that can be easily implemented under MapReduce, achieving an approximate N--N graph in 1111.14) empirically.
C Additional Experiments and Experimental Details
C.1 Experiments on heterophilous graph datasets
To analyze the performance SNAPS on heterophilous networks, we conduct experiments on two common heterophilous graph datasets. Detailed statistics of two datasets are shown in Appendix F.
We choose FSGNN (Maurya et al., 2022) as the GNN model. We adopt the dataset splits of Geom- GCN (Pei et al., 2020), i.e. splitting nodes into 60%/20% /00% for rraining/validation/essigg To evaluate the performance of the CP methods, we divide the test set equally into the calibration and evaluation sets. For DAPS, we set À = 0.5. For SNAPS, we set À 0.5, μ 0, and & = 20. i.e., neglecting the structural neighborhood. To construct a cosine similarity-based k--N graph for two heterophilous datasets, we utilize the embeddings from FSGNN. In Table 5, empirical results at = and 0.15 are presented. The experimental results show that SNAPS consistently outperforms the baselines heterophilous networks.
16

---

Table 5: Results of Coverage, Size on two heterophilous graph datasets. We report the average calculated from FSGNN with 100 conformal splits at different significance levels (a 0.05, 0.1). Bold numbers indicate optimal performance.
Datasets
Accuracy
Coverage
Sizel
Coverage
Size].
APS
DAPS
SNAPS
APS
DAPS
SNAPS
DAPS
SNAPS
APS
DAPS
SNAPS
Chameleon
78.0940.95 93
0.904
0.905
0.904
1,95
2.75
1,70
0,850
0.853
0.851
1.62
2.23
1.32
Squireel 73.7242.19 19
0.900
0.897
0,900
2,41
3.05
2.27
0.851
0.848
0.850
1.89
2.37
1.64
Discussion on heterophilous graph datasets. In this work, we utilize the embeddings from FSGNN to construct the similarity graph. Although this serves simple workaround for heterophilous graphs, does not effectively address the core issue in heterophily, where the expectation is that the embeddings would effectively capture the heterophilous networks. Therefore, we plan to construct the similarity graph based solely on graph structure and node features to enhance the performance of SNAPS in future work.
C.2 Comparison with CF-GNN
To compare with CF-GNN, we randomly select 20 nodes per class for training/validation. setting the calibration set size to 1,000 (Huang et al., 2023b). The APS scores are used as the basic non- conformity scores. The average results are calculated from 10 GCN with each trial of 100 conformal splits. Moreover, introduce new metric, i.e., Time, evaluate the running time for each trial. As shown in Table 6, SNAPS outperforms CF-GNN both metrics.
Table 6: Results of Size, Time on three graph datasets for CF-GNN and SNAPS. We report the results at different significance levels 0.05, 0.1). Bold numbers indicate optimal performance.
Size at 0.05
Size
0.1
Time
Datasets
CF-GNN
SNAPS
CF-GNN
SNPAS
CF-GNN
SNAPS
CoraMI. 2.60
1.68
1.68
1.31
142s
0.73s
PubMed
2.13
1.62
1.86
1.35
148s
0.98s
CiteSeer
3.07
1.84
1.96
1.39
124s
0.71s
D Detailed Results
In this section, we report the detailed experimental results. Firstly, we report the results of Coverage, Size, SH across different datasets using different GNNs models in Table 7, Table 8, Table 9, Table 10. Then, we report the results Coverage, Size, SH using RAPS as the basic non-conformity scores in Table 11. Finally, added two additional datasets CiteSeer and Amazon Computers observe changes in the distribution of mean scores for each label in Figure 5 and Figure The results show that SNAPS achieves superior performance.
E Experiments on Image Classification
To verify that our method could be adapted to image classification problems, we test SNAPS on ImageNet and various models. We split the test dataset containing 50000 images into 25000 images for the calibration set and 25000 images for the test set. The models are pretrained Imagenet classifiers from the torchvision repository (Paszke et al., 2019) with standard normalization, resize, and crop parameters. Moreover, all models are calibrated by the Temperature scaling procedure (Guo et al., 2017) on the calibration set. All experiments are conducted with ten trials, and the mean results are reported.
We use size-stratified coverage violation (SSCV) (Angelopoulos al., 2021) measure how pre- diction sets violate the conditional coverage. Specifically, considering disjoint set-size strata [S.) where U. St 21, ./I]. Then, we define the indexes of examples stratified by
17

---

Table Results of Coverage, Size, SH on different datasets, For SNAPS we use the APS score as the basic score. We report the average calculated from 10 GCN trials with each trial of 100 conformal splits at a significance level 0.1. Bold numbers indicate optimal performance.
Coverage
Sizel
SH%?
Datasets
APS
RAPS
DAPS
SNAPS
APS
RAPS
DAPS
SNAPS
APS
RAPS
DAPS
SNAPS
CoraML
0.900
0.901
0.900
0,900
1.81
1.43
1.41
1.31
54.96
56.87
65.21
69.10
PubMed
0.900
0.900
0.900
0.900
1.48
1.43
1.44
1.35
49.61
51.36
52.58
59.14
CiteSeer
0.900
0.900
0.900
0,900
1.85
1.46
1.43
1.39
57.86
57.17
70.11
72.56
CoraFull
10.70
16.31
18.04
15.92
CS
0.900
0,900
0.900
0.899
1.48
1.00
1.09
1,02
71.31
89.72
83.69
88.29
Physics
0.900
0.900
0.900
0,900
1.15
1.00
1.03
1.01
78.98
89,92
87.17
88.82
Computers
0.900
0.901
0.900
2.18
1.66
1.53
1.52
41.30
41.17
64.03
61.81
Photo
0:901
0,900
0.900
0,900
1.48
1.04
1.17
1.13
64.20
86,93
84.04
82.01
Arxiv
0.899
0.900
0.899
0,900
2.81
2.12
2.66
2.30
32.83
17.00
37,60
35,24
Products
0.900
0.900
0.900
0.900
6.49
3.91
3.62
3.27
34.03
21.26
48.90
44.64
Average
0.900
3.143
2.055
2.201
50.139
51.327
61.137
61.753
Ground-truth labe!
False label
Other label
Quantile score
1.00
APS scores
0.75
0.50
0.25
0.00
Node Labels
(a) APS: average Size
SNAPS scores
0.8
0.2
0.0
Node Labels
(b) SNAPS: Size 1.33
Figure 5: The average non-conformity scores of nodes belonging to each label based on the model GCN for dataset CiteSeer.
the prediction set size by Jj = {i: [C(::) E Sz}. Formally, define the SSCV as:
[ J, Ui C (xx)) -1 a))
SSCV sup
JT
where a is the significance level. In our experiments, we follow the setting of RAPS (Angelopoulos al., 2021), choosing relatively coarse partitioning of the possible set sizes: 0-1, 2-3, 410, 11-100, and 101-1000.
More Details on Dataset and Models
Table 12 displays the statistics of the dataset used for the evaluation. For CoraFulll remove the
classes (and the respective nodes) that have number of instances less than 50 in order to have the same number nodes per class in each train/validation split (Zargarbashi al., 2023). Table 13 summarizes the model's accuracy on every dataset.
18

---

Table 8: Results of Coverage, Size, SH on different datasets. For SNAPS we use the APS score as the basic score. We report the average calculated from GAT trials with each trial of 100 conformal splits at different significance levels (a 0.05, 0.1). Bold numbers indicate optimal performance.
Coverage
Sizel
SH&F
Datasets
APS
RAPS
DAPS
SNAPS
APS
RAPS
DAPS
SNAPS
APS
RAPS
DAPS
SNAPS
0.06
CoraML
0.950
0.950
0.950
0.950
2.91
2.75
2.31
1.92
30.82
15.54
41.45
46.51
PubMed
0.950
0.950
0,950
0.950
1.83
1.82
1.79
1.70
30.00
23.83
32.55
37.22
CiteSeer
0.950
0.950
0.950
0.950
2.61
2.58
2.18
2.08
38.82
32.87
49.43
51,25
CoraFull
0.950
0.950
0.950
0,951
25.38
17.13
17.43
13.80
2.85
0.43
2.77
1.97
CS 0.950
0.950
0.950
0,950
2.62
1.59
1.50
1.14
46.99
44.22
67.28
83,29
Physies
0.950
0.950
1.53
1.24
1.13
1.05
62.54
75.56
83.82
90.40
Computers
0.950
0.950
0.950
0,950
3.18
3.08
2.30
2.10
24.56
13.65
40.05
39.51
Photo
0.950
0.950
0.950
0,950
1.89
1.59
1.42
1.30
52.10
50.83
72.02
75.43
Average
0.950
0.950
0.950
0.950
5.244
3,973
3.758
3.136
36.085
32.116
48.671
53.198
0.1
CoraML
0.900
0.900
0,900
0.900
2.18
1.82
1.66
1.47
42.71
37.79
55.74
61.05
PubMed
0.900
0.900
0.900
0.901
1.54
1.49
1.48
1.40
44.96
45.39
49.59
54.71
CiteSeer
0.900
0.900
0.900
0.9001
2.05
1.59
1.63
1.56
49.10
50144
61.0N 018
63.85
CoraFull
0.900
0.900
0.900
0.900
15.71
9.63
10.80
8.81
5.84
0.83
6.12
4.96
CS
0.900
0.900
0.899
1.90
1.10
1.21
1.04
57.68
81.9
76.72
86.89
Physics
0.900
0.900
0.901
0.900
1.30
1.01
1.05
1.022
69.42
88.92
85.74
88.39
Computers
0.900
0.900
0.900
0,900
2.15
1.82
1.66
1.60
41.43
42.13
58.05
56.54
Photo
0.900
0.900
0.900
0.901
1.48
1.07
1.21
1.15
63.36
84.31
80.94
80.16
Average
0.900
0.900
0,900
0.900
3.539
2,441
2.588
2.256
46.813
53.964
59.248
62.069
Table 9: Results of Coverage, Size, SH on different datasets. For SNAPS we use the APS score the basic score. We report the average calculated from 10 APPNP trials with each trial of 100 conformal
splits at different significance levels (a 0.05, 0.1). Bold numbers indicate optimal performance.
Coverage
Sizel
SH
Datasets
APS
RAPS
DAPS
SNAPS
APS
RAPS
DAPS
SNAPS
APS
RAPS
DAPS
SNAPS
0.05
CoraML
0.950
0.950
0.950
0.950
2.20
2.01
1.78
1.66
46.85
27.70
$5.12
54.74
PubMed
0.950
0.950
0.950
0.950
1.75
1.75
1.74
36.42
32.58
36.79
41.25
CiteScer
0.950
0.950
0.950
0.950
2.18
2.22
1.88
1.86
54.08
34.40
61.85
59.74
CoraFulll
0.950
0.950
0.950
0.950
14.91
9.83
11.90
9.78
10.62
2.36
8.15
4.13
CS
0.950
0.950
0.951
0.950
1.64
1.16
1.21
1.08
70.22
80.86
79.91
88.02
Physics
0.950
0.950
0.950
0,950
1.24
1.05
1.07
1.03
78.71
90.86
89.24
92.38
Computers
0.950
0.950
0.950
0.950
2,90
2.81
2.08
2.01
31.85
20,80
46.41
42,91
Photo
0.950
0.950
0.950
0.950
1.69
1.42
1.38
1.31
60.31
67.94
75.01
76.13
Average
0.950
0.950
0.950
0.950
3.564
2.781
2,880
2.550
48.633
44.688
56,560
57.413
0.1
CoruML
0.900
0.900
0.900
0.901
1.73
1.37
1.37
1.30
55.15
58.92
66.84
69.33
PubMed
0.900
0.900
0.900
0.900
1.44
1.41
1.41
1.34
53.34
52.90
55.80
59.92
CiteSeer
0.900
0.900
0.900
0.900
1.70
1.28
1.39
1.38
62.50
69.73
72.18
72.71
CoraFull
0.900
0.900
0.900
0.900
8.39
5.21
6.03
5.05
18.43
3.43
16.89
14.44
CS
0.901
0.900
0.901
1.34
1.00
1.08
1.01
74.42
89.70
84.28
88.75
Physics
0.900
0.900
0.900
0.900
1.13
1.00
1.02
1.01
80.36
90.00
88.05
89.42
Computers
0.900
0.900
0.900
0,900
1.96
1.56
1.50
1.48
47.78
50.06
65.94
63.93
Photo
0.900
0.900
0.900
0.900
1.39
1.06
1.19
1.14
67.47
85.46
82.26
81.42
Average
0.900
0.900
0.900
0.900
2.385
1.736
1.874
1.714
57.431
62.525
66.530
67.490
19

---

Table 10: Results of Coverage, Size, SH on different datasets. For SNAPS we use the APS score as the basic score. We report the average calculated from 10 MLP trials with each trial of 100 conformal splits at different significance levels (a 0.05, 0.1). Bold numbers indicate optimal performance.
Coverage
Sizel
SH%T
Datasets
APS
RAPS
DAPS
SNAPS
APS
RAPS
DAPS
SNAPS
APS
RAPS
DAPS
SNAPS
0.05
CoraMI
0.950
0.950
0.950
0.950
4.21
4.22
3.04
2.68
6,85
6.16
16.63
22.28
PubMed
0.950
0.950
0.950
2.09
2.06
1.85
18.94
7.91
21.02
27.57
CiteSeer
0.950
0.950
0.950
0,950
4.08
4.13
3.33
3.18
11.20
10.20
17.75
21.81
CoraFull
0.950
0.950
0.950
0.950
25.36
26.40
16.36
16.44
0.00
0.00
0.00
0.00
CS
0.950
0.950
4.36
1.57
1.69
42.01
61.93
74.87
Physics
0.950
0.950
0.950
0,950
2.00
1.62
1.19
1.12
44.98
45.63
80.08
84.63
Computers
0.950
0.950
0.950
0.950
5.35
5.34
3.97
3,99
2.35
2.14
4.79
4.48
Photo
0.950
0.950
3.20
3.12
2.12
38.22
36,91
Average
0.950
0.950
0.950
0,950
6.331
6.058
4.214
4.091
16.909
15.589
30.053
34,069
0.1
CoruML
0.900
0.901
0.900
0,900
3.20
3.23
2.17
1.93
14.10
11.16
31.24
37.95
PubMed
0.900
0.900
0.901
0.900
1.77
1.71
1.69
1,53
31.03
26.82
35.10
43.78
CiteSeer
0.900
0.901
0.900
0.900
3.28
3.30
2.55
21.22
19.07
28.64
34.40
CoraFull
0.900
0.900
0.900
16.34
16.35
10.27
10.31
0.00
0.00
0.00
CS
0.900
0.900
0.900
0.900
3,08
1.13
1.32
1.10
40.97
78.73
71.64
82.36
Physics
0.900
0.901
0.900
0.900
1.62
1.19
1.07
1.03
54.04
75.65
84.02
87.12
Computers
3,90
2.75
16.75
Photo 0.900
0.901
0.900
0.900
2.46
2.02
1.60
1.61
27.68
19.72
54.38
53,70
Average
0.900
0.901
0.900
0,900
4,456
4.088
2.928
2.828
24.539
29.530
40.264
44.508
Table 11: Results of Coverage, Size, SH different datasets. For SNAPS the RAPS the basic score. We report the average calculated from 10 GCN trials with each trial of 100 conformal splits at different significance levels (a 0.05, 0.1). Bold numbers indicate optimal performance.
0.1
0.05
Dutasets
Coverage
Sizel
SHS1
Coverage
Sizel
SHS?
RAPS
SNAPS
RAPS
SNAPS
RAPS
SNAPS
RAPS
SNAPS
RAPS
SNAPS
RAPS
SNAPS
CoraML
0.901
0.900
1.43
1.34
56.87
61.43
0.950
0.950
2.21
1.94
22.19
33,05
PubMed
0,900
0.900
1.43
1.38
51.36
55.29
0.950
0.950
1.77
1.64
30.83
40.39
CiteSeer
0.900
0.900
1.46
1.36
57.17
64.44
0.950
0.950
2.36
2.02
38.99
48.14
CoraFull
0.900
5.48
1.39
0,950
10.70
0.99
CS
0.900
0.900
1.00
1.00
89.72
89.83
0.950
0.950
1.20
1.10
78.34
85.05
Physics
0.900
1.00
0.949
1.04
91.47
Computers
0.901
0.901
1.66
1.53
41.17
48.42
0.950
0.950
2.89
2.22
15.85
28.61
Photo
0.900
0.900
1.04
1.03
86.93
86.97
0.950
0.949
1.64
1.63
56.63
51.34
Arxiv
0.901
2.17
13.85
0.950
0.950
3.61
14:52
14,59
Products
0,900
0.901
3.91
3.48
21.26
21.04
0.951
0.951
13.67
7.77
11.51
23,30
Average
0,900
0.900
2.055
1,977
51.327
53.266
0.950
0.950
4.115
3.367
35.988
41.693
Table 12: Statistics the ten datasets.
Datasets
Nodes
Features
Edges
Classes
Homophily
CoraMI.
2995
2879
16316
7
78.85%
PubMed
19717
500
88648
3
80.23%
CiteSeer
4230
602
10674
94.94% 6
CoraFull
19749
8710
126524
68
56.76%
Coauthor CS
18333
6805
163788
80.80% 15
Coauthor Physics
34493
8415
495924
93.14% 5
Amazon Computers
13752
767
491722
10
77.72%
Amazon Photo
7650
745
238162
8
82.72%
OGBN Arxiv
169343
128
1166243
40
65.51 %
OGBN Products
2449029
100
123718280
49
80.75%
Chamelcon
2277
2325
36101
5
23%
Squirrel
5201
2089
217073
5
22%
20

---

Ground-truth label
False label
Other label
Quantile score
1.00
APS scores
0.50
0.25
0123456788
6 7 0008
2 6
01
Node Labels
1.00
APS scores
0.50
0.25
2 3
6 8
0123456788
0123456701
0123
Node Labels
(a) APS: average Size 4.7
SNAPS scores
0.75
0.25
0 3
7689
0123456789
0 0 6
0 4
0123456889
7
Node Labels
1.00
SNAPS
0.50
0.25
0.00
012345 8123456722
Node Labels
(b) SNAPS: Size 1.7
Figure 6: The average non-conformity scores of nodes belonging to each label based on the model GCN for dataset Amazon Computers.
Table 13: Accuracy report for datasets and models involved in the analysis.
Dataset
GCN
GAT
APPNP
MLP
CoraML
81.48+1.80
79.09+2.44
12.12
62.82+1.85
PubMed
1,.90+1.89
75.61+2.75
77.97+2.12
69.56*1.62
CiteSeer
83.90+1.04
83.03+0.80
84.91=0.74
62.67=1.
CoraFull
60.53+0.62
50.1940.74
61.08+0.48
38.06+0.65
CS
91.24+40.40
88.01+1.04
91.40=0.46
88.06+0.57
Physics
93.1140.60
91.12+1.52
93.66+0.48
86.93+1.20
Computers
81.05+1.70
77.78+2.29
81.36+1.85
59.4943.73
Photo
89.64+1.21
88.4940.90
89.69+2.19
74.4143.68
Arxiv
70.53
Products
75.44
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clearly state the claims, including the contributions and important assump- tions and limitations in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations in the conclusion and discuss the computational efficiency the appendix.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
22

---

Answer: [Yes]
Justification: We propose the propositions in the Motivation and Methodology section and provide the proofs in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We detail the experiment settings in the section Experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
23

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provide the whole code the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nipp cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//niss httppsccccpbccccccceececcccccccc htt.g/eeede/eeeeeeiiiaeeeeee /Cooeeeooiissseeeeeee wwsssonoolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
We specify all the training and test details in the section Experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Due to the limited width of the paper and our focus the average size in the statistics, we do not report error bars in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Each experiment is done with a single NVIDIA V100 32GB GPU.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that NeurIPS Code of Ethics https: / /nwuriss.sp.. cc cccppbbicc/eeeeeeeceeeeeeeeeeeee ctwp::/eeeecciiueeeeeeeeeeeeeee
didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification:
We strictly conform with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work a foundational research and is not tied to particular applications.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
25

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We properly credited the creators. We explicitly mention and properly respect the license and terms of use.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
26

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "hYIpJH7fjL", "reviewer": "Reviewer_8yy7", "summary": "The authors apply conformal prediction to graph neural networks by aggregating the non-conformity scores based on both one-hop neighbors and feature similarity. The framework is verified through various experiments on graph ML benchmark datasets, where it's shown to generate smaller prediction sets and higher singleton hit ratio (i.e. only the correct answer in the set).", "questions": "I think it's possible that this method could more strongly outperform DAPS in heterophilous networks due to the addition of the term that doesn't depend on neighbors. Is there any chance the authors have tested their methods on a heterophilous network or observed any dependency of the performance on the degree of homophily?", "limitations": "yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is clearly presented and the results are fairly intuitive. It builds upon DAPS by adding a feature similarity term in eq (4). The experimental section is comprehensive in terms of number of datasets, ablation studies and parameter analysis.", "weaknesses": "One suggestion is to add a discussion on the assumptions in Proposition 2 and a proof sketch (if possible). For example, what does \"$\\Delta$ very small\" really mean and how reasonable is it?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's recognition and valuable suggestions. Please find our response below:\n\n> **1. Discussion regarding the assumption in Proposition 2 [W1]**\n\nThank you for the great suggestion. Here is our discussion regarding the assumption in Proposition 2.\n\nGiven a data pair $(\\boldsymbol{x},y)$ and a model $f(\\boldsymbol{x})$, we define a predicted probability estimator as $\\pi(\\boldsymbol{x})\\_y$, where $\\pi(\\boldsymbol{x})\\_y:=\\sigma(f(\\boldsymbol{x}))$ represents the predicted probability for label $y$ and $\\sigma(\\cdot)$ is an activation function, such as softmax. Let $\\boldsymbol{S}$ denote APS scores of nodes, then we have\n$$\\begin{aligned}\\boldsymbol{S}\\_{ui}=\\sum\\_{j=1}^{|\\mathcal{Y}|}\\pi(\\boldsymbol{x}\\_u)\\_j\\mathbb{I}[\\pi(\\boldsymbol{x}\\_u)\\_j>\\pi(\\boldsymbol{x}\\_u)\\_i]+\\xi\\cdot \\pi(\\boldsymbol{x}\\_u)\\_i,\\end{aligned}$$ where $\\boldsymbol{S}\\_{ui}\\in[0,1]$ is the score corresponding to node $u$ with label $i$, and $\\xi\\in[0,1]$ is a uniformly distributed random variable. Let $E\\_k[\\boldsymbol{S}\\_{ui}]$ be the average of scores corresponding to label $i$ of nodes whose ground-truth label is $k$. Suppose $T$ is the number of nodes whose ground-truth label is label $k$.\n\n**a.** If $\\pi(\\boldsymbol{x}\\_u)\\_i$ is the largest predicted probability for node $u$, then $E\\_k[\\boldsymbol{S}\\_{ui}]=E\\_k[\\xi\\cdot \\pi(\\boldsymbol{x}\\_u)\\_i]=E\\_k[\\pi(\\boldsymbol{x}\\_u)\\_k]+E\\_k[\\xi\\cdot \\pi(\\boldsymbol{x}\\_u)\\_i]-E\\_k[\\pi(\\boldsymbol{x}\\_u)\\_k]$. Suppose the number of nodes satisfying this case is A.\n\n**b.** Otherwise, $E\\_k[\\boldsymbol{S}\\_{ui}]\\geq E\\_k[\\pi(\\boldsymbol{x}\\_u)\\_k]+E\\_k[\\xi\\cdot \\pi(\\boldsymbol{x}\\_u)\\_i]$. Suppose the number of nodes satisfying this case is B, where $A+B=T$. Therefore, summing up $E\\_k[\\boldsymbol{S}\\_{ui}]$ for both cases, we have\n$$A\\cdot E\\_k[\\boldsymbol{S}\\_{ui}]+B\\cdot E\\_k[\\boldsymbol{S}\\_{ui}]\\geq (A + B)\\cdot (E\\_k[\\pi(\\boldsymbol{x}\\_u)\\_k]+E\\_k[\\xi\\cdot \\pi(\\boldsymbol{x}\\_u)\\_i])-A\\cdot E\\_k[\\pi(\\boldsymbol{x}\\_u)\\_k], $$\n\ni.e., \n$$E\\_k[\\boldsymbol{S}\\_{ui}]\\geq E\\_k[\\pi(\\boldsymbol{x}\\_u)\\_k]+E\\_k[\\xi\\cdot \\pi(\\boldsymbol{x}\\_u)\\_i]-\\frac{A}{T}\\cdot E\\_k[\\pi(\\boldsymbol{x}\\_u)\\_k].$$\n\nLet $\\epsilon=\\frac{A}{T}\\cdot E\\_k[\\pi(\\boldsymbol{x}\\_u)\\_k]$, which reflects the average error of misclassifying label $k$ as label $i$. Let $\\eta$ be $1-\\alpha$ quantile of APS scores with a significance level $\\alpha$. Then we have\n$$\\begin{aligned}\\eta=(1-\\alpha)\\frac{1}{|\\mathcal{Y}|}\\sum\\_{j=1}^{|\\mathcal{Y}|} E\\_j[\\pi(\\boldsymbol{x}\\_u)\\_j].\\end{aligned}$$ We can set $\\eta - E\\_k[\\boldsymbol{S}\\_{ui}]=\\Delta$. If $\\Delta\\leq 0$, then $\\eta \\leq E\\_k[\\boldsymbol{S}\\_{ui}]$, which means $\\hat{\\boldsymbol{S}}\\_{vi}>\\eta$ holds in Subsection A.2 of the manuscript. If $\\Delta > 0$, then we have\n$$0<\\Delta=\\eta - E\\_k[\\boldsymbol{S}\\_{ui}]\n\\leq \\eta - E\\_k[\\pi(\\boldsymbol{x}\\_u)\\_k]-E\\_k[\\xi\\cdot \\pi(\\boldsymbol{x}\\_u)\\_i]+\\epsilon.$$\n\nThe upper bound of $\\Delta$ is given here. In most cases, $\\eta\\leq(1-\\alpha)E\\_k[\\pi(\\boldsymbol{x}\\_u)\\_k]$ or $\\eta\\approx(1-\\alpha)E\\_k[\\pi(\\boldsymbol{x}\\_u)\\_k]$, and then $0<\\Delta<-\\alpha E\\_k[\\pi(\\boldsymbol{x}\\_u)\\_k]-E\\_k[\\xi\\cdot \\pi(\\boldsymbol{x}\\_u)\\_i]+\\epsilon$. Since $\\epsilon$ reflects the average error of misclassifying label $k$ as label $i$, '$\\Delta$ very small' is reasonable.\n\n\n> **2. Performance on heterophilous networks and dependency of the performance on the degree of homophily [Q1]**\n\nWe thank the reviewer for this intriguing question. To analyze the performance of SNAPS on heterophilous networks, we conduct the experiments on two common heterophilous graph benchmarks. The benchmarks' details are as follows:\n\n| Datasets | Nodes | Features | Edges | Classes | Homophily Ratio |\n| :--: |:--: |:--: |:--: |:--: |:--: |\n| Chameleon | 2,277 | 2,325 | 36,101 | 5 | 0.23 |\n| Squirrel | 5,201 | 2,089 | 217,073 | 5 | 0.22 |\n\nWe choose FSGNN [1] as the GNN model. We adopt the dataset splits of Geom-GCN [2], i.e. splitting nodes into 60%/20%/20% for training/validation/testing. To evaluate the performance of the CP methods, we divide the test set equally into the calibration and evaluation sets. For DAPS, we set $\\lambda=0.5$. For SNAPS, we set $\\lambda=0.5, \\mu=0$ and $k=20$, i.e., neglecting the structural neighborhood. To construct a cosine similarity-based k-NN graph for these two heterophilous datasets, we utilize the embeddings from FSGNN. In the following tables, empirical results at $\\alpha=\\{0.10, 0.15\\}$ are presented respectively:\n\n| | FSGNN |Coverage |  | |Size |  | |\n| :--: |:--: |:--: |:--: |:--: |:--: |:--: |:--: |\n|Datasets | Accuracy | APS | DAPS | SNAPS | APS | DAPS | SNAPS\n|Chameleon| 78.09±0.93 | 0.904 | 0.905 | 0.904 | 1.95 | 2.75 | **1.70** |\n|Squirrel| 73.72±2.19 | 0.900 | 0.897 | 0.900 | 2.41 | 3.05 | **2.27**|\n\n| |Coverage |  | | Size |  | |\n| :--: |:--: |:--: |:--: |:--: |:--: |:--: |\n|Datasets | APS | DAPS | SNAPS | APS | DAPS | SNAPS\n|Chameleon| 0.850 | 0.853 | 0.851 | 1.62 | 2.23 | **1.32** |\n|Squirrel| 0.851 | 0.848 | 0.850 | 1.89 | 2.37 | **1.64**|\n\nWe can observe that SNAPS still shows **consistent superiority** over the baselines on heterophilous networks, which demonstrates its weak dependence on homophily.\n\n[1] Improving Graph Neural Networks with Simple Architecture Design. arxiv'21.\n\n[2] Geom-GCN: Geometric Graph Convolutional Networks. ICLR'20.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "64dac7r8k2", "reviewer": "Reviewer_aWFN", "summary": "The authors propose a new score function for conformal predictions on graphs. Given any baseline score the new score is aggregated based on the neighbors in the given graph; and the neighbors from a secondary kNN graph constructed based on the similarity between input features. The approach is motivated by noticing that augmenting the neighborhood of a node with other nodes from the same class improves performance.", "questions": "1. In Figure 1a) you show that the set size decreases as you increase the number of nodes with the same (oracle) label. This is effectively adding additional edges between nodes from the same class before the aggregation, increasing the homophily. This will likely increase the accuracy of the underlying model which non-surprisingly leads to reduced set size. How does the accuracy change if you e.g. take the argmin of the aggregated APS scores as a prediction or e.g. do vanilla GNN prediction on the augmented graph?\n2. CF-GNN (Huang et al., 2023b) can in principle learn to do a similar aggregation to the one your propose. Can you please compare with them?\n3. How does the performance of SNAPS (and the baselines) change as you vary the calibration set size? Importantly, also for small (realistic) sizes.\n4. How does the performance of SNAPS (and the baselines) change as you vary the significance level $\\alpha$?\n5. What are the optimal h-params for different datasets and is there a good default value that works for most datasets? Relatedly, how does Figure 4c and 4d look like for other datasets?\n6. Have you considered other similarity metrics?", "limitations": "The approach is likely to only work for graphs that have homophily (similar to DAPS). While this often holds for graphs of interest in practice, clearly highlighting this as a limitation would be appreciated.", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The approach is well motivated and the proposed score is simple and intuitive which is a pro.\n\nWhile I think the experimental evaluation can be improved (see weaknesses and questions) the experiments that are carried out are well described, thorugh, and help to support the claims made in the paper.", "weaknesses": "The calibration set size of $\\min\\\\{1000, |V_{calib} \\cup V_{test}|/2\\\\}$ seems problematic. For example, for Cora with 20 labels per class we have 20*7=140 labels for training/validation set. This means that a calibration set with size 1000 has an order of magnitude more labels. In practice it is much more likely to use most of the labels for training rather than calibration. At the very least results should be reported where the calibration set size is the same as the training/validation set size. Similarly, for ImageNet, equally dividing the data into a calibration set and a test set is not realistic.\n\nIn practice we either need to use fixed hyper-parameters or split the calibration set into 2 subsets: one for calibrating and one for tuning h-params. The authors do not discuss this issue (see also question 5).\n\nThe similarity graph is constructed based on a single heuristic (cosine similarity between node features). Considering other heuristics would be interesting, especially ones that also incorporate structure information and not only feature information.\n\n\nGiven the simplicity of the approach (which is a plus) the experimental evaluation should be strengthend (see questions).\nI am willing to increase my score if the authors adequately address my questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate the valuable comments and will incorporate these suggestions into the final version. We are certain they will substantially improve the presentation of our work. Please find our response below:\n\n> **1. Calibration set size [W1 & Q3]**\n\nHere, we provide effect analysis of various calibration set sizes:\n\n1. **Same calibration set size as training set.** We conduct experiments where the calibration set size is the same as the training set size (20 per class). Moreover, the calibration set is equally split into two sets: one for tuning h-params of CP methods and one for conformal calibration. SNAPS employs fixed h-params, i.e., $\\lambda=\\mu=1/3$ (A detailed analysis of fixed h-params for SNAPS can be found in Response 2 [W2 & Q5]). Here are the average results on 7 datasets at $\\alpha=0.05$:\n\n||APS/RAPS/DAPS/SNAPS||\n|-|-|-|\n||Size|SH|\n|Average|2.15/2.14/1.86/**1.54**|49.41/37.66/55.07/**65.10**|\n\nThe detailed results can be found in Table 1 of the attachment.\n\n2. **Small calibration set size.** The results of the average size are shown in the following table\n\n|Num.|50|100|200|300|400|\n|-|-|-|-|-|-|\n|APS|2.92|2.50|2.43|2.42|2.39|\n|RAPS|3.12|2.76|2.35|2.33|2.26|\n|DAPS|2.84|2.49|2.06|2.07|1.96|\n|SNAPS|**2.02**|**1.76**|**1.72**|**1.71**|**1.70**|\n\nThe results above both show that **SNAPS consistently outperforms other methods under different calibration set size setups**. \nIn Figure 1 from the attachment, more results on different datasets can be found.\n\nFor the vision dataset ImageNet, we provide the average results across different models for SNAPS and APS in Table 2 of the attachment.\nDespite the small size of calibration set, SNAPS still outperforms APS for classification problems.\n\n\n> **2. Choice of hyper-params [W2 & Q5]**\n\n**Optimal h-params.** In the manuscript, we use a hold-out dataset to tune the h-params, which is a common practice [1]. Here, we report the mean of the optimal h-params for SNAPS on different splits of each dataset.\n\n|Datasets|CoraML|PubMed|CiteSeer|\n|-|-|-|-|\n|$\\lambda$|0.32±0.19|0.24±0.22|0.39±0.21|\n|$\\mu$|0.44±0.13|0.51±0.24|0.27±0.19|\n\n**Good default hyper-params.** Moreover, there exist good default hyper-params for SNAPS on most datasets, i.e., $\\lambda=\\mu=1/3$, which indicates that three components of SNAPS are equally proportioned. The experiment results supporting this conclusion can be found in Response [W1 & Q3].\n\n**How does Figure 4c and 4d look like for other datasets?** We provide experimental results of other datasets in Figure 3 of the attachment.\n\n> **3. Other methods for similarity graph construction [W3 & Q6]**\n\nTo incorporate structural information, we can use self-supervised learning to obtain embeddings of nodes [2]. Then, we use the cosine similarity between node embeddings to construct the similarity graph. To validate this method, we conduct experiments on the self-supervised model GraphACL [2] and follow its experimental setup. The experimental results are as follows:\n\n|SNAPS with|Original/GraphACL|Original/GraphACL|\n|-|-|-|\n|Datasets|$\\alpha=0.05$|$\\alpha=0.10$|\n|CoraML|**1.68**/1.71|1.31/**1.28**|\n|PubMed|1.62/1.62|1.35/**1.31**|\n|CiteSeer|1.84/**1.68**|1.39/**1.23**|\n\nThe results demonstrate that the **similarity graph constructed based on self-supervised learning is applicable to SNAPS**.\n\n> **4. Effect of the aggregated APS scores / the augmented graph on the prediction accuracy [Q1]**\n\nThank you for posing this insightful question. We take the argmin of the aggregated APS scores as a prediction and train vanilla GCN on the augmented graph. The prediction accuracy for these methods is as follows:\n\n|Methods/Datasets|CoraML|PubMed|CiteSeer| \n|-|-|-|-|\n|vanilla GCN|81.48|77.40|83.90|\n|argmin of DAPS|81.25|78.70|83.88|\n|argmin of SNAPS|81.83|79.43|84.08|\n|augmented graph|77.50|75.89|74.31|\n\nThe results indicate that **SNAPS slightly enhances prediction accuracy**, which may be one reason for SNAPS's effectiveness. \n\n\n> **5. Comparison with CF-GNN [Q2]**\n\nTo compare with CF-GNN, we randomly select 20 nodes per class for training/validation and set the calibration set size to 1,000 [3]. The APS score serves as the basic non-conformity score. The average results are calculated from 10 GCN with each trial of 100 conformal splits. Moreover, we introduce a metric, i.e., **Time**, to evaluate the running time for each trial. As shown in the Table below, SNAPS outperforms CF-GNN in both metrics.\n\n|Datasets|Size with $\\alpha=0.05$|Size with $\\alpha=0.1$|Time|\n|-|-|-|-|\n|||(CF-GNN/SNAPS)||\n|CoraML|2.60/**1.68**|1.68/**1.31**|142s/**0.73s**|\n|PubMed|2.13/**1.62**|1.86/**1.35**|148s/**0.98s**|\n|CiteSeer|3.07/**1.84**|1.96/**1.39**|124s/**0.71s**|\n\n\n> **6. Different significance levels $\\alpha$ [Q4]**\n\nHere are the average set size across 10 GCNs with each trial of 100 conformal splits for CoraML at different significance levels:\n\n|Method\\alpha|0.05|0.07|0.09|0.10|0.12|0.14|0.16|\n|-|-|-|-|-|-|-|-|\n|APS|2.42|2.10|1.90|1.81|1.70|1.60|1.52|\n|RAPS|2.16|1.81|1.58|1.43|1.28|1.18|**1.10**|\n|DAPS|1.92|1.66|1.47|1.44|1.32|1.25|1.20|\n|SNAPS|**1.68**|**1.48**|**1.36**|**1.30**|**1.23**|**1.18**|1.14|\n\nThe results demonstrate that SNAPS outperforms other baselines at most significance levels. Additionally, we provide detailed results on PubMed and CiteSeer in Figure 2 of the attachment.\n\n\n> **7. Limitation to homophily**\n\nWe clarify that the proposed method does not depend on homophily. Specifically, we conduct experiments on heterophilous datasets and SNAPS still outperforms baseline methods under low homophily ratio. Details can be found in response 2 to Reviewer 8yy7.\n\n[1] DAPS: Conformal Prediction Sets for Graph Neural Networks. ICML'23.\n\n[2] Simple and Asymmetric Graph Contrastive Learning without Augmentations. NeurIPS'23.\n\n[3] Uncertainty Quantification over Graph with Conformalized Graph Neural Networks. NeurIPS'23.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "9KUfKemJxN", "reviewer": "Reviewer_3cJc", "summary": "This paper introduces a novel algorithm, SNAPS, which enhances conformal predictions by aggregating non-conformity scores based on feature similarity and structural connections. Extensive experiments validate SNAPS' effectiveness, demonstrating its ability to produce more compact prediction sets with higher singleton hit ratios while maintaining rigorous finite-sample coverage guarantees.", "questions": "1. Figure 1c shows that the number of nodes with the same label at the $k$-th nearest neighbors decreases as $K$ increases, but lines 272 -273 claim that more nodes with the same label are selected to enhance the ego node as $k$ increases. Does the explanation in lines 272-273 conflict with the observation in Figure 1c?\n2. As shown in Table 9, the experiments were conducted on homogeneous datasets. Can this approach be extended to heterogeneous datasets? Will using high-similarity nodes for calibration remain effective in such settings?", "limitations": "See the weakness", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is clearly written and well-structured, facilitating easy comprehension.\n2. It offers a new approach by utilizing similarity measurements based on node features to implement Conformal Prediction in node classification tasks, supported by a comprehensive theoretical analysis.\n3. The paper conducts thorough experiments to test the validity of the proposed method, showing consistent improvements across various metrics.", "weaknesses": "1. Computing pairwise similarity is computationally demanding, especially for large-scale graph data.\nAlthough the author notes in Appendix B. 1 that a subset was sampled to reduce computation costs, no details are provided on the sampling method or the size of the sample.\n\n2. According to Figure 1(b), the difference in feature similarity between identical and different labels is minor, which does not convincingly justify the necessity of using feature similarity as an additional calibration method.\n\n3. As shown in Figure 4, the success of this method hinges on the empirical selection of $\\lambda$ and $\\mu$, which restricts its broader application.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's insightful feedback. Please find our response below:\n\n> **1. Sampling method for large-scale dataset [W1]**\n\nTo reduce the computation burden, we utilize a random subset from the original nodes (80,000 / 2449029, OGBN Products). Despite its simplicity and limited access to full datasets, the proposed SNAPS still establishes superior performance without high cost.\n\n\n> **2. Necessity of using feature similarity as an additional calibration method [W2]**\n\nSorry for the misunderstanding caused by the lack of data precision. The features are high-dimensional and sparse in the vector space, leading to minor differences between similarity results. Therefore, we multiply the results shown in Figure 1(b) by 1000 and calculate the difference between the similarity of identical labels and that of different labels in each row, as shown in the following table:\n\n|class|0|1|2|3|4|5|6|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|0|0|25.90|31.38|36.27|35.76|19.08|20.48|\n|1|14.90|0|22.83|23.68|22.33|9.54|11.26|\n|2|22.32|24.76|0|33.78|29.37|20.06|17.36|\n|3|9.75|8.16|16.32|0|12.26|11.82|8.74|\n|4|10.08|7.64|12.75|13.10|0|9.09|4.68|\n|5|15.56|17.02|25.60|34.82|31.25|0|17.40|\n|6|26.01|27.79|31.96|40.80|35.90|26.45|0|\n\nThe table demonstrates that the **relative difference in feature similarity between the identical and different labels is significant**.\n\n> **3. Choice of hyper-parameters $\\lambda$ and $\\mu$ [W3]**\n\nIn the manuscript, SNAPS uses a hold-out dataset to tune the hyper-parameters, which is a common practice [1,2]. However, **there exist good default hyper-parameters for SNAPS** on most datasets, i.e., $\\lambda=\\mu=1/3, k=20$, whose experimental results at $\\alpha=0.05$ are shown in the following: \n\n|||APS/RAPS/DAPS/SNAPS||\n|-|-|-|-|\n|Dataset|Coverage|Size|SH|\n|CoraML|0.950/0.958/0.957/0.951|2.50/2.62/2.32/**1.74**|43.09/27.34/44.52/**54.11**|\n|PubMed|0.950/0.968/0.967/0.950|1.82/2.10/2.09/**1.61**|33.39/14.66/23.27/**44.11**|\n|CiteSeer|0.951/0.950/0.952/0.950|2.41/2.69/2.16/**1.90**|48.53/35.37/55.40/**58.22**|\n|CS| 0.950/0.953/0.954/0.950|2.04/1.31/1.33/**1.13**|64.32/66.91/74.91/**85.21** |\n|Physics|0.951/0.962/0.962/0.950|1.39/1.44/1.28/**1.07**|72.44/62.22/77.65/**88.58**|\n|Computers|0.950/0.950/0.951/0.950|3.01/3.04/2.30/**2.01**|29.21/9.87/42.19/**45.98**|\n|Photo|0.949/0.950/0.950/0.950|1.90/1.81/1.56/**1.30**|54.86/47.27/67.57/**79.50** |\n\nThe results show that SNAPS, with default hyper-parameters, outperforms RAPS and DAPS, even though both baseline methods are tuned on a hold-out dataset.\n\n> **4. Conflict between the explanation in lines 272-273 and the observation in Figure 1c [Q1]**\n\nThank you for pointing the conflict out. There is indeed the ambiguity for the explanation in lines 272-273 of the manuscript. For clarity, we rephrase the statement as follows:\n\nFigure 4(a) and Figure 4(b) show that the performance of SNAPS significantly improves as k gradually increases from 0.  This improvement occurs because the increasing nodes with the same label are selected to enhance the ego node. Subsequently, as k continues to increase, the performance of SNAPS tends to stabilize.\n\n\n> **5. Extension to heterophilous datasets [Q2]**\n\nwe guess your concern is about extension to heterophilous datasets, where nodes with different labels tend to be linked [3], because there may be inconsistencies in the types of nodes in heterogeneous datasets. To verify the efficiency of SNAPS on heterophilous graphs, we conduct the experiments on two common heterophilous graph benchmarks, as shown below:\n\n|Datasets|Nodes|Features|Edges|Classes|Homophily Ratio|\n|-|-|-|-|-|-|\n|Chameleon|2,277|2,325|36,101|5|0.23|\n|Squirrel|5,201|2,089|217,073|5|0.22|\n\nFor the experiment setting, we choose FSGNN [4] as the GNN model and follow the dataset splits of Geom-GCN [5], i.e. splitting nodes into 60%/20%/20% for training/validation/testing. To evaluate the performance of the CP methods, we divide the test set equally into the calibration and evaluation sets. For DAPS, $\\lambda=0.5$. For SNAPS, $\\lambda=0.5, \\mu=0$ and $k=20$, i.e., SNAPS neglecting structural neighborhood. To construct a cosine similarity-based k-NN graph for these two heterophilous datasets, we utilize the embeddings from FSGNN. In the following tables, empirical results at $\\alpha=\\{0.10, 0.15\\}$ are presented respectively:\n\n||FSGNN|Coverage|||Size|||\n|-|-|-|-|-|-|-|-|\n|Datasets|Accuracy|APS|DAPS|SNAPS|APS|DAPS|SNAPS|\n|Chameleon|78.09±0.93|0.904|0.905|0.904|1.95|2.75|**1.70**|\n|Squirrel|73.72±2.19|0.900|0.897|0.900|2.41|3.05|**2.27**|\n\n||Coverage|||Size|||\n|-|-|-|-|-|-|-|\n|Datasets|APS|DAPS|SNAPS|APS|DAPS|SNAPS|\n|Chameleon|0.850|0.853|0.851|1.62|2.23|**1.32**|\n|Squirrel|0.851|0.848|0.850|1.89|2.37|**1.64**|\n\n\n\n[1] DAPS: Conformal Prediction Sets for Graph Neural Networks. ICML'23.\n\n[2] Uncertainty sets for image classifiers using conformal prediction. ICLR'21.\n\n[3] Graph Neural Networks for Graphs with Heterophily: A Survey. arxiv'22.\n\n[4] Improving Graph Neural Networks with Simple Architecture Design. arxiv'21.\n\n[5] Geom-GCN: Geometric Graph Convolutional Networks. ICLR'20.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "dUGEjggDCK", "reviewer": "Reviewer_xCn2", "summary": "This paper addresses the problem of the lack of reliable uncertainty estimates in semi-supervised node classification tasks using Graph Neural Networks.\n\nThis paper shows that nodes with the same label as the ego node play a critical role in the non-conformity scores of the ego node.\n\nThe authors propose a method to aggregate the non-conformity scores based on\nfeature similarity and structural neighborhood, to improve the efficiency of prediction sets and singleton hit ratio.", "questions": "How will the proposed method perform on  heterphily graphs?", "limitations": "The authors discussed the limitations on transductive settings. \n\nN/A potential negative societal impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper is well-motivated, with clear motivation that nodes with high feature similarity or direct connections tend to have the same label.\n2. This paper provides theoretical guarantee that the proposed method can consistently generate a smaller prediction set than basic non-conformity scores functions while maintaining the marginal coverage rate.\n3. The authors provide adequate empirical analysis, including ablation studies and comparisons with state-of-the-art methods.", "weaknesses": "1. While the paper demonstrates the effectiveness of the proposed method on various datasets, it lacks a detailed analysis of the scalability / computation cost of the algorithm. It would be interesting to see how the method scales with the number of nodes and edges.\n2. The focus on transductive learning in the paper limits its applicability to inductive learning scenarios, which are common in real-world classification tasks.\n3. It would be interesting to see the discussion and experiments of the proposed method on heterphily graphs, where nodes with different labels are more likely to be connected.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the insightful and detailed comments. Please find our response below:\n\n> **1. Scalability / Computation cost [W1]**\n\nThank you for your valuable feedback. The time complexity of SNAPS is primarily determined by the computation of corrected scores. In this work, we use one-hop nodes and nodes with high feature similarity to correct the ego node. In the transductive setting, this complexity applies to the entire graph. Consequently, one-hop generalization requires $\\mathcal{O}(E)$ runtime, and K-NN generalization requires $\\mathcal{O}(NM)$, where $E$ is the number of edges, $N$ is the number of test nodes, $M$ is the number of nodes sampled to correct the scores of test nodes, with $M\\ll N$ for large graphs. Finally, the time complexity of SNAPS is $\\mathcal{O}(E+NM)$.\n\n**Time complexity of k-NN.** Calculating pairwise similarities is inherently parallelizable, which makes k-NN significantly more efficient. Additionally, there have been some approximation methods that could be used to significantly speed up the computation for large graphs, such as NN-Descent [1] that can be easily implemented under MapReduce to empirically achieve an approximate k-NN graph in $\\mathcal{O}(N^{1.14})$.\n\n> **2. Inductive learning [W2]**\n\nIn the context of inductive learning, exchangeability is not maintained as changes in the graph affect the calibration nodes' conformity scores [2, 3]. Therefore, our primary focus is on transductive learning. Additionally, we present experimental results in the inductive scenario using CoraML dataset, illustrated in Figure 4 of the attachment. The results demonstrate that SNAPS generally achieves **valid coverage with comparable set sizes** in the inductive setting.\n\n\n> **3. Performance on heterophilous graphs [W3 & Q1]**\n\n\nWe thank the reviewer for this intriguing question. Following the reviewer's advice, we conduct the experiments on two common heterophilous graph benchmarks. The benchmarks' details are as follows:\n\n| Datasets | Nodes | Features | Edges | Classes | Homophily Ratio |\n| :--: |:--: |:--: |:--: |:--: |:--: |\n| Chameleon | 2,277 | 2,325 | 36,101 | 5 | 0.23 |\n| Squirrel | 5,201 | 2,089 | 217,073 | 5 | 0.22 |\n\nFSGNN [4] is used as the GNN model, and we adopt the dataset splits from Geom-GCN [5], i.e. splitting nodes into 60%/20%/20% for training/validation/testing. To evaluate the performance of the CP methods, we divide the test set equally into the calibration and evaluation sets. For DAPS, we set $\\lambda=0.5$. For SNAPS, we set $\\lambda=0.5, \\mu=0$ and $k=20$, i.e., neglecting the structural neighborhood. To construct a cosine similarity-based k-NN graph for these two heterophilous datasets, we utilize the embeddings from FSGNN. In the following tables, empirical results at $\\alpha=\\{0.10, 0.15\\}$ are presented respectively:\n\n| | FSGNN |Coverage |  | |Size |  | |\n| :--: |:--: |:--: |:--: |:--: |:--: |:--: |:--: |\n|Datasets | Accuracy | APS | DAPS | SNAPS | APS | DAPS | SNAPS\n|Chameleon| 78.09±0.93 | 0.904 | 0.905 | 0.904 | 1.95 | 2.75 | **1.70** |\n|Squirrel| 73.72±2.19 | 0.900 | 0.897 | 0.900 | 2.41 | 3.05 | **2.27**|\n\n| |Coverage |  | | Size |  | |\n| :--: |:--: |:--: |:--: |:--: |:--: |:--: |\n|Datasets | APS | DAPS | SNAPS | APS | DAPS | SNAPS\n|Chameleon| 0.850 | 0.853 | 0.851 | 1.62 | 2.23 | **1.32** |\n|Squirrel| 0.851 | 0.848 | 0.850 | 1.89 | 2.37 | **1.64**|\n\nWe can observe that SNAPS still shows **consistent superiority** over the baselines on heterophilous networks, which demonstrates its weak dependence on homophily.\n\n[1] Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures. WWW'11.\n\n[2] DAPS: Conformal Prediction Sets for Graph Neural Networks. ICML'23.\n\n[3] Uncertainty Quantification over Graph with Conformalized Graph Neural Networks. NeurIPS'23.\n\n[4] Improving Graph Neural Networks with Simple Architecture Design. arxiv'21.\n\n[5] Geom-GCN: Geometric Graph Convolutional Networks. ICLR'20.", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their time, insightful suggestions, and valuable comments. We are certain that they will make our work more complete. We are glad and encouraged that reviewers find the method is **well-motivated** (aWFN, xCn2) and **theoretical** (3cJc, xCn2), our method is **simple** (aWFN) and **effective** (8yy7, 3cJc, xCn2), and the experiments are **extensive** (8yy7, aWFN, 3cJc, xCn2). Besides, reviewers recognize that the writing is **easy to follow** (8yy7, 3cJc). We provide point-by-point responses to all reviewers' comments and concerns.

**Performance of SNAPS on heterophilous graphs**. We note that all reviewers are interested in the performance of SNAPS on heterophilous graphs. Thus, we add experiments on two heterophilous datasets and provide the experimental results in reponses below. For example, on the dataset Squirrel, SNAPS reduce the average set size from 1.89 (APS) to 1.64 when $\alpha=0.15$. The results demonstrate that SNAPS still outperforms other baseline methods on heterophilous graphs.

In summary, our method may reduce the set size for homophilous and heterophilous graphs. We will present the analysis in the final version.

Meta-review: This paper proposes a simple extension of DAPS by Zargarbashi, Antonelli, and Bojchevski for conformal prediction on graph neural networks, which is named as SNAPS. The key idea is that, in addition to aggregate the non-conformity scores of the neighbors, SNAPS also aggregate the non-conformity score of nodes with the same labels into the non-conformity score of the ego node. During aggregation, to account for nodes without known label, the authors construct a feature similarity graph to select nodes with high features similarity for aggregation, based on the homophily assumption.

There are several advantages of the proposed work. It is very simple as the additional operations are aggregations over the original neighborhood and the high-similarity neighborhood, respectively. And the empirical results do show improvements on the prediction set size and the singleton hit ratio.

The reviewers raised several concerns regarding the evaluation of SNAPS, including comparison with CF-GNN, evaluation on heterophilous graphs, parameter analysis with varying significance level or calibration set size, etc. The additional results in the discussion phase consistently show a better performance than the existing methods. One thing I would suggest is about SNAPS on heterophilous graph: the way the authors evaluate it is to use embedding from FSGNN to construct feature similarity graph. Though it is a simple workaround for the heterophilous graphs, it doesn't really solve the problem on heterophilous where you hope that the embedding would be a good embedding on heterophilous embedding. So it would be great to add the additional results on heterophilous graphs and discussion about how you approach it, as well as the limitations in the future version. 

My major concern about this paper is regarding the theoretical analysis. Reviewer 8yy7 raised concern about the assumption in proposition 2, specifically the meaning of "very small". It would be helpful if the authors could add the response into the future version, as it is unclear what "very small" or "very high" means rigorously, which should be avoided in a more rigorous statement of a theorem.

Overall, the paper has its own limitations but it has its own merits that the proposed method is simple and does offers improvements. All reviewers unanimously hold positive thoughts about this paper. I recommend accepting the paper.
Decision: Accept (poster)