Decoupled Graph Neural Networks for Large Dynamic Graphs
Real-world graphs, such as social networks, financial transactions, and
recommendation systems, often demonstrate dynamic behavior. This phenomenon,
known as graph stream, involves the dynamic changes of nodes and the emergence
and disappearance of edges. To effectively capture both the structural and
temporal aspects of these dynamic graphs, dynamic graph neural networks have
been developed. However, existing methods are usually tailored to process
either continuous-time or discrete-time dynamic graphs, and cannot be
generalized from one to the other. In this paper, we propose a decoupled graph
neural network for large dynamic graphs, including a unified dynamic
propagation that supports efficient computation for both continuous and
discrete dynamic graphs. Since graph structure-related computations are only
performed during the propagation process, the prediction process for the
downstream task can be trained separately without expensive graph computations,
and therefore any sequence model can be plugged-in and used. As a result, our
algorithm achieves exceptional scalability and expressiveness. We evaluate our
algorithm on seven real-world datasets of both continuous-time and
discrete-time dynamic graphs. The experimental results demonstrate that our
algorithm achieves state-of-the-art performance in both kinds of dynamic
graphs. Most notably, the scalability of our algorithm is well illustrated by
its successful application to large graphs with up to over a billion temporal
edges and over a hundred million nodes.
Yanping Zheng, Zhewei Wei, Jiajun Liu
# Decoupled Graph Neural Networks for Large Dynamic Graphs

###### Abstract.

Real-world graphs, such as social networks, financial transactions, and recommendation systems, often demonstrate dynamic behavior. This phenomenon, known as graph stream, involves the dynamic changes of nodes and the emergence and disappearance of edges. To effectively capture both the structural and temporal aspects of these dynamic graphs, dynamic graph neural networks have been developed. However, existing methods are usually tailored to process either continuous-time or discrete-time dynamic graphs, and cannot be generalized from one to the other. In this paper, we propose a decoupled graph neural network for large dynamic graphs, including a unified dynamic propagation that supports efficient computation for both continuous and discrete dynamic graphs. Since graph structure-related computations are only performed during the propagation process, the prediction process for the downstream task can be trained separately without expensive graph computations, and therefore any sequence model can be plugged-in and used. As a result, our algorithm achieves exceptional scalability and expressiveness. We evaluate our algorithm on seven real-world datasets of both continuous-time and discrete-time dynamic graphs. The experimental results demonstrate that our algorithm achieves state-of-the-art performance in both kinds of dynamic graphs. Most notably, the scalability of our algorithm is well illustrated by its successful application to large graphs with up to over a billion temporal edges and over a hundred million nodes.

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †: journal:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:
+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:
+
Footnote †:

+
Footnote †:

+
Footnote †:
+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:
+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
FootnoteFootnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
Footnote †:

+
FootnoteFootnote †:

+
Footnote †:

+
Footnote †:
+
Footnote †:
+
Footnote †:

+
Footnote †:

+
FootnoteFootnote †:

+
Footnote †:

+
FootnoteFootnote †:

+
Footnote †:

+
FootnoteFootnote †:

+
Footnote †:

+
FootnoteFootnote †:

+
FootnoteFootnote †:

+
FootnoteFootnote †:

+
Footnote †:

+
Footnote
generic propagation methods for both continuous-time and discrete-time dynamic graphs.

We observe that CTDG methods, such as TGN (TGN et al., 2017), keep track of nodes affected by each graph event and adjust their embeddings, avoiding relearning the embeddings of all nodes and conserving computing resources. Since each snapshot is treated as a static graph in DTDG methods, edge deletion and the simultaneous occurrence of multiple graph events are naturally handled. Our objective is to develop a novel dynamic graph neural network that combines the strengths of both CTDG and DTDG methods. To achieve this, we introduce incremental node embedding update strategies specifically designed for handling batch graph events. This allows our model to process batch events similar to DTDG methods, while also keeping track of embedding changes akin to CTDG methods. Notably, our update strategy is not limited to adding new edges but also works seamlessly for removing edges. The main contributions can be summarized as follows:

* We propose a decoupled graph neural network for large dynamic graphs, which decouples the temporal propagation and prediction processes on dynamic graphs, enabling us to achieve great scalability and generate effective representation.
* We support the processing of continuous-time and discrete-time dynamic graphs by designing the generalized dynamic feature propagation. On the other hand, the model can fit various high-pass or low-pass graph filters to obtain a comprehensive temporal representation, by configuring various propagation formulas.
* Extensive experiments on seven benchmark datasets demonstrate the effectiveness of our method. Experimental results show that our model outperforms existing state-of-the-art methods. In addition, we evaluate our method on two large-scale graphs to show its excellent scalability.

## 2. Notations and Preliminary

In this section, we first introduce the necessary notations. Then we provide a concise overview of the classification of dynamic graphs and the common learning tasks associated with them.

**Notations.** A static graph is denoted as \(G=(V,E)\), where \(V\) is the set of \(n\) nodes, and \(E\) represents the set of \(m\) edges. Let \(\mathbf{A}\in\mathbb{R}^{n\times n}\) represent the adjacency matrix of \(G\), with entry \(\mathbf{A}(i,j)=w_{(i,j)}>0\) being the weight of the edge between node \(i\) and \(j\), and \(\mathbf{A}(i,j)=w_{(i,j)}=0\) indicates non-adjacency. The degree matrix \(\mathbf{D}\in\mathbb{R}^{n\times n}\) is a diagonal matrix defined by \(\mathbf{D}(i,i)=d(i)=\sum_{j\in V}w_{(i,j)}\). Each node \(i\in V\) has a \(d\)-dimensional features vector \(\mathbf{x}_{i}\), and all feature vectors form the feature matrix \(\mathbf{X}\in\mathbb{R}^{n\times d}\).

**Dynamic Graphs.** Dynamic Graphs can be summarized into two categories, CTDGs and DTDGs, depending on whether the entire timestamp is saved (Grover and Leskovec, 2015). A CTDG is composed of an initial graph and a sequence of events, denoted as \((G,S)\), where \(G\) is the initial state of the dynamic graph at time \(t_{0}\) and \(S\) is a set of observed events on the graph. Each event consists of a triplet of _(event type, event, timestamp)_, where the _event type_ can be edge additions, edge deletions, node additions, node deletions, node feature modifications, and so on. Therefore, \(G_{t}\) is the new graph generated from the initial graph \(G\) by sequentially completing the graph events of \(\{t_{1}\sim t\}\). Figure 1(a) shows an example of updating from an empty graph with only five nodes to the graph \(G_{5}\) at time \(t_{5}\), where the graph events involved are:

