Temporal motif-based attentional graph convolutional network for dynamic link prediction

Abstract

Dynamic link prediction is an important component of the dynamic network analysis with many real-world applications. Currently, most advancements focus on analyzing link-defined neighborhoods with graph convolutional networks (GCN), while ignoring the influence of higher-order structural and temporal interacting features on link formation. Therefore, based on recent progress in modeling temporal graphs, we propose a novel temporal motif-based attentional graph convolutional network model (TMAGCN) for dynamic link prediction. As dynamic graphs usually contain periodical patterns, we first propose a temporal motif matrix construction method to capture higher-order structural and temporal features, then introduce a spatial convolution operation following a temporal motif-attention mechanism to encode these features into node embeddings. Furthermore, we design two methods to combine multiple temporal motif-based attentions, a dynamic attention-based method and a reinforcement learning-based method, to allow each individual node to make the most of the relevant motif-based neighborhood to propagate and aggregate information in the graph convolutional layers. Experimental results on various real-world datasets demonstrate that the proposed model is superior to state-of-the-art baselines on the dynamic link prediction task. It also reveals that temporal motif can manifest the essential dynamic mechanism of the network.

Keywords

Dynamic link prediction graph convolutional network temporal motif

1. Introduction

A network,1

¹
Graph and network can be used interchangeably.

represented as graph-structured data, is a collection of nodes representing entities and links indicating connections. It can effectively model various types of associations in the real world, including social networks [1, 2], knowledge networks [3], and biological networks [4], etc. Graph-structured data is pervasive in information processing. It can be used to efficiently store and access relational knowledge about interactive entities. For example, in a social network, a node can represent a person, and nodes are connected with links indicating how people interact with each other. Analysis of the graph-structured data provides insights into patterns of underlying social activities.

Link prediction, considered as one of the vital tasks in various data mining applications, has drawn attention for decades and several methods have been applied in this domain [5]. These methods can be classified into substantial types such as similarity-based indices, probabilistic methods, content-based methods, and embedding-based methods, etc. A majority of the previous approaches mainly focus on static graphs without considering the graph evolution. However, many graphs in real-world applications are intrinsically dynamic, in which links between nodes dynamically change over time [6]. Examples include academic co-authorship networks where authors may periodically switch their collaboration behaviors, and social networks where individual users may continuously change their association or communication relationships with others. Aiming to predict whether a link will form between two nodes in the future based on past network information, link prediction in dynamic networks has become a significant research topic in recent years. It is inherently challenging because continual complex interacting behaviors between nodes can give rise to the non-linear transformation of underlying structures. Conventional link prediction methods using neighborhood-based node similarities in static graph settings such as Common Neighbors (CN), Katz, Preferential Attachment (PA), Jaccard Coefficient (JC), have been adapted to dynamic networks by allowing the latent features to change over time [7, 8, 9, 10, 11, 12, 13]. These approaches represent dynamic graphs as a sequence of graph snapshots from different time stamps, and take advantage of historical information to predict links of the next moment. Although those methods often work well in the respect of computing complexity, they can hardly extract the hidden network structure and overcome the problem of low link prediction accuracy.

In order to model the non-linear transformation of network structure, some dynamic network embedding methods [1, 14, 15, 16, 17, 18] have been proposed to capture the dynamic evolution pattern. Recently, graph neural networks (GNNs) [19, 20, 21] for dynamic link prediction have emerged and achieved excellent results in many aspects. Typical methods [22, 23, 24, 25, 26] are to inject the dynamism into the parameters of GCN [27] through recurrent neural network (RNN). They use GCNs as a feature extractor and RNNs for sequence learning from the extracted features. One limitation of these methods is that none of them consider time at finer level and they fail to capture both topological evolution and interactions simultaneously. Most real-world graphs exhibit at least two distinct dynamic processes that evolve at different time scales: (a) Long-term association: the number of nodes and links are expected to grow (or shrink) over time leading to structural changes in the graph; (b) Communication: it relates to activities between nodes that may or may not be structurally connected. In order to capture both topological evolutions and interactions simultaneously, Trivedi et al. [28] proposed a two-time scale deep temporal point process model, i.e. DyRep, to capture the continuous-time fine-grained temporal dynamics of the two observed processes. Knyazev et al. [29] further extended DyRep by replacing concatenation with bilinear layers to permit more complex relationships between node representations, and this extension achieved the-state-of-art performance.

However, these methods only focus on the binary relationship (i.e., link) in the graph, and ignore the higher-order connectivity patterns (e.g., motifs) in the graph. In static networks, higher-order structural units such as motifs [30] are indicative and informative subgraph patterns recurring frequently in a graph, whose counts are significantly higher than that in random networks. In temporal networks, temporal motifs [31] are defined as induced subgraphs on sequences of temporal links. It has been proved that higher-order connectivity patterns such as network motifs are essential to understanding the fundamental mechanism that control and mediate the behavior of many complex systems [32, 33]. Therefore, temporal motifs can capture both temporal and structural features for dynamic link prediction.

Figure 1 is a toy example illustrating why higher-order structural and temporal information matters. In Fig. 1, three avatar nodes represent one boy student, one girl student and one tutor. At the present time ${{t}_{1}}$ , the boy student establishes a link to his tutor. The task is to predict links in the following time ${{t}_{2}}$ and ${{t}_{3}}$ . $\delta$ is a constant representing the time period. A typical blocking conversation between two individuals characterized by fast exchanges happening back and forth. A typical non-blocking conversation characterized by the individual communicating with others without waiting for instant replies from the first individual [31]. If the three nodes are in networks such as Short Messaging Service (SMS) networks where blocking communication is vastly more common, we have high confidence that after the boy student sends a question to his tutor at time ${{t}_{1}}$ , he will have a deep discussion with his tutor on some research topics at time ${{t}_{2}}$ and ${{t}_{3}}$ . If they are in networks such as e-mail communication networks, where non-blocking communication is prevalent, after submitting his homework to his tutor, he may exchange his ideas with the girl student before his tutor finishes checking his homework and giving a reply. All of the above useful information cannot be obtained via link-defined neighborhood instead of temporal motifs.

Figure 1.

An example to illustrate that nodes can benefit from using temporal motifs compared to link-defined neighborhood.

Inspired by recent work on attention mechanism, we propose a novel model, named temporal motif-based attentional graph convolutional network (TMAGCN), to incorporate such higher-order structural and temporal information into node embeddings for dynamic link prediction. The main contributions of this work are summarized as follows:

•

We develop a temporal network motif matrix construction method to capture higher-order structural and temporal features. The respective field around a target node of interest is defined by combining temporal motif matrix with adjacency matrix.

•

We propose a novel model, TMAGCN, to model interleaved evolution of two-time scale series processes from a graph-based perspective. To the best of our knowledge, it is the first time to bridge the gap between the power of graph neural network and temporal motif in dynamic link prediction study. Two methods to combine multiple temporal motif-based attention, a dynamic attention-based method and a reinforcement learning-based method, are proposed to allow each individual node to make the most of the relevant motif-based neighborhood to propagate and aggregate information in the graph convolutional layers for updating node embeddings.

•

We conduct extensive experiments to comprehensively evaluate TMAGCN on the dynamic link prediction task using various real-world datasets. Experimental results show that the proposed method consistently outperforms the state-of-the-art methods on dynamic graphs. Qualitative analysis through embedding visualization is further presented to show the effectiveness of TMAGCN.

The remainder of the paper is organized as follows. Section 2 discusses related work on dynamic link prediction and network motif. Section 3 formulates the preliminaries and some necessary definitions of the problem. Section 4 details the proposed TMAGCN. Section 5 presents datasets, experimental settings and the experimental results. Finally, the conclusion is drawn and possible directions for future work are outlined in Section 6.

2. Related work

This section will introduce recent advances in link prediction with a primary focus on representation learning methods for dynamic link prediction, as well as higher-order structures with network motifs.

Dynamic Link prediction.

Link prediction has been widely studied and successfully applied to several domains. Numerous methods of link prediction have been proposed and can be grouped into several categories, like topology-based similarity metrics, probabilistic and maximum likelihood-based models, dimensionality reduction-based methods, learning-based models, etc. [5] A majority of these methods were originally proposed for static graphs.

However, most real-world networks are actually dynamic and keep evolving with time [34]. The dynamic link prediction problem is more complex. Methods for dynamic graphs are often the extensions of those for static ones, with an additional focus on the temporal dimensions and update rules. Taking the topology-based similarity metrics as an example, the larger the similarity is, the more likely two nodes will establish a link. A bunch of dynamic link prediction technologies [7, 8, 9, 10, 11, 12, 13, 35] utilize the topology information of the network to define the similarity of nodes, named structural similarity indices, including local similarity indices and global similarity indices. For example, Günes et al. [9] leveraged a time series forecasting model to predict future similarity scores between nodes based on their past similarity score values. However, these similarity-based features sometimes cannot capture high-quality underlying characteristics of networks, as they ignore the dynamic evolution of the network at the previous moment and contains not ample but segmentary features of the evolving network. The dominant advantage of such methods is the computational efficiency, while the accuracy of those methods is not as high as expected if the links dynamically change over time. In addition to spatial features, there are also methods that learn temporal information of dynamic networks. Some methods [36, 37, 38] are designed to utilize a sequence of previous snapshots to predict future links. They integrate both structural and temporal information to model the dynamic evolution process. For example, Yu et al. [37] proposed a link prediction model with spatial and temporal consistency (LIST) to predict links in a sequence of networks over time. LIST characterizes the network dynamics as a function of time. It integrates the spatial topology of network at each timestamp and the temporal network evolution. Many researchers [16, 17, 39, 40, 41, 42] recently integrated time information into network embedding to make it capable of capturing the dynamic evolution of the network. Goyal et al. [39] proposed DyLink2Vec for the task of link prediction in a dynamic network, which considers the feature learning task as an optimal coding problem and the learning process as a two-step compression-reconstruction step. Zhou et al. [17] proposed a novel representational learning method, DynamicTriad, to preserve both the structural information and evolutionary patterns of a given network, so that the model can capture network dynamics and learn the representation vector for each node at different time steps. Xiao et al. [1] proposed a model based on network embedding, which combines network structure feature and user text feature to predict links. Due to the great success of GNNs in handling graph data, some researchers harness the power of GNNs to handle dynamic graph data [22, 23, 24, 25, 26]. For example, in order to predict both the added and removed links at the same time, Chen et al. [25] proposed a unified model, GC-LSTM, to make full use of GCN to learn network structure in hidden state and cell state, and learn temporal feature of network through LSTM model. Lei et al. introduced a novel model GCN-GAN [26] to tackle the challenging temporal link prediction task, which combines the strengths of the GCN and LSTM in learning the comprehensive distributed representations of networks as well as the generative adversarial network (GAN) in generating high-quality weighted links. One limitation of these methods is that none of them consider time at finer level and do not capture both topological evolution and interactions simultaneously. Recent researches [28, 29] try to capture both topological evolution and interactions simultaneously with a two-time scale deep temporal point process model, and achieve the-state-of-art performance. However, all the GCN-based methods mentioned above primarily focus more on link-based node features but less on graph structures within the neighborhood, especially higher-order structural patterns named motifs.

Network motif.

Network motifs are fundamental building blocks of complex networks [30]. Investigations of such patterns usually lead to the discovery of meaningful connectivity patterns and understanding the dynamic mechanisms of complex systems. Motifs have been used successfully in static network analysis for a wide range of applications such as bioinformatics [43], neuroscience [44], scholar networks [45], and social networks [46, 47]. Multiple works have demonstrated that it is useful to explore the motifs in different graph-based ML tasks [32, 33, 48], such as node classification [49], node ranking [50, 51], community detection [52] and graph classification [53] tasks. Rossi et al. [32] proposed the notion of higher-order network embeddings, and demonstrated that one can learn better embeddings when various motif-based matrix formulations are considered. Paranjape et al. [31] found that temporal motif counts reveal key structural patterns in networks, and networks from different domains tend to exhibit very different organizational structures, whereas networks from the same domain tend to have similar structure. Zhao et al. [50] proposed a novel framework, motif-based PageRank (MPR), to incorporate higher-order structures into conventional PageRank computation. Our work extends but differs from previous approaches [28, 29, 31, 32, 50]. We employ temporal motifs to define the receptive field around a target node of interest both in spatial and temporal dimensions for graph convolution. Specifically, we propose a novel GCN which utilizes temporal motif-based attention for dynamic link prediction.

3. Preliminaries

3.1 Notations

Table 1 lists the mathematical symbols frequently used in model description. Upper-case bold letters denote matrices, lower-case bold letters represent vectors, and non-bold italicized letters for scalars.

Table 1
Table of notations

