Dynamic Graph Node Classification via Time Augmentation

Many existing works utilize recurrent models for discrete-time dynamic graphs to capture the temporal dynamics into hidden states for classification. Some works use separate GNNs to model individual graph snapshot and use RNNs to learn temporal dynamics [5]; some other works integrate GNNs and RNNs together into one layer, aiming to learn the spatial and temporal information concurrently [13]. Sankar et al.  [6] use the self-attention mechanism along both the spatial and temporal dimensions of dynamic graphs, while Xu et al.  [1] combine the self-attention mechanism and RNNs together to learn the spatio-temporal contextual information jointly.

Existing works on continuous-time dynamic graphs include RNN-based methods, temporal walk-based methods and temporal point process-based methods. RNN-based methods perform node updates through recurrent models at fine-grained timestamps [14], and the other two categories incorporate temporal dependencies through temporal random walks and parameterized temporal point processes [15, 16].

The first realization aims to produce a bijection between all possible walks on the time-augmented graph and all possible temporal walks on the original temporal graph. Formally, we denote the adjacency matrix of the constructed time-augmented graph as ${\bm{A}}\in{\mathbb{R}}^{TN\times TN}$. Then, the adjacency matrix of the time-augmented graph can be represented as:

where $\tilde{A}^{t}\in{\mathbb{R}}^{N\times N}$ is the corresponding adjacency matrix at time step $t$ with self-loops added.

In the self-evolution time-augmentation realization, we restrict the cross-time walks such that only temporally adjacent nodes can be attended by their historical versions. Formally, let $v^{t}$ and $v^{t+1}$ denote node $v$ at time $t$ and $t+1$. We only construct edge $(v^{t},v^{t+1})$. By doing so, all temporal walks can be realized by performing random walk on the time-augmented graph as it can visit a node’s neighbor at different time steps by visiting itself at different time steps first. With previous notation, the adjacency matrix of the time-augmented graph can be represented as:

where $I\in{\mathbb{R}}^{N\times N}$ is the identity matrix modeling node version updates across time. It is important to note that this realization of the time-augmented graph is relatively simplified and imposes trivial overhead in model space complexity.

In the third case where we aim to completely disentangle structural and temporal modeling, we decouple the self-evolution time-augmentation case. Instead of considering one time-augmented graph ${\bm{A}}$, we decouple it into ${\bm{A}}_{s}\in{\mathbb{R}}^{TN\times TN}$ and ${\bm{A}}_{t}\in{\mathbb{R}}^{TN\times TN}$ as below:

First, inspired by [18], we employ the dynamic attention mechanism to compute the adaptive information transition matrix, which allows different importance of nodes to be learned. Formally, the adaptive graph transition matrix $\hat{{\bm{A}}}\in{\mathbb{R}}^{TN\times TN}$ is computed as:

where ${\bm{\Theta}}_{L}\in{\mathbb{R}}^{F\times d}$ and ${\bm{\Theta}}_{R}\in{\mathbb{R}}^{F\times d}$ are the adaptive weight matrices applied on initial node features, $[\cdot,\cdot]$ is the horizontal concatenation of two matrix, $[\cdot||\cdot]$ is the vector concatenation operation, ${\bm{a}}\in{\mathbb{R}}^{F}$ is a learnable weight vector for attention calculation, $\sigma_{att}(\cdot)$ is the LeakyReLU activation, ${\mathcal{N}}_{v}=\{u\in{\mathcal{V}}_{ta}:(u,v)\in{\mathcal{E}}_{ta}\}$ denotes the immediate neighbor set of node $v$ on the time-augmented graph, and $\alpha_{uv}$ denotes the normalized attention coefficient of link $(u,v)$. For the disentangled time-augmentation case, the adaptive structural and temporal transition matrices $\hat{{\bm{A}}}_{s}\in{\mathbb{R}}^{TN\times TN}$ and $\hat{{\bm{A}}}_{t}\in{\mathbb{R}}^{TN\times TN}$ are computed separately following the exact same procedures but with different parameters. We would like to emphasize that the dynamic attention mechanism we introduced does not impose quadratic computational complexity with respect to the number of snapshots as previously mentioned attention-based models [6] since the attention scores are computed structurally for time-augmented neighborhoods.

In order to capture long range temporal and structural dependencies on the time-augmented graph, deep architectures are necessary. However, it is well-known that some GNN models such as GCN [3] and GAT [4] demonstrate significant performance degradation when the number of layers increases [19]. Thus, we adapt the message passing mechanism from GCNII [20] which relieves such over-smoothing issue through initial residual and identity mapping techniques. Formally, we denote the number of stacked information propagation layers as $L$ and the node representation output from the $l^{th}$ layer for the time-augmented graph as $\{{\bm{h}}_{v}^{l}\in{\mathbb{R}}^{F},\forall v\in{\mathcal{V}}\}$ where $F$ is the node representation dimension. The input is either the initial encoded or intermediate node representations: $\{{\bm{h}}_{v}^{l-1}\in{\mathbb{R}}^{F},\forall v\in{\mathcal{V}}\}$. When $l=1$, i.e., at the first layer, we have ${\bm{h}}_{v}^{0}={\bm{\Theta}}_{R}{\bm{x}}_{v}$. Compactly, we have ${\bm{H}}^{l}\in{\mathbb{R}}^{TN\times F}$. Then, we can define the message passing mechanism as:

