Title: GraphText: Graph Reasoning in Text Space

Institute: Université de Montréal

Authors: Jianan Zhao, Le Zhuo, Yikang Shen, Meng Qu, Kai Liu, Michael Bronstein, Zhaocheng Zhu, Jian Tang

link: https://arxiv.org/abs/2310.01089

Date: 2023.10.02

介绍

之前我们介绍过使用大模型来解决图问题的两篇论文，两篇文章的作者将LLM Reasoning领域的Prompt引入到图问题上进行实验并提出BenchMark。尽管两文成果颇丰，但是并没有针对图的特点提出新的Prompt生成方式。在本文，作者跟据图结构的特点提出了一种将图映射到文本空间的框架GRAPHTEXT。

GRAPHTEXT为每个图创建其对应的图语法树，图语法树同时封装了节点属性和节点间关系。通过遍历这棵树，可以产生图文序列，然后通过大型语言模型（LLM）处理，将图形任务视为文本生成任务。

除了将图空间映射到文本空间这一最大的优点外，本文还有如下贡献:

• 传统的GNN方式需要针对每一个图训练一个GNN模型，而本文只需要通用的LLM通过上下文学习就可以了

• GRAPHTEXT是一套通用框架，在普通图和文本属性图上都可以使用

• 可交互

方法论

概述

本方法可用如下公式概括:

参数表:

• $G$ 图

• $g(G)_i=T_{in}[i]$ $i$节点的文本表述

• $\phi$ LLM参数

• $f_\text{LLM}(\cdot;\phi):\mathcal{T}\to\mathcal{T}$ 基于LLM的映射函数，在输入和输出上都处于文本空间

• $h:T_{out}\mapsto\tilde{Y}$ 将LLM的输出映射至label

图语法树的构建

首先需要明确的是在本文，图由两个部分构成，分别是节点的属性。

图语法树的根节点是空节点，叶子节点 $\tilde{T}_\mathrm{L}$是图节点的文本属性，中间节点$\tilde{T}_{I}$是自然语言序列。

图语法树的构建可由三部分构成

1. 首先构建自我子图（ego-subgraph）

2. 选择叶子节点

3. 构建中间节点和边

如上图(c) 所示，图中的属性为 $F={\mathrm{F}_{X}[i],\mathrm{F}_{Y}[i]|\forall v_{i}\in V}$，关系被定义为最短路 : center-node, 1st-hop, and 2nd-hop，即 $R={\boldsymbol{R_{\mathrm{SPD=0}}},\boldsymbol{R_{\mathrm{SPD=1}}},\boldsymbol{R_{\mathrm{SPD=2}}}}$。以0为中心点，自我子图被构建了起来。然后构建叶子节点 $\tilde{T_{\mathrm{L}}}={\mathrm{F_{\mathrm{X}}[0]},\mathrm{F_{\mathrm{X}}[1]},\mathrm{F_{\mathrm{X}}[2]}\mathrm{F_{\mathrm{X}}[3]},\mathrm{F_{\mathrm{X}}[4]},\mathrm{F_{\mathrm{Y}}[1]},\mathrm{F_{\mathrm{Y}}[3]}}$、中间节点 $\tilde{T}_\mathrm{I}=\{\text{“center-node",“}1\text{st-}\text{hop",“2nd-hop”,“label”,“feature”}\}$和树的边。最后遍历图语法树即可生成自然语言序列。