GraphInsight: Unlocking Insights in Large Language Models for Graph Structure Understanding (2025.acl-long)
Copied to clipboard
| Challenge: | Large language models struggle with comprehending graphical structure information through prompts of graph description sequences, especially as the graph size increases. |
| Approach: | They propose a framework to improve LLMs’ comprehension of both macro- and micro-level graphical information by placing critical graphical data in positions where LLM's exhibit stronger memory performance. |
| Outcome: | The proposed framework outperforms all other graph description methods in understanding graph structures of varying sizes. |
Similar Papers
Graph-Assisted Large Language Models: A Perspective on Mitigating Intrinsic Limitations (2026.findings-acl)
Copied to clipboard
Haitong Luo, Fali Wang, Weiyao Zhang, Xianren Zhang, Zhiwei Zhang, Tianxiang Zhao, Minhua Lin, Jiahao Zhang, Hui Liu, Xianfeng Tang, Qi He, Suhang Wang, Xuying Meng, Yujun Zhang
| Challenge: | Large language models exhibit intrinsic limitations such as knowledge cutoff, single-threaded reasoning that hinders finer-grained branch and aggregation, and rigid collaboration mechanisms that struggle to coordinate specialized capabilities. |
| Approach: | They propose a taxonomy spanning *Graph-Assisted Knowledge Augmentation*, *Graph Assisted Reasoning and Planning*, and *Graphed LLM Collaboration*. |
| Outcome: | The proposed models show that graphs can augment and correct LLMs and support dynamic coordination among experts and agents in collaborative settings. |
Exploring Graph Learning Tasks with Pure LLMs: A Comprehensive Benchmark and Investigation (2026.findings-acl)
Copied to clipboard
| Challenge: | Recent studies focus on performance benchmarks without fully comparing LLMs to graph learning models. |
| Approach: | They evaluate off-the-shelf and instruction-tuned graph learning models across a variety of scenarios. |
| Outcome: | The proposed models outperform traditional graph learning models in few-shot settings, the authors show . their models out perform models with instruction tuning, and they show excellent generalization and robustness. |
GraphEval36K: Benchmarking Coding and Reasoning Capabilities of Large Language Models on Graph Datasets (2025.findings-naacl)
Copied to clipboard
| Challenge: | Large language models (LLMs) have demonstrated significant capabilities in processing and understanding text data. |
| Approach: | They propose a structure-based instruction-based method to enhance LLM performance on complex graph tasks. |
| Outcome: | The proposed framework outperforms open-source models on graph problem-solving, but the gap is narrowing. |
Benchmarking and Improving Large Vision-Language Models for Fundamental Visual Graph Understanding and Reasoning (2025.acl-long)
Copied to clipboard
| Challenge: | Existing methods for enhancing understanding and reasoning abilities in graphbased tasks focus on specific graph types or tasks, posing challenges in designing versatile systems suitable for various tasks and graphs across diverse domains. |
| Approach: | They propose a structure-aware fine-tuning framework to enhance LVLMs with structure learning abilities through three self-supervised learning tasks. |
| Outcome: | Extensive evaluations on 14 LVLMs reveal that LVLs are weak in basic graph understanding and reasoning tasks, particularly those concerning relational or structurally complex information. |
Colorful Talks with Graphs: Human-Interpretable Graph Encodings for Large Language Models (2026.findings-acl)
Copied to clipboard
| Challenge: | Graph problems require reasoning over explicit structure, permutation invariance, and computationally complex relationships, creating a mismatch with the representations of text-based models. |
| Approach: | They propose a human-interpretable structural encoding strategy that injects graph structure directly into natural language prompts. |
| Outcome: | The proposed method improves performance on synthetic and real-world datasets. |
Demystifying the Power of Large Language Models in Graph Generation (2025.findings-naacl)
Copied to clipboard
Yu Wang, Ryan A. Rossi, Namyong Park, Nesreen K. Ahmed, Danai Koutra, Franck Dernoncourt, Tyler Derr
| Challenge: | Large Language Models (LLMs) have been used for graph discriminative tasks, but their potential for graph structure generation remains unexplored. |
| Approach: | They propose to use LLMs to generate graphs that optimize network properties by injecting domain expertise from network science into the code. |
| Outcome: | The proposed model generates graphs satisfying each property in different domains and compares it with established graph generative models across multiple domains. |
All Roads Lead to Rome: Graph-Based Confidence Estimation for Large Language Model Reasoning (2025.emnlp-main)
Copied to clipboard
| Challenge: | Existing methods for confidence estimation are primarily designed for factual QA tasks and fail to generalize to reasoning tasks. |
| Approach: | They propose a set of training-free, graph-based confidence estimation methods tailored to reasoning tasks that exploit graph properties such as centrality, path convergence, and path weighting. |
| Outcome: | The proposed methods improve confidence estimation and performance on two downstream tasks. |
MSG-LLM: A Multi-scale Interactive Framework for Graph-enhanced Large Language Models (2025.coling-main)
Copied to clipboard
| Challenge: | Existing graph-enhanced large language models (LLMs) focus on matching subgraphs between subgraph and candidate subgraph at the same scale, neglecting that subgraph with different scales may also share similar semantics or structures. |
| Approach: | They propose to use graph kernel search to discover subgraphs from the entire graph to bridge the graph and LLMs, helping with graph retrieval and LRM generation. |
| Outcome: | The proposed method achieves state-of-the-art on two graph-based tasks and the results are published in the journal Nature. |
CGBridge: Bridging Code Graphs and Large Language Models for Better Structure-Aware Code Understanding (2026.findings-acl)
Copied to clipboard
| Challenge: | Existing structure-aware approaches treat structure as serialized text prompts or auxiliary training objectives, failing to provide explicit guidance during inference. |
| Approach: | They propose a plug-and-play method that enhances Large Language Models with Code Graph information through an external, trainable Bridge module. |
| Outcome: | The proposed method decouples structural reasoning from textual generation without updating the backbone. |
Mapping the Minds of LLMs: A Graph-Based Analysis of Reasoning LLMs (2025.emnlp-main)
Copied to clipboard
| Challenge: | Large Reasoning Models (LRMs) often display unstable behaviors, e.g., hallucinating unsupported premises, overthinking simple tasks, and displaying higher sensitivity to prompt variations. |
| Approach: | They propose a graph-based analytical framework that clusters long, verbose CoT outputs into semantically coherent reasoning steps, then constructs directed reasoning graphs to capture contextual and logical dependencies among these steps. |
| Outcome: | The proposed framework enables quantitative evaluation of internal reasoning structure and quality beyond conventional metrics and provides practical insights for prompt engineering and cognitive analysis of LLMs. |