Structural graph neural networks for suspicious event detection

Patent metadata

Field	Value
Publication number	US-11522881-B2
Application number	US-202016992395-A
Country	US
Kind code	B2
Filing date	Aug 13, 2020
Priority date	Aug 28, 2019
Publication date	Dec 6, 2022
Grant date	Dec 6, 2022

Abstract

A computer-implemented method for graph structure based anomaly detection on a dynamic graph is provided. The method includes detecting anomalous edges in the dynamic graph by learning graph structure changes in the dynamic graph with respect to target edges to be evaluated in a given time window repeatedly applied to the dynamic graph. The target edges correspond to particular different timestamps. The method further includes predicting a category of each of the target edges as being one of anomalous and non-anomalous based on the graph structure changes. The method also includes controlling a hardware based device to avoid an impending failure responsive to the category of at least one of the target edges.

First claim

What is claimed is:

1. A computer-implemented method for graph structure based anomaly detection on a dynamic graph, comprising:
detecting anomalous edges in the dynamic graph by learning graph structure changes in the dynamic graph with respect to target edges to be evaluated in a given time window repeatedly applied to the dynamic graph, the target edges corresponding to particular different timestamps;
predicting a category of each of the target edges as being one of anomalous and non-anomalous based on the graph structure changes; and
controlling a hardware based device to avoid an impending failure responsive to the category of at least one of the target edges,
wherein said detecting step comprises performing subgraph generation on the dynamic graph to obtain a set of subgraphs having node role labels assigned to nodes of the subgraphs to indicate a respective node role thereof, and performing, responsive to the node role labels, graph structural feature extraction to learn a feature embedding of each of the nodes of the subgraphs to obtain a set of node feature embeddings, wherein the graph structure feature extraction is performed using a graph convolutional neural network that learns the node feature embeddings of each of the nodes of the subgraphs and aggregates the node feature embeddings from neighboring h-hop nodes from among the nodes in the subgraphs, and wherein an aggregation of the node feature embeddings is used to predict the category of each of the target edges in said predicting step.

2. The computer-implemented method of claim 1 , wherein said detecting step further comprises modeling temporal information of the set of node feature embeddings using a Gated Recurrent Unit (GRU) to form a classifier that predicts the category of each of the target edges.

3. The computer-implemented method of claim 1 , wherein the set of subgraphs comprise a set of h-hop subgraphs, each of the h-hop subgraphs being centered on a respective one of the target edges.

4. The computer-implemented method of claim 1 , wherein the node role labels represent structure information for the nodes in the subgraphs.

5. The computer-implemented method of claim 1 , wherein the node role labels indicate which one of the nodes of the subgraphs the node role labels belong and also indicate a contribution of the nodes of the subgraphs in identifying the category of each of the target edges.

6. The computer-implemented method of claim 5 , wherein the node role labels are converted into one-hot vectors for each of the nodes of the subgraphs.

7. The computer-implemented method of claim 1 , further comprising fixing a feature size of features extracted from the subgraphs based on a feature importance in determining the category of each of the target edges.

8. The computer-implemented method of claim 1 , wherein the dynamic graph is a historical dynamic graph comprising historical data values up to a current timestamp, and wherein the method furthering comprising capturing, using one or more recurrent neural networks, temporal features from the historical data values, the temporal features used to predict the category of each of the target edges.

9. The computer-implemented method of claim 1 , wherein the method furthering comprises inputting a graph structure feature from a current timestamp and temporal feature from a previous timestamp into a current neural network to generate a temporal feature for a given one of the target edges.

10. The computer-implemented method of claim 1 , wherein the dynamic graph is a time-evolving dynamic graph comprising time-evolving data values for a current timestamp.

11. The computer-implemented method of claim 1 , wherein said detecting step detects unusual subgraph structures in the time window in consideration of temporal dependency.

12. The computer-implemented method of claim 1 , wherein the category of anomalous represents a network attack.

13. A computer program product for graph structure based anomaly detection on a dynamic graph, the computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to perform a method comprising:
detecting anomalous edges in the dynamic graph by learning graph structure changes in the dynamic graph with respect to target edges to be evaluated in a given time window repeatedly applied to the dynamic graph, the target edges corresponding to particular different timestamps;
predicting a category of each of the target edges as being one of anomalous and non-anomalous based on the graph structure changes; and
controlling a hardware based device to avoid an impending failure responsive to the category of at least one of the target edges,
wherein said detecting step comprises performing subgraph generation on the dynamic graph to obtain a set of subgraphs having node role labels assigned to nodes of the subgraphs to indicate a respective node role thereof, and performing, responsive to the node role labels, graph structural feature extraction to learn a feature embedding of each of the nodes of the subgraphs to obtain a set of node feature embeddings, wherein the graph structure feature extraction is performed using a graph convolutional neural network that learns the node feature embeddings of each of the nodes of the subgraphs and aggregates the node feature embeddings from neighboring h-hop nodes from among the nodes in the subgraphs, and wherein an aggregation of the node feature embeddings is used to predict the category of each of the target edges in said predicting step.

14. The computer program product of claim 13 , wherein said detecting step further comprises modeling temporal information of the set of node feature embeddings using a Gated Recurrent Unit (GRU) to form a classifier that predicts the category of each of the target edges.

15. The computer program product of claim 13 , wherein the set of subgraphs comprise a set of h-hop subgraphs, each of the h-hop subgraphs being centered on a respective one of the target edges.

16. A computer processing system for graph structure based anomaly detection on a dynamic graph, comprising:
a memory configured to store program code; and
a hardware processor operatively coupled to the memory for running the program code to:
detect anomalous edges in the dynamic graph by learning graph structure changes in the dynamic graph with respect to target edges to be evaluated in a given time window repeatedly applied to the dynamic graph, the target edges corresponding to particular different timestamps;
predict a category of each of the target edges as being one of anomalous and non-anomalous based on the graph structure changes; and
control a hardware based device to avoid an impending failure responsive to the category of at least one of the target edges,

wherein detecting the anomalous edges comprises performing subgraph generation on the dynamic graph to obtain a set of subgraphs having node role labels assigned to nodes of the subgraphs to indicate a respective node role thereof, and performing, responsive to the node role labels, graph structural feature extraction to learn a feature embedding of each of the nodes of the subgraphs to obtain a set of node feature embeddings, wherein the graph structure feature extraction is performed using a graph convolutional neural network that learns the node feature embeddings of each of the nodes of the subgraphs and aggregates the node feature embeddings from neighboring h-hop nodes from among the nodes in the subgraphs, an

Assignees

• Nec Lab America Inc
• Nec Corp

Inventors

• Chen Zhengzhang
• Gui Jiaping
• Chen Haifeng
• Cai Lei

Classifications

• G06N3/045

  Combinations of networks · CPC title

• G06N3/044

  Recurrent networks, e.g. Hopfield networks · CPC title

• H04L63/1425 Primary

  Traffic logging, e.g. anomaly detection · CPC title

• G06N3/088

  Non-supervised learning, e.g. competitive learning · CPC title

• G06N3/08

  Learning methods · CPC title