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

Introduction

We have previously covered two papers that use LLMs to solve graph problems. In both, the authors imported prompting techniques from the LLM reasoning literature, ran them on graph problems, and released a benchmark. Fruitful as they were, neither proposed a new way of generating prompts tailored to the nature of graphs. Here the authors draw on the properties of graph structure to propose GraphText, a framework that maps graphs into text space.

GraphText builds a graph-syntax tree for each graph; the tree encapsulates both node attributes and the relations between nodes. Traversing this tree produces a graph-text sequence, which is then handled by a large language model (LLM), turning the graph task into a text generation task.

Beyond its headline advantage — mapping graph space into text space — the paper makes the following contributions:

• Conventional GNN approaches require training a separate GNN model for every graph, whereas here a general-purpose LLM suffices via in-context learning

• GraphText is a general framework that works on both plain graphs and text-attributed graphs

• It is interactive

Methodology

Overview

The method can be summarized by the following formula:

$\tilde{y}_i=h(f_{LLM}(g(G)_i;\phi))$

Notation:

• $G$ the graph

• $g(G)_i=T_{in}[i]$ the textual description of node $i$

• $\phi$ the LLM parameters

• $f_\text{LLM}(\cdot;\phi):\mathcal{T}\to\mathcal{T}$ the LLM-based mapping function, whose input and output both live in text space

• $h:T_{out}\mapsto\tilde{Y}$ maps the LLM output to a label

Building the graph-syntax tree

It should first be made clear that in this paper a graph consists of two parts: the attributes of its nodes and the relations between them.

The root of the graph-syntax tree is an empty node, the leaves $\tilde{T}_\mathrm{L}$ are the textual attributes of the graph nodes, and the internal nodes $\tilde{T}_{I}$ are natural-language sequences.

Building the graph-syntax tree involves three parts:

1. Construct the ego-subgraph

2. Select the leaf nodes

3. Construct the internal nodes and edges

As shown in panel (c) above, the attributes in the graph are $F={\mathrm{F}_{X}[i],\mathrm{F}_{Y}[i]|\forall v_{i}\in V}$, and the relations are defined by shortest-path distance — center-node, 1st-hop, and 2nd-hop — that is, $R={\boldsymbol{R_{\mathrm{SPD=0}}},\boldsymbol{R_{\mathrm{SPD=1}}},\boldsymbol{R_{\mathrm{SPD=2}}}}$. Taking node 0 as the center, the ego-subgraph is constructed. Next the leaf nodes $\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]}}$, the internal nodes $\tilde{T}_\mathrm{I}=\{\text{“center-node",“}1\text{st-}\text{hop",“2nd-hop”,“label”,“feature”}\}$, and the tree edges are constructed. Finally, traversing the graph-syntax tree yields the natural-language sequence.