# US 10,311,117 B2 · Entity linking to query terms on online social networks

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,311,117 B2
- Document ID: US10311117B2
- Status: Granted
- Kind: B2
- Application number: 15/355,500
- Filed: 2016-11-18
- Published: 2018-05-24
- Granted: 2019-06-04
- Earliest claimed: 2016-11-18
- Assignees: Facebook, Inc.
- Applicants: Facebook, Inc.
- Inventors: Veselin S. Stoyanov
- Web page: https://patentgrep.com/patent/US10311117B2

## CPC

- G06F 16/9535: Search customisation based on user profiles and personalisation
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 16/9536: Search customisation based on social or collaborative filtering
- G06Q 10/42: Determination of affinities or common interests between users
- G06Q 10/48: using social graphs
- H04L 67/02: based on web technology, e.g. hypertext transfer protocol [HTTP]
- H04L 67/306: User profiles
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
identifying the one or more objects matching the assigned entities and the n-grams from the query.

### Claim 5 (depends on 1)

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

### Claim 6 (depends on 1)

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

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 1)

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.

### Claim 9 (depends on 1)

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

### Claim 10 (depends on 1)

The method of claim 1, wherein the confidence score for a particular entity candidate is s(ek), wherein:
s(ek)=Σiwiefie(ek, text)+Σjgjtfjt(type(ek), text), and wherein
ek is the particular entity candidate;
fie is a particular entity feature associated with the particular entity candidate ek;
wie is an entity weight assigned to the particular entity feature fie;
fjt is a particular type feature associated with the particular entity candidate ek; and
gjt is a type weight assigned to the particular type feature fjt.

### Claim 11 (depends on 1)

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
p
⁡
(
y
)
=
e
∑
e
i
∈
y
⁢
s
⁡
(
e
i
)
z
,
and wherein:
ei is a particular entity candidate;
y is a set of all possible assignments; and
z is a normalizing constant that represents a sum of all possible assignments.

### Claim 12 (depends on 1)

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.

### Claim 13 (depends on 1)

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.

### Claim 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.

### Claim 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.