Symbol	Meaning
${{\mathsf{\mathcal{G}}}_{t}}$	A temporal graph ${{\mathsf{\mathcal{G}}}_{t}}=({{\mathsf{\mathcal{V}}}_{t}},{{\mathsf{\mathcal{% E}}}_{t}})$ which contains a collection of continuous time-ordered temporal links ${{\mathsf{\mathcal{E}}}_{t}}$ and the set of nodes ${{\mathsf{\mathcal{V}}}_{t}}$ up to time $t$ , where $t\in\mathbb{R}$ , ${{t}_{0}}\leqslant t\leqslant T$ is a discrete index at a continuous time point $\tau$ .
$N$	Number of nodes in temporal graph ${{\mathsf{\mathcal{G}}}_{t}}$ .
$\mathsf{\mathcal{M}}$	The set $\{{{M}_{1}},\ldots,{{M}_{K}}\}$ of $K$ types of temporal network motifs.
${{\mathbf{A}}^{(k)}}(t)$	$N\times N$ motif-induced adjacency matrix corresponding to motif ${{M}_{k}}$ at time $t$ . $\mathbf{A}_{uv}^{(k)}(t)$ encodes the number of motifs of type ${{M}_{k}}$ in which $(u,v)\in E(t)$ . When the subscript $k$ is equal to 0, this refers to the default link-defined adjacency matrix.
${{D}^{(l)}}$	Number of dimensions of node feature embedding in the $l$ -th layer, where ${{D}^{(0)}}$ is the number of initial features or attributes per node.
$\mathbf{X}$	$N\times{{D}^{(0)}}$ initial attribute matrix.
${{\mathbf{H}}^{(l)}}(t)$	Node feature embedding matrix inputted in the $l$ -th layer at time $t$ ; ${{\mathbf{H}}^{(0)}}(t)=\mathbf{X}$ . ${{\mathbf{h}}_{u}}^{(l)}(t)\in{{\mathbb{R}}^{N\times D}}$ is the $u$ -th row of ${{\mathbf{H}}^{(l)}}(t)$ corresponding to the embedding of node $u$ .
${{\mathbf{W}}^{(l)}}$	${{D}^{(l)}}\times{{D}^{(l+1)}}$ trainable parameter matrix in the $l$ -th layer.
$\Gamma_{u}^{({{{\mathbf{A}}}^{(k)}}(t))}(t)$	The set of neighbors of node $u$ with respect to adjacency matrix ${{\mathbf{A}}^{(k)}}(t)$ .
${{\alpha}_{uv}}$	Weight coefficient that indicates the importance or contribution of neighbor node $v$ ’s features to node $u$ .
${{\mathbf{S}}^{(l)}}$	Node state matrix at layer $l$ with ${{S}^{(l)}}$ dimensions of the state-space in each row.
$\lambda_{uv}^{r}({{t}_{i}})$	The conditional intensity function that models the instantaneous rate at which a link of type $r$ (an association or communication event) occurs between nodes $u$ and $v$ in the infinitesimally tiny interval $[{{t}_{i}},{{t}_{i}}+\text{d}t)$ .

3.2 Problem formulation

The central goal of this work is to predict links in temporal graphs. DyRep [28] assumes that temporal graphs evolve according to two fundamental processes:

•
Association processes (dynamic of the network) which bring changes in the graph structure and lead to long lasting stable relationship between nodes.
•
Communication processes (dynamic on the network) which relate to activities leading to temporary information flow between nodes.

These two kinds of processes are realized in the form of sequential events observed between nodes over a temporal window $t\in[{{t}_{0}},T]$ , fully describing information transfer between nodes. We model real-world events of these two processes in the form of timestamped directed links between ordered pairs of nodes on graph. Let a temporal link $e=\{u,v,t,r\}$ denotes an event of type $r\in\{0,1\}$ , where $u$ and $v$ are two nodes involved in an event, $t$ represents time of the event, $r=0$ corresponds to the association process and $r=1$ corresponds to the communication process. Graphs describe the relationships among entities in a network. We give formal definitions of graph-related concepts below.

Definition 1 (temporal graph). A temporal graph is formulated as ${{\mathsf{\mathcal{G}}}_{{{t}_{m}}}}=({{\mathsf{\mathcal{V}}}_{{{t}_{m}}}},{{% \mathsf{\mathcal{E}}}_{{{t}_{m}}}})$ , which contains a collection of continuous time-ordered temporal links ${{\mathsf{\mathcal{E}}}_{{{t}_{m}}}}=\bigcup_{i=0}^{i=m}{{e}_{i}}=\bigcup_{i=0% }^{i=m}({{u}_{i}},{{v}_{i}},{{t}_{i}},{{r}_{i}})$ , $i=0,1,\ldots,m$ up to time ${{t}_{m}}$ , where ${{u}_{i}}$ and ${{v}_{i}}$ are elements of node set ${{\mathsf{\mathcal{V}}}_{t}}_{{}_{m}}$ , ${{t}_{i}}\in\mathbb{R}$ ( ${{t}_{0}}\leqslant{{t}_{i}}\leqslant T$ ) is a unique timestamp, and ${{r}_{i}}\in\{0,1\}$ is the type of link.

We use definition of temporal network motifs as defined in [31] and extend it with minor changes.

Definition 2 ( $\delta$ -temporal motif). A $n$ -node, $l$ -link, $\delta$ -temporal motif is a sequence of $l$ links that are time-ordered within a $\delta$ duration, i.e. $M=({{u}_{1}},{{v}_{1}},{{t}_{1}},{{r}_{1}}),({{u}_{2}},{{v}_{2}},{{t}_{2}},{{r% }_{2}}),\ldots,({{u}_{l}},{{v}_{l}},{{t}_{l}},{{r}_{l}})$ , ${{t}_{1}}<{{t}_{2}}<\ldots{{t}_{l}}$ and ${{t}_{l}}-{{t}_{1}}<\delta$ , such that the static graph induced from the sequence of $l$ links are connected and have $n$ nodes.

Some examples of temporal motifs are shown in Fig. 2. The above definition provides a template for any pattern types. A collection of timestamped links in a temporal graph is an instance of $\delta$ -temporal motif if it matches the same link pattern and all of the links occur in the right order within the $\delta$ time window. Formally, time-ordered sequence $S=({{u}_{1}}^{\prime},{{v}_{1}}^{\prime},{{t}_{1}}^{\prime},{{r}_{1}}^{\prime}% ),\ldots,({{u}_{l}}^{\prime},{{v}_{l}}^{\prime},{{t}_{l}}^{\prime},{{r}_{l}}^{% \prime})$ of $l$ unique links is an instance of the motif $M=({{u}_{1}},{{v}_{1}},{{t}_{1}},{{r}_{1}}),\ldots,({{u}_{l}},{{v}_{l}},{{t}_{% l}},{{r}_{l}})$ if

(a) there exists a mapping function $\Phi:\{\mathsf{\mathcal{G}}\}\to\{\mathsf{\mathcal{M}}\}$ from concrete nodes ${{u}_{i}}^{\prime},{{v}_{i}}^{\prime}\in\mathsf{\mathcal{V}}$ in graph $\mathsf{\mathcal{G}}$ to template nodes in motif $\mathsf{\mathcal{M}}$ such that $\Phi({{u}_{i}}^{\prime})={{u}_{i}}$ and $\Phi({{v}_{i}}^{\prime})={{v}_{i}}$ , $i=1,\ldots,l$ . (b) the links all occur within $\delta$ time, i.e., ${{t}_{l}}^{\prime}-{{t}_{1}}^{\prime}<\delta$ .

Figure 2.
3-link temporal motifs whose links appear in a time order. Note that the link numbers indicate their temporal orders. Adapted from [31].

Definition 3 (temporal motif-based adjacency matrix). Given a $k$ -type motif ${{M}_{k}}$ , its corresponding temporal motif-based adjacency matrix is ${{\mathbf{A}}^{(k)}}(t)$ , the element $\mathbf{A}_{uv}^{(k)}(t)$ is the number on the $u$ -row and $v$ -column of the motif matrix ${{\mathbf{A}}^{(k)}}(t)$ , and it is equal to the number of motifs of the given type ${{M}_{k}}$ which contains both nodes $u$ and $v$ up to time $t$ (note that nodes $u$ and $v$ can participate in motifs of multiple types). Formally,

$\displaystyle\mathbf{A}_{uv}^{(k)}(t)=\sum\limits_{u,v\in{{\mathsf{\mathcal{V}% }}_{t}},\Phi(u),\Phi(v)\in{{\mathsf{\mathcal{V}}}_{t}}^{\mathsf{\mathcal{M}}}}% I(\textit{uand v simultaneously occur in }{{M}_{k}}),$ (1)

where $I(\centerdot)$ is truth-value indicator function, i.e., $I(\centerdot)=1$ if the statement is true, and $I(\centerdot)=0$ otherwise. The larger $\mathbf{A}_{uv}^{(k)}(t)$ is, the more significant the relation between $u$ and $v$ is within the motif. The procedure is related to subgraph counting in larger graphs, which has been extensively explored in the literature [54, 55].

Figure 3.
(a) is an example 4-node, 8-link temporal graph. (b) is the temporal motif-based adjacency matrix for 3-node, 3-link triangle motif with time window $\delta=10s$ in Fig. 2. (c) Instances of the $\delta$ -temporal motif ${{M}_{k}}$ in the graph for $\delta=10s$ .

Now, we give an example to illustrate the motif-based adjacency matrix in Fig. 3. Assume we extract a temporal graph ${{\mathsf{\mathcal{G}}}_{20s}}$ from a sequence of links with time up to $t=20s$ . An example graph ${{\mathsf{\mathcal{G}}}_{20s}}$ with 4 nodes ${{v}_{1}},{{v}_{2}},{{v}_{3}},{{v}_{4}}$ and 8 temporal links are drawn in Fig. 3a. Assume that we want to compute the temporal motif-based adjacency matrix ${{\mathbf{A}}^{(k)}}(20s)$ given the triangle motif ${{M}_{k}}$ in Fig. 2. From the graph, we can see that ${{v}_{1}}$ and ${{v}_{2}}$ participate in three instances of ${{M}_{k}}$ . Please note that the crossed-out patterns are not instances of ${{M}_{k}}$ , because either the link sequence is out of order or the links do not all occur within the time window $\delta=10s$ . Details of the computation are illustrated in [31]. This example explains the meaning of temporal motif-based adjacency matrix, i.e., it records the frequency of two nodes occurring in a given temporal motif.

With the above definitions, the problem of dynamic link prediction can be formalized as follows:

Problem Statement: Given a sequence of continuous time-ordered temporal links of historical observations ${{\mathsf{\mathcal{E}}}_{{{t}_{m}}}}=\bigcup_{i=0}^{i=m}{{e}_{i}}=\bigcup_{i=0% }^{i=m}({{u}_{i}},{{v}_{i}},{{t}_{i}},{{r}_{i}})$ , the goal of dynamic link prediction is to learn the evolution information of the historical temporal graph ${{\mathsf{\mathcal{G}}}_{{{t}_{m}}}}=\{{{\mathsf{\mathcal{V}}}_{{{t}_{m}}}},{{% \mathsf{\mathcal{E}}}_{{{t}_{m}}}}\}$ and predict the linkage status of ${{\mathsf{\mathcal{G}}}_{{{t}_{m+1}}}}=\{{{\mathsf{\mathcal{V}}}_{{{t}_{m+1}}}% },{{\mathsf{\mathcal{E}}}_{{{t}_{m+1}}}}\}$ at future time $t={{t}_{m+1}}$ .
4. Design of TMAGCN

In this section, we introduce the design of TMAGCN. First, we overview the architecture of TMAGCN. Second, we introduce a novel algorithm to construct temporal motif-based adjacency matrix. Third, we introduce temporal motif-based attentional graph convolutional networks. Forth, we explain the latent mediation process for dynamic link prediction. Finally, we detail the training process of TMAGCN.

Figure 4.

The framework of TMAGCN.

4.1 Overview of TMAGCN

As shown in Fig. 4, TMAGCN consists of a temporal motif-based adjacency matrix constructing module (Block A), an embedding updating module (Block B), and an output module (Block C).

Block A: Given a collection of continuous time-ordered temporal links representing the observed events of association process and communication process, a novel algorithm is proposed to construct temporal motif-based adjacency matrices, which extracts high-order structural and temporal information from these temporal links. The outputs of Block A, i.e. temporal motif-based adjacency matrices, are sent to Block B for calculating the motif-attentional weights in multi-layer graph convolutional network.

Block B: The original GCN model is modified by replacing the temporal link-based adjacency matrices with temporal motif-based adjacency matrices, and different learning strategies are proposed to allow each individual node to select the most relevant motif neighborhood to propagate and aggregate information for updating node embeddings. The outputs of Block B, i.e. learned node embeddings, are sent to Block C for downstream tasks.

Block C: Learned node embeddings are fed into the output block and future links will be predicted based on nodes’ conditional intensity ranks. The link prediction results will be evaluated by checking whether the predicted future links and true future links are the same.

The above three modules operate in the workflow of latent mediation process for dynamic link prediction.

4.2 Temporal motif-based adjacency matrix construction

