Exploiting Interaction Links for Node Classification with Deep Graph Neural Networks

1 Introduction

Node classification is a central task in relational machine learning. In complex network domains, node classification methods have used different types of relational information such as features of direct neighbors [Lu and Getoor, 2003] and autocorrelation of class labels [Jensen et al., 2004]. While these, and other, methods have shown the effectiveness of using neighbor information to improve node classification, many real-world network datasets have sparse link structure which limits the amount of neighbor information available for classification. This is particularly true for networks constructed from interactions over time. Recent work on low-dimensional node embeddings and neural network architectures for graphs [Kipf and Welling, 2016; Grover and Leskovec, 2016] has shown promising results for addressing the sparsity problem in node classification tasks on static graphs. In particular, GCN [Kipf and Welling, 2016] learns individual node embeddings by passing, transforming, and aggregating node feature information across neighbors in an end-to-end fashion.

While many real world social network domains consist of interactions that are changing and evolving over time, it can be difficult to leverage the dynamics of temporal interactions in node classification methods. For example, users develop connections in social networks while interacting and communicating among themselves over time. The temporal patterns of interactions could be potentially useful for predicting their class labels (e.g., political view.) However, when the interaction edges are very sparse in each temporal snapshot or when a node's neighborhood is biased toward a particular class label in different snapshots, it may be difficult to identify temporal patterns that are useful for prediction. In these cases, static aggregated patterns may be more informative. Our proposed model can not only learn temporal interaction patterns, but also model the aggregated neighborhood, and jointly learn how to combine the two views for node classification.

Specifically, in this paper, we propose a novel deep neural network architecture for sequences of interaction graphs, called TSGNet. Our TSGNet model learns a temporal encoder that leverages the strengths of both the GCN to discover interaction patterns at each temporal snapshot and a recurrent unit, LSTM [Hochreiter and Schmidhuber, 1997], to capture complex long-term dependencies. To learn the temporal representation more efficiently, we propose a mini-batch training via importance sampling, which reduces the recursive neighborhood expansion across layers and helps to decrease time complexity while maintaining performance. In addition, TSGNet learns a second neighbor encoder representation from a static summary of each node's neighborhood. The static and temporal components of the model are jointly estimated to optimize node classification performance. For evaluation, we conduct extensive experiments on both one synthetic and four different real-world networks, with and without attributes, and we observe significant performance gains compared to state-of-the-art methods. Moreover, we conduct a careful ablation study to show that our architecture design is most robust compared to models that use different static and/or temporal components.

2 ProblemDefinition

2.1 Motivation

Figure 1a-b show examples of interactions in complex networks. Each node and edge indicate an author and a coauthor event, respectively. Note that colors represent topic labels, yellow for NLP and grey for Database. In Figure 1a, user A and B have the same coauthors (neighbors) when they are aggregated. In this context, the existing graph embedding approaches (e.g., Node2Vec [Grover and Leskovec, 2016] or GCN [Kipf and Welling, 2016]) will end up learning similar latent representations for the two nodes. However, their temporal interaction patterns may be different. When author A collaborates with other authors differently over time, compared to author B, their representations should be modified accordingly. Meanwhile, if node A and B show similar interaction patterns over time, then it may be difficult to determine the correct class labels through temporal patterns only. In Figure 1b, although the temporal coauthoring patterns around author A and B are similar, their neighborhoods on the aggregated graph are entirely different. In that case, using the aggregated neighborhoods (which correspond to static features) the class labels of node A and B could be identified.

In this paper, our goal is to jointly learn patterns in both interactions over time and in static neighbor sets. In order to model both properties, we propose a neural network model, TSGNet. The details are described in Section 3.

2.2 Notation

