Graph Linearization Methods for Reasoning on Graphs with Large Language Models
This work addresses the challenge of integrating graph machine learning with multimodal LLMs, offering a novel approach for graph reasoning tasks.
The paper tackles the problem of enabling large language models to reason on graphs by developing graph linearization methods that transform graphs into token sequences reflecting natural language properties like local dependency and global alignment. The results show these methods outperform random linearization baselines, demonstrating effectiveness in making graphs understandable to LLMs.
Large language models have evolved to process multiple modalities beyond text, such as images and audio, which motivates us to explore how to effectively leverage them for graph reasoning tasks. The key question, therefore, is how to transform graphs into linear sequences of tokens, a process we term "graph linearization", so that LLMs can handle graphs naturally. We consider that graphs should be linearized meaningfully to reflect certain properties of natural language text, such as local dependency and global alignment, in order to ease contemporary LLMs, trained on trillions of textual tokens, better understand graphs. To achieve this, we developed several graph linearization methods based on graph centrality and degeneracy. These methods are further enhanced using node relabeling techniques. The experimental results demonstrate the effectiveness of our methods compared to the random linearization baseline. Our work introduces novel graph representations suitable for LLMs, contributing to the potential integration of graph machine learning with the trend of multimodal processing using a unified transformer model.