# Similarity-Navigated Conformal Prediction for Graph Neural Networks

Jianqing Song1 Jianguo Huang2,3 Wenyu Jiang1,2 Baoming Zhang1 Shuangjie Li1
Chongjun Wang1
1State Key Laboratory of Novel Software Technology Corresponding author
<EMAIL_ADDRESS> Nanjing University
2Department of Statistics and Data Science  Southern University of Science and
Technology
3The School of Information Science and Technology  ShanghaiTech 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 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. This observation motivates us to propose a novel algorithm
named 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.

##  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 et al., 2018; Xu et al., 2019), have achieved remarkable accuracy
in various high-stakes applications, e.g., drug discovery (Li et al., 2022),
fraud detection (Liu et 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., 2017b; Kendall and Gal, 2017; Wang et
al., 2021; Hsu et al., 2022; Tang et al., 2024), while these methods lack
theoretical guarantees of quantification. Conformal prediction (CP), on the
other hand, offers a systematic approach to construct prediction sets that
contain ground-truth labels with a desired coverage guarantee (Vovk et al.,
2005; Romano et al., 2020; Angelopoulos et al., 2021; Huang et al., 2023a).

CP algorithms utilize non-conformity scores to measure dissimilarity between a
new instance and 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 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 analyse 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-truth labels of
all nodes are known, and then aggregating their non-conformity scores into the
ego node. The results indicate that aggregating scores of these nodes can
significantly reduces 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 is 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 as possible and aggregate their non-conformity scores.

To this end, we propose a novel algorithm named Similarity-Navigated 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 a higher probability of having the
same label as the ego node while preserving its own and the one-hop neighbors.
We utilize the feature similarity between nodes and the adjacency 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 et 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 $\frac{1}{5}$ of the prediction
set size from APS on ImageNet (Deng et al., 2009).

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 in its non-conformity scores.

  * •

We propose a 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 to 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 achieve 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 in an undirected graph.

Notation. Graph is represented as $\mathcal{G}=(\mathcal{V},\mathcal{E})$,
where $\mathcal{V}:=\\{v_{i}\\}_{i=1}^{N}$ denotes the node set and
$\mathcal{E}$ denotes the edge set with $|\mathcal{E}|=E$. Let
$\boldsymbol{A}\in\\{0,1\\}^{N\times N}$ be the adjacency matrix, where
$\boldsymbol{A}_{i,j}=1$ if there exists an edge between nodes $v_{i}$ and
$v_{j}$, and $\boldsymbol{A}_{i,j}=0$ otherwise, and $\boldsymbol{D}$ be its
degree matrix, where $\boldsymbol{D}_{i,i}=\sum_{j}\boldsymbol{A}_{i,j}$. Let
$\boldsymbol{X}:=[\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{N}]^{T}$ be the
node feature matrix, where $\boldsymbol{x}_{i}\in\mathbb{R}^{d}$ is a
$d$-dimensional feature vector for node $v_{i}$. The label of node $v_{i}$ is
$y_{i}\in\mathcal{Y}$, where $\mathcal{Y}:=\\{1,2,...,K\\}$ denotes the label
space.

Transductive setting. In transductive setting, we have access to two node
sets, $\mathcal{V}_{\text{label}}$ with labels and
$\mathcal{V}_{\text{unlabel}}$ without labels, where
$\mathcal{V}_{\text{label}}\cap\mathcal{V}_{\text{unlabel}}=\emptyset$ and
$\mathcal{V}_{\text{label}}\cup\mathcal{V}_{\text{unlabel}}=\mathcal{V}$.
$\mathcal{V}_{\text{label}}$ is then randomly split into
$\mathcal{V}_{\text{train}}/\mathcal{V}_{\text{valid}}/\mathcal{V}_{\text{calib}}$
with a fixed size, the training/validation/calibration node set,
correspondingly. $\mathcal{V}_{\text{unlabel}}$ is used as the testing node
set $\mathcal{V}_{\text{test}}$. The classifier $f(\cdot)$ is trained on
$\\{(\boldsymbol{x}_{i},y_{i})\\}_{v_{i}\in\mathcal{V}_{\text{train}}}$,
$\\{\boldsymbol{x}_{i}\\}_{v_{i}\in\mathcal{V}-\mathcal{V}_{\text{train}}}$
and the entire graph structure $\mathcal{G}=(\mathcal{V},\mathcal{E})$, and is
chosen through
$\\{(\boldsymbol{x}_{i},y_{i})\\}_{v_{i}\in\mathcal{V}_{\text{valid}}}$. Then
we can get the predicted probability
$\boldsymbol{P}=\\{\boldsymbol{p}_{i}\\}_{v_{i}\in\mathcal{V}}$ for each node
through $\boldsymbol{p}_{i}=\sigma(f(\boldsymbol{x}_{i}))$ where
$\boldsymbol{p}_{i}\in[0,1]^{K}$ and $\sigma$ is activation function such as
softmax. We usually choose the label with the highest probability as the
predicted label, i.e., $\hat{y}_{i}=\mathrm{argmax}_{k}\boldsymbol{p}_{ik}$.

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 a message passing mechanism
(Gilmer et al., 2017). The $l$-th layer of the GNNs takes the following form:

$\boldsymbol{h}_{i}^{(l)}=\mathrm{COMBINE}^{(l)}\left(\boldsymbol{h}_{i}^{(l-1)},\mathrm{AGG}^{(l)}\left(\left\\{\mathrm{MSG}^{(l)}(\boldsymbol{h}_{j}^{(l-1)},\boldsymbol{h}_{i}^{(l-1)})|v_{j}\in\mathcal{N}_{i}\right\\}\right)\right)$
(1)

where $\boldsymbol{h}_{i}^{(l)}$ is the hidden representation of node $v_{i}$
at the $l$-th layer with initialization of
$\boldsymbol{h}_{i}^{(0)}=\boldsymbol{x}_{i}$, and $\mathcal{N}_{i}$ is a set
of nodes adjacent to node $v_{i}$. $\mathrm{MSG}^{(l)}(\cdot)$,
$\mathrm{AGG}^{(l)}(\cdot)$ and $\mathrm{COMBINE}^{(l)}(\cdot)$ denote the
functions for message computation, message aggregation, and message
combination, respectively. After an iteration of the last layer, the obtained
final node representation
$\boldsymbol{H}=\\{\boldsymbol{h}_{i}^{L}\\}_{v_{i}\in\mathcal{V}}$ is then
fed to a classifier to obtain the predicted probability $\boldsymbol{P}$.

