Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks (2026.acl-long)
Copied to clipboard
| Challenge: | Large Language Models (LLMs) have improved reasoning abilities but are limited due to limited context length. |
| Approach: | They propose a large graph benchmark dataset and propose four tasks to evaluate LLMs' reasoning abilities. |
| Outcome: | The proposed tasks evaluate the reasoning abilities of LLMs on a large graph benchmark dataset. |
Similar Papers
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. |
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. |
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. |
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. |
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. |
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. |
Towards Reasoning in Large Language Models: A Survey (2023.findings-acl)
Copied to clipboard
| Challenge: | Reasoning is a fundamental aspect of human intelligence that plays a crucial role in many intellectual activities. |
| Approach: | They propose to improve LLMs' ability to elicit reasoning by providing exemplars or prompts to model reasoning. |
| Outcome: | This paper provides a comprehensive overview of the state of knowledge on reasoning in large language models. |
Can LLM Graph Reasoning Generalize beyond Pattern Memorization? (2024.findings-emnlp)
Copied to clipboard
| Challenge: | Existing studies seek to enhance the graph reasoning capabilities of Large Language Models (LLMs) by specialized instruction tuning. |
| Approach: | They propose to evaluate LLM graph reasoning generalization using in-distribution settings . they propose to use three strategies to improve LLM generalization . |
| Outcome: | The proposed benchmark evaluates LLM graph reasoning generalization with in-distribution settings only . it shows that LLMs struggle to generalize across reasoning and real-world patterns . |
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. |