PaperlayerView exact revision on arXiv

Source-linked AI summary

Talk like a Graph: Encoding Graphs for Large Language Models

Bahare Fatemi, Jonathan Halcrow, Bryan Perozzi

arXiv:2310.04560v1cs.LG

TL;DR

LLM reasoning over graphs remains understudied despite the importance of relational information and the limitations of unstructured text. This paper comprehensively studies encoding graphs as text for LLMs, finding that performance varies with encoding, task, and graph structure, with gains of 4.8% to 61.8%.

  • Problem

    LLM reasoning over graph-structured data remains understudied, despite graph data’s role in representing relational information and limitations of unstructured text.

  • Method

    The paper studies graph encoding and prompt engineering for fixed, black-box LLMs using graph data encoded as text.

  • Results

    LLM performance varies with graph encoding method, graph task, and graph structure, while suitable encoders boost performance by 4.8% to 61.8%.

  • Takeaways & Limitations

    The findings provide insights into strategies for encoding graphs as text and motivate further investigation using the GraphQA benchmark.

  • Takeaways & Limitations

    The study focuses on fixed, black-box LLMs and excludes iterative prompting after initial experiments found cascading errors.

Abstract

from arXiv · show

Graphs are a powerful tool for representing and analyzing complex relationships in real-world applications such as social networks, recommender systems, and computational finance. Reasoning on graphs is essential for drawing inferences about the relationships between entities in a complex system, and to identify hidden patterns and trends. Despite the remarkable progress in automated reasoning with natural text, reasoning on graphs with large language models (LLMs) remains an understudied problem. In this work, we perform the first comprehensive study of encoding graph-structured data as text for consumption by LLMs. We show that LLM performance on graph reasoning tasks varies on three fundamental levels: (1) the graph encoding method, (2) the nature of the graph task itself, and (3) interestingly, the very structure of the graph considered. These novel results provide valuable insight on strategies for encoding graphs as text. Using these insights we illustrate how the correct choice of encoders can boost performance on graph reasoning tasks inside LLMs by 4.8% to 61.8%, depending on the task.

1 INTRODUCTION

The paper studies how to make LLMs reason over graph-structured data represented as text, addressing an understudied intersection with varied graph tasks and structures. It introduces a comprehensive encoding study and the GraphQA benchmark to evaluate these choices.

  • Graph-structured data may address LLM limitations caused by reliance on unstructured text and difficulty incorporating fresh information.
  • General-purpose use of graph-structured data with LLMs remains understudied, while prior benchmarking omitted several natural graph tasks and varied graph structures.
  • The paper performs the first comprehensive study of reasoning over graph-structured data encoded as text for LLM consumption.
  • GraphQA benchmarks LLM reasoning with graphs having more varied and realistic structures than previously studied.
  • The work contributes an extensive study of graph-structure prompting techniques, graph-encoding best practices, and a benchmark for studying graph structure effects on prompting.

2 PROMPTING LLMS FOR GRAPH REASONING

The paper formulates black-box graph reasoning as choosing graph encodings and question rephrasings that help a fixed text-only LLM answer questions about relational information. It examines prompting heuristics and graph structures while optimizing graph encoding on basic graph tasks.

  • 2 PROMPTING LLMS FOR GRAPH REASONING: The framework represents a graph as G = (V, E), where V contains vertices and E contains edges connecting them.
  • 2.1 PROMPT ENGINEERING: Prompt engineering seeks a question phrasing Q that makes an LLM f return the corresponding answer A.
  • 2.1 PROMPT ENGINEERING: The study targets black-box LLM use, keeping model parameters fixed and restricting interaction to text inputs and outputs.
  • 2.1 PROMPT ENGINEERING: The graph encoding function g maps graphs to tokens, while the question rephrasing function q maps questions to tokens.
  • 2.1 PROMPT ENGINEERING: The answer is modeled as A = f(g(G), q(Q)), with training examples consisting of graph, question, and solution triples.
  • 2.1 PROMPT ENGINEERING: The paper studies graph encoding, question rephrasing, and graph structure as factors in optimizing prompt-system performance.
  • 2.2 PROMPTING HEURISTICS: The prompting heuristics include zero-shot prompting and few-shot in-context learning using task examples and desired outputs.
  • 2.2 PROMPTING HEURISTICS: Iterative prompting performed worse in initial experiments because of cascading errors, so the paper concentrates on other prompting methods.

3 TALK LIKE A GRAPH: ENCODING GRAPHS VIA TEXT

