MACHINE OPTIMIZATION DEVICES, METHODS, AND SYSTEMS

• US 20120005238A1
• Filed: 12/11/2009
• Published: 01/05/2012
• Est. Priority Date: 12/12/2008
• Status: Active Grant

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Jebara, Tony, Huang, Bert
• Granted Patent: US 8,631,044 B2
• Time in Patent Office: Days
• US Class Current: 707/798
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• 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/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/08 Auctions

Abstract

A method, system, computer program product and computer readable media for matching using degree distribution information are disclosed. An embodiment of the method can include performing b-matching on a graph data structure expanded using degree distribution information in order to identify neighbors of a selected input node. The b-matching can be performed using belief propagation. The belief propagation method is adapted to use a compressed message update rule and to be suitable for use with distributed processing systems. An embodiment can also include enhancing a matching result by applying degree distribution information to a first matching result to generate a second matching result. Embodiments for online advertisement/search term matching, product recommendation, dating service and social network matching, auction buyer/seller matching and resource allocation, among other, are disclosed.

Claims

1. A computer readable medium having software instructions stored thereon for matching an advertisement with a phrase, the software instructions, when executed by a processor, cause the processor to perform operations comprising:

receiving a first graph data structure, a first weight matrix and degree distribution data as input, the first graph data structure having a first group of nodes each representing an advertisement and a second group of nodes each representing a phrase, the first weight matrix including a bid value for each connection between an advertisement and a phrase in the first graph data structure;

generating a second graph data structure including nodes corresponding to the first graph data structure and additional dummy nodes;

generating a second weight matrix including the first weight matrix and additional weight values each associated with one of the nodes in the first graph data structure and one of the dummy nodes, the additional weight values in the second weight matrix being determined based on the degree distribution data and the second weight matrix also including a group of zero weight values;

constraining the nodes in the second graph data structure that correspond to the first graph data structure to a predetermined degree value and not constraining the dummy nodes in the second graph data structure;

determining a maximum weight b-matching based on the second graph data structure, where b is set to the predetermined degree value, and generating an intermediate graph data structure having binary weight values;

truncating the intermediate graph data structure; and

generating a result graph data structure based on the truncated portion of the intermediate graph data structure as output.

2. The computer readable medium of claim 1, wherein the determining the maximum weight b-matching includes:

updating a belief value corresponding to each neighboring advertiser node of a selected phrase node in the second graph data structure by passing messages between neighboring nodes until a termination condition is met, each message being based on the second weight matrix values and received messages, where a data content of each message is determined according to a compressed message update rule; and

storing each updated belief value and each received message in an electronic storage associated with the selected phrase node.

3. The computer readable medium of claim 2, wherein the generating the result graph includes:

selecting a predetermined number of advertisement nodes matching the selected phrase node, the matching based on updated belief values of advertisement nodes neighboring the selected phrase node; and

outputting the selected advertisement nodes.

4. The computer readable medium of claim 1, wherein the additional weight values include a first group of weight values in a first matrix and a second group of weight values in a second matrix, the second matrix being a transpose of the first matrix.

5. The computer readable medium of claim 1, wherein the degree distribution data includes data provided by an advertiser associated with each advertisement.

6. The computer readable medium of claim 1, wherein the degree distribution data includes data inferred from statistical properties of prior advertisement and phrase matching data.

7. The computer readable medium of claim 1, wherein the degree distribution data includes data learned from stored prior advertisement and phrase matching data.

8. The computer readable medium of claim 1, wherein the software instructions are adapted for execution on a distributed processor.

9. The computer readable medium of claim 1, wherein the operations further include:

receiving quota data for each advertisement;

adjusting weight values for each advertisement node in the first weight matrix based upon quota data corresponding to the node; and

generating the second weight matrix using the adjusted weight values for the advertisement nodes.

10. The computer readable medium of claim 2, wherein the data content of each message is a single scalar value.

11. The computer readable medium of claim 10, wherein the single scalar value corresponds to a potential matching of the selected phrase node with a respective one of its neighboring advertisement nodes.

12. The computer readable medium of claim 11, wherein the single scalar value includes a weight matrix value corresponding to a potential matching of the selected phrase node and the respective one of the neighboring nodes and a value of a message received by that respective neighbor node from another node and a weight matrix value corresponding to a potential matching between the respective neighbor node and the other node.

