# US 2021/0067527 A1 · Structural graph neural networks for suspicious event detection

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0067527 A1
- Document ID: US20210067527A1
- Status: Published application
- Kind: A1
- Application number: 16/992,395
- Filed: 2020-08-13
- Published: 2021-03-04
- Earliest claimed: 2019-08-28
- Assignees: NEC Laboratories America, Inc.
- Applicants: NEC Laboratories America, Inc.
- Inventors: Zhengzhang Chen; Jiaping Gui; Haifeng Chen; Lei Cai
- Web page: https://patentgrep.com/patent/US20210067527A1

## CPC

- H04L 63/1416: {Event detection, e.g. attack signature detection}
- H04L 63/1425: {Traffic logging, e.g. anomaly detection}
- G06N 3/044: Recurrent networks, e.g. Hopfield networks
- G06N 3/0442: characterised by memory or gating, e.g. long short-term memory [LSTM] or gated recurrent units [GRU]
- G06N 3/0464: Convolutional networks [CNN, ConvNet]
- G06N 3/08: Learning methods
- G06N 3/088: Non-supervised learning, e.g. competitive learning
- G06N 3/09: Supervised learning
- G06N 3/045: Combinations of networks
- H04L 2463/121: Timestamp
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## 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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, 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.

### Claim 3 (depends on 2)

The computer-implemented method of claim 2, 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.

### Claim 4 (depends on 2)

The computer-implemented method of claim 2, 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.

### Claim 5 (depends on 2)

The computer-implemented method of claim 2, 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.

### Claim 6 (depends on 2)

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

### Claim 7 (depends on 2)

The computer-implemented method of claim 2, 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.

### Claim 8 (depends on 7)

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

### Claim 9 (depends on 2)

The computer-implemented method of claim 2, 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.

### Claim 10 (depends on 1)

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.

### Claim 11 (depends on 1)

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.

### Claim 12 (depends on 1)

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.

### Claim 13 (depends on 1)

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

### Claim 14 (depends on 1)

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

### Claim 15

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.

### Claim 16 (depends on 15)

The computer program product of claim 15, 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.

### Claim 17 (depends on 16)

The computer program product of claim 16, 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.

### Claim 18 (depends on 16)

The computer program product of claim 16, 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.

### Claim 19 (depends on 16)

The computer program product of claim 16, 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.

### Claim 20

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.
