Spatio temporal gated recurrent unit

Systems and methods for implementing a spatial and temporal attention-based gated recurrent unit (GRU) for node classification over temporal attributed graphs are provided. The method includes computing, using a GRU, embeddings of nodes at different snapshots. The method includes performing weighted sum pooling of neighborhood nodes for each node. The method further includes concatenating feature vectors for each node. Final temporal network embedding vectors are generated based on the feature vectors for each node. The method also includes applying a classification model based on the final temporal network embedding vectors to the plurality of nodes to determine temporal attributed graphs with classified nodes.

BACKGROUND

Technical Field

The present invention relates to node classification and more particularly to node classification in graph structured data.

Description of the Related Art

Attributed graphs are widely used in real-world applications. Many attributed graphs have been generated because of the rapid growth of information, such as brain graphs, post graphs and co-author graphs. Node classification over attributed graphs aims to classify the node into different categories according to its feature attributes and its connection with other nodes.

SUMMARY

According to an aspect of the present invention, a method is provided for implementing a spatial and temporal attention-based gated recurrent unit (GRU) for node classification over temporal attributed graphs. The method includes computing, using a GRU, embeddings of nodes at different snapshots. The method includes performing weighted sum pooling of neighborhood nodes for each node. The method further includes concatenating feature vectors for each node. Final temporal network embedding vectors are generated based on the feature vectors for each node. The method also includes applying a classification model based on the final temporal network embedding vectors to the plurality of nodes.

According to another aspect of the present invention, a system is provided for implementing a spatial and temporal attention-based gated recurrent unit (GRU) for node classification over temporal attributed graphs. The system includes a processor device operatively coupled to a memory device. The processor device is configured to compute, using a GRU, embeddings of nodes at different snapshots. The processor device performs weighted sum pooling of neighborhood nodes for each node. The processor device also concatenates feature vectors for each node. Final temporal network embedding vectors are generated based on the feature vectors for each node. The processor device applies a classification model based on the final temporal network embedding vectors to the plurality of nodes.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

In accordance with embodiments of the present invention, systems and methods are provided to/for implementing a spatial and temporal attention-based gated recurrent unit (GRU) network model (STAG) for node classification over temporal attributed graph. The systems model the spatio-temporal contextual information in a temporal attributed graph. The systems distinguish the time steps in the temporal attributed graph (for example, based on relative importance). The node neighbors of a node are used to extract the spatial representation for the node. The systems detect the relative influence of the node neighbors on the target node.

For example, with respect to brain graphs, the representation of one node at one time step is decided by its neighbors and previous time step representation. In the brain network, the neighbors will influence target node with attention weights. The weights are calculated with neighbors features and target node features. The weights can be used to represent the (for example, relative) importance of neighbors to the target node.

In one embodiment, the system learns a function to generate node representation on spatial aspect by sampling and aggregating features from a local neighborhood of the node. The system implements a GRU network to learn the node representation on temporal aspect and integrate the node representation on the temporal aspect with the representation from spatial aspect. The system can further implement a dual attention mechanism on both temporal aspect and spatial aspect to distinguish the (for example, relative) importance of time steps and the node neighbors that influence the node label. The two-attention calculation (dual attention mechanism) is directed towards calculating the importance of neighbors to the target node. The two-attention calculation is also directed towards calculating the importance of time step.

Referring now to the drawings in which like numerals represent the same or similar elements and initially toFIG. 1, a generalized diagram of a neural network that can implement device failure prediction from communication data is shown, according to an example embodiment.

An artificial neural network (ANN) is an information processing system that is inspired by biological nervous systems, such as the brain. The key element of ANNs is the structure of the information processing system, which includes many highly interconnected processing elements (called “neurons”) working in parallel to solve specific problems. ANNs are furthermore trained in-use, with learning that involves adjustments to weights that exist between the neurons. An ANN is configured for a specific application, such as pattern recognition or data classification, through such a learning process.

ANNs demonstrate an ability to derive meaning from complicated or imprecise data and can be used to extract patterns and detect trends that are too complex to be detected by humans or other computer-based systems. The structure of a neural network generally has input neurons102that provide information to one or more “hidden” neurons104. Connections108between the input neurons102and hidden neurons104are weighted and these weighted inputs are then processed by the hidden neurons104according to some function in the hidden neurons104, with weighted connections108between the layers. There can be any number of layers of hidden neurons104, and as well as neurons that perform different functions. There exist different neural network structures as well, such as convolutional neural network, maxout network, etc. Finally, a set of output neurons106accepts and processes weighted input from the last set of hidden neurons104.

