Multi-hop search for entity relationships
An unsupervised multi-hop search across a corpus of documents in a database or other data resource permits the identification of relationships between two entities mentioned in the corpus in cases where the two entities are not co-mentioned within any documents in the corpus (or not mentioned within document(s) with sufficient frequency or proximity to infer the relationship). The search can employ a beam search algorithm anchored by word embeddings and an A* graph traversal to calculate semantic distance between the entities as different paths through the corpus for different entity co-mentions are evaluated.
1. A computer program product comprising computer executable code embodied in a non-transitory computer readable medium that, when executing on one or more computing devices, performs the steps of:
causing a search of a corpus of documents to obtain a search result including a plurality of documents each mentioning at least one of two entities;
automatically identifying a subset of the plurality of documents wherein each document in the subset contains a co-mention of both of the two entities, wherein the co-mention of both of the two entities comprises mentions of both of the two entities within a same sentence or in adjacent sentences or other surrounding text, in accordance with a rule or a metric used to identify the co-mention of the two entities;
in response to determining that a number of co-mentions of both of the two entities in the subset is above a predetermined threshold, identifying and substantiating a relationship between the two entities based on text in the documents belonging to the subset;
in response to determining that the number of co-mentions of both of the two entities in the subset is below the predetermined threshold, initiating an unsupervised multi-hop search within the plurality of documents for identifying and substantiating the relationship between the two entities through an intermediate third entity forming a chain of co-mentions between the first entity and the second entity, by:
ranking one or more additional entities co-mentioned in the plurality of documents with a first one of the two entities based on graph centrality over normalized entity identifiers;
iteratively evaluating the one or more additional entities with a beam search algorithm using an A* graph search to calculate a distance from the first one of the two entities to a second one of the two entities; and
determining an entity from the one or more additional entities that provides a smallest value for the distance from the first one of the two entities to the second one of the two entities and selecting this entity as the third entity; and
in response to locating the relationship between the two entities through the third entity, providing an identifier for the third entity and one or more segments of text substantiating a supporting co-mention of the third entity and the first one of the two entities.
2. The computer program product of claim 1 wherein using an A* graph search to calculate the distance includes calculating a text embedding to one or more top ranked ones of the one or more additional entities.
3. The computer program product of claim 2 wherein the text embedding uses a universal text embedding for natural language processing.
4. The computer program product of claim 1 further comprising code that performs the step of receiving a selection of the two entities from a user in a user interface.
5. The computer program product of claim 1 further comprising creating a knowledge graph for display in a user interface showing the relationship among the two entities and the third entity.
6. A computer program product comprising computer executable code embodied in a non-transitory computer readable medium that, when executing on one or more computing devices, performs the steps of:
causing a search of a corpus of documents to obtain a search result including a plurality of documents each mentioning one or more of two entities including a first entity and a second entity;
automatically identifying a subset of the plurality of documents wherein each document in the subset contains a co-mention of both of the two entities, wherein the co-mention of both of the two entities comprises mentions of both of the two entities within a same sentence or in adjacent sentences or other surrounding text, in accordance with a rule or a metric used to identify the co-mention of the two entities;
in response to determining that a number of co-mentions of both of the two entities in the subset is below a predetermined threshold, initiating an unsupervised multi-hop search for identifying and substantiating a relationship between the two entities through an intermediate third entity forming a chain of co-mentions with at least one of the first entity and the second entity in one or more of the plurality of documents; and
in response to locating the relationship between the two entities through the third entity, providing an identifier for the third entity and one or more segments of text substantiating the relationship with a supporting co-mention of the third entity and at least one of the two entities.
7. The computer program product of claim 6 further comprising code that performs the step of updating a knowledge graph containing the first entity and the second entity to include the relationship.
8. The computer program product of claim 7 wherein the relationship is represented in the knowledge graph as a direct relationship between the first entity and the second entity.
9. The computer program product of claim 7 wherein the relationship is represented in the knowledge graph as an indirect relationship between the first entity and the second entity through the third entity.
10. The computer program product of claim 7 further comprising code that performs the step of displaying the knowledge graph including the relationship to a user.
11. The computer program product of claim 7 wherein initiating the multi-hop search includes searching for the relationship through a plurality of intermediate entities forming a chain of co-mentions including text that substantiates the relationship between the first entity and the second entity.
12. The computer program product of claim 6 wherein the search includes a keyword search of the corpus of documents.
13. The computer program product of claim 6 wherein the search includes an entity-based search of the corpus of documents.
14. The computer program product of claim 6 further comprising code that performs the step of revising a search request against the corpus of documents when the search result includes a number of results below a second predetermined threshold.
15. The computer program product of claim 6 wherein the multi-hop search for the relationship between the two entities includes scoring one or more additional entities in the plurality of documents based on graph centrality over normalized entity identifiers.
16. The computer program product of claim 6 wherein the multi-hop search for the relationship between the two entities includes performing an A* graph search over a truncated document space using a semantic similarity function to evaluate a semantic distance to one of the two entities.
17. The computer program product of claim 6 wherein the multi-hop search for the relationship between the two entities includes evaluating a semantic distance to one of the two entities by calculating a sentence embedding using an embedding model trained for natural language processing.
18. The computer program product of claim 6 wherein the multi-hop search for the relationship between the two entities includes a beam search algorithm for iteratively evaluating semantic distances.
19. A system comprising:
a server coupled in a communicating relationship with a network;
a memory on the server storing computer executable code; and
a processor configured by the computer executable code to provide a user interface for receiving a selection of two entities including a first entity and a second entity from a user over the network, the process further configured by the computer executable code to cause a search of a corpus of documents to obtain a search result including a plurality of documents each mentioning one or more of the two entities, to automatically identify a subset of the plurality of documents wherein each document in the subset contains a co-mention of both of the two entities, wherein the co-mention of both of the two entities comprises mentions of both of the two entities within a same sentence or in adjacent sentences or other surrounding text, in accordance with a rule or a metric used to identify the co-mention of the two entities, in response to determining that a number of co-mentions of both of the two entities in the subset is below a predetermined threshold, to initiate an unsupervised multi-hop search for identifying and substantiating a relationship between the two entities through an intermediate third entity forming a chain of co-mentions with at least one of the first entity and the second entity in one or more of the plurality of documents, and in response to locating the relationship between the two entities through the third entity, presenting to the user through the user interface an identifier for the third entity and one or more segments of text substantiating the relationship with a supporting co-mention of the third entity and at least one of the two entities.
20. The system of claim 19 further comprising a database storing the corpus of documents.