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 side, we show theoretically that dense embeddings pre-calculated for nodes in graphs, even with augmented structure and neighborhood-aware features, can require embeddings of dimension of the graph to be able to answer families of knowledge graph queries. This limitation can be solved with query-adaptive embeddings under certain conditions, and there are graph neural network (GNN) variants that can do that. However, processing the whole graph with a GNN can also incur large amount of memory/computation, and besides that it requires dense ground truth answers, knowing for each node if they are an answer to query or not. Straightforward k-hop selection around some anchor nodes can also be problematic since small k would limit the number of nodes we are seeing 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 memory and computation demanding, at inference time can be even ran on a CPU as a first stage retrieval, and in training requires feedback on only small number of nodes at a time. We show that this method is competetive with methods that finetune LLMs to retrieve information from KGs. We call our method (Seed-Expand-Retrieve), and position it primarily as a first stage retrieval that can be ran using small computational resources.