2.1 Node update

Each event between any pair of nodes u, v triggers an update of node embeddings $$ {\mathbf{z}}_u^t,{\mathbf{z}}_v^t\in {\mathbb{R}}^d$$ followed by an update of temporal attention $$ S^t\in {\mathbb{R}}^{N\times N}$$ in a recursive way (Fig 2). That is, updated node embeddings affect temporal attention, which in turn affects node embeddings at the next time step. In particular, the embedding of node v, and analogously node u, is updated based on the following three terms:

Fig 2

A recursive update of node embeddingsz and temporal attention S.

An event between nodes u = 1 and v = 3 creates a temporary edge that allows the information to flow (in pink arrows) from neighbors of node u to node v. Orange edges denote updated attention values. Normalization of attention values to sum to one can affect attention of neighbors of node v. Dotted edges denote absent edges (or edges with small values).

Attention-based term

We highlight the importance of the first term, which is affected by temporal attention S^t−1 between node u and all its one-hop neighbors $$ {\mathcal{N}}_u^{t-1}$$ [14]:

where f is an aggregator and $$ W^{\text{h}}\in {\mathbb{R}}^{d\times d}$$ are learned parameters. Note that features of node u’s neighbors are used to update node v’s embedding, which can be interpreted as creating a temporal edge by which node features propagate between the two nodes. The amount of information propagated from node u’s neighbors is controlled by attention S^t−1, which we suggest to learn as described in Section 3.

The other two terms in (2) include a recurrent update of node v’s features and a function of the waiting time between the current event and the previous event involving node v.

2.2 Attention update

In DyRep, attention S^t between nodes u, v depends on three terms: 1) long term associations A^t−1; 2) attention S^t−1 at the previous time step; and 3) conditional intensity $$ {\lambda }_{k,u,v}^t$$ (for simplicity denoted as $$ {\lambda }_k^t$$ hereafter) of events between nodes u and v, which in turn depends on their embeddings:

Conditional intensity λ

Conditional intensity $$ {\lambda }_k^t$$ represents the instantaneous rate at which an event of type k (i.e., association or communication) occurs between nodes u and v in the infinitesimally small interval (τ, τ + δτ] [40]. DyRep formulates the conditional intensity as a softplus function of the concatenated learned node representations $$ {\mathbf{z}}_u^{t-1},{\mathbf{z}}_v^{t-1}\in {\mathbb{R}}^d$$:

where ψ_k is the scalar trainable rate at which events of type k occur, and $$ {\omega }_k\in {\mathbb{R}}^{2d}$$ is a trainable vector that represents the compatibility between nodes u and v at time t; [⋅, ⋅] is the concatenation operator. Combining (5) with (4), we can notice that $$ S_{u,v}^t$$ implicitly depends on the embeddings of nodes u and v.

In DyRep, λ is mainly used to compute the loss and optimize the model, so that its value between nodes involved in the events should be high, whereas between other nodes it should be low.

But λ also affects attention values using a hard-coded algorithm, which makes several assumptions (see Algorithm 1 in [14]). In particular, in the case of a communication event (k = 1) between nodes u and v, attention S^t is only updated if an association exists between them ($$ A_{u,v}^{t-1}=1$$). Secondly, to compute attention between nodes u and v, only their one-hop neighbors at time t − 1 are considered. Finally, no learned parameters directly contribute to attention values, which can limit information propagation, especially in case of imperfect associations A^t−1.

In this paper, we extend the DyRep model in two ways. First, we examine the benefits of learned attention instead of the DyRep’s algorithm in (4) by using a variational autoencoder, more specifically its encoder part, from NRI [15]. This permits learning of a sparse representation of the interactions between nodes instead of using a hard-coded function f_S and known adjacency matrix A (Section 3.1). Second, both the original DyRep work [14] and [15] use concatenation to make predictions for a pair of nodes (see (5) above and (6) in [15]), which only captures relatively simple relationships. We are interested in the effect of allowing a more expressive relationship to drive graph dynamics, and specifically to drive temporal attention (Sections 3.1 and 3.2). We demonstrate the utility of our model by applying it to the task of dynamic link prediction on two graph datasets (Section 4).