\[S=\{ (AddEdge,(v_{1},v_{5}),t_{1}),(AddEdge,(v_{2},v_{4}),t_{1}),\] \[(AddEdge,(v_{1},a_{4}),t_{2}),(AddEdge,(v_{3},v_{4}),t_{2}),\] \[(AddEdge,(v_{3},v_{5}),t_{3}),(DeleteEdge,(v_{3},v_{4}),t_{4}),\] \[(AddEdge,(v_{1},v_{3}),t_{5})\}\;.\]

A DTDG is represented as a sequence of snapshots, \(\{G_{0},\ldots,G_{T}\}\), which are sampled at regular time intervals. Figure 1(b) illustrates that the second snapshot, \(G_{1}\), of the DTDG can be considered as the graph snapshot captured by the CTDG in Figure 1(a) at time \(t_{5}\). However, it is important to note that the events occurring between \(t_{1}\) and \(t_{5}\) and their respective order are disregarded. Consequently, the DTDG fails to recognize the existence of the previous edge \((v_{3},v_{4})\) in the graph.

**Graph Learning Tasks.** Node classification and link prediction are traditional learning tasks for static graphs. We assume that each node is tagged with a label \(\mathrm{Y}(i)\) from the label matrix \(\mathbf{Y}\), but only the labels on a subset \(V^{\prime}\subset V\) are known. The objective of the node classification problem is to infer the unknown labels on \(V\setminus V^{\prime}\). In community detection, for instance, the label assigned to each node represents the community to which it belongs. Link prediction is the classical task of graph learning. It predicts whether an edge exists between two nodes that were not initially connected, inferring missing edges in \(E\). In social networks, link prediction is also known as the friend recommendation task, predicting whether a user is interested in another.

Similarly, there are node-level and edge-level prediction tasks for dynamic graphs. Based on the historical information observed so far, we are able to accomplish dynamic node classification and future link prediction defined as follows.

Definition 1 (Dynamic Node Classification).: _For a given graph \(G_{t}=(V_{t},E_{t})\) and the incomplete label matrix \(\mathbf{Y}_{t}^{\prime}\), where \(G_{t}\) can be regarded as the graph at timestamp \(t\) in a CTDG or the \(t\)-th snapshot in a DTDG, and \(\mathbf{Y}_{t}^{\prime}\) associates a subset \(V_{t}^{\prime}\subset V_{t}\) with known class labels at timestamp/snapshot \(t\), dynamic node classification is to classify the remaining nodes with unknown labels and estimate the label matrix \(\mathbf{Y}_{t}\)._

Definition 2 (Future Link Prediction).: _For a given timestamp/snapshot \(t\) and two nodes \(i,j\in V_{t}\), future link prediction aims to predict whether edge \((i,j)\) will be generated in the next timestamp/snapshot or not, based on observations learned from all nodes and their links before timestamp \(t\), i.e. observations of \(\{G_{0},\ldots,G_{t}\}\)._

Figure 1. Two types of dynamic graphs.
Related Works

The Encoder-Decoder framework is a commonly used model in machine learning, which has been applied to various tasks such as unsupervised auto-encoder (He et al., 2017) and neural network machine translation models (Wang et al., 2017). Recently, researchers have demonstrated that the Encoder-Decoder framework can generalize most high-performing dynamic graph learning algorithms (Han et al., 2017; Wang et al., 2017).

### CTDGs Learning Methods

It is important to capture the changes in node embedding caused by every graph event when learning CTDGs. Most methods follow the training strategy that the encoder receives a sequence of graph events as input and reflects their influence in node embeddings. The decoder can therefore be a sequence learning model or a static network such as Multilayer Perceptron (MLP) or Support Vector Machine (SVM).

CTDNE (Krizhevsky et al., 2012) uses the temporal random walk as an encoder and designs three strategies for selecting the next-hop node in dynamic graphs. The introduction of temporal information reduces the uncertainty of embedding, resulting in better performance. The temporal point process is utilized by DyREP (Krizhevsky et al., 2012) to capture temporal changes at the node and graph levels. DyREP (Krizhevsky et al., 2012) builds embeddings of target nodes by aggregating information from neighboring nodes, where neighbors are limited by biasing the hop count selection of the temporal point process. These methods inherit the deficiencies of conventional graph representation learning methods, such as their inability to include node properties.

More prevalent CTDG learning encoders are based on Recurrent Neural Networks (RNNs), where the RNN generates memories from observed events associated with the target node via a memory function. The representative model TGN (Krizhevsky et al., 2012) comprises a memory component and an embedding component, where the memory component stores the historical memory of the given node. JODIE (Krizhevsky et al., 2012), DyREP (Krizhevsky et al., 2012), and TGAT (Wang et al., 2017) can be viewed as variants of TGN (Krizhevsky et al., 2012), and they differ in how they update embeddings and memories. Utilizing an asynchronous mail propagator, APAN (Krizhevsky et al., 2012) enforces that graph events are submitted to the model in timestamped order. Wang et al. (Wang et al., 2017) builds node representations using Causal Anonymous Walks (CAWs), which anonymize the node information on sampled temporal causal routes and apply attention learning to the sampled motifs. The resulting motifs are fed to RNNs to encode each walk as a representation vector. Subsequently, the representations of multiple walks are aggregated into a single vector using a self-attention process for downstream tasks.

Generally, methods specific to CTDGs efficiently learn node embeddings by tracking the impacted nodes for each graph event and updating their embeddings accordingly. However, these methods typically focus on considering the immediate neighbors linked with a graph event, such as the endpoints of an inserted edge, and few consider the impact on second-order neighbors (Beng et al., 2015). Furthermore, the effect on higher-order neighbors or the overall graph is rarely evaluated, and there is limited discussion regarding edge deletions and simultaneous arrivals of multiple events.

### DTDGs Learning Methods

In the DTDGs learning process, temporal patterns are measured by the sequential relationships between snapshots. Some works apply Kalman filtering (Krizhevsky et al., 2012; Krizhevsky et al., 2012) or stacked spatial-temporal graph convolution networks (STGCN) (Krizhevsky et al., 2012) to create dynamic graph embeddings, and then use simple MLPs as decoders to perform the prediction task. More commonly, static methods, such as GAE and VGAE (Vaswani et al., 2017), are used to generate node embeddings of each snapshot. The embeddings are then sorted by time and treated as sequential data, and a sequential decoder is applied to extract the temporal patterns from them.