13. The computer readable medium of claim 1, wherein the phrase is a phrase included in a search query submitted to a search engine.

14. The computer readable medium of claim 1, wherein the phrase is a phrase extracted from content within a content page on which a predetermined number of advertisements are to be displayed such that displayed advertisements relate to the content found on the content page.

15. The computer readable medium of claim 1, wherein the phrase is a phrase determined based on a semantic analysis of a natural language phrase.

16. The computer readable medium of claim 1, wherein the natural language phrase is a natural language search query.

17. The computer readable medium of claim 1, wherein the natural language phrase is a natural language advertiser goal.

54. The computerized method of claim 1, wherein the degree distribution data includes data learned from stored prior supplier and customer matching data.

18. A distributed processing system for matching advertisements with search terms, the system comprising:

a plurality of processors each corresponding to at least one node of a graph data structure having advertisement nodes, search term nodes and dummy nodes, where each advertisement node is a neighbor to at least one search term node;

a network coupling the plurality of processors and adapted to transfer messages between the processors;

wherein each processor is adapted to load and execute software instructions stored on a computer readable medium, the software instructions, when executed, cause the processor to perform operations including;

receiving a portion of a first graph data structure, a portion of a profit matrix and a portion of degree distribution data as input, the first graph data structure having a first group of nodes each representing an advertisement and a second group of nodes each representing a phrase, the profit matrix including a bid value for each connection between an advertisement and a search term in the first graph data structure;

generating a second graph data structure including nodes corresponding to the first graph data structure and a plurality of dummy nodes;

generating a weight matrix portion including the portion of the profit matrix and, when the processor corresponds to one of the dummy nodes, generating an additional weight value associated with the dummy node, the additional weight value in the weight matrix portion being based on the portion of degree distribution data or having a zero value depending on a location of the dummy node in the second graph data structure;

receiving a node constraint value for nodes in the second graph data structure that correspond to the first graph data structure to a predetermined degree value and not receiving a constraint value for the dummy nodes in the second graph data structure;

determining a maximum weight b-matching based on the second graph data structure, where b is set to the predetermined degree value, and generating an intermediate graph data structure having binary weight values, the determining including;

updating belief values corresponding to its respective neighbor nodes by passing messages between neighboring nodes until a termination condition is met, a data content of each message being based on weight matrix values and received messages, where a data content of each message is determined according to a message update rule;

storing each updated belief value and each received message in an electronic storage associated with the respective processor;

truncating the intermediate graph data structure;

generating a result graph data structure based on the truncated portion of the intermediate graph data structure as output, including selecting a predetermined number of matching neighbor nodes, the matching being determined based on updated belief values of neighbor nodes; and

outputting the selected matching neighbor nodes.

19. The distributed processing system of claim 18, wherein the data content of each message is a single scalar value.

20. The distributed processing system of claim 19, wherein the single scalar value corresponds to a potential matching of the selected search term node with a respective one of its neighboring advertiser nodes.

21. The distributed processing system of claim 20, wherein the single scalar value includes a profit matrix value corresponding to a potential matching of the selected search term node and the respective one of the neighboring nodes and a value of a message received by that respective neighbor node from another node and a profit matrix value corresponding to a potential matching between the respective neighbor node and the other node.

22. The distributed processing system of claim 18, wherein the processors are constituted by a cloud computing system.

23. The distributed processing system of claim 18, wherein each profit matrix value represents a profit amount associated with an edge between neighboring nodes.

24. The distributed processing system of claim 18, wherein the updating is performed iteratively until the termination condition is met.

25. The distributed processing system of claim 18, wherein the termination condition is a predetermined number of iterations of the updating.

26. The distributed processing system of claim 18, wherein the termination condition is defined as receiving no changed message values within a predetermined period of time.

27. The distributed processing system of claim 18, wherein the termination condition is a number of messages sent from each node.

28. The distributed processing system of claim 18, wherein the termination condition is an elapsing of a predetermined period of time.

29. The distributed processing system of claim 18, wherein the termination condition is defined as the earliest occurrence of one of receiving no changed message values within a first predetermined period of time and an elapsing of a second predetermined period of time.

30. A computerized method for matching an advertiser with a search term, the method comprising:

providing a first bipartite graph data structure having a plurality of advertiser nodes and a plurality of search term nodes, where each advertiser node is connected to a corresponding search term node by an edge;

providing a profit matrix having a profit for each edge of the bipartite graph data structure;

