Node classification in dynamic networks using graph factorization

Methods and systems for detecting and responding to anomalous nodes in a network include inferring temporal factors, using a computer-implemented neural network, that represent changes in a network graph across time steps, with a temporal factor for each time step depending on a temporal factor for a previous time step. An invariant factor is inferred that represents information about the network graph that does not change across the time steps. The temporal factors and the invariant factor are combined into a combined temporal-invariant representation. It is determined that an unlabeled node is anomalous, based on the combined temporal-invariant representation. A security action is performed responsive to the determination that unlabeled node is anomalous.

BACKGROUND

Technical Field

The present invention relates to node classification, and, more particularly, to capturing the evolutionary patterns encoded by changing relationships and attributes in a dynamic network.

Description of the Related Art

The problem of classifying nodes in a dynamic network, node relationships and attributes can change over time, is challenging. Most existing approaches focus on static networks, and are unable to address networks that change over time, or cannot model the latent consistency in attributed temporal graphs. There are complex dynamics in the evolution of networks, as the temporal and spatial dimensions are entangled.

SUMMARY

A method for detecting and responding to anomalous nodes in a network includes inferring temporal factors, using a computer-implemented neural network, that represent changes in a network graph across time steps, with a temporal factor for each time step depending on a temporal factor for a previous time step. An invariant factor is inferred that represents information about the network graph that does not change across the time steps. The temporal factors and the invariant factor are combined into a combined temporal-invariant representation. It is determined that an unlabeled node is anomalous, based on the combined temporal-invariant representation. A security action is performed responsive to the determination that unlabeled node is anomalous.

A system for detecting and responding to anomalous nodes in a network includes a hardware processor and a memory. The memory is configured to store a temporal graph factorization network that is executed by the processor. The temporal graph factorization network is configured to infer temporal factors that represent changes in a network graph across a plurality of time steps, with a temporal factor for each time step depending on a temporal factor for a previous time step, to infer an invariant factor that represents information about the network graph that does not change across the plurality of time steps, to combine the temporal factors and the invariant factor into a combined temporal-invariant representation, and to determine that an unlabeled node is anomalous, based on the combined temporal-invariant representation. A security console is configured to perform a security action responsive to the determination that unlabeled node is anomalous.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

Embodiments of the present invention perform node classification, for example using attributed temporal graphs, to learn effective node embeddings that can fully capture the evolutionary patterns encoded by changing node relationships and attributes. A temporal graph factorization network (TGFN) is used as a latent factor model, to factorize dynamic node embeddings into two types of latent factors: a time-invariant factor that absorbs long-term consistency in the attributed temporal graph, and a sequence of temporal factors that capture node evolution. The sequence of temporal factors can use, for example, a deep Markovian model.

The distributions of all latent factors can be parameterized and inferred by a well-structured variational inference network. TGFN can reduce model complexity by specifically modeling the latent factors of node embeddings. In this manner, TGFN can generalize to scare training data, while achieving reasonable performance.

Referring now in detail to the figures in which like numerals represent the same or similar elements and initially toFIG.1, an exemplary network graph100is illustratively depicted in accordance with one embodiment of the present invention. The graph100captures the topological structure of a dynamic network of objects, represented as nodes104. As noted above, in some embodiments, such objects may represent physical objects in, e.g., a physical system. In some embodiments, the objects104may represent atoms or ions in a molecule. In yet other embodiments, the objects104may represent computing systems within a communications network. It should be understood that the illustrated graph is intended to be purely illustrative, and that the structure shown therein is not intended to be limiting in any way.

Edges106between the nodes104represent connections between the objects. For example, they may represent a chemical bond between two atoms, a structural connection between two physical objects, or a network communication between two computer systems. These connections develop and change over time, such that an edge106between two nodes104may disappear from one measurement to the next, while a new edge106may be formed between two different nodes106in the same interval.

Each node104in the network100includes one or more attributes or labels. These labels identify some characteristic of the node104. For example, in a complex molecule, individual atoms and ions may be labeled as contributing to a pharmacological effect of the molecule, with some nodes104being labeled as contributing, and other nodes104being labeled as not contributing. In a computer network environment, the nodes104may be labeled according to roles within the network (e.g., server vs workstation), or according to conformance to expected behavior (e.g., normal vs anomalous). The labels may include, for example, an attribute vector, denoting multiple attributes of the node respective104.