To obtain embeddings of each snapshot, GraRep (Beng et al., 2015), HOPE (Krizhevsky et al., 2012), and M-NMF (Krizhevsky et al., 2012) construct encoders using matrix decomposition, while DeepWalk (Krizhevsky et al., 2012) and node2vec (Chen et al., 2015) transform the graph structure into node-level embeddings using random walk. These algorithms, however, are shallow embedding methods, meaning that they do not consider the attribute information of the graph. Also, there is no parameter sharing between nodes, which makes these methods computationally inefficient. Graph neural networks are efficient ways for learning both the structure and attribute information of a graph. GNNs follow the message-passing framework, in which each node generates embeddings by aggregating information of neighbors (Chen et al., 2015). To improve the efficiency, Graph Convolutional Network (GCN) (Huang et al., 2016) derives the layer-by-layer propagation formula from the first-order approximation of the localized spectral filters on the graph:

\[\mathbf{H}^{(\ell+1)}=\sigma\left(\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D }^{-\frac{1}{2}}\mathbf{H}^{(\ell)}\mathbf{W}^{(\ell)}\right) \tag{1}\]

where \(\mathbf{A}\) and \(\mathbf{D}\) are the adjacency matrix and degree matrix, respectively. \(\mathbf{W}^{(\ell)}\) is the learnable parameter of layer \(\ell\), and \(\sigma\) is a nonlinear activation function such as ReLU. \(\mathbf{H}^{(\ell)}\) is the learnt node representation at the \(\ell\)-th layer, and \(\mathbf{H}^{(0)}=\mathbf{X}\). AddGraph (Krizhevsky et al., 2012) employs GCN as the encoder to analyze the structural information of each snapshot, while a sequence decoder is used to determine the relationships between snapshots. Graph Attention Network (GAT) (Chen et al., 2015) is an attention mechanism based on GCN that assigns various weights to the features of neighbors via weighted summation. DyGAT (Deng et al., 2015) employs GAT as an encoder for DTDGs learning, and node embeddings are generated by jointly computing self-attentions of neighborhood structure and time dimensions.

Long Short-Term Memory (LSTM) (Hochreiter and Schmidhuber, 2015) is a widely used sequence model, known for its ability to effectively capture long-term temporal dependencies and correlations. Therefore, Seo et al. (Seo et al., 2017) and Manessi et al. (Mansi et al., 2018) use LSTM as decoders, and their encoders are GCNs or their different versions. The combination structure of GNNs and LSTMs has demonstrated its efficacy in object detection (Krizhevsky et al., 2012) and pandemic forecasting (Krizhevsky et al., 2012) areas. EvolveGCN (Huang et al., 2016) uses LSTM and Gate Recurrent Unit (GRU) to update the GCN's parameters at each snapshot since it focuses on the evolution of the GCN's parameters rather than the node representation at each snapshot. These DTDG-specific methods typically treat each snapshot as a static graph, making it easy for them to address edge deletion and many simultaneous edges. However, they are unable to track the particular impact of each graph event on node embedding, and the recomputation of each snapshot is computationally expensive.

## 4. Decoupled Graph Neural Network

**Overview**. As previously indicated, we aim to design a decoupled GNN with high scalability for dynamic graphs. In addition, we
also require the model to operate multi-event arrivals simultaneously and support edge deletion while keeping tracking changes in node embedding, which incorporates the benefits of the CTDGs-specific and DTDGs-specific models. Therefore, inspired by the scalable static GNN framework (Beng et al., 2017; Wang et al., 2018), we develop a decoupled GNN for large dynamic graphs, in which the dynamic propagation of the graph is decoupled from the prediction process. To enable efficient computation on large-scale dynamic graphs, we employ dynamic propagation with strict error guarantees (as described in Section 4.1). This approach eliminates learning parameters in the propagation process, facilitating independent graph propagation for generating temporal representations of all nodes. The prediction process focuses on learning the underlying graph dynamics from the representations of nodes, which does not contain expensive graph computations, enabling the use of arbitrary learning models, as described in Section 4.2.

**Scalable GNNs.** In order to improve the scalability of GNN models, a line of research tries to decouple the propagation and prediction of conventional GNN layers. The idea behind them is to apply MLPs to batches of nodes simply without taking the graph structure into account, which is proposed by SGC (Wang et al., 2018) first. For implementation, the representation matrix \(\mathbf{Z}\) is generated first following this general formulation propagation:

\[\mathbf{Z}=\sum_{k=0}^{\infty}\gamma_{k}(\mathbf{D}^{-a}\mathbf{A}\mathbf{D}^{ -b})^{k}\mathbf{X}\,, \tag{2}\]

where \(\mathbf{X}\) denotes the input feature matrix, \(a\) and \(b\) are convolution coefficient, \(\gamma_{k}(k=0,1,2,\dots)\) is the weight of the \(k\)-th step convolution. When \(a=b=\frac{1}{2}\) and \(\gamma_{k}=1\), Equation 2 can be considered a GCN with an infinite number of layers, i.e., a stack of infinite layers of Equation 1. However, the parameters of each layer are discarded for better scalability. Therefore, MLPs take the representation matrix \(\mathbf{Z}\) as input and trains for downstream tasks. Mini-batch training can be easily accomplished since node representations can be viewed as distinct input samples for the neural network. Numerous models, including APPNP (Grover et al., 2017), SGC (Wang et al., 2018), and GBP (Chen et al., 2018), can be regarded as versions of Equation 2 constructed by choosing different values for \(a\), \(b\), and \(\gamma_{k}\). By varying \(\gamma_{k}\), Equation 2 can approximate any form of graph filter. For instance, Equation 2 corresponds to a low-pass graph filter when all \(\gamma_{k}(k=0,1,2,\dots)\) satisfy \(\gamma_{k}\geq 0\), and Equation 2 relates to a high-pass filter when \(\gamma_{k}\) is of the form \((-\alpha)^{k}\) with \(\alpha\in(0,1)\). For simplicity, we assume that \(a=\beta\), \(b=1-\beta\), and the sequence of \(\gamma_{k}\) is a geometric progression with a common ratio \(\gamma=\frac{\gamma_{k+1}}{\gamma_{k}}\) and \(0<|\gamma|<1\) in this paper.

We aim to extend the previous concept to dynamic graphs. Firstly, we derive temporal representations for all nodes in the graph based on dynamic approximate propagation, which can be efficiently pre-computed. Next, we batch the structurally enhanced temporal representations of nodes and feed them into the learning model. This decoupling framework, derived from scalable static GNNs, permits the use of any sequence model while preserving high scalability.