This represents a “feed-forward” computation, where information propagates from input neurons102to the output neurons106. The training data (or, in some instances, testing data) can include data in various application areas, such as speech recognition and machine translation. The training data can be used for node classification in graph structured data as described herein below with respect toFIGS. 2 to 9. For example, the training data can be used in implementing a spatial and temporal attention-based gated recurrent unit network model, STAG, that can generate node representations by considering both the node's temporal pattern and its local neighborhoods of different time steps. The STAG network model can be used for node classification over temporal attributed graph.

The ANNs can be used to implement setting of temporal attributed graphs where each node has a consistent class label across different time steps and the node set is fixed. For example, the label of a company over a period of time, such as promising and unpromising. The graph in that instance can be a transaction graph between companies. The label characterizes the company performance over a period of time. At different time steps, the node attributes are different and the connection between nodes can change, for example, edge deletion or addition. The systems herein classify (for example, some) unknown nodes. The unknown nodes are not known beforehand. For example, to label each node can be time consuming and/or expensive. An administrator can select a few to be labeled by human experts and predict the remaining “unknown” nodes by processes implemented by the ANN to save time and/or expense.

Upon completion of a feed-forward computation, the output is compared to a desired output available from training data. The error relative to the training data is then processed in “feed-back” computation, where the hidden neurons104and input neurons102receive information regarding the error propagating backward from the output neurons106. Once the backward error propagation has been completed, weight updates are performed, with the weighted connections108being updated to account for the received error. This represents just one variety of ANN.

Referring now toFIG. 2, an artificial neural network (ANN) architecture200is shown. It should be understood that the present architecture is purely exemplary and that other architectures or types of neural network may be used instead. The ANN embodiment described herein is included with the intent of illustrating general principles of neural network computation at a high level of generality and should not be construed as limiting in any way.

Furthermore, the layers of neurons described below and the weights connecting them are described in a general manner and can be replaced by any type of neural network layers with any appropriate degree or type of interconnectivity. For example, layers can include convolutional layers, pooling layers, fully connected layers, stopmax layers, or any other appropriate type of neural network layer. Furthermore, layers can be added or removed as needed and the weights can be omitted for more complicated forms of interconnection.

During feed-forward operation, a set of input neurons202each provide an input signal in parallel to a respective row of weights204. In the hardware embodiment described herein, the weights204each have a respective settable value, such that a weight output passes from the weight204to a respective hidden neuron206to represent the weighted input to the hidden neuron206. In software embodiments, the weights204may simply be represented as coefficient values that are multiplied against the relevant signals. The signals from each weight adds column-wise and flows to a hidden neuron206.

The hidden neurons206use the signals from the array of weights204to perform some calculation. The hidden neurons206then output a signal of their own to another array of weights204. This array performs in the same way, with a column of weights204receiving a signal from their respective hidden neuron206to produce a weighted signal output that adds row-wise and is provided to the output neuron208.

It should be understood that any number of these stages may be implemented, by interposing additional layers of arrays and hidden neurons206. It should also be noted that some neurons may be constant neurons209, which provide a constant output to the array. The constant neurons209can be present among the input neurons202and/or hidden neurons206and are only used during feed-forward operation.

During back propagation, the output neurons208provide a signal back across the array of weights204. The output layer compares the generated network response to training data and computes an error. The error signal can be made proportional to the error value. In this example, a row of weights204receives a signal from a respective output neuron208in parallel and produces an output which adds column-wise to provide an input to hidden neurons206. The hidden neurons206combine the weighted feedback signal with a derivative of its feed-forward calculation and stores an error value before outputting a feedback signal to its respective column of weights204. This back-propagation travels through the entire network200until all hidden neurons206and the input neurons202have stored an error value.

During weight updates, the stored error values are used to update the settable values of the weights204. In this manner the weights204can be trained to adapt the neural network200to errors in its processing. It should be noted that the three modes of operation, feed forward, back propagation, and weight update, do not overlap with one another.

A recurrent neural network (RNN) is a class of artificial neural networks that can capture the temporal dependencies of sequential data and learn its representations. The RNN considers both the current data input and its hidden representation at the last time when generating the data's hidden representation at current time.

