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.

Similarity-Navigated Adaptive Prediction Sets (SNAPS) 是一种基于特征相似性和结构邻域的新算法，通过聚合具有相同标签的节点的不符合性得分来提高预测集的有效性，并在保持有效覆盖的同时增加单例命中率。