**Approximate propagation.** The summation in Equation 2 goes to infinity, which makes it computationally infeasible. Following PPRGo (Beng et al., 2017) and AGP (Shen et al., 2017), we consider its approximate version. By representing each dimension of the feature matrix as an \(n\)-dimensional vector \(\mathbf{x}\), the feature matrix can be turned into a sequence of \(\{\mathbf{x}_{0},...,\mathbf{x}_{d-1}\}\), where the propagation of each vector is conducted independently. Equation 2 can therefore be expressed in a equivalent vector form: \(\mathbf{\pi}=\sum_{k=0}^{\infty}\gamma_{k}(\mathbf{D}^{-\beta}\mathbf{A}\mathbf{D }^{\beta-1})^{k}\mathbf{x}\). As illustrated in Algorithm 1, we generalize the propagation algorithm (Shen et al., 2017) to a weighted version to support weighted graph neural networks and relax the requirement for positive weight coefficients. We denote the approximate solution as \(\hat{\mathbf{\pi}}\), and the cumulative error of all steps is denoted as \(\mathbf{r}\). For initialization, we set \(\hat{\mathbf{\pi}}=0\) and \(\mathbf{r}=\mathbf{x}\). The propagation starts from the node whose residual exceeds the error tolerance \(r_{max}\). Then, the node distributes an equal portion of its residual to its neighboring nodes, and the remainder is transformed into its estimate to record the amount of information already propagated by that node. The feature propagation concludes when the residuals of all graph nodes satisfy the error bound.

```
Input:Graph \(G\), weight coefficients \(\gamma_{k}\), convolutional coefficients \(\beta\), threshold \(r_{max}\), initialized \((\hat{\mathbf{\pi}},\mathbf{r})\)
1whileexist \(i\in V\) with \(|\mathbf{r}(i)|>r_{max}\cdot d(i)^{1-\beta}\)do
2\(\hat{\mathbf{\pi}}(i)\leftarrow\hat{\mathbf{\pi}}(i)+\gamma_{0}\cdot\mathbf{r}(i)\);
3foreach\(j\in N(i)\)do
4\(\mathbf{r}(j)\leftarrow\mathbf{r}(j)+\frac{\gamma_{i}\cdot\gamma_{i(k,j)}\cdot\mathbf{r}(j )}{d(i)^{1-\beta}d(j)^{\beta}}\) ;
5\(\mathbf{r}(i)\gets 0\);
6 return \((\hat{\mathbf{\pi}},\mathbf{r})\);
```

**Algorithm 1**GeneralPropagation

The neural network model receives the structurally improved feature matrix \(\hat{\mathbf{Z}}=(\hat{\mathbf{\pi}}_{0},...,\hat{\mathbf{\pi}}_{d-1})\) as input and is trained to get the final representation of the nodes based on the subsequent task. For instance, the multi-label node classification task typically uses \(\mathbf{Y}=softmax(MLP(\hat{\mathbf{Z}}))\). By decoupling propagation and prediction, the model training complexity is independent of the graph topology, which enhances training efficiency and enables the use of sophisticated prediction networks simultaneously.

### Dynamic Propagation

We consider a dynamic graph \(\mathcal{G}=\{G_{0},G_{1},...,G_{T}\}\), where each \(G_{t}(t\in[0,T])\) is the graph derived from the initial graph in a CTDG after finishing the graph events before timestamp \(t\), or the \(t\)-th snapshot in a DTDG. That is, \(G_{t}\) refers to the \(t\)-th observed status of the dynamic graph. We are not concerned with how \(G_{t}\) is obtained, i.e. how the dynamic graph \(\mathcal{G}\) is stored. The overall update procedure is summarized in Algorithm 2. We obtain the feature propagation matrix for each \(G_{t}\), and \(\mathcal{I}_{t}\) is derived iteratively from \(\mathcal{I}_{t-1}\), as in lines 9-19. The estimated vector \(\hat{\mathbf{\pi}}\) and residual vector \(\mathbf{r}\) inherit the propagation results from the previous time step and make the necessary updates based on the current graph structure.

To construct sequential representations for all nodes in the dynamic graph, it is necessary to comprehend how to quantify the impact that changes to the network have on every node. Therefore, each node should have its individual observation perspective, with a unique comprehension of each graph modification. To improve the computational efficiency, we propose to incrementally compute the node representation when the graph changes. We start with the
following theorem on invariant properties. Due to the page limit, we defer the proof to the technical report (Bartos et al., 2017).

Theorem 1 (The Invariant Property).: _Suppose \(\hat{\mathbf{\pi}}(i)\) is the estimate of node \(i\), \(\mathbf{r}(i)\) is its residual, and \(\mathbf{x}(i)\) is its input feature, for each node \(i\in V\), we notice that \(\hat{\mathbf{\pi}}(i)\) and \(\mathbf{r}(i)\) satisfy the invariant property as follow:_

\[\hat{\mathbf{\pi}}(i)+\gamma_{\mathbf{r}}\mathbf{r}(i)=\gamma_{\mathbf{\alpha}}\mathbf{x}(i)+\sum_{ j\in N(i)}\frac{\gamma\cdot w_{(i,j)}\cdot\hat{\mathbf{\pi}}(j)}{d(i)^{\beta}d(j)^{1- \beta}}. \tag{3}\]

**Generalized update rules.** Without loss of generality, we assume that an edge \((u,v)\) with weight \(w_{(u,v)}\) is inserted to the graph. According to Equation 3, the set of affected nodes is \(V_{A}=\{u,w|w\in N(u)\}\). For node \(u\), the increment caused by the insertion can be quantified as \((\hat{\mathbf{\pi}}(u)+\gamma_{\mathbf{\alpha}}\mathbf{r}(u)-\gamma_{\mathbf{\alpha}}\mathbf{x}(u ))\frac{d(u)^{\beta}-(d(u)+w_{(u,v)})^{\beta}}{\gamma_{\mathbf{\alpha}}(d(u)+w_{( u,v)})^{\beta}}+\frac{\gamma\gamma\mu_{(u,v)}\hat{\mathbf{\pi}}(j)}{\gamma_{\mathbf{ \alpha}}(d(u)+w_{(u,v)})^{\beta}d(j)^{-\beta}}\), since the degree is updated to \(d(u)+w_{(u,v)}\) and a new neighbor \(v\) appears. According to the meaning of estimate and residual, we add this increment to the residual of node \(u\). Similarly, for each node \(w\in N(u)\), \(\frac{\hat{\mathbf{\pi}}(u)}{d(u)^{-\beta}\rho}\) in its equation will be updated to \(\frac{\hat{\mathbf{\pi}}(u)}{(d(u)+w_{(u,v)})^{1-\beta}}\) as a result of the change of node \(u\)'s degree. To guarantee that the update time complexity of each insertion is \(O(1)\), the following updates are performed to prevent alterations to node \(u\)'s neighbors:

