IC-858The choice of graph encoding method significantly changes LLM accuracy on graph reasoning tasks, with incident encoding outperforming adjacency by up to 34 percentage points on connected nodes

Bahare Fatemi, Jonathan Halcrow, Bryan Perozzi

SourceTalk like a Graph: Encoding Graphs for Large Language Models

The paper measures how nine different textual encodings of the same graph (adjacency, incident, friendship, co-authorship, South Park, Game of Thrones, social network, politician, expert) affect LLM performance on six basic graph tasks. On PaLM 62B with zero-shot prompting, connected nodes accuracy ranges from 4.0% (friendship) to 53.8% (incident), while node degree ranges from 9.0% (SP) to 25.0% (incident). The application-style question encoder also outperforms the graph-style encoder (e.g., 60.8% vs 42.8% on zero-shot edge existence for PaLM 2-xxs). The overall improvement from choosing the best over worst encoding spans 4.8% to 61.8% depending on the task.

Evidence

correlational

Key metric

PaLM 62B zero-shot connected nodes: adjacency 19.8%, incident 53.8%; PaLM 2-xxs zero-shot edge existence: graph encoder 42.8%, application encoder 60.8%; GPT-3.5-turbo zero-shot node degree: adjacency 5.4%, incident 66.4%; overall range 4.8% to 61.8%

Caveat

Results are on synthetic graphs with 5-20 nodes; the paper does not test on real-world graphs of larger scale.

Model

PaLM 62B, PaLM 2 FLAN-PaLM 2, GPT-3.5 / ChatGPT-3.5 GPT-3.5-turbo

Methods

Zero-shot prompting [primary], Few-shot prompting / 2-shot prompting / Few-shot ICL / Few-shot prompting for base models [primary], Chain-of-Thought prompting / Chain-of-Thought (CoT) prompting / CoT prompting / Few-shot Chain of Thought / Few-shot CoT / Chain-of-Thought (CoT-S) / CoT-bag prompting / Few-shot CoT prompting / Rationale prompting / Zero-shot CoT prompting / Wei et al. (2022) chain-of-thought prompting [primary]

Related work

Self-Consistency / Self-consistency prompting / Wang et al. 2023 (self-consistency) / Wang et al. 2023b (Self-Consistency) [compared-to]

Related findings

IC-859, IC-860, IC-861

Extraction

automatic-extraction