providing degree distribution data representing a degree distribution of each node;

generating a second bipartite graph data structure including nodes of the first bipartite graph data structure and a plurality of dummy nodes;

generating, with a processor adapted to perform weight matrix expansion, a weight matrix including values of the profit matrix and additional values associated with the dummy nodes, the additional values in the weight matrix being determined based on the degree distribution data and including a group of zero weight values;

constraining the nodes in the second graph data structure that correspond to the first graph data structure to a predetermined degree value and not constraining the dummy nodes in the second graph data structure;

determining a maximum weight b-matching based on the second graph data structure, where b is set to the predetermined degree value;

generating an intermediate bipartite graph data structure having binary weight values;

generating a result graph data structure by truncating the intermediate graph data structure to remove the dummy nodes;

selecting a predetermined number of advertiser nodes matching each search term node of a group of search term nodes of interest, the matching being determined based on result graph values of advertiser nodes adjacent to each search term node of interest; and

outputting the selected advertiser nodes matching each search term node of interest.

31. The computerized method of claim 30, wherein the determining the maximum weight b-matching includes:

updating, with a processor adapted to perform belief propagation generalized matching, a belief value corresponding to each advertiser node connected to a selected search term node by passing messages between adjacent nodes until a termination condition is met, each message being based on weight matrix values and received messages, where a data content of each message is determined according to a compressed message update rule; and

storing each updated belief value and each received message in an electronic storage associated with the corresponding advertiser node.

32. The method of claim 31, further comprising displaying advertisements associated with each of the selected advertiser nodes on a search results page corresponding to the search term node associated with the selected advertiser nodes.

33. The method of claim 31, further comprising storing at each advertiser node and at each search term node a portion of the profit matrix and a portion of the degree distribution data, where each portion is selected based on adjacent nodes of each respective advertiser node and each respective search term node.

34. The method of claim 31, wherein the updating and storing are performed using parallel processing.

35. The method of claim 31, wherein the processor is a cloud computing system adapted to perform bipartite matching using belief propagation with degree distribution data.

36. The method of claim 31, wherein the electronic storage is a cloud storage system.

37. The method of claim 30, wherein each profit represents a profit on placement of an advertisement by an advertiser associated with the advertisement.

38. The method of claim 31, wherein the updating is performed iteratively until the termination condition is met.

39. The method of claim 31, wherein the termination condition is a predetermined number of iterations of the updating.

40. The method of claim 31, wherein the termination condition is defined as a steady state of updated belief values during a predetermined period of time.

41. The method of claim 31, wherein the termination condition is a number of messages sent from each node.

42. The method of claim 31, wherein the termination condition is an elapsing of a predetermined period of time.

43. The method of claim 31, wherein the termination condition is defined as the earliest occurrence of one of a steady state of updated belief values during a first predetermined period of time and an elapsing of a second predetermined period of time.

44. A computerized method for matching customers with suppliers in an auction, the method comprising:

providing a first bipartite graph data structure having a plurality of supplier nodes and a plurality of customer nodes, where each supplier node is connected to a customer node by an edge;

providing a first weight matrix data structure having a weight value for each edge of the bipartite graph data structure, where a portion of the weight matrix is provided to each supplier node and each customer node, the weight matrix portion including weight values for nodes adjacent to each respective supplier node and customer node;

generating, using a processor adapted to estimate graph structure using prior degree distribution information, a second graph data structure including nodes corresponding to the first bipartite graph data structure and having a plurality of dummy nodes;

generating, with the processor, a second weight matrix including the first weight matrix and additional weight values each associated with one of the dummy nodes, the additional weight values in the second weight matrix being determined based on the degree distribution data, the second weight matrix also including a group of zero weight values associated with a group of dummy nodes;

storing the second weight matrix in an electronic memory coupled to the processor;

constraining nodes of the second graph data structure that correspond to nodes of the first graph data structure to a predetermined degree value, and leaving the dummy nodes in the second graph data structure unconstrained;

determining a maximum weight b-matching based on the second graph data structure, where b is set to the predetermined degree value, and generating an intermediate graph data structure having binary weight values;

truncating the intermediate graph data structure; and

generating a result graph data structure based on the truncated portion of the intermediate graph data structure as output.

45. The computerized method of claim 44, wherein the determining the maximum weight b-matching includes:

updating a belief value corresponding to each of the supplier nodes and customer nodes, with a processor adapted to perform belief propagation, by passing electronic messages between adjacent nodes until a termination condition is met, each message being based on the weight matrix portion values and received messages, where a value of each message is determined according to a compressed message update rule; and

storing, in an electronic memory, received messages and an updated belief value for each supplier node and customer node in storage locations of the electronic memory associated with the corresponding node.

46. The computerized method of claim 45, wherein the method further includes:

selecting, with the processor, a predetermined number of supplier nodes and a predetermined number of respective customer nodes matching each selected supplier node, the selecting of the customer nodes being based on updated belief values; and

outputting the selected supplier nodes and respective matching customer nodes.

47. The computerized method of claim 45, wherein the updating and storing are performed using parallel processing.

48. The computerized method of claim 45, wherein the parallel processing is carried out on a cloud computing system and the electronic memory includes a cloud storage system.

49. The computerized method of claim 45, wherein each weight in the first weight matrix represents a profit amount for a connection between the corresponding supplier and customer.

50. The computerized method of claim 45, wherein the updating is performed iteratively until the termination condition is met.

51. The computerized method of claim 44, wherein the determining the maximum weight b-matching includes applying a max flow algorithm to the second graph data structure.

52. The computerized method of claim 44, wherein the degree distribution data for each node includes data provided by a respective supplier or customer.

53. The computerized method of claim 44, wherein the degree distribution data includes data inferred from statistical properties of prior supplier and customer data.

55. A computer readable medium having software instructions stored thereon for matching buyers with sellers in an auction, the software instructions, when executed by a processor, cause the processor to perform operations comprising:

providing a first graph data structure having a plurality of seller nodes and a plurality of buyer nodes, where each seller node is connected to a buyer node by an edge;

providing a first weight matrix data structure having a weight value for each edge of the first graph data structure, where a portion of the first weight matrix is provided to each supplier node and each customer node, the weight matrix portion including weight values for nodes adjacent to each respective supplier node and customer node;

generating, using a processor adapted to estimate graph structure using prior degree distribution information, a second graph data structure including nodes corresponding to the first graph data structure and a plurality of dummy nodes;

generating, using the processor, a second weight matrix including the first weight matrix and additional weight values each associated with one of the dummy nodes, the additional weight values in the second weight matrix being determined based on the degree distribution data, the second weight matrix also including a group of zero weight values associated with a group of edges between dummy nodes;

storing the second weight matrix in an electronic memory coupled to the processor;

constraining nodes of the second graph data structure that correspond to nodes of the first graph data structure to a predetermined degree value, and leaving the dummy nodes in the second graph data structure unconstrained;

determining a maximum weight b-matching based on the second graph data structure, where b is set to the predetermined degree value, the determining including;

updating a belief value corresponding to each of the supplier nodes and customer nodes, with a processor adapted to perform belief propagation, by passing electronic messages between adjacent nodes until a termination condition is met, each message being based on the weight matrix portion values and received messages, where a value of each message is determined according to a compressed message update rule; and

storing, in an electronic memory, received messages and an updated belief value for each supplier node and customer node in storage locations of the electronic memory associated with the corresponding node;

generating an intermediate graph data structure having binary weight values by truncating the intermediate graph data structure; and

selecting, with the processor, a predetermined number of seller nodes and a predetermined number of respective buyer nodes matching each selected seller node, the selecting of the buyer nodes being based on updated belief values; and

outputting the selected seller nodes and respective matching buyer nodes.

56. A computerized method for matching social network members using belief propagation, the method comprising:

accessing a first graph data structure having a plurality of member nodes each representing a member of a social network service and a compatibility matrix representing a compatibility between member nodes joined by an edge of the graph data structure;

accessing degree distribution data including a degree distribution for each member node;

generating a second graph data structure that includes nodes copied from the first graph data structure and a group of dummy nodes;

generating a weight matrix including the compatibility matrix and additional weight values corresponding to edges between member nodes and dummy nodes, the additional weight values being based on a portion of the degree distribution data, the weight matrix also including a group of zero weight values corresponding to edges between dummy nodes;

constraining a degree value of the member nodes within the second graph data structure and leaving the dummy nodes within the second graph data structure unconstrained;

updating, with a processor adapted to perform social network service member matching using degree distribution and belief propagation, a belief value corresponding to edges between nodes of the second graph data structure by passing messages between neighboring nodes until a termination condition is met, each message being based on weight matrix values and received messages, where data content of each message is determined according to a compressed message update rule;