Gated recurrent unit (GRU) is a subclass of RNNs. The GRU is implemented in a similar manner to long short-term memory (LSTM) units. In contrast to LSTM that has a cell and three information flow gates, GRU simplifies the computation and only has two gates. As more layers using certain activation functions are added to neural networks, the gradients of the loss function approach zero, making the network hard to train (in other words, a vanishing gradient). As implemented within the STAG model, the GRU can reduce (or eliminate) vanishing gradients and capture long-term dependency, and can be used in various application areas, such as speech recognition and machine translation. The STAG network model can further consider the neighborhood information of the input data, such as described herein below with respect toFIGS. 3 to 9.

Referring now toFIG. 3, a block diagram illustrating temporal attributed graph node classification300, in accordance with example embodiments.

As shown inFIG. 3, each node (for example,315,320335) is one device, with attribute vector denoting the operating attributes of the device, the edge340of each graph denotes the communication between two devices. In another embodiment, each node (for example,315,320335) is one company, with attribute vector denoting the financial attributes of the company, the edge340of each graph denotes the transaction between two companies. The edge340is weighted and directed. G1(310), G2(350), G3(360), G4(370), . . . are the graphs for different time periods, such as January, February of2018, etc. The graphs can be generated for testing periods305and training periods355. The system300generates a sequence of attributed graphs and the labels325of each node. The label325is for the whole period of the corresponding node during the training period. The system300uses this information for training, and when given another sequence of attributed graphs with the same set of nodes (but different time periods), then predicts the labels of each node.

According to an example embodiment, the attributed graphs represent brain graphs, and each node (for example,315,320335) represents a cube of brain tissue called a voxel, the edge340indicates the connectivity between voxels and the node attributes include extra information about the voxel. Brain voxels can be classified into different categories according to their functionality: some are relevant to language processing; some are relevant to emotion processing; and some are relevant to human movement.

Referring now toFIG. 4, a block diagram illustrating a spatial and temporal attention-based gated recurrent unit network, in accordance with example embodiments.

As shown inFIG. 4, system400includes components for implementing an input sequence of attributed network data410, and node batches preparation420as described further in detail below with respect toFIG. 5, a GRU network430as described further in detail below with respect toFIG. 6, weighted sum pooling440as described further in detail below with respect toFIG. 7, concatenation of feature vectors450as described further in detail below with respect toFIG. 8, temporal network embedding vectors460as described further in detail below with respect toFIG. 9, and a classification model470. System400implements a spatial and temporal attention-based gated recurrent unit network model (STAG). STAG aims to generate node representations by considering both the node's temporal pattern and its local neighborhoods of different time steps.

According to an embodiment, to model the temporal behavior of the input node, the system400uses the GRU as a basic framework. The node feature attributes at different time steps are considered as the sequential data and are fed into GRU successively. Then, to generate the hidden representation of the input node at different time steps, the system400considers node attributes of the input node at that time step, its hidden representation at a previous time step and its local neighborhood at current time step. The local neighborhood is the aggregation of the node attributes of the node's neighbors. For example, with reference to back toFIG. 3, the local neighborhood of the node315is an aggregation of nodes320(within the inner circle of each graph). Moreover, the system400also implements a dual attention mechanism on both temporal and spatial aspects. Based on the temporal attention, the system400can automatically detect which time steps are more important when generating the node representations and put more emphasis on these time steps. Based on the spatial attention, the system400can put more emphasis on the neighbors that influence the node more.

The system400implements STAG for the node classification over temporal attributed graphs. The system400provides interpretable insights on both temporal and spatial aspects for node classification. The system400implements a GRU that can integrate the node attributes, its previous hidden representation and its local neighborhood to generate the representation at current time step. The system400can be used for any spatio-temporal applications where the relationships among objects evolves over time and the label is dependent on the temporal change of both attributes and topology. The system400can be implemented to address all these kinds of applications, for example, temporal graph node classification. The system400provides interpretability of results.

FIG. 5is a block diagram illustrating inputting a sequence of attributed network data and preparing node batches, in accordance with example embodiments.

As shown inFIG. 5, an input a sequence of attributed network data410, with node labels for 1-t snapshots. Snapshots (or the length of time between snapshots) can be determined at predetermined time instances based on instructions provided by an administrator or by calculating the rate of change of the data associated with the nodes. The network can be either direct505or undirected510. Each node of the network includes a feature vector515.

