Spatio-Temporal Attentive RNN for Node Classification in Temporal Attributed Graphs

1 Introduction

A large amount of graphs have been generated because of the rapid growth of information, such as co-author graphs [Ni et al., 2018], brain graphs [Wang et al., 2017a] and post graphs [Hamilton et al., 2017]. Node classification approaches aim to classify the nodes into different categories according to graph topology and node attributes. There have been a lot of efforts on node classification [Perozzi et al., 2014; Grover and Leskovec, 2016; Kipf and Welling, 2017;

∗These authors contributed equally to this work

Veliˇckovi´c et al., 2018]. node2vec [Grover and Leskovec, 2016] adopts a biased random walk to learn richer node representations and classifies nodes via a logistic regression model. GCN [Kipf and Welling, 2017] introduces a convolutional architecture directly applied on graphs and node labels are predicted by a softmax function. An attention-based network that performs node classification in graphs is proposed in [Veliˇckovi´c et al., 2018].

In many real-world applications, graphs are often dynamic and evolve rapidly over time. Hence, basic graph concepts are further extended to temporal graphs. Some recent progresses have been made on the node classification in temporal graphs [Du et al., 2018; Goyal et al., 2018b; Zhou et al., 2018; Zhu et al., 2018]. For example, DynamicTriad [Zhou et al., 2018] extracts the evolution patterns of temporal graphs and uses a logistic regression model to classify nodes. DNE [Du et al., 2018] extends the skip-gram based graph embedding methods into dynamic settings. The work in the literature is mostly designed for the case where graph topology evolves over time. However, a vast majority of real-world networks are coupled with a rich set of vertex attributes, which also evolve over time. As temporal and spatial dimensions are entangled, it's desirable to design an effective approach that can jointly model the spatio-temporal contextual information for both graph topology and node attributes, at the same time provide model interpretability for the classification results.

In this work, we focus on the problem of node classification in temporal attributed graphs. Given a sequence of attributed graphs for the same set of nodes, where each node has a unique class label over a period of time, the task is to predict the labels of unlabeled nodes by learning from the labeled ones. Both graph topology and node attributes change over time. The problem is challenging for two major reasons. First, effectively modeling the spatio-temporal contextual information is hard. For the temporal attributed graphs, the evolution lies in both graph topology and node attributes. Along with the changes, the temporal and spatial dimensions are entangled. How to jointly learn the node representations on both spatial and temporal aspects simultaneously is challenging. Second, differentiating the relative importance of different factors that influence node representations for effective classification is also challenging. Different neighbors at different time periods will influence node representations diversely. As the changes in temporal and spatial dimensions jointly determine the node labels, it is desirable to recognize which neighbors in which time periods exert more influence on the representation learning of the target node.

To address the above challenges, we propose a spatiotemporal attentive recurrent neural network model (STAR). STAR aims to learn node representations for classification by jointly considering both the temporal and spatial patterns of the node. Specifically, STAR embeds the sampling and aggregation of local neighbor nodes into a gated recurrent unit (GRU) network [Cho et al., 2014] to jointly learn the spatiotemporal contextual information. By feeding sequential node attributes at different time periods into the GRU network, the temporal features of attributes evolution can be effectively extracted. The process is entangled with the graph topology learning, in which the neighborhood representations are sampled and aggregated to learn the spatial information of the target node. Moreover, a dual attention mechanism on both temporal and spatial aspects is developed to selectively aggregate different time periods and different neighbors, which helps to perform a thorough analysis on the model interpretability. In particular, based on the temporal attention, we can detect the time periods that are more important for the node representations for classification, while the spatial attention can help us put more emphasis on the important neighbors. To summarize, the major contributions are as follows.

• We propose STAR. STAR is the first model that can provide the model interpretability for the node classification in temporal attributed graphs.
• We design a spatio-temporal GRU network that can jointly model the temporal evolution of both node attributes and graph topology.
• We perform extensive experiments on real datasets to evaluate the effectiveness of the proposed model. The results demonstrate the effectiveness of STAR.

2 The Problem

