1 of 16

Generative Subgraph Retrieval for �Knowledge Graph-Grounded Dialog Generation

Jinyoung Park¹, Minseok Joo¹, Joo-Kyung Kim², Hyunwoo J. Kim¹

¹Department of Computer Science and Engineering , Korea University

²Amazon AGI

Korea University

MLV Lab

2 of 16

Korea University

MLV Lab

Introduction

> Dialog generation

___________________.

Do you know Lionel Messi?

Doesn’t he play football on the Argentina team?

He used to. Can you tell me more?

Dialog

He is a midfilder and playing for FC Inter milan.

Hallucination Problem

Pretrained Language Model

(PLM)

Input token sequence

Output token sequence

3 of 16

Korea University

MLV Lab

Introduction

> Knowledge-augmented dialog generation

wikipedia

Internet

Database

External Knowledge

Knowledge Graph (KG)

___________________.

Do you know Lionel Messi?

Doesn’t he play football on the Argentina team?

He used to. Can you tell me more?

Dialog

4 of 16

Korea University

MLV Lab

Introduction

> Motivation

Prev method1:

Bi-encoder-based retrieval

Prev method2:

Conventional generative retrieval

Ours

One of prev knowledge-graph-grounded dialog generation models employ bi-encoder-based retrieval methods.

Bi-encoder-based retrieval encodes the dialog history into a single vector and then use it on another encoder to retrieve relevant triplets from the KG.

However, this apprpach has two limitations

First, it suffer from information bottelencks since the single convtext vector ha sa limited capacity to represent long and complex multi-turn dialog.

Second, these methods rely on separate graph-specific models to encode knowledge graphs, which lacks the language comprehension capabilities.

To address these limitations, recent previous method uses generative retrieval methods that autoregressively retrieves the knowledge through the decoder-based language model. But, conventional generative retrieval methods exclusively depends on the language model, which leads to the lack of graph understanding. Moreover, it sometimes generates invalid knowledge or knowledge, which is not included in the knowledge graph.

Thus, we propose our generative subgraph retrieval methods that addresses the limitations of the conventional generative retrieval model with structure-aware knowledge graph linearization and graph-constrained decoding. Instead of using standard decoding and standard knowledge linearization, we employ constrained-decoding to ensure the valid knowledge generation and represent knowledge graphs with structure-aware kg linearization to help the LM to understand both language and graph structure.

5 of 16

Korea University

MLV Lab

Methods

> Dialog Generation model with Generative Subgraph Retrieval

6 of 16

Korea University

MLV Lab

Methods

> Generative Subgraph Retrieval

Structure-aware knowledge graph linearization

Converts the knowledge graph into token sequences enriched with KG-specialized learnable tokens.

Graph-Constrained decoding

Ensures the language model to generate valid knowledge subgraphs by predicting the next tokens based not only on the LM’s scores but also on the relational proximities of entities within the KG.

7 of 16

Korea University

MLV Lab

Methods

> Structure-aware knowledge graph linearization

Augments a sequence of knowledge graph tokens with graph-specific learnable special tokens to help the language model to understand the graph’s structural information without separate graph encoders.

Multi-hop & Reverse relation

Triplets: (Messi, nationality, Argentina), (Uruguay, adjoints, Argentina)

Token sequence:

[Head]Messi[Int1]nationality[Int2]Argentina

[Rev3]adjoints[Rev4]Uruguay[Tail]

Knowledge graph reconstruction (self-supervised learning)

[Head]Messi[Int1]<MASK>[Int2]Argentina…

8 of 16

Korea University

MLV Lab

Methods

> Graph-constrained decoding

The next token prediction probability is restricted to tokens within the valid set defined by the constraint.

To account for the importance of each entity in the knowledge graph, a graph-based next-token prediction probability is also introduced.

9 of 16

Korea University

MLV Lab

Methods

> Graph-constrained decoding

The graph-based next-token prediction probability is proportional to the entity informativeness score of entity with respect to the mentioned entity set.

To consider the multi-hop relations, we design Katz-index-based entity informativeness score that is calculated with the number of knowledge paths between entities.

10 of 16

Korea University

MLV Lab

Methods

> Dialog Generation model with Generative Subgraph Retrieval

11 of 16

Korea University

MLV Lab

Methods

> Training DialogGSR

[Stage1] Knowledge graph reconstruction

[Stage2] Knowledge subgraph retrieval

[Stage3] Response generation

12 of 16

Korea University

MLV Lab

Experiments

> Response generation performance

Response generation performance on OpenDialKG

13 of 16

Korea University

MLV Lab

Experiments

> Retrieval performance and human evaluation

Retrieval performance

Human evaluation

14 of 16

Korea University

MLV Lab

Experiments

> Analysis

Ablation studies

LLM results (Llama-3-8b)

Information bottleneck

15 of 16

Korea University

MLV Lab

Experiments

> Qualitative analysis

16 of 16

Korea University

MLV Lab

Conclusion

We propose Dialog generation with Generative Subgraph Retrieval (DialogGSR), which retrieves the relevant knowledge subgraphs by generating their token sequences.

For effective generative retrieval, we design structure-aware knowledge graph linearization using learnable special tokens that capture the connectivity and reverse relations between entities.

We design a Graph-constrained decoding, which ensures the language model to generate valid knowledge subgraphs.

We show the best response generation performance on two benchmark datasets, OpenDialKG and KOMODIS.