GAEN: Graph Attention Evolving Networks

1 Introduction

Networks are ubiquitous to organize real-world data and systems, such as social networks, citation networks, communication networks, and protein interaction networks [Zhang et al., 2020]. The past few years have witnessed many successful graph-based applications such as text classification [Yao et al., 2019], image recognition [Chen et al., 2019] and traffic prediction [Zhao et al., 2019], which are largely benefited from the fruitful network embedding techniques. Given a network, the key to designing a successful network embedding framework lies in the high-efficient mechanism to fully capture the complex relationships (e.g., structure and feature similarities) among nodes, such that nodes with close relationships are represented with similar embedding vectors.

Traditional methods, including DeepWalk [Perozzi et al., 2014] and Node2vec [Grover and Leskovec, 2016], perform truncated random walks over the entire network to capture the neighborhood relationships between nodes. Recent work mainly focuses on the graph neural networks [Wu et al., 2020], where the idea is that nodes can aggregate features from their respective neighbors (e.g., first-order and secondorder) to preserve structure relationships in the embedding space with multiple graph convolution kernels or filters [Kipf and Welling, 2017; Veliˇckovi´c et al., 2017]. While existing methods are designed to characterize relationships between nodes from different views and levels, i.e., local and global neighborhood relationships, for quality node representation learning, they are specialized in modeling static networks with invariable node sets and topology structures.

In reality, most real-world networked systems are in an evolving process [Fournier-Viger et al., 2020], where network nodes and structures are continuously changing over time. For example, the dynamic social network arises from new edges and nodes being frequently created when new actors join the network or new friendships are being established. Analogically, newWeb pages and their links are interminably added and old ones are deleted, resulting in a highly dynamic Web page citation network. In the biological domain, the physical interactions among proteins will change with the age of proteins, resulting in an evolving protein-protein interaction network [Hegele et al., 2012]. In the dynamic environment, the network evolution trajectory can be recorded and streaming networked data can be organized in a temporal sequence composed of multiple varying networks at different time steps. Compared with a single static network, dynamic networks inherently reflect more complex relationships between nodes, i.e., the node structure evolutionary patterns. As a result, in addition to the structural node relationships observed from the most recent static network, the correlations between the current network with all its historical networks within a temporal sequence can be modeled to enhance the representation learning of dynamic networks.

To capture network dynamics, existing methods typically impose some regularization/constrain on embedding learning of networks at different time steps. For example, in the literature [Seo et al., 2018; Manessi et al., 2020], Long Short-Term Memory (LSTM) networks are used to model a sequence of temporal networks, i.e., each node can utilize its past node features for enriched embedding learning, where the static network at each time step is modeled by independent Graph Convolutional Networks (GCN) [Kipf and Welling, 2017]. Similarly, dynamic attention network [Sankar et al., 2019] is also proposed to capture temporal dynamics where each node can use its historical representations, while each static network is modeled based on a respective Graph Attention Networks (GAT) [Veliˇckovi´c et al., 2017]. Despite both network dynamics and structures can be preserved, above methods fail to consider the following two attractive properties of dynamic networks:

• Similar Network Topologies: While a network Gt at time t evolves to network Gt+1 at time (t + 1), the network topologies between Gt and Gt+1 are usually similar. Instead of learning the two networks independently, weights of the learning model (e.g., GCN) for Gt can be evolved to the model for Gt+1, thereby making the training across all temporal networks more efficient.
• Temporal Variation Patterns: While a network changes over time, nodes would demonstrate some temporal variation (e.g., change of local structures) patterns, i.e., adding or removing a link with a neighborhood, observed from a fixed number of sequential evolution steps. Such pattern information can be explicitly modeled in that nodes with similar patterns being close in the embedding space.

To this end, in this paper we propose a novel network representation learning framework, Graph Attention Evolving Networks (GAEN), for dynamic networks organized as a sequence of evolving networks at different time steps. Instead of learning the static networks at each time step independently as most existing methods do, GAEN learns to evolve and share model weights across all temporal networks based on a Gated Recurrent Unit (GRU) [Cho et al., 2014] by learning the topological discrepancies between networks. To model temporal node variation patterns, we first stack each network (e.g., adjacency matrix) with all its historical networks to form a three-way tensor, from which node temporal variation pattern similarities are derived based on the tensor factorization technique. Then, the pattern information is explicitly incorporated into the respective neighborhood attention calculation for enhanced network representation learning at each dynamic time point. Experimental results on four real-world datasets in both dynamic link prediction and node classification tasks demonstrate the effectiveness of the proposed approach.

