TRAINING RANDOM WALKS OVER ABSORBING GRAPHS

• US 20090006290A1
• Filed: 06/26/2007
• Published: 01/01/2009
• Est. Priority Date: 06/26/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Meek, Christopher A., Singh, Ajit Paul, Gunawardana, Asela J.
• Granted Patent: US 7,778,945 B2
• Time in Patent Office: Days
• US Class Current: 706/14
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 30/0283 Price estimation or determination

Abstract

A random walk is performed over a graph, such as an augmented bipartite graph, relating to ownership data with respect to a plurality of users and items owned; the graph can provide social links between the users as well. Items can be recommended to users who do not own the items by randomly walking the graph starting at the user node to which the recommendation will be given. The random walk can step from user to user or from user to item; when an item is reached, the node can be absorbing such that the random walk terminates. The arrived item is recommended to the user. Parameters can also be provided to affect decisions made during the walk about which users to walk to and/or whether to walk to a user or an item.

Claims

1. A system for specifying at least one learned parameter for a random walk over a graph, comprising:

a graph generation component that creates a graph from a portion of data, the graph having two or more disparate nodes and one or more links between the nodes based at least in part on the data; and

a training component that learns at least one parameter with respect to performing a random walk on the graph, the parameter corresponds to at least one probability that affects direction of the random walk.

2. The system of claim 1, the two or more nodes are of disparate types and the one or more links are of disparate types, the training component determines the parameter based at least in part on one or more of the disparate node or link types.

3. The system of claim 1, at least one of the nodes is absorbing such that a random walk terminates with a probability greater than zero upon reaching the node, the training component computes an absorption probability matrix corresponding to the nodes based on the data.

4. The system of claim 3, further comprising a recommendation component that provides a recommendation list with respect to a user, the recommendation list comprises one or more recommendations, corresponding to a subset of the nodes, ranked according to a decreasing absorption probability determined from the absorption probability matrix.

5. The system of claim 1, further comprising a recommendation component that utilizes a cost function to recommend one or more items to a user sorted according to the cost function, the cost function is at least one of a hitting time or a commute time between nodes and the items correspond to one or more of the nodes.

6. The system of claim 1, a stationary distribution is computed from probabilities associated with a random walk over the two or more nodes according to the parameter, the stationary distribution is utilized to provide a static rank or score.

7. The system of claim 1, the training component determines the parameter in conjunction with a cost function, the cost function is one of optimizing hit time, optimizing commute time, or an absorption probability.

8. The system of claim 7, the cost function relates to the two or more nodes or one or more links of the graph.

9. The system of claim 7, further comprising a recommendation component that utilizes the cost function to recommend one or more items to a user, the items corresponding to at least one of the nodes.

10. A method for recommending an item to a user in a media service platform, comprising:

creating a augmented bipartite graph utilizing data from a platform, nodes of the graph are created and for each user and item in the data, at least one user node is linked to at least one item node according to the data;

randomly walking the graph starting at a user node until an item node is reached, the decision of which node to traverse at each step is based on one or more weight parameters; and

recommending the reached item node to a user corresponding to the starting user node.

11. The method of claim 10, at least one user node is connected to at least one item node based on ownership of the item.

12. The method of claim 10, at least one user node is connected to at least one disparate user node based on a social relationship.

13. The method of claim 10, further comprising determining the one or more weight parameter in conjunction with a cost function.

14. The method of claim 10, at least one of the one or more weight parameters corresponds to utilizing a similarity calculation in choosing which user node to traverse.

15. The method of claim 14, the similarity is calculated between at least two user nodes, u and v, using a similarity formula, the formula is

$\mathrm{sim}$

( u , v ) = # 



items 



in 



common 



between 



u 



and 



v # 



items 



owned 



by 



u 



# 



items 



owned 



by 



v .

16. The method of claim 10, further comprising determining the one or more weight parameters by removing at least one link between a user and an item and choosing at least one value for the one or more weight parameters that provide a high probability to existence of the link.

17. The method of claim 10, the platform is a gaming service, the users in the data correspond to the users of the service, and the items in the data correspond to games collectively owned by the users.

18. The method of claim 10, further comprising ranking a list of recommendations of items according to a calculated probability of reaching the items in the random walk.

19. The method of claim 10, further comprising computing a stationary distribution from a matrix corresponding to at least one probability of randomly walking from at least one node to at least another node.

20. A system for providing recommendations, comprising:

means for randomly walking a graph having a plurality of nodes related to users and items owned by the users, the nodes are linked according to ownership and social connections between the users;

means for providing a recommendation to a user based on the random walk starting from a node relating to the user and ending on an item node relating to an item the user does not already own;

means for specifying parameters for weighing decisions of the random walk; and

means for determining the specified parameters to make optimal recommendations.