Paranjape et al. [31] proposed a general framework for exactly counting the number of instances of all possible $n$ -node, $l$ -link, $\delta$ -temporal motifs in an ordered sequence of temporal links. To construct a temporal motif-based adjacency matrix, we extend their work by restoring necessary information including node indexes and timestamps in the process of enumerating temporal motifs, which have been discarded in their original counting algorithms.

[!h] : Temporal motif-based adjacency matrix construction.[1] Sequence ${{\mathsf{\mathcal{E}}}_{{{t}_{m}}}}$ of links ${{e}_{0}}=({{u}_{0}},{{v}_{0}},{{t}_{0}},{{r}_{0}}),\ldots,{{e}_{m}}=({{u}_{m}% },{{v}_{m}},{{t}_{m}},{{r}_{m}})$ with ${{t}_{0}}<{{t}_{1}}<\ldots{{t}_{m}}$ , time window $\delta$ Number of instances of each $l$ -link, $\delta$ -temporal motif contained in the sequence ${{\mathsf{\mathcal{E}}}_{{{t}_{m}}}}$ , and temporal motif-based adjacency matrices. $\textit{start}\leftarrow 0$ , counts $\leftarrow$ Counter (default $=$ 0), linksrecord $\leftarrow$ $\varnothing$ , motiflinklist $\leftarrow$ $\varnothing$ ,Motif_Pattern_Set $\leftarrow$ $\{{{M}_{1}},\ldots,{{M}_{K}}\}$ , TMotifAdj (default $=$ 0) for $\textit{end}=0,\ldots m$ do while ${{t}_{\textit{start}}}+\delta<{{t}_{\textit{end}}}$ do for key in linksrecord.keys of length $==$ $l$ do Motif_Matching (linksrecord, key, Motif_Pattern_Set) Decrement ( ${{e}_{\textit{start}}}$ ), $\textit{start}+=1$ Increment ( ${{e}_{\textit{end}}}$ ) TMotifAdj $=$ Linklist_To_Adj_Matrix (motiflinklist) counts, TMotifAdj Function Decrement ( ${e}$ ) counts [ $e$ ] $-=$ 1 linksrecord [ $e$ ]. remove ( $e$ ) for suffix in counts.keys of length $<l-1$ do counts [concat ( $e$ , suffix)] $-=$ counts [suffix] linksrecord [concat ( $e$ , suffix)]. remove ( $e$ ) Function Increment ( ${e}$ ) for prefix in counts. keys. reverse() of length $<l$ do counts [concat (prefix, $e$ )] $+=$ counts [prefix] linksrecord [concat (prefix, $e$ )]. append ( $e$ ) counts [ $e$ ] $+=$ 1 linksrecord [ $e$ ]. append ( $e$ ) Function Motif_Matching (linksrecord, key, Motif_Pattern_Set) for motif in Motif_Pattern_Set do if Isomorphic (linksrecord [key], motif) motiflinklist. append (linksrecord [key]) Function Linklist_To_Adj_Matrix (motiflinklist) for motif in Motif_Pattern_Set do for link in motiflinklist do TMotifAdj [motif] [link. node1] [link. node2] $+=$ 1

The key idea in mapping a sequence of temporal links $S=\{{{e}_{1}}\ldots{{e}_{l}}\}$ to motifs ${{M}_{k}}$ is to make sure that the static subgraph induced by links in $S$ is isomorphic to ${{M}_{k}}$ , the order of links in $S$ matches the order in ${{M}_{k}}$ , and all the links in $S$ are at most $\delta$ time apart. As shown in Algorithm 4.2, it counts all possible $l$ -link, $\delta$ -temporal motif $\{{{M}_{1}},\ldots,{{M}_{K}}\}$ that occur in temporal graph ${{\mathsf{\mathcal{G}}}_{{{t}_{m}}}}=\{{{\mathsf{\mathcal{V}}}_{{{t}_{m}}}},{{% \mathsf{\mathcal{E}}}_{{{t}_{m}}}}\}$ , ${{\mathsf{\mathcal{E}}}_{{{t}_{m}}}}=\bigcup_{i=0}^{i=m}{{e}_{i}}=\bigcup_{i=0% }^{i=m}({{u}_{i}},{{v}_{i}},{{t}_{i}},{{r}_{i}})$ . Meanwhile it records set of time-order link list which could form isomorphism of the corresponding motifs. The data structure counts [ $\bullet$ ] maintains auxiliary counts of all ordered patterns of length at most $l$ . Specifically, counts [ ${{e}_{1}}\ldots{{e}_{r}}$ ] is the number of times that the subsequence $[{{e}_{1}}\ldots{{e}_{r}}]$ occurs in the current time window (if $r<l$ ) or the number of times the subsequence has occurred within all time windows of length $\delta$ (if $r=l$ ). Keys of counts [ $\bullet$ ] are accessed in order of length.

Algorithm 4.2 outlines the temporal motif-based adjacency matrix construction method. With respect to the original algorithm in [31], the highlighted codes in Algorithm 4.2 denote the changes for recording link list of motif. Line 1 includes all the necessary data initialization. The time serial numbers start from 0. The motif counter is set 0. The set linksrecord [ $\bullet$ ] is used to store the list of length-1 to length- $l$ subsequences. Different from the previous work [31], we not only record the count of motif, but also record the link list information including two nodes’ indexes of each link, timestamp and link type. The set motiflinklist is used to store list of temporal links isomorphic to $l$ -link, $\delta$ -temporal motifs. On lines 2-9, we update motif counter counts [ $\bullet$ ] and motiflinklist by enumerating all the time ordered links. For the first link $e=(u,v,t,r)$ , the single link counts counts [ $e$ ] are updated and $e$ is appended into the linksrecord [ $e$ ]. Based on these updates, length-2 subsequences formed with $e$ as its first link are updated and so on, up through length-( $l$ -1) subsequences. On the one hand, when a link $e$ is added to the time window, similar updates take place in order to increase counts in subsequences where $e$ is the last link (the Increment() function on lines 16–21). When the length of subsequence reaches $l$ (line 4–5), the subsequence will be fed into the Motif_Matching() function (lines 22–25) to check the isomorphism between subsequence induced subgraph and one type of motif ${{M}_{k}}$ . If the check process returns true, the subsequence will be appended in the set motiflinklist. On the other hand, moving the time window forward by adding a new link into the window, all links farther than $\delta$ time from the new link are removed from the window, the appropriate counts are decreased and linksrecord [ $\bullet$ ] are updated (the Decrement() function on lines 10–15). As the time window moves from the beginning to the end of the sequence of links, the algorithm accumulates counts and all length- $l$ subsequences of temporal links which could form motifs in all possible time windows of length $\delta$ . When the motiflinklist accumulation process is finished, we can fill in elements in the temporal motif-based adjacency matrix TMotifAdj according to Definition 3 (the Linklist_To_Adj_Matrix() Function on lines 26–29).

4.3 Temporal motif-based graph convolutional networks

4.3.1 Convolutional layer with single temporal motif-based attention

The original graph convolutional network (GCN) [27] aims to fuse a node’s information with its neighbors’ information to handle spatial dependencies in a graph. When the adjacency matrix $\mathbf{A}$ is replaced with temporal motif-based adjacency matrix ${{\mathbf{A}}^{(k)}}(t)$ (corresponding to the type of motif ${{M}_{k}}$ ), both the higher-order temporal and structural information will be involved in nodes’ representations. A multi-layer graph convolutional network with layer-wise propagation rule:

$\displaystyle{{\mathbf{H}}^{(l+1)}}(t)=\sigma({{({{{\mathbf{\widetilde{D}}}}^{% (k)}}(t))}^{-\frac{1}{2}}}{{{\mathbf{\widetilde{A}}}}^{(k)}}(t){{({{{\mathbf{% \widetilde{D}}}}^{(k)}}(t))}^{-\frac{1}{2}}}{{\mathbf{H}}^{(l)}}(t){{\mathbf{W% }}^{(l)}}),$ (2)

where ${{\mathbf{H}}^{(l)}}(t)\in{{\mathbb{R}}^{N\times{{D}^{(l)}}}}$ is the matrix of a set of node feature embeddings (with the ${{D}^{(l)}}$ input dimensions) inputted to the $l$ -th layer. The initial input to the convolutional layer can be set as ${{\mathbf{H}}^{(0)}}=\mathbf{X}$ , where $\mathbf{X}\in{{\mathbb{R}}^{N\times D}}$ is the initial node feature matrix and $D$ is the input embedding dimension. ${{\mathbf{\widetilde{A}}}^{(k)}}(t)={{\mathbf{A}}^{(k)}}(t)+\mathbf{I}_{N}^{(k% )}(t)$ , $\mathbf{I}_{N}^{(k)}(t)$ is the matrix of size $N$ with elements on the main diagonal being the number of times that nodes appearing in the same instances of motif ${{M}_{k}}$ and zeros elsewhere. ${{\mathbf{A}}^{(k)}}(t)$ is the corresponding temporal motif-based adjacency matrix of network ${{\mathsf{\mathcal{G}}}_{t}}$ . ${{\mathbf{\widetilde{D}}}^{(k)}}(t)$ is a diagonal degree matrix with $\mathbf{\widetilde{D}}_{uu}^{(k)}(t)=\sum\nolimits_{v}{\mathbf{\widetilde{A}}_% {uv}^{(k)}(t)}$ . ${{\mathbf{W}}^{(l)}}\in{{\mathbb{R}}^{{{D}^{(l)}}\times{{D}^{(l+1)}}}}$ is a matrix of trainable graph convolution parameters. $\sigma$ is a nonlinear activation function. ${{({{{\mathbf{\widetilde{D}}}}^{(k)}}(t))}^{-\frac{1}{2}}}{{\mathbf{\widetilde% {A}}}^{(k)}}(t){{({{{\mathbf{\widetilde{D}}}}^{(k)}}(t))}^{-\frac{1}{2}}}$ produces a symmetric normalized matrix which updates each nodes representation via a weighted sum of the features in a node’s one-hop temporal motif neighborhood. Each link’s weight is normalized by considering the temporal motif degrees of the corresponding pair of nodes. After the graph convolution, the $u$ -th row of ${{\mathbf{H}}^{(l+1)}}$ becomes:

$\displaystyle{{\mathbf{h}}_{u}}^{(l+1)}(t)=\sigma\left(\sum\limits_{v\in\Gamma% _{u}^{({{{\mathbf{\tilde{A}}}}^{(k)}}(t))}}{{{\alpha}_{uv}}}{{\mathbf{h}}_{v}}% ^{(l)}(t){{\mathbf{W}}^{(l)}}\right),$ (3)

where ${{\mathbf{h}}_{u}}^{(l+1)}(t)\in{{\mathbb{R}}^{1\times{{D}^{(l+1)}}}}$ is the new feature embedding of node $u$ at layer $l+1$ , ${{\Gamma}_{u}}^{({{{\mathbf{\widetilde{A}}}}^{(k)}}(t))}=\{v\in{{\mathsf{% \mathcal{V}}}_{t}}:(u,v)\in{{\mathsf{\mathcal{E}}}_{t}}\}$ is the set of neighbors defined by the matrix ${{\mathbf{\widetilde{A}}}^{(k)}}(t)$ . The attention coefficient ${{\alpha}_{uv}}$ indicating the importance or contribution of neighbor node $v$ ’s feature to node $u$ is fixed as follows:

$\displaystyle{{\alpha}_{uv}}=\frac{1}{\sqrt{\deg(u)}\sqrt{\deg(v)}},$ (4)

Based on the attentional mechanism of graph attention network (GAT) [56], we propose a variant of GAT to modify Eq. (4) with attention coefficient ${{\alpha}_{uv}}$ as follows:

$\displaystyle{{\alpha}_{uv}}=\frac{\exp(\sigma(\mathbf{\widetilde{A}}_{uv}^{(k% )}(t)\cdot\mathbf{a}{{[\mathbf{h}_{u}^{(l)}(t){{\mathbf{W}}^{(l)}}||\mathbf{h}% _{v}^{(l)}(t){{\mathbf{W}}^{(l)}}]}^{T}}))}{\sum\limits_{w\in{{\Gamma}_{u}}^{(% {{{\mathbf{\widetilde{A}}}}^{(k)}}(t))}}{\exp(\sigma(\mathbf{\tilde{A}}_{uw}^{% (k)}(t)\cdot\mathbf{a}{{[\mathbf{h}_{u}^{(l)}(t){{\mathbf{W}}^{(l)}}||\mathbf{% h}_{w}^{(l)}(t){{\mathbf{W}}^{(l)}}]}^{T}}))}},$ (5)

