Entity Linking and Knowledge Graph Construction › The Coherence Signal

Independent local decisions can miss evidence available elsewhere in a document. Once Chicago Bulls is linked to the basketball team, its connection to Michael Jordan can help rank an ambiguous Jordan mention. This is a useful signal, not a universal topical constraint: documents can compare unrelated people, countries, products, or events.

Collective entity linking scores combinations of assignments rather than choosing every entity independently. Ratinov et al. (2011) study local and global disambiguation, and Hoffart et al. (2011) combine mention-entity compatibility with coherence among entities. We use a small pairwise objective to inspect that idea. Whether coherence improves accuracy depends on the data, the compatibility measure, and its weight.

Milne and Witten (2008) use Wikipedia link structure to compare entities. The same shared-inlink count can represent very different degrees of overlap for small and large inlink sets. The following normalized link-overlap score accounts for those sizes; we explicitly distinguish its distance form from the compatibility reward used in our maximization problem.

Let $W$ be the article universe, with more than one article, and let $A$ and $B$ be the sets of articles linking to entities $a$ and $b$. For nonempty overlap and $\min(|A|,|B|)<|W|$, first compute a normalized link distance and then turn it into a bounded compatibility reward:

where:

• $W$: the article universe used by the link graph
• $A$ and $B$: articles linking to $a$ and $b$, respectively
• $|A\cap B|$: their number of shared inlink articles
• $D(a,b)$: a distance, with smaller values indicating greater overlap at fixed marginal counts
• $r(a,b)$: the clipped compatibility reward used below

We use natural logarithms; any common valid logarithm base gives the same ratio. Identical nonempty proper subsets give $D=0$ and $r=1$. At fixed $|A|$, $|B|$, and $|W|$, more shared articles decrease the distance. The clipped reward cannot decrease, but can remain zero while $D\geq1$. This normalization is not a probability or a statistical test of independence.

We explicitly return $r=0$ when either inlink set is empty or the sets are disjoint. If both sets equal $W$, the ratio has a zero denominator; the toy implementation returns $r=1$ for that identical-set case. Clamping $1-D$ below at zero is an implementation convention because the unbounded distance can exceed one. These boundary policies make the score defined on every pair in our small graph.

Let $\mathcal{C}(m_i)$ be the finite, nonempty candidate set for each mention $m_i$ included in the joint assignment. Apply a retrieval fallback or abstain on empty candidate lists before forming the product. With finite scores, the linking objective is a global optimization over those mentions.

where:

• $\hat{\mathbf{e}}$: the joint assignment of one entity to each mention, i.e. a tuple $(e_1, \dots, e_n) \in \mathcal{C}(m_1) \times \cdots \times \mathcal{C}(m_n)$
• $\mathcal{C}(m_i)$: the candidate entity set for mention $m_i$
• $s(e_i, m_i)$: the local score of entity $e_i$ for mention $m_i$ (prior plus context similarity)
• $r(e_i, e_j)$: the pairwise relatedness between entities $e_i$ and $e_j$ (Milne-Witten, defined above)
• $\gamma\geq0$: a finite weight on the pairwise coherence term, trading off document coherence against local evidence

This is a structured prediction score with unary terms $s$ and pairwise terms $\gamma r$. When every candidate set is nonempty and all scores are finite, exponentiating the total score and normalizing over the finite Cartesian product defines a conditional distribution. Its maximum-probability assignments are exactly the highest-scoring assignments. In that interpretation the displayed terms are log-potentials. The factorization includes every mention pair, unlike the linear-chain model in Conditional Random Fields.

For arbitrary fully connected pairwise terms, the linear-chain decomposition used by the Viterbi Algorithm does not directly solve this objective. Exhaustive search considers the full Cartesian product of candidate sets. Special parameter choices can be simpler, including $\gamma=0$ below. Options for the general case include:

• Exhaustive search when the candidate-set product is small enough that you can score every assignment.
• Integer linear programming with one binary choice variable per (mention, candidate), one-of-$k_i$ constraints for each mention $m_i$ with $k_i = |\mathcal{C}(m_i)|$, and auxiliary variables or equivalent constraints for pairwise products. These are assignment constraints, not transitivity constraints between mentions. AIDA's graph algorithm instead searches for a dense subgraph (Hoffart et al., 2011).
• Approximate search with loopy max-product belief propagation, or with Gibbs sampling from the score-induced distribution and selection of the highest-scoring complete assignment visited.
• Greedy sequential refinement: visit each mention, test its candidates while holding the other assignments fixed, and accept the best change only if it strictly improves the score. Repeat until a complete pass makes no change. On a finite candidate space, strict improvements cannot revisit an assignment. The resulting assignment has no improving single-mention move, but need not be the global optimum.

At $\gamma=0$, the objective decomposes into independent local choices, provided each candidate set is nonempty. Increasing $\gamma$ gives compatibility more influence and can overturn local evidence, including a correct local decision. There is no guarantee that a news article benefits from a larger value than another document. Select the weight on held-out development data and inspect mixed-topic documents for erroneous pressure toward one topic.

Our objective permits coherence to override local evidence; it does not enforce a tie-breaker-only policy. A different design could gate that contribution by a confidence criterion, but such a gate would need its own definition and validation. Keep this distinction visible when interpreting a successful toy example: a useful compatibility bonus can also propagate a wrong neighboring assignment.