Valid Conformal Prediction for Dynamic GNNs

## Abstract

Abstract Graph neural networks (GNNs) are powerful black-box models which have shown impressive empirical performance. However, without any form of uncertainty quantification, it can be difficult to trust such models in high-risk scenarios. Conformal prediction aims to address this problem, however, an assumption of exchangeability is required for its validity which has limited its applicability to static graphs and transductive regimes. We propose to use unfolding, which allows any existing static GNN to output a dynamic graph embedding with exchangeability properties. Using this, we extend the validity of conformal prediction to dynamic GNNs in both transductive and semi-inductive regimes. We provide a theoretical guarantee of valid conformal prediction in these cases and demonstrate the empirical validity, as well as the performance gains, of unfolded GNNs against standard GNN architectures on both simulated and real datasets.

## 1 Introduction

Graph neural networks (GNNs) have seen formidable success in a wide variety of application domains including prediction of protein structure [] and molecular properties [, ], drug discovery [], computer vision [], natural language processing [, ], recommendation systems [, , ], estimating time of arrival (ETA) in services like Google Maps [], and advancing mathematics []. They often top leaderboards in benchmarks relating to machine-learning on graphs [], for a range of tasks such as node, edge, or graph property prediction. Useful resources for getting started with GNNs include the introductions [, ] and the Pytorch Geometric library [].

Conformal prediction, advanced by Vovk and co-authors [], and later expanded on by various researchers in the Statistics community [, , , , , , , , ], is an increasingly popular paradigm for constructing provably valid prediction sets from a ‘black-box’ algorithm with minimal assumptions and at low cost. Several recent papers have brought this idea to quantifying uncertainty in GNNs [, , ].

There are many applications of significant societal importance, e.g. cyber-security [, , ], human-trafficking prevention [, ], social media & misinformation [], contact-tracing [], patient care [, ] where we would like to be able to use GNNs, with uncertainty quantification, on 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 Figure 1), resulting in large or invalid prediction sets in even simple and stable dynamic regimes.

Inspired by a concurrent line of statistical research on spectral embedding and tensor decomposition [, , , , , , ], we propose to use one of the *unfoldings* [] 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 only paper we found studying conformal inference on dynamic graphs is [], but the paper considers a strictly growing graph, which is not what we mean by a ‘dynamic graph’, where edges appear and disappear in complex and random ways, as in all of our examples and applications alluded to above. Our work naturally builds on earlier contributions combining GNNs and conformal inference [, , ] but our theory is distinct from those contributions, with arguments closer to [], and the use of unfoldings for GNNs is new. In the dynamic graph literature, unfoldings have exclusively been proposed for unsupervised settings [, , , , ], particularly spectral embedding, and have never been applied to conformal inference.

## 2 Theory & Methods

Problem setup. In this paper, a dynamic graph $G$ is a sequence of $T$ graphs over a globally defined nodeset $[n]=\{1,\ldots,n\}$, represented by adjacency matrices $\mathbf{A}^{(1)},\ldots,\mathbf{A}^{(T)}$. It may help to assume the $\mathbf{A}^{(t)}$ are $n\times n$ binary symmetric matrices corresponding to undirected graphs, but in fact all we require is that the $\mathbf{A}^{(t)}$ have the same number of rows, $n_{r}$, allowing for directed, bipartite and weighted graphs.

Along with the dynamic graph $G$, we are given labels for certain nodes at certain points in time, which could describe a state or behaviour. Our task is to 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 $1-\alpha$ (e.g. 95%).

We track the labelled and unlabelled pairs in this problem using a fixed sequence $\nu$ where for each $(i,t)\in\nu$ we assume existence of

- 1.
a class label $Y^{(t)}_{i}\in\mathcal{Y}$, which may or may not be observed, where $\mathcal{Y}$ is some discrete set of cardinality $d$;
- 2.
a set of attributes, which is observed, and represented by a feature vector $X^{(t)}_{i}\in\mathbb{R}^{p}$;
- 3.
a corresponding column in $\mathbf{A}^{(t)}$, denoted $\mathbf{A}^{(t)}_{i}$.

For a pair $w=(i,t)\in\nu$, we will use the notation $X_{w}\coloneqq X^{(t)}_{i}$, $Y_{w}\coloneqq Y^{(t)}_{i}$, $\mathbf{A}_{w}\coloneqq\mathbf{A}^{(t)}_{i}$.

Transductive regime. For some $m<|\nu|$, the missing label is missing completely at random among the first $m+1$ node/time pairs of $\nu$.
Semi-inductive regime. For some $m<|\nu|$, the missing label corresponds to a fixed pair among the first $m+1$ node/time pairs of $\nu$.