storing each updated belief value and each received message in an electronic storage associated with the corresponding node;

extracting a portion of the second graph data structure that corresponds to the member nodes as a result graph data structure;

selecting a predetermined number of neighboring member nodes matching a member node of interest from the result graph data structure, the matching being determined based on updated belief values of neighbor member nodes of the member node of interest; and

outputting the selected member nodes.

57. A system for matching items with other items comprising:

a storage adapted to store software instructions for performing a method of matching items with other items using degree distribution, a first graph data structure having nodes representing items, a first weight matrix having weight values associated with an edge in the first graph data structure connecting two items and degree distribution data having degree distribution data for each node in the first graph data structure;

a processor coupled to the storage and adapted to execute the software instructions and perform operations including;

generating a second graph data structure including nodes representing the first graph data structure and a plurality of dummy nodes;

generating a second weight matrix including values representing the first weigh matrix and having additional values associated with the dummy nodes, the additional values being determined based on the degree distribution data;

determining a constraint value for the nodes of the second graph data structure that represent the nodes of the first graph data structure;

performing a maximum weight b-matching operation on the second graph data structure and the second weight matrix to produce a result matrix;

extracting a portion of the result matrix corresponding to the nodes of the first graph data structure; and

providing a portion of the result matrix as output.

58. The system of claim 57, wherein performing the maximum weight b-matching operation includes performing a max flow operation on the second graph data structure and second weight matrix.

59. The system of claim 57, wherein performing the maximum weight b-matching operation includes performing a belief propagation operation among nodes of the second graph data structure.

60. The system of claim 59, wherein the belief propagation operation includes:

updating a belief value corresponding to each neighboring node of a selected node in the second graph data structure by passing messages between neighboring nodes until a termination condition is met, each message being based on the second weight matrix values and received messages, where a data content of each message is determined according to a compressed message update rule; and

storing each updated belief value and each received message in an electronic storage associated with the selected node.

61. A computerized method for post processing recommender outputs, the method comprising:

receiving a training data set containing a plurality of nodes having a group of nodes representing users and a group of nodes representing items;

receiving a ratings matrix representing preferences of users for items in the training data set, with each cell in the ratings matrix containing a value representing a rating of one of the items by one of the users;

receiving a testing data set containing a plurality of nodes having a group of nodes representing users and a group of nodes representing items generating deviation bound data including a deviation bound for each user and item in the training data set;

learning values for edge weights based on the training data set and the ratings matrix and storing the edge weights in a first weight matrix;

generating an expanded graph data structure including the nodes of the testing data set and additional dummy nodes;

generating a second weight matrix including values from the first weight matrix corresponding to nodes from the testing data set and additional values corresponding to the dummy nodes, the additional values being determined based on a portion of the deviation bound data;

constraining the expanded graph data structure nodes corresponding to the testing data set nodes to a predetermined degree value and not constraining the dummy nodes in the expanded graph data structure;

determining a maximum weight b-matching based on the expanded graph data structure and the second weight matrix, where b is set to the predetermined degree value, and generating an intermediate graph data structure having binary values;

truncating the intermediate graph data structure so that only the nodes corresponding to the nodes of the testing data set remain; and

generating a result graph data structure based on the truncated portion of the intermediate graph data structure as output.

62. The computerized method of claim 61, wherein the determining the maximum weight b-matching includes:

updating a belief value corresponding to each neighboring item node of a selected user node in the expanded graph data structure by passing messages between neighboring nodes until a termination condition is met, each message being based on the second weight matrix values and received messages, where a data content of each message is determined according to a compressed message update rule; and

storing each updated belief value and each received message in an electronic storage associated with the selected user node.

63. The computerized method of claim 62, wherein the generating the result graph includes:

selecting a predetermined number of item nodes matching the selected user node, the matching based on updated belief values of item nodes neighboring the selected user node; and

outputting the selected item nodes.

64. The computerized method of claim 61, wherein the learning includes performing a fast Max-Margin Matrix Factorization (fMMMF) with a logistic loss function.

65. A recommender system comprising:

a first processor adapted to learn edge weights for edges of a graph data structure having a plurality of nodes including a group of user nodes and a group of item nodes and to store the edge weights in a first weight matrix;

