Research map / Graph learning / Knowledge and temporal graphs
Talk like a Graph: Encoding Graphs for Large Language Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Systematic study of how encoding graphs as text (node/edge encodings, question phrasing, graph structure) affects black-box LLM performance on basic graph tasks, plus a new benchmark GraphQA.
Problem
LLMs are poor at graph reasoning, and how graphs are serialized as text, how questions are phrased, and what graph structure is used all affect performance; this had not been systematically studied for black-box LLMs.
Approach
Decompose graph prompting into graph encoding function, question encoder, and graph structure; systematically vary node naming (integers, names, characters), edge phrasing (adjacency, incident, friendship, etc.), prompting heuristics, and random graph generators on basic graph tasks, and release a benchmark (GraphQA) built on this.
Key results
- Choice of graph encoding significantly changes accuracy; for connected nodes on PaLM 62B, incident encoding reaches 53.8% vs 19.8% for adjacency under zero-shot prompting.
- Question phrasing matters: application-style question encoder raised PaLM 2-XXS zero-shot edge existence from 42.8% to 60.8%.
- Graph structure matters: zero-shot cycle check reaches 91.7% on complete graphs but 5.9% on path graphs, indicating priors over graph structure rather than reasoning.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace graph question encoder with application question encoder (ablation) | zero-shot prompting with PaLM 2-XXS · GQA Edge Existence | accuracy: 42.8 -> 60.8 | Helped |
| Replace zero-shot with zero-shot CoT (ablation) | PaLM 62B graph reasoning · GQA basic graph tasks | accuracy: 44.5 / 9.4 -> 33.5 / 11.6; 76.0 / 13.2 -> 32.3 / 23.2 | Hurt |
| Replace zero-shot prompting with CoT prompting (ablation) | PaLM 62B graph reasoning · GQA Node degree | accuracy: 14.0/16.0 -> 29.2 / 60.4 | Helped |
| Use incident encoding instead of adjacency encoding | PaLM 62B zero-shot · GQA Connected nodes | accuracy: 19.8 -> 53.8 | Helped |
| Use integer node encoding | graph encoding for integer-output tasks · GQA node degree, node count, and edge count | accuracy | Helped |
| Replace graph task wording with a friendship-based application question (ablation) | graph question encoder · GQA basic graph tasks | accuracy: 42.8 -> 60.8 | Mixed |
| Represent edges with multiple randomized relation words (ablation) | friendship graph encoding · GQA graph tasks | accuracy | Helped |
| Increase model capacity | PaLM 2 · GQA graph reasoning tasks | accuracy | Helped |
| Add few-shot examples to zero-shot prompting (ablation) | PaLM 62B on path-graph cycle checking · GQA Cycle check on path graphs | accuracy: 5.9 -> 19.7 | Helped |
| Use a complete graph rather than a path graph | PaLM 62B zero-shot · GQA Cycle check | accuracy: 5.9 -> 91.7 | Mixed |
| Use a path graph rather than a complete graph | PaLM 62B zero-shot · GQA Edge Existence | accuracy: 19.8 -> 60.9 | Mixed |
| Find disconnected nodes rather than connected nodes | LLM prompting methods · GQA Disconnected nodes | accuracy: 0.5%; close to 0.0% | Hurt |
Surprising findings
- LLMs perform worse than the majority baseline on edge existence and cycle check under zero-shot prompting with ER graphs.
- Zero-shot CoT underperforms zero-shot prompting on basic graph tasks, and LLMs score near 0% on disconnected nodes.
Limitations
- Evaluated only on PaLM-family models that are closed and accessed via internal serving on 4x4 TPU v4.
- Tasks are basic graph primitives with small graphs (5 to 20 nodes), not complex multi-hop graph reasoning.
- Iterative prompting methods were excluded after preliminary experiments showed poor results.
Experimental setup
Datasets: randomly generated graphs via NetworkX (ER, BA, SFN, SBM, star, path, complete)
Benchmarks: GraphQA
Metrics: accuracy
Baselines: zero-shot few-shot chain-of-thought zero-shot CoT cot-bag majority baseline
Builds on: chain-of-thought prompting zero-shot CoT Talk like a Graph bag prompting (Wang et al.) NetworkX
Closest papers by meaning
- Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models (NeurIPS 2024 · similarity 0.93)
- Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning (ICLR 2024 · similarity 0.91)
- How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension (ICLR 2025 · similarity 0.91)
- Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models (ICML 2025 · similarity 0.91)
- GraphArena: Evaluating and Exploring Large Language Models on Graph Computation (ICLR 2025 · similarity 0.90)
- $\texttt{G1}$: Teaching LLMs to Reason on Graphs with Reinforcement Learning (NeurIPS 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.