Let $\nu_{\text{test}}$ denote the missing node/time pair, $\nu^{(\text{training})}\coloneqq\{\nu_{\ell},\ell>m+1\}$, and $\nu^{(\text{calibration})}\coloneqq\{\nu_{\ell},\ell\leq m+1\}\setminus\{\nu_{
\text{test}}\}$.

In the transductive regime, a valid confidence set can be constructed with no further assumptions (Algorithm 1). This may seem surprising and could be very useful in view of the following implication: the pairs $\nu^{(\text{training})}$ can correspond to historical datapoints, at times $t<T$, and the pairs $\{\nu_{\text{test}}\}\cup\nu^{(\text{calibration})}$ can correspond to datapoints in the present, $T$. We only need the missing label to be uniformly chosen *among the labels at time $T$*. The semi-inductive regime is more challenging, and could reflect a scenario where we have only historical labels. Here, we will need to invoke further assumptions such as symmetry and exchangeability, familiar in the conformal prediction literature.

Proposed approach. We will repurpose a standard GNN, designed for static graphs, into producing dynamic graph embeddings with desirable exchangeability properties. Let $\mathcal{G}$ denote a GNN taking as input an adjacency matrix $\mathbf{A}$ corresponding to an undirected graph on $N$ nodes, along with node attributes and labels (some missing), and returning an *embedding* $\hat{\mathbf{Y}}\in\mathbb{R}^{N\times d}$. Typically, the $i$th row of $\hat{\mathbf{Y}}$ predicts the label of node $i$ through

$$ $\hat{\mathbb{P}}(\text{node $i$ has label $k$})=\left[\text{softmax}(\hat{ \mathbf{Y}}_{i1},\ldots,\hat{\mathbf{Y}}_{id})\right]_{k}.$ $$

In place of this generic input $\mathbf{A}$, we will enter the dilated unfolding [] corresponding to the dynamic graph $G$,

$$ $\mathbf{A}^{\text{UNF}}\coloneqq\begin{bmatrix}\mathbf{0}&\mathbfcal{A}\\ \mathbfcal{A}^{\top}&\mathbf{0}\end{bmatrix},$ $$

where $\mathbfcal{A}=\left(\mathbf{A}^{(1)},\dots,\mathbf{A}^{(T)}\right)$ (column-concatenation), along with the attributes $X_{w},w\in\nu$ and training labels $Y_{w},w\in\nu^{(\text{training})}$.

The resulting output from the GNN splits into embeddings

$$ $\begin{bmatrix}\hat{\mathbf{X}}^{\text{UNF}}\\ \hat{\mathbf{Y}}^{\text{UNF}}\end{bmatrix}\coloneqq\mathbfcal{G}\left(\mathbf{ A}^{\text{UNF}}\right),$ $$

where $\hat{\mathbf{X}}^{\text{UNF}}\in\mathbb{R}^{n_{r}\times d}$ contains global representations. The embedding $\hat{\mathbf{Y}}^{\text{UNF}}$ contains representations of node/time pairs, of principal interest here, and we let $\hat{\mathbf{Y}}^{\text{UNF}}_{w}$ denote the row representing node/pair $w\in\nu$.

Finally, we shall require some non-conformity score function $r:\mathbb{R}^{d}\times\mathcal{Y}\rightarrow\mathbb{R}$, with the convention that $r(\hat{y},y)$ is large when $\hat{y}$ is a poor prediction of $y$. In practice, we make use of the adaptive non-conformity measures detailed by [].

With these ingredients in place, we are in a position to obtain a prediction set $\hat{C}$ for $\nu_{\text{test}}$, the computation of which is detailed in Algorithm 1. The notation leaves implicit the dependence of the set $\hat{C}$ on the observed data; explicitly, the set $\hat{C}$ is a deterministic function of the dynamic graph $G$, the attributes $(X_{w},w\in\nu)$, and the labels $(Y_{w},w\in\nu\setminus\{\nu_{\text{test}}\})$.

Figure: Algorithm 1 Split conformal inference

Theory. As mentioned earlier, the transductive regime requires no further assumptions.

###### Lemma 1 .

In the transductive regime, the prediction set output by Algorithm 1 is valid, that is,

$$ $\mathbb{P}(Y_{\nu_{\text{\rm test}}}\in\hat{C})\geq 1-\alpha.$ $$

