SeedER: Seed-Expand-Retrieve for Efficient Knowledge Graph Retrieval

Knowledge graphs (KGs) offer a rich representation for relational knowledge, but their irregular structure makes retrieval challenging: ego-graph expansion grows rapidly, and dense embedding methods struggle with multi-hop compositional queries. Several approaches use LLM agents to explore the KG, analyze candidate nodes, and decide where to explore next. While expressive, these approaches can incur substantial computational and memory costs. On the other hand, we show theoretically that dense embeddings precomputed for graph nodes, even with augmented structure and neighborhood-aware features, can require embedding dimensions comparable to the size of the graph to answer families of knowledge graph queries. This limitation can be overcome with query-adaptive embeddings under certain conditions, and there are graph neural network (GNN) variants that can do so. However, processing the whole graph with a GNN can also incur substantial memory and computational costs, and it requires dense ground-truth labels indicating whether each node answers the query. Straightforward k-hop selection around anchor nodes can also be problematic: small k limits the nodes we can see, and even with small k values such as three and four, the k-hop subgraph can grow substantially. In this work, we devise a new approach using Graph Transformers and reinforcement learning that is much less demanding in memory and computation, can run on a CPU at inference time as a first-stage retriever, and requires feedback on only a small number of nodes at a time during training. We show that this method is competitive with methods that fine-tune LLMs to retrieve information from KGs. We call our method SeedER (Seed-Expand-Retrieve), and position it primarily as a first-stage retriever that can run with modest computational resources.