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 . |
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. |
Generalizable LLM Learning of Graph Synthetic Data with Post-training Alignment (2026.findings-acl)
Copied to clipboard
| Challenge: | Existing research has focused on enhancing graph reasoning capabilities of LLMs by supervised fine-tuning on synthetic graph data. |
| Approach: | They propose to unlock generalizable learning of graph with post-training alignment with synthetic graph data by aligning off-the-shelf LLMs and LLM fine-tuned on synthetic graphs. |
| Outcome: | The proposed algorithm improves on synthetic graph problems and out-of-domain tasks with implicit graph structures. |
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. |
Can Large Language Models Tackle Graph Partitioning? (2025.emnlp-main)
Copied to clipboard
| Challenge: | Large language models (LLMs) have remarkable capabilities in understanding complex tasks, but they can only handle graph partitioning tasks that require global perception abilities. |
| Approach: | They propose a pipeline for coarsening, reasoning, and refining to enable LLMs to perform graph partitioning on small-scale graphs. |
| Outcome: | The proposed pipeline can handle graph partitioning tasks on small graphs with coarsening, reasoning, and refining. |
Reasoning with Graphs: Structuring Implicit Knowledge to Enhance LLMs Reasoning (2025.findings-acl)
Copied to clipboard
Haoyu Han, Yaochen Xie, Hui Liu, Xianfeng Tang, Sreyashi Nag, William Headden, Yang Li, Chen Luo, Shuiwang Ji, Qi He, Jiliang Tang
| Challenge: | Large language models (LLMs) have demonstrated remarkable success across a wide range of tasks, however, they still face challenges in reasoning tasks that require understanding and inferring relationships between distinct pieces of information within text sequences. |
| Approach: | They propose to construct explicit graphs from context and leverage them to enhance LLM reasoning performance on reasoning tasks. |
| Outcome: | Extensive experiments show that the proposed method improves both logical reasoning and multi-hop question answering 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. |
Are LLMs Truly Graph-Savvy? A Comprehensive Evaluation of Graph Generation (2025.acl-srw)
Copied to clipboard
| Challenge: | Large language models have demonstrated impressive capabilities across diverse tasks . however, their ability to generate valid graph structures remains underexplored . |
| Approach: | They evaluate large language models on five specialized graph generation tasks . they also test the models using 3 different prompt types: direct, iterative feedback, and program-augmented. |
| Outcome: | The proposed models solve twice as many tasks as general-purpose models, compared to their general-usage peers. |
The Mystery of Compositional Generalization in Graph-based Generative Commonsense Reasoning (2024.findings-emnlp)
Copied to clipboard
| Challenge: | Existing studies have found that LLMs are limited in scenarios that require generalization abilities, such as out-of-domain tasks. |
| Approach: | They propose a Compositional Generalization Challenge for Graph-based Commonsense Reasoning that requires models to generate a natural sentence based on given concepts and a reasoning graph. |
| Outcome: | The proposed framework is based on seven well-known LLMs and shows that they struggle in compositional generalization. |
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. |