where $\mathbf{a}\in{{\mathbb{R}}^{1\times 2{{D}^{(l)}}}}$ is a trainable weight vector parameterizing the attention function, which is implemented as a single layer feedforward neural network, ${{\mathbf{W}}^{(l)}}$ is a shared weight transformation applied to each node. ${{[\centerdot]}^{T}}$ represents transposition and $||$ is the concatenation operation. Note that $\mathbf{\widetilde{A}}_{uv}^{(k)}(t)$ is equal to the number of motifs of the given type ${{M}_{k}}$ which contains both nodes $u$ and $v$ . It represents the weight of link $(u,v)$ in the temporal graph ${{\mathsf{\mathcal{G}}}_{t}}$ from the point of view of motif.

GAT employs the multi-head attention to stabilize the attention coefficients learning process. $J$ denotes the number of attentional heads, $\alpha_{uv}^{j}$ denotes the $j$ -th relative attention coefficient of $v$ ’s features to $u$ . As is shown in Eq. (6), the output features of nodes’ neighbors are averaged to form their final output features. The output of final layer is $\mathbf{h}_{u}^{k}(t)$ .

$\displaystyle{{\mathbf{h}}_{u}}^{(l+1)}(t)=\sigma\left(\frac{1}{J}\sum\limits_% {j=1}^{J}{\sum\limits_{v\in\Gamma_{u}^{({{{\mathbf{\widetilde{A}}}}^{(k)}}(t))% }}{\alpha_{uv}^{j}}{{\mathbf{h}}_{v}}^{(l)}(t){{\mathbf{W}}^{(l)}}}\right),$ (6)

4.3.2 Multiple temporal motif-based attention

We have demonstrated how to integrate higher-order temporal and structural information into node embeddings based on a single temporal motif-based attention. Given $K$ different temporal motifs, we now have $K$ motif matrices to define layer-wise propagations in Eq. (3). Since different motifs can vary in their importances for a specific task, we face the challenge of appropriately weighting the extracted features on each convolutional layer for effective feature propagation. A simple solution is to implement independent $K$ GCN instances and use a set of parameters to combine the output of each motif.

Inspired by recent advances in attention mechanism, we propose a motif-attention model to dynamically weight the importances of different motifs for each node. We use the scaled dot-product form to compute the node $u$ ’s multiple motif attentional embedding as follows:

$\displaystyle{{\mathbf{h}}_{u}}(t)=\sum\limits_{k=1}^{K}{\beta_{u}^{k}\mathbf{% h}_{u}^{k}(t)},\beta_{u}^{k}=\operatorname{softmax}(\mathbf{s}_{u}^{k})=\frac{% \exp(\mathbf{s}_{u}^{k})}{\sum\limits_{j=1}^{K}{\exp(\mathbf{s}_{u}^{j})}},$ (7)

where $\mathbf{h}_{u}^{k}(t)$ is node $u$ ’s embedding computed in Eq. (6) based on a single motif ${{M}_{k}}$ , $\mathbf{s}_{u}^{k}=\psi(\mathbf{h}_{u}^{k}(t),{{\mathbf{z}}^{k}})=\frac{{{({{% \mathbf{z}}^{k}})}^{T}}\cdot\mathbf{h}_{u}^{k}(t)}{\sqrt{{{\mathbf{z}}^{k}}}}$ is attention coefficient that indicates the importance of motif ${{M}_{k}}$ to node $u$ , ${{\mathbf{z}}^{k}}$ is a shared attention vector for motif ${{M}_{k}}$ describing the informativeness of ${{M}_{k}}$ across different nodes and ${{\mathbf{h}}_{u}}(t)$ is node $u$ ’s final embedding weighted by multiple temporal motifs $\{{{M}_{1}},\ldots,{{M}_{K}}\}$ .

Furthermore, we propose a reinforcement learning strategy to allow each node to select its most relevant neighborhood to integrate information. We define one function $\psi(\centerdot):{{\mathbb{R}}^{{{S}^{(l)}}}}\to{{\mathbb{R}}^{K}}$ , where ${{S}^{(l)}}$ is the dimension of the state-space at layer $l$ . The node state matrix at layer $l$ is defined as follows:

$\displaystyle{{\mathbf{S}}^{(l)}}=[{{({{{\mathbf{\widetilde{D}}}}^{(0)}}(t))}^% {-\frac{1}{2}}}{{{\mathbf{\widetilde{A}}}}^{(0)}}(t){{({{{\mathbf{\widetilde{D% }}}}^{(0)}}(t))}^{-\frac{1}{2}}}{{\mathbf{H}}^{(l)}}(t){{(\mathbf{W}_{s}^{{}^{% (l)}})}^{T}}C],$ (8)

where $\mathbf{W}_{s}^{{}^{(l)}}\in{{\mathbb{R}}^{N\times{{D}^{(l)}}}}$ is the weight matrix that embeds the inputs to dimension ${{D}^{(l)}}$ , $C$ is a motif count matrix that contains basic local structural information about each node by counting the number of $K$ different motifs that each node belongs to. The outputs of function $\psi(\centerdot)$ are softmaxed to produce a probability distribution over $\{1,\ldots,K\}$ . It specifies the importances of the various motifs and recommends the most relevant motif for each node. Let $\psi({{{\mathbf{s}}}_{u}})$ be the probability distribution for node $u$ , ${{k}_{u}}$ be the index of the largest value in $\psi({{{\mathbf{s}}}_{u}})$ . The $N\times N$ propagation matrix has the form as follows:

$\displaystyle\mathbf{\widehat{A}}(t)=\left[\begin{array}[]{c}{{({{{\mathbf{% \widetilde{A}}}}^{({{k}_{1}})}}(t))}_{1,:}}\\ \vdots\\ {{({{{\mathbf{\widetilde{A}}}}^{({{k}_{N}})}}(t))}_{N,:}}\\ \end{array}\right],$ (9)

where ${{({{{\mathbf{\widetilde{A}}}}^{({{k}_{u}})}}(t))}_{u,:}}\in{{\mathbb{R}}^{1% \times N}}$ ( $u=1,\ldots,N$ ) means the $u$ -th row of the temporal motif-based adjacency matrix ${{\mathbf{\widetilde{A}}}^{(k)}}(t)$ which corresponds to the most relevant motif ${{M}_{k}}$ for node $u$ in a slice form. The adjacency matrix ${{\mathbf{\widetilde{A}}}^{(k)}}(t)$ in Eq. (6) is replaced by $\mathbf{\widehat{A}}(t)$ , which allows each node to select the most appropriate motif to integrate or accumulate information from.

4.4 Learning latent mediation process for dynamic link prediction

In Section 3.2, we have formally stated that most real-world dynamic networks contain two interleaved processes in the form of communication and association events, and can be modeled as temporal graph ${{\mathsf{\mathcal{G}}}_{{{t}_{m}}}}=({{\mathsf{\mathcal{V}}}_{{{t}_{m}}}},{{% \mathsf{\mathcal{E}}}_{{{t}_{m}}}})$ . These two types of processes interact to fully describe information transfer between nodes. However, the dynamics are not two simple processes depend on each other, they are related through the latent mediation process and in the embedding space. The occurrence of a new event at time ${{t}_{i}}$ from either of these processes is dependent on the most recent state of the graph at time ${{t}_{i-1}}$ . The embeddings of both participating nodes need to be updated to capture the effect of the new observed event.

The interaction of these two processes can be expressed as three recursively executed functions:

$\displaystyle{{\mathbf{h}}_{u}}({{t}_{i}})={{f}_{h}}(\mathbf{H}({{t}_{i-1}}),% \mathbf{L}({{t}_{i-1}}),{{\Gamma}_{u}}^{(\mathbf{A}({{t}_{i}}))}),$ (10a) $\displaystyle{{\mathbf{h}}_{v}}({{t}_{i}})={{f}_{h}}(\mathbf{H}({{t}_{i-1}}),% \mathbf{L}({{t}_{i-1}}),{{\Gamma}_{v}}^{(\mathbf{A}({{t}_{i}}))}),$ (10b)

$\displaystyle\lambda_{uv}^{r}({{t}_{i}})={{f}_{\lambda}}([{{\mathbf{h}}_{u}}({% {t}_{i-1}}),{{\mathbf{h}}_{v}}({{t}_{i-1}})]),$ (11) $\displaystyle\mathbf{L}({{t}_{i}})={{f}_{L}}(\mathbf{H}({{t}_{i-1}}),\mathbf{A% }({{t}_{i}})),$ (12)

where ${{\mathbf{h}}_{u}}({{t}_{i}})$ , ${{\mathbf{h}}_{v}}({{t}_{i}})\in{{\mathbb{R}}^{1\times D}}$ are node embeddings of $u$ and $v$ at time ${{t}_{i}}$ ; $\mathbf{H}({{t}_{i-1}})\in{{\mathbb{R}}^{N\times D}}$ is node embedding matrix at previous time ${{t}_{i-1}}$ ; ${{\Gamma}_{u}}^{(\mathbf{A}({{t}_{i}}))}$ and ${{\Gamma}_{v}}^{(\mathbf{A}({{t}_{i}}))}$ are one-hop neighbors defined by adjacency matrix $\mathbf{A}({{t}_{i}})$ of the node ${{u}_{i}}$ and ${{v}_{i}}$ participating in the event $({{u}_{i}},{{v}_{i}},{{t}_{i}},{{r}_{i}})$ . For different learning strategies, adjacency matrix $\mathbf{A}({{t}_{i}})$ has different forms. If we just leverage link-based neighborhood to update node embeddings, then adjacency matrix is ${{\mathbf{A}}^{(0)}}({{t}_{i}})$ . ${{\Gamma}_{u}}^{(\mathbf{A}^{(0)}({{t}_{i}}))}$ and ${{\Gamma}_{v}}^{(\mathbf{A}^{(0)}({{t}_{i}}))}$ are one-hop link-based neighbors defined by adjacency matrix ${{\mathbf{A}}^{(0)}}({{t}_{i}})$ . In order to take advantage of temporal motif-based attentions, adjacency matrix $\mathbf{A}({{t}_{i}})$ will be changed into ${{\mathbf{A}}^{(k)}}({{t}_{i}})(k=1,\ldots,K)$ . ${{\Gamma}_{u}}^{(\mathbf{A}^{(k)}({{t}_{i}}))}$ and ${{\Gamma}_{v}}^{(\mathbf{A}^{(k)}({{t}_{i}}))}$ are one-hop temporal motif neighbors defined by adjacency matrix ${{\mathbf{A}}^{(k)}}({{t}_{i}})$ . If we adopt reinforcement learning-based method to combine multiple temporal motif-based attentions, then adjacency matrix $\mathbf{A}({{t}_{i}})$ will be changed into one-hop temporal motif adjacency matrix $\mathbf{\widehat{A}}({{t}_{i}})$ . ${{\Gamma}_{u}}^{(\mathbf{\widehat{A}}({{t}_{i}}))}$ and ${{\Gamma}_{v}}^{(\mathbf{\widehat{A}}({{t}_{i}}))}$ are most relevant one-hop temporal motif neighbors defined by adjacency matrix $\mathbf{\widehat{A}}({{t}_{i}})$ .

Embeddings ${\mathbf{h}}_{u}({{t}_{i}})$ and ${\mathbf{h}}_{v}({{t}_{i}})$ are updated in the same way, so below we only expand it for ${{\mathbf{h}}_{u}}({{t}_{i}})$ . For an event ${{\mathsf{\mathcal{E}}}_{{{t}_{i}}}}=({{u}_{i}},{{v}_{i}},{{t}_{i}},{{r}_{i}})$ between nodes u and v, the embeddings of both nodes are updated based on the summation of the following three terms, followed by a nonlinear activation function $\sigma$ . The function ${{f}_{h}}$ has the form as:

$\displaystyle{\mathbf{h}_{u}}({{t}_{i}})={{f}_{h}}(\mathbf{H}({{t}_{i-1}}),% \mathbf{L}({{t}_{i-1}}),{{\Gamma}_{u}}^{(\mathbf{A}({{t}_{i}}))})=\sigma({% \mathbf{W}^{\textit{neib}}}\mathbf{h}_{u}^{\textit{neib}}({{t}_{i-1}})+{{% \mathbf{W}}^{\textit{self}}}{{\mathbf{h}}_{u}}({{t}_{i-1}})+{{\mathbf{W}}^{% \textit{exo}}}({{t}_{i}}-{{t}_{i-1}})),$ (13)

