GraphInsight: Unlocking Insights in Large Language Models for Graph Structure Understanding
Yukun Cao, Shuo Han, Zengyi Gao, Zezhong Ding, Xike Xie, S. Kevin Zhou
Abstract
Although Large Language Models (LLMs) have demonstrated potential in processing graphs, they struggle with comprehending graphical structure information through prompts of graph description sequences, especially as the graph size increases. We attribute this challenge to the uneven memory performance of LLMs across different positions in graph description sequences, known as "Positional bias". To address this, we propose GraphInsight, a novel framework aimed at improving LLMs' comprehension of both macro-and micro-level graphical information. GraphInsight is grounded in two key strategies: 1) placing critical graphical information in positions where LLMs exhibit stronger memory performance, and 2) investigating a lightweight external knowledge base for regions with weaker memory performance, inspired by retrieval-augmented generation (RAG). Moreover, GraphInsight explores integrating these two strategies into LLM agent processes for composite graph tasks that require multi-step reasoning. Extensive empirical studies on benchmarks with a wide range of evaluation tasks show that GraphInsight significantly outperforms all other graph description methods (e.g., prompting techniques and reordering strategies) in understanding graph structures of varying sizes.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
7 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Efficient Streaming Language Models with Attention Sinks cites Language Models are Few-Shot Learners
- ArchRAG: Attributed Community-based Hierarchical Retrieval-Augmented Generation cites Language Models are Few-Shot Learners
- LEGO-GraphRAG: Modularizing Graph-based Retrieval-Augmented Generation for Design Space Exploration cites Language Models are Few-Shot Learners
- MA-GTS: A Multi-Agent Framework for Solving Complex Graph Problems in Real-World Applications cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- Graph of Thoughts: Solving Elaborate Problems with Large Language Models cites Language Models are Few-Shot Learners
- Graph of Thoughts: Solving Elaborate Problems with Large Language Models cites Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- Time-LLM: Time Series Forecasting by Reprogramming Large Language Models cites Language Models are Few-Shot Learners
Cited by top-tier papers7
- PathRAG: Pruning Graph-based Retrieval Augmented Generation with Relational PathsBoyu Chen, Zirui Guo, Zidan Yang, Yuluo Chen et al.AAAI 2026 · 45 citations
- ArchRAG: Attributed Community-based Hierarchical Retrieval-Augmented GenerationShu Wang, Yixiang Fang, Yingli Zhou, Xilin Liu et al.AAAI 2026 · 23 citations
- LEGO-GraphRAG: Modularizing Graph-based Retrieval-Augmented Generation for Design Space ExplorationYukun Cao, Zengyi Gao, Zhiyang Li, Xike Xie et al.VLDB 2025 · 5 citations
- DuetGraph: Coarse-to-Fine Knowledge Graph Reasoning with Dual-Pathway Global-Local FusionJin Li, Zezhong Ding, Xike XieNeurIPS 2025 · 5 citations
- MA-GTS: A Multi-Agent Framework for Solving Complex Graph Problems in Real-World ApplicationsZike Yuan, Ming Liu, Hui Wang, Bing QinEMNLP 2025
Builds on16
- Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 · 64,255 citations
- Chain-of-Thought Prompting Elicits Reasoning in Large Language ModelsJason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma et al.NeurIPS 2022 · 22,562 citations
- Efficient Streaming Language Models with Attention SinksGuangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han et al.ICLR 2024 · 1,714 citations
- Graph of Thoughts: Solving Elaborate Problems with Large Language ModelsMaciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger et al.AAAI 2024 · 1,292 citations
- Time-LLM: Time Series Forecasting by Reprogramming Large Language ModelsMing Jin, Shiyu Wang, Lintao Ma, Zhixuan Chu et al.ICLR 2024 · 915 citations
Related papers
- Empowering GraphRAG with Knowledge Filtering and IntegrationKai Guo, Harry Shomer, Shenglai Zeng, Haoyu Han et al.EMNLP 2025 · 2 citations
- Retrieval-Augmented Generation with Hierarchical KnowledgeHaoyu Huang, Yongfeng Huang, Junjie Yang, Zhenyu Pan et al.EMNLP Findings 2025 · 20 citations
- Can Graph Descriptive Order Affect Solving Graph Problems with LLMs?Yuyao Ge, Shenghua Liu, Baolong Bi, Yiwei Wang et al.ACL 2025
- MemGraphRAG: Memory-based Multi-Agent System for Graph Retrieval-Augmented GenerationChuanjie Wu, Zhishang Xiang, Yunbo Tang, Zerui Chen et al.KDD 2026 · 1 citation
- A Systematic Exploration of Knowledge Graph Alignment with Large Language Models in Retrieval Augmented GenerationShiyu Tian, Shuyue Xing, Xingrui Li, Yangyang Luo et al.AAAI 2025 · 3 citations
