Patent ID: 9195941
Filing Date: 2015-11-24
Classification: G06N,G06Q

Abstract:
1. A system for predicting a relation between entities comprising: a memory storage device; a computer system associated with said memory storage device, said computer system including a processor device configured to perform a method to: construct, at a computer device, a heterogeneous graph representation of multi-source data including: compute at said computer device, a steady-state relevance matrix for each sub-graph using a homogeneous Markov Random Walk model applied to each said unipartite sub-graph, wherein to apply said homogeneous Markov Random Walk model, said processor device is further configured to compute a transition probability matrix for each said unipartite sub-graph, said computing said steady-state relevance matrix associated with a respective unipartite sub-graph based on a respective computed transition probability matrix; and said processor device is further configured to compute state probability matrices at transition times t and t+1, where a computed state probability matrix at time t+1 is a function of a computed state probability matrix at time t, said computed transition probability matrix, a computed matrix representing a uniform prior state for all the vertices of said a unipartite graph, and for a modeled random walker time transition between vertices in said sub-graph, a restart probability value for said unipartite sub-graph; dynamically generate missing edges connecting vertices between each of two unipartite sub-graphs by applying, using said computed steady-state relevance matrix for each sub-graph, an iterative and heterogeneous Markov Random Walk model to said bipartite sub-graphs to dynamically generate missing edges, wherein a generated missing edge represents a cross-entity connection recommendation or prediction in said heterogeneous graph, and wherein a first unipartite sub-graph type of said multiple unipartite sub-graphs comprises vertices representing a plurality of different users, a second unipartite sub-graph type of said multiple unipartite sub-graph comprises vertices representing a plurality of items, and a third unipartite sub-graph type of multiple unipartite sub-graph comprises vertices representing a plurality of different entity types; wherein edges connecting a sub-set of different vertices in said first type of unipartite sub-graph have different edge weights according to observed user affinity measures between different users, wherein edges connecting a sub-set of different vertices in said second type of unipartite graph have different edge weights according to observed item similarity measures between different items; and edges connecting a sub-set of different vertices of said third type unipartite graph have different edge weights according to observed measures describing relationships between different entities; wherein a computed steady-state relevance matrix associated with said first type of unipartite sub-graph is a function of a transition probability computed for the users, and a computed normalized matrix representing an affinity of the user to other users as represented in said first type unipartite graph, a computed steady-state relevance matrix associated with said second type of unipartite sub-graph is a function of a transition probability matrix for the items, and a computed normalized matrix representing a similarity of an item to other items as represented in said second type unipartite graph, and a restart probability value for said second type sub-graph; and, a computed steady-state relevance matrix associated with said third entity type unipartite sub-graph is a function of a transition probability matrix for the entities, a computed normalized matrix representing a similarity of an entity to other entities in said entity type of unipartite graph, and a restart probability in said entity sub-graph.