It is necessary to mention that a recent work [Pareja et al., 2020], along a similar direction, proposes to evolve GCN weights with a recurrent neural network by taking the node features at different time steps as inputs. In comparison, our model considers the topological discrepancies between temporal networks to evolve and share multi-head graph attention network learning weights. In addition, to the best of our knowledge, this is the first work to explicitly represent and incorporate dynamic node variation patterns for learning dynamic graph attention networks.

In summary, our contribution is threefold: 1) We propose a novel graph attention network called GAEN for learning temporal networks; 2) We propose to evolve and share multi-head graph attention network weights by using a GRU to learn the topology discrepancies between temporal networks; and 3) We propose to represent temporal node variation patterns and explicitly incorporate pattern information for enhanced neighborhood attention and network embedding learning.

2 RelatedWork

Graph Neural Networks. Inspired by the success of Convolutional Neural Networks (CNN) which typically focus on the grid-like data, Graph Neural Networks (GNN) for learning irregular networked data have seen an explosion in attention over the past few years [Wu et al., 2020]. The incredible embedding learning ability of GNN lies in various efficient graph convolution filters. GCN adopts a spectral-based filter where each node generates the representation by aggregating features from its neighborhoods [Kipf and Welling, 2017]. Graph Attention Networks (GAT) extend to learn additional importance weights so that important neighborhoods will be given higher attention [Veliˇckovi´c et al., 2017]. GraphSAGE learns a set of aggregation functions for each node to flexibly aggregate information from neighborhoods of different hops. [Hamilton et al., 2017]. To select the appropriate convolution filter for a specific graph learning task, some researchers propose the GNN architecture search which can identify the optimal one from a set of candidate models [Shi et al., 2020].

Temporal Network Learning. Recently, some works seek to extend existing GNN models to handle temporal networks, where node sets and edge connections can evolve over time. STGCN employs a GCN layer to model the spatial dependency among network nodes at each time step, followed by a CNN layer to capture the temporal dependencies of networks at different time steps [Yu et al., 2017]. DySAT designs a self-attention mechanism in two directions namely structural neighborhood and temporal dynamics to respectively capture node dependency relationships within and between networks [Sankar et al., 2019]. EvolveGCN adapts GCN along the temporal dimension by using a recurrent neural network to evolve the GCN learning weights [Pareja et al., 2020]. In comparison, in this paper we focus on evolving the graph attention networks with multiple attention heads. Different from existing works that typically enforce some regularization on the multiple dynamic networks to capture the temporal node relationships, we propose to first represent the temporal node variation patterns and then explicitly incorporate them into each time step for enhanced node relationships modeling and network embedding learning.

3 ProblemDefinition

In this work, we extend graph attention networks to study an evolutionary graph attention network learning problem. An evolving network can be represented as a sequence of graph snapshots G = {G1, · · · ,GT}, where T is the number of time steps. Each snapshot at time step t ∈ [1, T]

is an undirected graph represented by Gt = (Vt, Et,Xt), where Vt = {vi}i=1,··· ,|Vt| is a set of unique nodes, Et = {eij}i,j=1,··· ,|Vt| is a set of edges which can be encoded in an adjacency matrix At ∈ R|Vt|×|Vt| , and Xt ∈ R|Vt|×d contains all |Vt| nodes and their d-dimensional feature vectors.

The objective of this paper is to map graph Gt ∈ G to a low-dimensional embedding space Ot ∈ R|Vt|×h while taking all its historical graphs G1,G2, · · · ,Gt-1 into consideration. It is worth noting that node sets of underlying graphs may be different. In this case, we are able to uniform node sets of these graphs by aligning them to the largest graph with maximum number of nodes n. Therefore, in the following we assume that adjacency matrices for graphs at different time steps have the same size n × n. In this work, we focus on evolving the graph attention networks to capture the dependency relationships across all input graphs and meanwhile explicitly preserve node variation or changing patterns derived from the temporal graph evolution sequence.

