TLDR: A new research paper demonstrates that Large Language Models (LLMs) can learn to solve fundamental graph tasks and generalize to unseen graph structures and sizes without specialized graph encoders. By training even small LLMs with instructive chain-of-thought solutions, the study found that methods like LoRA fine-tuning significantly improve performance and generalization across various graph-related challenges and even aid in question-answering over knowledge graphs.
Large Language Models (LLMs) have shown remarkable abilities in understanding and generating human language, but their capacity to reason over complex data structures like graphs has been a persistent challenge. Graphs, which represent relationships between entities (like social networks or knowledge bases), are crucial for many real-world problems. Traditionally, improving LLM graph reasoning involved complex methods like serializing graphs into text or combining LLMs with specialized Graph Neural Networks (GNNs). However, a recent research paper titled “Less is More: Learning Graph Tasks with Just LLMs” explores a more direct approach.
Authored by Sola Shirai, Kavitha Srinivas, Julian Dolby, Michael Katz, Horst Samulowitz, and Shirin Sohrabi from IBM Research, this paper investigates whether LLMs can learn to solve fundamental graph tasks without the need for specialized graph encoding models. It also examines their ability to generalize these learned solutions to new, unseen graph structures or tasks, and evaluates the merits of different approaches to infuse graph knowledge into LLMs.
The Challenge of Graph Reasoning for LLMs
Pre-trained LLMs often struggle with graph reasoning. While serializing small graph neighborhoods into natural language can work, it typically breaks down for larger, more complex graphs. The paper highlights two main existing approaches: encoding graphs with specialized encoders and fusing embeddings into the LLM, or training LLMs with instruction tuning to reason over text-serialized graphs. Previous comparisons of these methods were limited, often using small graphs (20 or fewer nodes), leaving the generalizability unclear.
Exploring Four Methods
The researchers compared four distinct methods to enable LLMs to understand graphs, all while keeping the core LLM weights frozen:
- Graph Tokens: This method uses a graph transformer to encode the graph into a set of tokens, which are then integrated with the LLM.
- Graph Tokens + Text: Similar to Graph Tokens, but it also includes a textual representation of the graph, allowing the model to learn correspondences between the graph tokens and the text.
- LoRA (Low-Rank Adaptation): A fine-tuning technique that adapts the LLM’s weights to new tasks by training low-rank matrices inserted into its layers. Here, the LLM processes the graph solely as text.
- P-Tuning: A soft prompt technique where the LLM receives the graph as text, and a continuous prompt encoding is learned during training.
A small LLM model, Phi4-Mini-Instruct (4-billion parameters), was trained on four fundamental graph tasks: node count, node degree, and reachability using Breadth-First Search (BFS) or Depth-First Search (DFS). The training incorporated instructive chain-of-thought solutions, where the LLM was taught to output reasoning steps before the final answer.
Key Findings: Generalization and Performance
The study yielded several significant insights:
- Learning Graph Tasks: Even small LLMs can effectively learn to solve fundamental graph tasks. Most methods performed very well on in-distribution graph sizes.
- Generalization to Graph Size and Structure: LoRA, combined with multi-task training and instruction tuning, demonstrated strong generalization across different graph sizes and structures, including graphs twice as large as those seen during training. Other approaches, particularly Graph Tokens alone, showed greater performance degradation when applied to out-of-distribution (OOD) structures like cycle graphs.
- Generalization to New Tasks: While models initially struggled to solve entirely new tasks (like Edge Existence, Edge Count, Shortest Path, or Cycle Check) out-of-the-box, they showed rapid improvement with just 30 examples of additional training. Fine-tuned models consistently outperformed models trained from scratch on the same limited data.
- Applicability to Question Answering: The trained models showed promise in question-answering tasks like PrOntoQA, especially when the logical statements were parsed into a graph format similar to the training data. For Knowledge Graph Question Answering (KGQA) using LC-QuAD 2.0, generalization was more challenging due to the introduction of relation information (triplets) and the need for more complex semantic reasoning beyond simple pathfinding. However, fine-tuning still improved performance.
Tradeoffs and Limitations
Each method presented its own set of tradeoffs. Graph Tokens, while effective in reducing input token count for large graphs, were less robust in OOD generalization. P-Tuning proved capable of using prompt changes to solve graph tasks, often matching or exceeding Graph Tokens + Text. LoRA consistently showed the strongest performance and generalization, but it is more specialized to the specific LLM it’s trained on. Graph Tokens and P-Tuning offer greater portability across different LLMs, as their learned components can potentially be transferred or adapted more easily.
Also Read:
- Large Language Models Reshape Optimization Modeling
- Navigating the Nuances: How LLMs Grapple with Ambiguous Graph Database Queries
Conclusion
The research concludes that LLMs can indeed be trained to reason on graphs and exhibit good generalization capabilities without requiring specialized graph encoding models. This opens up exciting possibilities for LLMs to tackle more complex, open-ended graph tasks, potentially by treating graph reasoning as a tool that the LLM can leverage rather than always directly computing over the graph itself.
