Encoder-Decoder Architecture for Supervised Dynamic Graph Learning: A Survey

In temporal data, periodicity is a frequent seen phenomena. For example, $50\%$ to $70\%$ of human movements can be explained by periodic behavior pattern[24]. Periodic pattern can be learnt by sequential model in DTDG setting. The learning model infers the underlying timestamps by the ordering and position of the input snapshots. However, in CTDG, this is unfeasible without the explicit use of time. Kazemi et al.[23] proposed Time2Vec to encode time and help the downstream learning model to recognize periodic pattern as well as linear time pattern.

TGAT[6] applies time2vec in message passing to assign more weight to neighbors with similar periodic patterns to target nodes. Explicit use of time with Time2Vec helps CTDG learning better learn periodical patterns.

Information flowing between two given nodes needs to traverse their shortest path. The difference in path length and edge property results in the difference in the flowing information’s arrival time at the target node. Temporal Distance between starting nodes and destination nodes is one metric to evaluate how much time is needed for the information to flow from the starting one to the destination[25]. Because the temporal distance from the target node to its neighbors has different value, most up-to-date information with respect to its neighbors is sent at different timestamp. This phenomena is described by the concept Vector Clock[15]. Since different nodes have different vector clocks,they evolve differently from each other. Temporal Point Process(TPP)[26] is one of the temporal learning methods that is capable to learn the impact from vector clock. With TPP and the explicit use of time, a learning algorithm could recognize the impacts from a given node’s vector clock to its evolution.

Moreover, the explicit use of time makes time prediction tasks feasible in dynamic graph learning. For the best of our knowledge, time prediction tasks could only be done with explicit time learning methods. Figure 1 shows the overall architecture of how this survey organizes different learning methods.

Static graph encoders could be categorized as non-attributed and attributed graph encoder. Non-attributed static graph encoders are not widely discussed in academia these days, due to their incapability to leverage graph attributes. This motivates the recent exploration in attributed static graph embedding approaches. We will first review briefly the non-attributed static graph embedding methods, and then provide an in-depth review of attributed static graph embedding methods. For those interested in a more detailed non-attributed static graph representation learning algorithms, we refer them to read the recent work of Hamilton et al. [14], Cui et al.[58] and kazemi et al.[12].

A basic form of non-attributed static graph encoder is the shallow embedding approach, which aims to transform graph structure and property to node-level graph embedding [58]. However, graph attributes are not considered in shallow embedding. Shallow embedding includes

• •

  Matrix Factorization based approaches such as Laplacian Eigenmaps[36], Graph Factorization[37], GraRep[38], HOPE[39] and M-NMF[40];

• •

  Random walk based approaches such as DeepWalk[41], TADW[42], HARP[43] and node2vec[44].

• •

  Other approaches, such as LINE[45] .

Shallow embedding encoder is simply an embedding look up based on node ids, there is no parameter sharing between nodes. Hence, the computation is inefficient and the trained encoder cannot be used for new graphs with unseen nodes [14].

To overcome these challenges and leverage graph attributes in the embedding generating process, multiple approaches are proposed to parameterized graph embedding (i.e, parameter sharing between nodes).

Deep Neural Graph Representation (DNGR)[46] and Structural Deep Network Embeddings (SDNE)[47] apply autoencoder[59] to map a high-dimension node similarity matrix to a low-dimension node embedding. These two approaches enable sharing of parameters, which can provide an efficient computation and be applied with unseen nodes.

To leverage graph attributes in static graph embedding generation, attributed static graph encoders are proposed. Attributed static graph encoders are based on Graph Neural Network (GNN)[17]. Such algorithms follow a message passing schema to aggregate neighborhood information and generate embedding for the target node [1]. In this survey, we focus on some widely used GNN based attributed graph encoders which are the foundation of dynamic graph encoders to review in later section.

GNN assigns state $\mathbf{h}_{v_{i}}$ to node $v_{i}$ of the input graph. Given mappings $N(v_{i})$ to be all neighbors of node $v_{i}$, mapping $E(v_{i})$ to be all edges connecting node $v_{i}$ and its neighbors $N(v_{i})$, $f_{w}(\cdot)$ to be the neighborhood information aggregating function, state $\mathbf{h}_{v_{i}}$ at the $k$ layer is defined as in Eqn. (5).

which can be written as Eqn. (6) when there is no positional information for the neighbours.

The output state from the last layer $n$ is the graph embedding $\mathbf{z}_{v_{i}}$:

