Collaborative filtering in directed graph

Patent metadata

Field	Value
Publication number	US-2016342899-A1
Application number	US-201514718391-A
Country	US
Kind code	A1
Filing date	May 21, 2015
Priority date	May 21, 2015
Publication date	Nov 24, 2016
Grant date	—

Abstract

Embodiments are disclosed for data computation of collaborative filtering in a social network. Collaborative filtering involves predicting a user's behavior or interests based on other users' behavior or interests. To predict a user's interests in an item such as a picture, a system performs an iterative computation to perform an evaluation by solving an objective function. The system characterizes “users” as “vertices” in a directed graph, “relationship among users” as “edges” in the directed graph, and “items” as “worker data” that is locally-calculated, stored, and managed in individual worker computers. When a local computing process is completed, the “worker data” can be transferred to other worker computers so as to complete a whole computing process. The system enhances an overall computing efficiency and enables collaborative filtering across a large data set.

First claim

I/We claim:

1 . A method for performing a computation on a directed graph, comprising:
selecting a first set of nodes from the directed graph to organize a first computing group; selecting a second set of nodes from the directed graph to organize a second computing group, wherein the first and second sets of nodes are selected at least based on computing resources allocated to perform the computation; associating the first computing group to a first computing device; associating a first set of items with the first computing device; associating the second computing group to a second computing device; associating a second set of items with the second computing device; performing the computation between each node of the first set of nodes and each item of the first set of items to generate a first intermediate result; performing the computation between each node of the second set of nodes and each item of the second set of items to generate a second intermediate result; storing the first intermediate result in the first computing device; storing the second intermediate result in the second computing device; receiving, at the second computing device, the first intermediate result; receiving, at the first computing device, the second intermediate result; performing the computation between each node of the first set of nodes and each item of the second set of items to generate an updated first intermediate result; performing the computation between each node of the second set of nodes and each item of the first set of items to generate an updated second intermediate result; generating a collective result at least based on the updated first and second intermediate results; and transmitting the collective result as an output.

2 . The method of claim 1 , wherein performing the computation includes calculating a solution of an objective function.

3 . The method of claim 1 , wherein the first set of nodes represents a first set of users in a social network, and wherein the first set of nodes are selected at least based on relationships among the first set of users.

4 . The method of claim 3 , wherein the second set of nodes are selected at least based on relationships among the second set of users.

5 . The method of claim 1 , wherein the first and second sets of nodes represent multiple users in a social network, and wherein the first and second sets of items represent multiple objects that the multiple users have interests in.

6 . The method of claim 1 , wherein the interests are represented by multiple rating numbers.

7 . The method of claim 1 , wherein performing the computation includes calculating a solution of an objective function by a stochastic gradient descent (SGD) algorithm.

8 . The method of claim 1 , wherein performing the computation includes calculating a solution of an objective function by an alternating least squares (ALS) algorithm.

9 . The method of claim 1 , wherein:
receiving, at the second computing device, the first intermediate result further includes: transmitting the first intermediate result to a third computing group having a third set of nodes selected from the directed graph; performing the computation between each node of the third set of nodes and each item of the first set of items; updating the first intermediate result; and transmitting the first intermediate result to the second computing device.

10 . The method of claim 1 , wherein:
receiving, at the first computing device, the second intermediate result further includes: transmitting the second intermediate result to a third computing group having a third set of nodes selected from the directed graph; performing the computation between each node of the third set of nodes and each item of the second set of items; updating the second intermediate result; and transmitting the second intermediate result to the first computing device. cm 11 . A method for performing an operation on a directed graph having multiple nodes, the method comprising: determining more than two computing groups at least based on computing resources allocated to perform the operation, wherein the more than two computing groups are respectively associated with more than two computing devices; assigning the multiple nodes of the directed graph to the more than two computing groups; assigning multiple items to the more than two computing groups; performing, at each of the more than two computing devices, the operation between each node of the corresponding computing group and each item of the corresponding computing group so as to form an intermediate result; storing, at each of the more than two computing devices, the intermediate result; transmitting the individual intermediate result from one computing device to another computing device in a cyclic order; updating the intermediate result by performing, at each of the more than two computing devices, the operation between each node of the corresponding computing group and each item of the corresponding computing group; repeating the storing step, the transmitting step, and the updating step until that the operation between each of the multiple items and each of the multiple nodes of the directed graph has been completed; generating a collective result at least based on the intermediate result from each of the more than two computing devices; and transmitting the collective result as an output.

12 . The method of claim 11 , wherein performing the operation includes calculating a solution of an objective function.

13 . The method of claim 11 , wherein the multiple nodes represent multiple users in a social network, and wherein the multiple nodes are assigned at least based on relationships among the multiple users.

14 . The method of claim 13 , wherein the multiple nodes represent multiple users in a social network, and wherein the multiple items represent multiple objects that the multiple users have interests in.

15 . The method of claim 14 , wherein the interests are represented by multiple rating numbers.

16 . The method of claim 11 , wherein performing the operation includes calculating a solution of an objective function with a SGD algorithm.

17 . The method of claim 11 , wherein performing the operation includes calculating a solution of an objective function with an ALS algorithm.

18 . An apparatus for performing an operation for multiple nodes in a directed graph, the apparatus comprising:
a processor; a memory component coupled to the processor; a storage component coupled to the processor and configured to store a selected number of the multiple nodes of the directed graph, wherein the storage component is further configured to store a set of information corresponding to a set of items; an operation component configured to perform the operation between each item of the set of items and each node of the selected number of the multiple nodes to form the set of information; a data-transmitting component configured to transmit the set of information; a data-receiving component configured to receive an updated set of information, wherein the updated set of information is updated by performing the operation between each item of the set of items and an unselected group of nodes of the multiple nodes; and a collective-processing component configured to generate a collective result.

19 . The apparatus of claim 18 , further comprising a verification component configured to verify the collective result.

20 . The apparatus of claim 18 , wherein:

Assignees

• Facebook Inc

Inventors

• Kabiljo Maja
• Ilic Aleksandar

Classifications

• G06Q10/40

  Business processes related to social networking or social networking services · CPC title

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06N5/04 Primary

  Inference or reasoning models · CPC title

• G06N7/005

  Physics · mapped topic

• H04L67/22

  Electricity · mapped topic