---
abstract: 'Graph representation learning resurges as a trending research subject owing to the widespread use of deep learning for Euclidean data, which inspire various creative designs of neural networks in the non-Euclidean domain, particularly graphs. With the success of these graph neural networks (GNN) in the static setting, we approach further practical scenarios where the graph dynamically evolves. For this case, combining the GNN with a recurrent neural network (RNN, broadly speaking) is a natural idea. Existing approaches typically learn one single graph model for all the graphs, by using the RNN to capture the dynamism of the output node embeddings and to implicitly regulate the graph model. In this work, we propose a different approach, coined EvolveGCN, that uses the RNN to evolve the graph model itself over time. This model adaptation approach is model oriented rather than node oriented, and hence is advantageous in the flexibility on the input. For example, in the extreme case, the model can handle at a new time step, a completely new set of nodes whose historical information is unknown, because the dynamism has been carried over to the GNN parameters. We evaluate the proposed approach on tasks including node classification, edge classification, and link prediction. The experimental results indicate a generally higher performance of EvolveGCN compared with related approaches.'
author:
- 'Aldo Pareja$^{1,2}$[^1]'
- 'Giacomo Domeniconi$^{1,2}$'
- 'Jie Chen$^{1,2}$[^2]'
- 'Tengfei Ma$^{1,2}$'
- 'Toyotaro Suzumura$^{1,2}$'
- |
    \
    Hiroki Kanezashi$^{1,2}$
- |
    Tim Kaler$^{1,3}$Charles E. Leisersen$^{1,3}$ $^1$MIT-IBM Watson AI Lab, $^2$IBM Research, $^3$MIT CSAIL\
    {Aldo.Pareja, Giacomo.Domeniconi1}@ibm.com, chenjie@us.ibm.com\
    Tengfei.Ma1@ibm.com, {tsuzumura, hirokik}@us.ibm.com, {tfk, cel}@mit.edu
bibliography:
- 'reference.bib'
title: 'EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs'
---

Introduction
============

Graphs are ubiquitous data structures that model the pairwise interactions between entities. Learning with graphs encounters unique challenges, including their combinatorial nature and the scalability bottleneck, compared with Euclidean data (e.g., images, videos, speech signals, and natural languages). With the remarkable success of deep learning for the latter data types, there exist renewed interests in the learning of graph representations [@Perozzi2014; @Tang2015; @Cao2015; @Ou2016; @Grover2016] on both the node and the graph level, now parameterized by deep neural networks [@Bruna2014; @Duvenaud2015; @Defferrard2016; @Li2016; @Gilmer2017; @Kipf2017; @Hamilton2017; @Jin2017; @Chen2018; @Velickovic2018].

These neural network models generally focus on a given, static graph. In real-life applications, however, often one encounters a dynamically evolving graph. For example, users of a social network develop friendship over time; hence, the vectorial representation of the users should be updated accordingly to reflect the temporal evolution of their social relationship. Similarly, a citation network of scientific articles is constantly enriched due to frequent publications of new work citing prior art. Thus, the influence, and even sometimes the categorization, of an article varies along time. Update of the node embeddings to reflect this variation is desired. In financial networks, transactions naturally come with time stamps. The nature of a user account may change owing to the characteristics of the involved transactions (e.g., an account participates money laundering or a user becomes a victim of credit card fraud). Early detection of the change is crucial to the effectiveness of law enforcement and the minimization of loss to a financial institute. These examples urge the development of dynamic graph methods that encode the temporal evolution of relational data.

Built on the recent success of graph neural networks (GNN) for static graphs, in this work we extend them to the dynamic setting through introducing a recurrent mechanism to update the network parameters, for capturing the dynamism of the graphs. A plethora of GNNs effectively perform information fusion through aggregating node embeddings from one-hop neighborhoods recursively. A majority of the parameters of the networks is the linear transformation of the node embeddings in each layer. We specifically focus on the graph convolutional network (GCN) [@Kipf2017] because of its simplicity and effectiveness. Then, we propose to use a recurrent neural network to inject the dynamism into the parameters of the GCN, which forms an evolving sequence.