Let $\nu^{+}_{\text{calibration}}=(\nu_{\ell},\ell\in[m+1])$, comprising $\nu_{\text{calibration}}$ and $\nu_{\text{test}}$. For the semi-inductive regime, we make the following assumptions:

###### A1 .

The columns $\mathbf{A}_{w}$, attributes $X_{w}$, and labels $Y_{w}$ corresponding to $w\in\nu^{+}_{\text{\rm calibration}}$ are jointly exchangeable.

We make the definition of exchangeability precise in the supplementary material. Informally, we can swap columns of $\mathcal{A}=\left(\mathbf{A}^{(1)},\dots,\mathbf{A}^{(T)}\right)$ corresponding to test or calibration pairs, along with the attributes and labels, without changing the likelihood of the data.

###### A2 .

The GNN $\mathcal{G}$ is label equivariant.

This definition is again made precise in the supplementary material. Informally, if we re-order the nodes, attributes and labels, we re-order the resulting embedding.

###### Theorem 1 .

Under assumptions 1 and 2, the prediction set output by Algorithm 1 is valid in the semi-inductive regime, that is,

$$ $\mathbb{P}(Y_{\nu_{\text{\rm test}}}\in\hat{C})\geq 1-\alpha.$ $$

Discussion. Assumption 2 is relatively mild and roughly satisfied by standard GNN architectures. Assumption 1 is more challenging, and can guide us towards curating a calibration set. For example, if we hypothesise that the $(\mathbf{A}^{(t)}_{i},t\in[T])$ are i.i.d. stationary stochastic processes (over time), then we can satisfy Assumption 1 by ensuring $\nu^{+}_{\text{calibration}}$ contains only distinct nodes. The independence hypothesis will typically break in undirected graphs because of the necessary symmetry of each $\mathbf{A}^{(t)}$, and in this case we may also wish to ensure that $\nu^{+}_{\text{calibration}}$ contains only distinct time points. In general, for predicting the label of nodes based on historical information, Assumption 1 should make us wary of global drift, a poor distributional overlap between the test and calibration nodes, and autocorrelation. The semi-inductive regime is where our theory actively requires a 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.

###### Lemma 1 .

###### A1 .

###### A2 .

###### Theorem 1 .

### 2.1 A Visual Motivation: i.i.d. Draws of a Stochastic Block Model

Consider a simple two-community dynamic stochastic block model (DSBM) [, ] for undirected graphs. Let

$$ $\mathbf{B}^{(1)}=\mathbf{B}^{(2)}=\begin{bmatrix}0.5&0.5\\ 0.5&0.9\end{bmatrix},$ (1) $$

be matrices of inter-community edge probabilities, and let $\tau\in\{1,2\}^{n}$ be a community allocation vector. We then draw each symmetric adjacency matrix point as $\mathbf{A}_{ij}^{(1)}\overset{\text{ind}}{\sim}\text{Bernoulli}(\mathbf{B}_{
\tau_{i},\tau_{j}}^{(1)})$ and $\mathbf{A}_{ij}^{(2)}\overset{\text{ind}}{\sim}\text{Bernoulli}(\mathbf{B}_{
\tau_{i},\tau_{j}}^{(2)}$), for $i\leq j$.

A typical way of applying a GNN to a series of graphs is to first stack the adjacency matrices as blocks on the diagonal [],

$$ $\mathbf{A}^{\text{BD}}=\begin{bmatrix}\mathbf{A}^{(1)}&&\mathbf{0}\\ &\ddots&\\ \mathbf{0}&&\mathbf{A}^{(T)}\end{bmatrix},$ $$

from which a dynamic graph embedding is obtained through

$$ $\hat{\mathbf{Y}}_{\text{BD}}=\mathcal{G}\left(\mathbf{A}^{\text{BD}}\right).$ $$

Figure 1 plots the representations, $\hat{\mathbf{Y}}_{\text{BD}}$ and $\hat{\mathbf{Y}}_{\text{UNF}}$ of $\mathbf{A}^{(1)},\mathbf{A}^{(2)}$ using a GCN [] as $\mathcal{G}$. It is clear that, despite the fact that $\mathbf{A}^{(1)}$ and $\mathbf{A}^{(2)}$ come from the same distribution, the output of the block diagonal GCN appears to encode a change that is not present. We refer to this issue as temporal shift. In contrast, the output of UGCN is exchangeable over time and so features no temporal shift.

Figure: Figure 1: UGCN and block diagonal GCN representations of an i.i.d. stochastic block model after applying PCA. The models were trained with transductive masks. Block diagonal GCN appears to encode a significant change over time despite there being none. The embedding from UGCN is exchangeable over time, as would be expected.
Refer to caption: extracted/5615723/general_figs/iid_sbm_ugcn_block_gcn_trans.png