The system prepares node batches420based on the input sequence of attributed network data410. To consider the neighborhood information at each snapshot, the system400extracts a neighborhood vector for each node to represent its relation information with other nodes at each snapshot. The system400can aggregate the representations of the node's neighbors. To consider the representations of the neighbors' neighbors and even ‘deeper’ (for example, further out, at different degrees of connection) neighbors, the system400searches K depth neighbors. Given a set of input nodes B and the search depth K, the system400sample the neighbors of these nodes at each depth and construct a sequence of batches of nodes, BK. . . B0. BKis the input nodes, for example, BK=B. Bk-1is the union of Bkand some neighbors of the nodes in Bk. The neighbors are sampled by the sampling function N(.). The sampling process is described below. After constructing the batch sequence for each snapshot, the system400can generate the neighborhood vectors for all the nodes in B, which is described in the aggregation process herein below. Gk t(v) is the representation of node v during the k-th updating at the t-th snapshot.

The system implements a sampling process as follows:

The system implements an aggregation process as follows:

FIG. 6is a block diagram illustrating a GRU network, in accordance with example embodiments.

The system400calculates embeddings of nodes at different snapshots (520) (for example, using Eqn. 1, herein below). The embedding of a node is a vector of real values. The embedding will maintain the feature of the node for both features and their topology information. The calculation can consider both neighborhood nodes and previous snapshot's representation (525).

To integrate the node spatial information into GRU network430, the system400implements a spatiotemporal GRU (ST-GRU). For a ST-GRU unit, the inputs include the node attribute at current time, its hidden representation at last time and the vector representation of its neighborhoods. The outputs are the hidden representations of the node at different time steps. The system400implements the ST-GRU in a manner that: 1) the generated hidden representations explicitly contain both the temporal information of node attributes and the spatial information encoded in its neighborhoods; 2) a dual attention mechanism can be implemented on both temporal and spatial aspects. Given a sequence of node attributes of the same node at different time steps x1, . . . xT∈dand the vector representations of their neighborhoods e1, . . . , etin Rdg, a state vector ht∈dbis calculated for each node attribute by applying the following equations iteratively, where h0=0:
zt=σ(Wz[xt⊕ht-1]+bz),
rt=σ(Wr[xt⊕ht-1]+br),
{tilde over (h)}t=tanh(Wh[xt⊕(rt⊙ht-1)]+bh),
ht=(1−zt)⊙ht-1+zt⊙{tilde over (h)}t,  Eqn. (1).

Eq. (1) describes the calculation process of the three gates that determines which information to throw away and which information to keep when generating the hidden representation of nodes. Wz, Wr, Wh∈dh×(d+dh)and bz, br, bh∈dhare parameters. z′t, rt∈dhare update, reset, separately and their values are in the range of [0,1]. ⊕ denotes a concatenation operator, ⊙ denotes element-wise multiplication. The concatenation of all the state vectors [h1⊕ . . . ⊕hT] or the state vector at the last time hTcan be used as the hidden representation for the whole sequence. The system400considers the current node attributes xt, its previous hidden representation ht-1and the current neighborhood representation etwhen calculating the gates so that the current node representation is influenced by the node's current attributes, its previous representation and its neighborhoods.

FIG. 7is a block diagram illustrating weighted-sum pooling with attention network for one graph, in accordance with example embodiments.

Different neighbors influence the node differently. The neighbors that share more similarities with the node (for example, usually) influence the node more compared to other neighbors. Attention technique is capable of adaptively capturing the pertinent information. The system400implements a neighborhood attention module530to detect the important neighbors that influence each node more. The neighborhood attention module530can apply Eqns. 2 and 3 (shown herein below) to determine weighted-sum pooling neighborhood nodes. Based on the attention values, the aggregator sums up the neighbors' representations as follows.

Where Σβuk-1=1, and Vk∈dg×dgare parameters. βuk-1is the attention value for node u. Vkis the matrix of size dg, and dgis the dimension size of node embedding. V is a node and N(v) means all neighbors of node v. AGGkaggregates the neighbors' representations. The attention value indicates the importance of node u to node v compared to other neighbors at depth K−(k−1). βuk-1is produced by neighborhood attention module530that takes the representations of the node and its neighbors as inputs, which is described as follows:

where v′ in N(v). F(.) is an activation function.

FIG. 8is a block diagram illustrating weighted-sum pooling with attention network for one graph, in accordance with example embodiments.

The system400applies concatenation of feature vectors for each node540. The concatenation of all the state vectors is denoted as:
H=[h1⊕ . . . ⊕hT]∈T×dh.  Eqn. (4).

The temporal attention module550takes htas input and outputs an attention value for htas follows.

