Representing graph edges using neural networks

Patent metadata

Field	Value
Publication number	US-11455512-B1
Application number	US-201815946301-A
Country	US
Kind code	B1
Filing date	Apr 5, 2018
Priority date	Apr 5, 2017
Publication date	Sep 27, 2022
Grant date	Sep 27, 2022

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for a graph processing system. In one aspect, the graph processing system obtains data identifying a first node and a second node from a graph of nodes and edges. The system processes numeric embeddings of the first node and the second node using a manifold neural network to generate respective manifold coordinates of the first node and the second node. The system applies a learned edge function to the manifold coordinates of the first node and the manifold coordinates of the second node to generate an edge score that represents a likelihood that an entity represented by the first node and an entity represented by the second node have a particular relationship.

First claim

What is claimed is:

1. A method of training a manifold neural network and a learned edge function to determine trained values of parameters of the manifold neural network and the learned edge function, wherein:
the manifold neural network is a deep neural network that is configured to receive input numeric embeddings representing input nodes in a graph and to process each input numeric embedding to generate manifold coordinates of the input node represented by the input numeric embedding, and
the learned edge function is configured to receive manifold coordinates of a first node in the graph and manifold coordinates of a second node in the graph and to process the manifold coordinates of the first node and the manifold coordinates of the second node to generate an edge score that represents a likelihood that an entity represented by the first node and an entity represented by the second node have a particular relationship, the method comprising:
performing a plurality of random walks on the graph, wherein each random walk defines a sequence of nodes from the graph;
generating a set of positive training examples based on the random walks on the graph, wherein each positive training example comprises a reference node and a positive node, wherein the reference node and the positive node are within a context window in a random walk on the graph;
obtaining: (i) a positive training example from the set of positive training examples, wherein the positive training example comprises a reference node and a positive node that are separated by at least one intervening node in a random walk on the graph, and (ii) one or more negative nodes corresponding to the reference node;
determining, using the manifold neural network and in accordance with current values of parameters of the manifold neural network, respective manifold coordinates of the reference node, the positive node, and the negative nodes;
determining, using the learned edge function and in accordance with current values of parameters of the learned edge function, a respective edge score with the reference node for the positive node and each of the negative nodes from the respective manifold coordinates;
determining gradients of an objective function that promotes generating a high edge score for the positive node and penalizes generating high edge scores for the negative nodes with respect to the parameters of the manifold neural network and the parameters of the learned edge function; and
using the gradients to update the current values of the parameters of the manifold neural network and of the parameters of the learned edge function.

2. The method of claim 1 , further comprising:
determining a gradient of the objective function with respect to a current numeric embedding of the reference node; and
updating the current numeric embedding of the reference node using the gradient.

3. The method of claim 1 , further comprising:
determining gradients of the objective function with respect to a current numeric embedding of the positive node; and
updating the current numeric embedding of the positive node using the gradients.

4. The method of claim 1 , wherein each negative node is a node that is not connected by an edge to the reference node in the graph.

5. The method of claim 1 , wherein the particular relationship is an asymmetric relationship, wherein edges in the graph are directed edges, and wherein the learned edge function is an asymmetric edge function.

6. The method of claim 5 , wherein the edge score represents a likelihood that the entity represented by the first node has the particular relationship to the entity represented by the second node regardless of whether the entity represented by the second node has the particular relationship to the entity represented by the first node.

7. The method of claim 1 , wherein a dimensionality of the manifold coordinates is smaller than a dimensionality of the numeric embeddings.

8. The method of claim 1 , wherein the learned edge function is a learned affine projection of the manifold coordinates for the first node and second node.

9. The method of claim 1 , wherein the learned edge function is an inner product of (i) a matrix multiplication between a learned left projection matrix and a transpose of the manifold coordinates of the first node and (ii) a matrix multiplication between a learned right projection matrix and the manifold coordinates of the second node.

10. The method of claim 1 , wherein the learned edge function is an inner product between (i) a learned parameter vector and (ii) a vector that includes, for each dimension of the learned parameter vector, a value of an activation function of a respective learned affine projection for the dimension.

11. A system comprising:
one or more computers; and
one or more storage devices communicatively coupled to the one or more computers, wherein the one or more storage devices store instructions that, when executed by the one or more computers, cause the one or more computers to perform operations for training a manifold neural network and a learned edge function to determine trained values of parameters of the manifold neural network and the learned edge function, wherein:
the manifold neural network is a deep neural network that is configured to receive input numeric embeddings representing input nodes in a graph and to process each input numeric embedding to generate manifold coordinates of the input node represented by the input numeric embedding, and
the learned edge function is configured to receive manifold coordinates of a first node in the graph and manifold coordinates of a second node in the graph and to process the manifold coordinates of the first node and the manifold coordinates of the second node to generate an edge score that represents a likelihood that an entity represented by the first node and an entity represented by the second node have a particular relationship, the operations comprising:
performing a plurality of random walks on the graph, wherein each random walk defines a sequence of nodes from the graph;
generating a set of positive training examples based on the random walks on the graph, wherein each positive training example comprises a reference node and a positive node, wherein the reference node and the positive node are within a context window in a random walk on the graph;
obtaining: (i) a positive training example from the set of positive training examples, wherein the positive training example comprises a reference node and a positive node that are separated by at least one intervening node in a random walk on the graph, and (ii) one or more negative nodes corresponding to the reference node;
determining, using the manifold neural network and in accordance with current values of parameters of the manifold neural network, respective manifold coordinates of the reference node, the positive node, and the negative nodes;
determining, using the learned edge function and in accordance with current values of parameters of the learned edge function, a respective edge score with the reference node for the positive node and each of the negative nodes from the respective manifold coordinates;
determining gradients of an objective function that promotes generating a high edge score for the positive node and penalizes generating high edge scores for the negative nodes with respect to the parameters of the manifold neural network and the parameters of the learned edge function; and
using the gradients to update the current values of the parameters of the manifold neural network and of the parameters of the learned edge function.

12. The system of claim 11 , wherein the operations furt

Assignees

• Google Llc

Inventors

• Al-Rfou′ Rami
• Abu-El-Haija Sami Ahmad
• Perozzi Bryan Thomas

Classifications

• G06N3/0985

  Hyperparameter optimisation; Meta-learning; Learning-to-learn · CPC title

• G06N3/04 Primary

  Architecture, e.g. interconnection topology · CPC title

• G06N3/0895

  Weakly supervised learning, e.g. semi-supervised or self-supervised learning · CPC title

• G06N3/0495

  Quantised networks; Sparse networks; Compressed networks · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title