Abstract:Graph problems are fundamentally challenging for large language models (LLMs). While LLMs excel at processing unstructured text, graph tasks require reasoning over explicit structure, permutation invariance, and computationally complex relationships, creating a mismatch with the representations of text-based models. Our work investigates how LLMs can be effectively applied to graph problems despite these barriers. We introduce a human-interpretable structural encoding strategy for graph-to-text translation that injects graph structure directly into natural language prompts. Our method involves computing a variant of Weisfeiler-Lehman (WL) similarity classes and maps them to human-like color tokens rather than numeric labels. The key insight is that semantically meaningful and human-interpretable cues may be more effectively processed by LLMs than opaque symbolic encoding. Experimental results on multiple algorithmic and predictive graph tasks show the considerable improvements by our method on both synthetic and real-world datasets. By capturing both local and global-range dependencies, our method enhances LLM performance especially on graph tasks that require reasoning over global graph structure.
| Comments: | Accepted to ACL Findings 2026 22 pages, 18 tables, 5 figures |
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2602.10386 [cs.LG] |
| (or arXiv:2602.10386v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2602.10386 arXiv-issued DOI via DataCite |
From: Angelo Zangari [view email]
[v1]
Wed, 11 Feb 2026 00:15:29 UTC (218 KB)
[v2]
Wed, 22 Apr 2026 16:40:29 UTC (221 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。