Reducing churn in knowledge graphs

• US 10,540,345 B2
• Filed: 12/09/2016
• Issued: 01/21/2020
• Est. Priority Date: 12/09/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Huang, Chiyuan, Sinha, Arnab
• Primary Examiner(s): Ly, Cheyne D
• Application Number:
  US15/374,962
• Publication Number:
  US 20180165352A1
• Time in Patent Office: 1,138 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Reductions in churn for assigning identifiers to entities in a knowledge graph enables several improvements to the functionality of the computing devices maintaining or accessing knowledge graphs. As the aliases or other terms used to identify a given entity change in response to updates to the knowledge graph, the identifiers assigned to various entities may change. For example, two individual entities conflated as one node may be split into two or two nodes merged into one in response to an update, and existing identifiers should be used to reduce churn. To select the existing identifiers to assign to a given updated entity, the aliases are clustered with the updated entities and the unique modal prior identifier is assigned as the identifier for the updated entity. Higher orders of modality are used to ensure as many existing identifiers are used before creating new identifiers.

Claims

1. A method for reducing churn in identifier assignment for entities in a knowledge graph, comprising:

identifying a plurality of aliases for a plurality of entities maintained in the knowledge graph, wherein each alias of the plurality of aliases is associated with one entity of the plurality of entities, and wherein each entity of the plurality of entities is associated with an entity identifier;

for each alias of the plurality of aliases, associating the alias with the entity identifier for the entity to which the alias is associated; and

in response to an update to the knowledge graph;

clustering the plurality of aliases based on the update into a plurality of alias clusters, wherein each alias retains the association with the entity identifier made prior to the update; and

for each alias cluster of the plurality of alias clusters, associating the alias cluster with one entity of the plurality of entities by assigning an entity identifier of the one entity to the alias cluster, wherein assigning the entity identifier of the one entity to the alias cluster comprises;

identifying each unique entity identifier associated with aliases of the alias cluster;

for each unique entity identifier, determining a number of the aliases associated with the entity identifier;

identifying, as a most frequent entity identifier, one entity identifier among each unique entity identifier that has a highest determined number of the aliases associated; and

assigning the most frequent entity identifier to the alias cluster and to the aliases of the alias cluster.

2. The method of claim 1, wherein the knowledge graph is maintained across multiple computing devices.

3. The method of claim 1, wherein if the one entity identifier is identified as the most frequent entity identifier for multiple alias clusters, further comprising:

for each of the multiple alias clusters, determine a number of aliases associated with the most frequent entity identifier;

determining the alias cluster that has a highest number of aliases associated with the most frequent entity identifier;

assigning the most frequent entity identifier to the alias cluster determined to have the highest number of aliases associated with the most frequent entity identifier; and

for each remaining alias cluster from the multiple alias clusters;

identifying, as a next-most frequent entity identifier, another entity identifier that has a next highest number of the aliases associated; and

assigning the next-most frequent entity identifier to the remaining alias cluster.

4. The method of claim 3, wherein the next-most frequent entity identifier is a null entity identifier, further comprising:

creating a new entity identifier; and

setting the new entity identifier as the next-most frequent entity identifier.

5. The method of claim 1, wherein if multiple entity identifiers among each unique entity identifier are determined to have the same highest number of the aliases associated, selecting one of the multiple entity identifiers to identify as the most frequent entity identifier.

6. The method of claim 5, wherein if one of the multiple entity identifiers is a null entity identifier, excluding the null entity identifier from selection.

7. The method of claim 5, wherein selecting one of the multiple entity identifiers to identify as the most frequent entity identifier further comprises:

determining whether a particular entity identifier of the multiple entity identifiers is identified as-the most frequent entity identifier of another alias cluster;

in response to determining that the particular entity identifier is identified as the most frequent entity identifier of another alias cluster, excluding the particular entity identifier from selection.

8. The method of claim 1, wherein the update to the knowledge graph includes:

adding new nodes to the knowledge graph;

removing existing nodes from the knowledge graph; and

adjusting edges between nodes in the knowledge graph.

9. A system for reducing churn in identifier assignment for entities in a knowledge graph, comprising:

a processor; and

a memory storage device including instructions that when executed by the processor are operable to;

maintain aliases in association with the entities from the knowledge graph, wherein each alias is associated in an alias cluster with an entity identifier; and

in response to an update to the knowledge graph;

produce a plurality of-updated alias clusters, wherein each alias retains the association with the entity identifier made prior to the update; and

for each updated alias cluster of the plurality of updated alias clusters, associate the updated alias cluster with one entity of the entities from the knowledge graph by assigning an entity identifier of the one entity to the updated alias cluster, wherein assigning the entity identifier of the one entity to the updated alias cluster comprises;

identifying each unique entity identifier associated with aliases of the updated alias cluster;

for each unique entity identifier, determining a number of the aliases associated with the entity identifier;

identifying, as a modal entity identifier of the updated alias cluster, one entity identifier among each unique entity identifier that has a highest determined number of the aliases associated; and

