Using Causality-Aware Graph Neural Networks to Predict Temporal
  Centralities in Dynamic Graphs
Node centralities play a pivotal role in network science, social network
analysis, and recommender systems. In temporal data, static path-based
centralities like closeness or betweenness can give misleading results about
the true importance of nodes in a temporal graph. To address this issue,
temporal generalizations of betweenness and closeness have been defined that
are based on the shortest time-respecting paths between pairs of nodes.
However, a major issue of those generalizations is that the calculation of such
paths is computationally expensive. Addressing this issue, we study the
application of De Bruijn Graph Neural Networks (DBGNN), a causality-aware graph
neural network architecture, to predict temporal path-based centralities in
time series data. We experimentally evaluate our approach in 13 temporal graphs
from biological and social systems and show that it considerably improves the
prediction of both betweenness and closeness centrality compared to a static
Graph Convolutional Neural Network.
Franziska Heeg, Ingo Scholtes
# Using Causality-Aware Graph Neural Networks to Predict Temporal Centralities in Dynamic Graphs

###### Abstract

Node centralities play a pivotal role in network science, social network analysis, and recommender systems. In temporal data, static path-based centralities like closeness or betweenness can give misleading results about the true importance of nodes in a temporal graph. To address this issue, temporal generalizations of betweenness and closeness have been defined that are based on the shortest time-respecting paths between pairs of nodes. However, a major issue of those generalizations is that the calculation of such paths is computationally expensive. Addressing this issue, we study the application of De Bruijn Graph Neural Networks (DBGNN), a causality-aware graph neural network architecture, to predict temporal path-based centralities in time series data. We experimentally evaluate our approach in 13 temporal graphs from biological and social systems and show that it considerably improves the prediction of both betweenness and closeness centrality compared to a static Graph Convolutional Neural Network.

## 1 Motivation

Node centralities are important in the analysis of complex networks, with applications in network science, social network analysis, and recommender systems. An important class of centrality measures are _path-based centralities_ like, e.g. betweenness or closeness centrality [1; 2], which are based on the shortest paths between all nodes. While centralities in static networks are important, we increasingly have access to time series data on temporal graphs with time-stamped edges. Due to the timing and ordering of those edges, the paths in a static time-aggregated representation of such time series data can considerably differ from _time-respecting paths_ in the corresponding temporal graph. In a nutshell, two time-stamped edges \((u,v;t)\) and \((v,w;t^{\prime})\) only form a time-respecting path from node \(u\) via \(v\) to \(w\) iff for the time stamps \(t\) and \(t^{\prime}\) we have \(t<t^{\prime}\), i.e. time-respecting paths must minimally respect the arrow of time. Moreover, we often consider scenarios where we need to additionally account for a _maximum time difference_\(\delta\) between time-stamped edges, i.e. we require \(0<t^{\prime}-t\leq\delta\)[3]. Several works have shown that temporal correlations in the sequence of time-stamped edges can significantly change the _causal_ topology of a temporal graph, i.e. which nodes can possibly influence each other
via time-respecting paths, compared to what one would expect based on the static topology of edges [4; 5; 6].

An important consequence of this is that static path-based centralities like closeness or betweenness can give misleading results about the true importance of nodes in temporal graphs. To address this issue, temporal generalizations of betweenness and closeness centrality have been defined that are based on the shortest time-respecting paths between pairs of nodes [7; 8; 9; 10]. A major issue of those generalizations is that the calculation of time-respecting paths as well as the resulting centralities is computationally expensive [11; 12; 13]. Addressing this issue, a number of recent works developed methods to approximate temporal betweenness and closeness centralities in temporal graphs [13]. Additionally, few works have used deep (representation) learning techniques to predict computationally expensive path-based centralities in _static_ networks [14; 15].

Research Gap and ContributionsTo the best of our knowledge, no prior works have considered the application of time-aware graph neural networks to predict path-based centralities in temporal graphs. Closing this gap, our work makes the following contributions:

* We introduce the problem of predicting temporal betweenness and closeness centralities of nodes in temporal graphs. We consider a situation where we have access to a training graph as well as ground truth temporal centralities and seek to predict the centralities of nodes in a future observation of the same system, which does not necessarily consist of the exact same set of nodes.
* To address this problem, we introduce a deep learning method that utilizes De Bruijn Graph Neural Networks (DBGNN), a recently proposed causality-aware graph neural network architecture [16] that is based on higher-order graph models of time-respecting paths, which capture correlations in the sequence of time-stamped edges. An overview of our approach in a toy example of a temporal graph is shown in Figure 1.
* We compare our proposed method to a Graph Convolutional Network (GCN), which only considers a static, time-aggregated weighted graph that captures the frequency and topology of edges.
* We experimentally evaluate both models in 13 time temporal graphs from biological and social systems. Our results show that the application of the time-aware DBGNN architecture considerable improves the prediction of both betweenness and closeness centrality compared to a static GCN model.

