GRAPH BASED TECHNIQUES FOR PREDICTING RESULTS

• US 20170243127A1
• Filed: 02/18/2016
• Published: 08/24/2017
• Est. Priority Date: 02/18/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: LinkedIn Corporation (Microsoft Corporation)
• Inventors: ZHU, QIANG, CHAO, JOHN, HU, QINGBO
• Granted Patent: US 10,387,788 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 9/4494 data driven
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06N 20/20 Ensemble learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

Techniques are provided for determining predicted results for entities based on relatedness of the entities in a graph of nodes. In an embodiment, the graph of nodes is generated based on the determined relatedness of the entities. A node in the graph of nodes represents an entity, and nodes representing entities with known results are assigned those results as their respective node values. The assigned node values are then propagated between the neighboring nodes throughout the graph of nodes in the amount determined by the relatedness of the nodes. Based on the propagation, node values for entities with unknown results are determined and represent the predicted results for those entities. Additionally, various classifiers may be combined with the propagated node values to increase the accuracy of the predicted results.

Claims

1. A method comprising:

for each entity of a plurality of entities, identifying a respective plurality of attribute values;

generating a graph of nodes that comprises a plurality of nodes and a plurality of edges, wherein each node in the plurality of nodes represents a respective entity of the plurality of entities and is connected to one or more neighbor nodes with one or more edges of the plurality of edges;

for each edge of the plurality of edges;

determining that a first node is connected to a second node by said each edge;

identifying a first set of attribute values of a first entity, of the plurality of entities, that is represented by the first node;

identifying a second set of attribute values of a second entity, of the plurality of entities, that is represented by the second node;

calculating an edge value for said each edge based on the first set of attribute values and the second set of attribute values;

for each node of the plurality of nodes;

calculating a node value of said each node based on one or more node values of one or more neighbor nodes of said each node and one or more edge values with which said each node is associated; and

storing the node value in association with the entity that is represented by said each node.

2. The method of claim 1, further comprising, prior to calculating:

assigning, to a node value of each first node in a first subset of the plurality of nodes, a positive label value that indicates a positive label of a respective first entity associated with said each first node in the first subset;

assigning, to a node value of each second node in a second subset of the plurality of nodes, a negative label value that indicates a negative or unknown label of a respective second entity associated with said each second node in the second subset.

3. The method of claim 1, further comprising, for each iteration in a plurality of iterations, calculating, for each node in the plurality of nodes a new node value based on the one or more corresponding edge values and one or more previous node values, associated with the one or more neighbor nodes, determined at a previous iteration.

4. The method of claim 3, further comprising terminating the plurality of iterations when a maximum of differences between calculated new node values at an iteration and corresponding node values at a particular previous iteration is less than a particular threshold value.

5. The method of claim 3, after said each iteration but before next iteration:

to a node value of each first node in a first subset of the plurality of nodes, assigning a positive label value that indicates a positive label of a respective first entity associated with said each node in the first subset;

to a node value of each second node in a second subset of the plurality of nodes, assigning a negative label value that indicates a negative label of a respective second entity associated with said each node in the second subset.

6. The method of claim 1, further comprising disconnecting a particular neighbor node of said one or more neighbor nodes when an edge value for an edge connecting said each node with the particular neighbor node is less than a threshold edge value.

7. The method of claim 1, wherein the plurality of attributes values correspond to a plurality of attributes that includes a particular attribute, the method further comprising:

for the plurality of entities, identifying a plurality of original attribute values that correspond to the particular attribute;

determining a maximum original attribute value and a minimum original attribute value from the plurality of original attribute values;

for each entity of the plurality of entities, calculating an attribute value for the particular attribute based on the maximum original attribute value, the minimum original attribute value, and an original attribute value, of the plurality of original attribute values, that is associated with said each entity.

8. The method of claim 1, wherein calculating the node value of said each node is further based on a special value of a particular classifier for the respective entity.

9. The method of claim 8, wherein the particular classifier is determined using a regression.

10. The method of claim 8, further comprising:

calculating a propagation value based on the one or more node values of the one or more neighbor nodes and the one or more corresponding edge values;

calculating the node value of said each node based on the special value weighted with a first weight value and based on the propagation value weighted with a second weight value.

11. The method of claim 10, wherein the first weight value depends on the second weight value.

