# US 2024/0176990 A1 · Method and System for Graph-to-graph Prediction Based on Recurrent Neural Network

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

- Number: US 2024/0176990 A1
- Document ID: US20240176990A1
- Status: Published application
- Kind: A1
- Application number: 18/479,474
- Filed: 2023-10-02
- Published: 2024-05-30
- Earliest claimed: 2022-11-29
- Assignees: Yangtze Delta Region Institute (Huzhou), University of Electronic Science and Technology of China
- Applicants: Yangtze Delta Region Institute (Huzhou), University of Electronic Science and Technology of China
- Inventors: Guan WANG
- Web page: https://patentgrep.com/patent/US20240176990A1

## CPC

- G06N 3/0455: Auto-encoder networks; Encoder-decoder networks
- G06N 3/044: Recurrent networks, e.g. Hopfield networks
- G06N 3/045: Combinations of networks
- G06N 3/08: Learning methods
- G06N 3/0985: Hyperparameter optimisation; Meta-learning; Learning-to-learn
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

The present disclosure discloses a method and system for graph-to-graph prediction based on recurrent neural networks. The method includes: representing a graph structure as a sequence; based on the sequentialization representation of the graph structure, constructing a deep neural network model for graph-to-graph prediction, wherein both input and output of the deep neural network model are graph structures; the deep neural network model includes an Encoder and a Decoder, wherein, in the Encoder, employing encNodeRNN and encEdgeRNN in combination to encode an input graph, and the Decoder decodes based on an encoding vector obtained from the Encoder, thereby obtaining a corresponding predicted graph and realizing the graph-to-graph prediction.

## Claims

### Claim 1

A graph-to-graph prediction method, comprising:
representing a graph structure as a sequence;
based on a sequentialization representation of the graph structure, constructing a deep neural network model for a graph-to-graph prediction, wherein both input and output of the deep neural network model are graph structures;
the deep neural network model comprising an Encoder and a Decoder, wherein, in the Encoder, employing encNodeRNN and encEdgeRNN in combination to encode an input graph, and the Decoder decodes based on an encoding vector obtained from the Encoder, thereby obtaining a corresponding prediction graph and realizing the graph-to-graph prediction.

### Claim 2 (depends on 1)

The graph-to-graph prediction method of claim 1, comprising the following steps:
step one: performing the sequentialization representation of the graph structure;
step two: constructing a network model based on the sequentialization representation of the graph structure;
step three: performing the graph-to-graph prediction using a constructed network model.

### Claim 3 (depends on 2)

The graph-to-graph prediction method of claim 2, wherein, in step one, the sequentialization representation of the graph structure comprises: data to be processed is a set of undirected graph data G={V,E}, where V represents a set of all nodes in the graph, and E represents a set of all edges between all nodes; denoting A as an adjacency matrix of G, the graph G is represented as a sequence of adjacency vectors {X1, X2, . . . , Xn}, where Xi=(Ai,i-1, Ai,i-2, . . . , Ai,1) encodes a connection relationship between node vi and its previous nodes {vi-1, vi-2, . . . , v1}; based on the sequentialization representation of the graph structure, the graph G is converted into a nested sequence.

### Claim 4 (depends on 2)

The graph-to-graph prediction method of claim 2, wherein, in step two, the deep neural network model constructed based on the sequentialization representation of the graph structure comprises the Encoder and the Decoder,
wherein the Encoder is used to extract high-level semantic information from the input graph, representing the input graph as two-dimensional sequence information and using a recurrent neural network for encoding, wherein graph information is encoded by two layers of recurrent neural networks, which comprise the encEdgeRNN for encoding edge information and the encNodeRNN for encoding node information,
wherein the encEdgeRNN sequentially reads elements from Xi,1 to Xi,i-1 in Xi, denoted as gedge; using GRU, gedge generates a series of hidden state sequences (hi,1edge, hi,2edge, . . . , hi,i-1edge), where hi,1edge is taken as the encoding of the sequence from Xi,1 to Xi,i-1, denoted as χi, and is input into encNodeRNN, and
wherein the encNodeRNN encodes all the encoding sequences (χ1, χ2, . . . , χn) generated by the encEdgeRNN, thereby generating a final encoding of the graph G, denoted as C.

### Claim 5 (depends on 4)

The graph-to-graph prediction method of claim 4, wherein, after the input graph G is encoded to obtain C, the Decoder decodes C according to a specific task to obtain a corresponding output graph;
the Encoder defines a probability distribution p(Y), where Y=(Y0, Y1, . . . , Ym-1) is an adjacency vector sequence obtained by the Decoder; p(Y) is decomposed into a product of a series of conditional distributions:
p(Y)=Πi=0mp(Yi|Y0,Y1, . . . ,Yi-1,C);
where m represents the number of nodes in the prediction graph to be generated, and C is the graph encoding obtained by the Encoder; simplifying p(Yi|Y0, Y1, . . . , Yi-1, C) as P(Yi|Y<i, C), then P(Yi|Y<i, C) is decomposed into:
p(Yi|Y<i,C)=Πk=0i-1p(Yi,k|Yi,<k,c;Y<i,C);
where c is the encoding generated when predicting Yi,k;
using two cascading RNNs, the decNodeRNN is responsible for transferring the information of the generated graph from the i−1th node to the ith node, thereby generating a new node; while the decEdgeRNN is responsible for generating the edges between the ith node and its previous nodes in an autoregressive manner.

### Claim 6 (depends on 2)

The graph-to-graph prediction method of claim 2, wherein, a definition of a loss function of the model in step two comprises:
for a sequentialization representation X of a given input graph and a corresponding true output graph Y, in the model M, a loss value between the predicted edge and the true edge between the ith node and the jth node is li,j=−(1−pijt)γ log(pi,jt), where pijt represents a likelihood of correct prediction, and γ is a hyperparameter for adjustment, set as γ=2;
a final model prediction loss function is (X),Y)=where varies depending on the actual problem being solved, and for a maximum clique computation problem, ∀a∈, Xa=1.

### Claim 7 (depends on 1)

A graph-to-graph prediction system for implementing the graph-to-graph prediction method of claim 1, comprising:
a graph structure sequentialization representation module for representing a graph structure as a sequence;
a deep neural network model construction module for constructing a deep neural network model for a graph-to-graph prediction, wherein both input and output of the deep neural network model are graph structures;
a graph structure encoding module for encoding an input graph at the encoder of the deep neural network model using encNodeRNN and encEdgeRNN in combination;
an encoding vector decoding module for decoding based on an encoding vector obtained from the Encoder to obtain a corresponding predicted graph, thereby realizing the graph-to-graph prediction.

### Claim 8 (depends on 1)

A computing device, wherein, the computing device comprises a memory and a processor, and the memory stores a computer program which, when executed by the processor, causes the processor to perform the steps of the graph-to-graph prediction method of claim 1.

### Claim 9 (depends on 1)

A computer-readable storage medium storing a computer program which, when executed by a processor, causes the processor to perform the steps of the graph-to-graph prediction method of claim 1.

### Claim 10 (depends on 7)

An information data processing terminal, wherein, the information data processing terminal is used to implement the graph-to-graph prediction system of claim 7.