This section studies how graph encodings, prompt formulations, graph structures, and model capacity affect LLM performance on graph reasoning tasks. Results show that performance is generally weak but can vary substantially with these choices.

  • Results: LLMs performed poorly on almost all basic graph tasks, often falling below majority baselines on edge existence and cycle checking.In the experiment, no edge occurred 53.96% of the time, while cycles occurred 81.96% of the time.
  • Prompting: Prompt complexity depended on task complexity: zero-shot prompting was better for simple tasks, while few-shot and chain-of-thought prompting generally helped more complex tasks.The paper attributes this pattern to simple tasks requiring less multi-hop reasoning and richer prompts providing task examples or answer-finding steps.
  • Graph encoding function: Graph encoding function choice significantly affected performance across graph reasoning tasks.The study separately examines node and edge encodings, with different encoders capturing different aspects of graph structure.
  • Graph encoding function: For connected-nodes prediction, adjacency achieved 19.8% accuracy while incident encoding achieved 53.8% accuracy.Incident encoding also outperformed other encoders for node degree and connected-nodes tasks, likely by placing relevant information closer together.
  • Graph encoding function: Integer node encoding improved integer-output tasks, whereas named encodings worked better for some non-integer-output tasks.Integer-output examples include node degree, node count, and edge count; named examples include edge existence and cycle check.
  • Question encoding: Application-style question encoding outperformed graph-style question encoding on almost all tasks despite using the same graph encoding function.For ZERO-SHOT edge existence with PaLM 2 XXS, accuracy was 42.8% for graph encoding and 60.8% for application encoding.

4 DOES THE STRUCTURE OF THE GRAPH MATTER FOR THE LLM?

The study finds that graph structure significantly affects LLM performance, motivating diverse graph generators and revealing structure-dependent effects across tasks. Fewer edges, simpler encodings, and out-of-distribution few-shot examples generally improve performance.

  • Benchmark design: GraphQA uses diverse generators to cover varied properties, reduce evaluation bias, and create more realistic benchmarks.The generators include ER, scale-free, BA, SBM, star, path, and complete graphs.
  • Results: Graph structure significantly affects LLM performance across graph reasoning tasks.The graph-generation algorithm changes task performance, so evaluation should include varied graph structures.
  • Results: 91.7% accuracy on cycle check occurs on complete graphs versus 5.9% on path graphs.Adding mixed few-shot examples raises path-graph cycle-check accuracy from 5.9% to 19.7%.
  • Results: 60.0% edge-existence accuracy on path graphs exceeds 19.8% on complete graphs.These results align with priors that nodes are more likely to be disconnected.
  • Results: Node degree, node count, and connected-nodes accuracy is highest on star and path graphs and among the lowest on complete graphs.Complete graphs require many edge specifications, producing more distracting statements.
  • Prompting: Out-of-distribution few-shot examples help on most tasks and need not come from the same graph generator.Their main role is to explain the task to the LLM.

5 RELATED WORK

Related work spans in-context learning, text-based reasoning, knowledge-augmented LLMs, and graph learning with LLMs. This study extends that literature by systematically examining graph encodings, questions, and graph structures through GraphQA.

  • In-context learning: In-context learning and fine-tuning can improve reasoning but may require substantial computation, domain-specific data, and human expertise.The paper distinguishes prompt-based methods from approaches requiring model training or modification.
  • Text-based reasoning: Text-based reasoning research includes modular reasoning and single-call prediction approaches using LLMs.Modular methods divide problems into smaller modules handled by distinct language models.
  • Knowledge-augmented LLMs: Knowledge-augmented LLM research uses knowledge graphs to improve world understanding through added training data or extended pretraining.The reviewed methods range from generating training data from knowledge graphs to extending pretraining.
  • Graph reasoning with LLMs: Graph-learning research applies LLMs to node classification, text-attributed graphs, and graph-reasoning benchmarks.The paper identifies Wang et al. as the closest prior benchmarking work.
  • Present work: This study contributes extensive experiments on graph, question, and graph-generator functions plus the GraphQA benchmark.It focuses on basic graph tasks as intermediate steps toward more complex graph reasoning.

6 CONCLUSIONS

