Valid Conformal Prediction for Dynamic GNNs

> The paper is poorly written with many concepts and notations not sufficiently explained. In addition, the structure of the paper needs to be improved. "Poorly written'' is really unfair. Other reviewers found our writing clear, the separation of formal mathematics and intuitive explanation helpful. In retrospect we may have accidentally made assumptions about background knowledge (particularly on conformal prediction, e.g. "calibration sets''). We will rectify these to make the paper more generally accessible. > (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) This is a great suggestion, thanks. Working on this now, will update you when the revised PDF is ready. > (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. It is surprising that this works, isn't it? The intuition, roughly, is to think of a dynamic graph as containing two families of nodes: global nodes, and time-localised nodes. $\mathbf{A}^{\text{UNF}}$ is a bipartite graph which connects them. We do not understand what is meant by "the explicit update form''. > (3) Algorithm 1 is introduced with no explanations on the steps. For example, what is a calibration set? Calibration sets were introduced in the conformal literature and explained only via a formal definition and Figure 1, so we take the reviewer's point. We add on first introduction "The data are split into four sets: _training_ which is used to learn the GNN parameters; _validation_, which is out-of-sample performance evaluation for the GNN; _calibration_, which is used to train the conformal model, and _test_, for the final performance metric." and add a brief heurisitic description of this (standard) algorithm: "the algorithm proceeds as follows. First, we fit the GNN to the training data. Then, we compute the model predictions on the calibration set, and compare those to the observed labels using a non-conformity score. Finally, for the test pair, we return a confidence set which contains labels giving scores which aren't "too large'', relative to the calibration set. '' > (4) In theory, the key definitions, such as exchanebility and label equivariant are deferred to appendix, which is not ideal. Happy to move the definitions into the main text. > 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. The best ideas are often simple (Metropolis-Hasting, back-propagation, etc); simplicity is _never_ a good reason to reject. Instead, we would recommend that the reviewer decide whether the idea is _novel_, _useful_, and _non-obvious_. (See answer to wToC for additional details.) > The scalability with the use of unfolded adj is poor. The scaleability of unfolded GNN is the same as block GNN (line 483). There is a difference in _parallelisation_, but as we state (line 524) a pathway to massive-scale analysis is plausible for future work. A naive algorithm would be to analyse node-times for random subsets of nodes. A better algorithm would be to apply random-walk approaches to obtain neighbourhood sets. Such _algorithmic_ improvement is appropriate for future work and is not needed to prove that _in theory_ unfolding is an important tool for conformal dynamic GNN, and we have demonstrated utility _in practice_. > In A2, is label equivariant the same as permutation equivariant? Because this is a supervised context, label was a confusing word to use here, apologies. We will go with permutation equivariant. > In section 2.1, can you formally prove the exchangebility of UGCN while BD GCN does not satisfy the exchangebiity? We will provide references showing GCN is permutation equivariant. We will include a brief demonstration that even if A1 holds, the embedding $\hat{\mathbf{Y}}_{\mathbf{BD}}$ is not row-exchangeable. (We think this is overkill, given that it is already flagrantly shown in Figure 1) > Why Algorithm 1 is present in the main paper but Algorithm 2 is used for experiments? This is an LaTeX labelling error! Apologies. We apply Algorithm 1.

> Could you confirm your algorithm is by combining dilated unfolding (Davis '23) and a GNN? Confirmed! > If that is the only contribution, could you please convince me there is enough innovation provided? The best ideas are often simple (Metropolis-Hasting, back-propagation, etc); simplicity is _never_ a good reason to reject. Instead, we would recommend that the reviewer decide whether the idea is _novel_, _useful_, and _non-obvious_. On novelty: It is nonsense to claim that because a certain graph representation has been proposed before, a new paper using it isn't novel. Shall we also reject any paper which uses an adjacency matrix? The dilated unfolding is used in Davis et al. 23 for unsupervised learning tasks such as clustering. Here we are doing supervised learning, such as classification. These are really very different domains, and Davis et al. do not allude to any possibilities (such as conformal prediction) in that direction. There is no overlap between the theory and models of both papers. In Davis et al. 23, an Erdos-Renyi model is used, i.e. $A_{ij}^{(t)} \sim \text{Bernoulli}(P^{(t)}_{ij})$ independently; here our model is more general, and can accommodate dependence between edges. Most of the work in Davis et al. 23 is to _establish_ exchangeability; here, most of the theoretical work is to establish _what sort of exchangeability_ we need (if any) for _conformal prediction_, a concept which has no meaning in unsupervised settings. On usefulness: 1. Obtaining prediction intervals for dynamic networks is a significant problem for society (see intro), completely unsolved until this paper. 2. The solution proposed, precisely because it is so simple, could reasonably be implemented on large GNNs already in deployment. On non-obvious: 1. (Theory) Demonstrating validity has required substantial and non-trivial novel analysis. Surely the reviewer does not claim that anyone could have predicted that the transductive and temporal transductive regime required no further assumptions, whereas the semi-inductive regime required A1 + A2? 2. (Experiments) We have conducted a comprehensive series of well-considered experiments, and provided the data and code, to uncover different interesting features of the algorithm in real data --- including smaller prediction sets than rival methods, prediction sets adapting to periods of uncertainty (see school data), and different failure modes.

>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. We would instead ask, what value would showing other backbone models add? The important point about unfolding is that it modifies the representation of the _data_ for _any GNN_ so that it will provide _valid predictions_ under well-defined assumptions (appropriate exchangeability). Whilst for any given dataset, it is possible that some clever block GNN will perform well empirically, _it can never be valid_ because the input data does not contain the information required - i.e. stability over time - for validity. Conformal inference is important not because of its empirical performance but because it offers a well-defined guarantee of validity, which is the focus of the paper. > This question is similar to the concerns in the weakness. Do you have more experimental results on other backbones? We do see how a demonstration of the above point could be better made through other backbone models, so we've added GraphSAGE [1] and JKNet [2], which have the same qualitative performance (See Appendix H in the updated manuscript). Others are plausible, if you have suggestions, though we note that many seem very slow (so far we've only had time to run the school example) and we see this as demonstrating the point that unfolding, and not the backbone model, is the key. [1] Hamilton, Ying and Leskovec 2017 "Inductive Representation Learning on Large Graphs", NeurIPS, https://cs.stanford.edu/people/jure/pubs/graphsage-nips17.pdf [2] Xu et al 2018, "Representation Learning on Graphs with Jumping Knowledge Networks" ICML, https://paperswithcode.com/paper/representation-learning-on-graphs-with > 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. There are no competing valid conformal prediction methods for dynamic graphs (in the sense we mean), which is why we view this contribution as important. There are valid approaches for static graphs, for which our literature review (line 48; line 64-80) contains the approaches we are aware of (and none are suitable for comparison in the dynamic graph case).

> 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. This is an interesting direction. In our discussion (lines 526-528) we briefly mentioned how works from Barber et al., 2023 and Clarkson, 2023 could be applied downstream of our UGNN embeddings to aid performance in settings where exchangeability may not hold. Barber et al. 2023 introduce a conformal framework in which the nonconformity scores of more "trusted" data points are assigned a larger weight when computing the prediction set. Clarkson, 2023 then applied this work to GNNs, proposing a nonconformity score known as neighbourhood adaptive prediction sets (NAPS), where nodes closest to the test point were weighted more strongly. So in the case of our trade example, assigning higher weightings to more recent data points will likely aid the performance of our method. However, as drift still exists between the most recent labelled nodes and the test nodes, assumption A1 will still not hold, and so conformal prediction will not generally hold, even after applying this. We therefore view these techniques as critical to improve predictive performance for particular tasks, but out of scope of this paper which is about validity. > 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. We were not completely sure what was being requested here, perhaps you can clarify? In Figure 4 we show the prediction sets over time for the school example, which demonstrates variation in when uncertainty is present under different conformal models. > a) Is there is any other way to reshape the dynamic graph from (T, N, N) into a 2D-shape, e.g. compare the performance of the reshaped matrix in shape (T, N^2) This is another very interesting question, being discussed in the unfolding literature in the context of spectral embedding; e.g. https://arxiv.org/html/2410.09810v1. There may be advantages for other shapes which make different assumptions about the underlying exchangability. We see this as a different direction to that of conformal inference for dynamic graphs, best explored in separate work. > b) Another simplification on the current A^UNF might be: A^1 at top left, and the remaining unfolded calA dilated in the same way. I would consider if this will somehow reduce the complexity, especially when T<<N. A critical aspect of unfolding is to maintain exchangeability, i.e. that reordering rows and columns appropriately does not affect the embedding. The structure we interpret from this suggestion favours A_1 as special and therefore not exchangeable. More generally, it is important to consider the motivation changing the representation. Using a sparse representation the dilation costs only a factor of 2 more compute, for which we gain symmetry (and hence applicability of many more algorithms) as well as theoretical benefits (as in our paper). Innovations in representation would be an interesting contribution that are distinct from our goal of bringing conformal inference to dynamic GNNs. > 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. This is a fascinating topic that would bear its own research paper by itself due to the many potential options. One is to simply unfold the node classes (e.g. infection status); another would be to turn to tensor representations discussed above - to which GNNs naturally generalise. The critical aspect is that unfolding leads to exchangeability properties only with respect to properties that are jointly anchored, i.e. share the same "rows" (and whatever else we anchor on, if we view e.g. infection status as a third dimension in a 3d array). [Response continues below...]

> 1- Some of the notations could be clarified. For instance, I found the part explaining the procedure a little confusing. We have clarified the procedure in response to your and other reviewers comments, rewriting how training, validation, calibration and testing data are all used. > $X^{UNF}$: since X is already used to describe features, another letter would be preferable here. I originally thought that it $X^{UNF}$ meant the unfolded features. Similarly, I thought this $Y^{UNF}$ meant the unfolded labels. Good point; this was an artefact of combining standard notational practices from embedding and conformal prediction work. We have switched from X and Y to represent different network embeddings to U and V. > It would be great to add the dimensions (only $X^{UNF}$ is indicated to have dimension). Thanks - we have added dimensions. > 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. We have reorganised subscripts and superscripts, removing $n_r$ and replacing it with $p$. > 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? Yes, this is correct. There was a typo in the definition of $\mathcal{G}$ which did not show the dependence on Y; We've updated the equation to make this clear. > 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. The unfolded matrix we propose will is (n+nT) x (n+nT), as opposed to 2nT x 2nT. > 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. This is a very good suggestion. To be clear, the principal challenge we are addressing is CP on _dynamic_ graphs. We have elaborated on the problem in the introduction. ``The unsolved problem we address ...''