Conformal prediction. CP is a promising framework for generating prediction
sets that statistically contain ground-truth labels with a desired guarantee.
Formally, given calibration data
$\mathcal{D}_{\text{calib}}=\\{(\boldsymbol{x}_{i},y_{i})\\}_{i=1}^{n}$, we
can generate a prediction set
$\mathcal{C}(\boldsymbol{x}_{n+1})\subseteq\mathcal{Y}$ for an unseen instance
$\boldsymbol{x}_{n+1}$ with the coverage guarantee
$\mathbb{P}[y_{n+1}\in\mathcal{C}(\boldsymbol{x}_{n+1})]\geq 1-\alpha$, where
$\alpha$ is the pre-defined significance level. The best characteristic of CP
is that it is distribution-free and only relies on exchangeability. This means
that every permutation of the instances is equally likely, i.e.,
$\mathcal{D}_{\text{calib}}\cup(\boldsymbol{x}_{n+1},y_{n+1})$ is
exchangeable, where $(\boldsymbol{x}_{n+1},y_{n+1})$ is 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 et 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 1

(Vovk et al., 2005) Let calibration data and a test instance, i.e.,
$\\{(\boldsymbol{x}_{i},y_{i})\\}_{i=1}^{n}\cup\\{(\boldsymbol{x}_{n+1},y_{n+1})\\}$
be exchangeable. For any non-conformity score function
$s:\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$ and any significance
level $\alpha\in(0,1)$, define the $1-\alpha$ quantile of scores as
$\hat{q}:=\mathrm{Quantile}\left(\frac{\lceil(1-\alpha)(n+1)\rceil}{n};\\{s(\boldsymbol{x}_{i},y_{i})\\}_{i=1}^{n}\right)$
and prediction sets as
$\mathcal{C}_{\alpha}(\boldsymbol{x}_{n+1})=\\{y|s(\boldsymbol{x}_{n+1},y)\leq\hat{q}\\}$.
We have

$1-\alpha\leq\mathbb{P}[y_{n+1}\in\mathcal{C}_{\alpha}(\boldsymbol{x}_{n+1})]<1-\alpha+\frac{1}{n+1}.$
(2)

Theorem 1 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 accumulating the softmax probabilities in descending order.
Formally, given a data pair $(\boldsymbol{x},y)$ and a predicted probability
estimator $\pi(\boldsymbol{x})_{y}$ for $(\boldsymbol{x},y)$, where
$\pi(\boldsymbol{x})_{y}$ is the predicted probability for class $y$, the non-
conformity scores can be computed by:
$s(\boldsymbol{x},y)=\sum_{i=1}^{|\mathcal{Y}|}\pi(\boldsymbol{x})_{i}\mathbb{I}[\pi(\boldsymbol{x})_{i}>\pi(\boldsymbol{x})_{y}]+u\cdot\pi(\boldsymbol{x})_{y}$,
where $u\in[0,1]$ is a uniformly distributed random variable. Then, the
prediction set is constructed as
$\mathcal{C}(\boldsymbol{x})=\\{y|s(\boldsymbol{x},y)\leq\hat{q}\\}$.

Evaluation Metrics. 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 $\mathcal{V}_{\text{test}}$,
the efficiency is defined as the average size of prediction sets:
$\mathrm{Size}:=\frac{1}{|\mathcal{V}_{\text{test}}|}\sum_{v_{i}\in\mathcal{V}_{\text{test}}}|\mathcal{C}(\boldsymbol{x}_{i})|.$
The smaller the size, the more efficient CP is. The empirical marginal
coverage is defined as
$\mathrm{Coverage}:=\frac{1}{|\mathcal{V}_{\text{test}}|}\sum_{v_{i}\in\mathcal{V}_{\text{test}}}\mathbb{I}[y_{i}\in\mathcal{C}(\boldsymbol{x}_{i})]$.
Although efficiency is a common metric for evaluating CP, singleton hit ratio
(SH), defined as the proportion of prediction sets of size one that contain
the true label, is also important (Zargarbashi et al., 2023). The formula of
SH is defined as:
$\mathrm{SH}:=\frac{1}{|\mathcal{V}_{\text{test}}|}\sum_{v_{i}\in\mathcal{V}_{\text{test}}}\mathbb{I}[\mathcal{C}(\boldsymbol{x}_{i})=\\{y_{i}\\}]$.

##  3 Motivation and Methodology

###  3.1 Motivation

In this subsection, we empirically show that nodes with the same label as the
ego node may play a critical role in the non-conformity scores of the ego
node. Specifically, using the scores of 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
CoraML (McCallum et al., 2000) dataset and choose APS as 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
$\alpha=0.05$.

In Figure LABEL:fig:motivation-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, $\mathrm{Size}$ can be reduced to a large extent.
Moreover, aggregating the scores of these nodes still achieves the coverage
guarantee.

###  3.2 Similarity-Navigated 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 to use the similarity to
approximate the potential label. Specifically, the nodes with high feature
similarity tend to have a high probability of belonging to 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 to be the same as the ego node (Kipf and
Welling, 2017), and several studies have demonstrated the effectiveness of
this (Clarkson, 2023; Zargarbashi et al., 2023; Huang et al., 2023b).
Therefore, we consider feature similarity and network structure to select
nodes that may have the same label as the ego node.

Feature similarity graph construction. We compute the cosine similarity
between the node features in the graph. For a given node pair $(v_{i},v_{j})$,
the cosine similarity between their features can be calculated by:

$\mathrm{Sim}(i,j)=\frac{\boldsymbol{x}_{i}^{\top}\boldsymbol{x}_{j}}{\|\boldsymbol{x}_{i}\|_{2}\cdot\|\boldsymbol{x}_{j}\|_{2}}.$
(3)

where $i\neq j$, $v_{i}\in\mathcal{V}$ and $v_{j}\in\mathcal{V}_{t,i}$. Here,
$v_{j}\in\mathcal{V}_{t,i}$ represents a set of nodes for which we calculate
the similarity with $v_{i}$. 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 as $\boldsymbol{A}_{s}$ and its degree
matrix as $\boldsymbol{D}_{s}$, where
$\boldsymbol{A}_{s}(i,j)=\mathrm{Sim}(i,j)$ and
$\boldsymbol{D}_{s}(i,i)=\sum_{j}\boldsymbol{A}_{s}(i,j)$. For large graphs,
we randomly select $M\gg k$ nodes to put into $\mathcal{V}_{t,i}$, whereas for
small graphs, we include all nodes into $v_{j}\in\mathcal{V}_{t,i}$.

