Valid Conformal Prediction for Dynamic GNNs
Authors: Ed Davis
Ian Gallagher
Daniel John Lawson
Patrick Rubin-Delanchy
Venue: ICLR 2025 Poster (2025)
Keywords: Graph neural networks
Graph machine learning
conformal prediction
Primary area: learning on graphs and other geometries & topologies
TL;DR: A method to perform valid conformal prediction on dynamic graphs using GNNs.

Abstract: Dynamic graphs provide a flexible data abstraction for modelling many sorts of real-world systems, such as transport, trade, and social networks. Graph neural networks (GNNs) are powerful tools allowing for different kinds of prediction and inference on these systems, but getting a handle on uncertainty, especially in dynamic settings, is a challenging problem.

In this work we propose to use a dynamic graph representation known in the tensor literature as the unfolding, to achieve valid prediction sets via conformal prediction. This representation, a simple graph, can be input to any standard GNN and does not require any modification to existing GNN architectures or conformal prediction routines. 

One of our key contributions is a careful mathematical consideration of the different inference scenarios which can arise in a dynamic graph modelling context. For a range of practically relevant cases, we obtain valid prediction sets with almost no assumptions, even dispensing with exchangeability. In a more challenging scenario, which we call the semi-inductive regime, we achieve valid prediction under stronger assumptions, akin to stationarity. 

We provide real data examples demonstrating validity, showing improved accuracy over baselines, and sign-posting different failure modes which can occur when those assumptions are violated.

Published as a conference paper at ICLR 2025
VALID CONFORMAL PREDICTION FOR DYNAMIC GNNS
Ed Davis' Ian Gallagher?
Daniel John Lawson' Patrick Kubin-Delanchy'
Universityy of Bristol, U.K. "The University of Melbourne, Australia Schoool of Mathematics and Maxwell Institute for Mathematical Sciences, University of Edinburgh, U.K.
(edward, davis, dan. Lnwson eerrrerrrooooooo ac. uk ian. gawllageerreeeeee wwwaaaareeinnneeoooe 1b. edu. prdfed. ac. uk
ABSTRACT
Dynamic graphs provide a flexible data abstraction for modelling many sorts of real-world systems, such as transport, trade, and social networks. Graph neural networks (GNNs) are powerful tools allowing for different kinds of prediction and inference on these systems, but getting handle on uncertainty, especially in dynamic settings, a challenging problem.
In this work propose literature as the unfolding, to achieve valid prediction sets via conformal predic- tion. This representation, simple graph, can be input to any standard GNN and does not require any modification to existing GNN architectures or conformal pre- diction routines.
dynamic graph representation known in the tensor
One of our key contributions is a careful mathematical consideration of the differ- ent inference scenarios which can arise dynamic graph modelling context. For a range of practically relevant cases, we obtain valid prediction sets with almost no assumptions, even dispensing with exchangeability. In a more challenging sce- nario, which we call the inni-ivduetive regime, we achieve valid prediction under stronger assumptions, akin stationarity.
We provide real data examples demonstrating validity, showing improved accu- racy over baselines, and sign-posting different failure modes which can occur when those assumptions are violated.
INTRODUCTION
Graph neural networks (GNNs) have seen success in wide variety of application domains including prediction of protein structure (Jmper al. 2021) and molecular properties (Duvenaud al. 2015
Gilmer et al. 2017). drug discovery (Stokes et al., 2020). computer vision (Sarlin et al.] 2020),
natural language processing (Peng et al. 2018 Wu al. (003). recommendation systems (Berg ct al. 2017 Wu et al. 2022 Borisyuk et al. 2024). estimating time of arrival (ETA) in services like et 2021). l,, and advancing mathematics (Davies al. 202T). They
Google Maps (Derrow-Pine)
often top leaderboards in benchmarks relating to machine-learning graphs (Ope), for a range of tasks such as node, edge, or graph property prediction. Useful resources for getting started with
GNNs include the introductions (Hamilton) 2020: Sanchez--Lengelnng et al. 2021) and the Pytorch Geometric library (Pyt).
Conformal prediction (CP), advanced by Vovk and co-authors (Vovk et al. 2005) and later expanded
on by various researchers in the Statistics community (Shafer and Vovk 2008 Lei et al. 2013
Lei and Wasserman 2014 Lei et al. 2018; Foygel Barber et al. 2021 Tibshirani et al. Barber et al.] [023; Gibbs et al. [2023] Romano et al. 2020). is an increasingly popular paradign for constructing provably valid prediction sets from "black-box' algorithm with minimal assumptions and at low cost. Several recent papers have brought this idea to guantifying uncertainty in GNNs
2019
(Huang al. 2024b Clarkson, 2023 Zargarbashi and Bojchevski, 2023

---

Published as a conference paper at ICLR 2025
There many applications of significant societal importance, e.g. eyber-security (Bilot et al. 2023 He et al. 2022 Bowman and Huang 202I). human- buman-trafficking trafficking prevention (Szekely et al. [2015] Nair et a 2024), social media & misinformation (Phan et al., (023),, contact-tracing (Tan et al. (022),
patient care (Luu et al. 2020 Boll et al., 2024) where we would like to be able to use GNNs, with uncertainty quantification, dynamic graphs.
The added time dimension in dynamic graphs causes serious issues with existing GNN + conformal methodology, broadly relating to de-alignment between embeddings across time points (see Fig- ure D.. resulting in large or invalid prediction sets in even simple and stable dynamic regimes. The unsolved problem we address, in nutshell, is guaranteeing that two nodes behaving the same way at distinct points in time are embedded in an exchangeable way, regardless of global network dynamics.
Inspired by concurrent line of statistical research on spectral embedding and tensor decomposition (Zhang and Xia 2018, Cape et al. 2019 Abbe et al. [2200] Delanchy et al. [022] Jones and
Rubin-Delanchy 2020 Gallagher et al. 2021 Agterberg and Zhang (022)) we propose use one of the unfoldings (De Lathauwer et al. 2000) of the tensor representation of the dynamic graph as
input to a standard GNN, and demonstrate validity in both transductive and semi-inductive regimes.
Related work. The use of (tensor) unfoldings in GNNs is new. At present. to our knowledge, the only paper studying conformal inference on dynamic graphs is (Zargarbashi and Bojchevski ). but the paper considers a strictly growing graph, which is very different from our meaning, in which 'dynamic graph' has edges which appear and disappear in complex and random ways, as in all of our examples and in the applications alluded to above. The motivation for our work derives from earlier contributions studying CP on static graphs using GNNs (Huang al. [024bb] Clarkson 2023 Zargarbashi and Bojchevski (2023) but our theory is distinct from those contributions, with ar- guments closer to (Barber a (2023). In the dynamic graph literature, unfoldings have exclusively been proposed for unsupervised settings Jones and Rubin-Delanchy 2020; Gallagher et al., 20221 Agterberg and Zhang 2022 Davis et al., 2023] Wang et al. 2023), particularly spectral embedding, and have never been applied to conformal inference.
Our contribution should be viewed as a novel interface between CP and GNNs, rather than an im- provement of either. This interface allows for modular system design in dynamic graph inference in which both the GNN and CP modules can be chosen and optimised independently. In view of the rapid development of both fields, we have opted against fine-tuning to allow more transparent, sta- blc, and reproducible performance assessments using recognised and standard baselines for GNNs and CP: Graph Convolutional Networks (GCN) (Kipf and Welling, 2016) and Graph Attention Net- works (GAT) (Veličković et al. 2017) for GNNs and APS (Romano et al. 2020) for CP. Our theory applies the representation of the dynamic graph, not the choice of GNN or CP procedures.
2 THEORY & METHODS
Problem setup. In this paper, dynamic graph G is a sequence of T graphs over a globally de- fined nodeset [n] = [I.....n} .n), represented by adjacency matrices A A Technically, all we require is that the A (t) have the same number of rows, allowing for directed, bipartite and weighted graphs. However, the reader may find it easier to assume the A (t) are n X n binary symmetric matrices corresponding to undirected graphs, in which case p-
Along with the dynamic graph G, we are given labels for certain nodes at certain points in time, which could describe state behaviour. Our task is predict the label for a different node/time pair, whose label is hidden or missing. Our prediction must take the form of a set which we can guarantee contains the true label with some pre-specified probability a (e.g. 95%).
We track the labelled and unlabelled node/time pairs in this problem using a fixed sequence v where for each (i, t) E V we assume existence of
1. a class label y: E y, which may not be observed, in some discrete set of cardinality d;
2. a set of attributes, which observed, and represented by a feature vector x(() E &:::
3. corresponding column in A (1) denoted A!)). with at least one non-zero entry.
2

---

Published as a conference paper at ICLR 2025
a) Choice graph representation
Node observation regime
Transductive regime mask
Adjacency Matrices point
Diagonal)
(A'))
Node
Bassline
Semi-inductive regime
Inddpendent
(AMN))
Node
Proposed arprashh
AlM (dliited untoldlngg)
A (Unfolded)
Temporal transductive regime mask
Node
Training
Validatio
Calbration
Test
c) Embedding for simulated data
Unfolded GCN
Block Diagonal GCN
Community #=1
Community 2+2
Time Community Community
Movernent
Simulation contains no change between Timepoints.
Figure Contribution overview. a) This paper is about the representation of the collection of adjacency matrix snapshots. The baseline (current practice) approach treats these as independent and can be viewed as padding 'block-diagonal matrix with zeroes. Unfolding instead column concatenates which links nodes to themselves over time. Dilation results in square symmetric matrix. b) Which data are available at training time affects performance; we report results transductive (all moints period is reserved for testing), or temporal transductive (a future period is reserved for testing and calibration). c) Simulation of an i.i.d. stochastic block model showing the embedding after applying PCA. The models were trained with transductive masks. Block diagonal GCN appears to encode a significant change time despite there being none. The embedding from UGCN is exchangeable over time, as would be expected.
exchangeable in terms of test/train split), semi-inductive (a future
For pair w = (i,t) v, we will use the notation X = x - = A
The data are split into four sets: (training) to learn the GNN parameters; y (ivliddation) for out-of-sample performance evaluation of the GNN; (calibeation) to train the conformal model, and ()ess) is the target for conformal inference.
Clearly, the theory and methodology of this paper are applicable to multiple test nodes, but for simplicity in this section we assume (tes)) comprises only one node.
From these objects define three versions of the inference problem.
Transductive regime. The test label missing completely at random allowing training, validation, and calibration at any time (Figure top).
Temporal transductive regime. Training and validation are undertaken up to some time т. The test label is missing completely at random after time 7, allowing calibration from this interval (Figure D.. bottom).
regime. Training and validation is undertaken up some time The test label occurs after time т, corresponding to a fixed node preventing calibration from this interval (Figure 1p. middle).
3

