Microstructures and Accuracy of Graph Recall by Large Language Models
This addresses the problem of LLMs' ability to handle graph-structured data for reasoning tasks, which is crucial for applications relying on textual graph descriptions, and it is incremental as it builds on human cognitive studies.
The study investigated how large language models (LLMs) perform in recalling graphs from text, finding that they often underperform and exhibit biased microstructures like favoring triangles and alternating 2-paths, with more advanced models showing better accuracy when the graph's narration matches its original domain.
Graphs data is crucial for many applications, and much of it exists in the relations described in textual format. As a result, being able to accurately recall and encode a graph described in earlier text is a basic yet pivotal ability that LLMs need to demonstrate if they are to perform reasoning tasks that involve graph-structured information. Human performance at graph recall has been studied by cognitive scientists for decades, and has been found to often exhibit certain structural patterns of bias that align with human handling of social relationships. To date, however, we know little about how LLMs behave in analogous graph recall tasks: do their recalled graphs also exhibit certain biased patterns, and if so, how do they compare with humans and affect other graph reasoning tasks? In this work, we perform the first systematical study of graph recall by LLMs, investigating the accuracy and biased microstructures (local structural patterns) in their recall. We find that LLMs not only underperform often in graph recall, but also tend to favor more triangles and alternating 2-paths. Moreover, we find that more advanced LLMs have a striking dependence on the domain that a real-world graph comes from -- by yielding the best recall accuracy when the graph is narrated in a language style consistent with its original domain.