We define a graph sequence as a set of graphs such that G = [G1,G2, ...,Gm]. Each Gk has the same set of nodes, vi ∈ V where ∀i ∈ [1, n], but a different set of edges, Ek ⊆ V ×V such that Gk = 〈V, Ek〉. If eij ∈ Ek, there is an edge between vi and vj at time k, otherwise there is not. Alternatively, let A = [A1,A2, ...,Am] be the set of adjacency matrices for G, where Ak[i, j] = 1 if eij ∈ Ek, 0 otherwise. While the network structure is changing over time, we assume that the node attributes are not changing over time 1 . Let F be the feature (attribute) set over the nodes. Each vi ∈ V has a corresponding feature vector fi ∈ F. Y is the label set over the nodes. Only a subset of the nodes, vi ⊆ V , have a class label, yi ∈ R|C| , where C is a set of class labels. The goal is to learn a model from the partially labeled network and use the model to make predictions ˆy for the unlabeled nodes {vi} s.t. yi /∈ Y . In this work, we assume that Y can be multi-labeled. Moreover, each prediction ˆ yi for vi has an estimated probability.

1 The setting is realistic for many social and interaction graphs because available node attributes are from basic profiles, resources, or fixed properties, so they are static or changing very slowly. For example, in Facebook, profile attributes like gender and religious

3 TSGNet for Node Classification

Figure 1c represents the overall architecture for TSGNet. The TSGNet is composed of (1) a static neighbor encoder and (2) multiple layers of GCN for modeling interaction graphs at each time step k. The details of each are described below.

3.1 GCN Layers

We use GCN as a basic component for modeling each temporal graph, A = [A1,A2, ...,Am]. Before the data is fed into the GCN, we use the symmetric normalizing trick described in [Kipf and Welling, 2016]. Dk is the diagonal degree matrix of Ak + I, and I is an Identity matrix:

Each GCN layer produces node-level output H(l+1) k ∈ R|V |×Z(l) where |V | is the number of nodes and Z (l) is the size of output representation per a node, which is determined by W(l) k . The outputs are generated at each time step, k.

views are used as attributes, and in IMDB pre-determined values like contents-rating and budgets are used as attributes of movies.

Note that each GCN layer has its own W(l) k at each time stamp, and ReLU is used only in the first GCN layer. Moreover, GCN originally uses the attribute matrix for H(1) k [Kipf and Welling, 2016]. In this paper, we also support a nonattribute option, where the identity matrix is used for H(1) k .

Let L be the number of GCN layers for each time step, then the final output for each time step will be an input for an LSTM cell. I.e., H(L+1) k for each time step, k, is the temporal input for the kth cell in the LSTM sequence. In Eq. (3) below, oi returns the final output vector for vi in the LSTM. The output, oi, is projected a final time using the weight matrix, Wlstm, and bias vector, blstm. This will be added to the neighbor encoder for vi below. If the interaction of vi ends before the last step, m, it still uses the sameWlstm, and blstm to generate the output, o′i .

3.2 Neighbor Encoder (NE)

The neighbor encoder uses an aggregated matrix ˇAagg as input. ˇAagg is created by aggregating all elements in [A1,A2, ...,Am] and normalizing in the same way described above. The static component reduces the dimensionality for node vi from its neighbor vector in ˇAagg, using stacked fully-connected layers.

where ⊙ refers to the Hadamard product, hi = {hi,j}|V | j=1 . Here, if ˇAagg[i, j] > 0, hi,j = β (for β ≥ 1). Otherwise, hi,j will be equal to 0. This Hadamard product is used to overcome sparsity in the adjacency matrix. If β is 1, it is the same as the adjacency matrix. Otherwise, it puts more weight on non-zero elements in the matrix. It is expected that β will make larger outputs and offset issues from sparsity. In experiments, we set β = 20, and using this we observe up to 4% of improvement in accuracy.

3.3 Addition Layer

The element-wise addition layer combines the outputs from the GCN-LSTM and the Neighbor Encoder. Specifically, we compute ˆvi as the element-wise addition of the outputs from the GCN-LSTM (Eq. 3) and the Neighbor Encoder (Eq. 4):

The addition layer enables a joint representation learned from both the static and temporal neighborhoods around the node. An additional benefit is that the addition layer does not introduce extra parameters, nor does it increase computational complexity. Then, the output, ˆvi is put though another softmax layer for classification:

Algorithm 1 TSGNet's mini-batched training (one epoch)

Generate a mini-batch set B from V

for each mini-batch ∈ B do

Sample |S| vertices, v1, ..., vs ∈ B according to distribution q frommini-batch

Initialize ˜Aagg to |V | × |V | matrix of zeros

for each v ∈ S do