where ${\bm{W}}^{l}\in{\mathbb{R}}^{F\times F}$ is the weight matrix, ${\bm{I}}\in{\mathbb{R}}^{F\times F}$ is the identity matrix, $\sigma_{ip}$ is the ReLU activation, $\alpha_{l}$ and $\beta_{l}$ are two hyperparameters adopting the same practice of GCNII [20]. We also adapt GCNII variant, whose message passing mechanism is defined as:

where different weights ${\bm{W}}_{1}^{l},{\bm{W}}_{2}^{l}$ are used for aggregated node representations $\hat{{\bm{A}}}{\bm{H}}^{l}$ and initial residual representations ${\bm{H}}^{0}$. Again, for the disentangled time-augmentation case, we compute the node representations ${\bm{H}}$ by first utilizing structural transition matrix $\hat{{\bm{A}}}_{s}$ to capture structural properties and then using temporal transition matrix $\hat{{\bm{A}}}_{t}$ to learn temporal dynamics, with different weight matrices ${\bm{W}}_{s}^{l}$ and ${\bm{W}}_{t}^{l}$. With ${\bm{A}}_{s},{\bm{A}}_{t}$ as the structural and temporal graph respectively, we first use one information propagation module for the structural graph ${\bm{A}}_{s}$. After we obtain ${\bm{H}}_{s}$ which summarizes structural information, we apply the second information propagation module guided by the temporal graph ${\bm{A}}_{t}$, with ${\bm{H}}_{s}$ as the initial node embedding input. Finally, we use ${\bm{H}}^{L}$ that summarizes both structural and temporal dynamics for the dynamic node classification task.

Dynamic node classification task is used to evaluate TADGNN’s effectiveness compared with other baselines. All models are trained based on the training partition ${\mathbb{G}}_{L}=\{{\mathcal{G}}^{1},{\mathcal{G}}^{2},\ldots,{\mathcal{G}}^{t}\}$ with label information. The task is to predict node labels in ${\mathbb{G}}_{U}=\{{\mathcal{G}}^{t+1},{\mathcal{G}}^{t+2},\ldots,{\mathcal{G}}^{T}\}$ by using the trained model with the entire dynamic graph ${\mathbb{G}}=\{{\mathcal{G}}^{1},{\mathcal{G}}^{2},\ldots,{\mathcal{G}}^{T}\}$ as input. Note that TADGNN is inductive since it is agnostic to number of input graph snapshots.

Each dataset is sliced into a discrete graph snapshot sequence where each snapshot corresponds to a fixed time interval that contains a sufficient number of links. In each set of experiments, the first $t$ snapshots are used for model training. After training, we use the next $t^{\prime}$ snapshots for validation, and the rest $T-t-t^{\prime}$ snapshots for testing. For all train/validation/test stages, TADGNN processes input graph snapshots all at once. We show the train/validation/test split statistics in Table II. Weighted cross-entropy loss is used as the objective function, that class weights obtained from training partition are used to relieve data imbalance issue. The original DySAT model is temporally transductive as it cannot easily incorporate new graph snapshots for testing. Thus, we modify its position embeddings [25] to sine and cosine positional encodings as in Transformer [26]. For the static baselines, we employ one shared model across all snapshots. All models are trained end-to-end.

Since label information for all four datasets are highly imbalanced, we select Area Under the Receiver Operating Characteristic Curve (AUC) metric to measure performance of different models. We use macro-AUC scores for evaluation. Macro-AUC is computed by treating performances from all classes across all time steps (i.e., snapshots) equally, which is desirable for the case of dynamic node classification.

We show the macro-AUC results in Table III. Our observations include:

• •

  TADGNN achieves superior performance on most of the datasets. This indicates that TADGNN can better capture both structural and temporal graph dynamics comparing to other methods. On one dataset (ML-Genre) GAT performed well and has better result, but its performances have larger variance on different datasets. In addition,  TADGNN is more efficient in space and time complexity, and can be applied in more scenarios especially where the dynamic graphs are large.

• •

  Other dynamic baselines have inferior performance on certain datasets comparing to static methods. Besides, these dynamic baselines tend to keep larger variances for most datasets, which suggests that TADGNN is more robust to random weight initialization. The results from our hyper-parameter search and analysis further indicate that the performance of these methods can be sensitive to hyper-parameter values; however, large time cost and space cost limit their potentials. This further suggests the importance of using temporal information efficiently to guide the dynamic graph node classification problem.