where ${\mathbf{W}^{\textit{neib}}}$ , ${\mathbf{W}^{\textit{self}}}$ and ${\mathbf{W}^{\textit{exo}}}$ are learned parameter matrices. The first term of Eq. (13) is the Neighborhood Factor, which is comprised of learned parameter matrix ${\mathbf{W}^{\textit{neib}}}\in{{\mathbb{R}}^{D\times D}}$ multiplied by a learned hidden representation $\mathbf{h}_{u}^{\textit{neib}}$ . $\mathbf{h}_{u}^{\textit{neib}}({{t}_{i-1}})$ is a function of temporal attention ${{\mathbf{L}}_{u}}({{t}_{i}})\in{{\mathbb{R}}^{1\times N}}$ between node $u$ and all its one-hop neighbors ${{\Gamma}_{u}}^{(\mathbf{A}({{t}_{i-1}}))}$ defined by adjacency matrix $\mathbf{A}({{t}_{i-1}})$ . $\mathbf{h}_{u}^{\textit{neib}}({{t}_{i-1}})$ has the form as Eq. (3) that updates node embeddings. Updating node $u$ ’s embeddings with its neighbors’ features is important for creating a temporal link by which node features propagate between the two nodes. The idea is that the more frequently the nodes communicate, the more similar their embeddings will be. The second term is the Self-Propagation Factor, which is comprised of learned parameter matrix ${\mathbf{W}^{\textit{self}}}\in{{\mathbb{R}}^{D\times D}}$ multiplied by the previous computed embedding ${{\mathbf{h}}_{u}}({{t}_{i-1}})$ , at the time index node $u$ last participated in an association or communication event ${{t}_{i-1}}$ . This term performs a recurrent update of the features of node $u$ . The third term is the Exogenous Factor, which is comprised of the learned parameter matrix ${{\mathbf{W}}^{\textit{exo}}}\in{{\mathbb{R}}^{1\times D}}$ multiplied by the waiting time between the current event ${{\mathsf{\mathcal{E}}}_{{{t}_{i}}}}$ and the previous event involving node $u({{\mathsf{\mathcal{E}}}_{{{t}_{i-1}}}})$ , which captures other factors that may influence the embedding of node $u$ , such as global events involving many nodes.

$\lambda_{uv}^{r}({{t}_{i}})$ is the conditional intensity function that models the instantaneous rate at which a link of type $r$ (association or communication) occurs between nodes $u$ and $v$ in the infinitesimally tiny interval $[{{t}_{i}},{{t}_{i}}+\text{d}t)$ . In the latent mediation process, learned node embeddings drive the complex temporal dynamics of both communicaiton and association processes. These processes subsequently lead to the nonlinear evolution of node embeddings. The conditional intensity $\lambda_{uv}^{r}({{t}_{i}})$ is an important factor in the latent mediation process as it plays the role of bridging occurrence of links and embedding updating. The conditional intensity $\lambda_{uv}^{r}({{t}_{i}})$ can be formulated as a softplus function of the concatenated learned node embeddings [28]:

$\displaystyle\lambda_{uv}^{r}({{t}_{i}})={{\psi}_{r}}\log\left(1+\exp\left\{% \frac{\mathbf{\omega}_{r}^{T}[{{\mathbf{h}}_{u}}({{t}_{i-1}})\parallel{{% \mathbf{h}}_{v}}({{t}_{i-1}})]}{{{\psi}_{r}}}\right\}\right),$ (14)

where ${{\psi}_{r}}$ is the scalar trainable rate at which events of type $r$ occur, and $\mathbf{\omega}_{r}^{T}\in{{\mathbb{R}}^{1\times 2D}}$ is a trainable vector that represents the compatibility between nodes $u$ and $v$ at time ${{t}_{i}}$ . The concatenation in Eq. (14) can be replaced with bilinear interaction [29]:

$\displaystyle\lambda_{uv}^{r}({{t}_{i}})={{\psi}_{r}}\log\left(1+\exp\left\{% \frac{\mathbf{\omega}_{r}^{T}[{{\mathbf{h}}_{u}}{{({{t}_{i-1}})}^{T}}{{\Omega}% _{r}}{{\mathbf{h}}_{v}}({{t}_{i-1}})]}{{{\psi}_{r}}}\right\}\right),$ (15)

where ${{\Omega}_{r}}\in{{\mathbb{R}}^{D\times D}}$ are trainable parameters, to allow more complex interactions between evolving node embeddings.

$\mathbf{L}({{t}_{i}})\in{{\mathbb{R}}^{N\times N}}$ is the temporal attention matrix capturing attention coefficients over neighborhood at time ${{t}_{i}}$ . The element ${{\mathbf{L}}_{uv}}({{t}_{i}})$ in temporal attention matrix can be calculated with Eq. (5), i.e. ${{\mathbf{L}}_{uv}}({{t}_{i}})={{\alpha}_{uv}}({{t}_{i}})$ . Concatenation operation in Eq. (5) can also be replaced with bilinear interaction:

$\displaystyle{{\mathbf{L}}_{uv}}({{t}_{i}})=\frac{\exp(\sigma(\mathbf{A}_{uv}^% {(k)}(t)\cdot\mathbf{a}{{[{{\mathbf{h}}_{u}}{{({{t}_{i-1}})}^{T}}\Omega{{% \mathbf{h}}_{v}}({{t}_{i-1}})]}^{T}}))}{\sum\limits_{w\in{{\Gamma}_{u}}^{({{{% \mathbf{A}}}^{(k)}}(t))}}{\exp(\sigma(\mathbf{A}_{uw}^{(k)}(t)\cdot\mathbf{a}{% {[{{\mathbf{h}}_{u}}{{({{t}_{i-1}})}^{T}}\Omega{{\mathbf{h}}_{w}}({{t}_{i-1}})% ]}^{T}}))}}.$ (16)

4.5 Training model

Given the mini-batch size $p$ and a sequence of observed events $\bigcup_{i=0}^{i=p}({{u}_{i}},{{v}_{i}},{{t}_{i}},{{r}_{i}})$ , our goal is to train our model that can predict the occurrences of new events. We learn these parameters of our model by minimizing the following cost function:

$\displaystyle\mathsf{\mathcal{L}}={{\mathsf{\mathcal{L}}}_{\textit{events}}}+{% {\mathsf{\mathcal{L}}}_{\textit{nonevents}}}+{{\mathsf{\mathcal{L}}}_{R}},$ (17)

where ${{\mathsf{\mathcal{L}}}_{\textit{events}}}=-\sum\nolimits_{i=1}^{i=p}{\log(% \lambda_{{{u}_{i}}{{v}_{i}}}^{r}({{t}_{i}}))}$ is the total negative log of the intensity rate for all events between nodes ${{u}_{i}}$ and ${{v}_{i}}$ , ${{\mathsf{\mathcal{L}}}_{\textit{nonevents}}}=\sum\nolimits_{r\in\{0,1\}}{\sum% \nolimits_{m=1}^{p}{\sum\nolimits_{i=1}^{p}{\lambda_{{{u}_{m}}{{v}_{i}}}^{r}({% {t}_{m}})}}}$ is the intensity rate of all nonevents between nodes ${{u}_{m}}$ and ${{v}_{i}}$ in the mini-batch. Since the second term is intractable and it is unnecessary to compute the integral for all possible non-events in a stochastic setting, we adopt a simple variant of Monte Carlo trick to sample a subset of nonevents $\bigcup_{i=0}^{i=\mathsf{\mathcal{M}}}({{u}_{i}},{{v}_{i}},{{t}_{i}},{{r}_{i}})$ as in [28] and set $\mathsf{\mathcal{M}}=\text{5}p$ . The complexity of mini-batch training will be $\mathsf{\mathcal{O}}(2prU)$ where $U$ accounts for the number of samples and 2 accounts for the update happening for two nodes per event.

While ${{\mathsf{\mathcal{L}}}_{\textit{events}}}$ and ${{\mathsf{\mathcal{L}}}_{\textit{nonevents}}}$ are sufficient for training the model to link prediction in temporal graphs, they cannot help to train the attention mechanism that selects the best temporal motif-based adjacency matrix for each node. Therefore, we define a loss function ${{\mathsf{\mathcal{L}}}_{R}}$ based on the REINFORCE rule [57]:

$\displaystyle{{\mathsf{\mathcal{L}}}_{R}}=-\sum\nolimits_{u,v\in{{\mathsf{% \mathcal{V}}}_{t}}_{{}_{p}}}{R}(\log\pi(\psi{{({{{\mathbf{s}}}_{u}})}_{{{k}_{u% }}}},\psi{{({{{\mathbf{s}}}_{v}})}_{{{k}_{v}}}})),$ (18)

where $R$ is the reward. $R=1$ if conditional intensity $\lambda_{uv}^{r}$ enters the top 10 ranking list $\lambda_{uj}^{r}$ ( $j=1,\linebreak\ldots,N-1$ and $j\neq v$ ), $R=-1$ if $\lambda_{uv}^{r}$ fall out of the top 10. The $\varepsilon$ -greedy strategy is used in the process of selecting a motif during training. We pick the motif with highest probability most of the time but during $\varepsilon$ instances we select a random motif. During testing, we choose the motif with highest probability.

5. Experimental evaluation

5.1 Datasets

In order to evaluate the performance of our proposed method, we use three real-world social networks: European Email Network (Email-EU) [13], Social Evolution Network (SocialEvl) [58] and Github Network (Github) [28]. Details of these datasets are introduced below.

Email-EU.

The network was generated using email data from a large European research institution. The e-mails only represent communication between institution members, and the dataset does not contain incoming messages from or outgoing messages to the rest of the world. A directed link $(u,v,t)$ means that person $u$ sent an e-mail to person $v$ at time $t$ . This network consists of 89 nodes and 4488 temporal links, and the graph dynamics evolve as a single time scale process. The Time span is 212 days. We use events from January 1, 1970 to May 31, 1970 for training, and from June 1, 1970 to August 1, 1970 for testing which gives 10 days of time per test slot. This leads to an approximate 60/40 (train/test) split.

SocialEvl.

This dataset is released by MIT Human Dynamic Lab. It was generated using everyday online social network data from an undergraduate dormitory. This dataset consists of 84 students, 426,332 communication events in 3 types and 10,548 association events in 5 types. Individual attributes and relationships were captured by phone sensors. A communication event is represented by the sending of an SMS message, or a PROXIMITY or CALL event from person $u$ to person $v$ . Individual attributes, relationships and diffusion were captured by survey data. An association event is represented by the fact that a person $u$ had a relationship with another person $v$ at the timestamp $t$ . The surveyed relationships are: close friends (CloseFriend), participated in at least two common activities per week (SocializeTwicePerWeek), discussed politics since the last survey (PoliticalDiscussant), shared all tagged Facebook photos (FacebookAllTaggedPhotos), shared blog/live journal/Twitter activities (BlogLivejournalTwitter). We use events from October 1, 2008 to November 30, 2008 for training, and from December 1, 2008 to December 31, 2008 for testing as [28] which gives 5 days of time per test slot. This leads to an approximate 75/25 (train/test) split. As Proximity events are noisy, we filter them by the probability that the event occurred as [29], which is available in the dataset annotations.

Github.

This dataset consists of 284 users and 7333 communication events in 7 types and 730 association events in 1 type. A communication event is represented by committing a ForkEvent, PushEvent, WatchEvent, IssuesEvent, IssueCommentEvent, PullRequestEvent, or a CommitCommentEvent from user to user. An association event is represented by the fact that a user committed a FollowEvent with another user. We use events from January 1, 2013 to May 31, 2013 for training, and from June 1, 2013 to June 31, 2013 for testing which gives 5 days of events per time slot. This leads to an approximate 75/25 (train/test) split.

Table 2
Summary statistics of temporal network datasets

Dataset	#nodes	#links	#time span	Cc	Cr
Email-EU	89	4488	212days	0.520	0.462
SocialEvl	84	436880	92days	0.548	0.714
Github	284	8063	181days	0.087	0.298

In Table 2, we summarize statistics of benchmark datasets. Cc denotes the clustering coefficient of networks, Cr denotes the correlation coefficient between train and test events. Graph dynamics in the first dataset belong to a single-time scale process and all the events are represented as $(u,v,t)$ . This form of datasets is prevalent in the mainstream dynamic link prediction research. Graph dynamics in the last two datasets belong to a two-time scale process and all the events are represented as $(u,v,t,r)$ . Research on two-time scale process is still in an infant stage. But it is an emerging and promising future direction. These datasets cover a range of configurations as Email-EU and SocialEvl datasets are small networks with high clustering coefficients and dense temporal links, while Github dataset is a large network with low clustering coefficient and sparse temporal links. The experimental performances on these datasets will show the robustness of our proposed method.

5.2 Experimental settings

We apply a two-layer GCN model to update node embeddings. Then, we use the rectified linear units (ReLU) as the nonlinear activation function in graph convolution layers, and exponential linear unit (ELU) to compute the attention weights in GAT model. GCN model is initialized using He [59] initialization while GAT model is initialized using Glorot [60] initialization. We construct temporal motif adjacency matrix based on the 3-link temporal network motifs as defined in [31]. We optimize all models by minimizing the cost function with the Adam optimizer [61], an initial learning rate of 0.0002, decay step of 10, decay weight of 0.5, minibatch size of 200, and 64 hidden units per layer. The number of attention heads in GAT model is 8. We adopt an $\varepsilon$ -greedy strategy with $\varepsilon=0.1$ .

For SocialEvl dataset, we generate the one-hot node embedding as the initial hidden representation based on the information about which year the subjects were in, and which living sector in the dorm building the subjects’ apartments were located in. This is for the reason that living sector in the dormitory and year in school are the two major factors in determining relationships in the dataset. For the other two datasets, we utilize motif counts distribution to generate the initial node embeddings, which are then updated during training.

