  While Retrieval-Augmented Generation (RAG) enhances the accuracy and
relevance of responses by generative language models, it falls short in
graph-based contexts where both textual and topological information are
important. Naive RAG approaches inherently neglect the structural intricacies
of textual graphs, resulting in a critical gap in the generation process. To
address this challenge, we introduce $\textbf{Graph Retrieval-Augmented
Generation (GRAG)}$, which significantly enhances both the retrieval and
generation processes by emphasizing the importance of subgraph structures.
Unlike RAG approaches that focus solely on text-based entity retrieval, GRAG
maintains an acute awareness of graph topology, which is crucial for generating
contextually and factually coherent responses. Our GRAG approach consists of
four main stages: indexing of $k$-hop ego-graphs, graph retrieval, soft pruning
to mitigate the impact of irrelevant entities, and generation with pruned
textual subgraphs. GRAG's core workflow-retrieving textual subgraphs followed
by soft pruning-efficiently identifies relevant subgraph structures while
avoiding the computational infeasibility typical of exhaustive subgraph
searches, which are NP-hard. Moreover, we propose a novel prompting strategy
that achieves lossless conversion from textual subgraphs to hierarchical text
descriptions. Extensive experiments on graph multi-hop reasoning benchmarks
demonstrate that in scenarios requiring multi-hop reasoning on textual graphs,
our GRAG approach significantly outperforms current state-of-the-art RAG
methods while effectively mitigating hallucinations.
