Machine learning and prediction using graph communities

Patent metadata

Field	Value
Publication number	US-10872298-B2
Application number	US-201716311024-A
Country	US
Kind code	B2
Filing date	Jul 11, 2017
Priority date	Jul 11, 2016
Publication date	Dec 22, 2020
Grant date	Dec 22, 2020

Abstract

Embodiments of the invention are directed to methods and devices for predicting interactions. One embodiment is directed to a method comprising receiving, by one or more computers, interaction data for a plurality of known interactions between resource providers and users, and creating a topological graph based on the plurality of known interactions. The method may further comprise determining, by the one or more computers, a plurality of communities to form a predictive model, and receiving a request for a prediction. In addition, the method may comprise applying the request to the predictive model, by the one or more computers, by identifying a community in the plurality of communities corresponding to the request, determining a node within the identified community, and providing information regarding the node as the requested prediction.

First claim

What is claimed is:

1. A method comprising:
a) receiving, by one or more computers, interaction data for a plurality of known interactions between resource providers and users;
b) creating, by the one or more computers, a topological graph based on the plurality of known interactions, the topological graph comprising nodes and edges;
c) determining, by the one or more computers, a plurality of communities to form a predictive model, each community comprising a dense collection of nodes connected by edges;
d) receiving, by the one or more computers, a request for a prediction;
e) applying the request to the predictive model, by the one or more computers, by identifying a community in the plurality of communities corresponding to the request;
f) determining, by the one or more computers, a node within the identified community; and
g) providing, by the one or more computers, information regarding the node as the requested prediction, wherein the plurality of communities in step c) are determined by:
h) computing a weight of each edge in the topological graph;
i) computing a weight of each node in the topological graph based on the computed weights of each of the edges;
j) generating a queue comprising the nodes in decreasing order by weight;
k) selecting a seed node from the queue, the seed node being a highest weighted node in the queue;
l) generating a community comprising the seed node;
m) calculating an interaction probability for each candidate node not included in the community, the interaction probability being a probability of a node not included in the community interacting with a node included in the community;
n) determining a highest priority node based on the interaction probabilities calculated in step m);
o) determining if the highest priority node meets predefined criteria;
p) adding the highest priority node to the community if it is determined at step o) that the highest priority meets the predefined criteria;
q) repeating steps m) through p) until it is determined at step o) that the highest priority node does not meet the predefined criteria;
r) outputting the community, the community comprising a unique identifier for the community and identifiers for the nodes included in the community;
s) removing from the queue, the nodes included in the community; and
t) repeating steps k) through s) until the queue is empty, each community outputted at step r) being a community in the plurality of communities that forms the predictive model.

2. The method of claim 1 , wherein the interaction probability for each candidate node calculated at step m) is calculated as: a total number of edges shared between the candidate node and the nodes included in the community, divided by the number of nodes included in the community.

3. The method of claim 1 , wherein determining if the highest priority node meets the predefined criteria at step p) comprises:
determining if the interaction probability for the highest priority node is greater than or equal to a predetermined threshold required for addition to the community.

4. The method of claim 3 , wherein determining if the highest priority node meets the predefined criteria further comprising:
determining whether or not an addition of the highest priority node to the community would cause a diameter of the community, or an average length of shortest paths between nodes included in the community, to increase beyond a pre-established boundary.

5. The method of claim 1 , wherein the request for the prediction includes data comprising one or more of: an account identifier of a user, a location of the user, a type of resource provider, and user inputted text.

6. The method of claim 5 , wherein determining the node within the identified community in step f) comprises:
determining a path comprising nodes connected in the identified community by edges, the path including a node for the account identifier of the user;
traversing the path starting from the node for the account identifier of the user;
terminating the traversal upon traversal of a last traversed node associated with the data included in the request for the prediction; and
outputting an identifier for the last traversed node associated with the data.

7. The method of claim 1 , further comprising:
receiving meta-information for a first resource provider;
querying the topological graph for a twin node for a second resource provider associated with the meta-information; and
generating a new node relating to interaction data for the twin node.

8. A computer comprising:
a processor;
a network interface; and
a non-transitory computer readable medium, the computer readable medium comprising code, executable by the processor, instructing the computer to:
a) receive interaction data for a plurality of known interactions between resource providers and users;
b) create a topological graph based on the plurality of known interactions, the topological graph comprising nodes and edges;
c) determine a plurality of communities to form a predictive model, each community comprising a dense collection of nodes connected by edges;
d) receive a request for a prediction;
e) apply the request to the predictive model by identifying a community in the plurality of communities corresponding to the request;
f) determine a node within the identified community; and
g) provide information regarding the node as the requested prediction,
wherein the instruction to determine a plurality of communities to form a predictive model comprises a method that includes the steps of:
h) computing a weight of each edge in the topological graph;
i) computing a weight of each node in the topological graph based on the computed weights of each of the edges;
j) generating a queue comprising the nodes in decreasing order by weight;
k) selecting a seed node from the queue, the seed node being a highest weighted node in the queue;
l) generating a community comprising the seed node;
m) calculating an interaction probability for each candidate node not included in the community, the interaction probability being a probability of a node not included in the community interacting with a node included in the community;
n) determining a highest priority node based on the interaction probabilities calculated in step m);
o) determining if the highest priority node meets predefined criteria;
p) adding the highest priority node to the community if it is determined at step o) that the highest priority meets the predefined criteria;
q) repeating steps m) through p) until it is determined at step o) that the highest priority node does not meet the predefined criteria;
r) outputting the community, the community comprising a unique identifier for the community and identifiers for the nodes included in the community;
s) removing from the queue, the nodes included in the community; and
t) repeating steps k) through s) until the queue is empty, each community outputted at step r) being a community in the plurality of communities that forms the predictive model.

9. The computer of claim 8 , wherein the interaction probability for each candidate node calculated at step m) is calculated as: a total number of edges shared between the candidate node and the nodes included in the community, divided by the number of nodes included in the community.

10. The computer of claim 8 , wherein determining if the highest priority node meets the predefined criteria at step p) comprises:
determining if the interaction probability for the highest priority node is greater than or equal to a predetermined threshold required for addition to the community.

11. The computer of claim 10 , wherein the method det

Assignees

• Visa Int Service Ass

Inventors

• Harris Theodore D
• O'Connell Craig
• Angelos Terry
• Korolevskaya Tatiana
• Li Yue
• Sawyer Todd

Classifications

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06Q30/0631

  Recommending goods or services · CPC title

• G06Q30/0202

  Market predictions or forecasting for commercial activities · CPC title

• G06N5/04

  Inference or reasoning models · CPC title

• G06N5/022 Primary

  Knowledge engineering; Knowledge acquisition · CPC title