This state updating process is described as a message passing process in [1, 48]. In each iteration, message from each node is passed through the edges to their neighbours. To learn local neighborhood structure, $k$ is required to be a small value, such as $k=2$ in the learning of $2$-hop neighborhood information. With Banach’s fixed point theorem, the state values will converge with the update of state in iterations [60, 1]. Therefore, to learn the global graph structure, we can just continue the iterative updating until the change in the state value between two consecutive iterations is close to 0 as shown in Eqn. (8). When the state values converge, the global graph structure and property is embedded in the resulting embedding.

Stacking the converged state value $z$ of each node together to produce $Z$, we obtain the node-wise embedding of the input graph. GraphSAGE[31] and column network[61] are following the same schema with different neighborhood information aggregation functions.

Inspired by GNN, Graph Convolution Network (GCN)[49] is a generalization of Convolution Neural Network (CNN)[62] to static graph data structure with spectral method. GCN applies graph Laplacian to generate the feature maps which are shared within the whole graph as in CNN. Given the adjacency matrix $\mathbf{A}$, $\mathbf{\hat{A}}=\mathbf{A}+\mathbf{I}_{N}$, the diagonal degree matrix $\mathbf{\hat{D}}:\mathbf{\hat{D}}_{ii}=\sum_{j}\mathbf{\hat{A}}_{ij}$, the graph Laplacian is calculated as follows:

Moreover, a convolution layer with the output of $d$ feature maps is calculated as follows:

where $\mathbf{X}\in\mathcal{R}^{|V|\times d}$ is the input node feature matrix with $d$ features and $\mathbf{W}\in\mathcal{R}^{d\times d^{\prime}}$ is the layer weight matrix to generate $d^{\prime}$ feature maps. The output $\mathbf{Z}$ of a hidden convolution layer is usually passed to an ReLU activation function, and the output of activation function will then be passed to the next layer as the input. As an example, a classic two layers GCN with softmax activation in the output layer has the form in Eqn. (11).

One example of GCN as static graph encoder to learn the neighborhood structure for each snapshot and a sequential decoder to learn the temporal pattern between snapshots is AddGraph[51] .

Similar to GCN, Graph Attention Network (GAT) [2] applies the attention mechanism [63, 64] to determine the importance of neighboring nodes in the neighborhood aggregation for the target node:

where $\mathbf{Q}$ is the linear projection of the target node’s input state $\mathbf{h}_{v_{i}}$ from the previous layer. $\mathbf{K}$ and $\mathbf{V}$ are the linear projections of the input state of the $v_{i}$’s neighboring nodes:

The function $\text{score}(\cdot)$ calculates a score representing how well $\mathbf{Q}$ align to $\mathbf{K}$. The alignment scores for $v_{i}$’s neighborhood $N(v_{i})$ are then normalized by a softmax layer. The output of the whole attention layer is the product of the normalized alignment score and the linear projection $\mathbf{V}$.

In Transformer [64], the score function is the dot product of $Q$ and $K$, while the score function is a leaky ReLU layer in Graph Attention Network (GAT)[2, 55]. GAT is used as static graph encoder to learn DTDG in Dysat[5]. All attributed static graph encoders can be used to generate embedding in a supervised or unsupervised manner[31, 50, 49, 2, 61].

DTDG can be considered as a time series of snapshots. Hence, traditional time series methods can be used naturally as decoders to learn temporal patterns. Exponential Moving Average (EMA) and Auto-Regressive Integrated Moving Average (ARIMA) are two widely-used methods, which are used as decoders in previous works [65, 66, 67]. As an example, Eqn. (14) shows the equation of EMA with a predefined smoothing factor $\alpha\in(0,1)$.

RNN based methods are frequently-used supervised sequential decoder and are capable to learn temporal correlation. A basic form of RNN decoders is defined by a recurrent state function which takes the previous state and the current embedding as input[59]:

The generated state is used as the input in the output unit which is usually a Feed forward Neural Network (FNN):

One frequently used RNN model is the Long Short Term Memory (LSTM)[68] which better learns long-term temporal pattern. For example, Seo et al.[69] applied the spectral GCN[75] as static graph encoder and LSTM as decoder; Narayan et al.[76] used a different GCN[52] as static graph encoder and LSTM as decoder; Manessi et al.[53] and Mohanty et al.[54] also used different version of GCN as static graph encoder and LSTM as decoder to perform dynamic graph learning. Yuan et al.[70] applies message passing GNN as static graph encoder and a four gates LSTM as sequential decoder to learn the dynamic graph constructed from video frames and performs object detection. DyGGNN[71] uses a gated graph neural network[77] as encoder and LSTM as decoder. Bogaets et al.[72] applies CNN as static graph encoder and LSTM as sequential decoder in traffic forecasting for road network in the city of Xi’an.