A temporal attributed graph is a collection of snapshots of an attributed graph at different time steps, denoted by G = (G 1 , G 2 , · · · , G T ). G t = (V, At , Xt ) is the graph at time step t. The set of nodes V is fixed for all time steps. Each node has its consistent label across T time steps. At ∈ RN×N is the adjacency matrix and Xt ∈ RN×d is the node attribute matrix. Both At and Xt are different at different time steps. Given G and the labels of a subset of nodes VL, the goal of node classification in temporal attributed graphs is to classify the nodes in subset VU whose labels are unknown, where V = VL ∪ VU .

3 Spatio-Temporal Attentive RNN

The framework of STAR is shown in Figure 1. It includes a spatio-temporal GRU and a dual attention module. First, we introduce the basic GRU. Then, we introduce the spatiotemporal GRU and discuss the dual attention mechanism.

3.1 Gated Recurrent Unit

The GRU network is an effective approach to capture the temporal patterns of sequential data. Given a sequence of input data x1, ...xT ∈ Rd , a state vector ht ∈ Rdh is calculated for each input data by applying the following equations iteratively.

where Wz,Wr,Wh ∈ Rdh×(d+dh) and bz, br, bh ∈ Rdh are parameters. zt, rt ∈ Rdh are called update, reset gates separately and their values are in the range of [0,1]. h0 = 0. ⊕ denotes concatenation operator. ⊙ denotes elementwise multiplication. The concatenation of all the state vectors [h1⊕· · ·⊕hT ] or the last state vector hT is usually used as the representation for the whole sequence. GRU can be utilized to classify the nodes in temporal attributed graphs. The intuitive way is to first feed the node attributes at different time steps into GRU to generate the node representations. Then apply a classifier to the learned representations. However, the basic approach ignores the neighborhood information of the node. Next we will introduce how to jointly integrate the neighborhood information so that the graph structural information can also be encoded for node classification.

3.2 Vector Representation of The Neighborhood

We extract a neighborhood vector for each node at each time step to represent its neighborhood information. The key idea is to aggregate the neighbors' representations. We will consider K-hop neighbors.

First, we prepare the K-hop neighbors. Given a set of nodes B to be classified, we sample the immediate neighbors of the nodes in B. These sampled neighbors and the nodes in B together form a new set B1 . We do the same for B1 and get another new set B2 . As a result, we can get a sequence of sets denoted by B0 ... BK , where B0 = B. The neighbors are sampled by sampling function N(·). The process is described in Algorithm 1.

Then, based on the sequence of node sets, we generate the neighborhood vectors for all the nodes in B. It is described in Algorithm 2, where gkt(v) is the representation of node v after aggregating its k-th hop neighbors at time step t. The key idea is to apply aggregator AGGk(·) to aggregate the neighbors' representations (Line 5) and concatenate the aggregation with

Algorithm 1: Preparing K-hop Neighbors

the node's representation (Line 6). The new representation is generated by a nonlinear transformation. Wktrans ∈ Rdg×2dg is the transformation matrix that we need to learn. We will introduce AGG(·) in Section 3.4.

3.3 Spatio-Temporal GRU

To integrate the neighborhood vector, a spatio-temporal GRU (ST-GRU) is proposed. The intuition behind ST-GRU is that we consider the neighborhood information besides the node attributes and the previous state vector when generating the new proposal to update the state vector (Eq. (8)). ST-GRU has two advantages. The state vectors explicitly contain both the temporal information of node attributes and the spatial information encoded in the neighborhoods. And it is practical to further implement a dual attention mechanism on both temporal and spatial aspects.

ST-GRU is described in Eqs. (5)-(9). Given a sequence of node attributes x1, ..., xT ∈ Rd and a sequence of neighborhood vectors e1, ..., eT ∈ Rdg , a state vector h′t ∈ Rdh is calculated for each time step by applying the following equations iteratively, where h′0 = 0.

where b′z , b′r , b′s , b′h ∈ Rdh , W′s ∈ Rdg×(d+dh+dg) , W′z , W′r , W′s ∈ Rdh×(d+dh+dg) are parameters. z′t , r′t ∈ Rdh , s′t ∈ Rdg are called update, reset, neighborhood gates respectively.

Eqs. (5)-(7) describe the calculation process of the three gates. The gates control the information when generating the state vector. The intuition of considering the node attributes, the previous state vector and the current neighborhood vector is that the current state vector is influenced by the current information of the node, the previous state vector and the current neighborhood information.

Eq. (8) describes the calculation process of a new proposal. The values in all gates are in the range of [0,1]. r′t ⊙ h′t-1 indicates how much information to keep from the previous state