It is worthwhile to distinguish here, on a conceptual level, the proposed method from those [@Seo2016; @Manessia2017; @Narayan2018] also based on a combination of GNNs and recurrent neural networks (RNN, typically an LSTM), with technical details elaborated in the next section. The referenced architectures use GNNs as a feature extractor and RNNs for sequence learning from the extracted features (node embeddings). As a result, one single GNN model is learned for all graphs on the temporal axis. On the other hand, we propose to use an RNN to update the GNN model (i.e., network parameters) at every time step. This approach effectively performs model adaptation, which focuses on the model itself rather than the node embeddings. Therefore, the referenced approaches require the knowledge of the nodes over the whole time span and can hardly expect the performance on new nodes in the future. In contrast, our approach evolves the GNN based on the dynamism of the graphs. Hence, for future graphs with new nodes without historical information, the evolved GNN is still sensible for them.

Related Work
============

Methods for dynamic graphs are often extensions of those for a static one, with an additional focus on the temporal dimension and update schemes. For example, in matrix factorization-based approaches [@Roweis2000; @Belkin2002], node embeddings come from the (generalized) eigenvectors of the graph Laplacian matrix. Hence, DANE [@Li2017] updates the eigenvectors efficiently based on the prior ones, rather than computing them from scratch for each new graph. The dominant advantage of such methods is the computational efficiency.

For random walk-based approaches [@Perozzi2014; @Grover2016], transition probabilities conditioned on history are modeled as the normalized inner products of the corresponding node embeddings. These approaches maximize the probabilities of the sampled random walks. CTDANE [@Nguyen2018] extends this idea by requiring the walks to obey the temporal order. Another work, NetWalk [@Yu2018a], does not use the probability as the objective function; rather, it observes that if the graph does not undergo substantial changes, one only needs to resample a few walks in the successive time step. Hence, this approach incrementally retrains the model with warm starts, substantially reducing the computational cost.

The wave of deep learning introduces a flourish of unsupervised and supervised approaches for parameterizing the quantities of interest with neural networks. DynGEM [@Goyal2017] is an autoencoding approach that minimizes the reconstruction loss, together with the distance between connected nodes in the embedding space. A feature of DynGEM is that the depth of the architecture is adaptive to the size of the graph; and the autoencoder learned from the past time step is used to initialize the training of the one in the following time.

A popular category of approaches for dynamic graphs is point processes that are continuous in time. Know-Evolve [@Trivedi2017] and DyRep [@Trivedi2018] model the occurrence of an edge as a point process and parameterize the intensity function by using a neural network, taking node embeddings as the input. DynamicTriad [@Zhou2018] uses a point process to model a more complex phenomenon—triadic closure—where a triad with three nodes is developed from an open one (a pair of nodes are not connected) to a closed one (all three pairs are connected). HTNE [@Zuo2018] similarly models the dynamism by using the Hawkes process, with additionally an attention mechanism to determine the influence of historical neighbors on the current neighbors of a node. These methods are advantageous for event time prediction because of the continuous nature of the process.

A set of approaches most relevant to this work is combinations of GNNs and recurrent architectures (e.g., LSTM), whereby the former digest graph information and the latter handle dynamism. The most explored GNNs in this context are of the convolutional style and we call them graph convolutional networks (GCN), following the terminology of the related work, although in other settings GCN specifically refers to the architecture proposed by [@Kipf2017]. GCRN [@Seo2016] offers two combinations. The first one uses a GCN to obtain node embeddings, which are then fed into the LSTM that learns the dynamism. The second one is a modified LSTM that takes node features as input but replaces the fully connected layers therein by graph convolutions. The first idea is similarly explored in WD-GCN/CD-GCN [@Manessia2017] and RgCNN [@Narayan2018]. WD-GCN/CD-GCN modifies the graph convolution layers, most notably by adding a skip connection. In addition to such simple combinations, STGCN [@Yu2018] proposes a complex architecture that consists of so-called ST-Conv blocks. In this model, the node features must be evolving over time, since inside each ST-Conv block, a 1D convolution of the node features is first performed along the temporal dimension, followed by a graph convolution and another 1D convolution. This architecture was demonstrated for spatiotemporal traffic data (hence the names STGCN and ST-Conv), where the spatial information is handled by using graph convolutions.

![image](egcu)

Method
======