In summary, we show that the prediction of temporal centralities is an interesting temporal graph learning problem, which could be included in community benchmarks [17]. Moreover, our study highlights the potential of causality-aware deep learning architectures for node-level regression tasks in temporal graphs. Finally, our results are a promising step towards the approximation of temporal centralities in large data sets, with potential applications in social network analysis and recommender systems.

## 2 Background and Related Work

In the following, we provide the background of our work. We first introduce temporal graphs and define time-respecting (or causal) paths. We then cover generalizations of path-based centralities for nodes in temporal graphs. We finally discuss prior works that have studied the prediction, or approximation, of path-based centralities both in static and temporal graphs. This will motivate the research gap that is addressed by our work.

Dynamic Graphs and Causal PathsApart from static graphs \(G=(V,E)\) that capture the topology of edges \(E\subseteq V\times V\) between nodes \(V\), we increasingly have access to time-stamped interactions that can be modelled as _temporal graphs or networks_[18; 19; 3]. We define a temporal graph as \(G^{\mathcal{T}}=(V,E^{\mathcal{T}})\) where \(V\) is the set of nodes and \(E^{\mathcal{T}}\in V\times V\times\mathbb{R}\) is a set of (possibly directed) time-stamped edges, i.e. an edge \((v,w;t)\in E^{\mathcal{T}}\) describes an interaction fron node \(v\) to \(w\) occurring at time \(t\). In our work, we assume that interactions are _instantaneous_, i.e. \((v,w;t)\in E^{\mathcal{T}}\) does not imply that \((v,w;t^{\prime})\in E^{\mathcal{T}}\) for all \(t^{\prime}>t\). Hence, we do not specifically consider _growing networks_, where the time-stamp \(t\) is the creation of an edge. For a temporal network \(G^{\mathcal{T}}=(V,E^{\mathcal{T}})\) it is common to consider a static, time-aggregated and weighted graph representation \(G=(V,E)\)
where \((v,w)\in E\) iff \((v,w;t)\in E^{\mathcal{T}}\) for some time stamp \(t\) and for the edge weights we define \(w(v,w)=|\{t\in\mathbb{R}:(v,w;t)\in E^{\mathcal{T}}\}|\), i.e. the number of occurrences of time-stamped edges.

An important difference to paths in static graphs is that, in temporal networks, the temporal ordering of edges determines what we call _time-respecting or causal paths_[20, 19, 3]. For a temporal graph \(G^{\mathcal{T}}=(V,E^{\mathcal{T}})\) we define a _time-respecting or causal path_ of length \(l\) as sequence of nodes \(v_{0},\ldots,v_{l}\) such that the following two conditions hold:

* \(\exists\;t_{1},\ldots,t_{l}\;:\;(v_{i-1},v_{i};t_{i})\in E^{\mathcal{T}}\) for \(i=1,\ldots,l\) ;
* \(0<t_{i}-t_{i-1}\leq\delta\) for some \(\delta\in\mathbb{R}\).

In contrast to definitions of time-respecting paths that only require interactions to occur in ascending temporal order, i.e. \(0<t_{i}-t_{j}\) for \(j<i\)[20, 21], we additionally impose a maximum "waiting time" \(\delta\)[5, 19]. This implies that we only consider time-respecting paths where subsequent interactions occur within a time interval that is often defined by the processes that we study on temporal networks [12, 22]. In line with the definition for static networks, we define a _shortest time-respecting path_ between two nodes \(v\) and \(w\) as a (not necessarily unique) time-respecting path of length \(l\) such that all other time-respecting paths from \(v\) to \(w\) have length \(l^{\prime}\geq l\). In static graphs a shortest path from \(v\) to \(w\) is necessarily a _simple_ path, i.e. a path where no node occurs more than once in the sequence \(v_{1},\ldots,v_{l}\). This is not neccessarily true for shortest time-respecting path, since -due to the maximum waiting time \(\delta\)- we may be forced to move between (possibly the same) nodes to continue a time-respecting path. Due to the definition of time-respecting paths with limited waiting time \(\delta\), we obtain a _temporal-topological_ generalization of shortest paths to temporal graphs that accounts for the temporal ordering and timing of interactions. We note that there exist definitions of _fastest paths_

Figure 1: Overview of proposed approach to predict temporal centralities of nodes in a temporal graph: We consider a time-based split in a training and test graph (left). Calculating time-respecting paths in the training split enables us to (1) compute temporal node centralities, and (2) fit a \(k\)-th order De Bruijn graph model for time-respecting paths. The weighted edges in such a \(k\)-th order De Bruijn graph capture the frequencies of time-respecting paths of length \(k\) (see time-respecting path of length one (red) and two (magenta)). (3) We then use these centralities and the k-th order models to train a De Bruijn graph neural network (DBGNN), which allows us to (4) predict temporal node centralities in the test graph.
that only account for the temporal rather than the topological distance [5], which we however do not consider in our work.

