Conformal Inductive Graph Neural Networks

We thank the reviewer for reading our paper and comments. Here we address the concerns pointed out by the reviewer:

Weaknesses:

(1) Our approach was to discuss the related works in context throughout the paper. For completeness, we now added a dedicated section in the appendix (section F) and provide a forward reference in the main paper (end of section 2).

(2) The suggestion to first introduce the method and then give the theoretical analyses is interesting and we agree that it can indeed improve readability. Since this is a major change that would disrupt the discussion with the reviewers (since sections will change) we defer this to after the rebuttal. Note, the algorithm which we added to the appendix for completeness is implicitly defined via the equations in section 4 since it essentially has only two steps: (1) computing (a potentially weighted) quantile line 3 or line 5, and (2) creating a set of scores above the quantile line 6. We also now updated it to clarify how $S_t$ is used.

(3) We are not aware of any baselines that are applicable expect standard CP and NAPS. In Appendix C we compared our approach to NAPS. On Figure 6 (left) we show the empirical coverage and we see that our approach matches the nominal value while NAPS consistently under/overcovers. Note, here we outperform NAPS even though the experimental setup favours NAPS since we can only evaluate the coverage on the subset of applicable nodes (nodes that have at least one calibration node in their neighbourhood). On Figure 6 (right) we further show the number of non-applicable nodes for NAPS which grows with time. All nodes are applicable for our approach.

As mentioned in section 2 and subsection 2.1, the coverage guarantee is probabilistic and can deviate from the specified value $1 - \alpha$. The concentration around $1 - \alpha$ (or the standard deviation) is a function of the calibration set size. The distribution (including the variance) is precisely characterized in Theorem 3. A realistic assumption for sparse graph is to have a calibration set not larger than the train set. Hence the small calibration set results in a relatively large variance. As we increase the calibration set size the variance quickly decreases (see figure 17).

We added results on large graphs Flickr, and Reddit2 to the appendix (section D.5). Interestingly the results on node-exchangeable sampling is close for both standard and subgraph CP. However in the edge-exchangeable sampling the result is different and only weighted subgraph CP can provide a valid coverage guarantee.

(4) As we explained in the paper, the coverage guarantee is bounded by upper- and lower-bounds. The coverage probability either follows a beta distribution, or a collection of hyper-geometric distributions which in both cases a valid CP results in a coverage close to $1 - \alpha$. An invalid guarantee can result in either over- or mis-coverage. There are two important notes: (i) an over-covering break of the guarantee results in larger set sizes and less singleton hits (see Figure 4) (ii) if the guarantee is invalid, one can not spot whether over- or mis-coverage happens before evaluating the result which makes it inapplicable. That is why in we reported the deviation from the guarantee showing that validity of the guarantee not the empirical coverage.

We thank the reviewer for constructive comments and we are happy that the reviewer liked the paper. Here we address the comments and questions:

(1) We added a formal description of node-inductive and edge-inductive sequences and node-exchageability and edge-exchageability in section B of the appendix and modified sections 4.1 and 4.2. All changes are shown with blue color in the updated paper.

(2) Thank you for the valuable suggestions. We changed some parts of section 4.1 which hopefully make the example clearer.

(3) Which node is included at which timestep is a design choice. One can wait until the last timestep and evaluate all the nodes at once, or evaluate each node upon arrival, or $k$ steps after arrival, etc. This corresponds to looking at e.g. columns of the coverage matrix $\boldsymbol{C}$, or the different diagonals of matrix C. As long as the decision is made prior to observing the prediction sets (independent of the data) the coverage validity holds. Importantly, this implies that the guarantee does not hold for adversarially chosen evaluation sets. To illustrate this, we can pick the smallest prediction set for each node across all timesteps. This breaks the guarantee as shown in Figure 13 (Section D.4 in appendix).

(4) Thank you for this suggestion. We now define $\mathrm{Cov}(\cdot)$ in section 2.1.

(5) Indeed, we assume that the underlying model and thus the score function is permutation-equivariant. We updated our papers and the theorems to clarify this. We also discuss this assumption in more detail in appendix B.

(6) In light of the reviewer’s comment, we revised section 4.2 and added a formal theorem and a proof (section B in the appendix). In the paper we assume that the nodes from the first $m$ edges from an edge-exchangeable sequence are chosen for the calibration set. Any other exchangable selection that does not depend on the edge order, e.g. uniform sampling, is valid.

We also thank the reviewer for mentioning the typos. We have resolved them in the modified file.

We thank the reviewer for the time and constructive comments. In following we address the mentioned concerns:

Weaknesses

