Paper Review | Talk Like a Graph: Encoding Graphs for Large Language Models
Institute: Google Research
Authors: Bahare Fatemi, Jonathan Halcrow, Bryan Perozzi
Link: https://arxiv.org/abs/2310.02207
Introduction
This paper feeds graphs into an LLM using a variety of natural-language formulations and measures how performance changes.
Background
There are currently four ways in the literature to tackle graph problems with an LLM:
Natural-language input
Embedding
LLM tuning
Hybrid: GNN & LLM
This paper focuses on the first of these. The authors report that encoding graphs according to the patterns they uncover here improves LLM performance on graph reasoning tasks by anywhere from 4.8% to 61.8%.
Contributions
The authors search for the best way to have an LLM handle graph reasoning problems, splitting the question into two aspects:
encoding
prompt
They introduce a new set of benchmarks, GraphQA
Encoding
Encoding a graph as text breaks down into two parts: encoding the nodes and encoding the edges.
Encoding Nodes:
Integers
English surnames
Characters from film and television
Politicians’ surnames
Letters
Encoding Edges:
Parentheses
Friendship
Co-authorship
Social relations
Arrows
Connection, e.g. Node 0 is connected to nodes 1, 2.
The graph encodings studied in this paper are combinations of the two lists above:
Adjacency: integers + parentheses
Incident: integers + connection
Friendship: English surnames + friendship
Co-authorship: English surnames + co-authorship
SP: characters from film and television + friendship
GOT: characters from film and television + friendship
Social network: English surnames + social relations
Politician: politicians’ surnames + social relations
Expert: letters + arrows
Prompt
Zero-shot prompting (ZERO-SHOT): describe the problem and ask directly
Few-shot in-context learning (FEW-SHOT): provide examples
Chain-of-thought (CoT): provide examples together with the steps that solve them
Zero-shot CoT prompting (ZERO-COT): provide the solution steps but no examples — “Let’s think step by step”
BAG prompting (COT-BAG)
GraphQA
GraphQA covers a range of elementary graph problems:
Edge existence
Node existence
Node counting
Edge counting
Connectivity
Cycle check
Disconnected nodes
Experiments
1. Encoding & Prompt
Model used: PaLM 62B
LLMs perform poorly on basic graph problems
On simple graph tasks ZERO-SHOT beats ZERO-COT; on complex tasks the ordering reverses
The choice of encoding has a large effect on performance
Encoding nodes as integers improves performance
2. Varying Prompt Questions
- In the vast majority of experiments, casting the graph question as a real-world question improves model performance
3. Encoding with multiple relation types
Using several relation types to encode a graph does not hurt LLM performance — it actually improves it
The improvement may come from diverse relations being closer to the LLM’s training distribution
4. Model capacity
- Model capacity has a pronounced effect on performance
5. Reasoning about disconnected nodes
- Accuracy is close to zero: LLMs have almost no ability to reason about disconnected nodes
6. Does graph shape matter?
Graph structure significantly affects LLM performance
Extraneous structure in the graph hurts the LLM: performance is best on path- and star-shaped graphs
Providing examples and reasoning chains improves LLM performance
Conclusion
LLMs perform poorly on basic graph problems
The graph encoding scheme significantly affects LLM performance
The number of model parameters has a pronounced effect on accuracy
Reflections
On models
a. How would 6B or 7B models perform?
b. Encoding schemes adapted to small models
c. Why do no emergent abilities show up on graph problems?
The graphs used in the experiments are mostly small
a. What is the relationship between LLM performance and graph size?
b. Could an input format be designed specifically for large graphs?
Why do LLMs do better on real-world graph problems? Does this phenomenon appear on other problems as well?
Could LoRA or LoRA tuning be used to improve model performance?
Why is there no comparison against embedding-based approaches?
How do LLMs perform on shortest-path problems? Is the complexity the same as for cycle problems?
