Can Graph Descriptive Order Affect Solving Graph Problems with LLMs?

Yuyao Ge1,5, Shenghua Liu1,5*, Baolong Bi1,5, Yiwei Wang2,
Lingrui Mei1,5, Wenjie Feng3, Lizhe Chen4, Xueqi Cheng1,5
1CAS Key Laboratory of AI Safety, Institute of Computing Technology, Chinese Academy of Sciences 2University of California, Merced
3Institute of Data Science, National University of Singapore 4Shenzhen International Graduate School, Tsinghua University, Shenzhen, China 5University of Chinese Academy of Sciences
Paper arXiv

Abstract

Large language models (LLMs) have achieved significant success in reasoning tasks, including mathematical reasoning and logical deduction. Among these reasoning tasks, graph problems stand out due to their complexity and unique structural characteristics, attracting considerable attention from researchers. Previous studies have explored LLMs’ graph reasoning abilities through various techniques, such as different encoding methods for graph structures and the use of carefully designed prompts. However, a critical factor has been mostly overlooked: the prompt sequential order in which graph descriptions are presented to the models. In this study, we present the first comprehensive analysis of how the order of graph descriptions impacts LLM performance. Specifically, we comprehensively evaluate four graph description orders across six graph problems using six mainstream LLMs. The results reveal that: (1) ordered graph descriptions significantly improve LLMs’ comprehension of graph structures; (2) the robustness of LLMs to graph description order varies across different tasks; and (3) the impact of graph order on performance is closely related to the inherent characteristics of tasks. Our study provides a critical advancement in the application of LLMs for solving graph-related problems, paving the way for future research to optimize model performance through strategic graph description ordering.



Research Highlights

  • First Comprehensive Analysis: Unraveling the impact of graph description order on LLM performance.
  • Significant Performance Gains: Ordered descriptions (BFS, DFS, PR, and PPR) yield marked improvements across diverse graph tasks.
  • GraphDO Dataset: A novel benchmark dataset that propels research in graph reasoning with LLMs.

Methodology



Our study pioneers a systematic exploration into how the sequential ordering of graph descriptions affects the reasoning capabilities of LLMs. By evaluating four distinct ordering strategies—breadth-first, depth-first, PageRank, and Personalized PageRank—across six rigorous graph tasks, we demonstrate that a well-structured narrative of graph data can dramatically boost LLM performance.



Experiement

Ordered graph descriptions consistently outperform the random baseline across all traditional graph tasks and prompt configurations. Moreover, simpler tasks like connectivity and cycle detection exhibit low variance, indicating strong robustness in LLM reasoning. However, more complex tasks (e.g., Hamilton path, topological sort, and shortest path) show higher variance, with the shortest path task being the most impacted due to its reliance on weighted graphs, where description order significantly influences complexity. Additionally, BFS generally outperforms DFS in tasks such as cycle detection, connectivity detection, and shortest path. On the other hand, for tasks requiring deeper exploration, such as topological sort and Hamilton path, DFS performs better.



Similarly, ordered descriptions consistently outperform the baseline in node classification tasks. However, the improvements in node classification are generally less pronounced than those observed in traditional graph tasks. For instance, in the Pubmed dataset with ego-graph sampling, the PR order boosts accuracy by 14.82%, marking the largest improvement in node classification tasks. Notably, for node classification, the PR order consistently outperforms the PPR across all datasets, while PPR generally performs better than traversal-based orders.



We hypothesize that LLMs' improved performance with ordered descriptions stems from limitations in positional encoding and attention mechanisms—what we call attention bias. Positional encodings, which are meant to provide sequence information in transformer models, may not effectively capture the structural complexity of graph data when the input sequence is unordered. Guided by positional encodings, attention mechanisms can give undue priority to certain sections of the input based on their order in the sequence, leading to over-dependence on the graph description.

Conclusion

In this work, we conduct the first comprehensive analysis of how graph description order affects LLM performance in solving graph problems. Our findings demonstrate that ordered graph descriptions significantly enhance LLMs' ability to comprehend and reason about graph structures, a crucial discovery that could reshape the way we approach graph reasoning tasks. Additionally, through detailed analysis of various graph description orders, we observe that the impact of order on performance is closely tied to the intrinsic characteristics of each task. We believe that the over-reliance on graph descriptions stems from limitations in positional encoding—what we refer to as attention bias. Lastly, we int roduce the GraphDO dataset, which aims to advance the community’s understanding of how graph descriptions influence reasoning in LLMs, providing a valuable benchmark for future research in this area.

BibTeX

@misc{ge2024graphdescriptiveorderaffect,
        title={Can Graph Descriptive Order Affect Solving Graph Problems with LLMs?}, 
        author={Yuyao Ge and Shenghua Liu and Baolong Bi and Yiwei Wang and Lingrui Mei and Wenjie Feng and Lizhe Chen and Xueqi Cheng},
        year={2024},
        eprint={2402.07140},
        archivePrefix={arXiv},
        primaryClass={cs.AI},
        url={https://arxiv.org/abs/2402.07140}, 
  }