To verify the effectiveness of feature similarity, we provide an empirical
analysis. Figure LABEL:fig:motivation-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 LABEL:fig:motivation-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 $k$ is not very large.

Figure 3: The overall framework of 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 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.

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 $v_{i}$ with a label $y$, the score function of SNAPS is
shown as :

$\hat{s}(\boldsymbol{x}_{i},y)=(1-\lambda-\mu)s(\boldsymbol{x}_{i},y)+\frac{\lambda}{\boldsymbol{D}_{s}(i,i)}\sum_{j=1}^{M}\boldsymbol{A}_{s}(i,j)s(\boldsymbol{x}_{j},y)+\frac{\mu}{|\mathcal{N}_{i}|}\sum_{v_{j}\in\mathcal{N}_{i}}s(\boldsymbol{x}_{j},y),$
(4)

where $s(\cdot,\cdot)$ is the basic non-conformity score function and
$\hat{s}(\cdot,\cdot)$ is the SNAPS score function. Both $\lambda$ and $\mu$
are hyperparameters, which are used to measure the importance of three parts
of non-conformity scores. The framework of SNAPS is shown in Figure 3 and
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-conformity scores based on the node embeddings obtained
by any GNNs 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 $\boldsymbol{S}=\\{\boldsymbol{s}_{i}\\}_{v_{i}\in\mathcal{V}}$ be basic
non-conformity scores of nodes, where $\boldsymbol{s}_{i}\in\mathbb{R}^{K}$.
Assume that $\boldsymbol{S}$ is exchangeable for all
$v_{i}\in(\mathcal{V}_{\text{calib}}\cup\mathcal{V}_{\text{test}})$. Then the
aggregated
$\boldsymbol{\hat{S}}=(1-\lambda-\mu)\boldsymbol{S}+\lambda\boldsymbol{\hat{A}}_{s}\boldsymbol{S}+\mu\boldsymbol{\hat{A}}\boldsymbol{S}$,
where $\boldsymbol{\hat{A}}_{s}=\boldsymbol{D}_{s}^{-1}\boldsymbol{A}_{s}$ and
$\boldsymbol{\hat{A}}=\boldsymbol{D}^{-1}\boldsymbol{A}$, is also exchangeable
for $v_{i}\in(\mathcal{V}_{\text{calib}}\cup\mathcal{V}_{\text{test}})$.

The corresponding proof is provided in Appendix A. We then demonstrate the
validity of our method theoretically.

###### Proposition 2

Assume that all of nodes aggregated by SNAPS are the same label as the ego
node. Let $\boldsymbol{S}$ be APS scores of nodes, where
$\boldsymbol{S}_{ui}\in[0,1]$ is the score corresponding to node $u$ with
label $i$. Let $E_{k}[\boldsymbol{S}_{ui}]$ be the average of scores
corresponding to label $i$ of nodes whose ground-truth labels are $k$ and
$\eta$ be $1-\alpha$ quantile of basic non-conformity scores with a
significance level $\alpha$. If $E_{k}[\boldsymbol{S}_{uk}]\ll\eta$ and
$E_{k}[\boldsymbol{S}_{ui}]-\eta\geq-\Delta$, where $\Delta>0$ and is very
small, then

$\mathbb{E}[|\mathcal{C}(\boldsymbol{x})|]\leq\mathbb{E}[|\mathcal{\tilde{C}}(\boldsymbol{x})|]$

where $\mathcal{C}(\cdot)$ and $\mathcal{\tilde{C}}(\cdot)$ represent the
prediction set from 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 obviously that we can’t ignore a very important thing,
which is to select nodes with the same label as ego node as correctly as
possible, otherwise it will lead to a decrease in the efficiency of SNAPS.

##  4 Experiments

###  4.1 Experimental Settings

Datasets. We consider ten datasets in experiments, including 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., 2019) and the
co-purchase graphs: Amazon Photos (Photos) and Amazon Computers (Computers)
(McAuley et al., 2015; Shchur et al., 2019). Moreover, we consider two large-
scale graph datasets, i.e., OGBN Arxiv (Arxiv) (Wang et al., 2020) and OGBN
Products (Products) (Bhatia et 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 datasets are shown in Appendix E.

Baselines. Since our SNAPS is a general post-processing methods for GNNs, here
we choose GCN (Kipf and Welling, 2017), GAT (Velickovic et al., 2018) and
APPNP (Gasteiger et al., 2018) as structure-aware models and MLP as a
structure-independent model. Moreover, our SNAPS can be based on general
conformal prediction non-conformity scores, here we 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., 2019), we train the model over ten trials
using varying train/validation splits. For per class in the
training/validation set, we randomly select 20 nodes. For Arxiv and Products
dataset, we follow the official split in 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
$|\mathcal{V}_{\text{calib}}|=\min\\{1000,|\mathcal{V}_{\text{calib}}\cup\mathcal{V}_{\text{test}}|/2\\}$.
For each trained model, we conduct 100 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 hyper-parameters, we split the
calibration set into two sets, one for tuning parameters, and the other for
conformal calibration (Zargarbashi et al., 2023). For SNAPS, we choose
$\lambda$ and $\mu$ in increments of 0.05 within the range 0 to 1, and ensure
that $\lambda+\mu<=1$. Each experiment is done with a single NVIDIA V100 32GB
GPU.