An initial set of edges106may be provided, for example in the form of a physical record, or may be inferred by pairwise regression of output data from pairs of objects104. Edges106can be weighted or unweighted, directed or undirected. However, label and edge information may not be available for every node104and for every attribute of every node104. Thus, some nodes102may be partially or entirely unlabeled at the outset.

The present embodiments identify the importance of different factors, such as neighboring nodes104, attributes, and topology, that influence the labels of a node. Topology and attribute information is adaptively selected for integration over the evolution of the graph100through time.

Given a sequence of attributed graphs100for a set of nodes104, where each node104has a unique class label over a period of time, the present embodiments predict the labels of unlabeled nodes102by learning from the labeled ones. In some embodiments, this can be used to detect anomalous network traffic. Given a network's historical records, a sequence of communication graphs can be constructed, where each node is a computational device and each edge indicates a communication. Each node can be associated with characteristic features, such as a network address (e.g., an IP address or MAC address) and a device type. The present embodiments can then classify the nodes into an anomalous class and a normal class, using the labeled historical data. The labeled network graph can then be used to identify anomalous behavior that may, for example, be indicative of a network failure or intrusion. The anomalous behavior can then be corrected.

In another application, brain graphs can be built to show the functional connectivity of widespread brain regions, by statistical analysis of fMRI and other signals. In a brain graph, each node indicates a particular region and each edge represents functional connectivity between two regions. To monitor the activity of the brain, a sequence of brain graphs can be constructed. In this context, node classification can be used to assign each node to a category of activity, such as language processing or sports. The brain graph can then be used to identify abnormalities in brain function, in preparation for surgery or treatment.

Referring now toFIG.2, a method of performing network classification, and taking an action responsive to that classification, is shown. Block202collects network information, including identifying available labels of the individual nodes104and identifying relationships between the nodes104. Using this information, block204builds a series of network graphs100that characterize the underlying network as it changes over time. Thus, for each time step t, block204builds a graph Gtthat represents the known node labels and relationships at that time.

Block206trains the TGFN, which is described in greater detail below. Training the TGFN206can be performed offline, prior to the analysis of a particular network. Alternatively, the TGFN can be trained parallel to the classification of the nodes in the network.

Block208uses the trained TGFN to perform classification for any unlabeled nodes102within the network100. These unlabeled nodes102are assigned labels across the evolution of the network100in time. Thus, for example, a particular node can be identified as being “anomalous.” Block210takes an action, based on the classification. In the example of identifying anomalous devices on a computer network, the action may include a security action that responds to anomalous activity. For example, the security action may include, e.g., shutting down devices, stopping or restricting certain types of network communication, raising alerts to system administrators, changing a security policy level, and so forth. The security action can include issuing commands to the other computer systems on the network.

Referring now toFIG.3, additional information is provided regarding the classification of block208. Block302performs neighborhood aggregation. At each time step t, a set of aggregator functions learns to aggregate feature information for each node's local neighborhood. For example, k-hop neighbors can be used to account for each node in a graph at t. This is performed across all time steps.

Given a batch of nodes0to be classified, and a graph snapshot Gt, for each node i in0, the features of i's neighbors are aggregated, up to k hops from i in Gt, for encoding local information. The k-hop neighbor batches are sampled for the nodes in0. First, the direct neighbors of each node i in0in G are sampled by a sampling function Nb(i). The sampled neighbors, together with the nodes in0, form a new set1. The same procedure is performed on1to obtain2, and is iteratively repeated untilkis obtained, which is a batch of all nodes within k hops of node i in G.

The sampling function Nb(i) can be any appropriate sampling function, but it is specifically contemplated that the sampling function may be a uniform sampling with a user-defined sample size S. Thus, Nb(i) may sample S neighbors of a node with equal probability.

