Microstructures and Accuracy of Graph Recall by Large Language Models

Yanbang Wang, Hejie Cui, Jon M. Kleinberg

This paper, presented at NeurIPS 2024, investigates a fundamental but often overlooked bottleneck in how Large Language Models (LLMs) handle structured data: Graph Recall. While much research focuses on whether LLMs can solve complex graph problems (like finding the shortest path), this study asks a simpler question: Can the model even remember the graph described in the prompt?

TL;DR

Researchers found that LLMs frequently fail at accurately recalling graph structures described in text and exhibit systematic structural biases, such as "hallucinating" triangles and alternating paths. Crucially, a model's ability to recall a graph depends heavily on whether the narrative style of the text matches the graph's real-world domain (e.g., social networks are recalled better when described as "friendships" rather than "road maps").

What Problem Does This Paper Address?

Graph-structured information is everywhere—from social networks in stories to protein interactions in biology. For an LLM to reason about these graphs, it must first "encode" the relationships into its internal state and "recall" them when prompted.

Cognitive scientists have known for decades that humans are biased when remembering social networks; we tend to "fill in the gaps" to create balanced structures (like assuming two of our friends are also friends with each other). This paper investigates whether LLMs suffer from similar "microstructural" biases and how these errors propagate to downstream reasoning tasks.

Methods

The authors designed a multi-step experimental pipeline:

  1. Task Introduction: The LLM is told it will be tested on its ability to memorize relationships.
  2. Presentation: A "vignette" (a short story) describes a graph using a specific narrative style.
  3. Memory Clearance: To simulate real-world delays, the model performs a "word span test" (recalling the last words of unrelated sentences) before the main task.
  4. Recall & Probability Extraction: The model is asked to list the edges. For GPT models, the authors used API log-probabilities to see how "confident" the model was in each edge; for Gemini, they used Monte Carlo sampling.
  5. Structural Analysis (ERGM): They used Exponential Random Graph Models (ERGM) to statistically measure if the model was biased toward specific motifs, such as triangles, stars, or "alternating 2-paths."

Datasets

The study used five distinct graph domains, each with 100 sampled graphs (5–30 nodes):

  • Social Networks: Facebook ego-networks.
  • Co-authorship: DBLP citation data.
  • Geological: California road networks.
  • Biological: Reactome protein-protein interactions.
  • Synthetic: Erdős–Rényi (random) graphs.

They also introduced a cross-evaluation framework where the same graph structure was described using different narrative "skins" (e.g., describing a road network using social friendship language).

Key Insights and Ideas

  • The "Narrative Match" Effect: This is the paper's most striking finding. LLMs (especially GPT-4) perform significantly better when the narrative style matches the graph's origin. A social graph is recalled most accurately when described as a social network. This suggests LLMs have developed "domain-specific priors"—they expect certain shapes from certain types of stories.
  • Selective Forgetting vs. Hallucination: LLMs generally tend to forget edges (omission) rather than invent them (commission). However, when they do hallucinate edges, they aren't random; they tend to "close" triangles or create specific local patterns, mirroring human cognitive biases.
  • Sensitivity to Contextual Noise: While GPT models were relatively robust, Gemini-Pro’s performance plummeted after even a small amount of "memory clearance" (distraction) tasks.
  • Recall as a Bottleneck: There is a strong correlation ($r \approx 0.8$) between a model's recall accuracy and its performance on downstream tasks like link prediction. If the model can't remember the graph, it can't reason about it.

Key Results

  • Performance Gap: No model achieved perfect recall. GPT-4 was the top performer, often hitting 90%+ accuracy on social and co-authorship graphs, but struggled significantly on random graphs (~60% accuracy).
  • Structural Bias: Models showed a statistically significant bias toward triangles and alternating 2-paths. In social domains, GPT-4's bias toward triangles was even stronger than that of humans.
  • Human Comparison: Compared to human subjects from previous cognitive studies, LLMs are generally more accurate (less forgetting) but exhibit "stronger hallucinations" of specific microstructures.

Limitations and Future Work

The authors acknowledge several constraints:

  • Graph Size: The study focused on small graphs (up to 30 nodes). Real-world applications often involve thousands of nodes.
  • Simple Narratives: The text descriptions were generated from templates. Real-world text is much noisier and more complex.
  • Model Selection: Due to the timing of the research, newer models like Llama 3 or Claude 3 were not included.

Future Direction: The authors suggest that "Graph Foundation Models" should be trained with balanced motifs to mitigate these systematic biases. They also propose that "graph-customized" versions of the "Needle in a Haystack" test could be a new benchmark for long-context LLM evaluation.

Summary updated

Abstract

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 by 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.
BibTeX
@inproceedings{wang2024microstructures,
  author = {Yanbang Wang and Hejie Cui and Jon M. Kleinberg},
  title = {{Microstructures and Accuracy of Graph Recall by Large Language Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=tNhwg9U767},
}
Figure