Deep neural network system for similarity-based graph representations

Patent metadata

Field	Value
Publication number	US-11983269-B2
Application number	US-202218087704-A
Country	US
Kind code	B2
Filing date	Dec 22, 2022
Priority date	May 18, 2018
Publication date	May 14, 2024
Grant date	May 14, 2024

Abstract

There is described a neural network system implemented by one or more computers for determining graph similarity. The neural network system comprises one or more neural networks configured to process an input graph to generate a node state representation vector for each node of the input graph and an edge representation vector for each edge of the input graph; and process the node state representation vectors and the edge representation vectors to generate a vector representation of the input graph. The neural network system further comprises one or more processors configured to: receive a first graph; receive a second graph; generate a vector representation of the first graph; generate a vector representation of the second graph; determine a similarity score for the first graph and the second graph based upon the vector representations of the first graph and the second graph.

First claim

What is claimed is:

1. A method performed by one or more computers, the method comprising:
receiving an input graph comprising a plurality of input nodes and a plurality of input edges;
receiving a context graph comprising a plurality of context nodes and a plurality of context edges;
processing the input graph using a graph neural network to generate a node state representation vector for each input node of the input graph and an edge representation vector for each input edge of the input graph, comprising:
initializing the node state representation vectors and the edge representation vectors;
updating the node state representation vectors and the edge representation vectors, comprising, for a particular node:
performing message passing to generate a respective message vector for each of one or more adjacent nodes in the input graph to the particular input node;
generating a cross-graph matching vector based upon a similarity between the particular input node of the input graph and one or more context nodes of the context graph; and
updating the node state representation vector for the particular input node using the respective message vectors and the cross-graph matching vector; and

processing (i) the node state representation vectors, (ii) the edge representation vectors, or (iii) both to generate a prediction for the input graph.

2. The method of claim 1 , wherein processing (i) the node state representation vectors, (ii) the edge representation vectors, or (iii) both to generate a prediction for the input graph comprises:
generating a vector representation of the input graph from (i) the node state representation vectors, (ii) the edge representation vectors, or (iii) both; and
generating the prediction for the input graph from the vector representation.

3. The method of claim 2 , wherein generating the prediction for the input graph from the vector representation comprises:
generating a vector representation of a second input graph; and
generating a similarity score from the vector representation of the input graph and the vector representation of the second input graph that measures a similarity between the input graph and the second input graph.

4. The method of claim 1 , wherein the similarity between the particular node of the input graph and the one or more context nodes of the context graph is based upon a difference between a node state representation vector associated with the particular node of the input graph and a weighted sum of node state representation vectors associated with each of the one or more context nodes of the context graph.

5. The method of claim 4 , wherein the weighted sum is a weighted sum of respective node state representation vectors associated with each of the context nodes of the context graph.

6. The method of claim 4 , wherein the weight for each respective context node of the one or more context nodes of the context input graph is based upon a similarity score between the node state representation vector associated with the particular node of the input graph and the respective node state representation vector associated with the respective context node of the context graph.

7. The method of claim 1 , wherein the graph neural network comprises:
an encoder neural network subsystem configured to process the input graph to initialize the node state representation vector for each node of the input graph and the edge representation vector for each edge of the input graph;
a propagation neural network subsystem configured to update the node state representation vectors and the edge representation vectors by performing message passing; and
an aggregator neural network subsystem configured to process the node state representation vectors associated with each node of the input graph to generate a vector representation of the input graph.

8. The method of claim 7 , wherein the encoder neural network subsystem comprises:
a node encoder neural network configured to generate the node state representation vector for each node of the input graph; and
an edge encoder neural network configured to generate the edge representation vector for each edge of the input graph.

9. The method of claim 7 , wherein the aggregator neural network subsystem comprises an aggregator neural network configured to process the node state representation vectors for the nodes to generate a respective transformed vector associated with each of the nodes; and wherein the vector representation of the input graph is based upon a summation of the respective transformed vectors associated with each of the nodes of the input graph.

10. A system comprising one or more computers and one or more storage devices storing instructions that when executed by the one or more computers cause the one or more computers to perform operations comprising:
receiving an input graph comprising a plurality of input nodes and a plurality of input edges;
receiving a context graph comprising a plurality of context nodes and a plurality of context edges;
processing the input graph using a graph neural network to generate a node state representation vector for each input node of the input graph and an edge representation vector for each input edge of the input graph, comprising:
initializing the node state representation vectors and the edge representation vectors;
updating the node state representation vectors and the edge representation vectors, comprising, for a particular node:
performing message passing to generate a respective message vector for each of one or more adjacent nodes in the input graph to the particular input node;
generating a cross-graph matching vector based upon a similarity between the particular input node of the input graph and one or more context nodes of the context graph; and
updating the node state representation vector for the particular input node using the respective message vectors and the cross-graph matching vector; and

processing (i) the node state representation vectors, (ii) the edge representation vectors, or (iii) both to generate a prediction for the input graph.

11. The system of claim 10 , wherein processing (i) the node state representation vectors, (ii) the edge representation vectors, or (iii) both to generate a prediction for the input graph comprises:
generating a vector representation of the input graph from (i) the node state representation vectors, (ii) the edge representation vectors, or (iii) both; and
generating the prediction for the input graph from the vector representation.

12. The system of claim 11 , wherein generating the prediction for the input graph from the vector representation comprises:
generating a vector representation of a second input graph; and
generating a similarity score from the vector representation of the input graph and the vector representation of the second input graph that measures a similarity between the input graph and the second input graph.

13. The system of claim 10 , wherein the similarity between the particular node of the input graph and the one or more context nodes of the context graph is based upon a difference between a node state representation vector associated with the particular node of the input graph and a weighted sum of node state representation vectors associated with each of the one or more context nodes of the context graph.

14. The system of claim 13 , wherein the weighted sum is a weighted sum of respective node state representation vectors associated with each of the context nodes of the context graph.

15. The system of claim 13 , wherein the weight for each respective context node of the one or m

Assignees

• Deepmind Tech Ltd

Inventors

• Li Yujia
• Gu Chenjie
• Dullien Thomas
• Vinyals Oriol
• Kohli Pushmeet

Classifications

• G06N3/08

  Learning methods · CPC title

• G06N3/0442

  characterised by memory or gating, e.g. long short-term memory [LSTM] or gated recurrent units [GRU] · CPC title

• G06N3/0455

  Auto-encoder networks; Encoder-decoder networks · CPC title

• G06N3/09

  Supervised learning · CPC title

• G06F21/563 Primary

  by source code analysis · CPC title