Retrieving Relevant Knowledge Subgraphs for Task-Oriented Dialogue (2025)

Abstract: In this paper, we present an approach for extracting knowledge graph information for retrieval augmented generation in dialogue systems. Knowledge graphs are a rich source of background information, but the inclusion of more potentially useful information in a system prompt risks decreased model performance from excess context. We investigate a method of retrieving relevant subgraphs of maximum relevance and minimum size by framing this trade-off as a Prize-collecting Steiner Tree problem. The results of our user study and analysis indicate promising efficacy of a simple subgraph retrieval approach compared with a top-K retrieval model.

## introduction contemporary approaches in nlp using large language models (llms) often employ retrieval augmented generation (rag) as a means of improving llm output without the need for costly fine-tuning @xcite . however, studies have shown that the inclusion of irrelevant information harms system performance @xcite . llms in dialogue systems may also make use of rag to include additional context to assist the model to accurately answer queries or otherwise provide more interesting conversational content @xcite . this information is often drawn from knowledge graphs (kgs), which are a flexible structure for representing background information seeing application in question-answering and dialogue @xcite @xcite . particularly in task-oriented dialogue, rag can reduce hallucinations @xcite and retrieve task-specific information. systems relying on kgs often require filtering methods to identify useful information @xcite . thus, rag re- ## related work dialogue systems using rag encompass both the use of large, static kgs of general information such as ones derived from dumps of wikipedia @xcite as well as smaller dynamic kgs representing dialogue-specific information such as mental states or logical inferences @xcite . an example of task-oriented dialogue using dialoguespecific kgs is the key-value retrieval networks of @xcite . meanwhile, @xcite used a sequence-to-sequence model conditioned on dialogue history and background facts to generate more appropriate responses. other models have used directly copied background information in response generation @xcite . to use kg information in an llm, a conversion to natural language through the use of templates can enhance the quality of the model's responses @xcite . subgraph retrieval specifically is a topic of increasing interest in both question answering (qa) and dialogue settings. within qa, the g-retriever model of @xcite made use of pcst subgraphs as a component that specifically informed our approach. other work includes that of @xcite , who presented a separate trained subgraph retriever to provide results for a qa model. additionally, @xcite presented a subgraph retrieval model for qa targeted in part at reducing ambiguities and redundancies within the kg during retrieval. as an example of subgraph retrieval in dialogue systems, @xcite presented the surge model, which utilized a mechanism to enforce consistency of embeddings between dialogue context and retrieved subgraphs. likewise, @xcite evaluated a method of subgraph retrieval on the opendialkg dataset. some work has also investigated subgraph retrieval with respect to graphs incorporating commonsense reasoning @xcite . in contrast to models using trained components, our subgraph-retrieval eschews training neural models to directly use pcst subgraph construction along with out-of-the-box methods for scoring relevance in the graph. ## subgraph retrieval we propose a model of retrieval that constructs a subgraph using an algorithm to solve a prizecollecting steiner tree problem (specifically the goemans-williamson algorithm, described in sec-tion 3.2). let us assume an initial knowledge graph @xmath0, e) where v denotes vertices (nodes) and e denotes edges across those vertices. the task of subgraph retrieval is to identify a subgraph in a prize-collecting steiner tree (pcst) problem, each node v is associated with a positive reward π(v) > 0 (also called prize), while each edge e has a cost c(e) > 0. solving a given pcst problem then involves finding the subgraph g * = (v * , e * ) that maximizes the total prize minus the costs of the edges of this subgraph: we evaluate these retrieval models using the graphwoz dataset @xcite , which contains dialogues associated with dialogue specific, dynamic kgs containing commonsense reasoning relations for the dialogue turns. this dataset contains a set of dialogues paired with taskspecific background information stored in knowledge graphs along with annotations of information such as user intents. the size of the dataset along with the existing annotations of e.g. user-intent allow us to annotate likely-relevant nodes and edges at each turn in order to evaluate our approach. following the analysis with this dataset, we conducted an experiment using similarly structured tasks in a live setting to collect user impressions of the sys-tem's performance. ## experiments we assess the performance of proposed approach in two distinct sets of experiments. we first evaluate the pcst-based approach to subgraph retrieval by comparing it against a baseline top-k retrieval on gold-standard annotations of existing data. additionally, we analyze the models with reference to the overall relevance scores of retrieved graphs. for the second part of our work, we deploy the subgraph retrieval method with live users in a taskoriented setting and obtain their evaluations of the system relative to a baseline. ## conclusion in this paper, we have presented a method of kg retrieval for task-oriented dialogue. approaching the retrieval component of rag as a prize-collecting steiner tree problem, our model retrieves subgraphs that maximize dialogue turn relevance while minimizing retrieved subgraph size. the proposed subgraph retrieval method has the advantage of returning a variable number of nodes and edges that also have a structural relation in the graph. subgraph-retrieval with the proposed method can vary according to dialogue context. additionally, the subgraph can contain intermediate elements that receive no initial relevance score but are still relevant for the system response. our experiments show that despite exhibiting slightly reduced relevance per node with respect to the gold-standard response, the subgraph retrieval method achieves a higher f1-score than a baseline top-k retrieval model when using a heuristic relevance scoring model. following this result, our evaluation of the system with user feedback also indicates that a task-oriented dialogue system using pcst-based subgraph retrieval may lead to increased perceptions of relevance and informativeness.