The definition of time-respecting paths above has the important consequence that the connectivity of nodes via time-respecting paths in a temporal network can be considerably different from paths in the corresponding time-aggregated static network. As an example, for a temporal network with two time-stamped edges \((u,v;t)\) and \((v,w;t^{\prime})\) the time-aggregated network contains a path from \(u\) via \(v\) to \(w\), while a time-respecting path from \(u\) via \(v\) to \(w\) can only exist iff \(0<t^{\prime}-t\leq\delta\). In other words, while connectivity in static graphs is _transitive_, i.e. the existence of edges (or paths) connecting \(u\) to \(v\) and \(v\) to \(w\) implies that there exists a path that transitively connects \(u\) to \(w\), the same does not hold for time-respecting paths. A large number of works have shown that this difference between paths in temporal and static graphs influences connectivity and reachability [4], the evolution of dynamical processes like diffusion or epidemic spreading [23, 6, 24, 25], cluster patterns [23, 26, 27], as well as the controllability of dynamical processes [28].

Temporal CentralitiesAnother interesting question is how the time dimension of temporal graphs influences the importance or _centrality_ of nodes [8]. To this end, several works have generalized centrality measures originally defined for static graphs to temporal networks. For our purpose we limit ourselves to generalizations of betweenness and closeness centrality, which are defined based on the shortest paths between nodes. In a static network, a node \(v\) has high _betweenness centrality_ if there are many shortest paths that pass through \(v\)[2] and it has high _closeness centrality_ if the overall distance to all other nodes is small [1]. We omit those standard definitions here due to space constraints but include them in appendix C.

Analogously to betweenness centrality for static graphs, for a temporal graph \(G=(V,E^{T})\) we define the _temporal betweenness centrality_ of node \(v\in V\) as

\[c_{B}^{temp}(v)=\sum_{s\neq v\neq t\in V}\frac{\sigma_{s,t}(v)}{\sigma_{s,t}}\]

where \(\sigma_{s,t}\) is the number of shortest _time-respecting_ paths from node \(s\) to \(t\). Following our definition above, we consider two time-respecting paths to be the same if the sequence of traversed nodes is identical, i.e. \(\sigma_{s,t}\) counts paths that traverse the same set of nodes at different times only once.

To calculate the _temporal closeness centrality_ we define the temporal distance \(d(u,v)\) between two nodes \(u,v\in V\) as the length of a shortest time-respecting paths from \(u\) to \(v\) and thus obtain

\[c_{C}^{temp}(v)=\frac{1}{\sum_{u\in V}d(u,v)}.\]

Even though the definitions above closely follow those for static networks, it has been shown that the temporal centralities of nodes can differ considerably from their counterparts in static time-aggregated networks [8, 27]. These findings highlight the importance of a _time-aware_ network analysis, which consider both the timing and temporal ordering of links in temporal graphs.

Approximating Path-based CentralitiesWhile path-based centralities have become an important tool in network analysis, a major issue is the computational complexity of the underlying all-pairs shortest path calculation in large graphs. For static networks, this issue can be partially alleviated by smart algorithms that speed up the calculation of betweenness centralities [29]. Even with these algorithms, calculating path-based centralities in large graphs is a challenge. Hence, a number of works considered approaches to calculate fast approximations, e.g. based on a random sampling of paths [30, 31, 32]. Another line of studies either used standard, i.e. not graph-based, machine learning techniques to leverage correlations between different centrality scores [15, 14], or used neural graph embeddings in synthetic scale-free networks to approximate the ranking of nodes [33].

Existing works on the approximation of path-based node centralities in time series data have generally focussed on a fast updating of _static_ centralities in _evolving graphs_ where edges are added or deleted [34, 35], rather than considering _temporal node centralities_. For the calculation of temporal closeness or betweenness centralities, the need to calculate shortest _time-respecting paths_ between all pairs of nodes is a major computational challenge. In particular, the calculation of time-respecting paths with a maximum waiting time constraint, which is the definition considered in our work, has recently been shown to be an NP-hard problem [12]. Considering the approximate estimation of temporal
betweenness and closeness centrality in temporal graphs, [36] generalizes static centralities to higher-order De Bruijn graphs, which capture the time-respecting path structure of a temporal graph. [13] recently proposed a sampling-based estimation of temporal betweenness centralities. To the best of our knowledge, no prior works have considered the application of deep graph learning to predict temporal node centralities in temporal graphs, which is the gap addressed by our work.

## 3 A Causality-Aware GNN Architecture to Predict Temporal Centralities

In the following, we first present higher-order De Bruijn graph models for time-respecting paths in temporal networks. We then describe the proposed deep learning architecture to predict temporal betweenness and closeness centrality.

