Graph-Based Disambiguation

Unlike local disambiguation which resolves each mention independently, graph-based methods evaluate the semantic coherence of all candidate entities simultaneously. The algorithm seeks the combination of entities that maximizes the density or weight of connections between them in the knowledge graph, ensuring that linked entities form a tightly interconnected subgraph. This prevents jarring disambiguation errors where one mention links to a musician and a neighboring mention links to an unrelated physicist.

A core algorithmic primitive is Personalized PageRank (PPR), adapted from Google's original ranking algorithm. The knowledge graph is treated as a directed or undirected graph where nodes are candidate entities and edges represent semantic relationships. A random walk with restart is initiated from a set of seed nodes representing the most likely candidates. Entities that accumulate high stationary probability are considered central to the document's topic and are selected as the final disambiguated set.

Graph-based disambiguators often frame the problem as identifying the densest subgraph within a larger candidate graph. The algorithm constructs a weighted graph where edge weights represent semantic relatedness scores between candidate entities. It then applies community detection or graph partitioning techniques to isolate a cluster of entities with maximal internal connectivity. This cluster represents the most topically coherent interpretation of the document's mentions.

The process begins by constructing a bipartite or heterogeneous graph with two node types: mention nodes (each ambiguous span in the text) and entity nodes (all candidate KB entries). Edges between mentions and entities are weighted by local compatibility scores (contextual similarity + prior probability). Edges between entity nodes are weighted by semantic relatedness derived from the knowledge graph structure. The disambiguation task becomes a graph labeling or inference problem on this unified structure.

Some graph-based systems employ probabilistic graphical models where entity assignments are treated as random variables. Loopy Belief Propagation (LBP) iteratively passes messages between mention nodes and entity nodes to compute marginal probabilities. Each message encodes how strongly one mention's disambiguation constrains another's based on entity-entity relatedness. After convergence, the entity with the highest marginal probability for each mention is selected, providing a globally consistent labeling.

Exhaustive joint inference over all possible entity combinations is computationally intractable. Practical systems first apply a Bi-Encoder or other fast retrieval method to prune the candidate space to the top-K entities per mention. The graph-based collective inference then operates only on this reduced candidate graph, making the approach scalable to documents with dozens of mentions and knowledge bases with millions of entities.

The global disambiguation paradigm that resolves all mentions in a document jointly, rather than independently. It operates on the principle of semantic coherence: the correct set of linked entities should be highly interrelated in the knowledge graph. This transforms disambiguation from a series of isolated classification tasks into a single global optimization problem, where the goal is to find the densest subgraph connecting all candidate entities.

A graph algorithm central to collective disambiguation, adapted from Google's original ranking formula. Starting from a set of seed nodes (candidate entities), it performs a random walk with restart over the knowledge graph. The stationary distribution reveals which candidates are most central and interconnected. Key properties:

• Restart probability: Keeps the walk focused on the local neighborhood of candidates
• Damping factor: Controls the trade-off between exploration and exploitation
• Convergence: Produces a ranked list of entities by their graph centrality score

A structured, semantically rich data model where entities are nodes and typed relationships are edges. For disambiguation, the graph provides the relational fabric against which coherence is measured. Critical features include:

• Typed edges: e.g., foundedBy, locatedIn, worksFor
• Multi-hop paths: Chains of relationships that connect seemingly distant entities
• Density signals: Highly interconnected entity clusters indicate strong topical coherence
• Canonical identifiers: Each node has a unique URI, providing the definitive target for linking

A dense, low-dimensional vector representation of a knowledge graph entity, learned to capture its semantic properties and relational context. In graph-based disambiguation, embeddings serve as the initial similarity signal before graph algorithms refine the selection. Common approaches:

• TransE: Models relationships as translations in vector space
• Graph Neural Networks: Aggregate information from neighboring nodes
• Text-based embeddings: Encode entity descriptions using transformer models
• Joint embeddings: Combine structural and textual features into a unified space

A dynamic measure of semantic relatedness between the textual context surrounding a mention and the descriptive text of a candidate entity. Unlike static prior probabilities, this score adapts to the specific document. It is typically computed using:

• Bi-Encoders: Independently encode mention context and entity description, then compute cosine similarity
• Cross-Encoders: Jointly process mention and entity text through full cross-attention for higher precision
• Attention-based aggregation: Weight the importance of different context words relative to each candidate

The static, context-independent likelihood that a specific surface form refers to a particular entity. Calculated from large-scale statistical analysis of annotated corpora like Wikipedia hyperlinks. Two key variants:

• Commonness: The frequency with which a surface form is used as anchor text for an entity, e.g., 'Apple' links to the company 85% of the time
• Entity prominence: The overall popularity or centrality of an entity in the knowledge base, independent of any specific mention
• Role in graphs: Priors serve as initial node weights before collective algorithms propagate coherence signals