4 The ProposedMethod

The proposed approach includes two major parts. First, we propose to extract temporal node variation pattern similarities from the respective graph topology evolution sequence based on the non-negative tensor factorization. Then, node variation pattern similarities are explicitly incorporated into the graph evolving attention network learning, where a neural model, GAEN shown in Fig.2, is proposed to evolve graph attention network weights across all temporal graphs. Details of the above processes are illustrated in the following sections.

4.1 Node Variation Pattern Similarity Calculation

Nodes often demonstrate implicit variation patterns as graph evolves over time [Fournier-Viger et al., 2020]. We are interested in the variation of graph structures, where graph nodes in the dynamic process of creating and removing connections with neighborhoods could exhibit similar structure changing patterns. For a given graph Gt at time t ∈ [1, T], its current topology structure together with all past topology structures can be organized in a three-way array or tensor by St = [A0,A1, · · ·At] ∈ Rn×n×t , where the structural dependencies between nodes are encoded in the frontal slice St[:: t] ∈ Rn×n and the structure variations of each node vi are encoded in the respective horizontal slice St[i ::] ∈ Rn×t along the time axis. Then, as shown in Fig.1 we aim to calculate the pairwise node variation pattern similarities by modeling above structure dependencies and variations simultaneously with tensor factorization (TF) [Kolda and Bader, 2009].

TF has been widely utilized to model high-order variable correlations and further discover temporal variation patterns of objects [Takeuchi et al., 2017]. In this paper, we consider non-negative TF (e.g., both input and output are nonnegative) based on the PARAFAC model given that its factorization results are deterministic [Kolda and Bader, 2009].

Definition 1 (rank-one): A tensor T ∈ RI1×I2×···×IN of order N has rank-one if it can be written as the outer product (notation ◦) of N vectors, i.e., T = b(1) ◦ b(2) ◦ · · · ◦ b(N) or Ti1,i2,··· ,iN = b(1) i1 b(2) i2 · · · b(N) iN for all 1 ≤ in ≤ IN.

Formally, TF aims to decompose tensor St ∈ Rn×n×t (t ∈ [1, T ]) into a sum of component rank-one tensors as:

where R is a parameter denoting the number of latent factors. Et = [e1, e2, · · · , eR] ∈ Rn×R, Qt = [q1 , q2 , · · · , qR] ∈ Rn×R and Ft = [f1, f2, · · · , fR] ∈ Rt×R are latent factor matrices, i.e., combination of rank-one components, where Et and Qt are equivalent since St is symmetric for undirected graphs. Et or Qt can be interpreted as that nodes along the 1st or 2nd mode (shown in Fig.1) are conceptually mapped in a shared space with R latent factors, while Ft reveals the variation patterns of these latent factors along the time axis (3rd mode). Then, we further derive the structural variation patterns H1t (1st mode) and H2t (2nd mode) of all nodes as:

where T denotes transpose. Finally, the pairwise node variation pattern similarities Ct ∈ Rn×n are computed by:

4.2 Temporal Graph Attention Network Learning

In this part, we incorporate the node variation pattern similarities for structure-based graph attention network embedding learning, where the inputs are node features Xt and node variation pattern similarities Ct for each single graph Gt. Assume Nvi = {vj ∈ Vt : ei,j ∈ Et} denotes the set of immediate neighborhoods of every node vi in graph Gt, the output embedding vector hvi ∈ Rh for vi is computed as:

where Xt,j ∈ Rd is the input features of node vj , Wt ∈ Rh×d is a shared weight transformation applied to each node in graph Gt, Ct,ij is the variation pattern similarity (e.g., till time step t) between vi and vj, and ReLU(·) is an activation function, i.e., ReLU(x) = max(0, x). αij indicates the attention weight or importance of node vj's features to node vi, which is computed with a single-layer Feedforward Neural Network (FNN) parameterized by a ∈ R2h :