Higher-Order De Bruijn Graph Models of Time-respecting pathsEach time-respecting path gives rise to an ordered sequence \(v_{0},v_{1},\ldots,v_{l}\) of traversed nodes. Let us consider a \(k\)-th order Markov chain model, where \(P(v_{i}|v_{i-k},\ldots,v_{i-1})\) is the probability that a time-respecting path continues to node \(v_{i}\), conditional on the \(k\) previously traversed nodes. A first-order Markov chain model can be defined based on the frequencies of edges (i.e. paths of length \(k=1\)) captured in a weighted time-aggregated graph, where

\[P(v_{i}|v_{i-1}):=\frac{w(v_{i-1},v_{i})}{\sum_{j}w(v_{i-1},v_{j})}.\]

While such a first-order model is justified if the temporal graph exhibits no patterns in the temporal ordering of time-stamped edges, a number of works have shown that empirical data exhibit patterns that require higher-order Markov models for time-respecting paths [23; 25; 26]. To address this issue, for \(k>1\) we can define a \(k\)-th order Markov chain model based on the frequencies of time-respecting paths of length \(k\) as

\[P(v_{i}|v_{i-k},\ldots,v_{i-1})=\frac{w(v_{i-k},\ldots,v_{i})}{\sum_{j}w(v_{i- k},\ldots,v_{i-1},v_{j})},\]

where \(w(v_{0},\ldots,v_{k})\) counts the number of time-respecting path \(v_{0},\ldots,v_{k}\) in the underlying temporal graph. For a temporal graph \(G^{\mathcal{T}}=(V,E^{\mathcal{T}})\), this approach defines a static \(k\)_-th order De Bruijn graph model_\(G^{(k)}=(V^{(k)},E^{(k)})\) with

* \(V^{(k)}=\{(v_{0},\ldots,v_{k-1})\mid v_{0},\ldots,v_{k-1}\text{ is a causal walk of length }k-1\text{ in }G^{\mathcal{T}}\}\)
* \((u,v)\in E^{(k)}\) iff \[\begin{array}{l}(i)\;\;v=(v_{1},\ldots,v_{k})\text{ with }v_{i}=u_{i}\text{ for }i=1,\ldots,k-1\\ (ii)\;u\bigoplus v=(u_{0},\ldots,u_{k-1},v_{k})\text{ is a causal path of length }k\text{ in }G^{\mathcal{T}}.\end{array}\]

We call this \(k\)-th order model a _De Bruijn graph model_ of time-respecting paths, since it is a generalization of a \(k\)-dimensional De Bruijn graph [37], with the additional constraint that an edge only exists iff the underlying temporal network has a corresponding time-respecting path. For \(k=1\) the first-order De Bruijn graph corresponds to the commonly used static, time-aggregated graph \(G=(V,E)\) of a temporal graph \(G^{T}\), where edge can be considered time-respecting paths of length one and which neglects information on time dimension. For \(k>1\) we obtain _static but time-aware higher-order generalizations of time-aggregated graphs_, which are sensitive to the timing and ordering of time-stamped edges. Each node in such a \(k\)-th order De Bruijn graph represents a time-respecting path of length \(k-1\), while edges represent time-respecting paths of length \(k\). Edge weights correspond to the number of observations of time-respecting paths of length \(k\) (cf. fig. 1).

De Bruijn Graph Neural Networks for Temporal Centrality PredictionOur approach to predict temporal betweenness and closeness centrality uses the recently proposed De Bruijn Graph Neural Networks (DBGNN), a deep learning architecture that builds on \(k\)-th order De Bruijn graphs [16]. The intuition behind this approach is that, by using message passing in multiple (static) \(k\)-th order De Bruijn graph models of time-respecting paths, we obtain a _causality-aware learning algorithm_ that considers both the graph topology as well as the temporal ordering and timing of interactions.

Our proposed method is summarized in fig. 1. Considering time series data on a temporal graph, we first perform a time-based split of the data into a training and test graph. We then calculate temporal
closeness and betweenness centralities of nodes in the training graph and consider a supervised node-level regression problem, i.e. we use temporal centralities of nodes in the training graph to train a DBGNN model. To this end, we construct \(k\)-th order De Bruijn graph models for multiple orders \(k\), based on the statistics of time-respecting paths of lengths \(k\). The maximum order is determined by the temporal correlation length (i.e. the Markov order) present in a temporal graph and can be determined by statistical model selection techniques [38].

Using the update rule defined in Eq. (1) of [16], we simultaneously perform message passing in all \(k\)-th order De Bruijn graphs. For each \(k\)-th order De Bruijn graph this yields a (hidden) representation of \(k\)-th order nodes. To aggregate the resulting representation to actual (first-order) nodes in the temporal graph, we perform message passing in an additional bipartite graph, where each \(k\)-th order node \((v_{0},\ldots,v_{k-1})\) is connected to first-order node \(v_{k-1}\) (cf. Eq (2) in [16] and fig. 1). Taking a node regression perspective, we use a final dense linear layer with a single output. We use the trained model to predict the temporal centralities of nodes in the test graph. Since the subset of nodes and edges that are active in the training and test graph can differ, our model must be able to generalize to temporal graphs with different nodes as well as different graph topologies. To address this, we train our models in an inductive fashion by choosing a suitably large number of dimensions for the one-hot encodings during the training phase. Upon acceptance of the manuscript, we will make our code publicly available via Zenodo.

