Efficient processing of neighborhood data

Patent metadata

Field	Value
Publication number	US-11232152-B2
Application number	US-201816178443-A
Country	US
Kind code	B2
Filing date	Nov 1, 2018
Priority date	Mar 13, 2018
Publication date	Jan 25, 2022
Grant date	Jan 25, 2022

Abstract

Systems and methods for generating embeddings for nodes of a corpus graph are presented. More particularly, operations for generation of an aggregated embedding vector for a target node is efficiently divided among operations on a central processing unit and operations on a graphic processing unit. With regard to a target node within a corpus graph, processing by one or more central processing units (CPUs) is conducted to identify the target node's relevant neighborhood (of nodes) within the corpus graph. This information is prepared and passed to one or more graphic processing units (GPUs) that determines the aggregated embedding vector for the target node according to data of the relevant neighborhood of the target node.

First claim

What is claimed:

1. A computer-implemented method for determining an aggregated embedding vector for a target node of a corpus graph, the method comprising:
accessing a target node of a corpus graph;
determining an aggregated embedding vector relating to the target node, comprising:
determining a relevant neighborhood of the target node within the corpus graph through execution by a central processing unit (CPU); and
generating an aggregated embedding vector for the target node in view of the relevant neighborhood of the target node through execution by a graphic processing unit (GPU);
wherein the aggregated embedding vector comprises an embedding vector of the target node concatenated with neighborhood embedding information for the target node determined from the relevant neighborhood of the target node; and

associating the aggregated embedding vector with the target node.

2. The computer-implemented method of claim 1 , further comprising:
receiving a query from a computer user;
determining that the query corresponds to the target node of the corpus graph;
determining a plurality of potential recommendation nodes as recommendations for the user in view of the query, where the plurality of potential recommendation nodes is identified from the corpus graph according to the aggregated embedding vector of the target node; and
providing at least one of the plurality of potential recommendation nodes to the user in response to the query as a recommended node to the user.

3. The computer-implemented method of claim 1 , further comprising:
processing the relevant neighborhood data of the target node into a fixed number of records of the relevant neighborhood of the target node; and
wherein generating the aggregated embedding vector for the target node in view of the relevant neighborhood of the target node comprises generating the aggregated embedding vector for the target node in view of the fixed number of records of the relevant neighborhood of the target node.

4. The computer-implemented method of claim 3 , further comprising:
fixing the number of neighbors of each node in the relevant neighborhood data of the target node to a predetermined fixed number; and
wherein processing the relevant neighborhood data of the target node into a fixed number of records comprises processing the relevant neighborhood data of the target node such that, after fixing the number of neighbors of each node in the relevant neighborhood data of the target node, each node has a corresponding record.

5. The computer-implemented method of claim 4 , wherein each record of the fixed number of records is a fixed sized record.

6. The computer-implemented method of claim 5 , wherein processing the relevant neighborhood data of the target node into a fixed number of records of the relevant neighborhood of the target node comprises truncating neighbor nodes of nodes in the neighborhood data that have more neighbor nodes than the fixed number of neighbors to the fixed number of neighbor nodes.

7. The computer-implemented method of claim 6 , wherein processing the relevant neighborhood data of the target node into a fixed number of records of the relevant neighborhood of the target node further comprises padding a node of the neighborhood data that has fewer than the fixed number of neighbor nodes with null neighbor nodes up to the fixed number of neighbor nodes.

8. The computer-implemented method of claim 5 , wherein:
each record corresponds to information of a node of the neighborhood data and information of that node's neighbor nodes; and
an indication of the number of null neighbor nodes of the node.

9. The computer-implemented method of claim 8 , wherein determining the relevant neighborhood of the target node within the corpus graph through execution by the central processing unit is performed asynchronously to generating the aggregated embedding vector for the target node in view of the relevant neighborhood of the target node through execution by the graphic processing unit.

10. The computer-implemented method of claim 9 , wherein processing the relevant neighborhood data of the target node into the fixed number of records of the relevant neighborhood of the target node is performed by the central processing unit.

11. The computer-implemented method of claim 10 , wherein the graphics processing unit is one of a cluster of graphics processing units.

12. The computer-implemented method of claim 11 , wherein the cluster of graphic processing units is a remote cluster of graphic processing units to the central processing unit.

13. A computer-readable medium bearing computer-executable instructions which, when executed on a computing system comprising at least a processor retrieving instructions from the medium, carry out a method for determining an aggregated embedding vector for a target node of a corpus graph, the method comprising:
accessing a target node of a corpus graph;
determining an aggregated embedding vector relating to the target node, comprising:
determining a relevant neighborhood of the target node within the corpus graph through execution by a central processing unit (CPU); and
generating an aggregated embedding vector for the target node in view of the relevant neighborhood of the target node through execution by a graphic processing unit (GPU);
wherein the aggregated embedding vector comprises an embedding vector of the target node concatenated with neighborhood embedding information for the target node determined from the relevant neighborhood of the target node; and

associating the aggregated embedding vector with the target node.

14. The computer-readable medium of claim 13 , the method further comprising:
processing the relevant neighborhood data of the target node into a fixed number of records of the relevant neighborhood of the target node; and
wherein generating the aggregated embedding vector for the target node in view of the relevant neighborhood of the target node comprises generating the aggregated embedding vector for the target node in view of the fixed number of records of the relevant neighborhood of the target node.

15. The computer-readable medium of claim 14 , the method further comprising:
fixing the number of neighbors of each node in the relevant neighborhood data of the target node to a predetermined fixed number; and
wherein processing the relevant neighborhood data of the target node into a fixed number of records comprises processing the relevant neighborhood data of the target node such that, after fixing the number of neighbors of each node in the relevant neighborhood data of the target node, each node has a corresponding record.

16. The computer-readable medium of claim 15 , wherein processing the relevant neighborhood data of the target node into a fixed number of records of the relevant neighborhood of the target node comprises:
truncating neighbor nodes of nodes in the neighborhood data that have more neighbor nodes than the fixed number of neighbors to the fixed number of neighbor nodes; and
padding a node of the neighborhood data that has fewer neighbor nodes than the fixed number of neighbor nodes with null neighbor nodes up to the fixed number of neighbor nodes.

17. The computer-readable medium of claim 15 , wherein determining the relevant neighborhood of the target node within the corpus graph through execution by the central processing unit is performed asynchronously to generating the aggregated embedding vector for the target node in view of the relevant neighborhood of the target node through execution by the gra

Assignees

• Pinterest Inc
• Amazon Tech Inc

Inventors

• Leskovec Jurij
• Eksombatchai Chantat
• Chen Kaifeng
• He Ruining
• Ying Rex

Classifications

• G06F16/9024 Primary

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

• G06F18/2413

  based on distances to training or reference patterns · CPC title

• G06F18/2148

  characterised by the process organisation or structure, e.g. boosting cascade · CPC title

• G06F18/29

  Graphical models, e.g. Bayesian networks · CPC title

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title