Autoregressive graph generation machine learning models

Patent metadata

Field	Value
Publication number	US-11947503-B2
Application number	US-202117351086-A
Country	US
Kind code	B2
Filing date	Jun 17, 2021
Priority date	Jun 17, 2021
Publication date	Apr 2, 2024
Grant date	Apr 2, 2024

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for generating data defining a graph. In one aspect, a method comprises: sequentially generating a respective edge set for each node in the graph, wherein for each of a plurality of nodes after a first node, generating the edge set for the node comprises: receiving a context embedding for the node that summarizes a respective edge set for each node that precedes the node; generating, based on the context embedding for the node: (i) a respective edge set for the node, and (ii) a respective embedding of the edge set for the node; generating a context embedding for a next node in the ordering of the nodes using the embedding of the edge set for the node; and adding the set of edges defined by the edge set for the node to the graph.

First claim

What is claimed is:

1. A method performed by one or more computers, the method comprising:
generating data defining a graph using a neural network system with a set of neural network parameters having trained values that have been determined by a machine learning training technique, wherein the graph comprises: (i) a plurality of nodes, and (ii) a plurality of edges that each connect a respective pair of nodes in the graph, wherein generating the graph using the neural network system comprises:
determining a number of nodes in the graph;
sequentially generating a respective edge set for each node in the graph starting from a first node in an ordering of the nodes in the graph, wherein the edge set for each node defines a set of edges in the graph corresponding to the node, wherein for each of a plurality of nodes after a first node in the ordering of nodes, generating the edge set for the node comprises:
receiving a context embedding for the node that summarizes a respective edge set for each node that precedes the node in the ordering of the nodes;
generating, based on the context embedding for the node: (i) a respective edge set for the node, and (ii) a respective embedding of the edge set for the node, using the neural network system and in accordance with the trained values of the set of neural network parameters of the neural network system;
generating a context embedding for a next node in the ordering of the nodes using the embedding of the edge set for the node using the neural network system and in accordance with the trained values of the set of neural network parameters of the neural network system, comprising:
updating a first level of a hierarchical arrangement of embeddings having a plurality of levels by adding the embedding of the edge set for the node to the first level;
propagating the update to the first level in the hierarchical arrangement of embeddings into each subsequent level in the hierarchical arrangement of embeddings,
wherein each embedding in each level after the first level in the hierarchical arrangement of embeddings is derived from two or more embeddings at a preceding level in the hierarchical arrangement of embeddings;
generating the context embedding for the next node based on the updated hierarchical arrangement of embeddings; and
providing the updated hierarchical arrangement of embeddings for use in generating the edge set for a next node in the ordering of the nodes; and

adding the set of edges defined by the edge set for the node to the graph; and

providing an output comprising the data defining the graph.

2. The method of claim 1 , wherein for one or more subsequent levels, propagating the update to the first level in the hierarchical arrangement of embeddings into the subsequent level comprises:
generating a new embedding by processing two or more embeddings from a preceding level in the hierarchical arrangement of embeddings using one or more neural network layers; and
updating the subsequent level by adding the new embedding to the subsequent level.

3. The method of claim 1 , wherein for one or more subsequent levels, propagating the update to the first level in the hierarchical arrangement of embeddings into the subsequent level comprises:
determining that the subsequent level should not be updated.

4. The method of claim 1 , wherein propagating the update to the first level in the hierarchical arrangement of embeddings into each subsequent level in the hierarchical arrangement of embeddings comprises:
adding a new level that includes at least one new embedding to the hierarchical arrangement of embeddings.

5. The method of claim 1 , wherein a number of embeddings in each level of the hierarchical arrangement of embeddings decreases exponentially with each level in the hierarchical arrangement of embeddings.

6. The method of claim 1 , wherein generating the context embedding for the next node based on the updated hierarchical arrangement of embeddings comprises:
selecting one or more embeddings from the updated hierarchical arrangement of embeddings, wherein the selected embeddings include at least one embedding from a level after the first level; and
processing the selected embeddings using one or more neural network layers to generate the context embedding for the next node.

7. The method of claim 6 , wherein selecting one or more embeddings from the updated hierarchical arrangement of embeddings comprises:
selecting the embeddings based on an index of the next node.

8. The method of claim 6 , wherein processing the selected embeddings using one or more neural network layers to generate the context embedding for the next node comprises:
sequentially processing each selected embedding using one or more recurrent neural network layers.

9. The method of claim 1 , generating the edge set for the node comprises:
constructing a tree, conditioned on the context embedding for the node, that comprises one or more leaf vertices that each identify a respective target node in the graph; and
determining that the graph includes a respective edge between: (i) the node, and (ii) each target node identified by a respective leaf vertex.

10. The method of claim 9 , wherein each vertex in the tree is associated with a respective interval of one or more node indices from a set of node indices that indexes the nodes in the graph, and wherein each child vertex is associated with an interval of node indices that is a proper subset of an interval of node indices associated with a parent vertex of the child vertex.

11. The method of claim 9 , wherein constructing the tree comprises:
instantiating a root vertex in the tree; and
for each vertex in the tree starting from the root vertex:
determining if the vertex has each of multiple possible child vertices; and
in response to determining that the vertex has a possible child vertex, recursively transitioning into the child vertex to generate a sub-tree rooted at the child vertex.

12. The method of claim 11 , wherein determining if the vertex has a possible child vertex comprises:
processing one or more tree state embeddings associated with the vertex that collectively represent a current state of the tree using one or more neural network layers to generate a probability value; and
probabilistically determining if the vertex has the possible child vertex based on the probability value.

13. The method of claim 12 , further comprising conditioning the construction of the tree on the context embedding for the node by initializing one or more tree state embeddings associated with the root vertex in the tree based on the context embedding for the node.

14. The method of claim 12 , wherein generating the embedding of the edge set for the node comprises, after constructing the tree:
determining the embedding of the edge set for the node based on one or more tree state embeddings generated for the root vertex of the tree.

15. The method of claim 9 , wherein the tree is a binary tree.

16. The method of claim 1 , wherein generating the edge set for the first node in the ordering of the nodes comprises:
receiving a default context embedding;
generating, based on the default context embedding for the first node: (i) a respective edge set for the first node, and (ii) a respective embedding of the edge set for the first node;
generating a context embedding for a next node in the ordering of the nodes using the embedding of the edge set for the first node; and
adding the set of edges defined by the edge set for the first node to the graph.

17. The method of claim 1 , w

Assignees

• Google Llc

Inventors

• Dai Hanjun
• Nazi Azade
• Li Yujia
• Dai Bo
• Schuurmans Dale Eric

Classifications

• G06N3/0495

  Quantised networks; Sparse networks; Compressed networks · CPC title

• G06N3/09

  Supervised learning · CPC title

• G06N3/0475

  Generative networks · CPC title

• G06N3/0442

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

• G06F16/212 Primary

  with details for data modelling support · CPC title