Knowledge-derived search suggestion

Patent metadata

Field	Value
Publication number	US-11768869-B2
Application number	US-202117170520-A
Country	US
Kind code	B2
Filing date	Feb 8, 2021
Priority date	Feb 8, 2021
Publication date	Sep 26, 2023
Grant date	Sep 26, 2023

Abstract

The present disclosure describes systems and methods for information retrieval. Embodiments of the disclosure provide a retrieval network that leverages external knowledge to provide reformulated search query suggestions, enabling more efficient network searching and information retrieval. For example, a search query from a user (e.g., a query mention of a knowledge graph entity that is included in a search query from a user) may be added to a knowledge graph as a surrogate entity via entity linking. Embedding techniques are then invoked on the updated knowledge graph (e.g., the knowledge graph that includes additional edges between surrogate entities and other entities of the original knowledge graph), and entities neighboring the surrogate entity are retrieved based on the embedding (e.g., based on a computed distance between the surrogate entity and candidate entities in the embedding space). Search results can then be ranked and displayed based on relevance to the neighboring entity.

First claim

What is claimed is:

1. A method for search querying, comprising:
identifying a search query comprising at least one query mention;
updating a knowledge graph by adding a surrogate entity as an additional node in the knowledge graph and a surrogate entity connection element as an additional edge in the knowledge graph, wherein the surrogate entity corresponds-to the at least one query mention, and wherein the surrogate entity connection element comprises a triplet structure including the surrogate entity;
generating a vector representation for the surrogate entity based on the surrogate entity connection element using a knowledge graph embedding algorithm;
predicting a link between a first entity other than the surrogate entity and a second entity other than the surrogate entity based on the surrogate entity;
identifying at least one neighboring entity based on the vector representation for the surrogate entity and the predicted link;
retrieving a search result based at least in part on the at least one neighboring entity; and
displaying the search result to a user.

2. The method of claim 1 , further comprising:
identifying the at least one query mention from the search query using natural language processing.

3. The method of claim 1 , further comprising:
identifying a linked entity in the knowledge graph using an entity linking algorithm, wherein the surrogate entity connection element connects the surrogate entity and the linked entity.

4. The method of claim 3 , further comprising:
determining a confidence score for the linked entity based on the entity linking algorithm, wherein the surrogate entity connection element includes the confidence score.

5. The method of claim 1 , further comprising:
generating a vector representation for a plurality of candidate entities of an updated knowledge graph using the knowledge graph embedding algorithm;
computing a distance between the surrogate entity and each of the plurality of candidate entities based on the vector representation for the surrogate entity and the plurality of candidate entities; and
selecting the at least one neighboring entity from among the plurality of candidate entities based on the computed distance.

6. The method of claim 5 , wherein:
the at least one neighboring entity is selected based on a k-nearest neighbor algorithm.

7. The method of claim 1 , wherein:
the knowledge graph comprises a plurality of nodes and a plurality of edges including a head entity, a tail entity, and a relation between the head entity and the tail entity.

8. The method of claim 1 , wherein:
the search result includes images related to the at least one neighboring entity.

9. The method of claim 1 , wherein:
the at least one neighboring entity is not linked to the additional node by the surrogate entity connection element.

10. The method of claim 1 , further comprising:
generating an updated search query based on the at least one neighboring entity, wherein the search result is retrieved based on the updated search query.

11. The method of claim 1 , further comprising:
retrieving a plurality of search results and ranking the plurality of search results based at least in part on relevance to the at least one neighboring entity.

12. The method of claim 1 , further comprising:
retrieving a plurality of search results and organizing the plurality of search results into categories based on relevance to a plurality of neighboring entities.

13. The method of claim 1 , wherein:
the search query is based on a text query, an image, a keyword, a facet, or any combination thereof.

14. A method for search querying, comprising:
identifying at least one query mention;
identifying entities in a knowledge graph for the at least one query mention using a linking algorithm;
updating the knowledge graph by adding a surrogate entity as an additional node in the knowledge graph and a surrogate entity connection element as an additional edge in the knowledge graph, wherein the surrogate entity corresponds-to the at least one query mention, and wherein the surrogate entity connection element comprises a triplet structure including the surrogate entity;
generating a vector representation for the surrogate entity and a plurality of candidate entities based on the surrogate entity connection element using a knowledge graph embed ding algorithm;
predicting a link between a first entity other than the surrogate entity and a second entity other than the surrogate entity based on the surrogate entity;
computing a distance between the surrogate entity and each of the plurality of candidate entities based on the vector representation;
selecting at least one neighboring entity from among the plurality of candidate entities based on the computed distance and the predicted link;
retrieving a search result based at least in part on the at least one neighboring entity; and
displaying the search result to a user.

15. The method of claim 14 , further comprising:
receiving a search query from a user input in a search field, wherein the at least one query mention is identified from the search query; and
retrieving search results corresponding to the at least one neighboring entity in response to the search query.

16. An apparatus for search querying, comprising:
a processor;
a memory including instructions, where the instructions are executable by the processor to perform functions including:
identifying entities in a knowledge graph for at least one query mention;
updating the knowledge graph by adding a surrogate entity as an additional node in the knowledge graph and a surrogate entity connection element as an additional edge in the knowledge graph, wherein the surrogate entity corresponds-to the at least one query mention, and wherein the surrogate entity connection element comprises a triplet structure including the surrogate entity;
generating a vector representation for the surrogate entity based on the surrogate entity connection element using a knowledge graph embedding algorithm;
predicting a link between a first entity other than the surrogate entity and a second entity other than the surrogate entity based on the surrogate entity;
selecting a neighboring entity for the surrogate entity based on the vector representation and the predicted link;
retrieving a search result based at least in part on the neighboring entity; and
displaying the search result to a user.

17. The apparatus of claim 16 , further comprising: a database storing the knowledge graph.

18. The apparatus of claim 16 , wherein the instructions are further executable by the processor to identify the at least one query mention from a search query.

Assignees

• Adobe Inc

Inventors

• Lipka Nedim
• Rezayidemne Seyedsaed
• Vinay Vishwa
• Rossi Ryan
• Dernoncourt Franck
• King Tracy Holloway

Classifications

• G06F16/532 Primary

  Query formulation, e.g. graphical querying · CPC title

• G06F16/55

  Clustering; Classification · CPC title

• G06F16/56

  having vectorial format · CPC title

• G06F40/20

  Natural language analysis (semantic analysis of natural language G06F40/30) · CPC title

• G06N5/02

  Knowledge representation; Symbolic representation · CPC title