## 4 Experimental Results

With our experimental evaluation we seek to answer the following research question:

* How does the predictive power of a causality-aware DBGNN model compare to that of a standard GCN that ignores the temporal dimension of dynamic graphs?
* How does the predictive power differ between temporal betweenness and closeness centrality and how does it vary across different temporal networks?
* How does the computational efficiency of the DBGNN-based prediction of temporal node centralities compare to that of a time-neglecting GCN architecture?
* Does the DBGNN architecture generate node embeddings that facilitate interpretability?

Experimental setupWe experimentally evaluate the performance of the DBGNN architecture by predicting temporal centralities in 13 empirical temporal graphs. Since a maximum order detection in those data sets yields a maximum of two (see table 7 in appendix A), we limit the DBGNN architecture to \(k=2\). To calculate edge weights of the DBGNN model, we count time-stamped edges for weights of the first-order De Bruijn graph as well as time-respecting paths of length two for weights of the second-order De Bruijn graph (cf. fig. 1). Adopting the approach in [16] we use one message passing layer with 16 hidden dimensions for each order \(k\) and one additional bipartite message passing layer with 8 hidden dimensions. We use a sigmoid activation function for the higher-order layers and an Exponential Linear Unit (ELU) activation function for the bipartite layer.

As a baseline model, we use a Graph Convolutional Neural Network (GCN) [39], which we apply to the weighted time-aggregated representation of the temporal graphs. For the GCN model, we use two message passing layers with 16 and 8 hidden dimensions and a sigmoid activation function, respectively. As input features, we use a one-hot encoding (OHE) of nodes for both architectures. In the case of the DBGNN architecture we apply OHE to nodes in all (higher-order) layers. Addressing a node regression task, we use a final dense linear layer with a single output and an ELU activation function, and use mean squared error (MSE) as loss function for both architectures. We train both models based on the (ground-truth) temporal node centralities in the training data, using 5000 epochs with an ADAM optimizer, different learning rates, and weight decay of \(5\cdot 10^{-4}\). We additionally tested the use of dropout layers for both architectures, but found the results to be worse. In table 10 and table 11 we summarize the architecture and the hyperparameters for both models.

Data setsWe use 13 data sets on temporal graphs from different contexts, including human contact patterns based on (undirected) proximity or face-to-face relations, time-stamped (directed) E-Mail communication networks, as well as antenna interactions between ants in a colony. An overview of the data sets along with a short description, key characteristics and the source is given in table 1. All data sets are publicly available from the online data repositories netzschleuder [40] and SNAP [41].
Evaluation procedureTo evaluate our models, we first fit the pre-trained models to the test graph, i.e. we apply the trained GCN model to the weighted time-aggregated test graph and the trained DBGNN model to the De Bruijn graphs for the test data. We then use the trained models to predict temporal closeness and betweenness centralities and compare those predictions to ground truth centralities, which we obtain by exhaustively calculating all time-respecting paths in the test data. Figure 1 provides an illustration of our evaluation approach. We calculate the mean absolute error between predicted and ground truth centralities. We further use Kendall-Tau and Spearman rank correlation to compare a node ranking based on predicted centralities with a ranking obtained from ground truth centralities. We evaluate predictions in terms of mean absolute error as well as Spearman and Kendall-Tau rank correlation coefficient. Since centrality scores are often used to identify a small set of most central nodes, we further calculate the number of hits in the set of nodes with the top ten predicted centralities. Since we repeated each experiment \(30\) times, we report the mean and the standard deviation of all scores. We further repeated all experiments for three different learning rates between \(0.1\) and \(0.001\) and only report the best mean scores for each model individually.

Discussion of resultsThe results of our experiments for temporal betweenness and closeness centralities are shown in table 2 and table 3, respectively. Considering **RQ1**, we find that our causality-aware DBGNN-based architecture significantly outperforms a standard GCN model for all 13 data sets and for all evaluation metrics in the case of temporal closeness centrality (with the exception of the MAE score in sp-hypertext, where we observe no significant difference). We further observe a large relative increase of the Spearman rank correlation coefficient averaging to 117 % across all data, ranging between 32 % for sp-hypertext and 436 % for eu-email-4. For temporal betweenness centrality, we find that the proposed causality-aware architecture significantly outperforms a GCN-based prediction in terms of Spearman and Kendall-Tau rank correlation for seven of the 13 data sets, while we observe no significant difference for five and better performance of the GCN model for a single data set. On average across all 13 data sets, the DBGNN architecture yields an increase in Spearman correlation by 39 %. For the seven cases where DBGNN outperforms GCN, we find relative increases in Spearman rank correlation between 18 and 97 %. For sp-highschool, where a GCN model outperforms a DBGNN-based prediction, the relative increase is 17 %.

