Deep neural network system for similarity-based graph representations

Patent metadata

Field	Value
Publication number	US-11537719-B2
Application number	US-201916416070-A
Country	US
Kind code	B2
Filing date	May 17, 2019
Priority date	May 18, 2018
Publication date	Dec 27, 2022
Grant date	Dec 27, 2022

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 neural network system implemented by one or more computers for determining graph similarity, the neural network system comprising:
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;
one or more processors configured to:
receive a first graph;
receive a second graph;
generate a vector representation of the first graph using the one or more neural networks;
generate a vector representation of the second graph using the one or more neural networks;
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, wherein the one or more neural networks are configured to process a pair of input graphs to generate a vector representation of each input graph of the pair of input graphs, the vector representation of each input graph being based upon both input graphs of the pair of graphs; and wherein

the vector representation of the first graph and the vector representation of the second graph are generated based upon inputting the first graph and the second graph as a pair of input graphs to the one or more neural networks.

2. The system of claim 1 , wherein the one or more neural networks comprises:
an encoder neural network subsystem configured to process an input graph to generate 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 vector associated with a particular node of the input graph based upon the node state representation vectors associated with one or more adjacent nodes in the input graph and the edge representation vectors associated with the edges connecting the particular node to the one or more adjacent nodes in the input graph;
an aggregator neural network subsystem configured to process the node state representation vectors associated with each node of the input graph to generate the vector representation of the input graph.

3. The system of claim 2 , wherein the encoder neural network subsystem comprises:
a node encoder neural network configured to generate the node state representation vector; and
an edge encoder neural network configured to generate the edge representation vector.

4. The system of claim 3 , wherein the node encoder neural network comprises a plurality of hidden layers and an output layer; and the node state representation vector comprises a plurality of node state representation vectors for each node of the input graph comprising a vector corresponding to each of the plurality of hidden layers and the output layer.

5. The system of claim 2 , wherein the propagation neural network subsystem comprises:
a message generation neural network configured to process the node state representation vector associated with a particular node and the node state representation vector associated with an adjacent node in the input graph and the edge representation vector associated with the edge connecting the particular node and the adjacent node to generate a message vector associated with the adjacent node in the input graph; and
a node update neural network configured to generate an updated node state representation vector associated with the particular node based upon the current node state representation vector associated with the particular node and message vectors generated for each adjacent node adjacent the particular node in the input graph.

6. The system of claim 5 , wherein the node update neural network is further configured to process a summation of the message vectors generated for each adjacent node adjacent the particular node in the input graph to generate the updated node state representation vector.

7. The system of claim 6 , wherein the summation is a weighted sum or an attention-based weighted sum.

8. The system of claim 5 , wherein the node update neural network is a recurrent type of neural network.

9. The system of claim 5 , wherein the propagation neural network subsystem is further configured to generate a cross-graph matching vector based upon a similarity between a particular node of the input graph and one or more nodes of a second input graph; and
wherein the node update neural network is further configured to generate an updated node state representation vector associated with the particular node based upon the current node state representation vector associated with the particular node, the message vectors generated for each adjacent node adjacent the particular node in the input graph, and the cross-graph matching vector.

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

11. The system of claim 10 , wherein the weighted sum is a weighted sum of all of the node state representation vectors associated with each of the nodes of the second input graph.

12. The system of claim 11 , wherein the weight for each respective node of the one or more nodes of the second 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 node state representation vector associated with the respective node of the second input graph.

13. The system of claim 2 , wherein the node state representation vectors associated with each node of the input graph undergo a plurality of updates.

14. The system of claim 4 , wherein the one or more neural networks comprises a propagation neural network subsystem for each of the plurality of hidden layers and the output layer of the node encoder neural network.

15. The system of claim 2 , wherein the aggregator neural network subsystem comprises an aggregator neural network configured to process a node state representation vector to generate a transformed vector associated with the node; and wherein the vector representation of the input graph is based upon a summation of the transformed vectors associated with each node of the input graph.

16. The system of claim 15 , wherein the summation of the transformed vectors is a weighted summation.

17. The system of claim 1 , wherein the similarity score is based upon one of the following: a Euclidean distance, a cosine similarity or a Hamming distance.

18. The system of claim 1 , wherein the one or more neural networks are trained based upon optimization of a loss function based upon a similarity between a pair of graphs.

19. The system of claim 1 , wherein the one or more neural networks are trained based upon optimization of a loss function based upon a relative similarity between a triplet of graphs.

20. The system of claim 18 , wherein the loss function is a margin-based loss function.

21. The system of claim 1 , wherein the graph represents one of the following: a molecule, a computer program function, a parse tree, a computer network, a vehicular traffic

Assignees

• Deepmind Tech Ltd

Inventors

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

Classifications

• G06F21/563 Primary

  by source code analysis · CPC title

• G06V30/1988

  Graph matching (graphical image representation G06V30/18181) · CPC title

• G06V10/426

  Graphical representations · CPC title

• G06V10/82

  using neural networks · CPC title

• G06F21/577 Primary

  Assessing vulnerabilities and evaluating computer system security · CPC title