Training random walks over absorbing graphs

• US 7,778,945 B2
• Filed: 06/26/2007
• Issued: 08/17/2010
• Est. Priority Date: 06/26/2007
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Singh, Ajit Paul, Meek, Christopher A., Gunawardana, Asela J.
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US11/768,867
• Publication Number:
  US 20090006290A1
• Time in Patent Office: 1,148 Days
• Field of Search: 706/14, 706/20, 463/29, 380/251, 707/5, 707/706, 707/708, 707/709, 707713-719, 707/737
• 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 parameter for a random walk over a graph, comprising:

a processor;

a memory communicatively coupled to the processor, the memory comprising components including;

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

a training component that learns the 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, the training component further comprising;

a link removal component to temporarily remove at least one link of the two or more links to define a temporarily removed link; and

a link prediction component to adjust the at least one parameter to predict the temporarily removed link.

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:

under control of one or more processors executing computer-executable instructions;

creating an augmented bipartite graph utilizing data from a platform, with nodes of the graph being created 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;

recommending the reached item node to a user corresponding to the starting user node; and

determining the one or more weight parameters in conjunction with a cost function such that a hit time is minimized while an absorption probability is maximized.

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:

a processor;

a memory communicatively coupled to the processor, the memory comprising components including;

a recommendation component for providing a recommendation to a user based on a random walk of a graph having a plurality of nodes related to a plurality of users and a plurality of items owned by the plurality of users, the nodes having a plurality of links therebetween according to ownership and social connections between the plurality of users, the recommendation starting from a node relating to the user and ending on an item node relating to an item the user does not already own; and

a training component for specifying parameters for weighing decisions of the random walk and

for determining the specified parameters to make optimal recommendations, the training component further comprising;

a link removal component to temporarily remove at least one link of the plurality of links to define a temporarily removed link; and

a link prediction component to adjust the at least one parameter to predict the temporarily removed link.