During testing, given a tuple $(u,t,r)$ , we compute the conditional density $\lambda_{uv}^{r}(t)$ of node $u$ with all other nodes $v\in{{\mathsf{\mathcal{V}}}_{t}}$ and rank them. Dynamic link prediction performances are evaluated by using the Mean Average Ranking (MAR) and HITS@10: the proportion of times that a positve test tuple $(u,v,t,r)$ appears in the top 10.

We divide the test sets into $n(n=6)$ slots based on time and report the performance for each time slot. This evaluation scheme is expected to provide fine-grained insights on how various methods perform over time as they move farther from the learned training history. We run each experiment 10 times with 10 epochs each time. The average of MAR and HITS@10 with a standard deviation is reported.

5.3 Results

To evaluate the superiority of our proposed TMAGCN, we conduct extensive experiments on dynamic link prediction tasks and compare TMAGCN against state-of-the-art evolving embeddings methods DyRep [28] (representation learning framework for dynamic graphs) and LDG [29] (latent dynamic graph) on 3 real world dynamic networks. Specifically, the compared baselines are as follows:

(1)
DyRep: A novel representation learning framework for dynamic graphs which updates attention weights in a predefined hard-coded way based on associative connections.
(2)
LDG $-$ : Latent dynamic graph (LDG) model for dynamic graphs which captures temporal attention weights between nodes through two passes of node and link mappings, without maintaining an explicit representation of the ground-truth graph in the form of an adjacency matrix. It predicts links using concatenation operation on pairs of nodes.
(3)
LDG $+$ : LDG model with bilinear relationship instead of concatenation to permit more complex relationships between node representations.
(4)
TMAGCN $-$ : Simple temporal motif-based graph convolutional network for dynamic link prediction. It uses GCN to update node embeddings with fixed weights as in Eq. (4), and computes multiple motif attentional embedding with Eq. (7).
(5)
TMAGCN $+$ : Improved TMAGCN model which uses GAT to update node embeddings with modified weights as in Eq. (5), and computes multiple motif attentional embedding with Eq. (7).
(6)
TMAGCN*: Advanced TMAGCN model which updates node embeddings as TMAGCN $+$ , but further modifies it by adopting reinforcement learning strategy to select the most appropriate motif adjacency matrix for each node.

5.3.1 Dynamic link prediction performance

In this paper, the dynamic link prediction task is to predict future events between nodes. We summarize the overall MAR and HITS@10 and standard deviations of different methods on the three dynamic network datasets in Table 3. For TMAGCN based methods, we choose $\delta=1$ hour for the time window as it is close to the median time for a node to take part in 3-links in most of our datasets. The bold and underlined values indicate the best and second prediction performance of corresponding methods respectively. From the table, we have the following observations:

(1)
TMAGCN achieves high HITS@10 and low standard variances for all datasets, which demonstrates its robustness in accurate learning from various properties of data. Specifically, TMAGCN based methods consistently improve results, achieving gains of 7.6%, 7.8% and 5.6% in HITS@10 while rising 6.7, 3.9 and 14.55 places in MAR over LDG based models on Email-EU, SocialEvl and Github datasets, respectively. Even though only the temporal motif-based adjacency matrix is utilized, TMAGCN $-$ surpasses all baseline methods DyRep and LDG in terms of MAR and HITS@10 metrics. The performance improvements show the power of capturing higher-order temporal and structural features through relevant evolving patterns defined by temporal motifs rather than separate links. Since the task of predicting future events in SocialEvl is more fine-grained, the attention mechanism improves performance significantly by weighting the importance of different motifs appropriately.
(2)
TMAGCN $+$ is capable of improving TMAGCN $-$ by a margin of 1.7%, 3.5% and 0.9% in terms of HITS@10 on the three datasets, respectively. It manifests that assigning different weights to nodes of a same neighborhood according to temporal motifs they participate in is beneficial. TMAGCN* is able to further improve TMAGCN $+$ by a margin of 0.3%, 2.7% and 2.1% in terms of HITS@10, respectively. It suggests that the motif-based neighborhood selected with REINFORCE-rule-based model is more suitable than with motif-attention model for each node to integrate or accumulate information from.
(3)
DyRep achieves the relatively lowest evaluation values, but it provides the cornerstone and inspiration for LDG and TMAGCN in modeling two-time scale dynamics. The results on one-time scaled dynamic graph of Email-EU dataset further confirm the finding from [29] that the bilinear transformation is superior to feature concatenation.

Table 3
Results of dynamic link prediction in terms of MAR and HITS@10 metrics

Method Email-EU SocialEvl Github

MAR $\downarrow$ HITS@10 $\uparrow$ MAR $\downarrow$ HITS@10 $\uparrow$ MAR $\downarrow$ HITS@10 $\uparrow$

DyRep 35.67 $\pm$ 0.72 0.188 $\pm$ 0.015 33.31 $\pm$ 5.36 0.161 $\pm$ 0.051 93.29 $\pm$ 7.57 0.181 $\pm$ 0.027

LDG $-$ 36.66 $\pm$ 0.43 0.225 $\pm$ 0.004 30.87 $\pm$ 2.87 0.177 $\pm$ 0.035 80.09 $\pm$ 5.32 0.215 $\pm$ 0.019

LDG $+$ 24.08 $\pm$ 0.99 0.349 $\pm$ 0.002 26.14 $\pm$ 0.87 0.232 $\pm$ 0.040 73.04 $\pm$ 2.67 0.223 $\pm$ 0.001

TMAGCN $-$ 24.07 $\pm$ 1.03 0.351 $\pm$ 0.010 25.92 $\pm$ 1.29 0.251 $\pm$ 0.050 64.14 $\pm$ 6.15 0.263 $\pm$ 0.009

TMAGCN $+$ 23.74 $\pm$ 0.14 0.368 $\pm$ 0.007 24.61 $\pm$ 1.22 0.286 $\pm$ 0.042 65.11 $\pm$ 6.03 0.272 $\pm$ 0.007

TMAGCN* 23.29 $\pm$ 0.98 0.371 $\pm$ 0.001 23.12 $\pm$ 1.19 0.313 $\pm$ 0.033 56.80 $\pm$ 5.96 0.291 $\pm$ 0.007

For SocialEvl dataset, there are three types of communication events: SMS, PROXIMITY and CALL. For Github dataset, there are seven types of communication events: ForkEvent (FE), PushEvent (PE), WatchEvent (WE), IssuesEvent (IE), IssueCommentEvent (ICE), PullRequestEvent (PRE) and CommitCommentEvent (CCE). In order to show the necessity of the attentional graph convolutional structure, we further illustrate the dynamic link prediction results of every specific type of communication events in Fig. 5. The series of TMAGCN methods based on the framework of GAT model almost consistently improve results. They increase HIST@10 values and decrease MAR values over DyRep and LDG based models on every specific type of communication event.

Figure 5.
Dynamic link prediction performance of every type of communication events in terms of HITS@10 and MAR on SocialEvl and Github datasets.

In Fig. 6, we take the SocialEvl dataset as an example to plot the dynamic link prediction performances of all methods in terms of HITS@10, and we explore the change of performance over time. Figure 6 shows our method outperforms all the baselines in every slot. The performances of all methods drop over time due to the temporal recency effects on node’s evolution. DyRep and LDG can capture event dynamics well in the first two slots but their performances deteriorate significantly in HITS@10 metric over time. Comparatively, the performances of TMAGCN based methods drop a little over time for all slots and can consistently maintain at a relatively higher level. It demonstrates that features learned through link-level modeling limit the predictive capacity over time, while features learned through temporal motif-level modeling can alleviate the problem to some extent.

Figure 6.
Dynamic link prediction performance in terms of HITS@10 in different time slots on the SocialEvl dataset.

5.3.2 Performance analysis at varying time scales

Method	Email-EU	SocialEvl	Github
DyRep	35.67 $\pm$ 0.72	0.188 $\pm$ 0.015	33.31 $\pm$ 5.36	0.161 $\pm$ 0.051	93.29 $\pm$ 7.57	0.181 $\pm$ 0.027
LDG $-$	36.66 $\pm$ 0.43	0.225 $\pm$ 0.004	30.87 $\pm$ 2.87	0.177 $\pm$ 0.035	80.09 $\pm$ 5.32	0.215 $\pm$ 0.019
LDG $+$	24.08 $\pm$ 0.99	0.349 $\pm$ 0.002	26.14 $\pm$ 0.87	0.232 $\pm$ 0.040	73.04 $\pm$ 2.67	0.223 $\pm$ 0.001
TMAGCN $-$	24.07 $\pm$ 1.03	0.351 $\pm$ 0.010	25.92 $\pm$ 1.29	0.251 $\pm$ 0.050	64.14 $\pm$ 6.15	0.263 $\pm$ 0.009
TMAGCN $+$	23.74 $\pm$ 0.14	0.368 $\pm$ 0.007	24.61 $\pm$ 1.22	0.286 $\pm$ 0.042	65.11 $\pm$ 6.03	0.272 $\pm$ 0.007
TMAGCN*	23.29 $\pm$ 0.98	0.371 $\pm$ 0.001	23.12 $\pm$ 1.19	0.313 $\pm$ 0.033	56.80 $\pm$ 5.96	0.291 $\pm$ 0.007

Noting that the temporal motif-induced adjacency matrix plays an important role in the representation learning, and the time window $\delta$ is an important parameter in capturing temporal motif. In this section, we are interested in uncovering the essential mechanism of evolving graph dynamics by exploring how the performance of our proposed TMAGCN changes at different time scales. We conduct sensitive analysis on Email-EU and Github datasets.

We first plot the distribution of temporal motif instance counts for $\delta=$ 60 seconds, 10 minutes, 1 hour and 1 day in Fig. 7. For each interval, the count in the $i$ -th row and $j$ -th column is the number of instances of motif ${{M}_{i,j}}$ . This motif is the union of the two links in the row label and the link in the column label. For example, there are 36 thousand instances of motif ${{M}_{6,1}}$ in the Github dataset for $\delta=1$ hour.

Then we plot the performance of TMAGCN* for the four different time windows in Fig. 8. We analyze these results in Fig. 8 based on the empirical observations in Fig. 7 uniquely available due to temporal motifs (compared to separate links). Prevalence of non-blocking motif ${{M}_{4,1}}$ , ${{M}_{4,3}}$ , ${{M}_{6,1}}$ and ${{M}_{6,3}}$ in Email-EU and ${{M}_{6,1}}$ in Github indicates that both of them belong to non-blocking communication networks. Both e-mail and Github are not immediate communication tools and replies within one minute are rare. For Email-EU dataset, when the length of time window $\delta=1$ hour, the fractions of counts corresponding to many blocking motifs such as ${{M}_{5,1}}$ , ${{M}_{5,2}}$ and ${{M}_{6,2}}$ obviously rise to a relatively higher level. From $\delta=$ 60 seconds to $\delta=1$ hour, the HITS@10 of Email-EU gradually increase due to the more counts of temporal motifs revealing the dynamic mechanism of Email-EU. When $\delta=$ 1 day, the HITS@10 drop a little, the possible reason for the drop is that many other motif communication patterns irrelevant to the essential dynamic mechanism of Email-EU have emerged and could be noise data for link prediction. In comparison, the HITS@10 of Github consistently increases over time scales due to the dominating fraction of counts corresponding to the main non-blocking motif ${{M}_{6,1}}$ .

5.3.3 Qualitative performance

In this section, we conduct qualitative experiments through a visualization using t-SNE (T-Distribution Stochastic Neighbour Embedding) [62], which extracts transformed feature representations on the SocialEvl dataset, to investigate the discriminative quality of evolving embeddings learned by TMAGCN. In a static graph, a good network visualization usually implies that nodes similar in terms of network

Figure 7.

Counts of temporal motif instances in four time intervals for the Email-EU and Github datasets. The color for the count of motif ${{M}_{i,j}}$ indicates the fraction over all ${{M}_{i,j}}$ on a linear scale. Darker blue means a higher count.

Figure 8.

Dynamic link prediction performance in terms of HITS@10 in different time slots on Email-EU and Github datasets.

topology tend to be visualized close to each other. In a dynamic graph, frequently communicating nodes generally reside closer to each other after training step.

We consider three use cases to demonstrate how the interactions and associations between the nodes change their representations and visualize them to realize the effect. The first use case is the pair of nodes 10 and 15 that have established 2 association events (1 SocializeTwicePerWeek and 1 PoliticalDiscussant), 137 communication events (6 SMS and 131 CALL) in training period and 1 association events (1 PoliticalDiscussant), 34 communication events (34 CALL) in testing period. The second use case is the pair of nodes 43 and 63 that have established 2 association events (1 FacebookAllTaggedPhotos and 1 BlogLivejournalTwitter), 892 communication events (889 Proximity and 3 CALL) in training period and 2 association events (1 FacebookAllTaggedPhotos and 1 BlogLivejournalTwitter), 220 communication events (220 Proximity) in testing period. The third use case is the pair of node 43 and node 10 that have established 2 association events (1 FacebookAllTaggedPhotos and 1 BlogLivejournalTwitter) in training period and 2 association events (1 FacebookAllTaggedPhotos and 1 BlogLivejournalTwitter) in testing period.

