Similarity-Navigated Conformal Prediction for Graph Neural Networks

Summary

This paper addresses the problem of the lack of reliable uncertainty estimates in semi-supervised node classification tasks using Graph Neural Networks. This 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. The authors propose a method to aggregate the non-conformity scores based on feature similarity and structural neighborhood, to improve the efficiency of prediction sets and singleton hit ratio.

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. 2. 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. 3. 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. 2. The focus on transductive learning in the paper limits its applicability to inductive learning scenarios, which are common in real-world classification tasks. 3. 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.

Questions

How will the proposed method perform on heterphily graphs?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

2

Limitations

The authors discussed the limitations on transductive settings. N/A potential negative societal impact.

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.

Strengths

1. The paper is clearly written and well-structured, facilitating easy comprehension. 2. 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. 3. 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. Although 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. 2. 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. 3. As shown in Figure 4, the success of this method hinges on the empirical selection of $\lambda$ and $\mu$, which restricts its broader application.

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? 2. 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?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

See the weakness

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.

Strengths

The approach is well motivated and the proposed score is simple and intuitive which is a pro. While 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. In 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). The 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. Given the simplicity of the approach (which is a plus) the experimental evaluation should be strengthend (see questions). I am willing to increase my score if the authors adequately address my questions.

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? 2. 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? 3. How does the performance of SNAPS (and the baselines) change as you vary the calibration set size? Importantly, also for small (realistic) sizes. 4. How does the performance of SNAPS (and the baselines) change as you vary the significance level $\alpha$? 5. 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? 6. Have you considered other similarity metrics?

Rating

6

Confidence

5

Soundness

2

Presentation

3

Contribution

2

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.

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

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?

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?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

yes

Thank you for raising your score

Thank you for checking our rebuttal and raising your score. We will incorporate the new results and explanations into the final version appropriately. Sincerely thanks for your valuable time on this paper!

Thank you for increasing the score

We appreciate the valuable suggestions and feedback from the reviewer. We are also glad that most of your concerns have been addressed. Thanks again for increasing the rating!