Table 1: Results of $\mathrm{Coverage}$, $\mathrm{Size}$ and $\mathrm{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 $\alpha=0.05$. Bold numbers indicate optimal
performance.

| Coverage | Size$\downarrow$ | SH%$\uparrow$
---|---|---|---
Datasets | 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

###  4.2 Experimental results

SNAPS generates smaller prediction sets and achieves higher singleton hit
ratio. Table 1 shows that $\mathrm{Coverage}$ of all conformal prediction
methods is close to the desired coverage $1-\alpha$. At a significance level
$\alpha=0.05$, $\mathrm{Size}$ and $\mathrm{SH}$ exhibit superior performance.
For example, when evaluated on Products, SNAPS reduces $\mathrm{Size}$ from
14.92 of APS to 7.68. Overall, the experiments show that SNAPS has the desired
coverage rate and gets smaller $\mathrm{Size}$ and higher $\mathrm{SH}$ than
APS, RAPS and DAPS. Detailed results for other basic models and SNAPS based on
RAPS are available in Appendix C.

SNAPS generates smaller average prediction sets for each label. We conduct
additional experiments to analyse the average performance of APS and SNAPS on
nodes belonging to the same label at a significance level $\alpha=0.05$.
Figure LABEL:fig:mean-size-aps 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., $E_{k}[\boldsymbol{S}_{uk}]\ll\eta$
and $E_{k}[\boldsymbol{S}_{ui}]-\eta\geq-\Delta$, where $\Delta>0$ and is very
small. $\mathrm{Size}$ of prediction sets corresponding to APS is 3.29. Figure
LABEL:fig:mean-size-snaps shows that only a few other labels different from
real label have the average scores lower than the quantile of scores.
$\mathrm{Size}$ of prediction sets corresponding to SNAPS is 1.29. Overall,
for basic non-conformity scores that match this distribution of our
assumptions, SNAPS can achieve superior performance based on this scores. The
results of CiteSeer and Amazon Computers datasets are available in Appendix C.

Table 2: Ablation study in terms of $\mathrm{Size}$. Overall, three parts of
our method are critical and removing any of them results a general decrease in
performance.

Orig. | Neigh. | Feat. | CoraML | PubMed | CiteSeer | CoraFull∗ | CS | Physics | Computers | Photo | arxiv | products
---|---|---|---|---|---|---|---|---|---|---|---|---
$\checkmark$ | $\times$ | $\times$ | 2.42 | 1.79 | 2.34 | 17.54 | 1.91 | 1.28 | 3.95 | 1.89 | 4.30 | 14.92
$\times$ | $\checkmark$ | $\times$ | 2.18 | 1.94 | 2.07 | 17.50 | 1.37 | 1.09 | 2.15 | 1.42 | 4.75 | 11.25
$\times$ | $\times$ | $\checkmark$ | 2.40 | 1.65 | 2.52 | 18.07 | 1.11 | 1.03 | 3.26 | 2.60 | 9.45 | 13.89
$\checkmark$ | $\checkmark$ | $\times$ | 1.87 | 1.72 | 1.91 | 12.10 | 1.22 | 1.07 | 2.22 | 1.37 | 3.76 | 10.81
$\checkmark$ | $\times$ | $\checkmark$ | 1.78 | 1.63 | 1.94 | 11.54 | 1.13 | 1.05 | 2.37 | 1.46 | 3.82 | 8.46
$\times$ | $\checkmark$ | $\checkmark$ | 1.72 | 1.63 | 1.86 | 10.51 | 1.09 | 1.04 | 1.94 | 1.31 | 4.44 | 7.65
$\checkmark$ | $\checkmark$ | $\checkmark$ | 1.68 | 1.62 | 1.84 | 9.80 | 1.08 | 1.04 | 1.98 | 1.31 | 3.62 | 7.68

Ablation study. To understand the effects of three part of our method, i.e.,
original scores (Orig.), neighborhood scores (Neigh.) and feature similarity
node scores (Feat.), we conduct a thorough ablation experiments using GCN at
$\alpha=0.05$. In Table 2, SNAPS has the best performance on most of datasets
when all three parts are included. Moreover, for remaining dataset on which
SNAPS exhibits comparable performance, all those better cases contains the
Feat. part. Overall, each part plays a critical role in CP for GNNs and
removing any will in general decrease performance.

Parameter analysis. We conduct additional experiments to analyse the
robustness of SNAPS. We choose GCN as the GNNs model and APS as the basic non-
conformity score function.

Figure LABEL:fig:param-k-size and Figure LABEL:fig:param-k-sh show that as $k$
increases, both $\mathrm{Size}$ and $\mathrm{SH}$ tend to stabilize, because
more nodes with the same label are selected to enhance the ego node. On the
other hand, we find that when $k$ is extremely large, it appears that nodes
with the same label cannot be selected with high accuracy only by feature
similarity. Thus, when $k$ is extremely large, performance will decline
slightly. Figure LABEL:fig:param-ab-size and Figure LABEL:fig:param-ab-sh show
that as the values of parameter $\lambda$ and $\mu$ change, the most areas in
the heatmaps of $\mathrm{Size}$ and $\mathrm{SH}$ display similar colors.
Overall, SNAPS is robust to the parameter $k$ and is not sensitive to
parameter $\lambda$ and $\mu$.

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 of image features to correct the
APS. Formally, the corrected APS, i.e., SNAPS, is defined as :

$\hat{s}(\boldsymbol{x},y)=(1-\eta)s(\boldsymbol{x},y)+\frac{\eta}{|\mathcal{N}_{\boldsymbol{x}}|}\sum_{\tilde{\boldsymbol{x}}\in\mathcal{N}_{\boldsymbol{x}}}s(\tilde{\boldsymbol{x}},y),$

where $s(\boldsymbol{x},y)$ is the score of standard APS,
$\mathcal{N}_{\boldsymbol{x}}$ is the $k$ nearest neighbors based on image
features in the calibration set and $\eta$ 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 $k=5$ and $\eta=0.5$. We
report the results of $\mathrm{Coverage}$, $\mathrm{Size}$ and size-stratified
coverage violation (SSCV) (Angelopoulos et al., 2021). The details of
experiments and SSCV are provided in Appendix D.

As indicated in Table 3, SNAPS achieves smaller prediction sets than APS. For
example, on the ResNeXt101 model and $\alpha$ = 0.1, SNAPS reduces
$\mathrm{Size}$ from 19.639 to 4.079 – only $\frac{1}{5}$ 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.

Table 3: Results on Imagenet. The median-of-means is reported over 10
different trials. Bold numbers indicate optimal performance.

| Accuracy | APS/SNAPS
---|---|---
| $\alpha=0.1$ | $\alpha=0.05$
Model | Top1 | Top5 | Coverage | Size $\downarrow$ | SSCV $\downarrow$ | Coverage | Size$\downarrow$ | SSCV $\downarrow$
ResNeXt101 | 79.32 | 94.58 | 0.899/0.900 | 19.64/4.08 | 0.088/0.059 | 0.950/0.950 | 45.80/14.41 | 0.047/0.033
ResNet101 | 77.36 | 93.53 | 0.900/0.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
CLIP | 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.98 | 0.039/0.029

##  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., 2017b; 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 et 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
guarantee both theoretically and empirically.

Conformal Prediction for GNNs. Although several CP methods for GNNs have been
studied, the use of CP in graph-structured data is still largely
underexplored. ICP (Wijegunawardana et al., 2020) is the first to apply CP
framework on graphs, designs a 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 et al., 2023b) introduces a topology-aware output correction model,
akin to GCN, which employs a conformal-aware inefficiency loss to refine
predictions and improve efficiency of post-hoc CP. Other recent efforts in
conformal prediction 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-
structure data, but also to other types of data, such as image data.

