PREDICTIVE AND DESCRIPTIVE ANALYSIS ON RELATIONS GRAPHS WITH HETEROGENEOUS ENTITIES

摘要

A method provides a random walk model with heterogeneous graphs to leverage multiple source data and accomplish prediction tasks. The system and method components include: 1) A heterogeneous graph formulation including heterogeneous instances of abstract objects as graph nodes and multiple relations as edges connecting those nodes. The different types of relations, such as client-vendor relation and client-product relation, are often quantified as the weights of edges connecting those entities; 2) To accomplish prediction tasks with such information, launching a multi-stage random walk model over the heterogeneous graph. The random walk within a subgraph with homogenous nodes usually produces the relevance between entities of the same type. The random walk across different type of nodes provides the prediction of decisions, such as a client purchasing a product.

主权项

1. A method of predicting a relation between entities comprising:
constructing, at a computer device, a heterogeneous graph representation of multi-source data including: receiving data for forming multiple unipartite sub-graphs, each sub-graph having homogeneous vertices and edges connecting said vertices, and receiving data for forming bipartite sub-graphs having partially observed edges connecting respective nodes between any two different unipartite sub-graphs, said partially observed edges representing cross-entity links; computing 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; dynamically generating 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, wherein a programmed processor unit of said computer device performs said receiving, constructing, applying said first Markov Random Walk model to each said unipartite sub-graph and applying said iterative Markov Random Walk model to said bipartite sub-graphs.