3.1 Bilinear encoder

DyRep’s encoder (4) requires a graph structure represented as an adjacency matrix A. We propose to replace this with a sequence of learnable functions $$ f_S^{\text{enc}}$$, borrowed from [15], that only require node embeddings as input:

(7): $$ f_{\text{node}}^1$$ transforms embeddings of all nodes;

(8): $$ f_{\text{edge}}^1$$ is a “node to edge” mapping that returns an edge embedding $$ {\mathbf{h}}_{(i,j)}^1$$ for all pairs of nodes (i, j);

(9): $$ f_{\text{node}}^2$$ is an “edge to node” mapping that updates the embedding of node j based on its all incident edges;

(10): $$ f_{\text{edge}}^2$$ is similar to the “node to edge” mapping in the first pass, $$ f_{\text{edge}}^1$$, but only the edge embedding between nodes u and v involved in the event is used.

Fig 4

Inferring an edge $$ S_{u,v}^t$$ of our latent dynamic graph (LDG) using two passes, according to (7)–(10), assuming an event between nodes u = 1 and v = 3 has occurred.

Even though only nodes u and v have been involved in the event, to infer the edge $$ S_{u,v}^t$$ between them, interactions with all nodes in a graph are considered.

The softmax function is applied to the edge embedding $$ {\mathbf{h}}_{(u,v)}^2$$, which yields the edge type posterior as in NRI [15]:

Replacing (4) with (5) means that it is not necessary to maintain an explicit representation of the human-specified graph in the form of an adjacency matrix. The evolving graph structure is implicitly captured by S^t. While S^t represents temporal attention weights between nodes, it can be thought of as a graph evolving over time, therefore we call our model a Latent Dynamic Graph (LDG). This graph, as we show in our experiments, can have a particular semantic interpretation.

The two passes in (7)–(10) are important to ensure that attention $$ S_{u,v}^t$$ depends not only on the embeddings of nodes u and v, $$ {\mathbf{z}}_u^{t-1}$$ and $$ {\mathbf{z}}_v^{t-1}$$, but also on how they interact with other nodes in the entire graph. With one pass, the values of $$ S_{u,v}^t$$ would be predicted based only on local information, as only the previous node embeddings influence the new edge embeddings in the first pass (8). This is one of the core differences of our LDG model compared to DyRep, where $$ S_{u,v}^t$$ only depends on $$ {\mathbf{z}}_u^{t-1}$$ and $$ {\mathbf{z}}_v^{t-1}$$ (see (4)).

Unlike DyRep, the proposed encoder generates multiple edges between nodes, i.e., $$ S_{u,v}^t$$ are one-hot vectors of length r. We therefore modify the “Attention-based” term in (2), such that features $$ h_u^{\text{S},t-1}$$ are computed for each edge type and parameters W^S act on concatenated features from all edge types, i.e., $$ W^{\text{S}}\in {\mathbb{R}}^{rd\times d}$$.

3.2 Bilinear intensity function

Earlier in (5) we introduced conditional intensity $$ {\lambda }_k^t$$, computed based on concatenating node embeddings. We propose to replace this concatenation with bilinear interaction:

Why bilinear? Bilinear layers have proven to be advantageous in settings like Visual Question Answering (e.g., [41]), where multi-modal embeddings interact. It takes a form of xWy, so that each weight W_ij is associated with a pair of features x_i,y_j, where i, j ∈ d and d is the dimensionality of features x and y. That is, the result will include products x_iW_ijy_j. In the concatenation case, the result will only include x_iW_i, y_jW_j, i.e. each weight is associated with a feature either only from x or from y, not both. As a result, bilinear layers have some useful properties, such as separability [42]. In our case, they permit a richer interaction between embeddings of different nodes. So, we replace NRI’s and DyRep’s concatenation layers with bilinear ones in (8), (10) and (12).