This example highlights two advantages of unfolded GNN over the standard GNN case. First, as there is no temporal shift, we would expect it 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 1. We will then delve deeper into a particular dataset to show how variation in 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.

SBM. A three-community DSBM with inter-community edge probability matrix

$$ $\mathbf{B}^{(t)}=\begin{bmatrix}s_{1}&0.02&0.02\\ 0.02&s_{2}&0.02\\ 0.02&0.02&s_{3}\end{bmatrix},$ $$

where $s_{1}$, $s_{2}$, and $s_{3}$ represent within-community connection states. Each $s$ can be one of two values: 0.08 or 0.16. We simulate a dynamic network over $T=8$ time points, corresponding to the $8=2^{3}$ possible combinations, drawing each $\mathbf{A}^{(t)}$ from each unique $\mathbf{B}^{(t)}$ as detailed in Section 2.1. The task is to predict the community label of each node.

Figure: 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.
Refer to caption: x1.png

School. A dynamic social network between pupils at a primary school in Lyon, France []. Each of the 232 pupils wore a radio identification device such that each interaction, with its timestamp, could be recorded, forming a dynamic network. An interaction was 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 to the end of 2021 []. The task is to predict the country of a given (European only) airport. The network exhibits seasonal and periodic patterns, and features a change in structure when the COVID-19 pandemic hit Europe around March 2020.

Trade. An agricultural trade network between members of the United Nations tracked yearly between 1986 and 2016 [], which features in the Temporal Graph Benchmark []. 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 is visualised in Figure 2. We consider the goal of predicting the top trade partner for each nation for the next year, a slight deviation from the benchmark where performance is quantified by the Normalized Discounted Cumulative Gain of the top 10 ranked trade partners (less naturally converted into a conformal prediction problem).

**Table 1: A summary of considered datasets.**
| Dataset | Nodes | Edges | Time points | Classes | Weighted | Directed | Drift |
| --- | --- | --- | --- | --- | --- | --- | --- |
| SBM | 300 | 38,350 | 8 | 3 | No | No | No |
| School | 232 | 53,172 | 18 | 10 | No | No | No |
| Flight | 2,646 | 1,635,070 | 36 | 46 | Yes | No | No |
| Trade | 255 | 468,245 | 32 | 163 | Yes | Yes | Yes |

### 3.1 Experimental Setup

On each dataset, we apply GCN [] and GAT [] 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 not 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 to the high computational cost of fitting multiple GNNs to quantify randomisation error, we follow [] 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 an 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 are then picked at random, regardless of time point label, from the remaining data with ratios 20/10/35. As the test set is fixed, efficiency saving is not possible and we instead run Algorithm 1 (split conformal) on 50 random data splits.

Prediction sets are computed using the Adaptive Prediction Sets (APS) algorithm [] 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. We additionally consider an empirical evaluation of conditional coverage, which is desirable but known to be theoretically impossible to guarantee []. We empirically estimate this property by returning the worst-case coverage across time for each of our examples [].

Code to reproduce 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 a more significant advantage (Table 2). Block GNN is close to random guessing in the semi-inductive SBM and School examples (having 3 and 10 classes respectively). In contrast, UGNN maintains a strong accuracy in both regimes.

**Table 2: Accuracy (higher is better) for 2 GNNs (GCN or GAT) under 2 representations (block diagonal adjacency or unfolding) for 4 datasets. Bold values indicate the highest accuracy for a given GNN/representation pair.**
| Methods | SBM | School |  |  |
| --- | --- | --- | --- | --- |
|  | Trans. | Semi-ind. | Trans. | Semi-ind. |
| Block GCN | 0.964 $\pm$ 0.011 | 0.334 $\pm$ 0.024 | 0.856 $\pm$ 0.011 | 0.116 $\pm$ 0.011 |
| UGCN | 0.980 $\pm$ 0.004 | 0.985 $\pm$ 0.003 | 0.924 $\pm$ 0.009 | 0.915 $\pm$ 0.013 |
| Block GAT | 0.916 $\pm$ 0.028 | 0.346 $\pm$ 0.024 | 0.807 $\pm$ 0.016 | 0.107 $\pm$ 0.024 |
| UGAT | 0.947 $\pm$ 0.032 | 0.969 $\pm$ 0.017 | 0.896 $\pm$ 0.016 | 0.868 $\pm$ 0.017 |

