Ed Davis

Contact & Links

Email: edward.davis[at]bristol.ac.uk

Office: School of Mathematics University of Bristol, Fry Building, GA.06 Woodland Road Bristol, BS8 1UG.

Twitter: EdD8ta

PhD supervised by Prof. Patrick Rubin-Delanchy and Dr Daniel Lawson.

Research Outline

My work focuses on dynamic network embedding. Dynamic networks encode both spatial and temporal relations between nodes, which are desirable for many applications from cyber security to neuroscience. By representing the nodes of the network as a vector space, it allows us to detect spatial and temporal patterns through clustering. Methods that I have developed during my PhD have been used by Microsoft and LV, and I have presented these methods at the Institute of Mathematics Big Data Conference and the COMPASS conference in 2022. I am interested in progressing dynamic embedding methods and applying them to a diverse range of problems.

Papers

A Simple but Powerful Framework for Dynamic Graph Embedding

In this paper, we address the problem of dynamic network embedding, that is, representing the nodes of a dynamic network as evolving vectors within a low-dimensional space. While the field of single-graph embedding is wide and established, the field of dynamic graph embedding is comparatively in its infancy. In this paper, we propose that we can take a wide class of established single-graph embedding methods and use them to produce interpretable and powerful dynamic graph embeddings by simply applying them to the dilated unfolded matrix. We provide a theoretical guarantee that, regardless of embedding dimension, these unfolded methods will produce stable embeddings over time and space, meaning that nodes with identical latent behaviour will be exchangeable, regardless of their position in time or space.

Figure: A one-dimensional URLSE displaying the average temporal structure of airports in Italy, the UK and across Europe. The embedding encodes the two main European waves of COVID-19 as well as an annual periodic structure before and after the pandemic. We also see that the pandemic hit Italy slightly before the UK and the rest of Europe.

Valid Conformal Prediction for Dynamic GNNs

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.

A dynamic embedding of i.i.d. data using UGCN and a standard GCN.

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

Valid Bootstraps for Networks with Applications to Network Visualisation

Quantifying uncertainty in networks is an important step in modelling relationships and interactions between entities. We consider the challenge of bootstrapping an inhomogeneous random graph when only a single observation of the network is made and the underlying data generating function is unknown. We utilise an exchangeable network test that can empirically validate bootstrap samples generated by any method, by testing if the observed and bootstrapped networks are statistically distinguishable. We find that existing methods fail this test. To address this, we propose a principled, novel, distribution-free network bootstrap using k-nearest neighbour smoothing, that can regularly pass this exchangeable network test in both synthetic and real-data scenarios. We demonstrate the utility of this work in combination with the popular data visualisation method t-SNE, where uncertainty estimates from bootstrapping are used to explain whether visible structures represent real statistically sound structures.

Figure: An overview of the proposed graph bootstrap framework. Given an adjacency matrix (a), we use its network embedding (b) to estimate the probability matrix (c) using k-nearest neighbours, from which the adjacency matrix was drawn. From this, we draw many new adjacency matrices (d) and use them to estimate the uncertainty in the network embedding (e). We then use this uncertainty to explain the visible structures in the network embedding (f).

Accomplishments

Award-Winning Data Visualisation

Runner-up in the Jean Golding Institute's Beauty of Data competition. This visualisation was presented at the Bristol Data and AI Showcase 2022. This visualisation displays an embedding of a friendship network between countries on the world stage based on their alliances.

(Click image for full-size)