Conv1d is used in time series analysis[78]. Therefore, it is naturally to use as the sequential decoder to learn the temporal pattern. Unlike RNN families, Conv1d only learns short-term temporal patterns in the given time frame. Periodicity of those short term temporal patterns could be learnt by stacking multiple Conv1d layers. By carefully setting the size of each feature map, Conv1d inputs the embedding of a given node for $n$ most recent snapshots $[\mathbf{z}_{v_{i},t_{1}},\mathbf{z}_{v_{i},t_{2}},\cdots,\mathbf{z}_{v_{i},t_{n}}]$, and generates the decoded state $\mathbf{h}_{v_{i},t_{n}}$ for node $v_{i}$ at time $t_{n}$:

The decoded state is then pass to the output unit as in Eqn. (16).

GraphTCN[73] applies a GAT based static graph encoder and Conv1d as the sequential decoder to learn the spatial and temporal information in Human Trajectory Prediction.

Attention mechanism is proved to perform very well in sequential data learning [63, 79]. As in Eqn. (18), given the node embedding $\mathbf{Z}_{v_{i}}$ of the target node $v_{i}$, each element encodes a snapshot from the observation period $[t_{1},t_{2},\cdots,t_{n-1},t_{n}]$, TSA uses each element in $\mathbf{Z}_{v_{i}}$ as a query to attend over the whole input history $\mathbf{Z}_{v_{i},[t_{1}:t_{n}]}$ to generate the temporal graph embedding for the corresponding snapshot. The output of a TSA layer $\mathbf{H}_{v_{i}}$ has the same time dimension as the input, such that it is feasible to stack multiple TSA layers to learn the evolution of its local neighborhood structure and attributes over time.

As in Eqn. (12), Dysat[5] applied TSA as the sequential decoder in DTDG learning. Their score function is shown in Eqn. (19).

To the best of our knowledge, there is no explicit time sequential decoder proposed for supervised DTDG learning. Because the snapshots are taken in a regular frequency, temporal information is revealed in the ordering and the position of the snapshots. However, without using time as a learning feature, implicit time sequential decoder is not capable to perform time prediction tasks as discussed in Sec. 2.

Recent developments commonly use attributed dynamic graph embedding as an encoder to learn both graph structures and temporal correlations. The generated dynamic graph embedding is then fed to a simple supervised predictive model as an decoder to conduct prediction.

Inspired by the success of network attention mechanism in learning sequence data[64], Xu et al. proposed the Temporal Attention mechanism as the dynamic graph encoder in Temporal Graph Attention Network (TGAT). It assumes that more critical temporal information are revealed in the relative time span, compared to the absolute time value. However attributes self-updating is not considered in its temporal learning framework.

With this assumption, Temporal Attention applies Time2Vec[23] to capture critical temporal information from the dynamic graph. Time2Vec aims to generate a simple vector representation of time so as to enable different learning algorithms to learn the temporal correlation as well as the periodicity with the explicit use of time. Given a scalar notion of time $\Delta t$, which could be time difference in CTDG setting, its naive Time2Vec encoding $\text{t2v}(\Delta t)$, is a vector of predefined size $d$ and calculated as:

where $w_{i}$ and $\varphi_{i}$ are trainable weight or predefined weight, and $f$ is a periodic function, such as $\text{sin}(\cdot)$ and $\text{cos}(\cdot)$. Time2Vec helps the learning model to learn temporal correlation by simple linear time projection when $i=1$; and it helps to learn the periodicity of time by kernel learning when $1<i\leq d$ [6].

TGAT applied a modified version of Time2Vec to calculate the functional encoding of a given node $v_{i}$ at time $t$:

where $\mathbf{x}_{v_{i},t_{i}}$ is the node feature vector for node $v_{i}$ at time $t_{i}$; $\mathbf{e}_{ij,t_{j}}$ is the edge feature vector for the edge between node $v_{i}$ and $v_{j}$ at time $t_{j}$. In Eqn. (29a), if $v_{j}=v_{i}$, $\mathbf{e}_{ij,t_{j}}$ is vector of zeros.

With the functional encoding, temporal attention calculates the query, key and value for $v_{i}$ at time $t_{i}$ as:

and the output state of the target node $v_{i}$ is given by Eqn. (12):