where || is the concatenation operation. Note that αij has been normalized by a softmax over all neighborhoods of vi which makes αij ̸= αji. Similar to the GAT [Veliˇckovi´c et al., 2017], multi-head attentions can be computed and averaged to stabilize the node embedding learning by:

where K is the number of attention heads and Wkt ∈ Rh×d is a learnable weight parameter associated with the kth attention head for all nodes in graph Gt.

Based on Eq. (6), we can obtain the embedding space Ot = {hi}i=1,··· ,n ∈ Rn×h for each graph Gt ∈ G with preserved static graph structures (e.g., multi-head graph attentions) and temporal node structure variation patterns. Note that the FNN weight parameter a is shared across all graph snapshots, and the trainable weights associated with each single graph snapshot Gt are Wt = {Wkt }k=1,··· ,K which solely lead to varying attention values in Eq. (5) and node embeddings in Eq. (6) for graph snapshots at different time steps. Instead of learning Wt for each graph snapshot from scratch, we propose to evolve the weight learning by taking the structure discrepancies between adjacent graphs along the time axis into consideration.

Algorithm 1: Training the GAEN model

Input : Graph sequence G = {G1, · · · ,GT} and node variation patterns C = {C1, · · · , CT }

• Output: Embeddings of each graph Gt : Ot ∈ Rn×h 1 Initialize the number of attention heads K, multi-head attention weights W1 and training epoch I

4.3 Multi-HeadGraph AttentionWeight Evolution

As shown in Fig. 2, we use an independent Gated Recurrent Unit (GRU) to evolve the network weight Wkt ∈Wt for each graph attention head. The input is the adjacency matrix At for every graph snapshot Gt and the hidden state is Wkt which evolves between adjacent graph snapshots as:

The main idea for the design is to learn the structure difference of the current graph Gt against its previous graph Gt-1, thereby updating the attention network weights for Gt.

4.4 AlgorithmTraining and Explanation

To train the graph attention weight evolving and embedding learning modules, nodes are forced to have similar embedding with their neighborhoods for every single graph. Similar to [Sankar et al., 2019], the set of neighborhoods N t vi for each node vi in the graph at time t are obtained by performing fixed-length random walks on Gt, i.e., nodes within the same random walk are neighborhoods. Finally, we minimize the similarities between nodes with their neighbors (positive samples) through minimizing a binary cross-entropy loss:

where 〈·〉 represents the inner product, P tvi is a set of negative samples that are not neighbored with node vi, and β is set to balance the positive and negative samples.

The detailed training procedure of GAEN is summarized in Algorithm 1. The weight evolving process based on GRU (Eq. 7) is completed through lines 6 and 9, where Pk· ∈ Rh×n , Uk· ∈ Rh×h and Bk· ∈ Rh×d are learnable GRU weights for the kth graph attention head. The above process requires that the column dimension of the GRU input (At ∈ Rn×n ) matches the number of node features d. For graphs without content features, graph features can be viewed as a diagonal matrix where d equals to n. In other situations where d ̸= n, we introduce an additional learnable weight matrix PkA ∈ Rn×d to transform the input as:

5 Experiments

This section evaluates GANE using link prediction and node classification tasks based on the learned network embeddings.

Datasets. We adopt four temporal networks Enron [Klimt and Yang, 2004], UIC [Panzarasa et al., 2009], Primary School [Stehl´e et al., 2011] and DBLP 1 summarized in Table 1. Each dataset is composed of a set of temporal graph snapshots at multiple time steps. Enron and UIC are communication networks, where in Enron the communication links are email interactions between core employees and in UIC the links represent messages sent between online social users. Primary School represents the face-to-face contact networks, where the network at each time step was constructed from the interactions among students and teachers with an interval of 20 consecutive seconds. There are 10 student classes and 1 teacher class. DBLP represents co-author networks between authors from 5 research areas. The features are extracted from the titles and abstracts of authors' publications.

ComparedMethods. We compare against five strong baseline methods, including GCN [Kipf and Welling, 2017] and GAT [Veliˇckovi´c et al., 2017] that perform embedding learning on static graph snapshots, GAT-GRU which uses GAT to learn different snapshots with capturing the network dependencies based on GRU, EvolveGCN [Pareja et al., 2020]

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