end for

Compute the categorical cross-entropy in Eq. (7)

Update W(l)

and bfinal

end for k , Wlstm, W(1),..,(L′ ) , b(1),..,(L′ ) , Wfinal,

Here, ˆyi is the vector output of the softmax function, and each dimension ˆ yi,j represents the predicted probability of the corresponding class j, given the inputs. For learning, we use categorical cross-entropy (over VL, the set of labeled nodes) as a loss function at the final layer

Since all activation functions are differentiable, learning is simply done via back-propagation.

3.4 Importance Sampling

Note that, in Eq. (2), the neighbor aggregation for node u is computed as:

which involves a sum over all other nodes in the graph. When we use multiple GCN layers, the recursive neighborhood expansion across layers poses time and memory challenges for training with large graphs. To overcome this limitation, we propose a method for efficient sampling-based learning.

Similar to [Chen et al., 2018], we approximate the equation above with importance sampling. First, we sample a set of S nodes using an importance distribution based on the overall number of interactions, q(v) = ||ˇAagg[:, v]||2 / ∑v′∈V ||ˇAagg[:, v′ ]||2 . Then given the sampled set S, we set ˜A(l) k = ˇAk[S, S] ∈ R|S|×|S| for all layers l < L and ˜A(l) k = ˇAk[:, S] ∈ R|V |×|S| when l = L, i.e., the last GCN layer. At the last layer, GCN still returns the node representation for all V . Finally, we approximate Eq. (8) for node u as follows:

Note the distribution q is only calculated once (i.e., before training) given the normalized aggregated graph and the input feature matrix, H(1) k , should also be updated according to S via H(1) k =H(1) k [S, :].

Our overall mini-batched training procedure is described in Algorithm 1. At every epoch, all nodes are randomly divided to create a mini-batch set, B, which is composed of multiples of γ nodes. We set γ = 1024. B provides a candidate node set for sampling |S| later. When it comes to a new mini-batch, ˜A(1)..(L) k is induced from ˇAk according to the S. Similarity, the input matrix of neighbor encoder, ˇAagg, is replaced by ˜Aagg. The inner for-loop for ˇAagg retains only the edges in S, but maintains the dimensionality of the NE.

3.5 Complexity Analysis

Recall that m is the number of temporal GCNs and |F| is the number of node attributes. Then assuming the number of hidden units in LSTM, GCN, and NE is constant, the computational complexity of TSGNet is O(|V | +m|F||E|), where O(|V |) is from neighbor encoder and O(m|F ||E|) is from the set of temporal GCNs. Because m and |F | are typically much smaller than |E|, the time complexity is linear in the number of edges, i.e., O(|E|). With importance sampling, the complexity becomes O(|V | + |ES|), where |ES| is the number of edges induced in S. When the non-attribute option is chosen, the complexity is still O(|V | + |ES|) because the input identity matrix is sparse, thus |F| = 1 in the sparse representation, and can be considered as a constant with sparse-dense matrix multiplication.

4 RelatedWork

Supervised node classification. There is some work on relational models that consider temporal patterns to improve node classification. TVRC [Sharan and Neville, 2008] attempts to model temporal structures through a two-step process. The key idea behind the TVRC is to model the temporal patterns through an exponential weight decay kernel, where the implicit assumption is that network structure in recent past is more important than the structure in the earlier past. The work was extended to ensemble model in [Rossi and Neville, 2012], but it is still limited in learning complex temporal interaction patterns because it heavily relies on the graph summarization with kernel-based edge weighting. This limits the models ability to learn more diverse temporal interactions, and temporal information is lost when collapsing graphs. In addition, DDRC [Park et al., 2017] proposed a convolutional neural network architecture with max pooling for node classification, which models temporal interactions among a node's neighbors. DDRC shows stable performance in spite of different variability of neighbor vectors. However, its effectiveness was partially shown in long and relatively denser graph sequences. Our TSGNet is evaluated from more diverse and larger graph datasets and shows better performance.