3.3 Training the LDG model

Given a minibatch with a sequence of $$ \mathcal{P}$$ events, we optimize the model by minimizing the following cost function:

The first two terms, $$ {\mathcal{L}}_{\text{events}}$$ and $$ {\mathcal{L}}_{\text{nonevents}}$$, were proposed in DyRep [14] and we use them to train our baseline models. The KL divergence term, adopted from NRI [15] to train our LDG models, regularizes the model to align predicted q_ϕ(S|Z) and prior p_θ(S) distributions of attention over edges. Here, p_θ(S) can, for example, be defined as [θ₁, θ₂, …, θ_r] in case of r edge types.

Following [15], we consider uniform and sparse priors. In the uniform case, θ_i = 1/r, i = 1, …, r, such that the KL term becomes the sum of entropies H over the events $$ p=[1,\dots ,\mathcal{P}]$$ and over the generated edges excluding self-loops (u ≠ v):

In case of sparse p_θ(S) and, for instance, r = 2 edge types, we set p_θ(S) = [0.90, 0.05, 0.05], meaning that we generate r + 1 edges, but do not use the non-edge type corresponding to high probability, and leave only r sparse edges. In this case, the KL term becomes:

4.1 Datasets

We evaluate our model on the link (event) prediction task using two datasets (Table 2). Source code is available at https://github.com/uoguelph-mlrg/LDG.

Table 2

Datasets statistics used in experiments.

Dataset	Social Evolution	Github
# nodes	83	284
# initial associations	575	149
# final associations	708	710
# train comm events	43,469	10,604
# train assoc events	365	1,040
# test comm events	10,462	8,667
# test assoc events	73	415

Social Evolution [16]. This dataset consists of over one million events o^t = (u, v, τ, k). We preprocess this dataset in a way similar to [14]. A communication event (k = 1) is represented by the sending of an SMS message, or a Proximity or Call event from node u to node v; an association event (k = 0) is a CloseFriend record between the nodes. We also experiment with other associative connections (Fig 5). As Proximity events are noisy, we filter them by the probability that the event occurred, which is available in the dataset annotations. The filtered dataset on which we report results includes 83 nodes with around 43k training and 10k test communication events. As in [14], we use events from September 2008 to April 2009 for training, and from May to June 2009 for testing.

Fig 5

Predicting links by leveraging training data statistics without any learning (“no learn”) turned out to be a strong baseline.

We compare it to learned models with different human-specified graphs used for associations. Here, for the Social Evolution dataset the abbreviations are following: Blog: BlogLivejournalTwitter, Cf: CloseFriend, Fb: FacebookAllTaggedPhotos, Pol: PoliticalDiscussant, Soc: SocializeTwicePerWeek, Random: Random association graph.

GitHub. This dataset is provided by GitHub Archive and compared to Social Evolution is a very large network with sparse association and communication events. To learn our model we expect frequent interactions between nodes, therefore we extract a dense subnetwork, where each user initiated at least 200 communication and 7 association events during the year of 2013. Similarly to [14], we consider Follow events in 2011-2012 as initial associations, but to allow more dense communications we consider more event types in addition to Watch and Star: Fork, Push, Issues, IssueComment, PullRequest, Commit. This results in a dataset of 284 nodes and around 10k training events (from December to August 2013) and 8k test events (from September to December 2013).

We evaluate models only on communication events, since the number of association events is small, but we use both for training. At test time, given tuple (u, τ, k), we compute the conditional density of u with all other nodes and rank them [14]. We report Mean Average Ranking (MAR) and HIST@10: the proportion of times that a test tuple appears in the top 10.

4.2 Implementation details