In this section we present a novel method, coined *evolving graph convolutional network* (EvolveGCN), that captures the dynamism underlying a graph sequence by using a recurrent model to evolve the graph convolutional network. Throughout we will use subscript $t$ to denote the time index and superscript $l$ to denote the network layer index. Without loss of generality, we assume that all the graphs are built on a common node set of cardinality $n$. A nonexistent node is treated as a dangling node with zero degree, because it does not affect the information flow in graph convolutions. Then, at time step $t$, the input data consists of the pair $(A_t\in{\mathbb{R}}^{n\times n}, X_t\in{\mathbb{R}}^{n\times d})$, where the former is the graph (weighted) adjacency matrix and the latter is the matrix of input node features. Specifically, each row of $X_t$ is a $d$-dimensional feature vector of the corresponding node.

Graph Convolutional Network (GCN) {#sec:gconv}
---------------------------------

A GCN [@Kipf2017] consists of multiple layers of graph convolution, which is similar to a perceptron but additionally has a neighborhood aggregation step motivated by spectral convolution. At time $t$, the $l$-th layer takes the adjacency matrix $A_t$ and the node embedding matrix $H_t^{(l)}$ as input, and uses a weight matrix $W_t^{(l)}$ to update the node embedding matrix to $H_t^{(l+1)}$ as output. Mathematically, we write $$\begin{aligned}
  H_t^{(l+1)} &= \operatorname{GCONV}(A_t, H_t^{(l)}, W_t^{(l)}) \nonumber \\
  &:= \sigma(\widehat{A}_t H_t^{(l)} W_t^{(l)}), \label{eqn:gcn}\end{aligned}$$ where $\widehat{A}_t$ is a normalization of $A_t$ defined as (omitting time index for clarity): $$\widehat{A}=\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}},
\quad \widetilde{A}=A+I,
\quad \widetilde{D}=\operatorname{diag}\Bigg(\sum_j\widetilde{A}_{ij}\Bigg),$$ and $\sigma$ is the activation function (typically ReLU) for all but the output layer. The initial embedding matrix comes from the node features; i.e., $H_t^{(0)}=X_t$. Let there be $L$ layers of graph convolutions. For the output layer, the function $\sigma$ may be considered the identity, in which case $H_t^{(L)}$ contains high-level representations of the graph nodes transformed from the initial features; or it may be the softmax for node classification, in which case $H_t^{(L)}$ consists of prediction probabilities.

One sees that the $\operatorname{GCONV}$ layer is similar to a perceptron (a fully connected layer), except for the multiplication with $\widehat{A}_t$ in the front. This matrix is motivated by spectral graph filtering on the graph Laplacian matrix and it results from a linear functional of the Laplacian. On the other hand, one may also interpret the multiplication with $\widehat{A}_t$ as an aggregation of the transformed embeddings of the neighboring nodes.

The parameters of the GCN are the weight matrices $W_t^{(l)}$, for different time steps $t$ and layers $l$. Graph convolutions occur for a particular time but generate new information (i.e., from $H_t^{(l)}$ to $H_t^{(l+1)}$) along the layers. The relationship between $H_t^{(l)}$, $W_t^{(l)}$, and $H_t^{(l+1)}$ is schematically illustrated in the middle part of Figure \[fig:egcu\].