Dynamic node embedding. Recently, dynamic network embedding approaches were proposed by [Zhang et al., 2018; Zhu et al., 2018; Ma et al., 2018], which use spectral updates over time for general relational tasks. However, they are evaluated in a synthetic setting, where two temporal snapshots are created by assigning a random timestamp to each edge. Moreover, attributes are also not exploited for learning temporal representations. In addition, CTDNE [Nguyen et al., 2018] learns node representations using temporal random walks. While the method shows promising results on link prediction tasks, it is still limited for learning attributes of nodes and is under-explored to supervised node classification tasks. DynamicTriad [Zhou et al., 2018] also attempted to learn node evolution through representation learning for general relational learning tasks using multiple temporal graph snapshots, but their effectiveness on node classification is still not clear. For example, they are limited to specific types of evolution strategies, and attributes are also not used.

Model categorization. Table 1 categorizes TSGNet and other baseline models according to the types of relational information they use as inputs to their models (w.r.t. edges and attributes). TSGNet uses dynamic interaction edges with and without attributes. In our experiments, we compare TSGNet to all the listed models. Logistic Regression (LR) and Multi-layered Neural Network (NN), Node2Vec [Grover and Leskovec, 2016], and an attributed node embedding, ASNE [Liao et al., 2018], are also employed to model static edges. See Section 5 for more detail. The colors in the table will be used later in the experiments to highlight the performance achieved using each type of relational input.

5 Experimental Evaluation

5.1 Data

We use four real-world network datasets for evaluation. Table 2 reports brief statistics for each network.

Facebook. The Facebook network was scraped from the Purdue University network [Pfeiffer et al., 2015]. Each user (node) is associated with political views for their class labels. An edge is formed when a user writes a post to his or her friend's wall. Users who post more than once a week for at least 8 weeks are chosen. A time window is defined as two weeks. Node attributes are religious views and gender.

DBLP. For this dataset, we extract a co-authorship network from the papers published in DBLP from 2000-2017. An edge is created to link two authors when they publish a paper together, with a time stamp based on the publication. Thus, nodes represent authors. Publication venues are selected from AI/NLP and DB conferences 2 . Authors are selected when they have at least 7 years of publication history, and their class label is assigned as the area in which they publish the majority of their papers. Node attributes correspond to term vectors from the titles of each user's published papers.

IMDB G (Gross Income). We use Kaggle's IMDB (Internet Movie Database) 5,000 movie dataset. An edge is formed when two movies share an actor or actress at each year. All movies have at least 2 temporal edges. A movie has a positive label if the movie gross is larger than 10 million dollars. For this work, we choose budgets, content rating, the number of faces in a movie poster, and genres as features. The budgets are quantized from 0 to 9 using percentiles. Each feature is transformed into one-hot encoding representation.

IMDB R (Rating). This dataset is from the whole IMDB database 3 , and all participants including actors and writers are imported. An edge is formed when two movies share any crew at each year. When a movie's rating is larger than 7.0, it is chosen as a positive label. The periods of all movies are from 2005 and 2018. There are many missing values when all movies are considered, so node attributes are ignored in this dataset. All movies have at least 11 temporal edges.

5.2 ComparisonModels

Logistic regression (LR). Logistic regression is performed using neighbor vectors with L1 regularization. This allows us to compare how relational and temporal patterns improve performance. The aggregated (binary or degree normalized (weighted)) graph of all temporal graphs is used for training.

LSTM. We use the TSGNet's input representation for the LSTM, but the GCN layers and the neighbor encoder are not used in the architecture. For inputs, the first-hop neighbors at each time window are fed directly into the LSTM layer.

GCN and GraphSAGE. To compare TSGNet with Graph neural networks, GCN [Kipf and Welling, 2016] and GraphSAGE [Hamilton et al., 2017] are evaluated with the aggregated (binary) static graph input. Attributes are used in the same way with TSGNet. We used an LSTM aggregator for GraphSAGE. Because other aggregators for the GraphSAGE such as GCN, mean, and pool are worse than LSTM, the results are not reported here.

Node2Vec. For learning a static node embedding method, Node2Vec, we set d = [16, 32, 64], r = 10, l = 80, k = 10, and p and q were searched over [0.5, 1, 2]. The aggregated (binary) matrix is used for its training.

ASNE. ASNE [Liao et al., 2018] is a recent attributed node embedding method. We used the same hyper-parameter search criteria as in [Liao et al., 2018].

