Machine optimization devices, methods, and systems

• US 8,631,044 B2
• Filed: 12/11/2009
• Issued: 01/14/2014
• 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
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US13/133,932
• Publication Number:
  US 20120005238A1
• Time in Patent Office: 1,495 Days
• Field of Search: 707/798, 707/999.102, 707/999.002, 709/201
• 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 non-transitory 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 advertisement nodes each representing an advertisement and a second group of phrase nodes each representing a phrase, the first weight matrix including weight values, each representing a bid value for each connection between an advertisement node of the first group and a phrase node of the second group 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 advertisement nodes in the first graph data structure and one of the additional 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 additional 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 to generate an intermediate graph data structure having binary weight values;

truncating the intermediate graph data structure to yield a truncated portion; and

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

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

updating a belief value corresponding to each advertisement node having a connection to a selected phrase node, thereby defining neighboring nodes in the second graph data structure by passing messages between the neighboring nodes until a termination condition is met, each message being based on the additional weight values in the second weight matrix 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 non-transitory computer readable medium of claim 2, wherein the generating the result graph data structure 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 predetermined number of advertisement nodes.

4. The non-transitory 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 non-transitory computer readable medium of claim 1, wherein the degree distribution data includes data provided by an advertiser associated with each advertisement.

6. The non-transitory 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 non-transitory computer readable medium of claim 1, wherein the degree distribution data includes data learned from stored prior advertisement and phrase matching data.

8. The non-transitory computer readable medium of claim 1, wherein the software instructions are configured to execute on a distributed processor.

9. The non-transitory 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 each advertisement node; and

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

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

11. The non-transitory 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 non-transitory 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 advertising nodes and a value of a message received by that respective neighboring advertising node from another node and a weight matrix value corresponding to a potential matching between the respective neighboring advertising node and the other node.

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

14. The non-transitory 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 non-transitory 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 non-transitory computer readable medium of claim 15, wherein the natural language phrase is a natural language search query.

17. The non-transitory computer readable medium of claim 15, wherein the natural language phrase is a natural language advertiser goal.

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 configured to transfer messages between the plurality of processors;

wherein each processor is configured to load and execute software instructions stored on a non-transitory 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 search term, 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 plurality of 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 representing 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 to generate an intermediate graph data structure having binary weight values, the determining including;

updating belief values corresponding to respective neighboring 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 to yield a truncated portion that remains after truncating and a removed portion;

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 neighboring nodes, the matching being determined based on updated belief values of neighbor nodes; and

outputting the selected matching neighboring 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 each search term node of the selected neighboring nodes with a respective one of the advertisement nodes of the selected neighboring 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 a selected search term node and the respective one of the neighboring nodes and a value of a message received by that respective neighboring node from another node and a profit matrix value corresponding to a potential matching between the respective neighboring node and the other node.

22. The distributed processing system of claim 18, wherein the plurality of 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 first 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 configured to perform weight matrix expansion, a weight matrix including values of the profit matrix and additional values associated with the plurality of 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 bipartite graph data structure that correspond to the first bipartite graph data structure to a predetermined degree value and not constraining the plurality of dummy nodes in the second bipartite graph data structure when determining a maximum weight b-matching based on the second bipartite graph data structure, where b is set to the predetermined degree value

to generate an intermediate bipartite graph data structure having binary weight values;

generating a result graph data structure by truncating the intermediate bipartite graph data structure to remove the plurality of 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 data indicating the selected predetermined number of advertiser nodes matching the 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 configured 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 predetermined number of advertiser nodes on a search results page corresponding to the search term node associated with the selected predetermined number of 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 configured 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 having a weight value for each edge of the first bipartite 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 connected respectively by edges to each respective supplier nodes and customer nodes;

