Can LLM Graph Reasoning Generalize beyond Pattern Memorization? (2024)

Abstract: Large language models (LLMs) demonstrate great potential for problems with implicit graphical structures, while recent works seek to enhance the graph reasoning capabilities of LLMs through specialized instruction tuning. The resulting “graph LLMs” are evaluated with in-distribution settings only, thus it remains underexplored whether LLMs are learning generalizable graph reasoning skills or merely memorizing patterns in the synthetic training data. To this end, we propose the NLGift benchmark, an evaluation suite of LLM graph reasoning generalization: whether LLMs could go beyond semantic, numeric, structural, reasoning patterns in the synthetic training data and improve utility on real-world graph-based tasks. Extensive experiments with two LLMs across four graph reasoning tasks demonstrate that while generalization on simple patterns (semantic, numeric) is somewhat satisfactory, LLMs struggle to generalize across reasoning and real-world patterns, casting doubt on the benefit of synthetic graph tuning for real-world tasks with underlying network structures. We explore three strategies to improve LLM graph reasoning generalization, and we find that while post-training alignment is most promising for real-world tasks, empowering LLM graph reasoning to go beyond pattern memorization remains an open research question.

## introduction large language models (llms) are increasingly employed for tasks at the intersection of language and structure such as multi-hop qa @xcite and structured commonsense reasoning @xcite . these problems are often described in natural language and have implicit graphical structures @xcite @xcite , where llms' graph reasoning capabilities are tested. while llms do possess preliminary abilities to represent and reason with graphs @xcite , they also face challenges such as hallucinations @xcite and prompt sensitivity @xcite when dealing with structured data. existing works seek to improve llm graph reasoning mainly through better prompting @xcite or instruction tuning @xcite , while the latter line of training-based approaches is generally more effective in producing specialized models for graphbased applications @xcite @xcite . however, these approaches are often evaluated in indistribution settings, while robust graph reasoners should go beyond training sets to encode general and transferable graph reasoning capabilities in model parameters. consequently, we ask: are llms graph reasoners or merely pattern regurgitators? more concretely, can llm graph reasoning go beyond memorizing patterns in the training data and perform well in out-of-distribution contexts? the answer to this question has profound implications for llm reliability in structured contexts since real-world graph-based problems are diverse, heterogeneous, and constantly evolving. to this end, we propose nlgift, a comprehensive testbed of natural language graph reasoning with shifting patterns. nlgift contains 37,000 problems in total, where llms are instruction tuned on a subset of problems with distribution d train and evaluated on both in-distribution d train and out-of-distribution d test test sets. nlgift features five types of patterns where llms should generalize beyond: 1) semantic, 2) numerical, 3) structural, 4) reasoning, and 5) real-world patterns. the first four settings focus on transferring across patterns in the synthetic graph data, while the realworld pattern focuses on the transfer from synthetic 2289 0 1 2 3 4 5 the following text describes an undirected graph. determine if there is a path between two nodes in the graph. node 0 is connected to 1, … q: is there a path between node 4 and node 3? g describes a friendship graph among the following people. we have the following edges in g: evan and willow are friends… q: is there a path between node christian and node thomas? in a directed graph, the nodes are numbered from 0 to 6, and the edges are: node 1 is connected to node 3 with capacity 2. node 5 is connected to node 1 with capacity 8… q: what is the maximum flow from node 6 to node 3? in a directed graph, the nodes are numbered from 0 to 6, and the edges are: node 1 is connected to node 3 with capacity 4.0. node 5 is connected to node 1 with capacity 6.2… q: what is the maximum flow from node 6 to node 3? the following text describes a directed graph among 0, 1, 2, 3, 4. node 1 should be visited before nodes 0… q: can all the nodes be visited? give the solution. the following text describes an undirected graph. determine if there is a path between two nodes in the graph. node 0 is connected to 1, 2… q: is there a path between node 4 and node 3? the following paragraph describes an undirected graph with weights. the following text describes an undirected graph. determine if there is a path between two nodes in the graph. node 0 is connected to 1, 2… q: is there a path between node 4 and node 3? the following paragraph describes an undirected graph with weights. node 0 is connected to node 4 with weight 1, node 5 with weight 10… q: what is the shortest path between node 1 and node 0, and what is the length of the shortest path? please answer the following question with either yes or no: has a neanderthal ever served on the supreme court of the united states? train on connectivity & shortest path test on realistic task 5. realistic pattern 0 4 5 1 10 1 7 neanderthal primitive humans lived 40,000 years ago established in 1798 supreme court of u.s. after are has attribute ha s at tr ib ut e figure 1 : overview of the nlgift benchmark, featuring five types of graph reasoning patterns that are increasingly challenging in order. we present an example for each pattern to show the transfer from training to test sets. to quantify the success of generalization, nl-gift establishes two standards: 1) the basic standard: significant transfer, i.e., the tuned model's improvement on out-of-distribution test sets over the zero-shot untuned model is statistically significant; 2) the strong standard: strong recovery, i.e., when evaluated on out-of-distribution data, the tuned llms could substantially recover the gains of in-distribution training. robust graph reasoners should ideally meet both basic and strong generalization standards across the five patterns. extensive experiments on nlgift with two llms demonstrate that on easier patterns (semantic, numerical, and structural), llms achieve the basic standard 75% of the time but only reach the strong standard in 35% of settings. on reasoning patterns, llms only achieve basic generaliza-tion 33% of the time while never qualify for the strong standard of generalization. what's worse, on the most challenging real-world patterns, llms achieve basic generalization in 6% of the settings while graph instruction tuning is counterproductive in 69% of cases, casting doubt on the benefit of synthetic graph data. further analysis reveals that task composition and keyword frequency in training corpus greatly impact graph reasoning generalization. we explore three preliminary strategies to augment llm graph reasoning generalization: code mixing, machine-generated cots, and posttraining alignment. while post-training alignment is most promising on real-world tasks, empowering llms with general and transferable graph reasoning abilities remains an open research question. to sum up, our key contributions include presenting the nlgift benchmark, evaluating llm graph reasoning generalization with diverse tasks and patterns, as well as exploring preliminary solutions to mitigate the profound generalization challenges. ## nlgift benchmark to examine whether llms are capable of robust reasoning with graph problems rather than memorizing training patterns, we present the nlgift benchmark (figure 1 ). specifically, we select four representative graph reasoning tasks: connectivity, shortest path, topological sort, and maximum flow. we then design five patterns that llms should generalize beyond. we present the five patterns in ascending order of difficulty so that they can serve as a progressive testbed. ## experiment settings we evaluate the graph reasoning capabilities of two llms: chatgpt (gpt-3.5-turbo) @xcite and llama2-7b (meta-llama/llama-2-7b-chat-hf) @xcite . we empirically employ temperature τ = 1 and τ = 0.9 for the two models respectively to ## results we evaluate llm graph reasoning generalization with nlgift across diverse data patterns: while generalization on simple patterns (semantic, numerical and structural) is somewhat satisfactory, llms struggle to generalize across the more challenging reasoning and real-world patterns, casting doubt on the benefit of synthetic graph tuning for real-world tasks with underlying network structures. ## analysis mixture of graph tasks real-world generalization gaps in llm graph reasoning might be less clear-cut: certain distributions might be underrepresented instead of outright missing. thus we investigate reasoning pattern generalization by keeping a majority task while gradually mixing other tasks in the training data. for a total of 500 training data points, we keep the majority task as shortest path with x%, while mixing the other three tasks of 1 3 (100x)% each. results in figure 3 with chatgpt show that when other tasks are present, the performance of the majority task (shortest path) drops dramatically by up to 43%, while we see higher performance for other simpler tasks (connectivity and topological sort). for tasks on the harder end (e.g. maximum flow), the performance didn't improve even 25% of training data is the maximum flow task. this suggests that even for chatgpt, instruction tuning on the mixture of graph tasks may not be the most effective option to improve overall performance on graph tasks. ## improving graph reasoning generalization results on the nlgift benchmark show llms are not robust graph reasoners but mostly pattern regurgitators, as they show limited capabilities when testing on out-of-distribution data across various settings. to improve llm graph reasoning generalization, we explore three preliminary strategies. mixing code previous works show that language models trained on code might be better reasoners with structures @xcite , as code data is naturally more structured than linear sequences of texts. we explore incorporating code into the instruction tuning data to improve graph reasoning generalization. specifically, we use two types of code instruction tuning data: general code instruction tuning data @xcite and graphrelated code filtered from greengerong (2023) using a list of graph-related keywords. we add 200 randomly selected samples to each training set of synthetic graph data for instruction tuning. machine-generated chain of thoughts in previous experiments, we generate intermediate reasoning paths for instruction tuning with predefined rules for each graph task. however, this handcrafted reasoning path might be different from llms' internal reasoning process, thus one possible improvement is to utilize chatgpt's output as machine-generated chain of thoughts (cots), and then filter out the correct response to further fine-tune llama2-7b. we hope this distillation of graph reasoning cots from a stronger model to a weaker one would help generalization. preference alignment in addition to adapting llms for graph reasoning through instruction tuning, we adopt direct preference optimization (dpo) @xcite to improve graph reasoning at the alignment stage. dpo aims to further refine the model's reasoning capabilities by learning from human preferences. it involves a labeled input pair (r w , r l ) where r w and r l are preferred and dispreferred responses. to be specific, we use the training sets in nlgift and sample five solutions from chatgpt to select preferred and dispreferred based on answer correctness, resulting in around 200 dpo pairs for each task. we then apply dpo on previously fine-tuned models and evaluate them on the same test set. ## related work a series of works have explored employing llms for graph learning and reasoning. @xcite propose one of the first natural language graph reasoning benchmarks, nlgraph, and show that llms have preliminary graph reasoning abilities while being brittle to spurious correlations in graphs. many works focus on designing prompts to elicit or evaluate the graph reasoning abilities of llms @xcite @xcite @xcite @xcite , among which fatemi et al. (2024) study encoding graphs with different semantic descriptions such as friend networks and find that graph encoding function has a significant impact on llm graph reasoning. besides prompt-based methods, perozzi et al. (2024) further replace the text-template-based graph encoder with graph neural network encoders, which improves the performance on graph reasoning tasks; wang et al. (2024) use instruction tuning and preference alignment to improve the graph reasoning ability of llms; li et al. (2024) incorporate the visual modality and evaluate large multimodal models on graph reasoning problems. another line of work aims at real-world graph tasks such as node classification @xcite @xcite , or tasks with implicit graph structures such as multi-hop knowledge qa @xcite . these methods can mainly be divided into three categories @xcite : 1) llms-as-enhancers, where llms are utilized to enhance the quality of node embeddings for gnns @xcite ; 2) llms-as-predictors, where llms directly make predictions for graph-related tasks @xcite ; and 3) gnn-llm alignment, where the embedding spaces of gnns and llms are aligned to integrate the graph modality with the text modality @xcite . although there is great improvement in llm graph reasoning through specialized instruction tuning, we hypothesize that llms might be merely memorizing in-distribution patterns, thus the learned graph reasoning skills are not general and transferable. we study the generalization across graph reasoning patterns and provide insights for future works on improving graph reasoning abilities. ## conclusion we propose nlgift, an evaluation suite of llm graph reasoning generalization across semantic, numerical, structural, reasoning, and real-world patterns. extensive experiments demonstrate that while llms are somewhat robust to changes in the graphs' semantic and numerical attributes, it is hugely challenging to generalize beyond synthetic reasoning patterns and benefit real-world tasks involving networks and structures. we explore three preliminary solutions: while post-training alignment is the most promising, empowering llms to go beyond memorizing synthetic patterns in the training data remains an open research question.