Figure 9.

Counts of temporal motif instances of the pair of node 10 and node 15, the pair of node 43 and node 63, and the pair of node 10 and node 43.

Figure 9 shows the counts of temporal motif instances the three pairs of nodes have participated in. Our proposed algorithm 1 finds that node 15 and node 10 have participated in ${{M}_{3,3}}$ once, ${{M}_{5,6}}$ once, ${{M}_{5,1}}$ 56 times, ${{M}_{5,2}}$ 39 times, ${{M}_{6,1}}$ 24 times, and ${{M}_{6,2}}$ 39 times. The main fraction of motifs they participate in are blocking. Prevalence of ${{M}_{5,1}}$ , ${{M}_{5,2}}$ , ${{M}_{6,1}}$ and ${{M}_{6,2}}$ indicates the exclusive intimacy between them without another person getting involved in. Comparatively, node 43 and node 63 have participated in ${{M}_{1,1}}$ once, ${{M}_{1,5}}$ once, ${{M}_{1,6}}$ once, ${{M}_{2,1}}$ 213 times, ${{M}_{2,5}}$ 232 times, ${{M}_{2,6}}$ once, ${{M}_{3,1}}$ 231 times, ${{M}_{3,4}}$ 211 times, ${{M}_{4,1}}$ once, ${{M}_{4,3}}$ once, ${{M}_{4,4}}$ twice, ${{M}_{5,3}}$ twice, ${{M}_{5,4}}$ twice, ${{M}_{6,3}}$ once, ${{M}_{6,4}}$ 288 times and ${{M}_{6,5}}$ 213 times. The main fraction of motifs they participate in are non-blocking. Prevalence of ${{M}_{2,1}}$ , ${{M}_{2,5}}$ , ${{M}_{3,1}}$ , ${{M}_{3,4}}$ , ${{M}_{6,4}}$ and ${{M}_{6,5}}$ indicates their relationship often get another person involved in and is not as intimate as the first pair. Actually, all communication events between them belonging to the type of Proximity indicates they just live on the same floor and don’t have as close relationship as the first pair. The third pair have participated in none of any type of temporal motif instances. According to the fact provided by [58], node 15 represents a graduate student tutors in f290.2 living sector in the dorm building, node 10 represents a sophomore in f290.4, node 43 represents a freshman in f290.4 and node 63 represents a junior in f290.4. Node 15 is the tutor of node 10 and they often exchange information by SMS or CALL communication events. Node 43 and node 63 represent two students from two different grades who live on the same floor.

Figure 10 shows the visualization of evolving embeddings. Different from exploratory analysis in [28], we put the three use cases in the same subplot figure to provide an explicit comparison. Solid lines denote the sampled pairs of nodes. Green hexagons correspond to the sampled frequently communicating pair of nodes with a close relationship. Inverted red triangles correspond to the sampled frequently communicating pair of nodes with a non-intimate relationship. For every subplot figure, we calculate the cosine distances and cosine similarities of node 10 and node 15, node 43 and node 63, and node 10 and node 43.

From the figure, we have the following observations:

(1)

For the first use case: after training, all the four comparing methods DyRep, LDG $+$ , TMAGCN $+$ and TMAGCN* have learned the close relationship between node 10 and node 15 with high cosine similarities – 0.999, 0.997, 0.998 and 0.983, respectively. This observation is aligned with the fact that nodes with larger number of events tend to develop similar features and closer relationship over time, and be visualized close to each other.

(2)

For the second use case: during training period, node 43 resides far from node 63. After training, in DyRep, the cosine similarity of node 43 and node 63 is very high – 0.998, almost equal to the cosine similarity of node 10 and node 15. DyRep tends to consider that node 43 and node 63 have a close relationship based on the large number of communication events between the two nodes. However, the fractions of counts corresponding to the blocking and non-blocking motifs out of the counts for all 36 motifs in Fig. 9 uncover that blocking communication events between node 10 and node 15 are vastly more common, while non-blocking communication events between node 43 and node 63 are prevalent. Our proposed TMAGCN $+$ and TMAGCN* methods on the other hand recognize the interactions between node 43 and node 63 are different from interactions between node 10 and node 15 with relatively lower cosine similarities – 0.717 and 0.865. In LDG $+$ , the cosine similarity of node 43 and node 63 is 0.616, aligned with Our proposed TMAGCN $+$ and TMAGCN* methods.

(3)

For the third use case, node 43 resides close to node 10 in training period but belong to different clusters in testing period since these two nodes share very limited interactions. After training, DyRep and LDG $+$ fail to separate these two node with the cosine distances equaling 0.268 and 0.106, the cosine similarity being very high – 0.732 and 0.894. Our proposed TMAGCN $+$ and TMAGCN* methods can successfully separate these two nodes with the cosine distances equaling 0.366 and 0.408, the cosine similarity being relatively low – 0.634 and 0.592.

These observations demonstrate that TMAGCN can leverage higher-order structural and temporal features to capture communication events effectively and correctly. These advantages cannot be obtained by exploring separate temporal links.

Figure 10.

t-SNE node embeddings on SocialEvl dataset from training period to testing period.

5.3.4 Computational efficiency

Figure 11.

Plots of training loss w.r.t. iteration for dynamic link prediction methods on Email-EU dataset.

Figure 12.

Comparison of (a) Number of training parameters and (b) Time per epoch on Email-EU dataset.

We take Email-EU dataset as an example to plot the loss curves of different methods. We compare the convergence rates of different methods by depicting the training loss curves using the same model configuration and hyper-parameters. The training process is illustrated in Fig. 11. The peak and trough of loss curves correspond to the first batch and last batch of data in each epoch. It is meaningful to focus on the downtrends and smoothness instead of absolute values of loss curves. Overall, TMAGCN based methods achieve faster convergence in comparison to baselines since it leverages multiple relevant graph patterns simultaneously.

We report running times on an AMD EPYC 7742 64-Core Processor system with 256 GB memory. We compare the numbers of training parameters and time costs per epoch of TMAGCN based methods with the compared baselines on Email-EU dataset in Fig. 12. We find that DyRep has the minimum number of training parameters and spends the least time per epoch at the cost of worse link prediction performance. TMAGCN $-$ has almost the same number of training parameters as LDG $-$ , while takes more time per epoch than LDG $-$ . TMAGCN $-$ has less training parameters than LDG $+$ , but takes more time per epoch than LDG $+$ . Based on these observations, we can conclude that bilinear operation is a substantial portion of the training parameters. Bilinear operation and attentional convolution operation are substantial portions of the time cost separately, but the combination of bilinear operation and attentional convolution operation is not the linear addition of their time costs. Although TMAGCN based methods cost more time than baselines (noticeably but not substantially longer time than LDG $+$ ), it is worth for the valuable information uniquely available due to TMAGCN about the mechanisms driving the changes in topological structure of graph and interactions between the nodes.

6. Conclusion and future work

In this work, we proposed a novel model TMAGCN for the task of dynamic link prediction. This work is as the first model that bridges the gap between the power of GCN and temporal motif in dynamic link prediction study. In order to model complex and nonlinear dynamics of evolving graph, we first extracted higher-order structural and temporal features by the temporal motif-based adjacency matrix construction algorithm. Then motivated by the attention mechanism, we adopted the attentional GCN to encode higher-order structural and temporal features into node embeddings. We designed a dynamic attention-based method and a reinforcement learning-based method to combine multiple temporal motif-based attentions. These two methods allow each individual node to make the most of the relevant motif-based neighborhood to propagate and aggregate information in the graph convolutional layers for updating node embeddings. Finally, we predicted future links through the latent mediation process. The experimental results on several real-world temporal networks demonstrate the advantages of the proposed model over state-of-the-art baselines.

The proposed model supports data mining and analysis on a wide range of temporal networks. It have many potential applications such as user behavior modeling for recommender systems and fraud discovery in telecommunication networks. Our future work will involve the extension of three-link temporal motif to more complex temporal motif containing more nodes and links. The multilayer temporal motif will also be explored to provide fine-grained insights on graph evolution by adding labels to each link denoting the type of relationship, e.g., private or public.

Footnotes

Acknowledgments

This research is supported by the National Natural Science Foundation for Young Scholars (No. 62002384), the China Postdoctoral Science Foundation (No. 2020M683760), and the Collaborative Innovation Program of Zhengzhou (No. 162/32410218).

References

Xiao

and Liu

, Link prediction based on feature representation and fusion, Information Sciences 548 (2021), 1–17. doi: 10.1016/j.ins.2020.09.039.

Tang

Liu

and Chen

, Exchange, adopt, evolve: Modeling the spreading of opinions through cognition and interaction in a social network, Information Sciences 551 (2021), 1–22. doi: 10.1016/j.ins.2020.11.043.

Wang

and Gupta

, Zero-Shot Recognition via Semantic Embeddings and Knowledge Graphs, 2018, 6857–6866. doi: 10.1109/CVPR.2018.00717.

Zitnik

and Leskovec

, Predicting multicellular function through multi-layer tissue networks, Bioinform 33(14) (2017), i190–i198. doi: 10.1093/bioinformatics/btx252.

Kumar

Singh

and Biswas

, Link prediction techniques, applications, and performance: A survey, Physica A: Statistical Mechanics and its Applications 553 (2020), 124289. doi: 10.1016/j.physa.2020.124289.

Holme

and Saramgäki

, Temporal networks, Physics Reports 519(3) (2012), 97–125. doi: 10.1016/j.physrep.2012.03.001.

Foulds

J.R.

DuBois

Asuncion

A.U.

Butts

C.T.

and Smyth

, A Dynamic Relational Infinite Feature Model for Longitudinal Social Networks, in: Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2011, Fort Lauderdale, USA, April 11–13, 2011, JMLR Proceedings, Vol. 15, JMLR.org, 2011, pp. 287–295.

Kim

and Leskovec

, Nonparametric Multi-group Membership Model for Dynamic Networks, in: Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5–8, 2013, Lake Tahoe, Nevada, United States, 2013, pp. 1385–1393.

Günes

Ögüdücü

S.G.

and Çataltepe

, Link prediction using time series of neighborhood-based node similarity scores, Data Min. Knowl. Discov. 30(1) (2016), 147–180. doi: 10.1007/s10618-015-0407-0.

10.

Ozcan

and Ögüdücü

S.G.

, Temporal Link Prediction Using Time Series of Quasi-Local Node Similarity Measures, in: 15th IEEE International Conference on Machine Learning and Applications, ICMLA 2016, Anaheim, CA, USA, December 18–20, 2016, IEEE Computer Society, 2016, pp. 381–386. doi: 10.1109/ICMLA.2016.0068.

11.

and Wang

, A bipartite network-based method for prediction of long non-coding RNA-protein interactions, Genomics, Proteomics & Bioinformatics 14(1) (2016), 62–71. doi: 10.1016/j.gpb.2016.01.004.

12.

Junuthula

R.R.

K.S.

and Devabhaktuni

V.K.

, Evaluating Link Prediction Accuracy in Dynamic Networks with Added and Removed Edges, in: 2016 IEEE International Conferences on Big Data and Cloud Computing (BDCloud), Social Computing and Networking (SocialCom), Sustainable Computing and Communications (SustainCom), BDCloud-SocialCom-SustainCom 2016, Atlanta, GA, USA, October 8–10, 2016, IEEE Computer Society, 2016, pp. 377–384. doi: 10.1109/BDCloud-SocialCom-SustainCom.2016.63.

13.

Leskovec

Kleinberg

J.M.

and Faloutsos

, Graph evolution: Densification and shrinking diameters, ACM Trans. Knowl. Discov. Data 1(1) (2007), 2. doi: 10.1145/1217299.1217301.

14.

Gao

and Zhang

, A Deep Learning Approach to Link Prediction in Dynamic Networks, in: Proceedings of the 2014 SIAM International Conference on Data Mining, Philadelphia, Pennsylvania, USA, April 24–26, 2014, SIAM, 2014, pp. 289–297. doi: 10.1137/1.9781611973440.33.

15.

Nguyen

Lee

Rossi

Ahmed

Koh

and Kim

, Continuous-Time Dynamic Network Embeddings, 2018, 969–976. doi: 10.1145/3184558.3191526.

16.

Zhang

Xiong

Kong

and Zhu

, Learning Node Embeddings in Interaction Graphs, 2017, 397–406. doi: 10.1145/3132847.3132918.

17.

Zhou

Yang

Ren

and Zhuang

, Dynamic Network Embedding by Modeling Triadic Closure Process, in: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2–7, 2018, AAAI Press, 2018, pp. 571–578.

18.

Pei

Fletcher

