Conformal Inductive Graph Neural Networks
Authors: Soroush H. Zargarbashi
Aleksandar Bojchevski
Venue: ICLR 2024 poster (2024)
Keywords: Conformal Prediction
Graph Neural Networks
Inductive Node Classification
Primary area: learning on graphs and other geometries & topologies
TL;DR: We adapt conformal prediction to node-classification under inductive scenario for both node-exchangeable and edge-exchangeable graphs.

Abstract: Conformal prediction (CP) transforms any model's output into prediction sets guaranteed to include (cover) the true label. CP requires exchangeability, a relaxation of the i.i.d. assumption, to obtain a valid distribution-free coverage guarantee. This makes it directly applicable to transductive node-classification. However, conventional CP cannot be applied in inductive settings due to the implicit shift in the (calibration) scores caused by message passing with the new nodes. We fix this issue for both cases of node and edge-exchangeable graphs,  recovering the standard coverage guarantee without sacrificing statistical efficiency. We further prove that the guarantee holds independently of the prediction time, e.g. upon arrival of a new node/edge or at any subsequent moment.

Published as a conference paper at ICLR 2024
CONFORMAL INDUCTIVE GRAPH NEURAL NETWORKS
Soroush H. Zargarbashi
Aleksandar Bojchevski University of Cologne
CISPA Helmholtz Center for Information Security Margarbashi@cs ani-koeln.de
bojchevski@cs. uni mni-Ken kooknoonnnnnnooonnoo.o.ee....... de
ABSTRACT
Conformal prediction (CP) transforms any model's output into prediction sets guaranteed to include (cover) the true label. CP requires exchangeability. a re- laxation of the i.i.d. assumption, to obtain valid distribution-frre coverage guar- antee. This makes it directly applicable to transductive node-classificatin. How- ever, conventional CP cannot be applied in inductive settings due to the implicit shift in the (calibration) scores caused by message passing with the new nodes. We fix this issue for both cases of node and edge-exchangeable graphs, recover- ing the standard coverage guarantee without sacrificing statistical efficiency. We further prove that the guarantee holds independently of the prediction time, e.g. upon arrival of new node/edge at any subsequent moment.
INTRODUCTION
Graph Neural Networks (GNNs) are used in many applications however without a reliable estimation of their output's uncertainty. We not rely solely the predicted distribution of labels ( æ)) (e.g. from the softmax) as it is often uncalibrated. Therefore, is crucial to find confidence estimates aligned with the true pv x). There a rich literature on uncertainty quantification methods many of which require retraining or modifications to the model architecture. Among them, almost none come with guarantee, and many rely on the i.i.d. assumption. Given the interdependency structure (adjacency) we cannot easily adopt these methods for node classification. As a result, uncertainty quantification methods for GNNs are very limited (Stadler al. 202T).
Conformal prediction (CP) is an alternative approach that uses the model as a black box and returns prediction sets guaranteed to cover the true label without any assumptions on the model's architec- ture or the data generating process. This guarantee is probabilistic and works for any user-specified probability - a. To apply CP, we need a conformity score function 8 X x y + ER that quan- tifies the agreement between the input and the candidate label. Additionally, we need a held-out calibration set. The only assumption for a valid coverage guarantee is exchangeability between the calibration set and the test set. This makes CP applicable to non-i.i.d settings like transductive node classification - ZZararbbashi et al.] (2023) and Huang et al. (2023) showed that with a permutation- equivariant model (like almost all GNNs) CP obtains valid coverage guarantee.
Given the dynamic nature real-world graphs which evolve over time, inductive node classification more reflective of actual scenarios than transductive. In the inductive setting, we are given an initial graph (used for training and calibration) which is progressively expanded by set of nodes and edges introduced the graph over time. Importantly test nodes are not present the training and calibration stage. For GNNs, updates in the graph cause an implicit shift in the embeddings of existing nodes and consequently the softmax outputs and conformity scores. Therefore. in the inductive setting, even assuming node/edge exchangeability (see f B for formal definition), the coverage guarantee is no longer valid. Intuitively, calibration scores are no longer exchangeable with test scores,
nodes edges are introduced (see Fig. rright).
To address this issue, Clarkson (2023) adapt the beyond exchangeability approach applying weighted CP for inductive clde-classification aiming to recover the guarantee up bounded (but unknown) error (Barber et al. 2023). Unfortunately, this approach has an extremely limited applicability when applied with realistic (sparse) calibration set. In sparse networks and limited labels, the method fails to predict any prediction set for a large number of nodes; and for the rest, the statistical effi- ciency is significantly low (see $ C for details).

---