(1) Thank you for these valuable suggestions. We added the definition of the graph, and the assumptions on the trained model in section 2.1. We also added formal definitions of node-inductive and edge-inductive sequences, as well as node- and edge-exchangeability. We updated the caption of Fig. 1 to improve clarity and included a forward pointer to the appendix (D.5) where the experiment is explained in full detail.

(2) We agree that the term "calibration budget" does not bring additional value so we removed it from the paper. We also agree that the term "no longer congruent" is not necessary and have replaced it with "no longer exchangeable".

(3) You are right, thank you. We modified Theorem 1 and the text to reflect this.

(4) See the answer to question 3.

Questions:

(1) Yes. Both [1] and [2] propose methods to boost conformal prediction on graphs. [1] approaches this problem by a diffusion over the conformity scores, and [2] trains another GNN network from scratch. We theoretically show that any continuous score function while applied with subgraph (and weighted subgraph) CP can adapt to node- or edge-exchangeable inductive graph sequence. Any boosting method on top remains valid if applied in our framework.

(2) Thank you for this suggestion. We modified the beginning of section 2.1, 3, 4.1, and 4.2 and included a more formal definition of node- and edge-exchangeability. All changes are shown with blue color in the updated paper. Additionally we dedicated a discussion in appendix B.

(3) We identified three main limitations. First, as with most other CP methods, the guarantee is marginal. Second, real-world graph may not satisfy node- or edge-exchagability. This can be partially mitigated by the beyond exchangeability framework. Finally, the guarantee does not hold for adversarially chosen evaluation sets $\mathcal{V}_\mathrm{eval}$. In other words, the choice of which nodes and at which timesteps are included in the evaluation set must be done prior to observing the prediction set. In the initial submission we only mentioned the first limitation. We now added a discussion of all three (last paragraph of section 6).

(4) We updated the caption of Fig. 1 to improve clarity and included a forward pointer to the appendix (D.5) where the experiment is explained in full detail. Figure 9 compares Subgraph CP with Standard CP for different GNN models. CP is model-agnostic, and although the model architecture (as long as it is permutation equivariant) does not affect the validity, it does affect the set size. On the left we show empirical coverage which matches the nominal value for our approach for all models. The MLP baseline does not use the graph structure and is unaffected by the distribution shift. On the right we see that some GNNs return smaller sets on average.

References

[1] Zargarbashi, Soroush H., Simone Antonelli, and Aleksandar Bojchevski. "Conformal Prediction Sets for Graph Neural Networks." (2023).

[2] Huang, Kexin, et al. "Uncertainty quantification over graph with conformalized graph neural networks." arXiv preprint arXiv:2305.14535 (2023).

We thank the reviewer for the time and constructive comments on our paper. Here we address questions and concerns:

Weaknesses:

(1) We added the explicit definition of the graph in section 2.1. We also added the assumptions for the trained model (e.g. GNN), and the notation of graph in equation (3) follows the same definition. The graph $\mathcal{G}_t$ here shows the timestep in which the scores are computed (it refers to the present nodes and edges at timestep $t$). For the definition of simple message passing we added the definition of each matrix. Here $\boldsymbol{A}$ refers to the adjacency matrix , and $\boldsymbol{X}$ is the feature matrix (defined in section 2.1) and $\boldsymbol{W}$ refers to the weight matrix which is defined immediately after. We thank the reviewer for mentioning that and in case the notation is still not clear we ask the reviewer to kindly point it out.

(2) In Appendix C we compared our approach to NAPS. On Figure 6 (left) we show the empirical coverage and we see that our approach matches the nominal value while NAPS consistently under/overcovers. Note, here we outperform NAPS even though the experimental setup favours NAPS since we can only evaluate the coverage on the subset of applicable nodes (nodes that have at least one calibration node in their neighbourhood). On Figure 6 (right) we further show the number of non-applicable nodes for NAPS which grows with time. All nodes are applicable for our approach.

(3) We draw the reviewer’s attention to Figures 4, 7 (middle, right), 9 (right), 10 (right), 11 (right), 12 (right). We report two metrics regarding efficiency: average set size, and singleton hit ratio which captures what proportion of test nodes are predicted with a singleton set the includes the true label. On all figures and all metrics our approach is superior and has lower average set size and higher singleton hit ratio.

Question: The idea of figure 2 is to show which nodes are (mis)-covered at which timestep. We added description of matrix C and Figure 2, in Section B (appendix) with a reference to it in the caption of the figure. We also draw the review’s attention to Figure 7 (in the appendix), where we compare both methods standard CP and subgraph CP. In the same figure we also compare the matrix of set sizes and singleton hits.