and Pechenizkiy

, Dynamic network representation learning via gaussian embedding, in: NeurIPS 2019 Workshop on Graph Representation Learning, 2019.

19.

Zhou

Cui

Zhang

Yang

Liu

and Sun

, Graph Neural Networks: A Review of Methods and Applications, CoRR abs/1812.08434, 2018.

20.

Zhang

Cui

and Zhu

, Deep Learning on Graphs: A Survey, CoRR abs/1812.04202, 2018.

21.

Pan

Chen

Long

Zhang

and Yu

P.S.

, A Comprehensive Survey on Graph Neural Networks, CoRR abs/1901.00596, 2019.

22.

Beutel

Covington

Jain

Gatto

and Chi

, Latent Cross: Making Use of Context in Recurrent Recommender Systems, 2018, 46–54. doi: 10.1145/3159652.3159727.

23.

C.-Y.

Ahmed

Beutel

Smola

and Jing

, Recurrent Recommender Networks, 2017, 495–503. doi: 10.1145/3018661.3018689.

24.

Zhu

Liao

Wang

Guan

Liu

and Cai

, What to Do Next: Modeling User Behaviors by Time-LSTM, in: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19–25, 2017, ijcai.org, 2017, pp. 3602–3608.

25.

Chen

and Zheng

, GC-LSTM: Graph Convolution Embedded LSTM for Dynamic Link Prediction, ArXiv abs/1812.04206, 2018.

26.

Lei

Qin

Bai

Zhang

and Yang

, GCN-GAN: A Non-linear Temporal Link Prediction Model for Weighted Dynamic Networks, in: 2019 IEEE Conference on Computer Communications, INFOCOM 2019, Paris, France, April 29–May 2, 2019, IEEE, 2019, pp. 388–396. doi: 10.1109/INFOCOM.2019.8737631.

27.

Kipf

T.N.

and Welling

, Semi-Supervised Classification with Graph Convolutional Networks, in: 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24–26, 2017, Conference Track Proceedings, OpenReview.net, 2017.

28.

Trivedi

Farajtabar

Biswal

and Zha

, DyRep: Learning Representations over Dynamic Graphs, in: 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6–9, 2019, OpenReview.net, 2019.

29.

Knyazev

Augusta

and Taylor

G.W.

, Learning Temporal Attention in Dynamic Graphs with Bilinear Interactions, CoRR abs/1909.10367, 2019.

30.

Milo

Shen-Orr

ltzkovitz

Kashtan

Chktovskii

and Alan

, Network Motifs: Simple Building Blocks of Complex Networks, 2011. ISBN 9781400841356. doi: 10.1515/9781400841356.217.

31.

Paranjape

Benson

A.R.

and Leskovec

, Motifs in Temporal Networks, in: Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, WSDM 2017, Cambridge, United Kingdom, February 6–10, 2017, ACM, 2017, pp. 601–610. doi: 10.1145/3018661.3018731.

32.

Rossi

R.A.

Ahmed

N.K.

and Koh

, Higher-order Network Representation Learning, in: Companion of the The Web Conference 2018 on The Web Conference 2018, WWW 2018, Lyon, France, April 23–27, 2018, ACM, 2018, pp. 3–4. doi: 10.1145/3184558.3186900.

33.

Rossi

R.A.

Zhou

and Ahmed

N.K.

, Estimation of Graphlet Counts in Massive Networks, IEEE Trans. Neural Networks Learn. Syst. 30(1) (2019), 44–57. doi: 10.1109/TNNLS.2018.2826529.

34.

Spiliopoulou

, Evolution in Social Networks: A Survey, in: Social Network Data Analytics, Springer, 2011, pp. 149–175. doi: 10.1007/978-1-4419-8462-3_6.

35.

Martínez

Berzal

and Talavera

J.C.C.

, A Survey of Link Prediction in Complex Networks, ACM Comput. Surv. 49(4) (2017), 69:1–69:33. doi: 10.1145/3012704.

36.

Ibrahim

N.M.A.

and Chen

, Link prediction in dynamic social networks by integrating different types of information, Appl. Intell. 42(4) (2015), 738–750. doi: 10.1007/s10489-014-0631-0.

37.

Cheng

Aggarwal

C.C.

Chen

and Wang

, Link Prediction with Spatial and Temporal Consistency in Dynamic Networks, in: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19–25, 2017, ijcai.org, 2017, pp. 3343–3349. doi: 10.24963/ijcai.2017/467.

38.

Ibrahim

N.M.A.

and Chen

, An efficient algorithm for link prediction in temporal uncertain social networks, Inf. Sci. 331 (2016), 120–136. doi: 10.1016/j.ins.2015.10.036.

39.

Rahman

Saha

T.K.

Hasan

M.A.

K.S.

and Reddy

C.K.

, DyLink2Vec: Effective Feature Representation for Link Prediction in Dynamic Networks, CoRR abs/1804.05755, 2018. http://arxiv.org/abs/1804.05755.

40.

Nguyen

G.H.

Lee

J.B.

Rossi

R.A.

Ahmed

N.K.

Koh

and Kim

, Continuous-Time Dynamic Network Embeddings, in: Companion of the The Web Conference 2018 on The Web Conference 2018, WWW 2018, Lyon, France, April 23–27, 2018, ACM, 2018, pp. 969–976. doi: 10.1145/3184558.3191526.

41.

M.V.

and L.S.

, Dynamic Link Prediction in Biomedical Domain, in: ICCVBIC 2019. Advances in Intelligent Systems and Computing, Springer Press, 2019, p. vol 1108.

42.

Yue

Wang

Huang

Parthasarathy

Moosavinasab

Huang

Lin

S.M.

Zhang

and Sun

, Graph Embedding on Biomedical Networks: Methods, Applications, and Evaluations, CoRR abs/1906.05017, 2019.

43.

Przulj

, Biological network comparison using graphlet degree distribution, Bioinform. 26(6) (2010), 853–854. doi: 10.1093/bioinformatics/btq091.

44.

Sporns

and Kötter

, Motifs in brain networks, PLoS Biology 2 (2004), e369. doi: 10.1371/journal.pbio.0020369.

45.

Wang

and Yu

, Identification of important nodes in directed biological networks: A network motif approach, PloS One 9 (2014), e106132. doi: 10.1371/journal.pone.0106132.

46.

Rotabi

Kamath

Kleinberg

and Sharma

, Detecting Strong Ties Using Network Motifs, 2017. doi: 10.1145/3041021.3055139.

47.

Ugander

Backstrom

and Kleinberg

, Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections, in: WWW 2013 – Proceedings of the 22nd International Conference on World Wide Web, 2013.

48.

Benson

A.R.

Gleich

D.F.

and Leskovec.

, Higher-order organization of complex networks, Science 353 (2016), 163–166.

49.

Monti

Otness

and Bronstein

M.M.

, MOTIFNET: A Motif-Based Graph Convolutional Network for Directed Graphs, in: 2018 IEEE Data Science Workshop, DSW 2018, Lausanne, Switzerland, June 4–6, 2018, IEEE, 2018, pp. 225–228. doi: 10.1109/DSW.2018.8439897.

50.

Zhao

Song

Lee

D.L.

Chen

and Gao

, Ranking Users in Social Networks With Higher-Order Structures, in: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2–7, 2018, AAAI Press, 2018, pp. 232–240.

51.

Zhang

Tang

Zhong

Song

Hall

and Sun

, StructInf: Mining Structural Influence from Social Streams, in: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4–9, 2017, San Francisco, California, USA, AAAI Press, 2017, pp. 73–80.

52.

Yin

Benson

A.R.

Leskovec

and Gleich

D.F.

, Local Higher-Order Graph Clustering, in: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada, August 13–17, 2017, ACM, 2017, pp. 555–564. doi: 10.1145/3097983.3098069.

53.

Yang

Liu

Zheng

V.W.

and Han

, Node, Motif and Subgraph: Leveraging Network Functional Blocks Through Structural Convolution, in: IEEE/ACM 2018 International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2018, Barcelona, Spain, August 28–31, 2018, IEEE Computer Society, 2018, pp. 47–52. doi: 10.1109/ASONAM.2018.8508729.

54.

Pinar

Seshadhri

and Vishal

, ESCAPE: Efficiently Counting All 5-Vertex Subgraphs, in: Proceedings of the 26th International Conference on World Wide Web, WWW 2017, Perth, Australia, April 3–7, 2017, ACM, 2017, pp. 1431–1440. doi: 10.1145/3038912.3052597.

55.

Stefani

L.D.

Epasto

Riondato

and Upfal

, TRIÈST: Counting local and global triangles in fully dynamic streams with fixed memory size, ACM Trans. Knowl. Discov. Data 11(4) (2017), 43:1–43:50. doi: 10.1145/3059194.

56.

Veličković

Cucurull

Casanova

Romero

Liò

and Bengi

, Graph Attention Networks, in: International Conference on Learning Representations, 2018.

57.

Mnih

Heess

Graves

and koray kavukcuoglu, Recurrent Models of Visual Attention, in: Advances in Neural Information Processing Systems 27, Vol. 27, 2014, pp. 2204–2212.

58.

Madan

Cebrian

Moturu

Farrahi

and Pentland

, Sensing the “health state” of a community, IEEE Pervasive Computing 11(4) (2012), 36–45.

59.

Zhang

Ren

and Sun

, Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification, in: 2015 IEEE International Conference on Computer Vision, ICCV 2015, Santiago, Chile, December 7–13, 2015, IEEE Computer Society, 2015, pp. 1026–1034. doi: 10.1109/ICCV.2015.123.

60.

Glorot

and Bengio

, Understanding the difficulty of training deep feedforward neural networks, in: Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2010, Chia Laguna Resort, Sardinia, Italy, May 13–15, 2010, JMLR Proceedings, Vol. 9, JMLR.org, 2010, pp. 249–256.

61.

Kingma

D.P.

and Ba

, Adam: A Method for Stochastic Optimization, in: 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7–9, 2015, Conference Track Proceedings, 2015.

62.

van der Maaten

and Hinton

, Visualizing Data using t-SNE, Journal of Machine Learning Research 9(86) (2008), 2579–2605.

63.

Zhao

Song

Lee

D.L.

Chen

and Gao

, Ranking Users in Social Networks with Motif-based PageRank, IEEE Transactions on Knowledge and Data Engineering, 2019, 1–1. doi: 10.1109/TKDE.2019.2953264.

64.

Williams

R.J.

, Simple statistical gradient-following algorithms for connectionist reinforcement learning, Machine Learning 8(3) (1992), 229–256.

Method	Email-EU		SocialEvl		Github
	MAR $\downarrow$	HITS@10 $\uparrow$	MAR $\downarrow$	HITS@10 $\uparrow$	MAR $\downarrow$	HITS@10 $\uparrow$
DyRep	35.67 $\pm$ 0.72	0.188 $\pm$ 0.015	33.31 $\pm$ 5.36	0.161 $\pm$ 0.051	93.29 $\pm$ 7.57	0.181 $\pm$ 0.027
LDG $-$	36.66 $\pm$ 0.43	0.225 $\pm$ 0.004	30.87 $\pm$ 2.87	0.177 $\pm$ 0.035	80.09 $\pm$ 5.32	0.215 $\pm$ 0.019
LDG $+$	24.08 $\pm$ 0.99	0.349 $\pm$ 0.002	26.14 $\pm$ 0.87	0.232 $\pm$ 0.040	73.04 $\pm$ 2.67	0.223 $\pm$ 0.001
TMAGCN $-$	24.07 $\pm$ 1.03	0.351 $\pm$ 0.010	25.92 $\pm$ 1.29	0.251 $\pm$ 0.050	64.14 $\pm$ 6.15	0.263 $\pm$ 0.009
TMAGCN $+$	23.74 $\pm$ 0.14	0.368 $\pm$ 0.007	24.61 $\pm$ 1.22	0.286 $\pm$ 0.042	65.11 $\pm$ 6.03	0.272 $\pm$ 0.007
TMAGCN*	23.29 $\pm$ 0.98	0.371 $\pm$ 0.001	23.12 $\pm$ 1.19	0.313 $\pm$ 0.033	56.80 $\pm$ 5.96	0.291 $\pm$ 0.007

Temporal motif-based attentional graph convolutional network for dynamic link prediction

Abstract

Keywords

1. Introduction

1 Graph and network can be used interchangeably.

Dynamic Link prediction.

Network motif.

3. Preliminaries

3.1 Notations

Table 1 Table of notations

4.2 Temporal motif-based adjacency matrix construction

4.3 Temporal motif-based graph convolutional networks

4.3.1 Convolutional layer with single temporal motif-based attention

5.1 Datasets

Email-EU.

SocialEvl.

Github.

Table 2 Summary statistics of temporal network datasets

5.3 Results

5.3.3 Qualitative performance

Footnotes

Acknowledgments

References

¹
Graph and network can be used interchangeably.

Table 1
Table of notations

Table 2
Summary statistics of temporal network datasets