which uses GCN to learn each single snapshot and meanwhile evolves weights between GCN networks based on the GRU, and DySAT [Sankar et al., 2019] which learns network embeddings by jointly employing self-attention layers along two dimensions: structural neighborhood and temporal dynamics. In addition, we develop a variant method GAENbasic without explicitly incorporating the pairwise node pattern similarities compared with GAEN.

Tasks and Experimental Setup. We evaluate the link prediction performance on all four datasets using Accuracy (Acc) and Area Under the Curve (AUC) metrics. We train an external logistic regression classifier to predict the existence of links at time t based on the embedding features learned from previous networks up to time t-1. We compare the node classification accuracy (Acc) on two datasets Primary School and DBLP as they have label information. Similarly, we train a logistic regression classifier to classify nodes into different categories based on embedding features learned from previous networks up to time t. For link prediction, 20% of the links are used as validation to fine-tune the hyper-parameters, and the remaining are split as 25% and 75% for training and test. For node classification, 20% of nodes are used for validation. Then, 30% and 70% of the remaining nodes are respectively used for training. To train the model, the number of attention heads is set as 8, the hidden dimension in GRU networks is set as 128 and the learning rate is set as 1e-4. For detailed parameter settings, please refer to the GitHub link 2 .

5.1 Link Prediction

Table 2 reports the latest time step link prediction performance of different methods. We conclude the following two main observations. 1) GAEN achieves better Acc and AUC performance than other methods on all four datasets. This is mainly attributed to two reasons: First, GAEN is efficient to capture the inter-dependency relationships between nodes across networks at different time steps, which can be observed from that GAENbasic generally performs better than other similar models, including DySAT, EvolveGCN and GAT-GRU. Second, GAEN performs better than GAENbasic in most cases, which indicates that the pairwise node pattern similarities explicitly preserved in GAEN are helpful to enhance the node relation modeling, i.e., Fig. 3 shows the visualization of node structure variation patterns and the respective node pattern similarities on primary school; 2) Compared with EvolveGCN that evolves the learning weights of GCN by considering the discrepancies of node features between adjacent graph snapshots, GAENbasic adopts GAT and evolves the GAT model weights by considering the discrepancies of node structures between adjacent graph snapshots. Table 2 shows that GAENbasic outperforms EvolveGCN, possibly because that graph snapshots are different in their topological structures and it is essential to learn their structural discrepancies while evolving the learning weights.

2 https://github.com/codeshareabc/GAEN

To further evaluate the three methods, EvolveGCN, GAENbasic, and GAEN, specifically designed to evolve the learning weights, we compared their link prediction performance at various time steps shown in Fig. 4. We can observe that GAENbasic performs better on Enron and demonstrates higher robustness on UIC when compared with EvolveGCN. In addition, GAEN is generally superior to GAENbasic, confirming the benefits of explicitly extracting and preserving the node pattern similarities in this paper.

5.2 Node Classification

Table 3 reports the node classification performance on the two labeled networks, where the node classification accuracy is much lower compared with the respective link prediction results in Table 2. This is because the compared methods are trained to force nodes to have similar embedding with their linked neighborhoods (e.g., Eq. 8), therefore the training scheme would bias the link prediction task. We can observe that GAEN outperforms all baseline methods, which asserts the benefits of preserving temporal node pattern similarities in the model. Similarly, the comparison results in Fig.5 demonstrate the effectiveness and robustness of GAEN for evolving graph attention networks.

6 Conclusion

Networked systems often work in evolving environments with changing network topology over time. It is beneficial to capture underlying dynamics for network learning, especially when the nodes in the evolution process demonstrate strong relevance to the change of network structures. In this paper, we advanced graph neural networks to explicitly incorporate node variation pattern similarities for enhanced node embedding learning. We proposed a novel framework with evolving graph attention networks across different time points, where a GRU network is used for progressive multihead attention weights learning by taking node structure differences between adjacent networks into consideration. Experiments and comparisons, using link prediction and node classification, demonstrated the effectiveness of the proposed approach against several baseline methods.

Acknowledgements

This research is sponsored by the US National Science Foundation through Grant Nos. IIS-2027339, IIS-1763452, CNS1828181, and OAC-2017597.