Algorithm 2: Generating Neighborhood Vector

Input: Temporal attributed graph G = (G 1 , G 2 , ..., G T ), K-hop neighbors B0 t ... BK t , where B0 t = B Output: Neighborhood vector et(v) for all v ∈ B0 t

vector. s′t ⊙ et indicates how much information to keep from its neighborhoods. Eq. (9) describes the calculation of a new state vector. (1-z′t ) ⊙ h′t-1 indicates how much information to throw away from the previous state vector. z′t ⊙˜h′t indicates how much new information to add from the new proposal.

3.4 Dual AttentionMechanism

Spatial Attention

Different neighbors influence node presentations diversely. Attention technique is capable of adaptively capturing the pertinent information [Vaswani et al., 2017; Shaw et al., 2018]. We design a spatial attention module to detect the important neighbors of a node.

The spatial attention is applied to the aggregator during the aggregation process (Line 5 in Algorithm 2). Based on the attention values, the aggregator sums up the neighbors' representations as follows.

where ∑ βk u = 1 and Vk ∈ Rdg×dg are parameters. βk u is the attention value of neighbor u located at the k-th hop. It indicates the importance of u to node v compared to other neighbors located at the k-th hop. βk u is produced by our spatial attention module that takes the representations of the node and its neighbors as inputs, which is described as follows.

where F(·) is an activation function. wk ∈ Rdg and Vk ∈ Rdg×dg are parameters.

Temporal Attention

For a temporal attributed graph G = (G 1 , G 2 , ..., G T ), the amount of valuable information provided by different time steps is different. Only some contain the most discriminative information for determining node labels. Take brain graphs as an example. The nodes represent the tidy cubes of brain tissue [Avena-Koenigsberger et al., 2018]. For the nodes related to language processing, the time during which the subject is speaking should have higher importance than the time when the subject does not speak. Based on this insight, a temporal attention module is designed to automatically pay different levels of attention to different time steps.

The temporal attention module takes the state vector h′t as input and outputs an attention value for it as follows.

where ˜w∈Rdα and ˜V∈Rdα×dh are parameters. αt indicates the importance of time step t for determining the target node's label compared to others. The concatenation of all the state vectors is denoted by

Thus, the attention values of all state vectors are

Then we sum up all the state vectors scaled by α to generate a vector representation for the node shown as follows.

The output of one such attention unit usually focuses on one part of the temporal pattern of the node. However, it is possible that multiple parts together describe the overall pattern. Thus we need multiple attention units to focus on different parts. Suppose there are m parts needed to extract from the input. We use m ˜w's and concatenate them as ˜W = [ ˜w1 ⊕ · · · ⊕ ˜wm]. The resulting attention value matrix is

where softmax(·) performs on the 2nd dimension of its input. The final representation is then denoted by

3.5 Objective Function

Given the node representations denoted by Q1,· · · , QN and the node labels y1 ,· · · , yN , where N is the number of nodes, the objective function of STAR is

Lce = - 1N ∑Ni=1 yi log ( ˜ yi ) is the cross-entropy loss. ˜ yi is the estimate. It is produced by applying softmax(·) to the output of a fully connected layer that takes the node representation as input, i.e., ˜ yi = softmax(WoQi+bo). Wo ∈ Rc×mdh and bo ∈ Rc are parameters. c is the number of classes. Patt = ‖AA⊤ -I‖2F is the penalization term to encourage multiple attentions to diverge from each other. Pnn is the penalization term for the parameters to prevent STAR from over-fitting. λ1 and λ1 are the hyper-parameters.

3.6 Computational Analysis

STAR is local in time and the length of input sequence does not affect its storage requirements. The complexity of STAR per time step is proportional to the number of parameters. The parameters of STAR are from the spatio-temporal GRU and the dual attention mechanism. Specifically, the numbers of parameters for generating the neighborhood vector and updating the spatio-temporal cell are 2(K-1)d2g and (dg+3dh)(d+dg+dh)+4dh respectively. Because dg=dh and d>dg, the complexity of the spatio-temporal GRU per time step is O(Kd2g +ddg). The number of parameters of the dual attention is K(2d2g +dg)+dα(m+dg). Because dα=dg and dg>m, the complexity of the dual attention is O(Kd2g ). Thus, the complexity per time step of STAR is O(Kd2g +ddg).