* \(\hat{\mathbf{\pi}}(u)=\frac{d(u)^{1-\beta}}{(d(u)+w_{(u,v)})^{1-\beta}}\cdot\hat{ \mathbf{\pi}}(u)\);
* \(\mathbf{r}(u)=\mathbf{r}(u)+\frac{\hat{\mathbf{\pi}}(u)}{\gamma_{\mathbf{\alpha}}}\cdot(\frac {d(u)^{1-\beta}}{(d(u)+w_{(u,v)})^{1-\beta}}-1)\).

The detailed calculation process of the update and its batched version can also be found in the technical report (Bartos et al., 2017). Since none of variables involved in the equation of other nodes have changed, the increment induced by the insertion of the edge \((u,v)\) is zero from the perspective of node \(i\in V,i\neq u\) and \(i\notin N(u)\). Algorithm 1 is then used to propagate this increment from node \(u\) to its neighbors, informing other nodes of the change in the graph.

The preceding procedure can be easily generalized to the case of deleting the edge \((u,v)\) with weight \(w_{(u,v)}\) by simply replacing \((d(u)+w_{(u,v)})\) with \((d(u)-w_{(u,v)})\). Therefore, it is unnecessary to recalculate the feature propagation when the graph changes, but rather obtain the current propagation matrix incrementally based on the past calculation result. In addition, we have Theorem 2 to guarantee the error of propagation on each \(G_{t}\).

Theorem 2 (Error Analysis).: _Suppose \(\hat{\mathbf{\pi}}_{t}(i)\) is the estimate of node \(i\) at time \(t\), \(\mathbf{\pi}_{t}(i)\) is its ground-truth estimate at time \(t\), \(d(i)_{t}\) is its degree at time \(t\), and \(r_{max}\) is the error threshold, for each node \(i\in V\), we have \(|\mathbf{\pi}_{t}(i)-\hat{\mathbf{\pi}}_{t}(i)|\leq r_{max}\cdot d(i)_{t}^{1-\beta}\) holds for \(\forall t\in\{0,1,\ldots,T\}\)._

**Handle CTDGs.** We can utilize the aforementioned update strategy to handle incoming graph events accompanied by either inserting or removing edges. For each arriving edge \((u,v)\), we can ensure that Equation 3 holds at all nodes by updating only the estimate and residual at node \(u\), and the time complexity of the update is \(O(1)\). Therefore, the above update strategy can be well adapted to sequences of frequently arriving graph events in CTDGs.

**Handle CTDGs.** For two successive snapshots \(G_{t-1}\) and \(G_{t}\) in a DTDG, we regard the changes between the two snapshots as graph events arrived simultaneously, and it is easy to statistically extract \(V_{A}\). We can then compute exactly the increment between the two snapshots by substituting \(w_{(u,v)}\) with the degree change \(\Delta d(u)=d(u)_{t}-d(u)_{t-1}\) for each affected node \(u\in V_{A}\). Similarly, Algorithm 1 transmits information about the changes in the graph to other nodes. Therefore, when a new snapshot \(G_{t}\) arrives, we incrementally update the feature propagation matrix based on the feature propagation results of snapshot \(G_{t-1}\). Since batches of graph updates can be efficiently processed, our method naturally supports DTDGs and maintains tracking for underlying node embeddings.

**Remark.** In comparison to CTDG-specific methods, our approach updates the dynamic graph based on timestamps rather than relying solely on the order of each edge. Since it is common for multiple graph events to occur simultaneously at a single time step in real-world scenarios, handling each event individually would be suboptimal. In contrast to DTDG-specific methods, where each graph snapshot is treated as a static graph, we adopt an incremental
update approach, which allows us to update the graph incrementally based on the differences between two successive snapshots. Based on this strategy, we avoid recalculating the underlying node embeddings for each snapshot and disregarding changes to them.

### Prediction

In this section, we provide illustrations of the prediction phase by considering dynamic node classification and future link prediction as examples. These two tasks are defined in detail in Section 2.

**Dynamic node classification.** We can incrementally obtain the feature propagation matrix at each time \(t\) using Algorithm 2. Each row of the feature propagation matrix \(\tilde{Z}_{t}\), denoted as a \(d\)-dimensional vector \(\mathbf{z}_{t,i}\), is the structural-enhanced node representation vector of node \(i\in V\) at time \(t\). Therefore, \(\mathbf{z}_{t,i}\) is the representation vector of node \(i\) under the error tolerance control described in Theorem 2. Since the aggregation of node features based on graph structure has been completed during the propagation process, the node representation vector \(\mathbf{z}_{t,i}(t\!=\!1,\ldots,T)\) for each node \(i\!\in\!V\) can be regarded as the standard input vector of neural networks at this stage. For instance, we use a two-layer MLP to predict the label of node \(i\) at time \(t\) as \(\mathbf{Y}_{t}(i)=softmax(MLP(\mathbf{z}_{t,i}))\).

**Future link prediction.** In this task, we aim to learn the temporal pattern of each node to forecast if the two given nodes would be linked at the given time. The changes in the node representation over time can be regarded as a time series, and the temporal information contained within it can be captured by a common temporal model such as LSTM. Notice that utilizing sequence \(\{\mathbf{z}_{1,i},\ldots,\mathbf{z}_{T,i}\}\) to describe the dynamic network will provide a very subjective impression from node \(i\). As a result, when changes in the graph have a large influence on node \(i\), the representation vector \(\mathbf{z}_{t,i}\) changes significantly with respect to the previous moment \(\mathbf{z}_{t-1,i}\). The vector changes little from that of the previous state \(\mathbf{z}_{t-1,i}\) when changes in the graph have little influence on node \(i\). Note that the degree of influence is related to the final feature propagation matrix generated by Algorithm 2. Therefore, node \(i\)'s perception of the degree of graph change is influenced by the descriptions of its neighboring nodes through the propagation process. The completion of the future link prediction task involves the following three steps.

