Similarity-Navigated Conformal Prediction for Graph Neural Networks

We appreciate the reviewer for the insightful and detailed comments. Please find our response below:

1. Scalability / Computation cost [W1]

Thank 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)$.

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})$.

2. Inductive learning [W2]

In 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.

3. Performance on heterophilous graphs [W3 & Q1]

We 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:

FSGNN [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:

We can observe that SNAPS still shows consistent superiority over the baselines on heterophilous networks, which demonstrates its weak dependence on homophily.

[1] Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures. WWW'11.

[2] DAPS: Conformal Prediction Sets for Graph Neural Networks. ICML'23.

[3] Uncertainty Quantification over Graph with Conformalized Graph Neural Networks. NeurIPS'23.

[4] Improving Graph Neural Networks with Simple Architecture Design. arxiv'21.

[5] Geom-GCN: Geometric Graph Convolutional Networks. ICLR'20.

We appreciate the reviewer's insightful feedback. Please find our response below:

1. Sampling method for large-scale dataset [W1]

To 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.

2. Necessity of using feature similarity as an additional calibration method [W2]

Sorry 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:

The table demonstrates that the relative difference in feature similarity between the identical and different labels is significant.

3. Choice of hyper-parameters $\lambda$ and $\mu$ [W3]

In 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:

The results show that SNAPS, with default hyper-parameters, outperforms RAPS and DAPS, even though both baseline methods are tuned on a hold-out dataset.

4. Conflict between the explanation in lines 272-273 and the observation in Figure 1c [Q1]

Thank 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:

Figure 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.

5. Extension to heterophilous datasets [Q2]

we 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:

For 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:

[1] DAPS: Conformal Prediction Sets for Graph Neural Networks. ICML'23.

[2] Uncertainty sets for image classifiers using conformal prediction. ICLR'21.

[3] Graph Neural Networks for Graphs with Heterophily: A Survey. arxiv'22.

[4] Improving Graph Neural Networks with Simple Architecture Design. arxiv'21.

[5] Geom-GCN: Geometric Graph Convolutional Networks. ICLR'20.

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:

1. Calibration set size [W1 & Q3]

Here, we provide effect analysis of various calibration set sizes:

1. 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$:

The detailed results can be found in Table 1 of the attachment.

2. Small calibration set size. The results of the average size are shown in the following table

The results above both show that SNAPS consistently outperforms other methods under different calibration set size setups. In Figure 1 from the attachment, more results on different datasets can be found.

For the vision dataset ImageNet, we provide the average results across different models for SNAPS and APS in Table 2 of the attachment. Despite the small size of calibration set, SNAPS still outperforms APS for classification problems.

2. Choice of hyper-params [W2 & Q5]

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.

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].

How does Figure 4c and 4d look like for other datasets? We provide experimental results of other datasets in Figure 3 of the attachment.

3. Other methods for similarity graph construction [W3 & Q6]

To 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:

The results demonstrate that the similarity graph constructed based on self-supervised learning is applicable to SNAPS.

4. Effect of the aggregated APS scores / the augmented graph on the prediction accuracy [Q1]

Thank 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:

The results indicate that SNAPS slightly enhances prediction accuracy, which may be one reason for SNAPS's effectiveness.

5. Comparison with CF-GNN [Q2]

To 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.

6. Different significance levels $\alpha$ [Q4]

Here are the average set size across 10 GCNs with each trial of 100 conformal splits for CoraML at different significance levels:

The 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.

7. Limitation to homophily

We 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.

[1] DAPS: Conformal Prediction Sets for Graph Neural Networks. ICML'23.

[2] Simple and Asymmetric Graph Contrastive Learning without Augmentations. NeurIPS'23.

[3] Uncertainty Quantification over Graph with Conformalized Graph Neural Networks. NeurIPS'23.

We appreciate the reviewer's recognition and valuable suggestions. Please find our response below:

1. Discussion regarding the assumption in Proposition 2 [W1]

Thank you for the great suggestion. Here is our discussion regarding the assumption in Proposition 2.

Given 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 $\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$.

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.

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 $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],$

i.e., $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].$

Let $\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 $\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