generating, using a processor configured to estimate a graph data 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 plurality of 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 the plurality 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 bipartite graph data structure to a predetermined degree value, and leaving the plurality of dummy nodes in the second graph data structure unconstrained while determining a maximum weight b-matching based on the second graph data structure, where b is set to the predetermined degree value to generate an intermediate graph data structure having binary weight values;

truncating the intermediate graph data structure to yield a truncated portion that remains after truncating; 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 configured 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 each supplier node and customer 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 one of the predetermined number of supplier nodes, the selecting of the customer nodes being based on updated belief values; and

outputting data responsive to selected ones of said predetermined number of customer nodes and said predetermined number of supplier nodes resulting from said selecting.

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

48. The computerized method of claim 47, 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.

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

55. A non-transitory 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 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 buyer node and each seller node, the weight matrix portion including weight values for nodes adjacent to each respective buyer node and seller node;

generating, using a processor configured to estimate a 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 plurality of 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 respective ones of the plurality 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 plurality of 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 buyer nodes and seller nodes, with a processor configured 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 buyer node and seller node in storage locations of the electronic memory associated with the each buyer node and seller node;

generating an intermediate graph data structure having binary weight values responsively to a result of said determining a maximum weight b-matching;

truncating the intermediate graph data structure to yield a truncated portion that remains after truncating and a removed portion; and

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

outputting data responsive to the selected buyer nodes and the selected seller nodes resulting from said selecting.

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 connected by an edge of the first graph data structure;

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

generating a second graph data structure that includes nodes 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 connecting 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 connecting 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 while updating, with a processor configured 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 nodes connected by edges 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;

storing each updated belief value and each received message in an electronic storage associated with a respective one of the nodes;

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 connected member nodes matching a member node of interest of the member nodes from the result graph data structure, the selecting being determined based on updated belief values of connected member nodes of the member node of interest; and

outputting the predetermined number of connected member nodes matching the member node of interest.

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

receiving, from an electronic storage, a training data set containing a plurality of nodes having a group of nodes representing users and a group of nodes representing items wherein the users are prospective purchasers, at least some of the training data set being responsive to said users, and the items correspond to products available for purchase and stored in an electronic storage of at least one server;

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 additional 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 additional 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 in a resulting truncated portion of 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.

58. The computerized method of claim 57, 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.

59. The computerized method of claim 58, wherein the generating the result graph data structure 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 predetermined number of item nodes.

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

61. A recommender system comprising:

a first processor configured 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 configured to receive a portion of the graph data structure and the first weight matrix from the first processor, the second processor being further configured 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 predetermined number of dummy nodes, the additional values being determined based on a portion of the deviation bound data;

constraining expanded graph data structure nodes corresponding to nodes of the portion of graph data structure nodes to a predetermined degree value and not constraining the predetermined number of 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 the graph data structure remain; and

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

62. The recommender system of claim 61, wherein the generating the result graph data structure 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 predetermined number of item nodes.

63. The recommender system of claim 62, wherein the item nodes include members of the opposite sex in a dating application.

64. The recommender system of claim 62, wherein the first processor is further configured to perform a fast Max-Margin Matrix Factorization (fMMMF) with a logistic loss function.

65. The recommender system of claim 62, wherein the item nodes include movies.

66. The recommender system of claim 62, wherein the item nodes include books.

67. The recommender system of claim 62, wherein the item nodes include sound recordings.

68. A non-transitory 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 additional 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 additional 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 expanded graph data structure so that only the nodes corresponding to the nodes of the testing data set remain in a resulting truncated portion of the expanded graph data structure; and

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

69. The non-transitory computer readable medium of claim 68, wherein generating the result graph data structure 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 predetermined number of item nodes.

70. The non-transitory computer readable medium of claim 68, wherein the items include movies.

71. The non-transitory computer readable medium of claim 68, wherein the items include books.

72. The non-transitory computer readable medium of claim 68, wherein the items include sound recordings.

73. The non-transitory computer readable medium of claim 68, wherein the items include members of the opposite sex in a dating application.