Based on the node batches for each graph snapshot, an embedding vector xican be generated for each node I in the target batch0. For each node i in the last batchk, xiis initialized by the input feature of node i. Then, for each node i inκ−1, where κ=k−1, the following steps can be applied:
{tilde over (x)}i=NAGGκ({xj, ∀j∈Nb(j)})
xinew=ReLU(MLPκ([xi; {tilde over (x)}i])
where NAGGκ(⋅) is a neighbor-based aggregation function at the κthlayer (e.g., a max pooling over vectors xi), MLPκ(⋅) is a multi-layer perceptron at the κthlayer, and [⋅;⋅] is a concatenation operator. These steps are applied iteratively until κ decreases to zero, when the final embedding xi, encoding the k-hop neighbors in graph G, is obtained. The same procedure is performed over all time steps, for each node i in0, and a sequence of node embeddings for node I from time 1 to T can then be obtained.

To infer latent temporal factors in block304, a deep Markovian model can be used. Each temporal factor is conditioned on observation of the time-invariant factor at its current time step and the temporal factor at its previous time step, in accordance with Markov properties.

Block304therefore models the distribution p(zit|xit, zit−1), where zitis the temporal factor of node i at time t, and xitis an observation of the time-invariant factor zic. In some embodiments, the distribution can be modeled using recurrent neural networks (RNNs). RNNs are particularly appropriate, because the statistical dependency of ziton xitand zit−1inherently has a recurrent structure. A gated recurrent unit (GRU) can be used in particular, formulated by:
{tilde over (h)}it=GRUϕ{tilde over (h)}(xit, {tilde over (h)}it−1)∈dht×1
where {tilde over (h)}it(0<t<T) is the hidden state at time step t, dhtis the dimensionality, and ϕ{tilde over (h)}represents the parameters of the GRU.

To encode the latent temporal factor zitin the Markovian manner, a transition function is used to integrate zitand {tilde over (h)}itto form a single hidden representation hitas follows:
hit=0.5[tanh(MLPϕh(zit−1))+{tilde over (h)}it]∈dht×1
where ϕhis the parameter of the MLP. A simple weighting can be used to integrate the components from zitand {tilde over (h)}it.

After obtaining the hidden representation hit, a diagonal Gaussian distribution is used for modeling the distribution p(zit|xit, zit−1) as follows:
p(zit|xit, zit−1)=(μit, diag((σit)2))
where μit=MLPϕμ(hit)∈dzt×1, where log(σit)2=MLPϕσ(hit)∈dzt×1, and where ϕμand ϕσare parameters of the MLPs. The model parameter ϕ in the inference network for the temporal factor is then determined as ϕ={ϕ{tilde over (h)}, ϕh, ϕμ, ϕσ}.

Block306determines the time-invariant factor zic, which is conditioned on features of all time points in the graph, and captures the information that stays consistent over time. To encode the information in all node embeddings xi1, . . . , xiT, a neural network can be used to learn the hidden representation hicas:
hic=tanh(MLPθh([xi1; . . . ; xiT]))∈dhc×1
where dhcis the dimensionality of hic, and θhis the parameter of the MLP. Based on the hidden representation hic, a diagonal Gaussian can be used to model the distribution p(zic|{xit}) as follows:
pθ(zic|{xit})=(μic, diag((σic)2))
whereis a gaussian distribution having a mean μic=MLPθμ(hic)∈dzc×1and a variance diag((σic)2), where log(σic)2=MLP74σ(hic)∈dzc×1, where θμand θσrepresent the parameters of the MLPs, and where diag((σic)2) represents a diagonal matrix, with (σic)2on its diagonal. Following the above, the logarithm of (σic)2is modeled, rather than (σic)2itself, to avoid a non-negative constraint. As a result, the model parameter θ in the inference network for the time invariant factor is θ={θh, θμ, θσ}.

Block308classifies unlabeled nodes102, using a decoder function that predicts the distribution of the class label yifor each node I, based on its latent factors zicand zi1, . . . , ziT.

Given the sequence zi1, . . . , ziT, the amount of valuable information present differs from one time step to the next. It is likely that only a few sub-sequences contain the most discriminative information for determining the node labels. For example, in a sequence of brain graphs, where each node represents a small cube of brain tissue, the times when a subject is speaking will be more important than other periods of time to determining which nodes are related to language processing. As a result, the present embodiments can use an attentive temporal aggregator to automatically assign different levels of attention to different sub-sequences. The attention value αit, for each node i, at each time step t, can be expressed as:

αit=ewT⁢tanh⁢Vzit∑τ=1TewT⁢t⁢a⁢n⁢h⁢V⁢ziτ
where V and w are parameters and τ is the transpose operator.

The attention for a specific node i across all time steps can be expressed as αi=[αi1, . . . , αiT]. Extending the attentive mechanism to include multiple nodes helps to stabilize the learning process, and benefits the exploration of multiple sub-spaces. As a result, multiple sub-sequences together may describe the overall pattern. Therefore, if Zi=[zi1; . . . ; ziT] represents the temporal factors for a given node, the attentive temporal aggregator is expressed as:
hitpr=[Zi(αi1)τ; . . . ; Zi(αiM)τ]∈Mdzt×1
where αimrepresents the attention of the mthattention head (1<m<M), and M is the total number of heads in the aggregator.

The aggregated temporal representation hitprand the time-invariant factor zicare combined into a single representation:
hiout=tanh(MLPφh([hitpr; zic]))∈
where φhis the parameter of the MLP. In practice, a dropout layer can also be applied to the concatenated vector [hitpr; zic], to improve robustness.

The label yican be drawn from a categorical distribution p(yi|{zit}, zic), which is represented by p(yi|{zit}, zic)=Categorical(qi), where qi=softmax(MLPφy(hiout))∈L×1. In this expression, φyis the parameter of the MLP, and L is the number of classes to be assigned to node i. The model parameter of the classification network is then φ={w, V, φh, φy}. The categorical distribution Categorical(qi) may be defined as the probability function f(y|q)=Πj=1Lqj[y=j], where [y=j] evaluates to 1 if y=j, and is zero otherwise. With this probability function, labels y can be drawn as classes j with probability qi.

Looking back to block206, where the TGFN is trained, Y represents a label matrix, with Yijbeing assigned to a predetermined value (e.g., 1) if node i belongs to class j, and being assigned to a 0 otherwise. Q represents a matrix with rows qi, which are described in greater detail below with respect to the classification of nodes. The loss function for training the TGFN model can be expressed as:

ℓc=∑i∈vL∑j=1LYi⁢j⁢log⁢Qi⁢j
where lcis the cross-entropy error over all labeled nodes, L is the number of classes for a node, and νLis a subset of nodes whose labels are known and which can be accessed during model training.

To encourage multiple attention heads to diverge from one another, a regularization term can be used:a=∥AiAiτ−I∥2, where Ai=[(αi1)τ; . . . ; (αiM)τ]τand where I is the identity matrix. The final loss function for training the model then becomes=c+λa, where λ is a trade-off parameter. By optimizing the loss function on training data, the parameters of a neural network can be learned, and the entire model can be trained for maximum predictive power. The trained model can make predictions on node labels for new nodes in new graphs that have not been observed during training.

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 a large number of 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.

Referring now toFIG.4, a generalized diagram of a neural network is shown. 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 is known generally to have input neurons402that provide information to one or more “hidden” neurons404. Connections408between the input neurons402and hidden neurons404are weighted and these weighted inputs are then processed by the hidden neurons404according to some function in the hidden neurons404, with weighted connections408between the layers. There may be any number of layers of hidden neurons404, 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 neurons406accepts and processes weighted input from the last set of hidden neurons404.

This represents a “feed-forward” computation, where information propagates from input neurons402to the output neurons406. 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 neurons404and input neurons402receive information regarding the error propagating backward from the output neurons406. Once the backward error propagation has been completed, weight updates are performed, with the weighted connections408being updated to account for the received error. This represents just one variety of ANN.

Referring now toFIG.5, an exemplary ANN architecture500is 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, softmax 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 neurons502each provide an input signal in parallel to a respective row of weights504. The weights504each have a respective settable value, such that a weight output passes from the weight504to a respective hidden neuron506to represent the weighted input to the hidden neuron506. In software embodiments, the weights504may 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 neuron506.

The hidden neurons506use the signals from the array of weights504to perform some calculation. The hidden neurons506then output a signal of their own to another array of weights504. This array performs in the same way, with a column of weights504receiving a signal from their respective hidden neuron506to produce a weighted signal output that adds row-wise and is provided to the output neuron508.

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

During back propagation, the output neurons508provide a signal back across the array of weights504. 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 weights504receives a signal from a respective output neuron508in parallel and produces an output which adds column-wise to provide an input to hidden neurons506. The hidden neurons506combine 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 weights504. This back propagation travels through the entire network500until all hidden neurons506and the input neurons502have stored an error value.

During weight updates, the stored error values are used to update the settable values of the weights504. In this manner the weights504can be trained to adapt the neural network500to 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.

Referring now toFIG.6, a schematic of an exemplary TFGN is shown. The functions shown inFIG.3are generally shown in dashed boxes. Thus, neighborhood aggregation302begins with sampling function Nb(i)t, sampling node i in each time step t in parallel. A neighborhood aggregation function604is used on each set of sampled neighbor nodes to produce respective embeddings xitof the k-hop neighbors of node i at each time step.

Temporal factor inference304can use these embeddings as the input to respective RNNs, shown as GRUs608. The GRUs608generate a hidden state, which is used, in combination with a time factor zit−1from a previous time step to determine parameters610for modeling the temporal factors612. At the first time step t=1, the previous time factor is considered to be zero.

The outputs of the neighborhood aggregation302are also used for inferring the invariant factors616, with parameters614being determined to characterize the relevant MLPs.

The temporal factors612and the invariant factors616are both used as inputs to the classification network308. The temporal factors612are fed to attentive temporal aggregator618, which generates temporal representation hitpr. This temporal representation is combined with the time-invariant factor616as an input to a categorical function620. The categorical function produces a set of one or more labels622for each node i.

Referring now toFIG.7, a computer network security system700is shown. It should be understood that this system700represents just one application of the present principles, and that other uses for predicting the labels of nodes in a dynamic network are also contemplated. The system700includes a hardware processor702and a memory704. A network interface706communicates with one or more other systems on a computer network by, e.g., any appropriate wired or wireless communication medium and protocol.

A TGFN710can be implemented as described above, with one or more discrete neural network configurations being implemented to provide classifications for unlabeled nodes in the network. In some embodiments, the nodes may represent computer systems on a computer network, with some of the identities and functions of the computer systems being known in advance, while other systems may be unknown. The TGFN710identifies labels for these unknown systems.

Network monitor708thus receives information from the network interface706regarding the state of the network. This information may include, for example, network log information that tracks physically connections between systems, as well as communications between systems. The network log information can be received in an ongoing manner from the network interface and can be processed by the network monitor to identify changes in network topology (both physical and logical) and to collect information relating to the behavior of the systems.

A model trainer709uses training data, stored in memory704, to train the TGFN710. In some embodiments, the TGFN710can identify systems in the network that are operating normally, and also systems that are operating anomalously. For example, a system that is infected with malware, or that is being used as an intrusion point, may operate in a manner that is anomalous. This change can be detected as the network evolves, making it possible to identify and respond to security threats within the network.

A security console712manages this process. The security console712reviews information provided by the TGFN710, for example by identifying anomalous systems in the network, and triggers a security action in response. For example, the security console712may automatically trigger security management actions such as, e.g., shutting down devices, stopping or restricting certain types of network communication, raising alerts to system administrators, changing a security policy level, and so forth. The security console712may also accept instructions from a human operator to manually trigger certain security actions in view of analysis of the anomalous host. The security console712can therefore issue commands to the other computer systems on the network using the network interface706.

Referring now toFIG.8, an embodiment is shown that includes a network800of different computer systems802. The functioning of these computer systems802can correspond to the labels of nodes in a network graph that identifies the topology and the attributes of the computer systems802in the network. At least one anomalous computer system804can be identified using these labels, for example using the labels to identify normal operation and anomalous operation. In such an environment, the computer network security system600can identify and quickly address the anomalous behavior, stopping an intrusion event or correcting abnormal behavior, before such activity can spread to other computer systems.