The paper presents a comprehensive study of encoding graph-structured data as text for LLMs. It shows that performance varies with encoding method, task type, and graph structure, with encoder choices boosting performance by 4.8% to 61.8%.

  • Conclusions: 4.8% to 61.8% performance boosts result from choosing graph encoders suited to graph reasoning tasks.The reported gains depend on the task.
  • Conclusions: LLM graph-reasoning performance varies with graph encoding method, graph task, and graph structure.The study presents these as three fundamental levels of variation.
  • Conclusions: GraphQA is intended to inspire additional research on graph reasoning with LLMs.The authors describe the area as a fruitful avenue for further investigation.

A.1 GRAPH ENCODING FUNCTION

The paper represents graphs as text by separately encoding nodes and edges, then combining these choices into graph encoding functions. It illustrates integer, name-based, alphabetic, and relation-specific encodings on a running graph.

  • Encoding design: Graph-to-text encoding separates the representation of nodes from the representation of edges.The resulting components are combined into graph encoding functions.
  • Encoding Nodes: Node encodings include integers, English first names, television characters, politicians’ names, and alphabet letters.These choices instantiate different semantic and surface forms for graph nodes.
  • Representing Edges: Edge encodings include parenthesized source-target pairs and relation descriptions such as friendship, coauthorship, social connection, and incident links.The paper examines several natural-language relation types alongside structural notation.
  • Graph encoding functions: The evaluated graph encoders combine node and edge schemes, including Adjacency, Incident, Friendship, Co-authorship, SP, GOT, Social network, Politician, and Expert.Expert encoding uses alphabet letters, arrows, and the instruction “You are a graph analyst.”
  • Examples: GOT, Social Network, Politician, and Expert provide additional named examples of node and edge representations.These examples use Game of Thrones characters, English names, American politicians, or alphabet letters.
  • Examples: The running example instantiates the encodings on the same graph using integers, named characters, social relations, or alphabetic labels.The examples include adjacency lists, incident descriptions, friendship and co-authorship relations, and character-based variants.

A.2 GRAPH TASKS

GraphQA evaluates LLM reasoning across diverse basic graph-analysis tasks, spanning existence checks, quantitative assessments, and relational or structural challenges. These tasks are simple but serve as foundations for more complex graph reasoning.

  • GraphQA includes edge existence, node degree, node count, edge count, connected nodes, cycle check, and disconnected nodes tasks.
  • The task suite combines discriminative challenges such as cycle checking with generative challenges such as finding connected or disconnected nodes.
  • The tasks cover existence checks, quantitative assessments, and path-related graph analysis.
  • Basic graph tasks support more complex reasoning, including shortest-path determination, community detection, and identifying influential nodes.

A.3 GRAPH ENCODING RANKINGS

The paper ranks graph encoders by their average standing across graph tasks, with lower ranks indicating better performance. Incident encoding performs best for most prompting methods, while zero-shot prompting favors node tokens with established representations in some cases.

  • Encoder rankings aggregate average standing across graph tasks, where a lower number indicates a higher-ranked encoder.
  • Incident encoding performs best for most prompting methods.
  • For zero-shot graph prompting, node tokens with established representations perform best in some cases.

A.4 IMPLEMENTATION DETAILS

The experiments use PaLM models with deterministic decoding and NetworkX-generated random graphs. The graph data spans four random graph families plus star, path, and complete graph generators across graphs of 5 to 20 nodes.

  • Experiments use PaLM 62B and PaLM 2 models served on a 4 × 4 TPU v4 architecture with decoding temperature set to zero.
  • NetworkX generates the random graphs and computes answers to the graph tasks.
  • The study samples 500 graphs each for ER, BA, SFN, and SBM, and 100 each for path, complete, and star graphs.
  • All generated graphs contain between 5 and 20 nodes.

A.5 EVALUATING MORE LLMS FOR GRAPH TASKS WITH DIFFERENT GRAPH ENCODING FUNCTIONS

The paper extends graph-encoding comparisons beyond PaLM 62B to multiple PaLM 2 sizes and instruction-finetuned Flan checkpoints. Tables 6–14 report encoder performance across graph tasks, identifying the best prompting heuristic and encoder for each setting.

  • Graph-encoding functions are evaluated on PaLM 2 XXS, XS, S, and L models in additional experiments.
  • Instruction-finetuned Flan checkpoints are also evaluated for the PaLM 2 XXS and XS model sizes.
  • Tables 6, 8, 10, and 11 compare graph encoders across tasks for PaLM 2 XXS, XS, S, and L, respectively.
  • Tables 7 and 9 report corresponding comparisons for Flan-PaLM 2 XXS and XS.
  • The tables underline the most effective prompting heuristic and bold the top-performing graph encoder for that heuristic.
Loading 2310.04560v1…