##  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 a 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 on node classification using transductive learning. However,
in real-world scenarios, many classification tasks require inductive learning.
In the future, we aim to apply our method to the inductive setting.
Additionally, the method we use to select nodes with the same as the ego node
is both computationally inefficient and lacking accuracy. Future work will
explore more efficient and accurate methods for node selection. The datasets
that we study are not general enough, and we would like to validate our method
on more datasets.

## References

  * Amodei et al. [2016] Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané.  Concrete problems in ai safety.  _arXiv preprint arXiv:1606.06565_ , 2016.
  * Angelopoulos et al. [2021] 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.
  * Barber et al. [2023] Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan J Tibshirani.  Conformal prediction beyond exchangeability.  _The Annals of Statistics_ , 51(2):816–845, 2023.
  * Bhatia et al. [2016] 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.
  * Bojchevski and Günnemann [2018] Aleksandar Bojchevski and Stephan Günnemann.  Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking.  In _6th International Conference on Learning Representations_ , 2018.
  * Clarkson [2023] Jase Clarkson.  Distribution free prediction sets for node classification.  In _International Conference on Machine Learning_ , pages 6268–6278, 2023.
  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pages 248–255, 2009.
  * Fey and Lenssen [2019] Matthias Fey and Jan Eric Lenssen.  Fast graph representation learning with pytorch geometric.  _arXiv preprint arXiv:1903.02428_ , 2019.
  * Gal and Ghahramani [2016] Yarin Gal and Zoubin Ghahramani.  Dropout as a bayesian approximation: Representing model uncertainty in deep learning.  In _international conference on machine learning_ , pages 1050–1059, 2016.
  * Gao et al. [2019] 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.
  * Gasteiger et al. [2018] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann.  Predict then propagate: Graph neural networks meet personalized pagerank.  _arXiv preprint arXiv:1810.05997_ , 2018.
  * Gilmer et al. [2017] 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.
  * Guo et al. [2017a] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger.  On calibration of modern neural networks.  In _International Conference on Machine Learning_ , pages 1321–1330. PMLR, 2017a.
  * Guo et al. [2017b] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger.  On calibration of modern neural networks.  In _International conference on machine learning_ , pages 1321–1330, 2017b.
  * Gupta et al. [2021] 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.
  * Hamilton et al. [2017] William L. Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In _Advances in Neural Information Processing Systems_ , pages 1024–1034, 2017.
  * Hsu et al. [2022] 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.
  * Huang et al. [2023a] 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.06430_ , 2023a.
  * Huang et al. [2023b] 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.
  * Jiang and Luo [2022] Weiwei Jiang and Jiayun Luo.  Graph neural network for traffic forecasting: A survey.  _Expert Systems with Applications_ , 207:117921, 2022.
  * Jin et al. [2021a] 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.
  * Jin et al. [2021b] 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.
  * Kendall and Gal [2017] 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.
  * Kipf and Welling [2017] Thomas N. Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In _5th International Conference on Learning Representations_ , 2017.
  * Li et al. [2022] Michelle M Li, Kexin Huang, and Marinka Zitnik.  Graph representation learning in biomedicine and healthcare.  _Nature Biomedical Engineering_ , 6(12):1353–1369, 2022.
  * Liu et al. [2023] Yajing Liu, Zhengya Sun, and Wensheng Zhang.  Improving fraud detection via hierarchical attention-based graph neural network.  _Journal of Information Security and Applications_ , 72:103399, 2023.
  * Lunde [2023] Robert Lunde.  On the validity of conformal prediction for network data under non-uniform sampling.  _arXiv preprint arXiv:2306.07252_ , 2023.
  * Marandon [2023] Ariane Marandon.  Conformal link prediction to control the error rate.  _arXiv preprint arXiv:2306.14693_ , 2023.
  * McAuley et al. [2015] 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.
  * McCallum et al. [2000] Andrew McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore.  Automating the construction of internet portals with machine learning.  _Inf. Retr._ , 3(2):127–163, 2000.
  * Namata et al. [2012] 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.
  * Paszke et al. [2019] 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.
  * Romano et al. [2020] Yaniv Romano, Matteo Sesia, and Emmanuel J. Candès.  Classification with valid and adaptive coverage.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Sanchez-Martin et al. [2024] Pablo Sanchez-Martin, Kinaan Aamir Khan, and Isabel Valera.  Improving the interpretability of gnn predictions through conformal-based graph sparsification.  _arXiv preprint arXiv:2404.12356_ , 2024.
  * Sen et al. [2008] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.  Collective classification in network data.  _AI Magazine_ , 29(3):93, 2008.
  * Shchur et al. [2019] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann.  Pitfalls of graph neural network evaluation, 2019.
  * Tang et al. [2024] Boshi Tang, Zhiyong Wu, Xixin Wu, Qiaochu 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.
  * Velickovic et al. [2018] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph attention networks.  In _6th International Conference on Learning Representations_ , 2018.
  * Vovk et al. [2005] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer.  _Algorithmic Learning in a Random World_.  Springer Science & Business Media, 2005.
  * Wang et al. [2020] Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia.  Microsoft academic graph: When experts are not enough.  _Quantitative Science Studies_ , 1(1):396–413, 2020.
  * Wang et al. [2021] 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.
  * Wijegunawardana et al. [2020] Pivithuru Wijegunawardana, Ralucca Gera, and Sucheta Soundarajan.  Node classification with bounded error rates.  In _Complex Networks XI: Proceedings of the 11th Conference on Complex Networks CompleNet 2020_ , pages 26–38. Springer, 2020.
  * Xu et al. [2019] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  In _7th International Conference on Learning Representations_ , 2019.
  * Zargarbashi and Bojchevski [2023] Soroush H Zargarbashi and Aleksandar Bojchevski.  Conformal inductive graph neural networks.  In _The Twelfth International Conference on Learning Representations_ , 2023.
  * Zargarbashi et al. [2023] Soroush H. Zargarbashi, Simone Antonelli, and Aleksandar Bojchevski.  Conformal prediction sets for graph neural networks.  In _International Conference on Machine Learning_ , volume 202, pages 12292–12318, 2023.
  * Zhang et al. [2020] Jize Zhang, Bhavya Kailkhura, and Thomas Yong-Jin Han.  Mix-n-match : Ensemble and compositional methods for uncertainty calibration in deep learning.  In _Proceedings of the 37th International Conference on Machine Learning_ , volume 119, pages 11117–11128, 2020.
  * Zou et al. [2023] Minhao Zou, Zhongxue Gan, Ruizhi Cao, Chun Guan, and Siyang Leng.  Similarity-navigated graph neural networks for node classification.  _Information Sciences_ , 633:41–69, 2023.