12. The method of claim 1, further comprising assigning a rank value to the respective entity of said each node based on comparison of the node value, of said each node, to node values of other nodes in the plurality of nodes.

13. The method of claim 1, further comprising:

displaying the graph of nodes to a user that includes displaying, for each particular node in the graph of nodes;

a particular node value of said each particular node in the graph of nodes,

a particular entity associated with said each particular node in the graph of nodes, and

connections to one or more particular neighbor nodes associated with said each particular node in the graph of nodes.

14. A system comprising:

one or more processors;

one or more storage media storing instructions which, when executed by the one or more processors, cause performing of a method comprising;

for each entity of a plurality of entities, identifying a respective plurality of attribute values;

generating a graph of nodes that comprises a plurality of nodes and a plurality of edges, each node in the plurality of nodes represents a respective entity of the plurality of entities and is connected to one or more neighbor nodes with one or more edges of the plurality of edges;

for each edge of the plurality of edges;

determining that a first node is connected to a second node by said each edge;

identifying a first set of attribute values of a first entity, of the plurality of entities, that is represented by the first node;

identifying a second set of attribute values of a second entity, of the plurality of entities, that is represented by the second node;

calculating an edge value for said each edge based on the first set of attribute values, and the second set of attribute values;

for each node of the plurality of nodes;

calculating a node value of said each node based on one or more node values of one or more neighbor nodes of said each node and one or more edge values with which said each node is associated; and

storing the node value in association with the entity that is represented by said each node.

15. The system of claim 14, wherein the method further comprises, prior to calculating:

assigning, to a node value of each first node in a first subset of the plurality of nodes, a positive label value that indicates a positive label of a respective first entity associated with said each first node in the first subset;

assigning, to a node value of each second node in a second subset of the plurality of nodes, a negative label value that indicates a negative or unknown label of a respective second entity associated with said each second node in the second subset.

16. The system of claim 14, wherein the method further comprises, for each iteration in a plurality of iterations, calculating, for each node in the plurality of nodes a new node value based on the one or more corresponding edge values and one or more previous node values, associated with the one or more neighbor nodes, determined at a previous iteration.

17. The system of claim 16, wherein the method further comprises terminating the plurality of iterations when a maximum of differences between calculated new node values at an iteration and corresponding node values at a particular previous iteration is less than a particular threshold value.

18. The system of claim 16, wherein the method further comprises after said each iteration but before next iteration:

to a node value of each first node in a first subset of the plurality of nodes, assigning a positive label value that indicates a positive label of a respective first entity associated with said each node in the first subset;

to a node value of each second node in a second subset of the plurality of nodes, assigning a negative label value that indicates a negative label of a respective second entity associated with said each node in the second subset.

19. The system of claim 14, wherein the method further comprises disconnecting a particular neighbor node of said one or more neighbor nodes when an edge value for an edge connecting said each node with the particular neighbor node is less than a threshold edge value.

20. The system of claim 14, wherein the plurality of attributes values correspond to a plurality of attributes that includes a particular attribute, the method further comprising:

for the plurality of entities, identifying a plurality of original attribute values that correspond to the particular attribute;

determining a maximum original attribute value and a minimum original attribute value from the plurality of original attribute values;

for each entity of the plurality of entities, calculating an attribute value for the particular attribute based on the maximum original attribute value, the minimum original attribute value, and an original attribute value, of the plurality of original attribute values, that is associated with said each entity.

21. The system of claim 14, wherein calculating the node value of said each node is further based on a special value of a particular classifier for the respective entity.

22. The system of claim 21, wherein the particular classifier is determined using a regression.

23. The system of claim 21, wherein the method further comprises:

calculating a propagation value based on the one or more node values of the one or more neighbor nodes and the one or more corresponding edge values;

calculating the node value of said each node based on the special value weighted with a first weight value and based on the propagation value weighted with a second weight value.

24. The system of claim 23, wherein the first weight value depends on the second weight value.

25. The system of claim 14, wherein the method further comprises assigning a rank value to the respective entity of said each node based on comparison of the node value, of said each node, to node values of other nodes in the plurality of nodes.

26. The system of claim 14, wherein the method further comprises:

displaying the graph of nodes to a user that includes displaying, for each particular node in the graph of nodes;

a particular node value of said each particular node in the graph of nodes,

a particular entity associated with said each particular node in the graph of nodes, and

connections to one or more particular neighbor nodes associated with said each particular node in the graph of nodes.