Thus, the attention values of all states can be denoted as
α=softmax(wTtanh(VHT))∈T.  Eqn. (6).

FIG. 9is a block diagram illustrating implementation of finalizing temporal network embedding vectors, in accordance with example embodiments.

System400generates final temporal network embedding vectors570. For example, system400sums up all the state vectors scaled by to generate a vector representation for the node shown as follows.
q=αTH∈dh.  Eqn. (7).

Herein, α represents attention values for all states, H is a concatenation of all state vectors, h is a state vector and d is the dimension of a final feature vector for each node. The feature vectors generated consider the temporal importance of attention weights560.

Referring now toFIG. 10, a method600for implementing a spatial and temporal attention-based gated recurrent unit for node classification over temporal attributed graphs is illustratively depicted in accordance with an embodiment of the present invention.

At block610, system400receives an input sequence of attributed network data with node labels. System400constructs a sequence of batches of nodes. For example, system400can search K depth neighbors, where K is a cardinal number greater than, for example, 2. Given a set of input nodes and the search depth K, the system400samples the neighbors of these nodes at each depth and construct a sequence of batches of nodes.

At block620, system400calculates embeddings of nodes at different snapshots. System400can implement processes to integrate the node spatial information into the GRU network430. The inputs to GRU network430include the node attribute at current time, its hidden representation at last time and the vector representation of its neighborhoods.

At block630, system400performs weighted sum pooling of neighborhood nodes. For example, system400can implement a neighborhood attention process to detect the important neighbors that influence the node more. Based on attention values, system400can apply an aggregator that sums up the neighbors' representations.

At block640, system400concatenates feature vectors for each node.

At block650, system400generates final temporal network embedding vectors. For example, system400can determine attention values and sum up all the state vectors scaled by α to generate a vector representation for the node.

At block660, system400applies the classification model to nodes. The nodes are classified according to its feature attributes and its connection with other nodes based on the model. For example, with respect to brain graphs, the representation of one node at one time step is decided by its neighbors and previous time step representation. In the brain network, the neighbors will influence target node with attention weights. The weights are calculated with neighbors features and target node features. The weights can be used to represent the (for example, relative) importance of neighbors to the target node.

A brain processing system can incorporate a spatial and temporal attention-based gated recurrent unit for node classification over temporal attributed graphs in accordance with an embodiment of the present invention.

The system receives temporal attributed brain graphs. The brain graphs can include nodes and edges, such as described with respect toFIG. 3, herein above. The temporal attributed brain graphs are input to node classification with a spatial and temporal attention-based gated recurrent unit (GRU) network model (STAG). Node classification over attributed graphs classifies each node into different categories according to its feature attributes and its connection with other nodes. Node classification with STAG determines brain graph with classified functionality. For example, in the brain graphs, a node represents a tidy cube of brain tissue called a voxel, the edge indicates the connectivity between voxels and the node attributes include extra information about the voxel. Brain voxels can be classified into different categories according to their functionality: some are relevant to language processing, some are relevant to emotion processing and some are relevant to human movement. These different brain processing input (data) can be input to brain graph with classified functionality.

Node classification with STAG determines the category of some unknown nodes and determines the underlying functionality of these unknown nodes and their role when interacting with others. With regard to brain graphs representation of the brain, brain consists of voxels. The connectivity between two brain voxels may change when the subject changes into a different task, which results in the edge deletion or addition on brain graphs. Moreover, the node attributes may change over time. For example, the neuron activities within a brain voxel during the periods of different tasks are different.

At different time steps, the node attributes are different and the connection between nodes might change, for example, edge deletion or addition. Node classification with STAG classifies unknown nodes. Node classification with STAG learns the node feature representations on spatial and temporal aspects simultaneously and integrates them into the brain graphs. For the temporal attributed graphs, Node classification with STAG determines the evolution over both spatial and temporal aspects, which are entangled together. Node classification with STAG distinguishes the importance of different time steps for extracting node representation. Different time steps play the different important roles for the nodes and distinguishing the difference helps extract better (for example, more accurate) node representation. When extracting the representation of the target node, node neighbors of the target node are utilized. Different neighbors influence the target node differently. Node classification with STAG detects the node neighbors that influence the representation of the target node to varying degrees to generate more accurate node representation.

The system can be applied to brain function processing and analysis, such as auditory processing, language processing, emotion processing, body movement, etc. The nodes (for example, brain voxels) can be classified based on their underlying functionality and role when interacting with other nodes.