Published as a conference paper at ICLR 2024
2
Density
Standard CP
-0.2
1000
-0.4
2000
-1.0
-0.8
-0.6
-0.4
-0.2
0.0
-0.6
Score
3000
NodeEx CP
EMD Dist.
Naive CP
-088
0.05 0.10
Cal
4000
Ground Truth
Test
1000
2000
3000
1000
2000
3000
4000
Timestep
Timestep
Figure 1: [Left] Each vertical line the heatmap shows sorted true dashed line shows the true (unknown) a-quantile and the quantile from each approach is also shown alongside. NodeEx CP (ours) closely tracks the true quantile, while naive CP deviates over time. [Upper right] Distributions from selected timesteps marked by the same color on the heatmap. The distribution shift is observable over time with new nodes appearing. [Lower right] The earth mover distance (EMD) between naive CP calibration scores and shifted true scores, denoted as "Test"; and EMD between naive and NodeEx CP scores, denoted as "Cal". Details D.5
each timestep. The
We show that for node or edge exchangeable graph sequence (without distribution shift), we can adapt CP w.r.t. the implicit shift in score space, recovering the desired coverage guarantee. Node- exchangeabilityy assumes that the joint distribution of nodes is invariant to any permutation. In the inductive setting, this means that any node is equally likely appear at any timestep. We show that under node-exchangeabiiie and the existing nodes. Hence, computing the conformity scores conditional to the subgraph at any timestep recovers the guarantee. Previous works under the transductive setting (Zargarbashi et al. 2023) and (Huang et al. 2023) also assume mode-exchangeabllity
the effect new coming nodes is symmetric to the calibration set
While real-world graphs are sparse, all node-exchangeable generative processes produce either empty dense graphs (see 3). Therefore, we extend our study the edge-exchangeable set- ting which can generate sparse graphs. In 4.2 we show that w.r.t. scores, any edge-exchangeable sequence equivalent
weighted node-exchangeable sequence. Therefore, through weighted CP (weighted quantile lemma from Tibshirani et al. (2019) we recover the 1 a coverage. Impor- tantly, the improvement of our method is orthogonal to whether there is distribution shift over time. Therefore, to address shift, we can still apply the weighting scheme from Barber et al. (2023) on top.
We focus on inductive code-classfficttion. We define node-exchangeable (NodeEx) CP, and we show that (i) for node-exchanggable sequences, NodeEx CP obtains shifted conformal scores conditional subgraphs in each timestep (Fig. left), (ii) the 1 a guar- antee is achievable via weighted CP on edge-exchangeable sequences, and (iii) The guarantee holds independent of the prediction time - the prediction set for a node at any timestep after its appearance benefits from the same coverage guarantee (e.g. prediction upon arrival or all nodes once both result in the same coverage). We justify our approach with both theoretical and empirical results.
guarantee by calibrating over
2 BACKGROUND: CONFORMAL PREDICTION AND TRANSDUCTIVE GNNS
Here recall the general guarantee of CP (c.g. for image dataset). Through this paper, assume a continuous score function without ties. This can apply to any function via adding noise. With weights w, [0, 1], and the sorting permutation 7*, we define the weighted quantile Quant (:::-)
Quant (a: (s:) ( ( inf (T((0)
w++ Σ Wj +1
Σj
2 a
2

---

Published as a conference paper at ICLR 2024
Theorem 1
Vovk et al. 2005 ). Let {(z,, Yo and (In+1, Bn+1) be exchangeable. With any
continuous function s x + R measuring the agreement between æ, and y, and user-specified significance level a (0,1), with prediction sets defined as C. (I,+1) {y s( y) 2 4)
where q == Quant (å; (s(2s, (i))= }). We have Prob [yn+1 E C(xn+1)) 2 az.
The marginal coverage probability is upper-bounded by 1 - a 1 + 1). With infinite samples, the coverage is distributed as a Beta(n + 1.1) with = [nn + 1)al (Vovk 2012), while with a fixed population [D] = + and exchangeable calibration set [Deal] 71, the probability of coverage Cov \ Deat)= : [1/m) E ((x)))eE--D Deu. derives from a collection of hyper-
geometric distributions (Huang et al. (023).
Conformity scores. The guarantee from Theorem I holds regardless of how the conformity score function : X' x y + R is defined. A wise choice of s(..-) is reflected in other metrics like the prediction set size. We use adaptive prediction sets (APS) with a score function defined as a(ar, y) := (p(æ, y) + (ar)y)) Here p(ær, y) = ΣK c=1 T(x) [π()), > =(x))]] is the sum of
all classes predicted as more likely than y. and E [0, 1 is a uniform random value that breaks the ties between different scores to allow exact 1 - a coverage (Stutz et al.) (022). Our method is independent of the choice of score function and we show its applicability on other neetorr--agnostic and network-award, scores in $ D.3
CP beyond exchangeability. For cases where the calibration and test points are not exchangeable, there is a coverage gap A., i.e. Prob [yn+1 E (xx++ > - A.. Barber et al. (2023) shows that A, has an upper bound that depends on how far the data deviates from exchangeability. This
upper bound can be further controlled via weighted conformal prediction. For related works see F
2.1 CONFORMAL PREDICTION FOR TRANSDUCTIVE NODE ADDE-CLASSIFICATIONN
Consider graph E, with X E Raxd as node-features matrix, A E Rxx= adjacency matrix, and y E R" as labels. V = Vur J Veat Uv is the set of vertices (training, calibration, and test). Let f be black-box and 8 be a continuous score function with access to the outputs of ʃ. The score function may or may not use information about the graph structure (see D.3). In the transductive setup the graph G is fixed, and training and calibration is performed with all observed nodes (including features and structure). The labels of Vur and Veal are used respectively for training and calibration, while all other labels remain unseen, Here when Veal and Vu are exchangeable, standard CP can be applied Zargarbashi et al. 2023) Huang et al.) (2023). For set with a fixed number of nodes V we define the discrete coverage as Cov(V")= = TP Σnyew MJ E ((s))) The following theorem shows that under transductive calibration, CP yields valid prediction sets.
model (e.g. GNN) trained labels of Var.
Theorem 2 (Rephrasing of Theorem by Huang et al. permutation-equvvanee score function s(--)). with Veal from V \. Vu, and prediction sets Č(u)= = {yy : s(v, 8) 2 Quant (a; [s(0,,
(2023)). For fixed graph G, and (:)) exchangeably sampled we have
Prob (Cov(V.) S =t]=1 Hna 1;M N,N,[MM taa)
(2)
where in [(N + () a is the unweighted o-quantile index of the calibration scores, and a HHG(; N,n, n, K) is the c.d.f. of a hyper-geometric geometric distribution with parameters N (population). n number of samples, and K number of successful samples among the population.
The issue with inductive node-clasiification The above approach does not directly translate the inductive setting. As soon as the graph is updated, the implicit shift in the nodes embeddings results in distribution shift w.r.t. the calibration scores that are computed before the update. This breaks the exchangeability as shown by Zargarbashi et al. (2023) and in Fig. 1 To address this issue, /ssue,Cllark, weights (NAPS), limiting the calibration nodes to those inside an immediate neighborhood of test node. Applying NAPS on sparse graphs or with small (realistic) calibration sets, leaves a significant proportion of test nodes with an "empty" calibration set. Hence, its applicability is limited to very special cases (see I Cfor details). Moreover, NAPS does not quantify the coverage gap A,, In contrast, when assum- ing either node or edge-exchangeability the gap for our approach is zero regardless of the weights.
son] adopts weighted CP (Barber et al. (023)) with srihhorhhoddddeenndee
3

---

Published as a conference paper at ICLR 2024
3 INDUCTIVE GNNS UNDER NODE AND EDGE EXCHANGEABILITY
In the inductive scenario, the graph changes after training and calibration. Therefore, the model f is trained, and CP is calibrated only on subgraph before the changes. We track these updates in sequence of graphs G1, 12......... where G. = (V,, ) is a graph with finite set of vertices and edges. We focus on progressive updates meaning vt' : V. S Vz+1 and & S E 1. At timestep / in node- inductive sequence, the update adds node 24 with all its connections to existing vertices. In an edge- inductive sequence, updates add an edge, which may or may not bring unseen nodes with it. W.l.o.g update sets are singular. Node-inductive and inge-inducttve sequences are formally defined in S B
We call a node-inductive sequence to be exchaneeaneee if the generative process is invariant to the order of nodes, meaning that any permutation of nodes has the same probability. Analogously, a sequence
excchnnccce if all permutations of edges are equiprobable. For both cases, the problem is node-clasiffiction. Since split CP is independent of model training w.l.o.g. we assume that we train on an initial subgraph Go. We do not need to assume that Go is sampled exchangeably. Formal definitions of node- excchangaaangbbltt and exceangaccaa are provided in B
For transductive GNNs, both Zargarbashi et al. (2023) and Huang et al. (2023) assume that the calibration set is sampled node-exchangeably w.r.t. the test set, however the entire graph is fixed and given. In contract, we assume that the sequence of graphs G1 92.... itself, including calibration and test nodes, is either node- edge-exchangeable Transductive setting can be seen special case.
Sparsity. Any node- node-exchangen exchangeablee graph is equivalent to mixture of graphons (Aldous) 1981,
Hoover 1979: Cai et al., 2016). A graphon (or graph limit) is symmetric measurable function W: 0. 1 0, and the graph is sampled by drawing us ~ Uniform(0, 1] for each vertex vi. and edge between 0,, and v, with probability W(u, u,) We know that graphs sampled from graphon are almost surely either empty or dense (Orbanz & 2014 Cai et al. 2016) the number of edges grows quandratically w.r.t. the number of vertices. However, sparse graphs (with edges sub- quadratical in the number of vertices) are more representative to real-world networks. Therefore, we also consider ddge-exchangeeble graph sequences (Cai et al., 2016) that can achieve sparsity.
CONFORMAL PREDICTION FOR EXCHANGEABLE GRAPH SEQUENCES
The first N nodes of the sequence (and their labels) are taken as the calibration set, leaving the rest of the sequence to be evaluated For easier analysis, we record the coverage of each node at each timestep. Let To be the time when the last calibration node arrived. Up to timestep T, let matrix C' e {0, 1) T with Cii, t] indicate whether the prediction set for test node v; at timestep t covers the To and w.l.o.g. we index nodes upon their appearance. Hence, in each column Cl t). the first [V]] elements are in f0, 1} and the rest are N/A. Formally:
true label yı- The time index in C' is relative to
Ci = [1 [u E {u: s(v; v) 2 Quant (a; (s(1s, vilG.) M, ;1)} \N/A
i 2
(3)
O.W.
Here we assume that one can evaluate node at any timestep after its appearance. We define vit) eval S V as For an edge-
the of nodes evaluated at timestep exchangeable sequence, a node v is considered as active (existing) upon the arrival of the first edge connected to
3000 2000 1000
Nodes
it. After T timesteps, we call the (recorded) sub-partition UI_ eval an evaluation mask Tr- Any node appears at
most once in Ty (we do not re-evaluate a node). We define the Cov (V(() eval)
evall Evrevto, Cli, 4) as the em- pirical coverage over the mask V!!)) evol Similarly, Cov the empirical coverage for IT (average over all records). We visualize 1 - C under node exchangeability on Fig. 2
(1/
0.
1000 2000
3000
Timestep
Figure 2: 1 C' for Cora. Details in $ B
All results can be trivially generalized to the case where the calibration nodes are scattered in the sequence.
This only affects the width of the coverage interval (the variance) as it is directly function of the number of available calibration nodes when computing prediction sets.
4

---

Published as a conference paper at ICLR 2024
4.1 NODE-EXCHANGEABLE SEQUENCES
A node-inductive graph sequence is node-exchangeable if any permutation of node appearance is equally likely each step, any unseen node has the same probability of appearing (see [s B
With the arrival of new nodes, the distribution of embeddings (and consequently scores) shifts (as shown in Fig. 1j. This is why calibrating prior to the update fails to guarantee coverage for new nodes. However, with node-exchangeabblity. calibration and evaluation scores computed conditional specific subgraph are still exchangeable. We extend Theorem 2 inductive GNNs on node- exchangeable graph sequences for any subset of evaluated vertices.
Proposition 1. At time step t, with graph G. = (V,, &t) from a node-exchangeable sequence, and a calibration set Veal consisting of the first nodes in Gb for any vi Vera C V. \ Veal define
c (w²) = {u- 8(),, 9x) 2 Quant (a: (s(Us, Vi 9t)) :1)
(4)
Then Prob y, (v²) uy vith
a. Moreover with m = | eval
Prob (ov() S 3 Hc - 1:m n, n, ia + [BE])
(5)
We deffer proofs to $ B Here we provide an intuitive justification of the theorem. First, if v(t) includes all vertices the problem reduces to the transductive case, for which Theorem aappliss with scores conditional on the current graph. Otherwise, V := V/ \ ((() eval is not empty. Here the effect
eval
of V is symmetric to Veal and y!! For instance, consider a linear message passing Z = AXW with weight matrix W (our results hold general). From standard CP we know that for row- exchangeable matrix X, X W is also row-exchangeable (a linear layer is permutation equivariant). Hence, we just question the row-exchangeability similarly split A into nine blocks based on the endpoints of each edge. We have that AX equals
AX. Split X into [XT cal X X and
eval
Acal-cal Aeval-cal Aprical
Acal-eval Aeval-eval Ayeeval
Acal- Aeval-V V Av..v
Acal-cal Xeal + Acal-eval Xeval Aevalcal Xeal + Aeval-eval Xoval
Acal-vi Xy
X=
+
Aeval. vaall Xy
Mat(1)
Mat(2)
For the guarantee to be valid, the first [Vail + Mevai rows should be exchangeable. For Mat this already holds due to node-exchangeability and Theorem 2] With X,, being common both only need Acal-v and Aeval-v be row-exchangeable which again holds
blocks of Mat(2), due to node exchangeability. Hence, the effect of V symmetric to calibration and evaluation sets. In other words, the shifted embedding still preserves the guarantee conditional to the graph at timestep t. The only requirement is to compute the conformal scores for all nodes including the calibration set and dynamically update the quantile threshold the threshold depends t. Another way to understand the theorem is that for any column in C, the expectation of any subset of elements a. Next, we generalize this guarantee any evaluation mask independent of time.
Theorem 3. On node-exchangeable graph sequence, with exchangeably sampled Veat consisting of the first n nodes 9v. for any valid partition Lr U._ (B8) we have
Prob yy: ((())()) (v:) E real 1
(6)
Moreover, it holds that Prob (Cov(lrr) S [] 1 (ia ||rl + n, da
[[lb]| -31)
Theorem 3 indicates that CP applies to inductive GNNs conditional to the subgraph which each node is evaluated. We will leverage this insight in 5 In conclusion, with node-exchangeable graph sequence, for any node v, appearing at timestep t, and evaluated at any timestep t' 2 t, holds that Prob yy E (x:) 2 a. Two special cases of this result are evaluation upon appearance (the diagonal of C) and evaluation all at once (the last column of C) which follows from Theorem 2] The latter also equivalent to the simultancous induuctvv setting in Zargarbashi et al. 2023). The user is flexible delay the prediction to any time, still preserving the guarantee.
5

---

Published as a conference paper at ICLR 2024
4.2 EDGE-EXCHANGEABLE SEQUENCES
In an edge-inductive sequence at each timestep an edge is added, G = () Ue
This edge may introduce new nodes connect existing ones. When all permutations f of the edge-sequence are equally likely. Prob [(1, (am......mm)) = Prob [(u(ee),... (....-((emm)))) [u(m)))] the sequence is edge-exchangeable (see for formal definition). We address this setting using a special case of weighted quantile lemma (Tibshirani et al. 2019) with weights defined by the frequency of elements.
Lemma Lel X { 3m) be exchangeable random variables and ʃ 2 + I be mapping defined on subsets of X. For any partitioning U m++1 X: X and 24 == f(X:) we have:
Prob 2n+1 & Quant (
3
We introduce the dige--xxchangeabbe (EdgeEx) CP and prove its guarantee by showing that any timestep f, an edge exchangeable sequence, is decomposed into weighted node exchangeable subse- quences with weights equal to 1/de((v). Then, on each subsequence weighted CP maintains valid guarantee. In this setup, there no isolated nodes, any node can be evaluated upon appearance.
Theorem 4. At each timestep t, given graph G. = E+) from an edge- tiige--echangebble sequence and with calibration set Veal, define q Quant (a;; {si) {1/deg(vv (v eV }), and for any 0j E Vlt define (v,) {y s(yy,)) 2 q). We have Prob [y, (v,)) 2
Via Theorem 4, EdgeEx CP is guaranteed to provide coverage. The result holds for each timestep 1, conditional that timestep.
NODE EXCHANGEABLE AND EDGE EXCHANGEABLE CP
Building upon the theory in 4 for node-exchangeable graph sequences we define node- exchangeable (NodeEx) CP with coverage guarantee conditional to the subgraph at each timestep. Recall that the shift in scores upon changes in the graph is symmetric for calibration and evalua- tion nodes. Hence, NodeEx recomputes the calibration scores with respect to the additional con- text. In an cdge-exchangeable sequence via Theorem 4] EdgeEx CP weighted NodeEx CP with w; L/de results in similar valid guarantee. Any further details about NodeEx also gener- alizes to the EdgeEx via Theorem 4
With both settings at each timestep t we have seen a set of nodes V,, Let (it) eval C V1 be the set of nodes evaluated at timestep t. This can contain any node from the past as long as they are not already evaluated. Specifically, we cannot use the prediction sets of particular node multiple times to compare and pick a specific one (see B D. for a discussion). We always assume that the calibration set is the union of all nodes appeared up to timestep / To and the test set contains the
remaining nodes. For a sequence of timesteps and corresponding evaluation sets { (tz, Vivai) i=Tu+1 ) where Up + V VT Veat, NodeEx CP (see A for algorithm) returns valid prediction sets. We use EdgeEx CP for edge-exchain blge-exxcangeable sequences.
CP on node-conditional random subgraphs. Another application of Proposition I is to produce subgraph conditional prediction sets even for transductive node-elassification For each node Utest define К subgraphs each including {Vestt) Veat and randomly sampled V с Vg. Then, we average the scores and return prediction sets. In another approach, we can run K concurrent CPs, each resulting in prediction set. Then we combine them with randomized voting mechanism to final prediction set. The resulting prediction sets include true labels with 1 probability. This approach works for any number of subgraphs. See D.I for further explanations.
Relation to full conformal prediction. In our paper, we technically adopted the split conforma approach where model training is separate from calibration due to its computational efficiency. An alternative is full conformal prediction, where to obtain score for (calibration) node E Veai and any candidate label y' w.r.t. a test node Utest we train a model from scratch on Veat U ((Veest: yf) and
"Similar results apply for updates with more than one edge. "Sometimes called inductive conformal prediction. However, this is an orthogonal use of the word inductive.

---

Published as a conference paper at ICLR 2024
consider its prediction for Ug. This involves training |eail - models for each y' and each test node, which is extremely expensive but can use all available labels. Transductive node classification can be seen middle ground between split and full conformal as explained by Hyyang al. (2023). Our approach is similarly in between instead of retraining the model from scratch we simply update the embeddings (and thus scores) by performing message-passing with the newly arrived nodes/edges.
6 EXPERIMENTAL EVALUATION
6.1 EXPERIMENTAL. SETUP AND DISCUSSION OF METRICS
We evaluate our approach for both node and edge exchangeable sequences where we have three options to make predictions: (i) upon node arrival, (ii) at a given fixed timestep shared for all nodes, (iii) at an arbitrary node-specific timestep (we choose at random). We compare our approach with naive CP where the coverage guarantee will not hold. Later we discuss why both over- and under- coverage are invalid. For completeness, we compare NodeEx CP with NAPS in [S Clin addition to detailed overview of its drawbacks. However, as discussed in 2.1 NAPS is not a suitable baseline. We use APS (Romano et al., 2020) the base score function while other scores are tested in D
Models and datasets. We consider 9 different datasets and 4 models: GCN Kipf & Welling (2017) GAT Veličković et al.] (2018), and APPNe/Klicpera et al.. (2019) as structure-aware and MLP as a structure-indepeddent model. We evaluate our NodeEx, and EdgeEx CP on the common citation graphs CoraML McCallum et al. (2004) CiteSeer [Sen et al. (2008), PubMed Namata et al. (2012), Coauthor Physics and Coauthor CS Shchur et al. (2018). and co- co-purchase graphs Amazon Photos and Computers |McAuley et al. (2015): Shchur al. (2018) (details in E). Results for Flickr (Young et al. 2014), and Reddit2 (Zeng et al. (019) (with GCN model and their original split) datasets are in D.S Here, the model only affects the efficiency and not the validity.
Evaluation procedure. For any of the mentioned datasets, we sample 20 nodes per class for training and 20 nodes for validation with stratified sampling. For the nodh-exchangeable setup, the calibra- tion set has the same size as the training. For the edge-exchangeable sequence, the same number of edges are sampled. Therefore, each round of simulation has a potentially different number of cali- bration nodes for the exchanebcaee setup. First, we take random sample of nodes train/val set and train the model on the resulting subgraph Go- Then, for the node-exchangeable sequence, randomly from the remaining nodes. Then, each timestep, we
first sample calibration add a random unseen node to the graph (with all edges to the existing nodes) and predict the class probability given the updated subgraph. We use the updated conformal scores create prediction sets for all existing test nodes until time t and record the empirical coverage results in column t of the coverage matrix C. Similarly, for the eeganeeecaa sampling, we sample calibration edges, and take both ends as calibration nodes. The remaining edges are sampled one at time. The rest of the procedure is the same as node-exchangeable setting and results in an analogous C.
Challenges with small calibration sets. With a limited number of samples in the calibration set, there will be an additional error in the coverage due to the discrete quantile function with a low sample rate. In practice, we take the [n/(n (n 1): a index of a discrete array the conformal threshold which is often not exactly equal to a quantile in the continuous domain. Therefore, expect 1 1/([/aai) + 1) error around 1 a. This error is in addition to the variance of the Beta or Hyper-geometric distribution and will converge to with increasing calibration set size.
Distance from target coverage. Our main evaluation criteria is the distance of empirical coverage w.r.t. the target a. For all datasets we set the desired coverage to 90%, and we report the (absolute) distance w.r.t. this value (see /S E). Each reported result is average of 10 different random node-exchangeable sequences and 15 different random edge-exchangeable sequences. Note that due to homophily, we observe a higher empirical coverage in the cochnnchaeee case which can wrongly be interpreted as being better. To address any potential confusion, first the guarantee invalid if it breaks either the lower or the upper-bound. In real-world deployment we do not have ground-truth labels to calculate empirical coverage, and if the guarantee is broken (in either direction) the output is unreliable nullifying the main goal of CP. Second, a higher empirical coverage also results in larger set sizes making the prediction sets less useful (see also Fig. 4)
"This is unlike split conformal that needs to split the available labels into training and calibration sets.
7

---

Published as a conference paper at ICLR 2024
1.00
1.00
Guarantee
Coverage
0.95
NodeEx
Coverage
0.95
Naive CP
0.90
0.90
0.85
0.85
1000
2000 Timestep
3000
1000
2000 Timestep
3000
1.00
Theoretical Distrihution
Coverage
0.95
Density
20
0.90
10
EdgeFx CP
0.85
1000
2000
3000
0.80
0.85
0.95
1.00
Timestep
Coverage
Figure 3: [Upper left] Coverage over time under node exchangeability when predicting upon node arrival (diagonals of C). [Upper right] Coverage when we instead predict fixed time (columns of C). [Lower right] Same as upper right but under edge-cxchangeabiliyy [Lower left] The empirical distribution coverage when we predict at node-specific times (fixed entries of C), compared to the theoretical distribution. Sample size results in slight expected shift. The transparent lines show a particular sequence, and the thick solid lines shows the average over 10 (15) sequences.
Efficiency and singletons. In addition to coverage, which is the main goal of our work, also briefly study the efficiency (average set size) and the singleton hit fraction correct sets of size 1. As will in 6.2, NodeEx and EdgeEx CP improve these metrics byproduct. Some scoring functions such as RAPS (Angelopoulos et al., (021) and DAPS (Zargarbashi et al., (023) directly target these metrics and be used on top our approach. We explore DAPS D.3
6.2 EVALUATION EMPIRICAL COVERAGE, SET SIZE AND SINGLETON HIT
Table I shows the deviation from the coverage guarantee for different datasets when the label of each node is predicted upon ity arrival. As shown in the table, while naive CP shows significant shift from the a = 0.9 coverage, NodeEx CP maintains the empirical coverage close to the desired value. In Fig. (upper left) we show the temporal evolution of coverage. We show the coverage for all nodes that arrived until time and see that the guarantee is preserved for each timestep t. As mentioned before, the goal to achieve near standard CP might misleadingly appear as better result. Not only does over-coverage come at cost of less efficiency as shown Fig. 4 (see [$ D.2 for details), but the empirical coverage of non-guaranteed prediction sets is not predictable apriori.
empirical coverage, the over-coverage of
Fig. 3) lower left) shows the same experiment for edge-exchangeability While NodeEx CP guaran- tees coverage under node-exchangeability the weights specified in our EdgeEx CP are necessary for the guarantee to hold on an edge-exchangeable sequence. Standard CP fails again.
As explained in 4 any node can be evaluated at any timestep after its appearance. Fig. 3 (upper right) shows the result when predicting at a fixed time (instead of upon arrival). Additionally. Fig. (lower right) shows the empirical distribution of coverage for node-specific times (random subsets of nodes, each node predicted at a random time after appearance). For NodeEx CP, the empiri- cal distribution matches the theoretical one, while the coverage of naive CP substantially diverges.
8

---

Published as a conference paper at ICLR 2024
Node Exch. Sequence
Edge Exch. Sequence
Dataset
Acc
NodeEx CP
Naive CP
EdgeEx CP
NodeEx CP
Naive CP
Cora-ML
0.800
0.280
5.860
1.929
3.883
6.860
PubMed
0.777
1.254
4.649
1.241
3,405
5.315
CiteSeer
0.816
0.039
4.150
0.335
1.572
3,460
Coauth-CS
0.914
0.397
4.082
3.024
4.662
7.835
Coauth-Phy.
0.940
0.555
2.689
2.240
4.378
6.123
Amz-Comp. 0.788
0.263
6.373
2.687
5.727
7.036
Amz-Photo
0.868
0.127
3.483
2.546
4.130
6.613
Table 1: Average absolute deviation from guarantee (in %, for GCN model and train/val split).
Unsurprisingly, under node exchangeability. in Fig. 4 we that NodeEx CP improves both additional metrics - has smaller sets and larger singleton hit ratio. The same holds for other settings.
consider sparse (and thus realistic) calibration set size, e.g. for PubMed we sample 60 nodes for calibration, which is a significantly lower number compared to other tasks like image classification with 1000 datapoints for same purpose (Angelopoulos calibration size controls the concentration (variance) around a reflected by the transparent lines on Fig. Increasing the size reduces the variance but the mean is always
In all experiments,
al. 202T). The
Limitations. We identified three main limitations, First, the guarantee is marginal. Second, real- world graphs may not satisfy node- or edge-exchagability. This can partially mitigated by the beyond exchangeability framework. Finally, the guarantee does not hold for adversarially chosen evaluation sets Veval- other words, the choice of which nodes is evaluated at which timesteps must be prior to observing the prediction set. We provide longer discussion each of these limitations $ A Our main focus is on the validity. However, we also reported other metrics such as average set size, singleton hit ratio and other score functions in
CONCLUSION
We adapt conformal prediction to inductive node-classification for both node and edge exchangeable graph sequences. We show that although introducing nodes/cdges causes a distribution shift in the conformity scores, this shift is symmetric. By recomputing the scores conditional to the evaluation subgraph, recover the coverage guarantee. Under edge-exchangeability, we need to also account for the node degrees to maintain validity. Importantly, our approach affords flexibility the guarantee holds regardless of prediction time which can be chosen differently for each node.
4.5
NodeEx CP.
Singleton Hit Ratio
NodeEx CP.
Average Set Size
Naive CP.
Naive CP
0.2
3.0
2.5
0.1
2.0
1000
2000
3000
1000
2000
3000
Timestep
Timestep
Figure 4: [Left] Average set size (lower is better) and [Right] singleton hits ratio (higher is better) of naive CP vs. NodeEx CP for CiteSeer and GCN. Our approach improves both metrics.

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
All datasets of our experiments are publicly available and referenced in S 6.1 in addition to details on experimental setups. The pseudocode of our approach provided in $ A The hyperparameters of models are given in The code of experiments is also uploaded as supplementary material.
REFERENCES
David J Aldous. Representations for partially exchangeable arrays of random variables. Journal of Multivariate Analysis, 1981.
Anastasios Angelopoulos and Stephen Bates. A gentle introduction to conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.075// 2021a.
Anastasios Nikolas Angelopoulos and Stephen Bates. A gentle introduction conformal prediction and distribution-free uncertainty quantification. ArXiv, abs/2107.07511 2021b.
Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncertainty sets for image classifiers using conformal prediction. In International Conference on Learning Representations, 2021.
Anastasios Nikolas Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster. Con- formal risk control. In The Twelfth International Conference on Learning Representations, 2024.
Rina Foygel Barber. Is distribution-fre frre inference possible for binary regression? arXiv: Statistics Theory, 2020.
Rina Foygel Barber, Emmanuel Candès, Aaditya Ramdas, and Ryan J. Tibshirani. Predictive inference with the jackknife+. arXiv: Methodology, 2019a.
Rina Foygel Barber, Emmanuel Candès, Aaditya Ramdas, and Ryan J. Tibshirani. The limits of distribution-free conditional predictive inference. Information and Inference: A Journal of the IMA, 2019b.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. Conformal prediction beyond exchangeability. The Annals of Statistics, 51, 2023.
Diana Cai, Trevor Campbell, and Tamara Broderick. Edge-exchangeable graphs and sparsity. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Informa- tion Processing Systems. Curran Associates, Inc., 2016.
Jase Clarkson. Distribution free prediction sets for node classification. In Proceedings of the 40th International Conference Machine Learning, 2023.
Adam Fisch, Tal Schuster, T. Jaakkola, and Regina Barzilay. Conformal prediction sets with limited false positives. Proceedings of the 39th International Conference on Machine Learning, 2022.
Douglas N. Hoover.
Relations on probability spaces and arrays of random variables. Preprint, Institute for Advanced Study, Princeton, NJ, 1979.
Kexin Huang, Ying Jin, Emmanuel Candes, and Jure Leskovec. Uncertainty quantification over graph with conformalized graph neural networks. In Thirth-seventh Conference on Neural Infor- mation Processing Systems, 2023.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Johannes Klicpera, Aleksandar Bojehevski, and Stephan Günneeann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2019.
Jing Lei and Larry A. Wasserman. Distribution- free prediction bands for non non-noonnnnnnee parametric regression. Journal of the Royal Statistical Society: Series (Statistical Methodology). 76, 2014.
10

---

Published as a conference paper at ICLR 2024
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel. Image-based recom- mendations on styles and substitutes. Proceedings of the 38th International ACM SIGIR Confer- on Research and Development in Information Retrieval, 2015.
Andrew McCallum, Kamal Nigam, Jason D. M. Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 2004.
Galilco Namata, Ben London, Lise Getoor, Bert Huang, and U Edu. Query-driven active surveying for collective classification. In 10th international workshop mining and learning with graphs, 2012.
Peter Orbanz and Daniel M Roy. Bayesian models of graphs, arrays and other exchangeable random structures. IEEE transactions on pattern analysis and machine intelligence, 37, 2014.
Yaniv Romano, Matteo Sesia, and Emmanuel J. Candès. Classification with valid and adaptive coverage. In NeurlPS, 2020.
Mauricio Sadinle, Jing Lei, and Larry A. Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rat Collective classification in network data. Al Magazine, Sep. 2008. doi: 10. 1...6699ammm..2200 2157.
Glenn Shafer and Vladimir Vovk. A tutorial conformal prediction. Journal of Machine Learning Research, 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. ArXiv, abs/1811 0tts/8811.05555 1.05668. 2018.
Maximilian Stadler, Bertrand Charpentier, Simon Geisler, Daniel Zügner, and Stephan Günnemann. Graph posterior network: Bayesian predictive uncertainty for node classification. Advances in Neural Information Processing Systems, 2021.
David Stutz, Krishnamurthy Dj Dvijotham, Ali Taylan Cemgil, and Amaud Doucet. Learning opti- mal conformal classifiers. In International Conference on Learning Representations, 2022.
Ryan Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal pre- diction under covariate shift. Advances in neural information processing systems, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Vladimir Vovk. Conditional validity of inductive conformal predictors. In Steven C. H. Hoi and Wray Buntine (eds.), Proceedings of the Asian Conference on Machine Learning, volume 25 of Proceedings of Machine Learning Research, pp. 475 Singapore Management University, Singapore, 04-06 Nov 2012. PMLR
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world, volume 29. Springer, 2005.
Pivithuru Wijegunawardana, Ralucca Gera, and Sucheta Soundarajan. Node classification with bounded error rates. 2020.
Peter Young, Alice Lai, Micah Hodosh, and Julia Hockenmaier. From image descriptions to visual denotations: New similarity metrics for semantic inference over event descriptions. Transactions of the Association for Computational Linguistics, 2, 2014.
Soroush H. Zargarbashi, Simone Antonelli, and Aleksandar Bojchevski. Conformal prediction sets for graph neural networks. In Proceedings of the 40th International Conference Machine Learning, 2023.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. 2019.
Graphsaint: Graph sampling based inductive learning method. CoRR,
11

---

Published as a conference paper at ICLR 2024
A ALGORITHM FOR NODEEX CP AND WEIGHTED EDGEEX CP
At each timestep with node-exchangeable graph G., we first run the GNN model extract con- formity scores for all nodes in Vr. We compute the a-quantile of the conformity scores conditional to the current graph, and for each test node Vtest Veea we return any candidate label with score larger than the conditional threshold. For an edge-exchangeable graph, the algorithm still the same unless we compute the conditional weighted quantile with weights equal 1/d(u) for all calibration vertices u. Algorithm shshows the pseudocode for NodeEx CP. The code is accessible at github. com wttp:///woroosssaaarrrrrooooooot
Algorithm 1: NodeEx and EdgeEx CP for inductive node classification
Data: Graph G. at timestep
Calibration vertex set Veal.
Permutation equívariant score function (e.g. function of GNN).
Evaluation vertex set V(t))
eval Result: (²())) vy v((e)
1 St 4 s(G)):
// Get score functions for all vertices
if node-exchangeable sequence then
3 Set 72 - Quant (a; (Si v.l.e... :1:: else if edge-exchungeahhe
sequence then 5 Set Te 4 Quant (ar; { [Sr M,l. 1/deg(v; (.)):
Vey E vl9 evall set (v, = ty S.D. vl 73;
Naive CP. In naive CP we compute calibration scores before the arrival of any new node, the inductive subgraph over Vrr U Veat. Prior to the evaluation of any node, we compute the calibration quantile g from calibration scores. For any test node, the conformity score of all its classes is compared to Clarkson (2023) shows that this approach fails to provide valid prediction sets (the guarantee is broken due to the shift caused by the arrival of new nodes).
Computational complexity. Conformal prediction has two main computational routines in addition to model's inference: computing scores and quantiles. For the calibration set we only need the scores of the true class, but for test nodes, we should compute scores for all classes. Depending on the score function the complexity can be different. For standard CP we compute calibration scores once, but for NodeEx CP for each evaluation (timestep) we need to recompute the predictions and the conformity scores. Hence, Node(Edge)): CP has an overhead of O(n t, x t) for t timesteps, calibration nodes, and 4, the time for computing a conformity score for one class and one node. At each step we should also evaluate the model once the model's prediction changes across time. Computing the quantile threshold takes (nn) steps. For standard CP have to compute this value once, but in NodeEx CP this values is updated upon each evaluation. The total wall-clock overhead is less the second. Additionally all mentioned complexities are for serial computation and some of CP procedures can run significantly faster via parallel computation.
Limitations of NodeEx and EdgeEx CP. Our study mainly focuses approaches that can pro- vide valid CP for changing subgraphs under certain assumptions of node-or edge-exchangeabbiiiy, There are three main limitations for using NodeEx (or EdgeEx) CP (i) The guarantee provided by NodeEx (and EdgeEx) CP is marginal. However, it is shown that exact conditional coverage Prob ly C(z) x]] is not achievable. Still, there are methods that tend to get better approximations of conditional coverage. (ii) In real-life graph sequences, it is hard to determine whether the graph sequence is node- or edge-exchangeable or neither. Here follow-up works is to use the beyond ex- changeability approach (Barber et al. (023) to achieve valid coverage guarantees without the need for node- or dig-eexchangeabiliiy assumption. (iii) Our result maintains validity as long as the se- lection evaluation timestep for each node is done without any knowledge of the prediction set. An adversarial selection can cause a significant deviation from the guaranteed coverage. For instance, an adversary can observe prediction sets for particular node during various timesteps and pick the timestep of the smallest prediction set similar to the two false examples in S D.I This results can lead to significant miscoverage rate compared to the guarantee.
12

---

Published as a conference paper at ICLR 2024
B ADDITION TO THE THEORY
Matric C. For timestep t and index i, Cii, t] indicates that whether node if evaluated at timestep t is going be covered or not. Hence this value can be either 1, indicating CP covers node ey at timestep t, O showing that CP does not cover this node, N/A showing that this node has not appeared at this timestep. This matrix constructed using ground-truth labels and is shown only for the purpose of sanity check and evaluation. The matrix C' is a very dense matrix since 1 entities at each column should 1. That is why in Fig. 2 we showed - C where each column is expected to have a- pepreenttage of ones. A valid CP approach should result in similar percentage of ones in each column. For an invalid CP, if the trend is gradually moving toward over-coverage, the matrix 1 C' becomes more sparse in later columns.
Node- and edge- exchangeability. A sequence 2 = (zi,..., zn) is called exchangeable for any permutation 14, the joint probability of the permuted sequence remains the same, i... Prob [(2)...., ]n = Prob ((u(z))..... [=(z))] Before considering inductive graph sequences, first define node- and liganexcanng on a fixed given graph g.
Definition 1 (Node-exchangeabiiit). Let E(V,EXX, y) be graph where i-th row of X is the feature vector for node vi. and similarly, i-th element of y is the label of that node. Let μv : {1, (1....,n.) n. x {1, ......,n] with n. = [V] be a permutation. We define (g( be relabeling of vertices V with (v((E) = ((pv(ss) uy (u;)) VVo,, E (x),, uv [y)]i (i)] The permuted graph (vv uV (
(l)v(i),)) and called node exchangeable if Prob [G = = Prob [G = (9)), where G is sampled from a generative graph distribution.
Definition (Edgg-exchangeabiitty, Let G(V, x, E, Each edge ex is defined as a pair ek = ([vi, Li, Wi), (1j, Tz, Y;)). For each node U; E V let X be the feature matrix with rows T,, and y be the vector of labels with entries ye. Let μ [1....,m} mm] x {1..... m with m = [E] be a permutation. We define p(g to be relabeling of edges E with (E(E) ( (Eng(s) Ye, E E). The permuted graph HE (G) pr(E), X,y). y). G is called edge
where & fei,... em. is the set of edges.
exchangeable if Prob |G 9] = Prob [G = (E())), where G is sampled from a generative graph distribution.
By an inductive sequence, we refer to a progressive sequence of graphs meaning that for each timestep the graph G--1 is subgraph of G. Node- and edge-inductive sequences are defined as follows:
Definition (Node-inductive sequence). A node-inee inductive sequence Go. Gr.... is a sequence start- ing from empty graph Go = (Ø, 2). For each timestep t, the graph G. is defined by adding a vertex Vt with all its connections to the vertices in the previous timestep. The vertex set is then Vi V U {wr) and the edge set is the union of all previous edges E and any edge between vt E,, 24 E Vi-1)).
and Vi-1i & = E,-1 U (n (e = (Ve, vi)
Similarly an edge-inductivy sequence is defined as follows:
Definition 4 (Fdge-inductive sequence). An edge inductive sequence Go, 91,... starts from an empty graph Go = (Ø, 2). For each timestep t, the graph Gr is defined by adding an edge e,- (v,, U)) to the graph at the previous timestep. Hence & = E U [er). and V. = V U {Ur, Uz}.
A node-inductive sequence is called oode-exchangeable for all graphs Ge in the sequence, Ge is node-excee mode-exchangeablee Similarly, if all graphs in the sequence are eecheeechan,e the sequence is also edge-exchangeable.
Note, an inductive sequence could be equivalentity defined with respect to "final" graph G.. where n can be infinity, by starting from an empty graph and adding a random nodeledge at each timestep. If the final graph is node-xxchangeable any node-inductive subgraph of G' C Gr, G' is also node ex- changeable. A similar argument holds for edge-inductive subgraphs of a "final" edge-exchangeable graph.
Permutation invariance and equivariance. A permutation invariant function f returns the same output for any permutation applied on its inputs, f(21.... ,,,....,,,,).. 2xx f(z())).. (p(()) ) for any per- mutation μ. A function ff is ceemutation-equivrrine permutation the output, i.e. for any f(1,,... ((a)) (y1,-.., Vn) have I (zx(1):-- -.. Pp(n))
permuting the input results in the same
13

---

Published as a conference paper at ICLR 2024
(z)(1).... (y(())..-uu(())) for any μ.. A cormmuatiionequivariinn GNN assigns the same predictions (and thus the same scores) to each node even when nodes/edges are relabeled.
Proof for Proposition 1 First assumee ((() V meaning that any node appeared at timestep t either in the calibration or the evaluation set. Due to nodt-exchangeabiiity Vi and Veat are exchangeable. Hence, we adapt the proof of [Theorem 2 Now consider the general V" : V Veal & 0. Any subset AA' of an exchangeable set A is still exchangeable. For any permu- tation of A' there are permutations in A all having the same ordering over elements of A', Since k is constant for all permutations and function of |A| and |AA,, any permutation in A'' has the same probability. Which implies the exchangeability of its elements. This implies that with non-empty set V. Veal and V. V" are still exchangeable. As a result, again we adapt Theorem 2 with the effect of V being symmetric the calibration and evaluation sets.
where
Proof for Theorem 3) We break the proof to two parts.
Part 1. For fixed node 2 timestep let aq E[q,,. For any timestep to with which by is existing in, we have [E(c,,2) = Oz--
Note that since v; is fixed its expected coverage probability is not exactly 1 - As in definition,
0g Prob [Quant (a: {s(e), (.))),, 11) S s(U), ys (c.)
Let y V4 \ (Van U {v:]). Node-exchangeability implies that V and V/2 have same and also symmetric effect all scores. Hence, with either of sets as context, the expected order of elements remains similar and B[cr,ra] = a, Moreover, for each node e and all f, Ci, ~ Bernoulli(a)).
Part The coverage of any sub-partitioning Ir can be written as an average over set of elements in Cr. other words define ((v,)= = + (v,
V Vevai) we have
Lrl
Hrl
Cov(Ir) =
C(i,((e)]
Part
cl.
Mr
2m
Following Proposition
we have
[r Cli, (vx))====
Prob (Cov(TTT) S
H (fai [Trl + n, n, ia + -[Tr] (3))
Proof for Theorem 4 We divide the proof into two cases:
Graph where all nodes have degree In this case Gr is a union of disjoint edges (eI,.. Cy We divide V. V1 U V/ including one and only one endpoint of each edge decided at random. The vertex set in this case has the same size as the edge set, and there a one-to-one mapping between any permutation μ over the edge set to vertices in Vi or V> since only one endpoint is present in each set. Hence Prob [E] = Prob [Eμu] implics Prob [V.] = Prob [Vi, (1,2)- Similarly,
selection Veal decomposes to Veat,1 U Veal.2 and again Veal. and Vi \ Veal, are exchangeable due to node-exchangeability V,, Any test node belongs to either of the subsequences which means is guaranteed via the CP applied to that subset.
The vertex set is divided into two subsets, and the intersection of the calibration set to each subset exchangeable. Hence calibrating on each subset result in 1 coverage for all the nodes in the subset. Both calibrations have the same expected quantile threshold q. This is because each calibration node has 1/2 probability of being included in each of the sets.
General graphs. We follow the same approach. We divide the endpoints of edges into two multi- sets. For each edge In each partition, each node v; has the expected frequency deg(v;)/2. Via Lemma we show that weighted CP is valid for each subsequence V; and hence for V,.
this division and this decision is made for each vertex deg(t) times.
14

---

Published as a conference paper at ICLR 2024
1-hop NAPS
10a
Applicable Nodes
2000
2-hop NAPS
Cal. Set Size
Arrived Nodes
No. Cal. Nodes
1000
10a
1000
2000
1000
2000
Timestep
Timestep
Figure 5: [Left] The proportion of nodes without prediction set due to empty calibration CoraML dataset. The plot shows the inapplicability k-hop NAPS with & E (1, [Right] The average size of each node's filtered calibration set. Note that this plot excludes non-applicable nodes.
1.0
Inapplicable Nodes
NAPS
Emp. Coverage
0.9
2000
NodeEx CP
1000
0.7
Guarantec
0.6
1000
2000
1000
2000
Timestep
Timestep
Figure 6: [Left] Comparison of NAPS and NodeEx CP empirical coverage for CoraML dataset and GCN model across different permutations of nodes. [Right] The number of nodes without pre- diction set for different permutations on the same dataset/model.
C LIMITATIONS OF NAPS
For the inductive scenario, NAPS Clarkson 2023) adapts the beyond exchangeability approach (Barber al. 2023) without any computed bounds the coverage gap (the distance between the coverage of the given non-exchangeable sequence and - -o). For each test node, calibration weights are assigned equal to 1 in case they are in the immediate neighborhood of the test node and 0 other- wise. In other words, this approach filters out the non-neighbor calibration nodes for each test node. This weight assignment is generalized to any k-hop neighbor while it is originally suggested to k = 1 or 2. In a sparse graph, or with a limited calibration set, the probability of having calibra- tion points in the immediate neighborhood significantly low which leaves many of the test nodes with empty calibration sets. FFg.. 5 shows that for our experimental setup, until the end of the graph sequence, notable proportion of the nodes are left without a prediction set. For the same reason, for nodes in the neighborhood of the calibration this inapplicability is reported on node-exchangeable sequence, it is independent the prediction timestep- node disconnected from the calibration set will remain disconnected as the graph grows.
the statistical efficiency is very low. Since
Setting aside non-applicable nodes we compared NAPS with NodeEx CP in empirical coverage. Fig. shows that NAPS is significantly far from the coverage guarantee compared to NodeEx CP. Note that this experiment is very biased in favor of NAPS as it excludes nodes without a prediction set while evaluating the same nodes for NodeEx CP.
15

---

Published as a conference paper at ICLR 2024
D ADDITIONAL EXPERIMENTS
D.1 CP WITH SUBGRAPH SAMPLING
Although the theory in concerns induc- leverage its via subgraph sampling. For each node Utest, we sample K inductive subgraphs all including { [teett } U Veat- Considering Theorem 3 in each subgraph, calibration scores and test scores are exchangeable. This leaves K prediction sets all with coverage guarantce
tive graph sequences, results to transductive node-classificttion
0.9
Coverage
0.8
0.7
- a. We consider each prediction set vote for all its ele- ments. Each label y' will be selected in the final prediction set with Bernoulli exper- iment with parameter p Σ 1 Cr(Veest)// K. Again the resulting predic- tion set contains the true label with a probability. It is important to note that Theorem doess not imply any result about the probability of node being covered in all of K prediction sets. Specifically, the probability of a node being covered in all prediction sets simultaneously less than (or equal to) the probability of the same event in each single CP. As shown in Fig. the sub- graph Bernoulli prediction sets result in the same coverage as standard CP for transductive node- classification. Additionally, the union and intersection of CPs respectively result in over-coverage and under-coverage.
Guarantee
Standard CP
Sub CP (Bem)
Sub CP (Max)
Sub CP (Mm)
Figure Comparison between standard CP, Bernoulli prediction sets from NodeEx CP on random subgraphs, the union, and intersection of CPs.
D.2 SET SIZE AND SINGLETON HIT RATIO
In we focused on empirical coverage as the main evaluation criteria since our goal to recover the conformal guarantee. When the guarantee holds, this metric is often reported as sanity check. In that case, the average prediction set size (efficiency) is considered as direct indicator how efficient (and therefore useful) prediction sets are. Another important metric called singleton hit ratio is the frequency of singleton sets covering the true label. In Fig. 8 we show the coverage matrix alongside the prediction size and singleton hits indicator for each node at each timestep. As shown in the figure, since the standard CP breaks the guarantee toward over-coverage, it results average and hence, lower number of singleton hits. The same result is also shown in Fig. 4 Jover different timesteps.
in larger prediction
D.3 DIFFERENT SCORE FUNCTIONS
The threshold prediction sets (TPS) approach (Sadinle et al. 2018) directly takes the softmax output as a conformity score sæx y) л (a:) y- where л ( is the predicted probability for class y. Al- though TPS produces small prediction sets, its coverage is biased toward easier examples leaving the hard examples under-covered (Angelopoulos & Bates 202 Romano et al. (2020) define adap- tive prediction sets (APS) with a score function defined as s(x, y) := (p(æ y) + u т (x)y). Here (z))g] is the sum of all classes predicted as more likely than y, and u E [o, 1] is uniform random value that breaks the ties between different scores to allow exact 1 coverage (Stutz et al. 2022). APS returns the smallest prediction sets satisfying conditional coverage if the model returns the ground truth conditional probability p(y æ). otherwise Barber et al. (2019b) show that achieving conditional coverage is impossible without strong unrealistic sumptions. Here we use APS as baseline scoring function, but our method is orthogonal to this
p(æ, v) := Σ c- (x))1 1 (x:
choice and works with any score.
16

---

Published as a conference paper at ICLR 2024
1000
1000
1000
Nodes
2000
2000
2000
2
3000
3000
3000
1000
2000
3000
0
1000
2000
3000
1000
2000
3000
1000
1000
1000
Nodes
2000
2000
2000
2
3000
3000
3000
0
1000
2000
3000
0
1000
2000
3000
0
1000
2000
3000
Timestep
Timestep
Timestep
Figure 8: [Left column] The coverage matrix C (colored points show miscoverage). [Middle column] The prediction set size for each point each timestep. [Right column The matrix of singleton hits. A cell is colored if the node the timestep is predicted with singleton set covering the true label. [Upper row] The NodeEx CP approach. [Lower row] The standard CP. The result is shown for CiteSeer dataset and GCN model.
Although used APS the base score function for evaluation, results general to any other scoring function. Here we evaluate our approach with two other score functions called threshold prediction sets (TPS) (Sadinle et al. 2018), and diffused adaptive prediction sets DAPS! Zargarbashi et al. 22023) TPS (Fig. 9 left) simply applies the softmax function on model's results (logits) and uses it the conformity score. Although produces small prediction
its coverage is
biased toward easier examples (Angelopoulos & Bates 20216). DAPS ( 9 right) works as structure-awand extension scoring over APS. It diffuses conformity scores over the network structure
1.00
1.00
Guarantee
0.95
0.95
NodeEx CP (DAPS)
Naive CP (DAPS)
0.90
0.90
Coverage
Coverage
0.85
Guarantee
0.75
NodeFx CP (TPS)
0.75
Naive CP (TPS)
0.70
0.70
0
1000
2000
3000
1000
2000
3000
Timestep
Timestep
Figure 9: [Left] Comparison of naive CP and NodeEx CP with TPS score function and [Right] DAPS score function. Results are for CiteSeer dataset and GCN model.
17

---

Published as a conference paper at ICLR 2024
to leverage the uncertainty information in the neighborhood and produce more efficient prediction set. Since DAPS also incorporates the structure in the scores' space (in addition to the implicit effect via message passing) it is even more influenced by the changes in the graph structure while using standard CP. However, as shown in the Fig. 9 we can recover the coverage guarantee via NodeEx CP regardless of the utilized score function.
D.4 DIFFERENT MODELS AND INITIAL SPL.TS
The coverage guarantee in CP holds regardless of the model structure. CP uses the model black-box box and just performs the quantile calibration over the output the model which is the input conformity score function. However, better model structure, training procedure, other metrics like set size and singleton hits. As shown in Fig. 10 NodeEx CP results in similar coverage values for all the models while standard CP results in different coverage for each model (note the significant distance between structure-aware models and MLP). As MLP does not take the adjacency structure into account, its empirical coverage still guaranteed even with the standard CP. Note that different models result in different efficiencies in the prediction sets, Fig. I1 shows the same experiment conducted on exchaneacee sampling. Again similar results are observed for edge-exchangeable sequences.
reflected in
As pointed out in (Shchur et al. 2018), GNNs are sensitive to the initial train/validation sampling. This however does not impact the coverage of NodeEx (and EdgeEx) CP as it is guaranteed agnostic to the model and the initial split. However similar to different model architectures, different initial splits also affect the model's accuracy which is reflected in the efficiency of the prediction set.
Ave. Set. Size
Coverage
APPNPNet
0.9
0.8
1000
2000
1000
2000
Ave. Set Size
Coverage
GAT
0.9
0.8
1000
2000
1000
2000
1.0
Ave. Set Size
Coverage
GCN
0.9
0.8
1000
2000
1000
2000
1.0
Ave. Set Size
Coverage
MLP
0.9
3.5
NodeEx
Naive
3.0
0.8
1000
2000
1000
2000
No. Nodes
No. Nodes
Figure 10: [Left] The empirical coverage for different models. [Right] The average set size. The results shown for the CoraML dataset with node-exchangeable sampling.
18

---

Published as a conference paper at ICLR 2024
1.0
Ave. Set Size
Coverage
APPNPNet
0.8
500
1000
1500
2000
2000
4000
1.0
Ave. Set Size
Coverage
GAT
0.8
500
1000
1500
2000
2000
4000
6000
1.0
Ave. Set Size
Coverage
GCN
0.8
500
1000
1500
2000
2000
4000
6000
1.0
Ave. Set Size
3.5
Coverage
NodeEx
MLP
0.9
Naive
3.0
EdgeFx
2.5
0.8
500
1000
1500
2000
2000
4000
6000
No. Nodes
No. Nodes
Figure 11: [Left) The empirical coverage for different models. [Right] the average set size. The results are shown for the CoraMI, dataset with edge-exchangeable sampling.
Fig. 12 verifies this fir the node-exchangee bode-exchangeable sampling. We also evaluated our method compared to standard CP for edge-exchangeable sequences over different initial sampling. The result is in Fig. 13
D.5 OTHER EXPERIMENTS
Experiment corresponding to Fig. 1 We performed a node-exchangeable sampling on CiteSeer dataset. At each timestep, ran the model (GCN trained the train/val nodes) the existing subgraph extracting conformal scores for all existing test nodes. The heatmap in Fig. T (left) shows the distribution of scores (sorted) each timestep. An oracle CP (with access to nodes and their label) will choose the line labeled as "ground truth" as the conformal threshold since it is the exact quantile of existing test scores. This is shown the ideal reference evaluate each CP approach with respect to it. We draw the threshold computed by standard CP and NodeEx CP. It is shown that the NodeEx CP picks thresholds close the ideal line while the naive CP shifts from due to the message passing with the new nodes.
We drew the distribution of conformity score for calibration nodes at some selected times (sampled with equal distance across from all timesteps) and compared it with calibration scores used by stan- dard CP in Fig. [upper right). distribution shift is clearly observable. We showed this shift in Fig. Tupper right) by plotting the distibutions across various timesteps. The corresponding timestep for each distribution is marked in the left subplot with the same color. Here we computed the EMD (earth mover distance) between the scores of standard CP and conformity scores (of true labels) for calibration and test points. is shown that the distribution shift is increasing by the number of new nodes introduced to the graph. This shift is almost similar in calibration and test. One source of
19

---

Published as a conference paper at ICLR 2024
1.00
5
0.95
Average Set Size
Coverage
0.90
3
NodeEx
0.85
Naive CP
Guarantee
0.80
1000
2000
792
1188
1584
1980
No. Nodes
No. Nodes
Figure 12: [Left]] The empirical coverage of standard CP and NodeEx CP with different initial train/val splits. [Right] The average size. The result shown for CoraMI, dataset and GCN model for node-exchangeable samplings.
1.00
3.5
0.95
Average Set Size
3.0
Coverage
0.90
2.5
NodeEx CP
0.85
Naive
2.0
Edgelix CP
Guarantee
0.80
1.5
500
1000
1500
2000
1188
2376
3564
4752
No. Nodes
No. Nodes
Figure 13: [Left] The empirical coverage of standard CP and EdgeEx CP with different initial train/val splits. [Right] The average set size. The result is shown for CoraML dataset and GCN model for edge-exchangeable samplings.
the noise thresholds and EMD is the uniform random value in APS scoring function. EMD is smoothed over 10 steps.
Large Datasets. We ran NodeEx CP and compared it with the baseline for two large datasets: Flickr Young et al. (2014), Reddit2 (Zeng et al.) (019). Our results for Flicker and Reddit2 datasets under node exchangeable sampling are shown in Fig. 14 Both NodeEx CP and naive CP show similar results. In the edge-exchangeable sampling Fig. shows a significant deviation from the guarantee for NodeEx CP and naive CP, while EdgeEx CP maintains a valid coverage.
Class-come consicondiiional coverage. Conformal prediction comes with marginal guarantee which means that it does not guarantee conditional to group or class. In Fig. 16 we compare this metric. In most of the classes, observe the standard CP to be closer the guaranteed line.
Effect of calibration set size. non-graph data as mentioned in the coverage probability follows Beta distribution. In graph data with fixed number of test nodes (see Theorem 2} the distribution of coverage over test nodes follows a collection of syper-geomene distributions. In both scenarios, there is possible variance around predefined 1 a probability which is function
20

---

Published as a conference paper at ICLR 2024
Naive
0.94
Naive CP
NodeEx CP
NodeEx
0.92
0.92
Coverage
Coverage
0.90
0.90
0.88
0.88
0.86
0.86
5000
10000
15000
20000
5000
10000
15000
20000
Timestep
Timestep
Figure 14: Coverage Results for [Left] Fl Plickr, and [Right] Reddit2 dataset under node- exchangeable sampling. The results shown for GCN model.
1.00
1.00
0.95
0.95
Coverage
Coverage
0.90
0.90
Naive CP
Naive CP
0.85
0.85
NodeEx CP
NodeEx CP
FdgeFxx CP
EdgeFx CP
0.80
0.80
5000
10000
15000
20000
0
5000
10000
15000
20000
Timestep
Timestep
Figure 15: Coverage Results for [Left] Flicks and [Right] Reddit2 dataset under edge- exchangeable sampling. The results are shown for GCN model.
of calibration set size. As the number of calibration nodes increases, the distribution coverage followed a realistic setup
probability concentrates around a. Since our experiments (not allowing calibration set to be larger than training set) there is variance observed around the guarantee line each line converges value close to but not exactly equal a. Fig. 17 shows that as we increase the calibration set size the result concentrates around the guarantee.
E SUPPLEMENTARY DETAILS OF EXPERIMENTS
Datasets. Table 2 provides specifications of datasets used in our experimental evaluations, including the number of nodes, edges, and homophily. The details label sampling are provided in 6 For each experiment,
each CP approach 10 different sequences in node-exchangeable and 15 different sequences on edge- adge-exchangeable setup. All transparent lines in plots show the result for sequence. In those experiments, the solid line shows the average of sequences at each timestep.
Models. For all architectures, we built one hidden layer 64 units and one output layer. We applied dropout the hidden layer with probability 0.6 for GCN, and GAT, 0.5 for APPNP Net, and 0.8 for
21

---

Published as a conference paper at ICLR 2024
1.00
1.00
0.95
0.95
Coverage
0.90
0.90
Naive. CP
0.85
NodeEx. CP
0.85
Guarantee
0.80
1000
2000
2000
1.00
1.00
0.95
0.95
Coverage
0.90
0.90
0.85
0.85
0.80
1000
2000
2000
3000
Timestep
Timestep
Figure 16: NodeEx CP and standard CP in class-conditional coverage. The result is for CiteSeer dataset and GCN model. Plots show classes and [Upper row left to right), and [Lower row).
1.00
1.00
0.95
0.95
Coverage
Coverage
0.90
0.90
0.85
NodeEx CP
Guarantee
Naive CP.
0.80
0.80
0
1000
2000
500
1000
1,00
Timestep
Timestep
Figure 17: Effect of different calibration set sizes on the concentration of coverage probability. The results are on Cora-ML dataset and for 200 [Left] and 1000 [Right] calibration nodes.
MLP. For GAT we used heads. We trained all models with categorical cross-entropy loss, and Adam optimizer with T.2 regularization.
Adaptive and constant coverage. Despite many studies on CP, Zargarbashi al. (023) chooses an adaptive value for 1 - a which is conditional to the model accuracy. This is suitable choice when the main comparison based on set size and other efficiency-related metrics. The main supporting idea is that efficiency should be compared with guarantee that is not trivially achievable by the normal model prediction. However, our main concern to recover the guarantee meaning that the empirical coverage is the main comparison criteria. Hence choose 0.9 the required coverage for all datasets and models regardless of the accuracy. Furthermore, NodeEx CP works for any user-specified coverage guarantee including model-conditional values.
22

---

Published as a conference paper at ICLR 2024
Table 2: Statistics of the datasets.
Dataset Name
Vertices
Attributes
Edges
Classes
Homophily
CoraML
2995
2879
16316
7
78.85%
PubMed
19717
500
88648
3
80.23%
CiteSeer
4230
602
10674
94.94% 6
Coaut. CS
18333
6805
163788
80.80% 15
Coauth. Physics
34493
8415
495924
93.14% 5
Amz. Comp.
13752
767
491722
10
77.72%
Amz. Photo
7650
745
238162
8
82.72%
F RELATED WORKS
Standard conformal prediction. CP is introduced by Vovk et al. (2005) and further developed in Lei & Wasserman (2014); |Shafer & Vovk (2008); : |arbeer (2020). Different variants of CP are yet defined ranging in the trade-off between statistical and computational efficiency. While full conformal prediction requires multiple training rounds for each single test point, Jackknife+ (Brberr jet al. (2019a). and split conformal prediction sacrifice statistical efficiency, defining faster and hence more scalable CP algorithms. A comprehensive survey of CP can be found in Angelopoulos & Bates 2021a). In this study, we focus on split conformal prediction.
Further contributions in this area include generalization of the guarantee from including the true label to any risk function Angelopoulos et (2024), improving the efficiency (reducing the average set size) by simulating calibration during training Stutz al. (2022). limiting the false positive rate Fisch et al. (2022), etc.
CP without exchangeability. Standard CP requires exchangeability for datapoints and assumes the model to treat datapoints symmetrically. The latter assumption ensures the exchangeability of datapoints even after observing the fitted model. Tibshirani al. (2019) extend CP cases where exchangeability breaks via different p(X) for calibration set and the test data, given p(Y X) is still the same. In this case, CP is adapted via reweighing the calibration set using the likelihood ratio to compare the training and test covariate distributions. This requires the high-dimensional likelihood to be known or well-approximated. [Barber et al.] (2023) does neither rely on known likelihood between the original and shifted distribution nor the symmetry in the learning algorithm and proposes a coverage gap based on the total variation distance between calibration points and the test point. The main upperbound the coverage requires predefined fixed weight function. To adapt this bound to data-dependent weights, the div--iitance must be computed conditional to the assigned weights.
CP for graphs. Recently adapting CP to graphs got increasing attention. Wijegunawardana et al. 2020 adapted conformal prediction for node classification to achieve bounded error. Clarkson 2023 assumed exchangeability violated for node classification hence adapting weighted exchange-
ability without any lowerbound on the coverage, however, Zargarbashi al. (2023) and HHang et al. (2023) proved the applicability of standard CP for transductive setting in GNNs. Moreover, Huang et (2023) proposed secondary GNN trained to increase the efficiency of prediction sets, and Zargarbashi et al. (2023) stated that in homophily networks, diffusion of conformal score can increase the efficiency significantly.
For the inductive GNNs, the only work we are aware of is the neighborhood APS (NAPS) approach which an adaptation weighted CP Clarkson (202)). however, shown that NAPS can not be applied significant fraction of nodes if the network is sparse or the quantity of calibration nodes are limited Zargarbashi et al. (2023) (this number increases to over 70% in some benchmark datasets). As our approach is adaptable sparse networks and works for any calibration set size, we do not compare our approach with NAPS.
23


Reviews:
[{"review_id": "PMrv2lgXmw", "reviewer": "Reviewer_2Ri3", "summary": "This paper explores the application of conformal prediction to graph neural networks, particularly addressing the challenge of inductive settings where the entire graph is not visible. In such scenarios, classic conformal prediction cannot be directly applied due to the loss of exchangeability when new nodes are introduced, which shifts the distribution of calibration scores.", "questions": "What is the motivation behind presenting Figure 2? Please consider adding an introductory explanation for this visualization figure.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The key insight of this paper is to demonstrate that the impact of new data points on the calibration and evaluation sets is symmetric, ensuring that the shift embedding still maintains its guarantee, conditional to the graph at a specific time step.", "weaknesses": "(1) Notations:\nThe presentation of this paper leaves room for improvement, as some notations are either omitted or unclear, making it misleading for readers. For instance, in Equation (3), the graph is not explicitly noted, and on page 5, in the linear message passing example, the meanings of A, X, and W are not immediately clear. Although these aspects become clearer upon reading the entire paper, the initial lack of clarity can impede readers from following the logic in their first encounter.\n\n(2) Baselines:\nIn the experimental section, the paper exclusively utilizes standard CP as the baseline. While the authors explain the rationale for not including NAPS as a baseline, it would be beneficial to at least include NAPS results or another inductive-case baseline in the experimental evaluation for a more comprehensive assessment.\n\n(3) Efficiency:\nFor CP methods, it's essential to consider both validity and efficiency. While the experimental results focus on \"coverage,\" which assesses validity, it's equally crucial to assess efficiency. A predictive set that is overly large may not be practically useful. Therefore, it is recommended to include at least one experiment that demonstrates the efficiency of the subgraph CP method.\n\n Taking into account the feedback from other reviewers and the author's response, I have decided to raise my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mFemwj8F69", "reviewer": "Reviewer_daSk", "summary": "While for transductive node-classification, we are given a fixed graph, in the inductive scenario the graph is changing. This leads to a shift in the scores and the standard conformal prediction methods do no longer apply.  This paper therefore proposes a method for calculating conformal prediction sets within the framework of inductive graph classification. The authors demonstrate coverage guarantees and provide extensive empirical experiments to show that their method is effective.", "questions": "Is it possible to \"boost\" any given non-conformity score with graphical information as in \"Uncertainty Quantification over Graph with Conformalized Graph Neural Networks\"?\n\nCan you give the mathematical definition of \"node-exchangeability\" and \"edge-exchangeability\"?\n\nWhat are the main limitations of the method?\n\nCan you explain Fig1 and Fig9 in more detail?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This is an interesting conformal prediction problem.\n\nThe paper seems solid with a large amount of experiments.\n\nThe code of experiments is available in the supplementary material.", "weaknesses": "1\\ I found the paper difficult to follow. For instance, the setting of transductive node-classification of Section 2.1 or the inductive one of Section 3 are not properly defined. Another example is Fig.1 which is, in my opinion, not very clear and not explained properly. The definition of a graph is never given etc. Globally, the paper lacks explanation.\n\n2\\ There is a misuse of several words/expressions to discuss known concepts, which ultimately confuses the paper. What is the added value of a phrase such as \"calibration budget\" to mean that we only use the first N nodes or \"no longer congruent with test scores\" to mean that it is no longer exchangeable?\n\n3\\ The paper never indicates when scores should be assumed to be continuous in theoretical results. For instance, in all the remarks below Theorem 1, we need this assumption.\n\n4\\ There is no \"limitation\" in the conclusion.\n\nMinor:\n\ntypos \"callibration\", \"hyper-geomteric\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sJQ5DfXvJ8", "reviewer": "Reviewer_w8hy", "summary": "This paper studies conformal prediction (CP) on graph data with graph neural networks in node-exchangeable and edge-exchangeable settings. The author(s) describe how certain exchangeability structure for nodes still persist in these settings, and how conformal prediction techniques can be adapted based on these observations. In particular, the proposed CP methods are valid conditional on subgraphs and when stopping at non-adversarial times, especially in cases when standard CP fails to provide the desired coverage. The methods and theory are clearly supported by empirical experiments. \n\nOverall, I think this paper provides interesting discussion, which both extends the current understanding of CP on graph-structure data and forms a solid foundation for future efforts in this direction. Though the methods only adapt existing ones, the discussion on exchangeability structure is important. The presentation is overall clear, but potential improvements in mathematical rigor and presentation clarity would further strengthen this paper.", "questions": "1. Mathematical definition of node exchangeability and edge exchangeability.\n\nI suggest adding a formal definition for node and edge exchangeability, just to avoid any confusion. It will also be beneficial to mention some important implications of such exchangeability, e.g., at each time $t$, the existing nodes are exchangeable, so on and so forth. \n\n2. Rigorous terminology in explaining Proposition 1.\n\nCurrently the explanation via $Z=AXW$ after Proposition 1 can be improved by using rigorous terminologies. For instance, in \"For the guarantee to be valid the first two blocks of the result must be row-exchangeable.\", it is unclear what \"the first two blocks of the result\" is, which is harmful for understanding. Also, related to question 1, \"For Mat(1) row-exchangeability already holds from Theorem 2\" can be further clarified by pointing out that nodes in cal and eval are exchangeable due to node exchangeability. I suggest the authors revise this part to improve clarity. \n\n3. How is the evaluation set $\\mathcal{V}_{eval}^{(t)}$ decided? \n\nI am a bit confused how one decides the evaluation set at each time. Is there a pre-defined rule, for instance, do we evaluate all newly arrived nodes immediately at each time $t$, or do we pre-fix the set of indices that will be evaluated at each time $t$? I was asking because if $\\mathcal{V}_{eval}^{(t)}$ is data-dependent, it may need more efforts in justifying the approach/theory. \n\n4. Definition of $Cov(\\mathbb{I}_T)$.\n\nThis is an important quantity in the theorem, and it shall be formally defined. \n\n5. Requirement on score function in Prop 1 and Theorem 3. \n\nIt seems to me that under node exchangeability, one still has exchangeability between calibration and evaluation nodes. However, it is now crucial how the score function $s$ is trained. At least it should be permutation invariant to these nodes? But nothing is mentioned there. I suggest revising this proposition (and its proof, which is a bit handwavy). Similarly for Theorem 3. \n\n6. Is there a technical result for the validity of weighted CP in edge-exchangeable setting? \n\nThe discussion for edge exchangeability (the end of Section 4) is interesting, but incomplete as there is no formal theorem on the validity of weighted CP. I would suggest adding a formal theorem, with clear description on how the edge appears (e.g., it is more clear to state that edges are uniformly sampled from a candidate edge set). \n\n\n-------\nsmall typos & wording questions:\n1. Section 4, line 3: \"callibration node\" should be \"calibration node\"\n\n2. Lemma 1, \"defined on a subsets of $\\mathcal{X}$\"\n\n3. I don't really understand the sentence \"Specifically we can not use the prediction sets of a particular node multiple times to compare and pick a specific one (see § D.4 for a discussion).\" in the second paragraph of Section 5.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Significance of contribution.\n\nConformal prediction on graph data has just recently become a popular topic. This topic is important for deploying GNNs in critical domains. While existing discussion mainly focuses on transductive setting, or only provides approximate and not-actionable guarantees for other settings, this paper stands out by providing solid theory, method, and experiments on node-exchangeable and edge-exchangeable settings. By thoroughly exploring the exchangeability structure in these settings, existing CP methods can be applied to solve seemingly challenging problems in this field. Thus, I think this paper makes a significant contribution to this topic, and will inspire future research efforts of the community.\n\n2. Originality. \n\nThe idea of this paper is original and provides novel insights. \n\n3. Quality. \n\nThis is a thorough paper with solid theory, fruitful discussion, and concrete experiments. \n\n4. Clarity. \n\nThe presentation is moderately clear. The positive points include (1) informative comparison to the literature, (2) useful remarks from place to place, and (3) succinct and clear statements of problem settings. I will mention points for improvement in the weakness part.", "weaknesses": "My complaints are not detrimental to this paper. I'm happy with the main ideas of this paper, so they are just comments that should be addressed to make the paper stronger. \n\nConformal prediction relies crucially rigorous mathematical statements about how data is generated / how test data appears in the set, how score functions are defined, how the score is trained and applied. These are all important factors for the validity of CP. While I believe the technical discussion in this paper is correct, sometimes I have to further check the statements in my own mind as some crucial mathematical terminologies are missing. A few possible points that deserve clarification include (1) formal definition of node and edge exchangeability, (2) clearly state the conditions on the score function and how the model is trained, (3) formal definition and examples of the \"evaluation mask\", etc. Please see my questions part. I'd be happy to increase my score if these points can be addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rvQM7hQNEa", "reviewer": "Reviewer_aMS7", "summary": "The work develops conformal prediction for graph neural networks in the inductive setting (i.e., new nodes and edges are added in test time). Specifically, the authors address the implicit shift in calibration scores by recompute the calibration scores with respect to the new graph to restore coverage guarantees. Empirical comparisons against the standard CP (std. CP) on different GNNs and graph datasets are considered.", "questions": "* Method: \n   * What is the complexity of the method with respect to graph size, number of samples, number of classes, etc. Specifically, if the graph $\\mathcal{G}_t$ is large with complicated definition of score $s$, I expect line 5 of Algorithm 1 to create some computational burden in real-time use.\n   * How does the method work if two or more nodes/edges are added at each time step?\n* Experiments:\n   * What exactly is the \"standard CP\" in the inductive context and how is it actually implemented? The idea of standard CP is mentioned in section 2, but that section is for general CP and transductive GNNs. I think the details should be discussed in the appendix with a reference in the main text, unless the baseline is taken directly from existing methods. Also, I think the abbreviation \"std. CP\" reads too much like standard deviation of CP, so I suggest changing the name.\n   * Does the method always work well on any GNN models being considered? It is helpful and important to discuss the generality and/or limitation of the method for different GNN baselines\n   * From looking at Figure 3 and 4, it seems standard CP coverages gradually increases as timestep increases. This leads to larger set sizes (as expected). Why is this the case? I think for a meaningful comparison, the empirical coverage should be set the same and then we can compare average set size.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "* Address the limitations of existing methods for inductive node-classification by recognizing that calibration and evaluation scores computed conditional to a specific subgraph are still exchangeable.\n* Adapt the non-exchangeable CP method in the edge-exchangeable case, with weights inverse proportional to nodal degrees.\n* Show promising results on different datasets and GNN models.", "weaknesses": "* Missing literature review: The work does not have a standalone literature review section. \n\n* Writing: \n   * Organization: the lengths between sections 4 and 5 are imbalanced. Specifically, section 4 contains the \"method\", theoretical analyses, and examples, where section 5 made reference to section 4 but the algorithm is delayed until the appendix. I think it makes more sense to first introduce the method, provide intuitions of why it works, and then give the theoretical analyses with additional remarks.\n   * The Algorithm in Appendix A is not well-written. For example, it is unclear how $\\boldsymbol{S}_t$ in line 5 is used later. The $\\tau^t$ in line 11 is also different from that in lines 7 and 9. Furthermore, it is unclear where the algorithm starts because the line numbers for inputs are intertwined with those for algorithmic steps.\n\n* Experiments:\n    * As explained in the paper, it is expected that standard CP does not work (e.g., in terms of reaching the coverage guarantees). I expect to see additional baselines for this setting that can be compared.\n    * Missing examples on larger graphs. For example, the Flickr and Reddit2 datasets in https://arxiv.org/pdf/2211.14555.pdf. These examples have considerably more nodes than the current settings.\n    * Missing standard deviation of results. From Figure 3 and 4, it seems the standard deviations can be high (I assume each line with light color indicates results from a specific run).\n    * Presentation needs to be improved. For example, the left column of Figure 3 and the Figure 4 have too many lines that affects readability. It is best to just show the average values with error bars. In addition, the authors considered 4 GNN models, but results for some more recent ones are only in the appendix. \n    * Misleading Table 1: it says \"average deviation from guarantee\", but it does not mean a higher deviation necessarily means worse performance. This is because if deviation is positive, this indicates over-coverage, which is still acceptable (one just needs to lower the significance level). In fact, this seems to be the case from looking at Figure 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)