We train models with the Adam optimizer [44], with a learning rate of 2×10⁻⁴, minibatch size $$ \mathcal{P}=200$$ events, and d = 32 hidden units per layer, including those in the encoder (7)–(10). We consider two priors, p_θ(S), to train the encoder: uniform and sparse with r = 2 edge types in each case. For the sparse case, we generate r + 1 edges, but do not use the non-edge type corresponding to high probability and leave only r sparse edges. We run each experiment 10 times and report the average and standard deviation of MAR and HIST@10 in Table 3. We train for 5 epochs with early stopping. To run experiments with random graphs, we generate S once in the beginning and keep it fixed during training. For the models with learned temporal attention, we use random attention values for initialization, which are then updated during training (Fig 6).

Fig 6

An adjacency matrix of the latent dynamic graph (LDG), S^t, for one of the sparse edge types generated at the end of training, compared to randomly initialized S^t and associative connections available in the Social Evolution dataset at the beginning (top row) and end of training (bottom row).

A quantitative comparison is presented in Table 3.

Table 3

We proposed models with bilinear interactions and learned temporal attention. Bolded results denote best performance for each dataset. Comparison to other baselines and ablation studies are presented in Tables 4 and 5.

Results on the Social Evolution and GitHub datasets in terms of MAR and HITS@10 metrics.

	Model	Learned attention	MAR ↓		HITS@10 ↑
			Concat	Bilinear	Concat	Bilinear
Social Evolution	GCN (CloseFriend)	✘	27.1 ± 0.6	29.4 ± 2.6	0.42 ± 0.01	0.33 ± 0.05
	GAT (CloseFriend)	✘	48.2 ± 5.0	52.4 ± 2.6	0.09 ± 0.04	0.07 ± 0.02
	DyRep (CloseFriend)	✘	16.0 ± 3.0	11.0 ± 1.2	0.47 ± 0.05	0.59 ± 0.06
	DyRep (Fb)	✘	20.7 ± 5.8	15.0 ± 2.0	0.29 ± 0.21	0.38 ± 0.14
	LDG (random, uniform)	✘	19.5 ± 4.9	16.0 ± 3.3	0.28 ± 0.19	0.35 ± 0.17
	LDG (random, sparse)	✘	21.2 ± 4.4	17.1 ± 2.6	0.26 ± 0.10	0.37 ± 0.08
	LDG (learned, uniform)	✔	22.6 ± 6.1	16.9 ± 1.1	0.18 ± 0.09	0.37 ± 0.06
	LDG (learned, sparse)	✔	17.0 ± 5.8	12.7 ± 0.9	0.37 ± 0.14	0.50 ± 0.06
GitHub	GCN (Follow)	✘	53.5 ± 1.9	53.8 ± 0.3	0.36 ± 0.00	0.36 ± 0.00
	GAT (Follow)	✘	107.1 ± 3.6	111.5 ± 3.9	0.21 ± 0.02	0.20 ± 0.01
	DyRep (Follow)	✘	100.3 ± 10	73.8 ± 5.0	0.187 ± 0.01	0.221± 0.02
	LDG (random, uniform)	✘	90.3 ± 17.1	68.7 ± 3.3	0.21 ± 0.02	0.24 ± 0.02
	LDG (random, sparse)	✘	95.4 ± 14.9	71.6 ± 3.9	0.20 ± 0.01	0.23 ± 0.01
	LDG (learned, uniform)	✔	92.1 ± 15.1	66.6 ± 3.6	0.20 ± 0.02	0.27 ± 0.03
	LDG (learned, sparse)	✔	90.9 ± 16.8	67.3 ± 3.5	0.21 ± 0.03	0.28 ± 0.03
	LDG (learned, sparse) + Freq	✔	47.8 ± 5.7	43.0 ± 2.8	0.48 ± 0.03	0.50 ± 0.02

We also train two simple baselines based on GCN [8] and GAT [45]. Both of them have three graph convolutional layers with 32 hidden units in each layer and the GAT has 4 attention heads. To train these baselines, in the first training iteration we propagate the initial node embeddings through the GCN or GAT using the association graph at the current timestamp obtaining node embeddings z. We then use z to compute intensity λ for all events in the minibatch according to (5) or (12) and afterwards the baseline DyRep loss (the first two terms in (13)). For the following training iteration, the input to the GCN or GAT are the output embeddings from the previous training iteration, which allows the embeddings to evolve during training. The main limitation of theses baselines compared to DyRep or LDG is that the communication events are only used to compute λ and do not define the node propagation scheme neither during training or testing.