2 AI/NLP: IJCAI, AAAI, SIGIR, ECIR, CLEF, CHIIR, AIRS, ACL, EMNLP, and COLING; DB: ICDE, VLDB, SIGMOD/PODS, and EDBT.

3 The IMDB dataset was downloaded November 2018.

DDRC. DDRC [Park et al., 2017] is a CNN-baed temporal classifier, which considers interactions over time. This does not have a neighbor encoder or GCN component. The inputs are used as in LSTM above.

Multi-layered neural network (NN). For NN, the neighbor encoder of TSGNet is used for training and testing.

TempGCN (GCN+LSTM). This is a version of the TSGNet without the neighbor encoder (NE) component where we use GCN to model the temporal graphs with an LSTM.

DynamicTriad. A dynamic node embedding method, DynamicTriad, is also tested with all combinations of parameters as in [Zhou et al., 2018]. Both unweighted graphs and weighted graphs were used for learning, and edges are weighted by the number of common neighbors.

5.3 EvaluationMethodology

Every result we report is the average of 10 trials using randomly shuffled node sets. Note that the entire graph is known before learning, and 70%, 20%, and 10% of node labels are used for training, testing, and validation, respectively. If the accuracy on the validation dataset does not increase during five epochs, learning stops. We also use dropout regularization (0.2) and rectified linear units for activation functions. For optimization, we use the adam optimizer [Kingma and Ba, 2014] to update variables. For TSGNet, LSTM, and GCN, the number of hidden nodes is searched over [16, 32, 64, 128], and the numbers of hidden nodes in the neighbor encoder are 512, 128, and 16 at each layer. In addition, there are three GCN layers for TSGNet. For importance sampling, the sampling size, |S| is chosen from [16, 32, 128, 256, 512].

5.4 Results: Synthetic Data

To evaluate the concept of TSGNet, we generate synthetic data from two simplified-Dynamic Stochastic Block Models (DSBM) [Yang et al., 2011] to evaluate our model. We set the number of users to 100, and the length of time-windows for each node is determined by 25 + uniform(0, 1) × 25. The first DSBM (Dense Block Model) is composed of 4 different partitions, P1, .., P4, at time(k)%2 == 1. Each partition is composed of 50×50 nodes. In all other time-windows, edges are generated from 9 partitions, P ′1 , .., P ′9 . Each partition has different edge probabilities, as in Figure 2. The second model (Sparse Block Model) is designed to generate sparse DSBM with low probability. All other conditions are same, but each probability is 10 times sparser than the dense block model. For class labels, 0 is assigned for the first half of nodes (thus, senders of P1 and P2), and 1 is set to the second half.

Node classification accuracy (and standard errors) on the synthetic data are shown in Table 3. Bold numbers indicate statistically significant top results. For data from both sparse and dense block models, our proposed model exhibited good performance. While DynamicTriad, DDRC, and LSTM show better performance than TSGNet in the dense data, they are worse in the sparse block model. Meanwhile, other classifiers (GCN, LR, and NN), which were originally designed for static graphs, showed the worse performance than TSGNet's results. Node2Vec works well for the sparse data, but it is worse than TSGNet (p-value < 0.05 in paired t-test).

5.5 Results: Real-world Data

Performance without Node Attributes

Table 4 shows the classification results for the four different real-world datasets. Note that bolded numbers indicate statistically significant top results. (Weighted) in LR refers to versions where the input matrices of the corresponding methods are normalized by the number of edges per each node. In the experiment, TSGNet exhibited the best performance over other alternatives for all datasets and shows comparable performance to TSGNet w/o IS (Importance Sampling). While simple static classifiers such as LR and NN return good performance for Facebook (FB) and DBLP due to the high correlation between neighbor vectors and class labels, however, they are still worse than our TSGNet. These characteristics make TempGCN more difficult to model the data because it is too complex to learn the simple neighborhood. Despite that, the neighbor encoder component of the TSGNet helps it learn the hidden dependencies among nodes and their static neighborhood well. As a result, it produces a significant gain in performance. DDRC and LSTM showed poor performance because the data is also very sparse. DynamicTriads are better than GCN and GraphSAGE in IMDB G but still worse than TempGCN and TSGNet. Overall, TSGNet produces an average reduction in classification error of 16%, compared to GraphSAGE, which is the best competitor.