##  Appendix A Proofs

In this section, we provided the proofs that were omitted from the main paper.

###  A.1 Proof of Proposition 1

Proof. [Zargarbashi et al., 2023] have proved that
$(1-\lambda-\mu)\boldsymbol{S}+\mu\boldsymbol{\hat{A}}\boldsymbol{S}$ is
exchangeable for
$v_{i}\in(\mathcal{V}_{\text{calib}}\cup\mathcal{V}_{\text{test}})$. So we
only need to prove that $\boldsymbol{\hat{A}}_{s}\boldsymbol{S}$ is also
exchangeable. $\boldsymbol{\hat{A}}_{s}$ is obtained by calculating the
feature similarity between two nodes from a global perspective. Before
obtaining this matrix, we can not distinguish between labeled and unlabeled
nodes, so we just build a 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,
$\boldsymbol{\hat{S}}=(1-\lambda-\mu)\boldsymbol{S}+\lambda\boldsymbol{\hat{A}}_{s}\boldsymbol{S}+\mu\boldsymbol{\hat{A}}\boldsymbol{S}$
is a special case of a message passing GNNs layer. It follows that
$\boldsymbol{\hat{S}}$ is invariant to permutations of the order of the
calibration and testing nodes on the graph. Through the proof above, we can
conclude that $\boldsymbol{\hat{S}}$ is also exchangeable for
$v_{i}\in(\mathcal{V}_{\text{calib}}\cup\mathcal{V}_{\text{test}})$.

###  A.2 Proof of Proposition 2

For the sake of description, we denote "$1-\alpha$ quantile of basic non-
conformity scores in the calibrated set" as "the quantile score". We first
introduce some background before the proof.

Let $\boldsymbol{S}$ and $\boldsymbol{\hat{S}}$ denote APS and SNAPS non-
conformity scores, respectively. For node $v$ whose label is $k$,
$\boldsymbol{\hat{S}}_{v}$ can be actually be expressed as

$\boldsymbol{\hat{S}}_{v}=(1-\lambda)\boldsymbol{S}_{v}+\frac{\lambda}{|\mathcal{V}_{k}|}\sum_{u\in\mathcal{V}_{k}}\boldsymbol{S}_{u},$
(5)

where $\mathcal{V}_{k}$ denotes the nodes set where nodes’ ground-truth label
is $k$, because regardless of whether high feature similarity nodes or one-hop
structural neighbors, the purpose of aggregating these nodes’ scores is
actually to aggregate, as much as possible, non-conformity scores of nodes
with the same label as the ego node.

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
$v$, i.e., $\boldsymbol{\hat{S}}_{vk}\leq\boldsymbol{S}_{vk}$ or
$\boldsymbol{\hat{S}}_{vk}\leq\eta$. 2) SNAPS is efficient for the score
corresponding to the other label $i$ of node $v$, i.e.,
$\boldsymbol{\hat{S}}_{vi}\geq\boldsymbol{S}_{vi}$ or
$\boldsymbol{\hat{S}}_{vi}\geq\eta$. The key idea behind this is as follows.
We try to ensure that scores corresponding to the ground-truth label are below
the quantile score or decrease compared to the before and scores corresponding
to the other label are above the the quantile score or increase compared to
the before.

Proof. Here’s our proof.

#### Firstly

SNAPS is efficient for the score corresponding to the ground-truth label $k$
of node $v$, i.e., $\boldsymbol{\hat{S}}_{vk}\leq\boldsymbol{S}_{vk}$ or
$\boldsymbol{\hat{S}}_{vk}\leq\eta$. Here we have

$\boldsymbol{\hat{S}}_{vk}=(1-\lambda)\boldsymbol{S}_{vk}+\lambda
E_{k}[\boldsymbol{S}_{uk}].$

1) If $\boldsymbol{S}_{vk}\geq E_{k}[\boldsymbol{S}_{uk}]$, then

$\displaystyle\boldsymbol{\hat{S}}_{vk}-\boldsymbol{S}_{vk}$
$\displaystyle=(1-\lambda)\boldsymbol{S}_{vk}+\lambda
E_{k}[\boldsymbol{S}_{uk}]-\boldsymbol{S}_{vk}$
$\displaystyle=-\lambda(\boldsymbol{S}_{vk}-E_{k}[\boldsymbol{S}_{uk}])$
$\displaystyle\leq 0.$

Thus, $\boldsymbol{\hat{S}}_{vk}\leq\boldsymbol{S}_{vk}$. 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 to ground-truth labels will decrease, $\hat{\eta}<\eta$, where
$\hat{\eta}$ denotes $1-\alpha$ quantile of SNAPS scores in the calibrated
set.

2) If $\boldsymbol{S}_{vk}<E_{k}[\boldsymbol{S}_{uk}]$, then

$\displaystyle\boldsymbol{\hat{S}}_{vk}$
$\displaystyle=(1-\lambda)\boldsymbol{S}_{vk}+\lambda
E_{k}[\boldsymbol{S}_{uk}]$
$\displaystyle<(1-\lambda)E_{k}[\boldsymbol{S}_{uk}]+\lambda
E_{k}[\boldsymbol{S}_{uk}]$ $\displaystyle=E_{k}[\boldsymbol{S}_{uk}]$
$\displaystyle<\eta.$

Thus, $\boldsymbol{\hat{S}}_{vk}<\eta$. This means that for original scores
less than the quantile score, they still less than the quantile score after
aggregation.

#### Secondly

SNAPS is efficient for the score corresponding to the other label $i$ of node
$v$, i.e., $\boldsymbol{\hat{S}}_{vi}\geq\boldsymbol{S}_{vi}$ or
$\boldsymbol{\hat{S}}_{vi}\geq\eta$. Here we have

$\boldsymbol{\hat{S}}_{vi}=(1-\lambda)\boldsymbol{S}_{vi}+\lambda
E_{k}[\boldsymbol{S}_{ui}].$

1) If $\boldsymbol{S}_{vi}\leq E_{k}[\boldsymbol{S}_{ui}]$, then

$\displaystyle\boldsymbol{\hat{S}}_{vi}-\boldsymbol{S}_{vi}$
$\displaystyle=(1-\lambda)\boldsymbol{S}_{vi}+\lambda
E_{k}[\boldsymbol{S}_{ui}]-\boldsymbol{S}_{vi}$
$\displaystyle=-\lambda(\boldsymbol{S}_{vi}-E_{k}[\boldsymbol{S}_{ui}])$
$\displaystyle\geq 0.$

