  Given a graph with textual attributes, we enable users to `chat with their
graph': that is, to ask questions about the graph using a conversational
interface. In response to a user's questions, our method provides textual
replies and highlights the relevant parts of the graph. While existing works
integrate large language models (LLMs) and graph neural networks (GNNs) in
various ways, they mostly focus on either conventional graph tasks (such as
node, edge, and graph classification), or on answering simple graph queries on
small or synthetic graphs. In contrast, we develop a flexible
question-answering framework targeting real-world textual graphs, applicable to
multiple applications including scene graph understanding, common sense
reasoning, and knowledge graph reasoning. Toward this goal, we first develop a
Graph Question Answering (GraphQA) benchmark with data collected from different
tasks. Then, we propose our G-Retriever method, introducing the first
retrieval-augmented generation (RAG) approach for general textual graphs, which
can be fine-tuned to enhance graph understanding via soft prompting. To resist
hallucination and to allow for textual graphs that greatly exceed the LLM's
context window size, G-Retriever performs RAG over a graph by formulating this
task as a Prize-Collecting Steiner Tree optimization problem. Empirical
evaluations show that our method outperforms baselines on textual graph tasks
from multiple domains, scales well with larger graph sizes, and mitigates
hallucination.~\footnote{Our codes and datasets are available at:
\url{https://github.com/XiaoxinHe/G-Retriever}}