* **Firstly**, we calculate the difference between each node's state in two consecutive graph states as \(\mathbf{\delta}_{t,i}=g(\mathbf{z}_{t,i},\mathbf{z}_{t-1,i})\), where \(g(\cdot)\) is distance measure function. We implement \(g(\cdot)\) as a simple first-order distance, although it could also be a \(\ell_{2}\)-norm, cosine similarity, or other complicated design. Based on the above, we interpret \(\mathbf{\delta}_{t,i}(s)\) as the score of graph changes from the perspective of node \(i\) at the \(s\)-th feature dimension.
* **Secondly**, sequence models, such as LSTM, directly take the sequence \(\{\mathbf{\delta}_{t,i},\ldots,\mathbf{\delta}_{t,i}\}\) as input to capture the temporal patterns for node \(i\). Since the graph structure information is already included in \(\mathbf{z}_{t,i}\) and \(\mathbf{\delta}_{t,i}\), the sequence model can be employed more effectively by focusing solely on temporal patterns. The predicted state at time \(t\) is denoted as \(\mathbf{h}_{t}=\mathcal{M}(\mathbf{h}_{t-1},\mathbf{\delta}_{t})\), where \(\mathcal{M}\) is the chosen sequence learning model, \(\mathbf{\delta}_{t}\) is the current input vector, and \(\mathbf{h}_{t-1}\) is the learned prior state. The standard LSTM cell is defined by the following formula: \[\begin{split}\mathbf{i}_{t}&=\sigma(\mathbf{W}_{t}\mathbf{ h}_{t-1}+\mathbf{U}_{t}\mathbf{\delta}_{t}+\mathbf{b}_{i}),\\ \mathbf{f}_{t}&=\sigma(\mathbf{W}_{f}\mathbf{h}_{t-1}+\mathbf{ U}_{f}\mathbf{\delta}_{t}+\mathbf{b}_{f}),\\ \mathbf{o}_{t}&=\sigma(\mathbf{W}_{o}\mathbf{h}_{t-1}+ \mathbf{U}_{o}\mathbf{\delta}_{t}+\mathbf{b}_{o}),\\ \tilde{\mathbf{c}}_{t}&=\tanh(\mathbf{W}_{c}\mathbf{h}_{t-1 }+\mathbf{U}_{c}\mathbf{\delta}_{t}+\mathbf{b}_{c}),\\ \mathbf{c}_{t}&=\mathbf{f}_{t}\odot\mathbf{C}_{t-1}+\mathbf{i}_{ t}\odot\tilde{\mathbf{c}}_{t},\\ \mathbf{h}_{t}&=\mathbf{o}_{t}\odot\tanh(\mathbf{c}_{t}),\end{split}\] (4) where \(\sigma\) is the sigmoid activation function, \(\odot\) denotes the matrix product operation, \(\mathbf{i}_{t}\), \(\mathbf{f}_{t}\) and \(\mathbf{o}_{t}\) represent the degree parameters of the input gate, forgetting gate and output gate of the LSTM cell at time \(t\). \(\{\mathbf{W}_{t}\mathbf{U}_{t},\mathbf{b}_{t}\}\), \(\{\mathbf{W}_{f}\mathbf{U}_{f},\mathbf{b}_{f}\}\), \(\{\mathbf{W}_{o}\mathbf{U}_{o},\mathbf{b}_{o}\}\) are their corresponding network parameters, respectively. \(\tilde{\mathbf{c}}_{t}\) denotes the candidate states used to update the cell states. \(\{\mathbf{W}_{c},\mathbf{U}_{c},\mathbf{b}_{c}\}\) are the parameters of the network for generating candidate memories. \(\mathbf{c}_{t}\) is formed as the output vector \(\mathbf{h}_{t}\) at the current time \(t\) after the output gate has discarded some information. Note that the LSTM cell could be replaced by a GRU cell or a Transformer cell, as \(\mathcal{M}\) is free from graph-related computations.
* **Finally**, we combine the pair of hidden states of node \(i\) and \(j\) as \(\mathbf{\varphi}_{t}(i,j)=f(\mathbf{h}_{t,i},\mathbf{h}_{t,j})\), where \(f(\cdot)\) is the combine function, and we experiment on concatenation following previous work (Wang et al., 2019; Wang et al., 2019). Then the probability score of edge \((i,j)\)'s existence at time \(t\) is given by \(\mathbf{Y}_{t}(i,j)=\sigma(MLP(\mathbf{\varphi}_{t}(i,j)))\).

## 5. Experiments

In this section, we evaluate the effectiveness of our method on two representative tasks, future link prediction and dynamic node classification, on both CTDGs and DTDGs. Furthermore, we conduct experiments on two large-scale dynamic graphs to demonstrate the scalability of our method.

**Datasets.** We conducted experiments on seven real-world datasets, including Wikipedia (Han et al., 2017), Reddit (Han et al., 2017), UCI-MSG (Rao et al., 2018), Bitcoin-OTC (Rao et al., 2018; Wang et al., 2019), Bitcoin-Alpha (Wang et al., 2019; Wang et al., 2019), GDELT (Rao et al., 2018) and MAG (Wang et al., 2019; Wang et al., 2019). The statistics of datasets are presented in Table 1. In all graphs, the weight of an edge is determined by its frequency of occurrence. More details about the datasets can be found in the technical report (Bahdan et al., 2018).

**Baseline methods.** We compare our method to state-of-the-art dynamic graph neural networks, including TGN (Wang et al., 2019), CAW-Ns (Wang et al., 2019) for CTDGs and ROLAND (Wang et al., 2019) for DTDGs. In the two CTDG datasets, Wikipedia and Reddit, we strictly inherit the baseline results from their papers and follow the experimental setting of TGN (Wang et al., 2019). In the three DTDG datasets, UCI-Message, Bitcoin-Alpha, and Bitcoin-OTC, our experimental setting is closely related to those of EvolveGCN (Wang et al., 2019) and ROLAND (Wang et al., 2019), and we adopt the original paper's stated results. To provide a fair comparison, we employ the same data processing and partitioning techniques as TGN (Wang et al., 2019) and ROLAND (Wang et al., 2019). For the two large-scale datasets GDELT and MAG, we utilize the results reported by TGL (Rao et al., 2018). Other baseline methods are described in Section 3.

### Experiments on CTDGs

**Experimental Setting.** We conduct experiments on Wikipedia and Reddit dataset in both transductive and inductive settings, following (Wang et al., 2019). In both settings, the first 70% of edges are used as
the training set, 15% are used as the validation set, and the remaining 15% are used as the test set. In the transductive setting, we predict future links for observed nodes in the training set. In the inductive setting, the future linking status of nodes that do not present in the training set is predicted. We formulate the prediction of future links between two nodes as a binary classification problem. More specifically, we assign a label of 1 to indicate that the two nodes will be connected in the future, while a label of 0 signifies that there will be no link between them. The time span of the prediction is one time step. The popular classification metric Average Precision (AP) is employed to evaluate the algorithm's performance on both future link prediction and dynamic node classification tasks. In order to maintain the balance of the data, we generate one negative sample for each test edge or node when computing AP, following the experimental setting in TGN (Zhou et al., 2017) and TGL (Zhou et al., 2017). For our method, we set the weight coefficients \(\gamma_{k}=\alpha(1-\alpha)^{k}\), which is known as the Personalized PageRank weights with a hyperparameter \(\alpha\in(0,1)\). The standard LSTM is utilized as the sequence model to learn the temporal patterns present in the node representation. Since no node features are provided, we use a randomly generated 172-dimensional vector as the initial node feature vector.

