Node embedding in multi-view feature vectors

Patent metadata

Field	Value
Publication number	US-11636137-B2
Application number	US-202117301797-A
Country	US
Kind code	B2
Filing date	Apr 14, 2021
Priority date	Aug 10, 2017
Publication date	Apr 25, 2023
Grant date	Apr 25, 2023

Abstract

Embodiments of the present disclosure relate generally to determining node embedding using multi-view graphs for analyzing electronic content.

First claim

What is claimed is:

1. A system comprising:
a processor; and
memory coupled to the processor and storing instructions that, when executed by the processor, cause the system to perform operations comprising:
identifying a plurality of nodes within an electronic content, each respective node in the plurality of nodes comprising a respective portion of the electronic content;
identifying a plurality of views associated with the electronic content, wherein each respective view is associated with a respective portion of the plurality of nodes;
generating a respective sequence of nodes for each respective view in the plurality of views; and
for each respective view, traversing each respective node in the respective sequence of nodes for the respective view to determine a respective embedding for the respective node for the respective view, wherein traversing each respective node includes sampling a node adjacent to the respective node in the respective sequence of nodes for the respective view; and
determining, based on the determined embedding for each respective node in the plurality of nodes, a respective view-independent embedding for the respective node.

2. The system of claim 1 , wherein the electronic content includes one or more of: text, an image, audio, and video.

3. The system of claim 1 , wherein traversing each respective node includes sampling a predetermined number of negative samples of nodes, relative to the respective node, in the respective sequence of nodes.

4. The system of claim 3 , wherein traversing each respective node includes performing a one-step gradient descent for the respective node based on the sampled adjacent node and the predetermined number of negative samples of nodes.

5. The system of claim 4 , wherein the one-step gradient descent updates a direction of an embedding vector associated with the respective node.

6. The system of claim 5 , wherein a magnitude of the direction updated to the embedding vector is based on a gradient length.

7. The system of claim 5 , wherein determining the respective view-independent embedding for each respective node includes concatenating the embedding vectors from the plurality of views for the respective node.

8. The system of claim 1 , wherein determining the respective embedding for the respective nodes for each respective view includes identifying, for each respective view, a set of edges between the respective nodes in the respective view, each edge in the set of edges denoting a relationship between a pair of nodes in the respective view.

9. The system of claim 8 , wherein each respective view in the plurality of views comprises edges associated with a respective time frame.

10. The system of claim 8 , wherein each respective node is associated with a respective phrase contained within the electronic content.

11. The system of claim 10 , wherein an edge between a first node and a second node in a view from the plurality of views denotes a phrase associated with the first node and a phrase associated with the second node are both present in a portion of the electronic content.

12. The system of claim 8 , wherein each respective node is associated with a respective user of an online social network described within the electronic content.

13. The system of claim 12 , wherein an edge between a first node and a second node in a view from the plurality of views denotes a connection in the online social network between a first user associated with the first node and a second user associated with the second node.

14. The system of claim 1 , wherein the plurality of nodes are common to all views in the plurality of views.

15. The system of claim 1 , wherein generating the respective sequence of nodes for each respective view includes performing a plurality of random recursive traversals of the plurality of nodes for the respective view.

16. The system of claim 1 , wherein determining the respective embedding for each respective node includes initializing an embedding entry based on a uniform sampling of a value associated with the plurality of nodes.

17. The system of claim 1 , wherein determining the respective embedding for each respective node includes initializing an embedding entry using a predetermined value.

18. A method comprising:
identifying, by a processor, a plurality of nodes within an electronic content, each respective node in the plurality of nodes comprising a respective portion of the electronic content;
identifying a plurality of views associated with the electronic content, wherein each respective view is associated with a respective portion of the plurality of nodes;
generating a respective sequence of nodes for each respective view in the plurality of views;
for each respective view, traversing each respective node in the respective sequence of nodes for the respective view to determine a respective embedding for the respective node for the respective view, wherein traversing each respective node includes sampling a node adjacent to the respective node in the respective sequence of nodes for the respective view; and
determining, based on the determined embedding for each respective node in the plurality of nodes, a respective view-independent embedding for the respective node.

19. A non-transitory computer-readable medium storing instructions that, when executed by a computer system, cause the computer system to perform operations comprising:
identifying a plurality of nodes within an electronic content, each respective node in the plurality of nodes comprising a respective portion of the electronic content;
identifying a plurality of views associated with the electronic content, wherein each respective view is associated with a respective portion of the plurality of nodes;
generating a respective sequence of nodes for each respective view in the plurality of views;
for each respective view, traversing each respective node in the respective sequence of nodes for the respective view to determine a respective embedding for the respective node for the respective view, wherein traversing each respective node includes sampling a node adjacent to the respective node in the respective sequence of nodes for the respective view; and
determining, based on the determined embedding for each respective node in the plurality of nodes, a respective view-independent embedding for the respective node.

Assignees

• Snap Inc

Inventors

• Han Fangqiu
• He Xinran
• Luo Jie
• Shi Yu

Classifications

• G06F16/9024

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

• G06F16/285 Primary

  Clustering or classification · CPC title

• G06F3/0484

  for the control of specific functions or operations, e.g. selecting or manipulating an object, an image or a displayed text element, setting a parameter value or selecting a range · CPC title

• H04L51/52

  for supporting social networking services · CPC title

• G06F16/288 Primary

  Entity relationship models · CPC title