Regarding **RQ2** we observe that the performance of a time-neglecting GCN-based prediction of temporal closeness and betweenness centrality are comparable. On the contrary, the time-aware DBGNN model performs significantly better for temporal closeness compared to temporal betweenness. Moreover, we find a large variation of predictive performance across different data sets. To further investigate the differences between data sets, in Figure 2 and Figure 3 in appendix C we plot the temporal and static closeness and betweenness centralities of nodes. The results indicate that the timing and temporal ordering of interactions translates to larger differences between temporal and static betweenness centrality, compared to closeness centrality, which could explain our observation.

A potential criticism of our approach could be that the size of a higher-order De Bruijn graph model can be considerably larger than for a standard first-order graph, thus possibly making them computationally expensive. To address this issue, and to answer **RQ3**, we investigate the scalability of our approach for all of the 13 data sets. For this, we calculate both the training and the inference time of our DBGNN-based architecture with those of a simpler GCN model. The results in table 5 and table 6 in appendix A show that the computational requirements of the DBGNN and GCN model are comparable, both during training and the inference time. We attribute this to the fact that the

\begin{table}
\begin{tabular}{l l l|c c c c} \hline \hline data set & Description & \multicolumn{1}{c|}{Ref} & Nodes & Edges & Temporal Edges & Directed & \(\delta\) \\ \hline ants-1-1 & Ant Antenna interactions, colony 1 - filming 1 & [42] & 89 & 947 & 1,911 & True & 30 sec \\ ants-1-2 & Ant Antenna interactions, colony 1 - filming 2 & [42] & 72 & 862 & 1,820 & True & 30 sec \\ ants-2-1 & Ant Antenna interactions, colony 2 - filming 1 & [42] & 71 & 636 & 975 & True & 30 sec \\ ants-2-2 & Ant Antenna interactions, colony 2 - filming 2 & [42] & 69 & 769 & 1,917 & True & 30 sec \\ company-emails & E-Mail exchanges in manufacturing company & [43] & 167 & 5,784 & 82,927 & True & 60 mins \\ eu-email-2 & E-Mail exchanges in EU institution (dept 2) & [44] & 162 & 1,772 & 46,772 & True & 60 mins \\ eu-email-3 & E-Mail exchanges in EU institution (dept 3) & [44] & 89 & 1,506 & 12,216 & True & 60 mins \\ eu-email-4 & E-Mail exchanges in EU institution (dept 4) & [44] & 142 & 1,375 & 48,141 & True & 60 mins \\ sp-hospital & Face-to-face interactions in a hospital & [24] & 75 & 1,139 & 32,424 & False & 60 mins \\ sp-hypertext & Face-to-face interactions at conference & [45] & 113 & 2,498 & 20,818 & False & 60 mins \\ sp-workplace & Face-to-face interactions in a workspace & [46] & 92 & 755 & 9,827 & False & 60 mins \\ sp-highschool & Face-to-face interactions in a highschool & [47] & 327 & 5,818 & 188,508 & False & 60 mins \\ hagle & Human proximity recorded by smart devices & [48] & 274 & 2,899 & 28,244 & False & 1 min \\ \hline \hline \end{tabular}
\end{table}
Table 1: Overview of time series data sets used in the experiment evaluation
DBGNN architecture utilizes a compact, _static but time-aware_ De Bruijn graph representation of potentially large time series, rather than requiring a representation of all time-stamped edges.

A potential advantage of our method is that it can facilitate fast approximate predictions of temporal centralities. The exact calculation of those centralities is computationally expensive as it requires to exhaustively calculate shortest time-respecting paths (with a given maximum time difference) between all pairs of nodes [49]. Highlighting this, in table 4 in the appendix we report the time required to calculate (ground truth) temporal closeness and betweenness centralities based on shortest time-respecting paths between all pairs of nodes in the test networks. Importantly, while our approach requires to fit a \(k\)-th order De Bruijn graph model in the test set, this procedure only requires to calculate time-respecting paths of exactly length \(k\), which is a much simpler problem.

Considering **RQ4**, another aspect of our approach to use a time-aware but _static_ graph neural network is that the hidden layer activations yield _static_ embeddings that are based on the _causal topology_ of a dynamic graph. This causal topology is influenced by (i) the topology of time-stamped links, and (ii) their timing and temporal ordering. To explain the favorable performance of our model, we hypothesize that nodes for which our model learns similar embeddings also have more similar temporal centralities, compared to the embeddings generated by a GCN model. To test this hypothesis, we apply a dimensionality reduction to the node activations generated by the last 8-dimensional bipartite layer in the DBGNN architecture, comparing it to the representation obtained from the last message passing layer of a GCN model. In appendix D we show the resulting embeddings for one representative prediction of temporal closeness using the DBGNN (left) and the GCN model (right) in the eu-email-4 data, where an additional color gradient highlights ground truth closeness centralities of nodes in the test data. The resulting plot clearly shows that the time-aware DBGNN architecture is able to capture the ranking of nodes, while the time-neglecting GCN model is not.