4 Experiments

4.1 Datasets and Baselines

We use four real datasets as shown in Table 1. In the Brain dataset, the nodes represent the tidy cubes of brain tissue and the edges indicate the connectivity [Preti et al., 2017]. We apply PCA to the functional magnetic resonance imaging (fMRI) data 1 to generate node attributes. Two nodes are connected if they show similar degree of activation [GonzalezCastillo et al., 2015]. In the Reddit dataset 2 , the nodes represent the posts. Two posts are connected if they contain similar keywords. We apply the word2vec approach [Mikolov et al., 2013] to the comments of a post to generate its node attributes [Hamilton et al., 2017]. The DBLP-3 and DBLP-5 datasets are extracted from the bibliography website DBLP 3 . Both of them are the co-author graphs where nodes represent authors. The paper titles and abstracts are used to generate node attributes by word2vec. The authors in DBLP-3 and DBLP-5 are from three and five research areas respectively.

We compare STAR with the state-of-the-art baseline methods. The comparison between them is shown in Table 2. DeepWalk [Perozzi et al., 2014], node2vec [Grover and Leskovec, 2016], GCN [Kipf and Welling, 2017] and GraphSAGE [Veliˇckovi´c et al., 2018] are originally designed for static graphs. They can not model the temporal patterns of the sequence data. We first apply them to each time step to generate an node representation. Then we concatenate the representations of different time steps into a vector. The node labels are predicted by employing a logistic regression model on the vector. LSTM [Hochreiter and Schmidhuber, 1997], GRU [Cho et al., 2014], DynGEM [Goyal et al., 2018b] and DynAERNN [Goyal et al., 2018a] can model the temporal patterns. LSTM and GRU only consider the evolution of node attributes. DynGEM and DynAERNN can model the neighborhood information.

1 https://tinyurl.com/y4hhw8ro

2 https://www.reddit.com/

3 https://dblp.uni-trier.de/

To evaluate the effectiveness of different components of STAR, we study its variants. STAR-NH is the variant that generates node representations only based on node attributes. The temporal attention is applied. STAR-TA is the variant without applying the temporal attention. STAR-SA is the variant without applying the spatial attention. It generates the aggregation of the neighborhood by the mean pooling.

In our experiments, dg, dh and dα are set to 10. K and m are set to 2 and 3 respectively. λ1 and λ2 are set to 10-3 . They are determined by grid-search from {1,2,5,10,15}, {1,2,3,4} and {0, 10-5 ,10-4 ,10-3 ,10-2 } respectively. N(·) is the uniform sampling function. The number of sampled neighbors is set to 4. LeakyReLU [Maas et al., 2013] is adopted as F(·). We apply 10-fold cross-validation to evaluate all supervised methods. STAR is implemented with Tensorflow [Abadi et al., 2016] and optimized by Adam [Kingma and Ba, 2014]. The code of STAR and the data used are publicly available 4 .

4.2 Experimental Results

Node classification. We evaluate the classification results by accuracy, AUC and F1 [Grover and Leskovec, 2016], which are shown in Table 3. It is observed that STAR achieves the best performance. DeepWalk and node2vec show good performance on the Reddit dataset. This is because the node labels of Reddit are largely dominated by the graph topology information, which is well utilized by DeepWalk and node2vec. LSTM and GRU show good performance on Brain, DBLP-3 and DBLP-5, where the node labels are dominated by node attributes information. STAR shows the best performance on all datasets, which indicates STAR utilizes well both graph topology and node attributes. Moreover, compared to DynGEM and DynAERNN, STAR shows a better ability of modeling the evolution patterns of temporal attributed graphs. STAR outperforms STAR-NH, indicating the importance of the spatial information of neighborhood on extracting better representations. By comparing STAR with STAR-TA and STAR-SA, we see the benefits of applying the dual attention mechanism.

4 https://tinyurl.com/y67ywq6j