---

Published as a conference paper at ICLR 2025
In either of the transductive regimes, valid confidence set can be constructed with further assumptions (Algorithm []. We believe this could be exciting because we view the temporal trans- ductive regime, in particular, challenging, and reflects a scenario where we have only historical lahels. Here, we will need to invoke further assumptions such as symmetry and exchangeability. familiar in the conformal predic- tion literature.
extremely common scenario. The semi-inductive regime is more
Formally, for some m < | 11 we reorder the dataset v that the first m node/time pairs correspond to the calibration and test sets, while the remaining pairs correspond to the training and validation sets. For both transductive regimes, the missing label is missing random among the first m node/time pairs of 1r; for the semi-inductive regime, the missing label corresponds to fixed node/time pair in this set. Let (test) =
{ (Weest denote the missing node/time pair, (scalirration) {we,& l S m (tex), and (traiiing) U y (validation) == {we,, & >> m).
Proposed approach. We will repurpose a standard GNN, designed for static graphs, produce dynamic graph embeddings with desirable exchangeability properties. Let g denote a GNN taking as input an adjacency matrix corresponding an undirected graph on n nodes, along with node attributes and node labels, and returning an embedding V Raad Typically, the ith row of V predicts the label of node through
(node has label k) = softmax (V...... Vea)
To represent the adjacency matrix we apply dilated unfolding (Davis et al. 2023) representing the dynamic graph G in the form
A
A
UNF
E
((++aT)x((+xN))
A
0
where A = (A A (T)) E RPXXT (columa-concatenattio)) containing p global (i.e. not t dependent) nodes and temporal nodes (each node/time pair).
The GNN takes input matrix XUNF [(++x))x containing c-dimensional attributes for all nodes in the dilated unfolding. For networks without attributes this matrix is the (p++IT) x (p+ identity matrix. The GNN also requires training and validation labels Yu w E y (training) Up (validation) where global nodes are not assigned label. The resulting output splits into embeddings
UUNF V UNF
= g (AUNP,
UNF X UNF, (Yw : w E (triiing) y (validdution))
where ÚUNF E Rxx contains global representations and the embedding VUNF RR'''xd contains representation of each node/time pair, of principal interest here.
Finally, we shall require some non-conformity score function r Rd x y + R, with the convention that r(j. y) is large when is poor prediction of In practice, we make use of the adaptive non-conformity measures detailed by Romano et al. (2020).
With these ingredients in place, we are in a position to obtain a prediction set Ò for Wast the computation of which is detailed in Algorithm The notation leaves implicit the dependence of the set Ć on the observed data; explicitly, the set Ć is deterministic function of the dynamic graph G, v), and the labels (Yw, E \ ((es))
the attributes (Xw.
Theory. As mentioned earlier, the transductive regime requires no further assumptions.
Lemma 1. In the transductive regime, the prediction set output by Algorithm 7 valid, that is,
F(Yma E0)21-
For the semi-inductive regime, we make the following assumptions:
A1. The columns Aw, w E v, attributes X w E v, and labels Yw, w E are jointly exchangeable, that is, for any permutation [m] + [m].
(=G, n
( (Xu, v), (Y w E v)} A (G, (X,, w E v), (Yw, E EV)]
4

---

Published as a conference paper at ICLR 2025
Algorithm Split conformal inference
Input: Dynamic graph G, node/time pairs V ((triining) pf (validatiio))
p (calibration)
y
attributes (X w E v); labels (Ywr, w E \ (((es)), confidence level a, non-conformity function
1: Learn ŞUNF based ((training) and (validaation)
2: Let the initial confidence set be y
3: Let Rw rrVuN Yw) for p(calibration)
4: Let
[a(m)] largest value in Re: w E y (calibbaation
5: for y E do
6: Let Riest
r -rVUNF 3/)
Whet
7: Remove y from C' if Riest 2
8:
end for
Output: Prediction set Č
The symbol means "equal in distribution". Informally, we can swap columns of A (A A ())) corresponding test or calibration pairs, along with the attributes and labels, without changing the likelihood of the data.
Given a permutation т [m]] + [m]) we use TG to denote dynamic graph in which the columns of G corresponding to V/...... Vm are permuted according to x. More precisely, TG is the dynamic graph corresponding to the sequence of adjacency matrices A (1)' ..... ATY obtained as follows. First, copy (1), ..... A to (1)", ..... A (TY) Next, overwrite any column Ve E MI....; to A Av lçe If xr sequence of length at least m, we write æe to denote the same sequence
with its first m elements permuted according to ग,, that is, (TT)) Ix- if l S m and (TI)e = xe otherwise.
A2. The GNN G is permutation equivariant, that is, for any permutation [N] + [N] with associated permutation matrix II,
G(IAII))) II)(A).
Informally, we re-order the nodes, attributes and labels, we re-order the resulting embedding. Theorem 1. Under assumptions 7 and the prediction output by Algorithm is valid in the semi-inductive regime, that is,
P(Y West E - a
Discussion. Assumption 2 is relatively mild and roughly satisfied by standard GNN architectures. Assumption is more challenging, and can guide us towards curating calibration set. For example, if we hypothesise that the (A E [T') are i.i.d. stationary stochastic processes (over time), then we can satisfy Assumption by ensuring (calibraaton) U (test) contains only distinct nodes. The independence hypothesis will typically break undirected graphs because of the necessary symmetry each (t), and in this case we may also wish ensure that ((cllibration) (tet))) contains only distinct time points. In general, for predicting the label of nodes based on historical information, Assumption [ should make us wary of global drift, poor distributional overlap between the test and calibration nodes, and autocorrelation. The semi-inductive regime is where our theory actively requires dilated unfolding, and where alternative approaches can fail completely; however, even in the transductive regime where our theory covers alternative approaches, the prediction sets from unfolded GNNs (UGNNs) are often smaller.
2.1 VISUAL MOTIVATION: L.I.D DRAWS OF STOCHASTIC BLOCK MODEL
Consider simple two-community dynamic stochastic block model (DSBM) (Yang al. 201 and Hero 2014) for undirected graphs. Let
Xu
[0.5
0.5
B = 2
(1)
0.55
0.9
5

---

Published as a conference paper at ICLR 2025
be matrices of inter-community edge probabilities, and let 2 E 2) be community allocation vector. We then draw each symmetric adjacency matrix point as A (1) ind Bernoulli (B)))) (..
and
(2) (2) ind Bernouli(( 2,.,, for j.
Aij
typical way of applying a GNN to a series of graphs is to first stack the adjacency matrices as blocks the diagonal (Fey and Lenssen 2019).
(1)
0
A
A
from which dynamic graph embedding is obtained through
BB (A XBD {Yw (ttaining)
(validatioo)) )):
where XBD E RDT'xe is the matrix of c-dimensional attributes for all node/time pairs. (For networks without attributes, XBD set be the nT n/ identity matrix). From this representation, it is clear that A BD is not exchangeable over time.
Figure plots the representations, VED and VUNF of A A2) using GCN (Kipf and Welling 2016) as G. It is clear that, despite the fact that A (1) and A (2) come from the same distribution, the output of the block diagonal GCN appears to encode change that is not present. We refer this issue as temporal shift. In contrast, the output of UGCN is exchangeable over time and so features no temporal shift.
This example highlights two advantages of unfolded GNN over the standard GNN case. First, as there is no temporal shift, we would expect to show improved predictive power. Second, exchangeability over time allows for the application of conformal inference across time.
3 EXPERIMENTS
We evaluate the performance of UGNNs using four examples, comprising simulated and real data, summarised in Table prediction sets can tell us something about the underlying network dynamics. Figure 2 displays the number of edges in each of the considered datasets over time. The SBM, school and flight data each feature abrupt changes in structure, while the trade data is relatively smooth.
will then delve deeper into a particular dataset to show how variation in
Dataset
Nodes
Edges
Time points
Classes
Weighted
Directed
Drift
SBM
300
38,350
No
No
No
School
232
53,172
18
10
No
No
No
Flight
2,646
1,635,070
Yes
No
No
Trade
255
468,245
32
163
Yes
Yes
Yes
Table 1: A summary of considered datasets.
SBM. A three-community DSBM with inter-community edge probability matrix
81
0.02
0.027
(+)
0.02
82
0.02
0.02
0.02
where 81, 82, and 83 represent within-community connection states. Fach s can be one of two
values: 0.08 0.16. We simulate dynamic network over T 8 time points, corresponding the 8 = 2 possible combinations, drawing each A from each unique (()) detailed in Section 2.1 The ordering of these time points is random, leading to dynamic total edge count (Figure task is to predict the community label of each node.
The
School. dynamic social network between pupils at a primary school in Lyon, France (Stchlé et al. 2011). Each of the 232 pupils wore radio identification device such that each interaction, with its

---

Published as a conference paper at ICLR 2025
SBM
School
4000
W
5500
5000
3000
4500
2500
2000
4000
1500
10am 12pm 2pm 4pm
10am 12pm 2om
4pm
Time
Day
flight ht
Trade
70000
60000
18000
52000
16000
Number
42000
14000
20000
23000
10000
181
Sep
May
Sep
Jan
May
1998
1990
1900
J992
2004
20100
2008
Time
Figure 2: Numbers of edges over time. The School and Flight data show rough periodic/seasonal structure, which the Trade data features drift with the number of edges growing smoothly with time.
timestamp, could be recorded, forming dynamic network. An interaction defined by close proximity for 20 seconds. The task here is to predict the classroom allocation of each pupil. This dataset has temporal structure particularly distinguishing class time, where pupils cluster together based on their class (easier), and lunchtime, where the cluster structure breaks down (harder). The data covers two full school days, making it roughly repeating.
Flight. The OpenSky dataset tracks the number of flights (edges) between airports (nodes) over each month from the start of 2019 the end of 2021 (Olive et 2022). The task is predict the country of a given (European only) airport. The network exhibits seasonal and periodic patterns, and features a change structure when the COVID-19 pandemic hit Europe around March 2020.
Trade. An agricultural trade network between members of the United Nations tracked yearly be- tween 1986 and 2016 (MacDonald al. 2015). which features the Temporal Graph Benchmark (Huang et al., 2024b). The network is directed and edges are weighted by total trade value. Unlike the other examples, this network exhibits important drift over time. This behaviour visualised in Figure 2 We consider the goal of predicting the top trade partner for each nation for the next year, slight deviation from the benchmark where performance quantified by the Normalized Discounted Cumulative Gain of the top 10 ranked trade partners (less naturally converted into conformal prediction problem).
3.1 EXPERIMENTAL SETUP
On each dataset, we apply GCN (Kipf and Welling 2016) and GAT (Veličković et al. 2017 to the block diagonal and unfolded matrix structures (referred to as UGCN and UGAT respectively) in both the transductive and the semi-inductive settings. The datasets considered do have attributes. In the transductive regime, we randomly assign nodes to train, validation, calibration and test sets with ratios 20/10/35/35, regardless of their time point label. Due the high computational cost of fitting multiple GNNs to quantify randomisation error, we follow (Huang et al.) 2024a) by fitting the GNN 10 times, then constructing 100 different permutations of calibration and test sets to allow 1,000 conformal inference instances per model and dataset, and apply Algorithm 2
For the semi-inductive regime, we apply a similar approach, except that we reserve the last 35% of the observation period as the test set, rounded to use integer number of time points for testing to ensure every node/time pair in the test set is unlabelled. The training, validation and calibration sets then picked random, regardless of time point label. from the remaining data with ratios 20/10/3 10/15 As the test set is fixed, efficiency saving is not possible and we instead run Algorithm (split conformal) 50 random data splits.
7

---

Published as a conference paper at ICLR 2025
Prediction sets computed using the Adaptive Prediction Sets (APS) algorithm (Romano al. 2020) in both regimes. For each experiment, we return the mean accuracy, coverage and prediction set size across all conformal runs to evaluate the predictive power of each GNN, as well as its conformal performance. To quantify error, we quote the standard deviation of each metric. Code to reproduce all experiments can be found in Appendix A
3.2 RESULTS
UGNN has higher accuracy in every semi-inductive example and most transductive examples. In the transductive regime such advantages are often minor, however in the semi-inductive regime UGNN displays more significant advantage (Table 2. Block GNN is close to random guessing in the semi-inductive SBM and School examples (having and classes respectively). In contrast, UGNN maintains strong accuracy in both regimes.
Methods
SBM
School
Trans.
Semi-ind.
Trans.
Semi-ina -nni-ind.
Block GCN
0.964 0.011
0.334 0.024
0.856 0.011
0.116 0.011
UGCN
0.980 = 0.004
0.985 = 0.003
0.924 + 0.009
0.915 + 0.013
Block GAT
0.916 0.028
0.346 = 0.024
0.807 1 0.016
0.107 + 0.024
UGAT
0.947 + 0.032
0.969 = 0.017
0.896 + 0.016
0.868 + 0.017
Methods
Flight
Trade
Trans.
Semi-ind.
Trans.
Semi-ind.
Block GCN
0.405 0.075
0.121 0.059
0.095 = 0.017
0.049 0.018
UGCN
0.441 + 0.069
0.477 = 0.061
0.082 = 0.031
0.050 + 0.017
Block GAT
0.417 0.031
0.114 = 0.061
0.125 = 0.017
0.046 = 0.015
UGAT
0.408 = 0.060
0.427 = 0.061
0.111 + 0.010
0.048 + 0.015
Table 2: Accuracy (higher is better) for GNNs (GCN or GAT) under 2 representations (block diagonal adjacency or unfolding) for 4 datasets. Bold values indicate the highest accuracy for given GNNrepresentatioon pair.
Conformal prediction UGNN and block GNN is empirically valid for every transductive ample. This confirms (Lemma]] [ that exchangeabilitylltee equivariance are not necessary for valid conformal prediction in the transductive regime, even block GNN (which has exchangeability properties) is valid here (Table However, UGNN achieves valid coverage with smaller prediction sets in most cases, making it the preferable method (Ta
Methods
SBM
School
Trans.
Semi-ind.
Trans.
Semi-ind.
Block GCN
0.901
0.014
0.659 + 0.045
0.901
0.012
0.812 0.033
UGCN
0.901
+ 0.015
0.918 + 0.025
0.901 + 0.012
0.924 + 0.013
Block GAT
0.901
0.015
0.450 + 0.154
0.901
0.012
0.662 + 0.084
UGAT
0.901 0.014
0.914 = 0.022
0.901 + 0.012
0.909 + 0.021
Methods
Flight
Trade
Trans.
Semi-ind.
Trans.
Semi-ind.
Block GCN
0.900
0.002
0.853 + 0.013
0.900
0.009
0.842 1 0.015
UGCN
0.900
+ 0.002
0.910 + 0.003
0.900
+ 0.009
0.847 + 0.017
Block GAT
0.900
0.002
0.862 + 0.013
0.900
0.009
0.840 + 0.021
UGAT
0.900
0.002
0.906 + 0.002
0.901 + 0.009
0.854 + 0.023
Table 3: Coverage (targeted to > 0.9) for 2 GNNs (GCN or GAT) under 2 representations (block diagonal adjacency or unfolding) for 4 datasets. Bold values indicate valid coverage with target 2 0.9.
Conformal prediction UGNN is empirically valid for every semi-inductive example without drift, while block GNN is valid for none. In all examples, except the trade dataset, UGNN produces valid conformal (Table with similar prediction set sizes to the transductive case (Table 4
We include the trade data as an example of where UGNN fails to achieve valid coverage in the semi-inductive regime. This failure is due the drift present in the trade network (Figure which
8

---

Published as a conference paper at ICLR 2025
grows over time (approximately doubling in edges over the whole period). Therefore, the network at the start of this series is not approximately exchangeable with the network at the end of the series.
The problem of drift is difficult to handle for UGNN alone, but hypothesise that downstream methods could be applied to improve coverage in these cases, for example (Barber et al. 2023) and (Clarkson] 2023). We leave this investigation for future work.
Due to the unfolded matrix having double the entries of the block diagonal matrix, the computation times for UGNN were roughly double that of block GNN. The maximum time to train an individual model was around minute on an AMD Ryzen 5 3600 CPU processor. A full run of experiments on the largest dataset took around 4.5 hours.
In the appendix, we include many further experiments which include a demonstration of valid- ity in the temporal transductive regime (Appendix E consideration of other score functions for obtaining prediction sets (Appendix G time-conditional coverage (Appendix D various other haiin/aalid/aliibratinnees splits (Appendix F.. and use of other GNN architectures (Appendix HH). In each case, these further experiments bolster the claims made here; UGNN is superior in both predictive performance and in conformal metrics.
Methods
SBM
School
Trans.
Semi-ind.
Trans.
Semi-ind.
Block GCN
1.258 = 0.053
1.977 = 0.138
4.542 = 0.167
8,079 = 0.188
UGCN
1.263 0.206
1.097 = 0.171
2.763 0.311
3.037 = 0.251
Block GAT
1.063 = 180
1.320 = 0.466
3.863
= 0.813
6.540 0.830
UGAT
1.053 + 0.249
1.042 = 0.201
3.552 + 0.756
4.185 = 1.228
Methods
Flight
Trade
Trans.
Semi-ind.
Trans.
Semi-ind.
Block GCN
24.116 2.711
23.283 + 2.285
82.556 1 4.966
80.652 1 6.709
UGCN
22.369 + 1.953
23.030 + 2.115
86.319 = 7.520
85.006 + 9.516
Block GAT
25.173 + 1.631
24.956 + 1.977
87.603 + 6.945
84.708 + 9.690
UGAT
24.453 + 2.368
24.451 + 2.307
92.200 + 7.364
90.021 = 11.592
Table 4: Set sizes (lower is better) for GNNs (GCN or GAT) under representations (block adjacency unfolding) for 4 datasets. Values in bold indicate smaller set size for a given GNN. Values in italics indicate invalid sets.
3.3 TEMPORAL ANALYSIS
The goal of conformal prediction is to provide notion of uncertainty otherwise black-box model. As problem becomes more difficult. this should be reflected in a larger prediction set size maintain target coverage. We analyse this behaviour by focusing on the school data example.
Figures and 3d compare the accuracy of both UGAT and block GAT for each time window of the school dataset. During lunchtime, pupils are longer clustered in their classrooms, making predic- tion of their class more difficult. Figure 3a confirms significant drop in accuracy for both models lunchtime the transductive case. UGAT also displays this behaviour in the semi-inductive case (Figure 3d while block GAT's performance is no better than random selection.
At these more difficult lunchtime windows, the prediction set sizes increase for both methods in the transductive case as shown in Figure 3c UGAT also displays this increase in the semi-inductive regime (Figure 3f). while block GAT does not adapt. This demonstrates that conformal prediction can quantify classification difficulty over time when using UGNN. Note that while computing accuracy requires the knowledge of test labels to quantify difficulty, conformal prediction of set size does not. Figure 3b) confirms that both methods maintain coverage in the transductive case (increasing uncertainty at lunchtimes), and UGAT maintains coverage in the cemi-inductive case (Figure 3ep. The story is similar for UGCN (Appendix Ch.

---

Published as a conference paper at ICLR 2025
1.2
Lonchtime
1.2
8
Block Diagonal
Unfolded
1.0
1.0
Prediction Set Siz0
Set size incresses.
3a lunchtimess
0.8
Coverage
0.8
0.0
Accuracy lunchitime
0.0
Unccertaitty increades
Uncertainty increases
at aunchieeeee
0.4
0.4
Lunchoane
Lunatbme
0.2
0.2
Block Diagonal
Unfolded
Block Diagonal
Unfolded
0.0
10am
2pm
4pm
0.0
10am
12em
Day
20m
4pm
2
Apm
12 Day 2pm
4pm
Time Window
Time Window
Time Window
(a) Accuracy Transductive.
(b) Coverage Transductive.
(c) Set Size Transductive.
1.0
1.2
1
Accuracy
Block Diagonal
Unfolded
1.0
1.2
coverage
maintains
UGAT UGAT uncertainty
increases Pu
Predictoon Set Size
Block diagonal GAT does not react to aunchtime
F Block Diagonal
Unfolded
Accuracy
0.8
USAT has much ligher accuracy
Coverage
0.8
Block diagonal GAI under covers
0.6
0.6
0.4
Block diagonal GAT
0.4
uncertainty does not
Block diagonal GAT
w >
UGAT set sizes
Increase at lanchtime
0.2
Barsform choice
selects randomly
0.2
Unfoldedd
Block Diagonal
increase
Lunchcire
Lonottim
0.0
10am
m
120
2pm
Apm
4pm
0.0
12em
Day 1 2pm
4pm
17pm
Dol 2
4pm
10wm
12pm
Day
2pm
4pm
12pm
Day 2
4pm
Time Window
Time Window
Time Window
(d) Accuracy
Semi-inductive.
(c) Coverage Semi- -eni-inductive.
(f) Set Size Semi-inductive.
Figure 3: Performance metrics for each time window of the school dataset for unfolded GAT and block diagonal GAT. The prediction task gets more difficult at lunchtime, shown by the drop in accuracy of both methods in the transductive case. UGAT has marginally better performance in the transductive case and significantly better performance in the semi-inductive case. Prediction set sizes increase at lunchtime, with only UGAT set sizes reacting in the semi-inductive case. Both methods maintain target coverage in the transductive case, with uncertainty increasing at the more difficult lunchtime window. UGAT also maintains target coverage in the semi-inductive case, while block GAT under-covers.
DISCUSSION
This paper proposes unfolded GNNs, which exhibit exchangeability properties allowing conformal inference in both transductive and semi-inductive regimes. We demonstrate improved predictive performance, coverage, and prediction set size across range of simulated and real data examples.
As the supplied code will demonstrate, have intentionally avoided any type of fine-tuning, be- cause the goal here is less prediction accuracy than uncertainty quantification. There are significant opportunities improve the prediction performance of unfolded GNNs, such as employing archi- tectures better suited to bipartite graphs.
The raw computational challenge of unfolding modest (a factor of 2) but typical tricks for mega- scale analyses, for example loading time-points into memory independently, cannot be applied. However, the embedding of the behaviour of a node over time ('rows' of A) is in principle amenable to acceleration. Specifically, the behaviour of node at only few representative times may be needed to anchor behaviour at a target time. Therefore acceleration of unfolded GNNs to mega- scale is plausible for future work (e.g. Gao et al. (2024a b)).
There are also opportunities to improve the downstream treatment embeddings, such as deploying the CF-GNN algorithm (Huang et al. 2024a) to reduce prediction set sizes, or weighting calibration points according to their exchangeability with the test point (Barber et al. 2023 Clarkson 2023).
Our use of unfolding originates from body of statistical literature on spectral embedding and tensor decomposition, where it may be useful to observe that inductive embedding is straightforward: the singular vectors provide projection operator which be applied to new nodes. Being able to somehow emulate this operation in unfolded GNNs could provide a path towards fully inductive inference.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
Ed Davis gratefully acknowledges support by LV= Insurance (Allianz Group) and the Centre for Doctoral Training in Computational Statistics and Data Science (Compass, EPSRC Grant number EP/S023569/1), Compass is funded by United Kingdom Research and Innovation (UKRI) through the Engineering and Physical Sciences Research Council (EPSRC), (EtsRC),btttss councila/epsre This work was carried out using the computational facilities the Advanced Computing Research Centre, University of Bristol Ihtt::/ www. briis ac uk/ ak/accr/] PR- gratefully acknowledges support from the NeST programme grant, EPSRC grant number EP/X002195/1.
www. ukri org/
REFERENCES
Open graph benchmark. httpps://ogb.staffordd.ee Accessed: 2024-05-22.
PyG documentation. Accessed: 2024-05-22.
Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigenvector analysis of random matrices with low expected rank. Annals of statistics, 48(3):1452, 2020.
Joshua Agterberg and Anru Zhang. Estimating higher-order mixed memberships via the l2,00 tensor perturbation bound. arXiv preprint arX1::211.006642, 2022.
Anastasios Angelopoulos, Stephen Bates, Jitendra Malik, and Michael Jordan. Uncertainty sets for image classifiers using conformal prediction. arXiv preprint arXiv:2009. /4/93, 2020.
Anastasios Angelopoulos and Stephen Bates. A gentle introduction conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXivv2107.07511, 2021.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. Conformal prediction beyond exchangeability. The Annals of Statistics, (2): 16845, 2023.
Rianne den Berg, Thomas N Kipf, and Max Welling. Graph convolutional matrix completion. arXiv preprint arXiv: 770.00226, 2017.
Tristan Bilot, Nour El Madhoun, Khaldoun A1 Agha, and Anis Zouaoui. Graph neural networks for intrusion detection: A survey. IEEE Access, 2023.
Heloísa Oss Boll, Ali Amirahmadi, Mirfarid Musavian Ghazani, Wagner Ourique de Morais, Edison Pignaton Freitas, Amira Soliman, Kobra Etminani, Stefan Byttner, and Mariana Recamonde-Mendozaa Graph neural networks for clinical risk prediction based on electronic health records: A survey. Journal of Biomedical Informatics, page 104616, 2024.
Fedor Borisyuk, Shihai He, Yunbo Ouyang, Morteza Ramezani, Peng Du, Xiaochen Hou, Cheng- ming Jiang, Nitin Pasumarthy, Priya Bannur, Birjodh Tiwana, al. LiGNN: Graph neural net- works at LinkedIn. arXiv preprint 240. 2024.
Benjamin Bowman and H Howie Huang. Towards -exeeeennattion cybersecurity with graph AI. ACM SIGOPS Operating Systems Review, 55(1):61-67, 2021.
Joshua Cape, Minh Tang, and Carey E. Priebe. The two-to-infinity norm and singular sub- space geometry with applications to high-dimensional statistics. The Annals of Statistics, 47 (5):2405 2439, 2019. doi: 10.1214/18-A0S1777 URL httpp:://cc....... http:///0o..oo11.11111111 (8-A081752)
Jase Clarkson. Distribution free prediction sets for node classification. In International Conference on Machine Learning, pages 6268-6278. PMLR, 2023.
Alex Davies, Petar Veličković, Lars Buesing, Sam Blackwell, Daniel Zheng, Nenad Tomašev, Richard Tanbur,, Peter Battaglia, Charles Blundell, András Juhász, et al. Advancing mathematics by guiding human intuition with AI. Nature, 600(7887):70-74, 2021.

---

Published as a conference paper at ICLR 2025
Ed Davis, lan Gallagher, Daniel John Lawson, and Patrick Lubin-Delandee A simple and powerful framework for stable dynamic network embedding. arXiv preprint arXiv:2311.09251, 2023.
Lieven De Lathauwer, Bart De Moor, and Joos Vandewalle. A multilinear singular value decompo- sition. SIAM journal on Matrix Analysis and Applications, 21(4):1253-1277 2000.
Austin Derrow-Pinion Jennifer She, David Wong, Oliver Lange, Todd Hester, Luis Perez, Marc Nunkesser, Seongjae Lee, Xueying Guo, Brett Wiltshire, et al. ETA prediction with graph neural networks in google maps. In Proceedings of the 30th ACM International Conference on Informa- fion & Knowledge Management, pages 3767-3776, 2021.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. The limits of distribution-free conditional predictive inference. Information and Inference: Journal of the IMA, 10(2):455-482, 2021.
Gallagher, Andrew Jones, and Patrick Rubin- Sebin-Delanchy. Spectral embedding for dy- namic networks with stability guarantees. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan, editors, Advances cessing Systems, volume 34, pages 10158-10170. Curran Associates, Inc., 202L. URL https::/proceddngs neurips. ccppppr httpppppppr_fsspppppapeeeeeeeee wwt.ss/paaae//222//......
Neural Information Pro-
Shihong Gao, Yiming Li, Yanyan Shen, Yingxia Shao, and Lei Chen. ETC: Efficient training of temporal graph neural networks over large-scale dynamic graphs. Proc. VLDB Endow, 17(5):
1060-1072, May 2024a. ISSN 2150-8097, doi: 10. 10.14778/34412043344122
URL https:
//doi.org/10, 14711477788
Shihong Gao, Yiming Li, Xin Zhang, Yanyan Shen, Yingxia Shao, and Lei Chen. Simple: Ef- ficient temporal graph neural network training at scale with dynamic data placement. Proc. ACM Manag. Data, 2(3), May 2024b. doi: 10.1145/3654977. URL htttps:///oi..... .org/
10.1145/365497
Isaac Gibbs, John Cherian, and Emmanuel Candès. Conformal prediction with conditional guar- antees. arXiv preprint arXiv:2305. 2tt.:23355/261/1 /26/6, 2023.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In International conference machine learning, pages 1263-1272. PMLR, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
William Hamilton. Graph representation learning. Morgan & Claypool Publishers, 2020.
Haoyu He, Yuede Ji, and H Howie Huang. Illuminati: Towards explaining graph neural networks for cybersecurity analysis. In 2022 IEEE 7th European Symposium on Security and Privacy (EuroS&P), pages 74-89. IEBE, 2022.
Jianguo Huang, Huajun Xi, Linjun Zhang, Huaxiu Yao, Yue Qiu, and Hongxin Wei. Conformal prediction for deep classifier via label ranking. arXiv preprint arXiv:2310.06433 2023.
Kexin Huang, Ying Jin, Emmanuel Candes, and Jure Leskovec. Uncertainty quantification over graph with conformalized graph neural networks. Advances Neural Information Processing Systems, 36, 2024a.
12

---

Published as a conference paper at ICLR 2025
Shenyang Huang, Farimah Poursafaei, Jacob Danovitch, Matthias Fey, Weihua Hu, Emanuele Rossi, Jure Leskovec, Michael Bronstein, Guillaume Rabusseau, and Reihanch Rabbany. Temporal graph benchmark for machine learning temporal graphs. Advances in Neural Information Processing Systems, 36, 2024b.
Andrew Jones and Patrick Rubin-Delanche The multilayer random dot product graph. arXiv preprint arXiv:2007. 10455, 2020.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger,
Kathryn Tunyasuvumakool, Russ Bates, Augustin Zidek, Anna Potapenko, et al. Highly accurate protein structure prediction with AlphaFold. Nature, 596(7873)5583- 2021.
Thomas N Kipf and Max Welling. Supi-super classification with graph convolutional net- works. arXiv preprint arXiv: 2016.
Jing Lei and Larry Wasserman. Distribution-free prediction bands for non- non- con-parametric regression. Journal of the Royal Statistical Sociery Series B: Statistical Methodology, 76(1):71-99) 2014.
Jing Lei, James Robins, and Larry Wasserman. Distribution- free prediction sets. Journal of the American Statistical Association, 108(501):27--287 2013.
Jing Lei, Max Gelll, Alessandro Rinaldo, Ryan J. Tibshirani, and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113 (523):1094-1111, 2018. doi: 10.108000162145922117..338
Zheng Liu, Xiaohan Li, Hao Peng. Lifang He, and S Yu Philip. Heterogeneous similarity graph neural network on electronic health records. 2020 IEEE international conference on big data (big data), pages 1196-1205. IEEE, 2020.
Graham K MacDonald, Kate A Brauman, Shipeng Sun, Kimberly M Carlson, Emily S Cassidy, James S Gerber, and Paul C West. Rethinking agricultural trade relationships in an era of global- ization. BioScience, 65(3)277--289 2015.
Prathecksha Nair, Javin Liu, Catalina Vajiac, Andreas Olligschlaeger, Duen Horng Chau, Mirela Cazzolato, Cara Jones, Christos Faloutsos, and Reihaneh Rabbany. T-net: Weakly supervised graph learning for combatting human trafficking. Proceedings of the AAAI Conference on Artificial Intelligence, volume 38(20), pages 22276-22284, 2024.
Xavier Olive, Martin Strohmeier, and Jannis Lübbe. Crowdsourced air traffic data from The Open- Sky Network 2020 [CC-BY], January 2022. URL
5281/ zenodo.
58 1548
Hao Peng, Jianxin Li, Yu He, Yaopeng Liu, Mengjiao Bao, Lihong Wang, Yangqiu Song, and Qiang Yang. Large-scale hierarchical text classification with recursively regularized deep graph-CNN. In Proceedings of the 2018 world wide web conference, pages 1063-1072, 2018.
Huyen Trang Phan, Ngoe Thanh Nguyen, and Dosam Hwang. Fake news detection: A survey of graph neural network methods. Applied Soft Computing, page 110235, 2023.
Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive cover- age. Advances Neural Information Processing Systems, 33:3581-3591, 2020.
Patrick Rubin-Delanchy, Joshua Cape, Minh Tang, and Carey Priebe. A statistical interpretation of spectral embedding: the generalised random dot product graph. Journal of the Royal Statistical Society Series B: Statistical Methodology, 8464):1446-1473, 2022.
Benjamin Sanchez-Lengelee
Emily Reif, Adam Pearce, and Alexander B. Wiltschko. A gentle introduction graph neural networks. Distill, 2021. doi: (0.2391.5ddisttll.00033. https://disilll.pb/0022/// 1tg.///in/o....ooo...ooomm intro..
Paul-Edouard Sarlin, Daniel DeTone, Tomasz Malisiewicz, and Andrew Rabinovich. Superglue: Learning feature matching with graph neural networks. In Proceedings of the IEEE/CVF confer- on computer vision and pattern recognition, pages 4938-4947, 2020.
13

---

Published as a conference paper at ICLR 2025
Glenn Shafer and Vladimir Vovk. A tutorial conformal prediction. Journal of Machine Learning Research, 9(3), 2008.
Juliette Stehlé, Nicolas Voirin, Alain Barrat, Ciro Cattuto, Lorenzo Isella, Jean-François Pinton, Marco Quaggiotto, Wouter Van den Broeck, Corinne Régis, Bruno Lina, et al. High-resolution measurements of face-to-face contact patterns in primary school. PloS one, 6(8):e23176, 2011.
Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar A deep learning approach to antibiotic discovery. Cell, 180(4):688-702. 2020.
et al.
Pedro Szekely, Craig A Knoblock, Jason Slepicka, Andrew Philpot, Amandeep Singh, Chengye Yin, Dipsy Kapoor, Prem Natarajan, Daniel Marcu, Kevin Knight, et al. Building and using a knowl- edge graph to combat human trafficking. In The Semantic Web-ISWC 2015: 14th International Semantic Web Conference, Bethlehem, PA, USA, October 1-1,, 2015, Proceedings, Part 14, pages 205-221. Springer, 2015.
Chee Wei Tan, Pei-Duo Yu, Siya Chen, and H Vincent Poor. Deeptrace: Learning optimize contact tracing in epidemic networks with graph neural networks. arXiv preprint arXiv:2211 1.00800 2022.
Ryan J Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal pre- diction under covariate shift. Advances in neural information processing systems, 32, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 2017.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world, volume 29, Springer, 2005.
Fan Wang, Wanshan Li, Oscar Herman Madrid Padilla, Yi Yu, and Alessandro Rinaldo. Multi- layer random dot product graphs: Estimation and online change point detection. arXiv preprint arXiv:2306. 15286, 2023.
Lingfei Wu, Yu Chen, Kai Shen, Xiaojie Guo, Hanning Gao, Shucheng Li, Jian Pei, Bo Long, al. Graph neural networks for natural language processing: A survey. Foundations and Trends@ in Machine Learning. 16(2):1 19-328. 2023.
Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recommender systems: survey. ACM Computing Surveys, 55(5):1-37, 2022.
Kevin S Xu and Alfred Hero. Dynamic stochastic blockmodels for time-evolving social networks. IEEE Journal Selected Topics in Signal Processing, 8(4):552-50) 562, 2014.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks. In International conference on machine learning, pages 5453-5462. PMLR, 2018.
Tianbao Yang. Yun Chi, Shenghuo Zhu, Yihong Gong, and Rong Jin. Detecting communities and their evolutions in dynamic social networks-a Bayesian approach. Machine learning, 82:157- 189, 2011.
Soroush H Zargarbashi and Aleksandar Bojchevski. Conformal inductive graph neural networks. In The Twelfth International Conference on Learning Representations, 2023.
Anru Zhang and Dong Xia. Tensor SVD: Statistical and computational limits. IEEE Transactions on Information Theory, 64(11):7311-7338, 2018.
A CODE AVAILABILITY
Python code for reproducing experiments is available at https://github com/
edwa s foo for dyn.miimmm.mmmmmmmmm cammmmmigggm gnn
14

---

Published as a conference paper at ICLR 2025
B SUPPORTING THEORY FOR SECTION 2
B.I TRANSDUCTIVE THEOOR
Our arguments are similar in style to (Barber et al. 2023), showing validity of full conformal infer- ence, and then split conformal special case full conformal.
We observe Y for all w E apart from Yuu. where the query point K is chosen independently and uniformly at random among (L.....m].
B.1.1 FULL CONFORMAL PREDICTION
Suppose we have access to an algorithm A(g. z, y) which takes as input:
1. 9. a dynamic graph on nodes and T time points;
2. | sequence of feature vectors;
3. y, a |p|-long sequence of labels;
and returns sequence
(fi Tm) of real values, which will act as non-conformity scores.
Algorithm Full conformal inference
Input: Dynamic graph G, index set v, attributes (Xw,, w E 2/), labels (Y.:: w E v VK), confidence level a, algorithm A, query point K
1: Let Ć ==
2: for y do
3: Let
X (Xm...., Xmm)): yt y+= (Vm..... Yuk-1 Y YERH..... Yen))
4: Compute
(Ri,..., Rm) = A(G,X,Y*)
5: Remove y from Ö' if
Rx among [a(m)] largest of Bi,..., Rm
6: end for
Output: Prediction set Ò
Lemma 2. The prediction set output by Algorithm is valid.
Proof. Because K ind
uniform((m]), the event
E "Rx among [a(m) largest of Ri...., Rm
occurs with probability
P(E) a
But E occurs if and only if Yux Ò. Therefore,
IPYY2x E E = 1 $ $ 1- 2 1 - a.
What this formalism makes clear is that the validity of full conformal inference in a transductive setting has nothing to do with exchangeability or any form of symmetry in A (neither which were assumed).
15

---

Published as a conference paper at ICLR 2025
Algorithm 3 Split conformal inference (abstract version)
Input: Dynamic graph G, index set attributes (Xw, E v), labels (Yu: E PK), confidence
level a, prediction function f, non-conformity function r, query point K
1: Let CC=
2: Let R2 = r(f(v) x,) for E [m] \ K
3: Let
q = [a(m] largest value R. [m] / K
4: for y E J do
5: Let Rx = =r(s(uk), ),
6: Remove y from Ö if Rx 2 ④
7:
end for
Output: Prediction set Ć
B.1.2 SPLIT CONFORMAL PREDICTION
Suppose we construct A according split training/calibration routine, as follows. First, using g, 1/, the feature vectors (Xw; E v), and the labels Yu,, > m, learn prediction function - R2d
The vector f(ve) might, for example, relate to predicted class probabilities via
P(Y,, = k) = (fottaa((fv)))...... ((v))))
in which case f(v)) is often known as an embedding.
Second, for non-conformity function Rdd x y + R. dynamic graph g. and x, y of length |u], define
[A y)le = r(f(ve), ve), E [m].
Then Algorithm 2 can potentially be made much more efficient, shown in Algorithm [ This is nothing but the usual split conformal inference algorithm, where the labels Yo,, & > m are being used for training, and Yz,, E [m] K for calibration.
Thus split conformal inference is a special case of full conformal inference, in which special struc- ture is imposed A, and must therefore inherit its general validity (Lemmal) I
B.2 SEMI-INDUCTIVE THEORY
Otherwise keeping the same setup, suppose K is not uniformly chosen but is instead fixed, to (say)
K 1.
A3. The algorithm A(g, v. y) is symmetric in input. For any permutation v + v.
Alng, nZ, ny) TA(g x.
Theorem 2. Under assumptions and the prediction output by Algorithm (and Algo- rithm 3) is valid even if K deterministicall::
Proof. The combination of assumptions therefore the event
I and ensures that Ri...., Ry are exchangeable, and == "Ri among [a(m)] largest of Ri...., "
occurs with probability
PPE) a.
But E occurs if and only if Yv, & Ć. Therefore,
P(Y,, Ô) P(Yxx &
16

---

Published as a conference paper at ICLR 2025
To map Theorem Theorem | observe that Assumptions I and are the same (the latter detailed version of the former); and that inputting A UNF to GNN satistying Assumption 2 along with the attributes X w E and training labels Yu, w E ultaainig)) results in an satisfying Assumption 3
C TEMPORAL ANALYSIS USING GCN
In this section, we present a temporal analysis of the school data example using GCN instead of GAT the GNN model. We see similar conclusions to those stated in Section The accuracy of UGCN is slightly higher at every time point in the transductive case and much higher in the semi-inductive case. Block GCN essentially guessing randomly in the semi-inductive case. The prediction sets for UGCN are always smaller than those of block GCN, with UGCN's set sizes also reacting to the difficulty problem in the semi-inductiiv regime. However, neither method achieves valid coverage of every time point in the transductive regime, in contrast to GAT. UGCN also under-covers the first test point in the semi-inductive case (unlike UGAT), while block GCN continually under-covers here.
Accuracy
Accuracy
1.0
Block Diagoral
Unfolded
Acoracy
Acturaty
0.4
Block Diagonal
0.2
Unfolded
10am 17pm 2pm
4pm
10am
12pm 2pm
4pm
10am 12pm 2pm
4pm
10am
12
2pm
4pm
Day
Day
Day
Day?
Window
Time
(a) Transductive.
(b) cemi-inductive.
Figure 4: Prediction accuracy for each time window of the school dataset for unfolded GCN and block diagonal GCN. The prediction task gets more difficult at lunchtime, as shown by the drop in accuracy of both methods in the transductive case. UGCN has marginally better performance in the transductive case and significantly better performance in the semi- aomi-inductive case.
GCN Coverage
GCN Coverage
1.00
Block Diagona'
Unfolded
0.35
0.95
0.90
0.90
Corenge
0.85
0.85
0.75
0.70
Diagenal
0.65
Unfolded
12pm
2pm
2pm
4pm
2pm
4pm
12pm 2pm
4pm
Time Window
Window
(a) Transductive.
(b) Semi-inductive.
Figure 5: Coverage for each time window of the school dataset for unfolded GCN and block diagonal GCN. Both methods maintain target coverage on average in the transductive case, but not at every point in time. In the remi-inductive case, block GCN under-covers continuously and UGCN under- covers for the first test point.
17

---

Published as a conference paper at ICLR 2025
Prediction
Prediction
Block Dagonal
Block Diagonal Unfolded
Prediction Sel Size
Prediction Set
10am 17pm 7pm 4pm
10am 17pm
4pm
10am 12pm 2pm Day 2
10am
12pm 7pm
4pm
Day
Day
Day 2
Time Window
Time Window
(a) Transductive.
(b) Semi-inductive.
Figure 6: Prediction set sizes for each time window of the school dataset for unfolded GCN and block diagonal GCN. As the prediction task gets more difficult lunchtime the prediction set sizes increase. Only the UGCN set sizes react to lunchtime the
case.
D TIME-CONDITIONAL COVERAGE
When evaluating conformal procedure, it is common to consider conditional coverage (Angelopou- los and Bates 2021 Huang et al. 2024a Lei and Wasserman 2014). A procedure with conditional coverage would be very adaptable, it would return prediction sets with coverage 1 condi- tional on the test point. While this property is desirable, exact distribution-ffed conditional coverage (Lei and Wasserman 2014). Despite this, is common to evaluate approximate conditional coverage by looking at the worst-case coverage across certain features or groups (Angelopoulos and Bates 2021). For the purposes of this paper, evaluate the time-conditional coverage, in other words, the worst-case coverage for a single time point out of all time points in the series.
known to be impossible to achieve
displaas the condiiinii coverage for each method. While UGAT is often valid, it is not generally true that either block GNN UGNN achieves validity here. The reason for this again rooted in data drift. As no two time points are exactly exchangeable, no two embedded time points will be exactly exchangeable. This then translates variation in coverage between time points. In the marginal coverage case, variation is fine long the average coverage is target. However, under this metric, any variation causes decrease.
Despite this, let us consider example with no drift between time points. Consider another three- community DSBM with inter-community edge probability matrix
0.16
0.02
0.027
B
0.02
0.08
0.02
0.02
0.02
0.16
and draw each A (*) from B. This means that the series is simply list of i.i.d. draws and so features no data drift. Table 6 displays the result of running our experiments on this data. As expected, each method achieved value time-conditional coverage in the transductive and temporal transductive regimes as drift between time points no longer problem. However, even with such a basic data example, it is only the UGNNs that are able to achieve valid temporal-conditional coverage here.
18

---

Published as a conference paper at ICLR 2025
Methods
SBM
School
Trans.
Semi-ind.
Trans.
Semi-ind,
Block GCN
0.783 + 0.091
0.645 = 0.055
0.820 = 0.077
0.797 + 0.062
UGCN
0.806 0.044
0.869 + 0.030
0.702 + 0.051
0.710 + 0.041
Block GAT
0.856 = 0.068
0.450 = 0.154
0.763 = 0.114
0.656 + 0.083
UGAT
0.877 0.040
0.907 0.031
0.828 0.058
0.870 0.056
Methods
Flight
Trade
Trans.
Semi-ind.
Trans.
Semi-ind.
Block GCN
0.881 0.011
0.852 = 0.013
0.801 + 0.064
0.767 + 0.044
UGCN
0.877 = 0.011
0.894 = 0.004
0.800 - 0.094
0.774 0.056
Block GAT
0.885 = 0.011
0.861 = 0.014
0.822 + 0.061
0.776 + 0.046
UGAT
0.889 0.009
0.896 0.004
0.784 + 0.076
0.792 0.065
Table 5: Time-conditional coverage over time with target coverage.
0.90. Values in bold indicate valid
Methods
SBM (i.i.d.)
Trans.
Temp. Trans.
Semi Ind.
Block GCN
0.875
0.063
0.982 = 0.018
0.653 0.072
UGCN
0.880
0.031
0.881 + 0.048
0.891 0.010
Block GAT
0.862 + 0.079
0.976 = 0.022
0.449 + 0.158
UGAT
0.883 0.031
0.887 = 0.045
0.885 0.016
Table Time-conditional coverage on an i.i.d. version the SBM experiment. Bold values indicate validity with target 2 0.90.
TEMPORAL TRANSDUCTIVE
As mentioned in Section 2 and visualised in Figure [ (bottom), the temporal transductive regime represents the case where the train and validation sets are selected randomly from data at times 1 T, and calibration and test sets are selected randomly from 2 T. This regime exists as more practical version of the standard transductive regime, despite, theoretically, requiring no extra assumptions for valid conformal sets. However, this regime presents more of a challenge in comparison to the standard transductive case require model that is trained on t < T to generalise to 2
Table 7 displays the results of rumning experiments in this regime. As predicted by theory, and similarly to the transductive experiments, every method (including the block diagonal methods) achieves valid coverage here. However, as only the unfolded methods are exchangeable over time, the UGNN methods have a significantly higher accuracy on the datasets with out drift. Due to this, the average prediction size is also reduced for the UGNNs.
19

---

Published as a conference paper at ICLR 2025
Methods
SBM
School
Flight
Trade
Block GCN
0.318 = 0.036
0.118 = 0.025
0.103 + 0.063
0.052 + 0.014
UGCN
0.984 = 0.010
0.925 = 0.020
0.464 = 0.075
0.043 + 0.021
Block GAT
0.355 0.046
0.104 0.032
0.106 0.064
0.049 0.015
UGAT
0.980 = 0.012
0.903 = 0.028
0.420 + 0.064
0.051 + 0.016
(a) Accuracy.
Bold values indicate higher accuracy.
Methods
SBM
School
Flight 0.900 + 0.005
Trade
Block GCN
0.985 = 0.011
0.911 = 0.026
0.901 - 0.014
UGCN
0.904 0.028
0.901 0.027
0.900 = 0.005
0.901 0.015
Block GAT
0.977 = 0.014
0.931 = 0.033
0.900 = 0.005
0.901 = 0.015
UGAT
0.905 0.027
0.902 = 0.026
0.900 + 0.005
0.901 + 0.015
(b) Coverage. Bold values indicate validity with target 2 0.90.
Methods
SBM
School
Flight
Trade
Block GCN
2.952 + 0.018
9.069 0.186
30.075 2.783
111.315
10.401
UGCN
1.170 = 0.199
3.718 + 0.259
21.466 + 2.226
112.427 = 8.300
Block GAT
2.933 + 0.031
9.153
0.322
30.842 + 2.519
115.805 8.289
UGAT
0.933 = 0.036
4.488 0.698
23.626 2.399
111.892 7.711
(c) Average set size. Bold values indicate smaller set sizes.
Methods
SBM
School
Flight
Trade
Block GCN
0.985 + 0.017
0.898 + 0.072
0.899 + 0.017
0.858
0.055
UGCN
0.858 + 0.080
0.654 + 0.104
0.884 + 0.017
0.842
0.049
Block GAT
0.975 = 0.024
0.914
0.083
0.898 + 0.017
0.850
0.055
UGAT
0.870 + 0.058
0.832 + 0.084
0.891 + 0.017
0.844 = 0.068
(d) Time-conditional coverage. Bold values indicate validity with target 2 0.90.
Table 7: Experiments run in the temporal transductive regime.
F REPEAT EXPERIMENTS WITH DIFFERENT DATA SPLITS
Throughout this work, we have used a standard 20/10/35/35 reinnvaalidtioonccllrrrtinnettti data split. To explore the sensitivity of our results to data split selection, we carry out repeat of our experiments using six different data split ratios. For the sake of computational efficiency, we repeat these experiments using only the school dataset.
Across the different data splits, we almost always achieve the same results as those in the main text. While there is one case of UGCN just missing out on valid coverage, and few cases of block GCN achieving valid coverage in the semi-inductive regime, we never see block GNN achieving valid coverage when UGNN does not, Therefore, UGNN appears to be the favoured method, regardless of data split choice.
20

---

Published as a conference paper at ICLR 2025
Embedding
School
Trans.
Semi-ind.
Temp. Trans.
Block GCN
0.901 = 0.014
0.833 = 0.046
0.909 = 0.019
UGCN
0.901
0.014
0.943 = 0.018
0.903 0.014
Block GAT
0.902
0.014
0.681 = 0.102
0.916
0.026
UGAT
0.901 + 0.014
0.912 = 0.024
0.901 + 0.014
(a) Coverage for the School experiment with data split 25/25/25/25.
Embedding
School
Trans.
Semi-ind.
Temp. Trans.
Block GCN
0.903
0.015
0.826
0.075
0.913
0.020
UGCN
0.902 + 0.016
0.939 = 0.020
0.902 + 0.016
Block GAT
0.904
0.015
0.692
+ 0. 1.109
0.926
0.029
UGAT
0.903
0.016
0.901
0.035
0.902
0.015
(b) Coverage for the School experiment with data split 50/10/20/20.
Embedding
School
Trans.
Semi-ind.
Temp. Trans.
Block GCN
0.901 + 0.011
0.822 = 0.055
0.905 + 0.016
UGCN
0.900
0.011
0.867 = 0.022
0.899 0.011
Block GAT
0.901
0.011
0.628 = 0.099
0.909
0.017
UGAT
0.901 + 0.011
0.909 = 0.021
0.901 + 0.011
(c) Coverage for the School experiment with data split 10/10/40/40.
Embedding
School
Trans.
Semi-ind.
Temp. Trans.
Block GCN
0.901
0.012
0.823 = 0.049
0.906 0.017
UGCN
0.901 + 0.012
0.889 = 0.020
0.903 + 0.012
Block GAT
0.901
0.012
0.654 + 0.093
0.914 + 0.022
UGAT
0.901
0.012
0.907 = 0.024
0.901
0.012
(d) Coverage for the School experiment with data split 20/10/35/35.
Embedding
School
Trans.
Semi-ind.
Temp. Trans.
Block GCN
0.906 + 0.022
0.845 = 0.070
0.918 + 0.031
UGCN
0.905
0.022
0.903 + 0.030
0.906
0.026
Block GAT
0.906
0.022
0.705 + 0.115
0.946
0.046
UGAT
0.906 + 0.022
0.876 = 0.042
0.907 + 0.026
(c) Coverage for the School experiment with data split 50/30/10/10.
Embedding
School
Trans.
Semi-ind.
Temp. Trans.
Block GCN
0.901 0.013
0.870 = 0.039
0.910 0.017
UGCN
0.901
0.013
0.897 = 0.020
0.902 0.014
Block GAT
0.901
0.013
0.786 = 0.069
0.908 0.019
UGAT
0.902 0.013
0.908 = 0.023
0.901 0.013
(f) Coverage for the School experiment with data split 5/35/30/30.
Table Coverage for repeated runs of the School experiment with various data splits. Bold values indicate valid coverage with target 2 0.9.
21

---

Published as a conference paper at ICLR 2025
Embedding
School
Trans.
Semi-ind.
Temp. Trans.
Block GCN
0.888 + 0.013
0.109 = 0.025
0.112 = 0.010
UGCN
0.935 0.007
0.896 = 0.010
0.938 0.006
Block GAT
0.834
0.021
0.108 = 0.028
0.106
0.018
UGAT
0.908 + 0.019
0.883 = 0.014
0.904 + 0.024
(a) Accuracy for the School experiment with data split 25/25/25/25.
Embedding
School
Trans.
Semi-ind.
Temp. Trans.
Block GCN
0.911 0.010
0.108 = 0.035
0.118
0.015
UGCN
0.931
0.010
0.971 = 0.008
0.923 + 0.009
Block GAT
0.880
0.016
0.111
+ 0.034
0.095
0.032
UGAT
0.912 0.017
0.962 = 0.010
0.908
0.014
(b) Accuracy for the School experiment with data split 50/10/20/20.
Embedding
School
Trans.
Semi-ind.
Temp. Trans.
Block GCN
0.787 + 0.020
0.105 = 0.019
0.110 + 0.010
UGCN
0.928 0.009
0.913 = 0.014
0.924 0.006
Block GAT
0.697
0.031
0.102 = 0.023
0.108
0.015
UGAT
0.880 + 0.019
0.903 = 0.016
0.876 + 0.014
(c) Accuracy for the School experiment with data split 10/10/40/40.
Embedding
School
Trans.
Semi-ind.
Temp. Trans.
Block GCN
0.871
0.010
0.105 = 0.024
0.113 0.009
UGCN
0.933 + 0.006
0.913 = 0.009
0.953 + 0.006
Block GAT
0.808 + 0.018
0.107 + 0.025
0.109 + 0.010
UGAT
0.901
0.021
0.899 = 0.012
0.910
0.014
(d) Accuracy for the School experiment with data split 20/10/35/35.
Embedding
School
Trans.
Semi-ind.
Temp. Trans.
Block GCN
0.910 + 0.016
0.113 = 0.038
0.135 + 0,026
UGCN
0.934
0.014
0.996
0.006
0.998
0.002
Block GAT
0.881
0.017
0.116 + 0.035
0.114
0.041
UGAT
0.913 + 0.018
0.991 - 0.007
0.979 + 0.013
(c) Accuracy for the School experiment with data split 50/30/10/10.
Embedding
School
Trans.
Semi-ind.
Temp. Trans.
Block GCN
0.583 0.031
0.105 = 0.022
0.105 0.011
UGCN
0.918 + 0.026
0.897 = 0.022
0.939 = 0.009
Block GAT
0.543 0.030
0.106 = 0.025
0.111 0.010
UGAT
0.838 0.031
0.874 = 0.022
0.877 0.032
(f) Accuracy for the School experiment with data split 5/35/30/30.
Table Accuracy values (higher is better) for repeated runs of the School experiment with various data splits. Bold values indicate the highest accuracy for given GNN/representation pair.
22

---

Published as a conference paper at ICLR 2025
G REPEAT EXPERIMENTS USING DIFFERENT SCORE FUNCTIONS
Up to now, we have used adaptive prediction sets (APS) (Romano et al. 2020) to get our prediction sets. However, our theoretical results are not limited single choice of conformal procedure. To highlight this, we include experiments where we use the APS, RAPS (Angllopoulos et al. 2020 and SAPS (Hang et 2023) methods to compute prediction sets.
As both RAPS and SAPS require the choice of hyperparameter, we follow Huang et al. (2023) in holding out 20% of the calibration set to select the best hyperparameter for these methods. As the school dataset is the smallest real-world dataset considered in this work, we run these extra experiments on this dataset alone.
In almost all cases, both block GNN and UGNN achieve valid coverage in the two transductive regimes, with UGNN also mostly being valid in the semi-inductive regime.
Embedding
School
Trans.
Semi-ind.
Temp. Trans.
Block GCN
0.901 + 0.012
0,821 = 0.049
0.913 + 0.024
UGCN
0.901 0.012
0.889 + 0.020
0.902 0.016
Block GAT
0.901
0.012
0.665 = 0.097
0.922 = 0.027
UGAT
0.901 + 0.012
0.907 = 0.023
0.903 = 0.016
(a) Coverage for the School experiment using APS.
Embedding
School
Trans.
Semi-ind.
Temp. Trans.
Block GCN
0.902
0.013
0.821 + 0.049
0.915
0.027
UGCN
0.901 + 0.012
0.890 + 0.020
0.903
0.017
Block GAT
0.902
0.012
0.665
+ 0.096
0.921
0.029
UGAT
0.901
0.013
0.907 = 0.024
0.904
0.017
(b) Coverage for the School experiment using RAPS.
Embedding
School
Trans.
Semi-ind.
Temp. Trans.
Block GCN
0.891 + 0.014
0.817 = 0.050
0,226 + 0.018
UGCN
0.897
0.013
0.875 = 0.023
0.901 0.017
Block GAT
0.855
0.022
0.651 = 0.098
0.169 = 0.097
UGAT
0.895 0.017
0.900 + 0.025
0.898 0.020
Coverage for the School experiment using SAPS.
Table 10: Coverage values for of the School experiment using different conformal score functions.
Values in bold indicate valid coverage with target 2 0.90.
23

---

Published as a conference paper at ICLR 2025
Embedding
School
Trans.
Semi-ind.
Temp. Trans.
Block GCN
5.195 0.156
8.174 + 0.386
9.121 0.254
UGCN
3.541 0.314
2.714 + 0.326
3.719 0.239
Block GAT
4.367 + 0.798
6.567 + 0.897
9.124 0.310
UGAT
4.480 0.882
3.024 + 0.508
4.503 0.683
(a) Average set sizes for the School experiment using APS.
Embedding
School
Trans.
Semi-ind.
Temp. Trans.
Block GCN
5.205
0.169
8.766 + 0.393
9.135 0.273
UGCN
3.549 + 0.318
2.728 + 0.336
3.735 = 0.250
Block GAT
4.377
0.802
6.565 1 0.887
9.117
0.322
UGAT
4.486 + 0.891
3.029 + 0.501
4.516 = 0.696
(b) Average set sizes for the School experiment using RAPS.
Embedding
School Semi-ind.
Trans.
Temp. Trans.
Block GCN
5,044 0.162
8.130 + 0.400
1.972 0.030
UGCN
3,489
0.329
2.593 + 0.355
3.719 0.254
Block GAT
3.755 0.770
6.419 + 0.936
1.570 + 0.886
UGAT
4.451 0.954
2.982 + 0.519
4.483 0.740
(c) Average set sizes for the School experiment using SAPS.
Table 11: The average prediction set size for each method using APS, RAPS and SAPS on the school dataset. Values in bold indicate the smallest valid prediction set size for a given GNN architecture. Values in italics are the set sizes for invalid prediction sets.
H REPEAT EXPERIMENTS USING DIFFERENT GNNS
In section presented experiments using two of the most popular GNN architectures: GCN (Kipf and Welling, 2016) and GAT (Veličkovćć et al. (017). However, our theoretical results are not limited by the choice of GNN, long as that GNN meets assumption A2 (which is light). Below we repeat the school experiment using two different choices GNN: GraphS (Hamilton et al. 2017) and JKNet (Xu et al. 2018).
Similar to the results in the main text, we see that coverage remains valid under these GNNs. Further, see that the unfolded embeddings out-perform the block embeddings, both in terms of accuracy and prediction set size, in both the transductive and cami-inductive regimes.
24

---

Published as a conference paper at ICLR 2025
Embedding
School
Trans.
Semi-ind.
Block GraphSAGE
0.856 = 0.014
0.102 + 0.025
Unfolded GraphSAGE
0.932 0.006
0.917 = 0.009
Block JKNet
0.885
0.009
0.102 + 0.027
Unfolded JKNet
0.930 + 0.007
0.909 + 0.009
Accuracy. Bold values indicate higher accuracy.
Embedding
School
Trans.
Semi-ind.
Block GraphSAGE
0.900
0.012
0.869 1 0.072
Unfolded GraphSAGE
0.902 = 0.011
0.922 + 0.027
Block JKNet
0.901 + 0.012
0.897 + 0.028
Unfolded JKNet
0.901
0.012
0.907
0.027
(b) Coverage. Bold values indicate validity with target 2 0.90.
Embedding
School
Trans.
Semi-ind.
Block GraphSAGE
5,350 + 0.230
8.632 + 0.683
Unfolded GrephSAGE
3.879 0.978
3.194
0.659
Block JeN
4.724 + 0.332
8.946 + 0.189
Unfolded JKNet
2.566 = 0.292
2.472 + 0.477
(c) Average set size. Bold values indicate smaller set sizes.
Table 12: Repeated runs on the school dataset using GraphSAGE and JKNet as the choice of GNN.
25


Reviews:
[{"review_id": "KtO7Vu3nfW", "reviewer": "Reviewer_7kpc", "summary": "The purpose of this paper is to provide valid prediction sets (with finite sample guarantees) achieved through conformal prediction for GNNs on dynamic graphs. In this setting, the graph evolves through time and can thus be represented as a set of adjacency matrices\" nodes are fixed, but edges can appear and disappear at each time point. Each node is also endowed with a set of potentially varying features and labels.\n\nTo provide prediction sets (ie, sets of labels for each nodes such that the real label is within the set with, say, 95% probability), the authors suggest leveraging unfolding, a tool stemming from the tensor literature. The procedure they describe is as follows:\n- 1- create an unfolded adjacency by concatenating all the adjacency matrices (columnwise),  yielding a matrix of size 2nT  * 2nT. Same for the features: X_unf is of size nTp.\n- 2- apply a GNN on the unfolded adjacencies and features to output a set of global representations for each of the nodes (meaning, global across time points), and \"local\" representations (node/time pairs).\n- 3 -compute conformity scores to output prediction sets.\n\nThe authors  show that this procedure can help them get uncertainty estimates for 3 types of scenarios: transductive, timewise transductive, and semi-transductive.\nThe authors then proceed to show the results of numerous experiments (synthetic and on real data). More specifically, they use as benchmark a block GNN (GNN fitted on the block diagonal adjacency, essentially treating each snapshot as a different graph). The authors show that the block approach creates \"block\" effects when there should be none, and this also results in higher accuracy of the UGNNs over the block approach, and lower set sizes.", "questions": "My questions pertain the implementation of the method (see weaknesses).", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper proposes an interesting approach to uncertainty quantification in the context of dynamic graph. The method that they propose is new, but leverages existing methods in the GNN and conformal prediction literature.\n\nThe examples chosen by the authors are quite strong and compelling.", "weaknesses": "On the whole, I think this is a good paper, but perhaps a couple of modifications would clarify certain aspects:\n1- Some of the notations could be clarified. For instance, I found the part explaining the procedure a little confusing. More specifically:\n- $\\hat{X}^{UNF}$: since X is already used to describe features, another letter would be preferable here. I originally thought that it meant the unfolded features.\n- Similarly,  $\\hat{Y}^{UNF},$ I thought this meant the unfolded labels.\n- It would be great to add the dimensions (only  $\\hat{X}^{UNF}$ is indicated to have dimension $n_r \\times d$). \n- Would it be possible to replace $n_r$ by $n$? I personally find the subscript to be more justified to indicate a refinement, such as when, say, there would be different numbers of nodes across time points. I (personally) find that here, it invites more questions than would be necessary.\n\n2- the UGNN framework could be further detailed:\n- I am personally not familiar with the dilated unfolding approach of Davis, and consequently don't really understand the training procedure. $Y^{UNF}$ corresponds to the time-node pairs, so they should be trained with the node/pair labels?\n\n3- the current challenges in deploying CP to graphs could be clearer: it seems to me that the main contribution of the paper is the unfolding mechanism, that allows (a) better representation of nodes in embedding spaces, and that consequently (b)  lends itself well to UQ using CP. Maybe a reformulation of the introduction highlighting that some of the challenges in CP on graph embeddings would be a distribution shift of the embeddings if there is a batch effect could help highlight the contribution of the method. Currently, it is succintly mentioned (\"de-alignment between embeddings across time points\"), but I think this should be expanded upon to highlight current challenges and set the context a bit more clearly.", "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": "zr440lje0q", "reviewer": "Reviewer_bSGQ", "summary": "The authors established a novel conformal prediction method for dynamic GNNs, where edges evolve over time, like transport and social networks. The primary contributions are as follows:\n\n1. Dynamic Graph Representation for GNNs: an \"unfolding\" technique for representations of dynamic graphs has been proposed to achieve reliable prediction sets, compared to the original block representations.\n\n2. Inference Scenarios: The authors fully discussed various inference scenarios specific to dynamic graphs, including transductive, temporal transductive, and semi-inductive regimes, with valid and reasonable assumptions if needed.\n\n3. Empirical Validation and Practical Applications: Using several real-world datasets as well as simulated data, the proposed method demonstrates improved metrics over baseline approaches, with particular advantages in the semi-inductive case, showing great potential in analyzing various dynamic graph systems.", "questions": "Besides several concerns that mentioned in the weakness part, here are several questions regarding the paper details:\n\nLine 88: why requires a bipartite graph? Needs to explain.\n\nLines 161-165: for better understanding, I would prefer the authors directly used $m$ over $m + 1$ (surely some other formula like \nAlgorithm 1 also needs to be changed). But this is more neat.\n\nLine 165: it is not encouraged to mix superscripts and subscripts in notation, especially when they share the same meanings (e.g. test pairs and calibration pairs).\n\nLine 179: do we have any differences if we use row- rather than column-concatenation? I guess they might be the same. Please think about this.\n\nLine 222: does column swapping means permutation? For example, is it equivalent to say, there exists a permutation matrix $P$. such that $PA^{UNF}P^T=A^{UNF, swapped}$?\n\nSection 2.1 and Figure 1: If you can plot $A^{(1)}$ as a 2D heatmap, or the original graph using tools like networkx package, it will be better for illustration rather than just representation scatter plots. For example, the density of nodes or the color of heatmap may clear show what happened in this toy system.\n\nFigure 2: needs a short comment on SBM evolving edges. Why is that?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Originality: One innovation in this paper is introducing the “unfolded” dynamic graph representation, which allows standard GNNs to process dynamic graphs while maintaining the validity of CP techniques. Additionally, the paper extends CP applications to multiple dynamic graph inference cases, for example, semi-inductive regimes, which is pretty challenging in discovering missing labels.\n\n2. Quality and Clarity: The authors provided clean and rigorous theoretical analysis in explaining how its method achieves valid predictions under varied dynamic settings, supported by well-defined assumptions and conditions for applicability in different inference scenarios. Visualizations like bar graphs and tables further help readers understand the reasonableness and benefits of the unfolded approach compared to the baseline. \n\n3. Significance: The paper addresses an important issue in uncertainty quantification for dynamic GNNs, where given reasonable prediction intervals over time is essential. The basic idea for this approach seems to have great potential for scaling up, therefore advancing the applicability of GNNs with evolving edges.", "weaknesses": "1. Semi-Inductive Settings:\n\nAs the authors acknowledged, the assumption of exchangeability may not hold in many real-world cases, necessary discussions for mitigating it would be appreciated. For instance, if adapting robust techniques from time-series, like basic ARIMAs, or even neural SDEs might be useful. \n\n2. Understanding UQ:\n\nThough I acknowledged the authors’ efforts in providing extensive metrics, it would be insightful to how to interpret the size of prediction sets correlates with meaningful uncertainty in a dynamic graph. This could help researchers from other backgrounds understand the logic, and make benefits for them. Making a plot showing the coverage (if possible) will make the paper more solid.\n\n3. Miscellaneous:\n\nI suggested the reviewers consider the following issues, and if time allows, do some elaboration.\n\na) If there is any other way to reshape the dynamic graph from $(T, N, N)$ into a 2D-shape, e.g. compared the performance the reshaped matrix in shape $(T, N^2)$.\n\nb) Another simplification on the current $A^{UHF}$ might be: $A^{(1)}$ at top left, and the remaining unfolded $\\mathcal{A}$ dilated in the same way. I would consider if this will somehow reduce the complexity, especially when $T << N$.\n\nc) In this paper the dynamical graphs always mean edge-evolving ones. There are also cases where nodes are evolving with time, or even both edges and nodes are changing, e.g. pandemic networks (with different types of nodes, and some nodes will disappear permanently). It is appreciated if authors can do some brainstorming on this topic to provide meaningful improvements.", "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": "Jnd5IqlPHK", "reviewer": "Reviewer_X1HP", "summary": "This paper works on applying conformal prediction on dynamic graphs. The key contribution of this paper is introducing a careful mathematical consideration of different inferences in modeling dynamic graphs. Valid conformal predictions are obtained in most of the scenarios and the authors provide real data examples to prove the theory.", "questions": "1. This question is similar to the concerns in the weakness. Do you have more experimental results on other backbones?\n2. What is the current state-of-the-art algorithm applying conformal prediction on dynamic graphs or even static graphs? The authors should include more competitive baseline methods.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "It is interesting to use block GCN to prove the validity of applying conformal prediction on dynamic graphs. The authors provide detailed and sufficient explanations and analysis on different scenarios on dynamic graph tasks. Besides, the authors provide a variety of real data examples to show the effectiveness of their theory. The paper is well-written and organized.", "weaknesses": "This paper aims to apply conformal prediction to dynamic graphs. It should include more competitive baselines that use conformal predictions on graphs. And the backbone models should be more rather than simply using GCN and GAT.", "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": "ijb60U0RbF", "reviewer": "Reviewer_wToC", "summary": "This paper focuses on dynamic graphs. More specifically, utilizing the tool of dilated unfolding, this paper expands the traditional GNN to dynamic graphs. No modification to GNN structure is required.", "questions": "Could you confirm your algorithm is by combining dilated unfolding (Davis '23) and a GNN? If that is the only contribution, could you please convince me there is enough innovation provided?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 1, "strengths": "For a sequence of graphs, the paper cleverly utilizes dilated unfolding to make it a sparse matrix $A^{UNF}$. In the semi-inductive regime, the paper shows a proof guarantee of the algorithm. A comparison with the standard block GNN is provided in Sec 2.1 and clearly shows this advantage. Experiments in Sec 3.2 also support this.", "weaknesses": "I am not an expert in GNN, so please tell me if I am incorrect. It seems the innovation in this paper is incremental because dilated unfolding is known in Davis '23. The theoretical contributions (the proof in Sec. B.1 and B.2) also seem natural.", "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": "dJj5RQ5n4J", "reviewer": "Reviewer_69Z2", "summary": "The paper studies uncertainty prediction for dynamic graphs. For the representation learning of dynamic graphs, the paper leverages the unfolded adjacency matrix as input to GNNs and for uncertainty prediction, the paper follows procedures of conformal prediction that constructs provably valid prediction sets.", "questions": "1. In A2, is label equivariant the same as permutation equivariant?\n\n2. In section 2.1, can you formally prove the exchangebility of UGCN while BD GCN does not satisfy the exchangebiity?\n\n3. Why Algorithm 1 is present in the main paper but Algorithm 2 is used for experiments?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper studies an important problem relating to uncertainty quantification for GNN prediction. \n\n2. The use of unfolded adjacency for GNNs on dynamics graphs is natural and promising. \n\n3. The experiments show promise for the proposed method.", "weaknesses": "1. The paper is poorly written with many concepts and notations not sufficiently explained. In addition, the structure of the paper needs to be improved. For example, (1) in line 161, it is not clear what it means for 'appropriate ordering of pairs', and what does m here represent? (It is better add some examples) (2) What is the intuition of using dilated unfolding in line 176? How does line 181-185 work? It would be clearer if the explicit update form is written under the example of GCN. (3) Algorithm 1 is introduced with no explanations on the steps. For example, what is a calibration set? (4) In theory, the key definitions, such as exchanebility and label equivariant are deferred to appendix, which is not ideal.  \n\n2. The developments are disconnected and it is thus not clear what are the key contributions of this work. The paper claims the contribution as a novel interface between conformal prediction and GNN. However, from the present version of the paper, it seems straightforward to combine the two to form conformal prediction on graphs. The consideration of dynamic graphs in this paper is novel but the use of unfolded adjacency has been considered previously for spectral embedding. \n\n3. The scalability with the use of unfolded adj is poor.", "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)