Entity Linking and Knowledge Graph Construction › Candidate Generation

Candidate generation is a retrieval problem. Given a mention and its context, return up to $k$ plausible KB entities. Large inventories make the retrieval design consequential: the BLINK study evaluates retrieval over 5.9 million candidate entities (Wu et al., 2020). A cheap retrieval stage can reduce how many mention-description pairs an expensive reranker must evaluate. Those paper-specific counts are not current catalog-size claims.

If the reranker scores each returned candidate once, each additional candidate adds one pair evaluation. With fixed positive cost per pair, it also adds that scoring cost. For a fixed ranked retrieval result, enlarging $k$ cannot remove a retrieved gold entity, so recall@k is nondecreasing. It need not reach one: some referents may remain unretrieved at the tested depths. Select $k$ by measuring retrieval recall, downstream accuracy, and latency rather than assuming a particular list size is sufficient.

The classic approach builds an alias table from Wikipedia anchor text. For each surface string $m$, you store the set of entities it has been used to link to, along with counts. At inference time, you look up the normalized surface form and get candidates plus the prior

$$P(e \mid m) = \frac{\text{count}(m \to e)}{\sum_{e' \in \mathcal{C}(m)} \text{count}(m \to e')}$$

where:

• $P(e \mid m)$: the fraction of recorded reference-corpus links with normalized alias $m$ whose target is $e$
• $\text{count}(m \to e)$: how many times the alias table records the surface string $m$ being linked to entity $e$
• $\mathcal{C}(m)$: the candidate set for $m$, all entities $m$ has been linked to
• $\sum_{e' \in \mathcal{C}(m)} \text{count}(m \to e')$: the total link count over all candidates, the normalizing constant

Here $m$ denotes a normalized alias string, rather than the entire occurrence with its context. The denominator must be positive. We retain only positive-count candidates in this example, so their priors sum to one and the logarithms used later are defined. An unseen alias needs another retrieval route or an explicit fallback; a zero denominator is not a probability distribution.

Exact dictionary lookup is limited to the stored keys and candidates. Potential gaps include:

• Unseen aliases: a nickname, abbreviation, or translation absent from the collected dictionary.
• Case and morphology: APPLE, apples, Apple's.
• New entities: anything added to the KB after the dictionary was built.

If a shorthand has no dictionary key and normalization does not map it to one, exact lookup returns no candidates. Case and possessive handling likewise depend on the lookup rules: matching Apple's to apple needs an appropriate normalization or matching policy. A fixed table cannot return an entity missing from that table, even if a newer KB snapshot contains it.

The normalization rules from Text Normalization can reduce some spelling variation. Character n-gram retrieval is another option: overlapping character sequences can give similar spellings a nonzero retrieval score. This differs from the learned merge rules in Byte Pair Encoding. Measure whether approximate string matching retrieves useful variants and how many unrelated names it adds; spelling similarity alone does not establish identity.

A learned retriever can replace or augment the dictionary by mapping mention contexts and entity descriptions into a shared vector space. Similarity search then permits retrieval without an exact name match. This representation can connect different wording, although whether it retrieves the intended entity is an empirical question. The same retrieval pattern appears later in Retrieval-Augmented Generation.

BLINK (Wu et al., 2020) uses a bi-encoder to represent mention context and entity descriptions separately. Entity vectors can be precomputed, and an inner-product search retrieves candidates for a newly encoded mention. A cross-encoder then jointly encodes the mention and each retrieved description for reranking. The paper evaluates the resulting accuracy-speed tradeoff; a cross-encoder's advantage on another corpus must still be measured.

Description-based linking can represent an entity that has no labeled mention examples in linker training. In this bi-encoder design, encode its description and add the vector to the entity index; that can happen before queries arrive. This permits index updates without learning a new independent classifier weight for every entity. It does not guarantee retrieval: descriptions, language coverage, and domain shift still affect the match.

GENRE (De Cao et al., 2021) performs autoregressive entity retrieval: it generates an indexed entity name token by token, conditioned on the context. A trie can constrain continuations to allowed entity names. With correct termination constraints and a complete name-to-ID mapping, a completed output belongs to that index. It can still identify the wrong entity. The trie can cover the full name index or a supplied candidate subset, as in the paper's disambiguation experiments. Searching the full index avoids a separate retrieved shortlist, but remains limited by index coverage, the learned scores, and approximate decoding search.

Autoregressive decoding makes successive token decisions. Bi-encoder retrieval instead encodes the mention and searches a precomputed entity index. Their total latency also depends on batching, hardware, index search, name length, and decoding width. A valid constrained name is a structural guarantee, not a guarantee of better accuracy or of lower latency than another architecture.