Conformal prediction on UGNN and block GNN is empirically valid for every transductive example. This confirms (Lemma 1) that exchangeability/label equivariance are not necessary for valid conformal prediction in the transductive regime, as even block GNN (which has no exchangeability properties) is valid here (Table 3). However, UGNN achieves valid coverage with smaller prediction sets in most cases, making it the preferable method (Table 4).

**Table 3: Coverage (targetted to $\geq 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 $\geq 0.9$.**
| Methods | SBM | School |  |  |
| --- | --- | --- | --- | --- |
|  | Trans. | Semi-ind. | Trans. | Semi-ind. |
| Block GCN | 0.901 $\pm$ 0.014 | 0.659 $\pm$ 0.045 | 0.901 $\pm$ 0.012 | 0.812 $\pm$ 0.033 |
| UGCN | 0.901 $\pm$ 0.015 | 0.918 $\pm$ 0.025 | 0.901 $\pm$ 0.012 | 0.924 $\pm$ 0.013 |
| Block GAT | 0.901 $\pm$ 0.015 | 0.450 $\pm$ 0.154 | 0.901 $\pm$ 0.012 | 0.662 $\pm$ 0.084 |
| UGAT | 0.901 $\pm$ 0.014 | 0.914 $\pm$ 0.022 | 0.901 $\pm$ 0.012 | 0.909 $\pm$ 0.021 |

Conformal prediction on UGNN is empirically valid for every semi-inductive example without drift, while block GNN is valid for none. In all examples, except for the trade dataset, UGNN produces valid conformal (Table 3) 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 to the drift present in the trade network (Figure 2), which 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.

Neither method achieves conditional coverage. In Appendix C we show that (as anticipated), the worst-case conditional coverage across all time points for both methods is less than the target coverage, both for block and unfolded matrices and both for GCN and GATs. In most semi-inductive regimes, UGNN is closer to this target, but they perform similarly in the transductive regime here.

The problems of drift and conditional coverage are difficult to handle inside an unfolded GNN, but we hypothesise that downstream methods could be applied to improve coverage in these cases, for example [] and []. 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 a minute on an AMD Ryzen 5 3600 CPU processor. A full run of experiments on the largest dataset took around 4.5 hours.

**Table 4: Set sizes (lower is better) for 2 GNNs (GCN or GAT) under 2 representations (block adjacency or Unfolding) for 4 datasets. Values in bold indicate a smaller set size for a given GNN. Values in italics indicate invalid sets.**
| Methods | SBM | School |  |  |
| --- | --- | --- | --- | --- |
|  | Trans. | Semi-ind. | Trans. | Semi-ind. |
| Block GCN | 1.258 $\pm$ 0.053 | 1.977 $\pm$ 0.138 | 4.542 $\pm$ 0.167 | 8.079 $\pm$ 0.188 |
| UGCN | 1.263 $\pm$ 0.206 | 1.097 $\pm$ 0.171 | 2.763 $\pm$ 0.311 | 3.037 $\pm$ 0.251 |
| Block GAT | 1.063 $\pm$ 0.180 | 1.320 $\pm$ 0.466 | 3.863 $\pm$ 0.813 | 6.540 $\pm$ 0.830 |
| UGAT | 1.053 $\pm$ 0.249 | 1.042 $\pm$ 0.201 | 3.552 $\pm$ 0.756 | 4.185 $\pm$ 1.228 |

### 3.3 Temporal Analysis

The goal of conformal prediction is to provide a notion of uncertainty to an otherwise black-box model. As a problem becomes more difficult, this should be reflected in a larger prediction set size to maintain target coverage. We analyse this behaviour by focusing on the school data example.

Figure 3 compares accuracy of both UGAT and block GAT for each time window of the school dataset. During lunchtime, pupils are no longer clustered in their classrooms, making prediction of their class more difficult. Figure 3 confirms a significant drop in accuracy for both models at lunchtime in the transductive case. UGAT also displays this behaviour in the semi-inductive case, 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 4. UGAT also displays this increase in the semi-inductive regime, while block GAT does not adapt. This demonstrates that conformal prediction can quantify classification difficulty over time when using a UGNN. Note that while computing accuracy requires the knowledge of test labels to quantify difficulty, conformal prediction of set size does not. In this particular example, both methods maintain coverage in the transductive case (increasing uncertainty at lunchtimes), and UGAT maintains coverage in the semi-inductive case. The story is similar for UGCN (Appendix D).

Figure: (a) Transductive.
Refer to caption: x2.png

Figure: (a) Transductive.
Refer to caption: x4.png

Figure: (a) Transductive.
Refer to caption: x6.png

## 4 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 a range of simulated and real data examples.

As the supplied code will demonstrate, we have intentionally avoided any type of fine-tuning, because the goal here is less prediction accuracy than uncertainty quantification. There are significant opportunities to improve the prediction performance of unfolded GNNs, such as employing architectures better suited to bipartite graphs.

There are also opportunities to improve the downstream treatment of embeddings, such as deploying the CF-GNN algorithm [] to reduce prediction set sizes, or weighting calibration points according to their exchangeability with the test point [, ].

Our use of unfolding originates from a 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 a projection operator which can be applied to new nodes. Being able to somehow emulate this operation in unfolded GNNs could provide a path towards fully inductive inference.

## Appendix A Code availability

Python code for reproducing experiments is available at [https://github.com/edwarddavis1/valid_conformal_for_dynamic_gnn](https://github.com/edwarddavis1/valid_conformal_for_dynamic_gnn).

## Appendix B Supporting theory for Section 2

### B.1 Transductive theory

Our arguments are similar in style to [], showing validity of full conformal inference, and then split conformal as a special case of full conformal.

We observe $Y_{w}$ for all $w\in\nu$ apart from $Y_{\nu_{K}}$, where the query point $K$ is chosen independently and uniformly at random among $\{1,\ldots,m+1\}$.

#### B.1.1 Full conformal prediction

Suppose we have access to an algorithm $\mathcal{A}(g,x,y)$ which takes as input:

- 1.
$g$, a dynamic graph on $n$ nodes and $T$ time points;
- 2.
$x$, a $|\nu|$-long sequence of feature vectors;
- 3.
$y$, a $|\nu|$-long sequence of labels;

and returns a sequence $r=(r_{1},\ldots,r_{m+1})$ of real values, which will act as non-conformity scores.

Figure: Algorithm 2 Full conformal inference

###### Lemma 2 .

The prediction set output by Algorithm 2 is valid.

###### Proof.

Because $K\overset{ind}{\sim}\text{uniform}([m+1])$, the event

$$ $E=\text{``$R_{K}$ among $\lfloor\alpha(m+1)\rfloor$ largest of $R_{1},\ldots,R _{m+1}$''},$ $$

occurs with probability

$$ $\mathbb{P}(E)\leq\alpha.$ $$

But $E$ occurs if and only if $Y_{\nu_{K}}\not\in\hat{C}$. Therefore,

$$ $\mathbb{P}(Y_{\nu_{K}}\in\hat{C})=1-\mathbb{P}(Y_{\nu_{K}}\not\in\hat{C})=1- \mathbb{P}(E)\geq 1-\alpha.$ $$

∎

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 $\mathcal{A}$ (neither of which were assumed).

###### Lemma 2 .

###### Proof.

#### B.1.2 Split conformal prediction

Figure: Algorithm 3 Split conformal inference (abstract version)

Suppose we construct $\mathcal{A}$ according to a split training/calibration routine, as follows. First, using $g$, $\nu$, the feature vectors $(X_{w},w\in\nu)$, and the labels $Y_{\nu_{\ell}},\ell>m+1$, learn a prediction function $\hat{f}:\nu\rightarrow\mathbb{R}^{d}$.

The vector $\hat{f}(\nu_{\ell})$ might, for example, relate to predicted class probabilities via

$$ $\hat{\mathbb{P}}(Y_{\nu_{\ell}}=k)=\left[\text{softmax}(\hat{f}(\nu_{\ell})_{1 },\ldots,\hat{f}(\nu_{\ell})_{d})\right]_{k},$ $$

in which case $\hat{f}(\nu_{\ell})$ is often known as an embedding.

Second, for a non-conformity function $r:\mathbb{R}^{d}\times\mathcal{Y}\rightarrow\mathbb{R}$, a dynamic graph $g$, and $x,y$ of length $|\nu|$, define

$$ $\left[\mathcal{A}(g,x,y)\right]_{\ell}=r(\hat{f}(\nu_{\ell}),y_{\ell}),\quad \ell\in[m+1].$ $$

Then Algorithm 2 can potentially be made much more efficient, as shown in Algorithm 1. This is nothing but the usual split conformal inference algorithm, where the labels $Y_{\nu_{\ell}},\ell>m+1$ are being used for training, and $Y_{\nu_{\ell}},\ell\in[m+1]\setminus K$ for calibration.

Thus split conformal inference is a special case of full conformal inference, in which special structure is imposed on $\mathcal{A}$, and must therefore inherit its general validity (Lemma 1).

### B.2 Semi-inductive theory

Otherwise keeping the same setup, suppose $K$ is not uniformly chosen but is instead fixed, to (say) $K=1$.

Given a permutation $\pi:[m+1]\rightarrow[m+1]$, we will write $\pi G$ to denote a dynamic graph in which the columns of $G$ corresponding to $\nu_{1},\ldots,\nu_{m+1}$ are permuted according to $\pi$. More precisely, $\pi G$ is the dynamic graph corresponding to the sequence of adjacency matrices $\mathbf{A}^{(1)^{\prime}},\ldots,\mathbf{A}^{(T)^{\prime}}$ obtained as follows. First, copy $\mathbf{A}^{(1)},\ldots,\mathbf{A}^{(T)}$ to $\mathbf{A}^{(1)^{\prime}},\ldots,\mathbf{A}^{(T)^{\prime}}$. Next, overwrite any column $\nu_{\ell}\in\nu_{1},\ldots,\nu_{m+1}$ to $\mathbf{A}^{\prime}_{\nu_{\ell}}=\mathbf{A}_{\nu_{\pi^{-1}(\ell)}}$. If $x$ is a sequence of length at least $m+1$, we write $\pi x$ to denote the same sequence with its first $m+1$ elements permuted according to $\pi$, that is, $(\pi x)_{\ell}=x_{\pi^{-1}(\ell)}$ if $\ell\leq m+1$ and $(\pi x)_{\ell}=x_{\ell}$ otherwise.

A more fully stated version of Assumption 1 is

###### A3 .

The columns $\mathbf{A}_{w},w\in\nu$, attributes $X_{w},w\in\nu$, and labels $Y_{w},w\in\nu$ are jointly exchangeable, that is, for any permutation $\pi:[m+1]\rightarrow[m+1]$,

$$ $\left\{\pi G,\pi(X_{w},w\in\nu),\pi(Y_{w},w\in\nu)\right\}\triangleq\left\{G,( X_{w},w\in\nu),(Y_{w},w\in\nu)\right\}.$ $$

The symbol $\triangleq$ means “equal in distribution”.

###### A4 .

The algorithm $\mathcal{A}(g,x,y)$ is symmetric in its input. For any permutation $\pi:\nu\rightarrow\nu$,

$$ $\mathcal{A}(\pi g,\pi x,\pi y)=\pi\mathcal{A}(g,x,y)$ $$

###### Theorem 2 .

Under assumptions 3 and 4, the prediction set output by Algorithm 2 (and so Algorithm 3) is valid even if $K=1$ deterministically.

###### Proof.

The combination of assumptions 3 and 4 ensures that $R_{1},\ldots,R_{m+1}$ are exchangeable, and therefore the event

$$ $E=\text{``$R_{1}$ among $\lfloor\alpha(m+1)\rfloor$ largest of $R_{1},\ldots,R _{m+1}$''},$ $$

occurs with probability

$$ $\mathbb{P}(E)\leq\alpha.$ $$

But $E$ occurs if and only if $Y_{\nu_{1}}\not\in\hat{C}$. Therefore,

$$ $\mathbb{P}(Y_{\nu_{1}}\in\hat{C})=1-\mathbb{P}(Y_{\nu_{K}}\not\in\hat{C})=1- \mathbb{P}(E)\geq 1-\alpha.$ $$

∎

For a permutation $\pi:[N]\rightarrow[N]$ with associated permutation matrix $\Pi$, we say that the GNN is label equivariant if

$$ $\mathcal{G}(\Pi\mathbf{A}\Pi^{\top})=\Pi\mathcal{G}(\mathbf{A}).$ $$

To map Theorem 2 to Theorem 1, we observe that Assumptions 1 and 3 are the same (the latter a detailed version of the former); and that
inputting $\mathbf{A}^{\text{UNF}}$ to a GNN satisfying Assumption 2, along with the attributes $X_{w},w\in\nu$ and training labels $Y_{w},w\in\nu^{(\text{training})}$, results in an $\mathcal{A}$ satisfying Assumption 4.

###### A3 .

###### A4 .

###### Theorem 2 .

###### Proof.

## Appendix C Conditional Coverage

Table 5 displays the worst-case coverage across all time points for both methods, which as expected is not always conditionally valid. The problem here is similar to the problem mentioned with drift. As no two time points are exactly exchangeable, no two embedded time points will be exactly exchangeable. This then translates to variation in coverage between time points. In the marginal coverage case, variation is fine as long as the average coverage is on target. However, under this metric, any variation causes a decrease.

**Table 5: Worst-case coverage over time with target $\geq 0.90$. Values in bold indicate closest to the target for a given GNN.**
| Methods | SBM | School |  |  |
| --- | --- | --- | --- | --- |
|  | Trans. | Semi-ind. | Trans. | Semi-ind. |
| Block GCN | 0.760 $\pm$ 0.067 | 0.619 $\pm$ 0.063 | 0.746 $\pm$ 0.045 | 0.767 $\pm$ 0.040 |
| UGCN | 0.790 $\pm$ 0.035 | 0.857 $\pm$ 0.026 | 0.693 $\pm$ 0.045 | 0.710 $\pm$ 0.041 |
| Block GAT | 0.774 $\pm$ 0.054 | 0.450 $\pm$ 0.154 | 0.702 $\pm$ 0.061 | 0.616 $\pm$ 0.085 |
| UGAT | 0.836 $\pm$ 0.030 | 0.879 $\pm$ 0.031 | 0.763 $\pm$ 0.048 | 0.810 $\pm$ 0.085 |

## Appendix D Temporal Analysis using GCN

In this section, we present a temporal analysis of the school data example using GCN instead of GAT as the GNN model. We see similar conclusions to those stated in Section 3. 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 is 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-inductive 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.

Figure: (a) Transductive.
Refer to caption: x8.png

Figure: (a) Transductive.
Refer to caption: x10.png

Figure: (a) Transductive.
Refer to caption: x12.png

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: My questions pertain the implementation of the method (see weaknesses).
soundness: 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.

The examples chosen by the authors are quite strong and compelling.
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.

To 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:
- 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.
- 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).
- 3 -compute conformity scores to output prediction sets.

The authors  show that this procedure can help them get uncertainty estimates for 3 types of scenarios: transductive, timewise transductive, and semi-transductive.
The 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.
weaknesses: On the whole, I think this is a good paper, but perhaps a couple of modifications would clarify certain aspects:
1- Some of the notations could be clarified. For instance, I found the part explaining the procedure a little confusing. More specifically:
- $\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.
- Similarly,  $\hat{Y}^{UNF},$ I thought this meant the unfolded labels.
- It would be great to add the dimensions (only  $\hat{X}^{UNF}$ is indicated to have dimension $n_r \times d$). 
- 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.

2- the UGNN framework could be further detailed:
- 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?

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

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: Besides several concerns that mentioned in the weakness part, here are several questions regarding the paper details:

Line 88: why requires a bipartite graph? Needs to explain.

Lines 161-165: for better understanding, I would prefer the authors directly used $m$ over $m + 1$ (surely some other formula like 
Algorithm 1 also needs to be changed). But this is more neat.

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

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

Line 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}$?

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