assigning the modal entity identifier to the updated alias cluster and to the aliases of the updated alias cluster.

10. The system of claim 9, wherein the system is configured in a distributed system to reduce churn in the knowledge graph as multiple instances operating in parallel.

11. The system of claim 9, wherein in response to identifying a multi-modal cluster in which multiple entity identifiers are identified as the modal entity identifier, the instructions when executed by the processor are further operable to:

determine whether the multiple entity identifiers are the modal entity identifier for other updated alias clusters; and

in response to determining that one of the multiple entity identifiers is not the modal entity identifier for the other updated alias clusters, assign the one of the multiple entity identifiers as the modal entity identifier for the updated alias cluster.

12. The system of claim 11, wherein in response to determining that at least two of the multiple entity identifiers are not the modal entity identifier for the other updated alias clusters, the instructions when executed by the processor are further operable to randomly select one of the at least two of the multiple entity identifiers as the modal entity identifier for the updated alias cluster.

13. The system of claim 11, wherein in response to determining that all of the multiple entity identifiers are the modal entity identifier for the other updated alias clusters, the instructions when executed by the processor are further operable to:

determine whether a number of aliases defining the modal entity identifier for a particular updated alias cluster of the other updated alias clusters is less than a number of aliases defining the modal entity identifier for the updated alias cluster;

in response to determining that the number of aliases defining the modal entity identifier for the particular updated alias cluster is less than the number of aliases defining the modal entity identifier for the updated alias cluster;

assign the modal entity identifier to the updated alias cluster,

determine a subsequent modal entity identifier for the particular updated alias cluster, and

assign the subsequent modal entity identifier as the modal entity identifier for the particular updated alias cluster; and

in response to determining that the number of aliases defining the modal entity identifier for the particular updated alias cluster is not less than the number of aliases defining the modal entity identifier for the updated alias cluster;

determine the subsequent modal entity identifier for the updated alias cluster, and

assign the subsequent modal entity identifier as the modal entity identifier for the updated alias cluster.

14. The system of claim 9, wherein, in response to the one entity identifier being identified as the modal entity identifier for multiple updated alias clusters, the instructions when executed by the processor are further operable to:

for each of the multiple updated alias clusters, determine a number of aliases associated with the one entity identifier;

determine an updated alias cluster of the multiple updated alias clusters having a highest determined number of aliases associated with the one entity identifier; and

assign the one entity identifier to the updated alias cluster.

15. The system of claim 14, wherein, in response to assigning the one entity identifier to the updated alias cluster, the instructions when executed by the processor are further operable to treat a subsequent order modal entity identifier for other updated alias clusters of the multiple updated alias clusters as the modal entity identifier.

16. The system of claim 15, wherein the subsequent order modal entity identifier is null, and the instructions when executed by the processor are further operable to:

create a new entity identifier; and

assign the new entity identifier as the modal entity identifier.

17. A computer readable storage device including instructions reducing churn in identifier assignment for entities in a knowledge graph that when executed by a processor in response to an update to the knowledge graph comprise:

clustering, based on the update, a plurality of entity aliases into a plurality of alias clusters, wherein each alias is associated with a pre-update entity identifier to which each alias was associated prior to the update; and

for each alias cluster of the plurality of alias clusters, associating the alias cluster with one entity in the knowledge graph by assigning an entity identifier of the one entity to the alias cluster, wherein assigning the entity identifier of the one entity to the alias cluster comprises;

identifying each unique entity identifier associated with aliases of the alias cluster;

for each unique entity identifier, determining a number of the aliases associated with the entity identifier;

identifying, as a most frequent entity identifier, one entity identifier among each unique entity identifier that has a highest determined number of the aliases associated; and

assigning the most frequent entity identifier to the alias cluster and the aliases of the alias cluster.

18. The computer readable storage device of claim 17, wherein, in response to determining multiple entity identifiers among each unique entity identifier have the same highest determined number of the aliases associated, selecting one of the multiple entity identifiers as the most frequent entity identifier based on:

whether the one of the multiple entity identifiers is identified as the most frequent entity identifier for other alias clusters;

whether the other alias clusters include a higher number of aliases associated with the one of the multiple entity identifiers than the alias cluster; and

whether the one of the multiple entity identifiers is a null entity identifier.

19. The computer readable storage device of claim 17, wherein in response to determining that multiple alias clusters of the plurality of alias clusters share the one entity identifier as the most frequent entity identifier, further comprising:

setting the most frequent entity identifier-for one alias cluster of the multiple alias clusters; and

for each alias of the multiple alias clusters aside from the one alias cluster;

identifying, as a next-most frequent entity identifier, another entity identifier; and

setting the next-most frequent entity identifier for the alias cluster.

20. The computer readable storage device of claim 19, wherein the one alias cluster of the multiple alias clusters is selected based on which alias cluster of the multiple alias clusters has a highest number of aliases associated with the most frequent entity identifier.