4.3 Quantitative evaluation

On Social Evolution, we report results of the baseline DyRep with different human-specified associations and compare them to the models with learned temporal attention (LDG) (Table 3, Fig 5). Models with learned attention perform better than most of the human-specified associations, further confirming the finding from [15] that the underlying graph can be suboptimal. However, these models are still slightly worse compared to CloseFriend, which means that this graph is a strong prior. We also show that bilinear DyRep and LDG models consistently improve results and exhibit better training behaviour, including when compared to a larger linear model with an equivalent number of parameters (Fig 7).

Fig 7

(a) Training curves and test MAR for baseline DyRep, bilinear DyRep, and larger baseline DyRep, with a number of trainable parameters equal to the bilinear DyRep. (b) Training curves and test MAR for the bilinear LDG with sparse prior, showing that all three components of the loss (see (13)) generally decrease or plateau, reducing test MAR.

Both DyRep and LDG also outperform simple GCN and GAT baselines, which confirms the importance of modeling the dynamics of both association and communication events. Among these baselines, GAT shows significantly worse results. This can be explained by the difficulty of training attention heads in the GAT. These baselines also often diverge when combined with the bilinear intensity function and so we had to apply additional squashing of embeddings (see our implementation for full details). Therefore, in these cases, bilinear models underperform.

GitHub is a more challenging dataset with more nodes and complex interactions, so that the baseline DyRep model has a very large MAR of 100 (random predictions have the MAR of around 140). On this dataset, bilinear DyRep and LDG models provide a much larger gain, while models with learned attention further improve results. The baseline DyRep model using Follow associations is performing poorly, even compared to our model with randomly initialized graphs. These results imply that we should either carefully design graphs or learn them jointly with the rest of the model as we do in our work.

Surprisingly, on this dataset, the GCN baseline outperform DyRep and LDG. This can be due to a certain artifact in the dataset or that there exists a simple pattern of events, and more complex models cannot capture them. Note that while GCN is better than LDG in this case, the GCN model leverages the ground truth association graph, which is unavailable to the LDG.

We compare our implementation of DyRep to [14] and other static and dynamic models (Table 4). Our results are worse than those reported in [14] due to the possible implementation differences (no source code of [14] is available) and different preprocessing steps of the Social Evolution dataset. However, we highlight that our results are still significantly better than other baselines.

Table 4

Comparison of our DyRep implementation to other baselines on the Social Evolution dataset.

Model	MAR ↓	HITS@10 ↑
GraphSage [14, 46]	37.0†	0.12†
KnowEvolve [14, 47]	30.0†	0.25†
DynGem [14, 28]	52.0†	0.01†
DyRep [14]	6.0†	0.95†
DyRep (our implementation)	16.0	0.47

^†According to the results shown on the plots in [14].

We also perform additional ablation studies of our LDG (Table 5). In particular, we report the results of using the bilinear transformation only for the encoder (NRI) components or only for computing the conditional intensity. The results suggest a more important role of the latter. While using the bilinear form only for the NRI component degrades the performance, combining it with the bilinear intensity function leads to the best results. The results of our LDG without or with the bilinear transformation on the GitHub dataset are presented in Table 3.

Table 5

The effect of the bilinear transformation when used in different components of our LDG model on the Social Evolution dataset.

Model	MAR ↓	HITS@10 ↑
DyRep	16.0	0.47
DyRep+bilinear λ	11.0	0.59
LDG	17.0	0.37
LDG+bilinear NRI ((7))-(10)	17.9	0.38
LDG+bilinear Ω (12)	13.5	0.48
LDG+bilinear Ω and NRI	12.7	0.50

4.4 Interpretability of learned attention