**Results.** The results of future link prediction in both transductive and inductive settings are shown in Table 2. The presented results are the average of 10 runs. Our method performs better than baseline methods in both transductive and inductive settings. The interesting thing is that we did not use the provided edge features and achieve comparable or even better performance. This may be strongly related to the experimental setting and dataset. For the current future link prediction, we simply need to forecast whether a connection will be created between two given nodes in the future. The specifics of that link are practically of no concern. The publicly accessible edge features of Wikipedia and Reddit are derived from the textual content of each edit or post on the respective web page and sub-reddit. The learning objective is to detect whether a user would edit a certain page or post on a given sub-reddit in the future, without predicting the edit or post content. It is possible that semantic information of textual material is superfluous. The historical interaction data already contains sufficient information to reveal users' preferences for particular pages and sub-reddits. Our hypothesis is also supported by the results of our method on graphs that lack semantic information.

Table 3 shows the experimental results for the dynamic node classification. For node classification, we always use the most recent node representation based on the history observed so far. The three-layer MLP is employed as the classifier. The results in Table 3 show that our method effectively captures the temporal changes of the nodes in time, thus enabling the correct classification of the nodes.

### Experiments on DTDGs

**Experimental Setting.** We use three datasets in this experiment: Bitcoin-OTC, Bitcoin-Alpha and UCI-Message. To ensure a fair comparison, we partition the dataset and calculate evaluation measures in the same manner as ROLAND (Zhou et al., 2017). Since node features and edge features are not provided in these three datasets, we generate the 128-dimensional random vector to serve as the initial node feature. The ranking metric, Mean Reciprocal Rank (MRR), is employed to evaluate performance. We collect 1000 negative samples for each positive sample and then record the ranking of positive samples according to predicted probabilities. MRR is calculated independently for each snapshot in the test set, and the average of all snapshots is reported. For our method, we combine the node temporal representations obtained under settings \(\gamma_{k}=\alpha(1-\alpha)^{k}\) and \(\gamma_{k}=\alpha(\alpha-1)^{k}\) to approximate the low-pass and high-pass filters on the graph and

\begin{table}
\begin{tabular}{l|l l l l l} \hline \hline  & \#nodes & \#edges & max(\(t\)) & \#classes & \#node features & \#edge features \\ \hline Wikipedia & 9,227 & 157,474 & 152,757 & 2 & 172 (random) & 172 \\ Reddit & 11,000 & 672,447 & 669,065 & 2 & 172 (random) & 172 \\ UCI-Message & 1,899 & 59,835 & 87 & - & 128 (random) & - \\ Bitcoin-OTC & 5,881 & 35,592 & 138 & - & 128 (random) & 1 \\ Bitcoin-Alpha & 3,783 & 24,186 & 138 & - & 128 (random) & 1 \\ GDELT & 16,682 & 191,290,882 & 170,522 & 81 & 413 & 186 \\ MAG & 121,751,665 & 1,297,748,926 & 120 & 152 & 768 & - \\ \hline \hline \end{tabular}
\end{table}
Table 1. Statistics of the datasets.

\begin{table}
\begin{tabular}{c|c c} \hline  & Wikipedia & Reddit \\ \hline Jodie & 81.37 & **70.91** \\ DySAT & 86.30 & 61.70 \\ TGAT & 85.18 & 60.61 \\ TGN & 88.33 & 63.78 \\ APAN & 82.54 & 62.00 \\
**ours** & **89.81** & 67.53 \\ \hline \hline \end{tabular}
\end{table}
Table 3. Dynamic node classification on CTDGs. ROC AUCs (%) are exhibited.

\begin{table}
\begin{tabular}{c|c c|c c} \hline  & \multicolumn{2}{c}{Wikipedia} & \multicolumn{2}{c}{Reddit} \\ \hline  & Transductive & Inductive & Transductive & Inductive \\ \hline GAE & 91.44 \(\pm\) 0.1 & - & 93.23 \(\pm\) 0.3 & - \\ VGAE & 91.34 \(\pm\) 0.3 & - & 92.92 \(\pm\) 0.2 & - \\ DeepWalk & 90.71 \(\pm\) 0.6 & - & 83.10 \(\pm\) 0.5 & - \\ Node2Vec & 91.48 \(\pm\) 0.3 & - & 84.58 \(\pm\) 0.5 & - \\ GAT & 94.73 \(\pm\) 0.2 & 91.27 \(\pm\) 0.4 & 97.33 \(\pm\) 0.2 & 95.37 \(\pm\) 1.1 \\ GraphSAGE & 93.56 \(\pm\) 0.2 & 91.09 \(\pm\) 0.3 & 97.65 \(\pm\) 0.2 & 96.27 \(\pm\) 0.2 \\ CTDNE & 92.17 \(\pm\) 0.5 & - & 91.41 \(\pm\) 0.3 & - \\ Jodie & 94.62 \(\pm\) 0.5 & 93.11 \(\pm\) 0.4 & 97.11 \(\pm\) 0.3 & 94.36 \(\pm\) 1.1 \\ TGAT & 95.34 \(\pm\) 0.1 & 93.99 \(\pm\) 0.3 & 98.12 \(\pm\) 0.2 & 96.62 \(\pm\) 0.3 \\ DyRep & 94.59 \(\pm\) 0.2 & 92.05 \(\pm\) 0.3 & 97.98 \(\pm\) 0.1 & 95.68 \(\pm\) 0.2 \\ TGN & 98.46 \(\pm\) 0.1 & 97.81 \(\pm\) 0.1 & 98.70 \(\pm\) 0.1 & 97.55 \(\pm\) 0.1 \\ CAW-N-mean & 98.28 \(\pm\) 0.1 & 98.28 \(\pm\) 0.1 & 98.72 \(\pm\) 0.1 & 98.74 \(\pm\) 0.1 \\ CAW-N-attn & 98.84 \(\pm\) 0.1 & 98.31 \(\pm\) 0.1 & 98.80 \(\pm\) 0.1 & 98.77 \(\pm\) 0.1 \\
**ours** & **99.16 \(\pm\) 0.3** & **98.54 \(\pm\) 0.2** & **99.51 \(\pm\) 0.5** & **98.81 \(\pm\) 0.6** \\ \hline \hline \end{tabular}
\end{table}
Table 2. Future link prediction on CTDGs. AP (%) \(\pm\) standard deviations computed of 10 random seeds are exhibited.
introduce low-frequency and high-frequency information, respectively. Three traditional sequence models, LSTM (He et al., 2017), GRU (He et al., 2017) and Transformer (Zhu et al., 2017), are used to finish the future link prediction task.