Figure 3 shows learning curves on the four datasets as we vary the amount of training data. The learning curves compare the performance as the number of training nodes increases. Note that the set of nodes for testing and validation is same across all range of x-axis. Although the number of training nodes was controlled to calculate the supervised loss, the complete adjacency matrices at each time step for the GCN layers were fixed for the experiment. The experimental assumption was also applied to all other alternatives, TempGCN, Node2Vec, and LR. For Node2Vec, the compete network structure is known for learning representation, and the number of nodes is controlled when its supervised classifier is trained. Therefore, all results with the small training data were not poor. In the Facebook and DBLP datasets, TSGNet was consistently better than the others. For IMDB G dataset, TSGNet improved in performance as the size of training set increased.

Performance with Node Attributes

Table 5 shows classification results when node attributes are incorporated into the models. The result for TSGNet with attributes was better than the other alternatives which used attributes in their input. Moreover, the performance of TSGNet without attributes was even better than the result of the best model which uses attributes. Note that, for the DDRC without attributes, an identity matrix is concatenated to the input neighbor vector. This result indicates that it can learn a good representation with only the structural interactions. (attr. + neighbor) refers to a concatenated input including both attribute and neighborhood vectors. ASNE, LR, and NN with the new input show good results in general, but they are worse than TSGNet. ASNE performed poorly on DBLP because it could not utilize labels to learn the embedding. Also, GCN did not work well both with and without attributes. GCN is based on a 1-layer perceptron, which is not a universal approximator [Hornik, 1991]. The 1-layer perceptron in the GCN works like a linear mapping, so the layers may degenerate into simply summing over neighborhood features [Xu et al., 2019]. With this reason, GraphSAGE with LSTM aggregator can model interaction better than GCN for Facebook and DBLP. Overall, TSGNet with or w/o attributes reduces classification error up to 24% and produces an average reduction in classification error of 10%, compared to GraphSAGE.

Temporal Sequence Randomization: Impact on Performance

To see the effect of temporal sequence's randomization, the time-windows were randomly shuffled and used for training. The order of words in language models for NLP and speech recognition is quite important to represent sentences, but the temporal order of social interactions could be reversed and often spontaneously happen. In this case, the randomized temporal sequences are likely to represent another instance of evolution. As can be seen in Table 6, TSGNet and TempGCN also work well given the randomized inputs and are not significantly different from the results of original inputs. These results may be interpreted in the context of recent work on Janossy pooling [Murphy et al., 2019] for learning permutation invariant functions with LSTMs via randomization. The fact that the randomized inputs work well within our LSTM architecture may indicate that the model is learning a temporally-invariant function over the interactions.

Ablation Study of Model Components

TSGNet uses GCNs for learning temporal interactions and a NN neighbor encoder for learning the aggregated static firstneighbors. However, we could have chosen other architectures for either component. Table 7 shows the results for different variants of the architecture, with the original components of TSGNet in the first row. Note that we did not use importance sampling to see the true effect of each component. Instead of the GCN in TSGNet, when we use regular densely-connected NN, its performances decreases in DBLP, as shown in the second row of the table. When the GCN is missing in TSGNet like the last row of the table, it also does not work well. Similarly, when the NN in TSGNet is replaced with GCN layers or an empty layer, we can observe the significant drop in Facebook and DBLP. This indicates that our NN-based neighbor encoder helps to jointly learn the temporal network's interaction well if we use GCN layers.

6 Conclusions

In this paper, we described TSGNet, a neural network architecture that can learn jointly from static and temporal neighborhood structure. The architecture exploits the interactions among local neighbors over time, by learning the temporal evolution of a low-dimensional embedding from a GCN, and models its static neighborhood with a densely connected NN. TSGNet is able to improve classification performance by utilizing both patterns in social interactions over time and the set of nodes in the aggregate relational neighborhood.

Acknowledgments

We thank the anonymous reviewers for their useful comments. This research is supported by NSF and AFRL under contract numbers: IIS-1546488, IIS-1618690, and FA865018-2-7879. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation hereon.