Colorful Talks with Graphs: Human-Interpretable Graph Encodings for Large Language Models
This addresses the problem of LLMs struggling with graph reasoning for researchers and practitioners in AI, though it is incremental as it builds on existing encoding methods.
The paper tackled the challenge of applying large language models (LLMs) to graph problems by introducing a human-interpretable structural encoding strategy that maps graph structures to color tokens, resulting in considerable improvements on algorithmic and predictive graph tasks across synthetic and real-world datasets.
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.