Weight Evolution {#sec:gru}
----------------

At the heart of the proposed method is the update of the weight matrix $W_t^{(l)}$ at time $t$ based on current, as well as historical, information. This requirement can be naturally fulfilled by an RNN, which treats $W_t^{(l)}$ as the hidden state of the system. We focus on the gated recurrent unit (GRU), although other types of RNN, such as LSTM, are also applicable. They require a particularly named “input” argument, which is the information injected to the recurrent system at every time. This information is the node embeddings $H_t^{(l)}$ in our context.

The mathematics is a bit involved, because different from the standard GRU which maps vectors to vectors, we now have matrices. Moreover, the matrix dimensions do not match on the surface. To proceed, let us begin with the definition of a function $g$ in the following pseudocode format, whereby variables are defined only locally and they do not belong to the system of notations we have been using so far:

$Z_t = \operatorname{sigmoid}(W_ZX_t + U_ZH_{t-1} + B_Z)$ $R_t = \operatorname{sigmoid}(W_RX_t + U_RH_{t-1} + B_R)$ $\widetilde{H}_t = \tanh(W_HX_t + U_H(R_t\circ H_{t-1})+B_H)$ $H_t = (1-Z_t) \circ H_{t-1} + Z_t \circ \widetilde{H}_t$

One recognizes that the function $g$ is nothing but the standard GRU modified from the vector version to the matrix version. The involved matrices have the same number of columns; in other words, one may treat the function $g$ as applying the standard GRU on each column of the involved matrices independently. In this context, $X_t$ is the input, $H_{t-1}$ is the past hidden state, and $H_t$ is the new hidden state. Moreover, $Z_t$, $R_t$, and $\widetilde{H}_t$ are the update gate output, the reset gate output, and the pre-output, respectively. We use these notations to familiarize the reader with the standard formulas of GRU.

As hinted earlier, we want to treat the node embeddings $H_t^{(l)}$ as the GRU input and the weight matrix $W_t^{(l)}$ as the (new) GRU hidden state. However, these matrices have different numbers of columns and they are not readily applicable to the function $g$. To this end, we summarize the embedding matrix $H_t^{(l)}$ into one with only $k$ nodes, where $k$ is the number of columns of $W_t^{(l)}$. Then, the function $g$ is applied.

The following pseudocode gives one popular approach for summarizing a matrix $X_t$ with many rows into a matrix $Z_t$ with only $k$ rows (see, e.g., [@Cangea2018]). Note again that in this pseudocode the variables are defined only locally, even though the same names have been used elsewhere. The summarization requires a parameter vector $p$ that is independent of the time index $t$ (but may vary for different $\operatorname{GCONV}$ layers). This vector is used to compute weights for the rows, among which the ones corresponding to the top $k$ weights are selected and weighted for output.

$y_t = X_tp/\|p\|$ $i_t = \text{top-indices}(y_t, k)$ $Z_t = [X_t \circ \tanh(y_t)]_{i_t}$

With the above functions $g$ and $summarize$, we now are ready to evolve the weight matrices: $$\begin{aligned}
  W_t^{(l)} &= \operatorname{GRU}(H_t^{(l)}, W_{t-1}^{(l)}) \\
  &:= g(summarize(H_t^{(l)}, \#col(W_{t-1}^{(l)}))^T, W_{t-1}^{(l)}),\end{aligned}$$ where $\#col$ denotes the number of columns of a matrix and the superscript $T$ denotes matrix transpose. We reuse the name “GRU” to denote this evolution function. Effectively, it summarizes the node embedding matrix $H_t^{(l)}$ into one with appropriate dimensions and then evolves the weight matrix $W_{t-1}^{(l)}$ in the past time step to $W_t^{(l)}$ for the current time. As opposed to the $\operatorname{GCONV}$ layer which occurs for one particular time step but progresses along the layers, the $\operatorname{GRU}$ occurs for one particular layer but progresses along time.

The relationship between $W_{t-1}^{(l)}$, $H_t^{(l)}$, and $W_t^{(l)}$ is schematically illustrated in the left part of Figure \[fig:egcu\].

Evolving Graph Convolution Unit (EGCU) and Network (EvolveGCN)
--------------------------------------------------------------

Combining $\operatorname{GCONV}$ presented in Section \[sec:gconv\] and $\operatorname{GRU}$ in Section \[sec:gru\], we reach the *evolving graph convolution unit* (EGCU), defined by the following pseudocode:

$W_t^{(l)} = \operatorname{GRU}(H_t^{(l)}, W_{t-1}^{(l)})$ $H_t^{(l+1)} = \operatorname{GCONV}(A_t, H_t^{(l)}, W_t^{(l)})$

Different from the two pseudocodes presented in the preceding subsection, here we do not have notational clash with conventions. For readability, the variables therein need not be considered local. This unit performs graph convolutions along layers and meanwhile evolves the weight matrices over time. It is illustrated in the right part of Figure \[fig:egcu\].

Chaining the units bottom-up, we obtain a GCN with multiple layers for one time step. Then, unrolling over time horizontally, the units form a lattice on which information ($H_t^{(l)}$ and $W_t^{(l)}$) flows. We call the overall model *evolving graph convolutional network* (EvolveGCN).

Task-Specific Training {#sec:training}
----------------------

So far, we have presented the proposed EvolveGCN model from the angle of representation learning, but the real power comes from pairing it with the prediction model for a downstream task and training them together end-to-end. We consider three example tasks here: node classification, edge classification, and link prediction.

For an EvolveGCN with $L$ layers, the output node embeddings are contained in the matrix $H_t^{(L)}$. For notational clarity, in what follows we omit the superscript $L$ and write the output embedding of a node $u$ at time $t$ as $h_t^u$, which is a column vector.

#### Node Classification

Predicting the label of a node $u$ at time $t$ follows the same practice of a standard GCN. One may assume that the node label may change over time so that the problem is more interesting. We let the activation function $\sigma$ of the output $\operatorname{GCONV}$ layer (see  with $l=L-1$) be the softmax, so that $h_t^u$ is a probability vector. Then, with the ground-truth one-hot label vector $y_t^u$, the training loss is the weighted cross entropy $$L=-\sum_t\sum_u \alpha_u \sum_i (y_t^u)_i \log (h_t^u)_i,$$ where nonuniform weights $\alpha_u$ (treated as hyperparameters) sometimes help mitigate class imbalance problems.

#### Edge Classification

Predicting the label of an edge $(u,v)$ at time $t$ requires the embeddings of both nodes. We let the activation function of the output $\operatorname{GCONV}$ layer be ReLU, so that $h_t^u$ and $h_t^v$ are interpreted as node embeddings. Then, we introduce an additional parameter matrix $U$, which is independent of time, to form the predictive model $$p_t^{uv}=\operatorname{softmax}(U[h_t^u; h_t^v]).$$ Then, with the ground-truth one-hot label vector $y_t^{uv}$, the training loss is the weighted cross entropy $$L=-\sum_t\sum_{(u,v)} \alpha_{uv} \sum_i (y_t^{uv})_i \log (p_t^{uv})_i,$$ where nonuniform weights $\alpha_{uv}$ sometimes help mitigate class imbalance problems.

#### Link Prediction

The task of link prediction is to leverage information up to time $t$ and predict the existence of an edge $(u,v)$ at time $t+1$. Since historical information has been encoded in the GCN parameters, we base the prediction on $h_t^u$ and $h_t^v$. In order to make them embedding vectors, similar to edge classification, we let the activation function of the output $\operatorname{GCONV}$ layer be ReLU. Then, we introduce a column vector $q$, which is independent of time, to form the predictive model $$p_{t+1}^{uv}=\operatorname{sigmoid}(q^T[h_t^u; h_t^v]),$$ whose output $p_{t+1}^{uv}$ indicates the probability that the edge $(u,v)$ exists at time $t+1$.

The training is not scalable if we use all existent and nonexistent edges, because the number of node pairs scales quadratically with the number of nodes. Typically, existent edges are substantially fewer than nonexistent ones, possibly differing in count by orders of magnitude. Hence, we appeal to negative sampling. To this end, let $P_t$ and $\overline{P}_t$ be the collection of existent and nonexistent edges at time $t$, respectively. For some sampling ratio $\beta$, we sample $\beta|P_t|$ nonexistent edges from $\overline{P}_t$ and form a set $Q_t$. Additionally, we let $y_{t+1}^{uv}$ be the binary label and $C_{t+1}^{uv}$ be the sample cross entropy: $$C_{t+1}^{uv} = -y_{t+1}^{uv}\log p_{t+1}^{uv} -(1-y_{t+1}^{uv})\log (1-p_{t+1}^{uv}).$$ Then, the training loss is $$L=\sum_t\sum_{(u,v)\in P_t} C_{t+1}^{uv}
+\alpha\sum_t\frac{|\overline{P}_t|}{|Q_t|}\sum_{(u,v)\in Q_t} C_{t+1}^{uv},$$ where $\alpha$ is a tunable weighting factor.

Experiments
===========

In this section, we present a comprehensive set of experiments to demonstrate the effectiveness of EvolveGCN. In particular, we experiment with several combinations of data sets and tasks. In addition to existing benchmark data sets, we also work on one generated from a financial fraud simulator. Table \[tab:dataset\] summarizes the information of each data set. Details and processing are presented in individual subsections. Hyperparameters are tuned by using the validation set and test results are reported at the best validation epoch.

  --------------- ---------- ---------- ----------------------
                   \# Nodes   \# Edges      \# Time Steps
                                         (Train / Val / Test)
    Bitcoin-OTC     5,881      35,592        96 / 21 / 21
   Bitcoin-Alpha    3,783      24,186        96 / 20 / 20
      AMLSim        20,000    117,805       104 / 22 / 23
  --------------- ---------- ---------- ----------------------

  : Data sets.[]{data-label="tab:dataset"}

Baseline Methods
----------------

We compare EvolveGCN with two baselines.

#### GCN

The first one is GCN without any temporal modeling. We use one single GCN model for all time steps and the loss is accumulated along the time axis.

#### GCN-GRU

The second one is also a single GCN model, but it is co-trained with a recurrent model (GRU) that takes node embeddings as input. We call this approach GCN-GRU, which is conceptually the same as Method 1 of [@Seo2016], except that their GNN is the ChebNet [@Defferrard2016] and their recurrent model is the LSTM.

Data Set: Bitcoin-OTC
---------------------

Bitcoin-OTC[^3] is a who-trusts-whom network of bitcoin users trading on the platform <http://www.bitcoin-otc.com>. Since bitcoin users are anonymous, there emerge ratings of reputation among users for the purpose of reducing transaction risks and avoiding fraud. Members of this network rate the level of trust they have on the other ones in a scale from $-10$ (distrust) to $+10$ (trust).

In this data set, the time of rating spans approximately five years and we use a granularity of approximately two weeks to form a sequence of graphs with 138 time steps. One may easily calculate, according to Table \[tab:dataset\], that on average each graph has only 258 edges (compared this number with the number of nodes, 5,881) and thus is overly sparse, if each edge appears only once in the sequence. The over-sparsity may adversarially affect the usefulness of any node embedding technique assuming graph connectivity. Hence, we maintain a window of size $T$ for the existence of an edge in the graph sequence, since its initial creation. Through extensive experimentation, we find that setting $T=10$ results in good performance for at least the baseline GCN. We use in/out node degree (two-hot) as input features.

#### Edge Classification

We predict the polarity of each rating (binary classification). The hypothesis is that the rating given by a user to another one is based on life knowledge that accumulates over time (e.g., knowledge of existing ratings and identified fraudulent accounts). Hence, the dynamism of the network is a helpful signal for trustfulness prediction, at which a model that captures temporal evolution may excel.

We summarize the performance of EvolveGCN and those of the baselines in Table \[tab:performance\]. The classes are relatively skewed: $89\%$ of the ratings are positive. Because negative ratings (the minority class) are more important (as they reveal distrust and transaction risks), we make the minority class as the positive class and report precision/recall/F1 that focuses on this class. One sees that EvolveGCN achieves the highest recall and F1 score, which means that negative ratings are much more likely to be captured in predictions, promoting safer trading. For completeness, we also include the micro-average F1 score. If we dilute the focus on negative ratings to all ratings, EvolveGCN performs less competatively.

Figure \[fig:otc.f1.over.time\] shows the F1 score over time for the test set.

![F1 score over time, Bitcoin-OTC, edge classification.[]{data-label="fig:otc.f1.over.time"}](image2.png){width=".7\linewidth"}

#### Link Prediction

The task of link prediction is to forecast whether a bitcoin user will rate another one in the next time step. Link prediction shares similarities with a general binary classification, but a distinct characteristic is that the negative class (nonexistent edges) typically dominates the other class. For training, we have discussed in Section \[sec:training\] that negative sampling is necessary in the formulation of the loss function. Similarly, for testing, we also sample a substantial amount of nonexistent edges. The negative sampling ratio for training is $\beta=20$ and that for testing is $\beta=100$.

The results are reported in Table \[tab:performance\]. Naturally, the class imbalance problem is substantially more severe here than that of rating prediction. However, EvolveGCN achieves the best F1 and micro F1 scores simultaneous.

Data Set: Bitcoin-Alpha
-----------------------

The data set Bitcoin-Alpha[^4] is created in the same manner as is Bitcoin-OTC, except that the users and ratings come from a different trading platform, <http://www.btc-alpha.com>. The positive rating ratio is $93\%$. We follow the same experimentation setting as in Bitcoin-OTC and report the results in Table \[tab:performance\]. In both edge classification and link prediction tasks, EvolveGCN achieves the best F1 and micro F1 scores.

[ccccc]{}\
& Precision & Recall & F1 & Micro F1\
GCN & 0.278 & 0.437 & 0.340 & 0.863\
GCN-GRU & 0.301 & 0.437 & 0.357 & 0.872\
EvolveGCN & 0.287 & 0.618 & 0.392 & 0.845\

[ccccc]{}\
& Precision & Recall & F1 & Micro F1\
GCN & 0.341 & 0.394 & 0.365 & 0.9989\
GCN-GRU & 0.310 & 0.318 & 0.314 & 0.9989\
EvolveGCN & 0.487 & 0.369 & 0.420 & 0.9992\

[ccccc]{}\
& Precision & Recall & F1 & Micro F1\
GCN & 0.159 & 0.646 & 0.255 & 0.609\
GCN-GRU & 0.163 & 0.664 & 0.262 & 0.613\
EvolveGCN & 0.168 & 0.611 & 0.263 & 0.646\

[ccccc]{}\
& Precision & Recall & F1 & Micro F1\
GCN & 0.541 & 0.347 & 0.423 & 0.9991\
GCN-GRU & 0.316 & 0.422 & 0.361 & 0.9986\
EvolveGCN & 0.520 & 0.358 & 0.424 & 0.9991\

[ccccc]{}\
& Precision & Recall & F1 & Micro F1\
GCN & 0.068 & 0.263 & 0.108 & 0.959\
GCN-GRU & 0.203 & 0.291 & 0.239 & 0.982\
EvolveGCN & 0.081 & 0.234 & 0.121 & 0.968\

Data Set: AMLSim
----------------

Money laundering is one of the most important crime problems in the finance domain. Since banking transaction data is highly sensitive and rarely publicly available, we have developed a multi-agent simulator called AMLSim (anti-money laundering simulator)[^5], aiming at simulating banking transaction behaviors that include typical money laundering activities. With AMLSim, we generate a benchmark transaction data set[^6].

The data set consists of a temporal graph sequence. A node represents a bank account and an edge represents a time-stamped transaction between two accounts. The data set also comes with node labels that indicate which accounts are suspicious and since when. Basic statistics of the graph sequence is given in Table \[tab:dataset\]. Among the 20,000 accounts, 493 of them are labeled as suspicious.

The task is node classification: predict at a time whether an account becomes suspicious. As one sees, the class distribution is also highly skewed. We report the results in Table \[tab:performance\]. EvolveGCN outperforms GCN but is less competative than GCN-GRU. One possible cause is that suspicious nodes become so only after a few time steps and hence the lack of historical information for a new node is less problematic. Nevertheless, the fact that GCN results in the worst performance signifies the importance of temporal modeling.

Conclusions and Future Work
===========================

A plethora of neural network architectures were proposed recently for graph structured data and their effectiveness have been widely confirmed. In practical scenarios, however, we are often faced with graphs that are constantly evolving, rather than being conveniently static for a once-for-all investigation. The question is how neural networks handle such a dynamism. Combining GNN with RNN is a natural idea. We are not the first to explore this route. Typical approaches use the GNN as a feature extractor and use an RNN to capture the dynamism of the node embeddings. We, on the other hand, use the RNN to evolve the GNN, so that the dynamism is captured in the evolving network parameters. Our method is a model adaptation approach. One advantage is that it handles more flexibly dynamic data, because a node does not need to be present all time around. Experimental results confirm that the proposed approach generally outperforms related ones for a variety of tasks, including node classification, edge classification, and link prediction.

One of the pressing needs is to scale the method to industrial-level graphs, such as transaction graphs that may contain millions or even billions of accounts and transactions. The graph model and the recurrent model have their own limitations regarding scalability. The graph model, particularly in the convolutional style, suffers repeated expansion of the neighborhood. Much of existing work tackles this problem through restricting the neighborhood size (see, e.g., [@Hamilton2017; @Chen2018]). On the other hand, the recurrent model is notoriously sequential and hence good parallelism is difficult to achieve. Emergent architectures using the attention mechanism (see, e.g., [@Vaswani2017]) appear to be a successful remedy.

Another avenue of future research is to tackle the class imbalance problem, which appears common in practical scenarios. For example, in financial activities, frauds are rare compared with normal operations. Prediction of the minority class is like finding a needle in a haystack, wherein outlier prediction approaches appear to be more natural than a classification approach. How one applies the proposed neural network architecture in an outlier prediction framework is the next step of our investigation.

[^1]: Equal contribution

[^2]: Contact author

[^3]: <http://snap.stanford.edu/data/soc-sign-bitcoin-otc.html>

[^4]: <http://snap.stanford.edu/data/soc-sign-bitcoin-alpha.html>

[^5]: <https://github.com/IBM/AMLSim>

[^6]: <https://github.com/IBM/AMLSim/tree/master/sample/20K_cycle200.tgz>