While the models with a uniform prior have better test performance than those with a sparse prior in some cases, sparse attention is typically more interpretable. This is because the model is forced to infer only a few edges, which must be strong since that subset defines how node features propagate (Table 6). In addition, relationships between people in the dataset tend to be sparse. To estimate agreement of our learned temporal attention matrix with the underlying association connections, we take the matrix S^t generated after the last event in the training set and compute the area under the ROC curve (AUC) between S^t and each of the associative connections present in the dataset.

Table 6

CloseFriend is highlighted as the relationship closest to our learned graph.

Edge analysis for the LDG model with a learned graph using the area under the ROC curve (AUC, %); random chance AUC = 50%.

Associative Connection	Initial		Final
	Uniform	Sparse	Uniform	Sparse
BlogLivejournalTwitter	53	57	57	69
CloseFriend	65	69	76	84
FacebookAllTaggedPhotos	55	57	58	62
PoliticalDiscussant	59	63	61	68
SocializeTwicePerWeek	60	66	63	70
Github Follow	79	80	85	86

These associations evolve over time, so we consider initial and final associations corresponding to the first and last training events. AUC is used as opposed to other metrics, such as accuracy, to take into account sparsity of true positive edges, as accuracy would give overoptimistic estimates. We observe that LDG learns a graph most similar to CloseFriend. This is an interesting phenomenon, given that we only observe how nodes communicate through many events between non-friends. Thus, the learned temporal attention matrix is capturing information related to the associative connections.

We also visualize temporal attention sliced at different time steps and can observe that the model generally learns structure similar to human-specified associations (Fig 8). However, attention can evolve much faster than associations, which makes it hard to analyze in detail. Node embeddings of bilinear models tend to form more distinct clusters, with frequently communicating nodes generally residing closer to each other after training (Fig 9). We notice bilinear models tend to group nodes in more distinct clusters. Also, using the random edges approach clusters nodes well and embeds frequently communicating nodes close together, because the embeddings are mainly affected by the dynamics of communication events.

Fig 8

Final associations of the subgraphs for the Social Evolution (top row) and GitHub (bottom row) datasets compared to attention values at different time steps selected randomly.

Fig 9

tSNE node embeddings after training (coordinates are scaled for visualization) on the Social Evolution dataset.

Lines denote associative or sampled edges. Darker points denote overlapping nodes. Red, green, and cyan nodes correspond to the three most frequently communicating pairs of nodes, respectively.

4.5 Leveraging the dataset bias

While there can be complex interactions between nodes, some nodes tend to communicate only with certain nodes, which can create a strong bias. To understand this, we report results on the test set, which were obtained simply by computing statistics from the training set (Fig 5).

For example, to predict a link for node u at time τ, we randomly sample node v from those associated with u. In the Random case, we sample node v from all nodes, except for u. This way we achieve high performance in some cases, e.g., MAR = 11 by exploiting SocializeTwicePerWeek, which is equivalent to learned DyRep. This result aligns with our intuition that people who socialize with each other tend to communicate more, whereas such associations as friends tend to be stronger, longer term relationships that do not necessary involve frequent communications.

Another bias present in the datasets is the frequency bias, existing in many domains, e.g. visual relationship detection [48]. In this case, to predict a link for node u at time τ we can predict the node with which it had most of communications in the training set. On GitHub this creates a very strong bias with performance of MAR = 58. We combine this bias with our LDG model by averaging model predictions with the frequency distribution and achieve our best performance of MAR = 45. Note that this bias should be used carefully as it may not generalize to another test set. A good example is the Social Evolution dataset, where communications between just 3-4 nodes correspond to more than 90% of all events, so that the rank of 1-2 can be easily achieved. However, such a model would ignore potentially changing dynamics of events at test time. Therefore, in this case the frequency bias is exploiting the limitation of the dataset and the result would be overoptimistic. In contrast the DyRep model and our LDG model allow node embeddings to evolve over time based on current dynamics of events, so that it can adapt to such changes.