Thus, $\boldsymbol{\hat{S}}_{vi}\geq\boldsymbol{S}_{vi}$. 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 $\boldsymbol{S}_{vi}>E_{k}[\boldsymbol{S}_{ui}]$, then

$\displaystyle 0$
$\displaystyle<\boldsymbol{S}_{vi}-E_{k}[\boldsymbol{S}_{ui}]$
$\displaystyle\leq\boldsymbol{S}_{vi}-(\eta-\Delta).$

Thus, $\boldsymbol{S}_{vi}-\eta>-\Delta$. Then we have

$\displaystyle\boldsymbol{\hat{S}}_{vi}-\eta$
$\displaystyle=(1-\lambda)\boldsymbol{S}_{vi}+\lambda
E_{k}[\boldsymbol{S}_{ui}]-\eta$
$\displaystyle=(1-\lambda)(\boldsymbol{S}_{vi}-\eta)+\lambda(E_{k}[\boldsymbol{S}_{ui}]-\eta)$
$\displaystyle>(1-\lambda)(-\Delta)+\lambda(-\Delta)$ $\displaystyle=-\Delta.$

Thus, $\boldsymbol{\hat{S}}_{vi}>\eta-\Delta$. Since $\hat{\eta}<\eta$ and
$\Delta$ is very small, the probability of
$\boldsymbol{\hat{S}}_{vi}<\hat{\eta}$ is very low. This means even though in
this case we may have corrupted some scores corresponding to the other labels,
the probability of $\boldsymbol{\hat{S}}_{vi}>\hat{\eta}$ is very high.

#### Finally

$\mathbb{E}[|\mathcal{C}(\boldsymbol{x})|]\leq\mathbb{E}[|\tilde{\mathcal{C}}(\boldsymbol{x})|]$.

##  Appendix B Algorithm overview

The pseudo-code for SNAPS is presented in Algorithm 1. First, we preprocess
the feature matrix to obtain the similarity graph. Then, we treat the GNNs
model as a black box to generate node embeddings. Finally, we perform
conformal prediction using SNAPS.

Algorithm 1 Conformal prediction with SNAPS for GNNs pseudo-code

0: Graph $\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$, feature matrix
$\boldsymbol{X}$, label set $\mathcal{Y}$, adjacency matrix
$\boldsymbol{A}$GNNs Model $f$, activation function $\sigma$basic score
function $s$, SNAPS score function $\hat{s}$Calibration data set
$\mathcal{D}_{\text{calib}}=\\{(\boldsymbol{x}_{i},y_{i})\\}_{i=1}^{n}$test
node $v_{n+1}$Significance level $\alpha$

1: Preprocessing: construct similarity graph $\boldsymbol{A}_{s}$ based on
node features Train GNNs model $f(\mathcal{G},\boldsymbol{X})$

2: $\forall v_{i}\in\mathcal{V}$,
$\boldsymbol{p}_{i}=\sigma(f(\boldsymbol{x}_{i}))$

3: $\forall v_{i}\in\mathcal{V},\forall k\in\mathcal{Y}$, compute
$\boldsymbol{S}_{ik}=s(\boldsymbol{p}_{i},k)$

4: $\forall v_{i}\in\mathcal{V}_{\text{calib}}\cup\\{v_{n+1}\\}$, compute
$\boldsymbol{\hat{{S}}}_{i}=\hat{s}(\boldsymbol{S}_{i},\boldsymbol{A}_{s})$

5: Sort all SNAPS scores
$\mathcal{S}=\\{\boldsymbol{\hat{S}}_{i}\\}_{i=1}^{n}$

6: Set
$\hat{q}:=\mathrm{Quantile}(\frac{\lceil(1-\alpha)(n+1)\rceil}{n};\mathcal{S})$

7: $\forall k\in\mathcal{V}$, compute $\hat{s}(\boldsymbol{x}_{n+1},k)$

8: return
$\mathcal{C}_{\alpha}(\boldsymbol{x}_{n+1})=\\{k|\hat{s}(\boldsymbol{x}_{n+1},k)\leq\hat{q}\\}$

###  B.1 Time Complexity

Constructing the similarity graph will have particularly high time complexity
for large-scale graphs if we compute the feature similarity between each node
pair, i.e., time complexity is $\mathcal{O}(N^{2})$. To address this problem,
we randomly select a subset of nodes as the target node set with a size of
$M\ll N$. We then calculate the similarity between the nodes in calibration
and testing sets and the nodes in the target set, and select $k$-NN. This
approach reduces the time complexity to $\mathcal{O}(MN)$.

##  Appendix C Detailed Results

In this section, we report the detailed experimental results. Firstly, we
report the results of $\mathrm{Coverage}$, $\mathrm{Size}$, $\mathrm{SH}$
across different datasets using different GNNs models in Table 4, Table 5,
Table 6, Table 7. Then, we report the results of $\mathrm{Coverage}$,
$\mathrm{Size}$, $\mathrm{SH}$ using RAPS as the basic non-conformity scores
in Table 8. Finally, We added two additional datasets CiteSeer and Amazon
Computers to observe changes in the distribution of mean scores for each label
in Table LABEL:fig:citeseer-size and Table LABEL:fig:com-size. The results
show that SNAPS achieve superior performance.

