System and method for real-time graph-based recommendations
Systems and methods for generating real-time, personalized recommendations are disclosed. In one embodiment, a method operates upon an electronic data collection organized as a network of vertices and edge connections between the vertices. The method provides the recommendations includes iteratively traversing across edges that satisfy search criteria to a new set of vertices and filtering each new set of vertices to satisfy the search criteria. At the conclusion of the traversing and filtering, a final set of vertices represents the recommended entities. In some embodiments, a control vector describes a sequence of relationships between a requester and the items to be recommended. The method can assign scores to candidate recommendations and select the recommendations having the highest scores. Advantageously, the method provides flexibility and rapid execution of recommendation queries without the need to precompute intermediate results.
1. A method for providing a recommendation to a request based on a graph having one or more edges each connecting a source vertex and an endpoint vertex, comprising:
providing a control vector to one or more subgraph processors, the control vector defines a set of relationship edges and target vertices for each of the source vertices in response to the request;
identifying a current set of source vertices from the provided control vector via the subgraph processors;
traversing the identified current set of source vertices to a current set of endpoint vertices based on the set of relationship edges and the target vertices of the control vector for the current set of source vertices via the subgraph processors;
selecting any of the endpoint vertices as recommended vertices that satisfy the provided control vector via the subgraph processors;
iteratively repeating said identifying, traversing, and selecting, wherein the current set of endpoint vertices becomes the current set of source vertices for each subsequent iteration of said identifying, and each subsequent iteration of said identifying, traversing, and selecting occurring only when all of the subgraph processors have completed a current iteration; and
returning the selected endpoint vertices representing the recommendation to the request, wherein said providing the control vector comprises providing one or more iteration control objects each defining one or more selected source vertices and one or more edges that can be traversed from each selected source vertex.
2. The method of claim 1 , wherein each of the iteration control objects further defines a set of restricted target vertices that limit the one or more edges and the endpoint vertices that can be traversed from each selected source vertex.
3. The method of claim 1 , wherein said providing the iteration control objects further comprises defining the one or more edges that can be traversed as a set of conditional statements.
4. The method of claim 1 , further comprising assigning a score to each of the relationship edges and target vertices, and wherein said selecting is further based on the assigned scores.
5. The method of claim 1 , further comprising translating the request into the control vector.
6. The method of claim 5 , wherein said translating maps at least one portion of the request into a vertex type, a vertex, an edge type, or an edge.
7. The method of claim 1 , wherein said providing the control vector includes providing a Directed Acyclic Graph or a Finite State Machine.
8. A method for providing a control vector to a graph-based recommendation system in response to a request, the graph having one or more edges, each of the one or more edges connecting a source vertex and an endpoint vertex, the method comprising:
defining a set of relationship edges and target vertices for each of the source vertices in response to the request, the set of relationship edges providing at least one graph traversal path of the graph;
identifying a set of source vertices as seed vertices based on the defined set of relationship edges and target vertices for each of the source vertices;
generating one or more iteration control objects each defining one or more selected source vertices and one or more edges that can be traversed from each selected source vertex;
providing the defined set of relationship edges and the identified seed vertices to one or more subgraph processors of the graph-based recommendation system; and
iteratively traversing the graph via the subgraph processors based on the provided defined set of relationship edges and the identified seed vertices to define a set of recommended vertices, each subsequent iteration occurring only when all of the subgraph processors have completed a current iteration, wherein said one or more subgraph processors performs said identifying for each subsequent iteration.
9. The method of claim 8 , wherein each iteration control object further defines a set of restricted end vertices that limit the one or more edges that can be traversed from each of the selected source vertices.
10. The method of claim 8 , wherein said providing the iteration control objects further comprises defining the one or more edges that can be traversed as a set of conditional statements.
11. The method of claim 8 , wherein said providing the defined set of relationship edges and the identified seed vertices includes providing a Directed Acyclic Graph or a Finite State Machine.
12. A system for providing a recommendation to a request based on a graph having one or more edges, each of the one or more edges connecting a source vertex and an endpoint vertex, the system comprising:
one or more subgraph processors for traversing the graph; and
a system manager for providing a control vector to said subgraph processors, the control vector defining a set of relationship edges and target vertices for each of the source vertices in response to the request,
wherein each subgraph processor iteratively identifies a current set of source vertices from the provided control vector; traverses the identified current set of source vertices to a current set of endpoint vertices based on the set of relationship edges and the target vertices of the control vector for the current set of source vertices, selects any of the endpoint vertices as recommended vertices that satisfy the provided control vector, wherein the current set of endpoint vertices becomes the current set of source vertices for each subsequent iteration and returns the selected endpoint vertices representing the recommendation to the request, wherein said system manager provides the control vector as one or more iteration control objects each defining one or more selected source vertices and one or more edges that can be traversed from each selected source vertex, and each subsequent iteration of identifying, traversing, and selecting via the subgraph processors occurring only when all of the subgraph processors have completed a current iteration.
13. The system of claim 12 , wherein each iteration control object further defines a set of restricted target vertices that limit the one or more edges and the endpoint vertices that can be traversed from each selected source vertex.
14. The system of claim 12 , wherein each subgraph processor further assigns a weight to each of the relationship edge and target vertices to limit the one or more edges that can be traversed from each selected source vertex.
15. The system of claim 12 , further comprising a translation module for translating the request into the control vector.
16. The system of claim 15 , wherein the translation module maps at least one portion of the request into a vertex type, a vertex, an edge type, or an edge.
17. The system of claim 12 , wherein said system manager provides the control vector as a Directed Acyclic Graph or a Finite State Machine.