## 5 Conclusion

In summary, we investigate the problem of predicting temporal betweenness and closeness centralities in temporal graphs. To this end, we use a recently proposed causality-aware graph neural network architecture, which relies on higher-order De Bruijn graph models of time-respecting paths. An empirical study in which we compare our approach with a time-neglecting graph neural network demonstrates the potential of our method. A comparative analysis in 13 empirical temporal networks

\begin{table}
\begin{tabular}{l|c c c c|c c c c} \hline \hline Experiment & MAE & Spearman & Kendall & hikn10 & MAE & Spearman & Kendall & hikn10 \\ \hline ants-1-1 & **202.743 \(\pm\)**0.435 & **0.748 \(\pm\)**0.019 & **0.571 \(\pm\)**0.018 & **6.633 \(\pm\)**0.964 & 207.561 \(\pm\) 2.603 & 0.500 \(\pm\) 0.145 & 0.357 \(\pm\) 0.105 & 2.900 \(\pm\) 1.197 \\ ants-2-2 & **8.932 \(\pm\)**0.37 & **0.830 \(\pm\)**0.021 & **0.650 \(\pm\)**0.023 & **6.767 \(\pm\)**0.568 & 14.558 \(\pm\) 1.373 & 0.421 \(\pm\) 0.165 & 0.303 \(\pm\) 1.24 & 4.800 \(\pm\) 1.229 \\ ants-2-1 & **2.196 \(\pm\)**0.117 & **0.485 \(\pm\)**0.05 & **0.349 \(\pm\)**0.023 & 4.54 \(\pm\) 0.777 & 3.941 \(\pm\) 0.877 & 0.246 \(\pm\) 0.199 & 0.186 \(\pm\) 0.121 & 3.22 \(\pm\) 0.632 \\ ants-2-2 & 25.091 \(\pm\) 0.693 & **0.699 \(\pm\)**0.047 & **0.529 \(\pm\)**0.042 & 5.767 \(\pm\) 1.223 & 25.541 \(\pm\) 1.825 & 0.554 \(\pm\) 0.111 & 0.378 \(\pm\) 0.093 & 5.1 \(\pm\) 1.101 \\ company-mails & **41.393 \(\pm\)**0.942 & **0.833 \(\pm\)**0.013 & **0.707 \(\pm\)**0.016 & 3.233 \(\pm\) 0.971 & 5.305 \(\pm\) 1.485 & 0.601 \(\pm\) 0.009 & 0.491 \(\pm\) 0.099 & 1.6 \(\pm\) 1.075 \\ e-email-4 & **3.915 \(\pm\)**0.165 & 0.388 \(\pm\)**0.059 & 0.290 \(\pm\) 0.206 & 3.003 \(\pm\) 1.377 & 5.671 \(\pm\) 2.52 & 0.332 \(\pm\) 0.14 & 0.254 \(\pm\) 0.121 & 4.1 \(\pm\) 1.955 \\ eu-email-2 & 3.072 \(\pm\) 0.14 & 0.511 \(\pm\) 0.061 & 0.391 \(\pm\) 0.018 & 2.807 \(\pm\) 1.332 & 3.424 \(\pm\) 0.174 & 0.421 \(\pm\) 0.097 & 0.325 \(\pm\) 0.077 & 4.6 \(\pm\) 1.506 \\ e-email-3 & **2.212 \(\pm\)**0.094 & **0.566 \(\pm\)**0.023 & **0.446 \(\pm\)**0.021 & 3.53 \(\pm\) 1.377 & 3.308 \(\pm\) 0.47 & 0.295 \(\pm\) 0.182 & 0.230 \(\pm\) 0.134 & 4.4 \(\pm\) 2.055 \\ sp-hoptrial & 48.827 \(\pm\) 1.377 & 0.743 \(\pm\) 0.036 & 0.546 \(\pm\) 0.033 & 5.14 \(\pm\) 1.296 & **3.874 \(\pm\)**3.474 & 0.733 \(\pm\) 0.029 & 0.579 \(\pm\) 0.032 & 5.6 \(\pm\) 1.578 \\ sp-hoptrial & **10.802 \(\pm\)**0.277 \(\pm\)**1.872 & 0.792 \(\pm\) 0.024 & 0.605 \(\pm\) 0.027 & 5.367 \(\pm\) 1.299 & **3.745 \(\pm\)**3.364 & 0.802 \(\pm\) 0.027 & 0.617 \(\pm\) 0.027 & 5.5 \(\pm\) 1.088 \\ sp-norqlence & 52.506 \(\pm\) 1.479 & 0.629 \(\pm\) 0.041 & 0.454 \(\pm\) 0.023 & 4.097 \(\pm\) 0.491 & **4.145 \(\pm\)**0.58 & 0.723 \(\pm\) 0.065 & 0.517 \(\pm\) 0.058 & 5.1 \(\pm\) 1.101 \\ sp-highschool & **72.697 \(\pm\)**0.169 & 0.743 \(\pm\) 0.018 & 0.505 \(\pm\) 0.050 & **4.567 \(\pm\)**1.104 & 145.323 \(\pm\) 0.512 & **0.860 \(\pm\)**0.010 & **0.678 \(\pm\)**0.002 & 1.200 \(\pm\) 0.422 \\ haggle & **16.635 \(\pm\)**0.399 & **0.755 \(\pm\)**0.005 & **0.618 \(\pm\)**0.006 & 5.4 \(\pm\) 0.983 & 19.266 \(\pm\) 1.043 & 0.637 \(\pm\) 0.034 & 0.520 \(\pm\) 0.043 & 6.8 \(\pm\) 1.229 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Results for prediction of temporal betweenness centrality

