Generating neighborhood convolutions according to relative importance

Patent metadata

Field	Value
Publication number	US-11227014-B2
Application number	US-201916273969-A
Country	US
Kind code	B2
Filing date	Feb 12, 2019
Priority date	Mar 13, 2018
Publication date	Jan 18, 2022
Grant date	Jan 18, 2022

Abstract

Systems and methods for generating embeddings for nodes of a corpus graph are presented. More particularly, embedding information of a target node may be based on the node itself, as well as related, relevant nodes to the target node within a corpus graph. The information of various nodes among the relevant nodes to the target node can be used to weight or influence the embedding information. Disclosed systems and methods include generating neighborhood embedding information for a target node, where the neighborhood embedding information includes embedding information from neighborhood nodes of the target node's relevant neighborhood, and where certain nodes having more relevance to the target node can be weighted to influence the generation of the neighborhood embedding information over nodes having less relevance to the target node.

First claim

What is claimed:

1. A computer-implemented method, comprising:
under the control of one or more processors executing on a computer system:
maintaining, in a data store, a corpus graph comprising a first plurality of nodes;
conducting a random walk process among the first plurality of nodes originating with a target node and resulting in a subset of nodes of the first plurality of nodes, wherein each node of the subset of nodes is associated with an importance value to the target node according to a visit count to the respective node during the random walk process;
determining a relevant neighborhood for the target node comprising a second plurality of nodes of the subset of nodes having highest associated importance values;
generating neighborhood embedding information for the target node, the neighborhood embedding information comprising a plurality of embedding elements, each embedding element determined according to an embedding vector of a node of the relevant neighborhood and as a function of the associated importance value of the node to the target node;
storing the neighborhood embedding information in the data store in association with the target node; and
in response to determining that a query corresponds to the target node, providing at least one item of content corresponding to at least one node as responsive to the query, the at least one node determined based at least in part on the neighborhood embedding information.

2. The computer-implemented method of claim 1 , wherein generating the neighborhood embedding information for the target node comprises:
for each element of the neighborhood embedding information:
selecting a node of the relevant neighborhood; and
selecting an embedding element of an embedding vector of the selected node as a current embedding element of the neighborhood embedding information.

3. The computer-implemented method of claim 2 , wherein selecting a node of the relevant neighborhood comprises selecting a node of the relevant neighborhood according to the importance values of the nodes of the relevant neighborhood.

4. The computer-implemented method of claim 1 , wherein the relevant neighborhood for the target node includes up to a predetermined number of nodes.

5. The computer-implemented method of claim 1 , wherein the second plurality of nodes comprises nodes of the subset of nodes having the highest associated importance values greater than a predetermined threshold value.

6. The computer-implemented method of claim 1 , further comprising:
combining the embedding elements of the neighborhood embedding information with an embedding vector of the target node to form an aggregated embedding vector for the target node; and
storing the aggregated embedding vector in the data store in association with the target node.

7. The computer-implemented method of claim 1 , wherein the nodes of the relevant neighborhood are further determined, at least in part, according to a frequency of relationships between at least some nodes of the relevant neighborhood.

8. A non-transitory computer-readable medium bearing computer executable instructions which, when executed on a computing system comprising at least a processor, carry out a method, comprising:
maintaining, in a data store of the computing system, a corpus graph comprising a first plurality of nodes;
conducting a random walk process among the first plurality of nodes originating with target node, the random walk process resulting in a subset of nodes of the first plurality of nodes, wherein each node of the subset of nodes is associated with an importance value to the target node according to a visit count to the respective node during the random walk process;
determining a relevant neighborhood for the target node comprising a second plurality of nodes of the subset of nodes having highest associated importance values;
generating neighborhood embedding information for the target node, the neighborhood embedding information comprising a plurality of embedding elements, each embedding element determined according to an embedding vector of a node of the relevant neighborhood and as a function of the associated importance value of the node to the target node;
storing the neighborhood embedding information in the data store in association with the target node; and
in response to determining that a query corresponds to the target node, providing at least one item of content corresponding to at least one node as responsive to the query, the at least one node determined based at least in part on the neighborhood embedding information.

9. The non-transitory computer-readable medium of claim 8 , wherein generating the neighborhood embedding information for the target node comprises:
for each embedding element of the neighborhood embedding information:
selecting a node of the relevant neighborhood; and
selecting an embedding element of an embedding vector of the selected node as a current embedding element of neighborhood embedding information.

10. The non-transitory computer-readable medium of claim 9 , wherein selecting a node of the relevant neighborhood comprises selecting a node of the relevant neighborhood according to the importance values of the nodes of the relevant neighborhood.

11. The non-transitory computer-readable medium of claim 8 , wherein the relevant neighborhood for the target node includes up to a predetermined number of nodes.

12. The non-transitory computer-readable medium of claim 8 , wherein the second plurality of nodes comprises nodes of the subset of nodes having the highest associated importance values greater than a predetermined threshold value.

13. The non-transitory computer-readable medium of claim 8 , wherein the method carried out on the computing system further comprises:
combining the embedding values of the neighborhood embedding information with an embedding vector of the target node to form an aggregated embedding vector for the target node; and
storing the aggregated embedding vector in the data store in association with the target node.

14. The non-transitory computer-readable medium of claim 8 , wherein the nodes of the relevant neighborhood are further determined, at least in part, according to a frequency of relationships between at least some nodes of the relevant neighborhood.

15. A computer system comprising a processor and a memory, wherein the processor, in executing instructions stored in the memory, causes the computer system to at least:
maintain in a data store a corpus graph comprising a first plurality of nodes;
conduct a random walk process among the first plurality of nodes originating with a target node and resulting in a subset of nodes of the first plurality of nodes, wherein each node of the subset of nodes is associated with an importance value corresponding to the target node based, at least in part, on a visit count to the respective node during the random walk process;
determine a relevant neighborhood for the target node comprising a second plurality of nodes of the subset of nodes having highest associated importance values;
generate neighborhood embedding information for the target node, the neighborhood embedding information comprising a plurality of embedding elements, each embedding element determined according to an embedding vector of a node of the relevant neighborhood and as a function of the associated importance value of the node to the target node;
store the neighborhood embedding information in the data store in association with the target node; and
in response to determining that a query corresponds to the target node, provide at l

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

• G06N3/045

  Combinations of networks · CPC title

• G06F18/211

  Selection of the most significant subset of features · CPC title

• G06F18/214

  Generating training patterns; Bootstrap methods, e.g. bagging or boosting · CPC title

• G06F18/29

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