Entity linking to query terms on online social networks

• US 10,311,117 B2
• Filed: 11/18/2016
• Issued: 06/04/2019
• Est. Priority Date: 11/18/2016
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Stoyanov, Veselin S.
• Primary Examiner(s): Alam, Shahid A
• Application Number:
  US15/355,500
• Publication Number:
  US 20180144051A1
• Time in Patent Office: 928 Days
• Field of Search: 707706
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/306 User profiles

Abstract

In one embodiment, a method includes identifying one or more entity candidates matching one or more n-grams in a character string, wherein each entity candidate corresponds to an entity associated with the online social network, each entity candidate being associated with one or more entity features and one or more type features, and wherein each entity candidate is of a particular entity type; calculating, for each entity candidate, a confidence score representing a likelihood that the entity candidate is intended to match the corresponding n-gram, wherein the confidence score is based on: an entity-score based on the one or more entity features and a type-score based on the one or more type features; and assigning an entity candidate to one or more of the n-grams based on the calculated confidence scores corresponding to the n-grams.

Claims

1. A method comprising:

receiving, from a client system of a first user of an online social network, a search query comprising a character string inputted by the first user;

parsing the character string to identify a plurality of n-grams;

identifying one or more entity candidates matching one or more of the n-grams, wherein each entity candidate corresponds to an entity associated with the online social network, each entity candidate being associated with one or more entity features and one or more type features, and wherein each entity candidate is of a particular entity type;

calculating, for each entity candidate, a confidence score representing a likelihood that the entity candidate is intended to match the corresponding n-gram, wherein the confidence score is based on;

an entity-score based on the one or more entity features, the entity-score representing a likelihood that the entity candidate matches the corresponding n-gram, and

a type-score based on the one or more type features, the type-score representing a likelihood that the entity type associated with the entity candidate matches an entity type the first user intended to reference with the corresponding n-gram;

assigning an entity candidate to one or more of the n-grams based on the calculated confidence scores corresponding to the n-grams; and

sending, to the client system for display, instructions for presenting a search-results interface responsive to the search query, wherein the search-results interface comprises one or more search results corresponding to one or more identified objects, respectively, matching the assigned entities and the n-grams from the query.

2. The method of claim 1, further comprising:

accessing a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising;

a first node corresponding to the first user; and

a plurality of second nodes corresponding to a plurality of entities associated with the online social network, respectively.

3. The method of claim 2, wherein one or more of the entity candidates are sourced from the social graph, and wherein one or more of the entity candidates correspond to one or more of the second nodes, respectively.

4. The method of claim 1, further comprising:

identifying the one or more objects matching the assigned entities and the n-grams from the query.

5. The method of claim 1, wherein the confidence score is calculated using a segmental conditional random field (CRF) model.

6. The method of claim 1, wherein the entity candidate is either a social-graph entity or a keyword.

7. The method of claim 1, wherein the entity features comprise one or more of:

a number of likes associated with the entity candidate,

a number of in-links associated with the entity candidate in a third-party database, or

an affinity coefficient between the entity candidate and the first user.

8. The method of claim 1, wherein the type features comprise one or more of:

one or more n-grams comprised in the entity candidate, or

one or more n-grams surrounding the entity candidate in the search query.

9. The method of claim 1, wherein the entity candidates are sourced from a third party database.

10. The method of claim 1, wherein the confidence score for a particular entity candidate is s(e_k), wherein:

s(e_k)=Σ

_iw_i^ef_i^e(e_k, text) Σ

_jg_j^tf_j^t(type(e_k), text), and wherein

e_k is the particular entity candidate;

f_i^e is a particular entity feature associated with the particular entity candidate e_k;

w_i^e is an entity weight assigned to the particular entity feature f_i^e;

f_j^t is a particular type feature associated with the particular entity candidate e_k; and

g_j^t is a type weight assigned to the particular type feature f_j^t.

11. The method of claim 1 further comprising calculating a probability that all identified entity candidates will be assigned to the plurality of n-grams, wherein the probability is

12. The method of claim 1, wherein the entity features comprise:

one or more context features associated with the entity candidate, wherein the context features are based on a similarity of an embedding of the n-gram and an embedding of the entity candidate.

13. The method of claim 1, wherein each entity candidate is referenced by an entity forward index that stores the entity features and a canonical ID for each entity candidate.

14. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

receive, from a client system of a first user of an online social network, a search query comprising a character string inputted by the first user;

parse the character string to identify a plurality of n-grams;

identify one or more entity candidates matching one or more of the n-grams, wherein each entity candidate corresponds to an entity associated with the online social network, each entity candidate being associated with one or more entity features and one or more type features, and wherein each entity candidate is of a particular entity type;

calculate, for each entity candidate, a confidence score representing a likelihood that the entity candidate is intended to match the corresponding n-gram, wherein the confidence score is based on;

an entity-score based on the one or more entity features, the entity-score representing a likelihood that the entity candidate matches the corresponding n-gram, and

a type-score based on the one or more type features, the type-score representing a likelihood that the entity type associated with the entity candidate matches an entity type the first user intended to reference with the corresponding n-gram;

assign an entity candidate to one or more of the n-grams based on the calculated confidence scores corresponding to the n-grams; and

send, to the client system for display, instructions for presenting a search-results interface responsive to the search query, wherein the search-results interface comprises one or more search results corresponding to one or more identified objects, respectively, matching the assigned entities and the n-grams from the query.

15. A system comprising:

one or more processors; and

a non-transitory memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to;

receive, from a client system of a first user of an online social network, a search query comprising a character string inputted by the first user;

parse the character string to identify a plurality of n-grams;

identify one or more entity candidates matching one or more of the n-grams, wherein each entity candidate corresponds to an entity associated with the online social network, each entity candidate being associated with one or more entity features and one or more type features, and wherein each entity candidate is of a particular entity type;

calculate, for each entity candidate, a confidence score representing a likelihood that the entity candidate is intended to match the corresponding n-gram, wherein the confidence score is based on;

an entity-score based on the one or more entity features, the entity-score representing a likelihood that the entity candidate matches the corresponding n-gram, and

a type-score based on the one or more type features, the type-score representing a likelihood that the entity type associated with the entity candidate matches an entity type the first user intended to reference with the corresponding n-gram;

assign an entity candidate to one or more of the n-grams based on the calculated confidence scores corresponding to the n-grams; and

send, to the client system for display, instructions for presenting a search-results interface responsive to the search query, wherein the search-results interface comprises one or more search results corresponding to one or more identified objects, respectively, matching the assigned entities and the n-grams from the query.