Dense vector retrieval can miss evidence connected through intermediate entities, while direct graph retrieval requires access to the graph at query time. We compare five offline graph-based embedding transformations and strategies for using the resulting graph-modified embeddings alongside the originals, without query-time graph access. On a synthetic professional-network benchmark with complete supporting-evidence sets, direct replacement of the original embeddings reduces evidence recovery. Multi-stage strategies improve recovery by using graph-modified embeddings to guide the search while retaining the originals for semantic relevance. On questions requiring linked facts or comparisons among candidates, the strongest configuration improves recovery by up to 25.9% relative to plain vector retrieval. It also matches baseline recovery with 40% fewer returned nodes. Controls confirm that graph information contributes beyond multi-stage retrieval alone. Across the tested methods, retrieval performance depends more on how graph-modified embeddings are used than on how they are produced.
Figures & tables
Figure 1: Graph information used by the five transformations. Darker nodes are more similar to the source node; orange outlines mark embeddings included in an average, with thicker outlines indicating greater weight. Dashed regions and crosses show Louvain communities and their centroids.
Figure 2: Allocation of the 40-node retrieval budget. Each cell represents one returned node. Light blue and pink denote original- and modified-space searches; orange denotes fused scoring. The two darker blues denote successive searches with shifted queries in the original space. Vertical lines separate stages.
Figure 3: Gold-evidence recovery under direct retrieval across all 977 validation questions. The dashed line denotes plain vector retrieval.
Figure 4: Gold-evidence recovery across retrieval strategies on the 527 difficult questions. The dashed line denotes plain retrieval.
Figure 5: Alternating budget split on the 527 difficult questions.
Figure 6: Two-stage fused retrieval on the 527 difficult questions.
Figure 7: Gold-evidence recovery of the single requery and chained requery schedules across graph-modified embedding collections. The dashed line denotes plain vector retrieval.
Figure 8: Improvement of chained requery with the walk representation over plain retrieval, reported by question group. Annotations show absolute and relative gains.
Figure 9: Cumulative gold-evidence recovery over the first k nodes returned in stage order, without global reranking. The full chained requery method uses the walk representation; both controls retain its 6/6/14/14 schedule but remove graph conditioning. Vertical dotted lines mark stage boundaries. The horizontal dashed line shows plain retrieval’s recovery at 40 nodes.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 10: The graph schema and one instance from the validation corpus. Shape marks the node type: a circle is a chunk, a rounded square a document, a square an entity. Counts on the schema edges are those of the validation graph. In the instance, a resume document is about a person, its chunks are part_of it, and each chunk mentions the entities named in its text. Because mentions always runs from a chunk to an entity, two hops lead from one chunk to another through an entity they share — here two employees of the same organisation.
Multi-hop retrieval must recover passages that provide sufficient evidence together. An initial passage often resolves an entity or relation implicit in the question, making the missing evidence easier to describe only after retrieval begins. Graph retrieval improves access to related evidence through stored corpus structure, but its retrieval signal is commonly derived from the original question. Complementary evidence must then be reached through stored relations even when an observed passage provides a more direct semantic cue. We introduce EviReform, which separates revising the retrieval request from aggregating evidence in the graph. Retrieved source passages formulate residual queries for the unresolved information need. The original and residual retrieval signals are normalized separately, combined, and propagated between propositions that share entities. On 2WikiMultiHopQA, HotpotQA, and MuSiQue, EviReform exceeds the strongest baseline by up to 5.59 Recall@5 points and 4.50 F1 points. These results show that observed evidence can guide graph retrieval toward the part of a supporting chain left underspecified by the original question. Code is available at https://github.com/XrazyMee/EviReform.
Xinlong Xu, Yoshua Y. Li
Nanjing University of Information Science and Technology · Meituan
Entity-Memory graph retrieval keeps dialogue turns as verbatim Memory nodes, links repeated mentions through shared Entities, and connects adjacent Memories with directed chronological edges. At query time the retriever moves from Entity gating through semantic fusion and one-hop chronological recovery to dense backfill. The path can keep a neighboring Memory that dense cosine ranking would otherwise omit. A matched dense control shares the Memory and query vectors, context budget, requested answer protocol, and evaluator, isolating graph structure from changes to the reader. On 1,986 questions from ten LoCoMo conversations, graph retrieval raises official evidence recall at top-k 25 from 79.7468% to 84.4842%. The recall advantage is supported from top-k 5 to 50, while no matched cutoff supports an overall final-answer F1 difference. Four paper-eligible requested configurations support empirical robustness across the tested GPT-3.5 and DeepSeek extractors on both outcomes. Embedding robustness is mixed: F1 has no supported contrast, but recall is sensitive to the embedding artifact. The comparison isolates a retrieval-coverage gain from graph structure. It does not establish a final-answer F1 gain, model or embedding equivalence, or cross-dataset generalization.
Semantic search in retrieval-augmented generation (RAG) systems is often insufficient for complex information needs, particularly when relevant evidence is scattered across multiple sources, because it may fail to retrieve the complete set of evidence. Existing approaches to addressing this problem either rely on iterative agentic retrieval, which can be computationally inefficient, or maintain additional structures such as knowledge graphs, which introduce storage and maintenance overhead. In this paper, we propose GraphER, a graph-based enrichment and reranking framework that (1) leverages the organizational structure of data to capture proximity relationships beyond semantic similarity, (2) constructs a graph at query time based on these proximities, and (3) applies graph-based ranking to surface the top candidate documents. Experiments across table retrieval, multi-hop retrieval, and long-document retrieval benchmarks demonstrate consistent improvements in terms of retrieval completeness. Additionally, GraphER requires no additional graph infrastructure and integrates seamlessly with standard vector stores. The framework is retriever-agnostic, supports multiple forms of proximity, and introduces minimal query-time latency.