\begin{table}
\begin{tabular}{l|c c c c|c c c c} \hline \hline \multicolumn{1}{c|}{\multirow{2}{*}{Experiment}} & \multirow{2}{*}{MAE} & \multicolumn{2}{c}{DBGNN} & \multicolumn{2}{c}{GCN} \\ \cline{2-10}  & MAE & Spearman & Kendall & hikn10 & MAE & Spearman & Kendall & hikn10 \\ \hline ants-1-1 & **4.306 \(\pm\)**0.269 & **0.931 \(\pm\)**0.005 & **0.790 \(\pm\)**0.008 & **8.533 \(\pm\)**0.629 & 10.514 \(\pm\) 1.082 & 0.422 \(\pm\) 0.092 & 0.288 \(\pm\) 0.066 & 3.100 \(\pm\) 1.101 \\ ants-1-2 & **1.466 \(\pm\)**0.083 & **0.966 \(\pm\)**0.005 & **0.841 \(\pm\)**0.012 & **6.667 \(\pm\)**0.479 & 5.829 \(\pm\) 0.662 & 0.311 \(\pm\) 0.138 & 0.215 \(\pm\) 0.095 & 2.800 \(\pm\) 0.0919 \\ ants-2-1 & **0.852 \(\pm\)**0.026 & **0.981 \(\pm\)**0.003 & **0.985 \(\pm\)**0.01 & **8.400 \(\pm\)**0.
highlights differences between static and temporal centralities that are likely due to the underlying temporal patterns, and shows that our model is generally better at predicting temporal closeness compared to betweenness. An evaluation of scalability reveals that our model offers training and inference times that are comparable to those of a simpler GCN model, while yielding better performance. We finally investigate the (static) embeddings produced by the last message passing layer of our architecture and show that they better capture temporal centralities compared to a GCN model.

While we hope that our work is of interest for the Temporal Graph Learning community, this workshop paper necessarily leaves open questions that we will address in future work. A first limitation is that -due to time constraints- we did not perform a comprehensive hyperparameter exploration. This affects multiple aspects of our analysis, such as the investigation of multiple values for the maximum time difference \(\delta\), the maximum order \(k\) of the De Bruijn graphs used in the DBGNN architecture, as well as the number and width of graph convolutional layers. While we do report optimal values across three learning rates for all models, a more thorough investigation of this hyperparameter must be considered future work. A second open issue is the comparison of our approach to a more comprehensive choice of baselines. This comparison should include additional time-neglecting GNN architectures like Graph Attention Networks (GAT) [50], Graph Isomorphism Networks (GINs) [51] or embedding techniques like DeepWalk [52] or node2vec [53]. Moreover, we miss a comparison against other time-aware representation learning techniques like, e.g., HONEM [54] or EVO [55]. While we did not utilize additional node features like, e.g., degrees, static centralities, or embeddings, we expect that including such features could further improve our results.

In the light of these open issues, the investigation presented for the first time in this workshop paper must necessarily appear preliminary. We nevertheless hope that our work shows that the prediction of temporal centralities is an interesting problem for temporal graph learning, which could potentially be included in community-based benchmarks like TGB [17]. Moreover our study highlights the potential of using _compact, static but time-aware graph neural network architectures_ for node-level regression tasks in time series data on temporal graphs. We thus hope that our work is of interest for the Temporal Graph Learning community and we would appreciate feedback and suggestions.

Ingo Scholtes acknowledges support by the Swiss National Science Foundation (SNF), grant number 176938. The authors would also like to thank Lisi Qarkaxhija for the valuable feedback on the code of the DBGNN model.
