Graph-Embedding Empowered Entity Retrieval

Emma J. Gerritse, Faegheh Hasibi, Arjen P. de VriesarXiv 2025 · arXiv

TL;DR

While graph embeddings are widely used to improve entity retrieval, researchers typically pick a single entity linker and embedding model without exploring how they interact. This paper systematically evaluates three distinct categories of graph embeddings and five entity linkers, revealing that the best retrieval performance comes from combining text-and-graph hybrid embeddings with linkers that capture both named entities and general concepts.

What Problem Does This Paper Address?

Entity retrieval—the task of finding specific real-world entities (like people, places, or concepts) from a Knowledge Graph (KG) in response to a user query—is foundational for modern search engines and question-answering systems. While text-based lexical models struggle with rare "long-tail" entities and dense retrievers often fail to generalize, graph embeddings offer a way to capture rich, human-curated relational data in low-dimensional vector spaces.

However, existing literature suffers from a narrow focus: most studies arbitrarily pair one entity linker (which identifies entity mentions in a query) with one graph embedding method (which represents those entities as vectors). This leaves a critical gap in our understanding: How do different entity linking and embedding techniques interact, and which properties actually drive retrieval performance?

Methods

The authors investigate this design space using a two-stage ranking framework:

  1. Initial Retrieval: A strong lexical baseline model (BM25F-CA) generates a preliminary list of candidate entities.
  2. Re-ranking: The candidate entities are re-ordered based on their cosine similarity to the entities identified in the query by an entity linker. The final score interpolates the lexical baseline score with this embedding-based similarity score. If a query has multiple interpretations (e.g., "Java" as an island, a drink, or a programming language), the model dynamically selects the interpretation that yields the maximum score.

To find the optimal configuration, the authors benchmark combinations of:

  • Three Graph Embedding Categories: Wikipedia2Vec (skip-gram-based, combining text and link structures), RDF2Vec (random-walk-based), and ComplEx (transition-based, utilizing complex vector spaces).
  • Five Entity Linkers: TagMe, REL, Nordlys, SMAPH, and ELQ.

Datasets

The experiments are conducted on the standard DBpedia-Entity V2 collection, which contains 467 queries split into four categories (SemSearch ES, INEX-LD, ListSearch, and QALD-2).

To evaluate the entity linkers, the authors compare two human-annotated ground truths:

  • Webis Annotations: An existing dataset that maps queries to multiple scenarios but focuses exclusively on Named Entities (NEs) like people or locations.
  • Radboud Annotations (New): A novel dataset created for this work. Unlike Webis, it includes both Named Entities and general Concepts (e.g., mapping "who produced the film..." to the concept movie producer).

Key Insights and Ideas

  • General Concepts are Crucial: Entity linkers that only look for named entities (like REL or Nordlys) underperform in retrieval tasks. Linkers like TagMe, SMAPH, and ELQ succeed because they capture broader concepts that provide vital contextual clues for the query.
  • Structure + Text = The Winning Combo: Wikipedia2Vec consistently outperforms pure graph models (ComplEx and RDF2Vec). This is because it jointly embeds words and entities in the same space, leveraging both the textual descriptions of entities and the structural hyperlinks connecting them.
  • Graph Coverage is a Silent Killer: A major bottleneck in embedding-based retrieval is "missing entities" (entities in the dataset that lack trained vectors). By tuning Wikipedia2Vec to include rare entities and disambiguation pages, the authors boosted entity coverage from 75% to 97.6%, which drastically improved downstream retrieval. Similarly, adding "Pagelinks" to RDF2Vec and ComplEx significantly improved their performance by expanding the underlying graph size.

Key Results

The quantitative evaluation uses Normalized Discounted Cumulative Gain (NDCG) at ranks 10 and 100:

  • Baseline vs. Enhanced: The standalone BM25F-CA baseline achieved an NDCG@10 of 0.461. Re-ranking with Wikipedia2Vec (2019) and the newly introduced Radboud annotations boosted this significantly to 0.492 (and NDCG@100 from 0.551 to 0.576).
  • Linker Performance: When using automatic linkers, ELQ, TagMe, and SMAPH achieved the highest retrieval gains, directly correlating with their high F-measure on concept annotations.
  • Clustering Quality: Using UMAP visualizations and query coherence scores, the authors proved that incorporating graph structure creates tighter, more distinct entity clusters for related search intents compared to text-only embeddings.

Limitations and Future Work

Despite optimizing the embedding training to maximize coverage, 2.4% of the entities in the Wikipedia2Vec space remained missing, which still hurts performance for queries targeting highly specific long-tail entities.

Additionally, this study focuses on a two-stage linear interpolation framework with traditional graph embeddings. The authors note that future work should explore how these embedding and linking dynamics affect more modern, end-to-end Transformer-based dense retrievers, as well as how well these methods adapt to highly specialized, domain-specific, or sparse knowledge graphs.

Summary updated

Abstract

In this research, we investigate methods for entity retrieval using graph embeddings. While various methods have been proposed over the years, most utilize a single graph embedding and entity linking approach. This hinders our understanding of how different graph embedding and entity linking methods impact entity retrieval. To address this gap, we investigate the effects of three different categories of graph embedding techniques and five different entity linking methods. We perform a reranking of entities using the distance between the embeddings of annotated entities and the entities we wish to rerank. We conclude that the selection of both graph embeddings and entity linkers significantly impacts the effectiveness of entity retrieval. For graph embeddings, methods that incorporate both graph structure and textual descriptions of entities are the most effective. For entity linking, both precision and recall concerning concepts are important for optimal retrieval performance. Additionally, it is essential for the graph to encompass as many entities as possible.
BibTeX
@misc{gerritse2025graph,
  author = {Emma J. Gerritse and Faegheh Hasibi and Arjen P. de Vries},
  title = {{Graph-Embedding Empowered Entity Retrieval}},
  year = {2025},
  eprint = {2506.03895},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.03895},
}
Figure