**Results.** The results in Table 4 demonstrate the state-of-the-art performances of our method. In the Bitcoin-OTC dataset, our method outperforms the second-best method ROLAND by 41%. The results show that the LSTM model consistently outperforms the GRU model, which is possibly due to the LSTM having more parameters. The Transformer model tends to achieve a higher MRR, which could be attributed to its holistic approach to the temporal sequence of nodes and reduced reliance on previous hidden states. Additionally, we conducted an ablation study in the technical report (He et al., 2017) to validate the necessity of introducing high-frequency information.

### Experiments on Large Graphs

**Experimental Setting.** To demonstrate the scalability of our method, we conduct experiments on two large-scale real-world graphs, GDELT and MAG. We exclude EvolveGCN (Zhu et al., 2017), ROLAND (Zhu et al., 2017) and CAW-Ns (Zhu et al., 2017) from experiments on GDELT and MAG datasets, since they met out-of-memory issues on both datasets. Note that the scalability of the baseline methods JODIE (Zhu et al., 2017), DySAT (Zhu et al., 2017), TGAT (Zhu et al., 2017), TGN (Zhu et al., 2017), and APAN (Zhu et al., 2017) was not taken into account in their original papers, and their original versions cannot be trained on these two large-scale dynamic graphs. TGL (Zhu et al., 2017) has successfully applied these methods to large-scale graphs by developing a distributed dynamic graph neural network training framework. In contrast, our method can learn large-scale graphs directly. Our method exhibits greater scalability due to the elimination of parameters in the propagation process, allowing the training on these two large-scale graphs to be completed on a single machine. We validate the performance of all methods on the dynamic node classification task and compare their performance using the multiple-class classification metric F1-Micro. To guarantee a fair comparison, we ensure that the training, validation and test sets are consistent with the settings in TGL. For our method, we set \(\gamma_{k}=\alpha(1-\alpha)^{k}\) to obtain the temporal representation of each node, and a three-layer MLP is utilized to complete the training for the classification task.

**Results.** Table 5 shows the dynamic node classification results. Compared to baseline methods, we achieve significant performance improvement in both datasets. Specifically, our method improves F1-Micro by 13.6 on the GDELT dataset and 9.68 on the MAG dataset. This indicates that our method can effectively capture the dynamic changes in node representations by precisely locating the directly affected nodes via Equation 3 and quantifying the degree of graph change. The following propagation process that immediately follows broadcasts the change from the affected node to its surroundings, so that higher-order neighbors can also naturally perceive the change on the graph. However, from a practical application standpoint, the performance of all methods in GDELT is not adequate. We note that this is due to the presence of much noise in the labeled data of GDELT. Participants can participate in events held around the world via remote means such as online, resulting in some nodes may simultaneously belong to many classes.

## 6. Conclusion

This paper propose a universal general graph neural network for dynamic graphs that can extract the structural and attribute information of the graph, as well as the temporal information. Our algorithm is based on the framework of decoupled GNNs, which can pre-compute temporal propagation in dynamic graphs and then train them for downstream tasks depending on the nodes' temporal representation. We devised a unified dynamic propagation methods to support the learning on both continuous-time and discrete-time dynamic graphs. Empirical studies on continuous-time and discrete-time dynamic graphs at various scales demonstrate the scalability and state-of-the-art performance of our algorithm.

###### Acknowledgements.

 This research was supported in part by National Key R&D Program of China (2022ZD0114802), by National Natural Science Foundation of China (No. U2241212, No. 61972401, No. 61932001, No. 61832017),

\begin{table}
\begin{tabular}{c|c c c} \hline \hline  & \multicolumn{1}{c}{UCI-Message} & Bitcoin-Alpha & Bitcoin-OTC \\ \hline GCN & 0.1141 & 0.0031 & 0.0025 \\ DynGEM & 0.1055 & 0.1287 & 0.0921 \\ dyngraph2vecAE & 0.0540 & 0.1478 & 0.0916 \\ dyngraph2vecAERNN & 0.0713 & 0.1945 & 0.1268 \\ EvolveGCN-H & 0.0899 & 0.1104 & 0.0690 \\ EvolveGCN-O & 0.1379 & 0.1185 & 0.0968 \\ ROLAND Moving Average & 0.0649 \(\pm\) 0.0049 & 0.1399 \(\pm\) 0.0107 & 0.0468 \(\pm\) 0.0022 \\ ROLAND MLP & 0.0875 \(\pm\) 0.0110 & 0.1561 \(\pm\) 0.0114 & 0.0778 \(\pm\) 0.0024 \\ ROLAND GRU & 0.2289 \(\pm\) 0.0618 & 0.2885 \(\pm\) 0.0123 & 0.2203 \(\pm\) 0.0167 \\ \hline  & GRU & 0.2024 \(\pm\) 0.0010 & 0.3289 \(\pm\) 0.0070 & 0.2985 \(\pm\) 0.0121 \\
**ours** & LSTM & 0.2140 \(\pm\) 0.0034 & **0.3405 \(\pm\) 0.0133** & 0.3102 \(\pm\) 0.0046 \\  & Transformer & **0.2314 \(\pm\) 0.0048** & 0.3173 \(\pm\) 0.0135 & **0.3110 \(\pm\) 0.0049** \\ \hline \hline \end{tabular}
\end{table}
Table 4. Future link prediction on DTDGs. MRR \(\pm\) standard deviations computed of 3 random seeds are exhibited.

\begin{table}
\begin{tabular}{c|c c} \hline \hline  & GDELT & MAG \\ \hline Jodie & 11.25 & 43.94 \\ DySAT & 10.05 & 50.42 \\ TGAT & 10.04 & 51.72 \\ TGN & 11.89 & 49.20 \\ APAN & 10.03 & - \\
**ours** & **25.49** & **61.40** \\ \hline \hline \end{tabular}
\end{table}
Table 5. Dynamic node classification on large graphs. F1-Micros (%) are exhibited.
by the major key project of PCL (PCL2021A12), by Beijing Natural Science Foundation (No. 4222028), by Beijing Outstanding Young Scientist Program No.BJJWZYJH012019100020098, by Alibaba Group through Alibaba Innovative Research Program, and by Huawei-Renmin University joint program on Information Retrieval. Jiajun Liu was supported in part by CSIRO's Science Leader project R-91559. We also wish to acknowledge the support provided by Engineering Research Center of Next-Generation Intelligent Search and Recommendation, Ministry of Education. Additionally, we acknowledge the support from Intelligent Social Governance Interdisciplinary Platform, Major Innovation & Planning Interdisciplinary Platform for the "Double-First Class" Initiative, Public Policy and Decision-making Research Lab, Public Computing Cloud, Renmin University of China.