Visualization of temporal attention. To investigate the interpretability of STAR, we visualize the attention values of different time steps. Figure 2 shows the results on four categories of nodes from the Brain dataset. It is observed that the nodes belonging to different categories show different kinds of attention distributions across time steps. This is because different categories of brain nodes show different degrees of activation when the subject conducts different tasks. For example, during time steps 7, 8 and 11, the subject mainly focuses on processing the audio information. As can be seen in Figure 2(a), the attention values of time steps 7, 8 and 11 are significantly larger for the nodes belonging to the category of auditory processing. Similar observations can be observed in Figures 2(b)-2(d). Larger values indicate that these time steps are more important for the node representations for classification. This demonstrates the effectiveness of the temporal attention mechanism. In addition, for Figure 2(a), the attention values of time steps 7, 8 and 11 are generated by three temporal attention units respectively. The same case exists for Figures 2(b)-2(d). This verifies the effectiveness of the multiple temporal attention mechanism.

Visualization of spatial attention. To gain further insight about the interpretability of STAR, we visualize the attention values of different neighbors. The results of two nodes from the Brain dataset, node 4023 and node 3266, are shown in Figure 3. Different node colors represent different node categories. Solid red and dotted gray lines represent higher and lower attention values respectively. Higher values indicate the neighbors are more important to the target node's representation. As can be seen in Figure 3, the target node is influenced more by the the neighbors from the same category. This is because the nodes from the same category play similar roles in the graph. For example, for node 4023, its immedi-

(a) Auditory Processing

• (b) Language Processing

(c) Emotion Processing

(d) Body Movement

Figure 3: Visualization of spatial attention values. Solid red and dotted gray lines indicate higher and lower values respectively.

ate neighbors with higher attention values are node 3685 and node 2975. The two nodes and node 4023 belong to the category of auditory processing. Similar observations can be observed for node 3266. This verifies that STAR is capable of detecting the important neighbors for node classification based on the spatial attention mechanism.

Parameter sensitivity. We study the sensitivity of STAR with respect to two parameters, the size of state vectors dh and the parameter for the attention penalization term λ1. The values of dh and λ1 are from {1,2,5,10,15} and {0, 10-5 , 10-4 ,10-3 ,10-2 } respectively. Other settings are the same as Section 4.1. Figs. 4(a)-4(b) summarize the results of dh and λ1 respectively. It is observed that as dh or λ1 increases, the classification accuracy increases until an optimal value. dh ∈ [10,15] and λ1 ∈ [10-4 ,10-2 ] give the optimal results. Thus, it is reasonable to set them as 10 and 10-3 respectively. Moreover, the non-zero choices of λ1 verify the importance of the attention penalization term in STAR in Eq. (18).

5 RelatedWork

In recent years, node classification has drawn extensive research attention [Perozzi et al., 2014; Grover and Leskovec, 2016; Wang et al., 2016; Kipf and Welling, 2017; Wang et al., 2017b; Hamilton et al., 2017]. Random walks are employed to extract the local information of a node in the graph. Nodes are further classified based on the local information preserved by word embedding techniques [Perozzi et al., 2014]. A biased random walk is proposed to learn richer node representations by exploring diverse local information [Grover and Leskovec, 2016]. Recently, some interest has been focused on the use of attention mechanism for node classification [Veliˇckovi´c et al., 2018]. These approaches are for the static graphs. Graphs in many real-world applications are dynamic. Both graph topology and node attributes evolve over time. Some recent progresses have been made on the node classification in the temporal graphs [Zhu et al., 2018; Du et al., 2018; Goyal et al., 2018a; Ma et al., 2018; Zuo et al., 2018; Yu et al., 2018]. The triadic closure process is used to model the evolution patterns of temporal graphs and a logistic regression model is used to classify nodes [Zhou et al., 2018]. To make the node representations stable over time, the node representation at time t is generated from the one at time t-1 [Goyal et al., 2018b]. SLIDE [Li et al., 2018] uses a low-rank matrix to preserve all observed nodes in the graph where both structure and attributes change. However, none of these approaches can differentiate the relative importance of different factors that influence node representations.

6 Conclusion

In this paper, we propose a novel method, STAR, for node classification in temporal attributed graphs. STAR consists of a spatio-temporal GRU and a dual attention module. By feeding the sequential node attributes and the neighborhood representations into the GRU, the temporal features of attributes evolution and the spatial information of the node's local neighborhood can be effectively modeled respectively. A dual attention mechanism is developed to perform a thorough analysis on the interpretability of STAR. And it helps STAR detect the time steps and the node neighbors that are more important for the classification. Extensive experimental results demonstrate the effectiveness of STAR.

Acknowledgements

This work was partially supported by the National Science Foundation grant IIS-1707548.