a second processor coupled to the first processor and adapted to receive a portion of the graph data structure and the first weight matrix from the first processor, the second processor being further adapted to perform a matching operation using degree distribution data, the degree distribution data being based on deviation bound data including a deviation bound for each user and item in the graph data structure, the deviation bound data determined based on the portion of the graph data structure and a preference matrix corresponding to the graph data structure,

wherein the matching operation includes;

generating an expanded graph data structure including the nodes of the portion of the graph data structure and a plurality of dummy nodes;

generating a second weight matrix including values from the first weight matrix corresponding to nodes from the portion of the graph data structure and additional values corresponding to the dummy nodes, the additional values being determined based on a portion of the deviation bound data;

constraining the expanded graph data structure nodes corresponding to the portion of the graph data structure nodes to a predetermined degree value and not constraining the dummy nodes in the expanded graph data structure;

determining a maximum weight b-matching based on the expanded graph data structure and the second weight matrix, where b is set to the predetermined degree value, the determining including;

updating a belief value corresponding to each neighboring item node of a selected user node in the expanded graph data structure by passing messages between neighboring nodes until a termination condition is met, each message being based on the second weight matrix values and received messages, where a data content of each message is determined according to a compressed message update rule; and

storing each updated belief value and each received message in an electronic storage associated with the selected user node;

truncating the intermediate graph data structure so that only the nodes corresponding to the portion of nodes of the graph data structure remain; and

generating a result graph data structure based on the truncated portion of the intermediate graph data structure as output.

66. The recommender system of claim 65, wherein the generating the result graph includes:

selecting a predetermined number of item nodes matching the selected user node, the matching based on updated belief values of item nodes neighboring the selected user node; and

outputting the selected item nodes.

67. The recommender system of claim 66, wherein the items include members of the opposite sex in a dating application.

68. The recommender system of claim 66, wherein the learning includes performing a fast Max-Margin Matrix Factorization (fMMMF) with a logistic loss function.

69. The recommender system of claim 66, wherein the items include movies.

70. The recommender system of claim 66, wherein the items include books.

71. The recommender system of claim 66, wherein the items include sound recordings.

72. A computer readable medium having software instructions stored thereon for programming a computer to perform post processing on recommendation data, the software instructions, when executed by a processor, cause the processor to perform operations comprising:

receiving a training data set containing a plurality of nodes including a group of user nodes and a group of item nodes;

receiving a ratings matrix representing preferences of users for items in the training data set, with each cell in the ratings matrix containing a value representing a rating of one of the items by one of the users;

receiving a testing data set containing a plurality of nodes including a group of user nodes and a group of item nodes;

generating deviation bound data including a deviation bound for each user and each item in the training data set;

learning values for edge weights in the testing data set based on the training data set and the ratings matrix and storing the edge weights in a first weight matrix, the learning including performing a fast Max-Margin Matrix Factorization routine with a logistic loss function;

generating an expanded graph data structure including nodes of the testing data set and additional dummy nodes;

generating a second weight matrix including values from the first weight matrix corresponding to nodes from the testing data set and additional values corresponding to the dummy nodes, the additional values being determined based on a portion of the deviation bound data;

constraining the expanded graph data structure nodes corresponding to the testing data set nodes to a predetermined degree value and not constraining the dummy nodes in the expanded graph data structure;

determining a maximum weight b-matching based on the expanded graph data structure and the second weight matrix, where b is set to the predetermined degree value, the determining including updating a belief value corresponding to each neighboring item node of a selected user node in the expanded graph data structure by passing messages between neighboring nodes until a termination condition is met, each message being based on the second weight matrix values and received messages, where a data content of each message is determined according to a compressed message update rule, and storing each updated belief value and each received message in an electronic storage associated with the selected user node;

truncating the intermediate graph data structure so that only the nodes corresponding to the nodes of the testing data set remain; and

generating a result graph data structure based on the truncated portion of the intermediate graph data structure as output.

73. The computer readable medium of claim 72, wherein generating the result graph includes:

selecting a predetermined number of item nodes matching the selected user node, the matching based on updated belief values of item nodes neighboring the selected user node; and

outputting the selected item nodes.

74. The computer readable medium of claim 72, wherein the items include movies.

75. The computer readable medium of claim 72, wherein the items include books.

76. The computer readable medium of claim 72, wherein the items include sound recordings.

77. The recommender system of claim 72, wherein the items include members of the opposite sex in a dating application.