Figure 2: needs a short comment on SBM evolving edges. Why is that?
soundness: 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.

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

3. 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.
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:

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

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

3. 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.
weaknesses: 1. Semi-Inductive Settings:

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

2. Understanding UQ:

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

3. Miscellaneous:

I suggested the reviewers consider the following issues, and if time allows, do some elaboration.

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

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

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

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. This question is similar to the concerns in the weakness. Do you have more experimental results on other backbones?
2. 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.
soundness: 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.
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.
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.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 4
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?
soundness: 4
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.
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.
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.

---

confidence: 3
contribution: 2
initial_rating: 8
presentation: 3
questions: 1. In A2, is label equivariant the same as permutation equivariant?

2. In section 2.1, can you formally prove the exchangebility of UGCN while BD GCN does not satisfy the exchangebiity?

3. Why Algorithm 1 is present in the main paper but Algorithm 2 is used for experiments?
soundness: 3
strengths: 1. The paper studies an important problem relating to uncertainty quantification for GNN prediction. 

2. The use of unfolded adjacency for GNNs on dynamics graphs is natural and promising. 

3. The experiments show promise for the proposed method.
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.
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.  

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

3. The scalability with the use of unfolded adj is poor.

Meta-review: The paper proposes a method for achieving valid conformal prediction on dynamic graphs using graph neural networks. By leveraging an unfolded representation, the approach ensures valid prediction sets across various inference regimes.

Strengths: Novel integration of unfolding with conformal prediction for dynamic graphs. Strong theoretical guarantees under multiple inference regimes. Demonstrates practical relevance with compelling experimental results. Provides a simple and generalizable method adaptable to any GNN architecture.

Weaknesses: Initial unclear notation and explanations. Limited discussion on addressing exchangeability assumptions in real-world scenarios. Scalability challenges with large dynamic graphs. Lack of comparison with more diverse baseline methods.

Decision: Accept (Poster)