Table 4: Results of $\mathrm{Coverage}$, $\mathrm{Size}$, $\mathrm{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 $\alpha=0.1$. Bold numbers indicate
optimal performance.

| Coverage | Size$\downarrow$ | SH%$\uparrow$
---|---|---|---
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 | 0.900 | 0.900 | 0.900 | 0.900 | 10.70 | 5.50 | 6.63 | 5.48 | 16.31 | 1.87 | 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 | 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 | 0.900 | 0.900 | 0.900 | 3.143 | 2.055 | 2.201 | 1.978 | 50.139 | 51.327 | 61.137 | 61.753

Table 5: Results of $\mathrm{Coverage}$, $\mathrm{Size}$, $\mathrm{SH}$ on
different datasets. For SNAPS we use the APS score as the basic score. We
report the average calculated from 10 GAT trials with each trial of 100
conformal splits at different significance levels ($\alpha=0.05,0.1$). Bold
numbers indicate optimal performance.

| Coverage | Size$\downarrow$ | SH%$\uparrow$
---|---|---|---
Datasets | APS | RAPS | DAPS | SNAPS | APS | RAPS | DAPS | SNAPS | APS | RAPS | DAPS | SNAPS
| $\alpha=0.05$
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
Physics | 0.950 | 0.950 | 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
| $\alpha=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.901 | 2.05 | 1.59 | 1.63 | 1.56 | 49.10 | 50.44 | 61.08 | 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 | 0.900 | 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.02 | 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 6: Results of $\mathrm{Coverage}$, $\mathrm{Size}$, $\mathrm{SH}$ on
different datasets. For SNAPS we use the APS score as the basic score. We
report the average calculated from 10 APPNP trials with each trial of 100
conformal splits at different significance levels ($\alpha=0.05,0.1$). Bold
numbers indicate optimal performance.

| Coverage | Size$\downarrow$ | SH%$\uparrow$
---|---|---|---
Datasets | APS | RAPS | DAPS | SNAPS | APS | RAPS | DAPS | SNAPS | APS | RAPS | DAPS | SNAPS
| $\alpha=0.05$
CoraML | 0.950 | 0.950 | 0.950 | 0.950 | 2.20 | 2.01 | 1.78 | 1.66 | 46.85 | 27.70 | 55.12 | 54.74
PubMed | 0.950 | 0.950 | 0.950 | 0.950 | 1.75 | 1.75 | 1.74 | 1.67 | 36.42 | 32.58 | 36.79 | 41.25
CiteSeer | 0.950 | 0.950 | 0.950 | 0.950 | 2.18 | 2.22 | 1.88 | 1.86 | 54.08 | 34.40 | 61.85 | 59.74
CoraFull | 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
| $\alpha=0.1$
CoraML | 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 | 0.900 | 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

Table 7: Results of $\mathrm{Coverage}$, $\mathrm{Size}$, $\mathrm{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 ($\alpha=0.05,0.1$). Bold
numbers indicate optimal performance.

| Coverage | Size$\downarrow$ | SH%$\uparrow$
---|---|---|---
Datasets | APS | RAPS | DAPS | SNAPS | APS | RAPS | DAPS | SNAPS | APS | RAPS | DAPS | SNAPS
| $\alpha=0.05$
CoraML | 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 | 0.950 | 2.09 | 2.06 | 2.01 | 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 | 0.950 | 0.950 | 4.36 | 1.57 | 1.69 | 1.31 | 32.81 | 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 | 0.950 | 0.950 | 3.20 | 3.12 | 2.12 | 2.16 | 18.14 | 10.66 | 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
| $\alpha=0.1$
CoraML | 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 | 2.33 | 21.22 | 19.07 | 28.64 | 34.40
CoraFull | 0.900 | 0.900 | 0.900 | 0.900 | 16.34 | 16.35 | 10.27 | 10.31 | 0.00 | 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 | 0.901 | 0.900 | 0.900 | 0.901 | 3.90 | 3.77 | 2.75 | 2.78 | 7.27 | 5.09 | 17.09 | 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 8: Results of $\mathrm{Coverage}$, $\mathrm{Size}$, $\mathrm{SH}$ on
different datasets. For SNAPS we use the RAPS score as the basic score. We
report the average calculated from 10 GCN trials with each trial of 100
conformal splits at different significance levels ($\alpha=0.05,0.1$). Bold
numbers indicate optimal performance.

| $\alpha=0.1$ | $\alpha=0.05$
---|---|---
Datasets | Coverage | Size$\downarrow$ | SH%$\uparrow$ | Coverage | Size$\downarrow$ | SH%$\uparrow$
| 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 | 0.900 | 5.50 | 5.48 | 1.87 | 1.39 | 0.950 | 0.950 | 10.72 | 10.70 | 2.13 | 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 | 0.900 | 1.00 | 1.00 | 89.92 | 90.00 | 0.950 | 0.949 | 1.07 | 1.04 | 88.89 | 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.900 | 0.901 | 2.12 | 2.17 | 17.00 | 13.85 | 0.950 | 0.950 | 3.62 | 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

##  Appendix D 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., 2017a] 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 et al., 2021]
to measure how prediction sets violate the conditional coverage. Specifically,
considering a disjoint set-size strata $\\{S_{i}\\}_{i=1}^{N_{s}}$, where
$\bigcup_{i=1}^{N_{s}}S_{i}=\\{1,2,\cdots,|\mathcal{Y}|\\}$. Then, we define
the indexes of examples stratified by the prediction set size by
$\mathcal{J}_{j}=\\{i:|\mathcal{C}(\boldsymbol{x}_{i})|\in S_{j}\\}$.
Formally, we can define the SSCV as:

$\text{SSCV}=\sup_{j}\left|\frac{\left|\\{i\in\mathcal{J}_{j}:y_{i}\in\mathcal{C}\left(\boldsymbol{x}_{i}\right)\\}\right|}{\left|\mathcal{J}_{j}\right|}-(1-\alpha)\right|$
(6)

where $\alpha$ is the significance level. In our experiments, we follow the
setting of RAPS [Angelopoulos et al., 2021], choosing a relatively coarse
partitioning of the possible set sizes: 0-1, 2-3, 410, 11-100, and 101-1000.

##  Appendix E More Details on Dataset and Models

Table 9 displays the statistics of the dataset used for the evaluation. For
CoraFull∗ we remove the classes (and the respective nodes) that have a number
of instances less than 50 in order to have the same number of nodes per class
in each train/validation split [Zargarbashi et al., 2023]. Table 10 summarizes
the model’s accuracy on every dataset.

Table 9: Statistics of the ten datasets. Datasets | Nodes | Features | Edges | Classes | Homophily
---|---|---|---|---|---
CoraML | 2995 | 2879 | 16316 | 7 | 78.85%
PubMed | 19717 | 500 | 88648 | 3 | 80.23%
CiteSeer | 4230 | 602 | 10674 | 6 | 94.94%
CoraFull∗ | 19749 | 8710 | 126524 | 68 | 56.76%
Coauthor CS | 18333 | 6805 | 163788 | 15 | 80.80%
Coauthor Physics | 34493 | 8415 | 495924 | 5 | 93.14%
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%
Table 10: Accuracy report for datasets and models involved in the analysis. Dataset | GCN | GAT | APPNP | MLP
---|---|---|---|---
CoraML | 81.48±1.80 | 79.09±2.44 | 82.18±1.52 | 62.82±1.85
PubMed | 77.40±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.11
CoraFull | 60.53±0.62 | 50.19±0.74 | 61.08±0.48 | 38.06±0.65
CS | 91.24±0.40 | 88.01±1.04 | 91.40±0.46 | 88.06±0.57
Physics | 93.11±0.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.49±3.73
Photo | 89.64±1.21 | 88.49±0.90 | 89.69±2.19 | 74.41±3.68
Arxiv | 70.53 | - | - | -
Products | 75.44 | - | - | -