As discussed in Sec. 4, external factors have major contribution to a dynamic graph’s evolution. RNN-based CTDG encoder follows the Three Stages Recurrent Temporal Learning Frameworkto capture the external factors contributing to the node attribute self-update. RNN-based encoder first generates impression from the observed events related to the target node by a memory function, and then maintains its memory related to the target node by feeding the impression to a sequential model. Node embedding is generated from the maintained memory optionally together with other factors, such as node embedding from other kinds of encoder, embedding from the observed events, and embedding from the timestamps.

Temporal Graph Neural Network (TGN)[10] provides a general framework for RNN based encoder. TGN consists of two components which are the memory component and embedding component. The memory component represents the model’s memory for a given node’s history. we can denote the memory of node $v_{i}$ at time $t$ by vector $\mathbf{s}_{v_{i},t}$. $\mathbf{s}_{v_{i},t}$ is updated when an updating event involving node $v_{i}$ is encountered. If the event is a node-wise event with new node attribute vector $\mathbf{x}_{v_{i},t}$, the message to $\mathbf{s}_{v_{i},t}$ will be calculated as shown in Eqn. (32), where $t^{-}$ is the timestamp for the last observation for node $v_{i}$ before $t$ and $\Delta t$ is the time span between $t^{-}$ and $t$:

For an interaction event with new edge feature vector $\mathbf{e}_{ij,t}$ indicating node $v_{i}$ as source and $v_{j}$ as destination, the message is calculated as shown in Eqn. (33a) and (33b), respectively.

For an undirected network, $\text{msg}_{s}$ and $\text{msg}_{d}$ share the same parameters.

Once the messages for all input events with the target node $v_{i}$ involved are generated, they are aggregated as described in Eqn. (34), where $t^{-}<t_{1},\dots,t_{b}<=t$:

The $\text{agg}(\cdot)$ refers to a aggregation function, which can be a trainable deep learning layer (e.g., RNN, LSTM), or a simple aggregation without trainable weight (e.g., the mean of those messages, the most recent message). The $\text{mem}(\cdot)$ function is a deep learning layer representing the memory of the model, and should be selected from the RNN family. The output of the memory component $s_{i,t}$ can be used directly as the resulted node embedding as in Jodie[86, 87], Know-Evolve[7] and DyREP[34].

However, as proposed by Kazemi et al. [12], there is a so-called memory staleness problem for nodes that are not active for a relatively long time depending on the context. The memory $\mathbf{s}_{v_{i},t^{-}}$ of these kind of node is not updated for a long time. Once a new event arrives, the outdated memory has the same impact as a recent memory. When calculating the new memory $\mathbf{s}_{v_{i},t}$, this is not desirable when the events happened long time ago has not much impact to the graph’s evolution. For example, two users with past frequent connections may not be currently connected in a call social network, since one of the users changes the phone number. A new event for an abandoned number represents that this number is recycled and used by a different user, and the history for this number is no longer meaningful. To overcome this challenge, TGN proposed the embedding component which uses a time embedding [23, 6] as one of the input features in inference and could be trained to recognize the impact of staled memory.

The embedding component $\mathbf{z}_{v_{i},t}$ has a general form as the following message passing schema:

where $f(\cdot)$ is a neighbour node aggregation function and $t_{j}$ is the timestamp that the last edge updating event observed between $v_{i}$ and $v_{j}$.

The embedding component $\mathbf{z}_{v_{i},t}$ has different implementations and can generate embedding without neighborhood information aggregation. For example, it could be as simple as just the identify function of the memory $\mathbf{s}_{v_{i},t}$; the time projection used in Jodie [87]:

A MLP-TGAT network structure takes the states of the target node $v_{i}$ and its neighbors from the last layer and the Time2Vec embedding of their last updating events’ time stamps $\text{t2v}(t-\mathbf{T}_{N(v_{i})})$ as input, the input state $\mathbf{h}_{v_{i},t}^{(1)}$ of the first layer is the memory $\mathbf{s}_{v_{i},t}$ and the output state $\mathbf{h}_{v_{i},t}^{(l)}$ of the last layer would be the resulting embedding:

Similarly, Temporal Graph Sum is proposed in TGN [10]:

APAN[35] applies an asynchronous mail propagator to over come the out-of-order event arrivial issue in TGN’s node memory units design. In on-line training, graph updating events are not guaranteed to arrive in timestamp order. This will bring instability to RNN based CTDG encoder such as TGN. The asynchronous mail propagator fixes this issue by storing the incoming events in their timestamp order.