# Graph Linearization Methods for Reasoning on Graphs with Large Language Models

arXiv: https://arxiv.org/abs/2410.19494 · HTML: https://mlsanity.com/paper/2410.19494/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 26 of its 59 references that are in the map.
- First posted on arXiv 25 Oct 2024.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 26 of 26)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [A Survey on Multimodal Large Language Models](https://mlsanity.com/paper/2306.13549/) (2023)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Language is All a Graph Needs](https://mlsanity.com/paper/2308.07134/) (2023)
- [GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking](https://mlsanity.com/paper/2305.15066/) (2023)
- [Talk like a Graph: Encoding Graphs for Large Language Models](https://mlsanity.com/paper/2310.04560/) (2023)
- [Predicting multicellular function through multi-layer tissue networks](https://mlsanity.com/paper/1707.04638/) (2017)
- [Let Your Graph Do the Talking: Encoding Structured Data for LLMs](https://mlsanity.com/paper/2402.05862/) (2024)
- [GraphText: Graph Reasoning in Text Space](https://mlsanity.com/paper/2310.01089/) (2023)
- [GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability](https://mlsanity.com/paper/2403.04483/) (2024)
- [LLM4DyG: Can Large Language Models Solve Spatial-Temporal Problems on Dynamic Graphs?](https://mlsanity.com/paper/2310.17110/) (2023)
- [Evaluating Large Language Models on Graphs: Performance Insights and Comparative Analysis](https://mlsanity.com/paper/2308.11224/) (2023)
- [Beyond Text: A Deep Dive into Large Language Models' Ability on Understanding Graph Data](https://mlsanity.com/paper/2310.04944/) (2023)
- [Which Modality should I use -- Text, Motif, or Image? : Understanding Graphs with Large Language Models](https://mlsanity.com/paper/2311.09862/) (2023)
- [Exploring the Potential of Large Language Models in Graph Generation](https://mlsanity.com/paper/2403.14358/) (2024)
- [GraCoRe: Benchmarking Graph Comprehension and Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2407.02936/) (2024)
- [GraphEval36K: Benchmarking Coding and Reasoning Capabilities of Large Language Models on Graph Datasets](https://mlsanity.com/paper/2406.16176/) (2024)
- [Graph Reasoning with Large Language Models via Pseudo-code Prompting](https://mlsanity.com/paper/2409.17906/) (2024)
- [Leveraging Discourse Structure for Extractive Meeting Summarization](https://mlsanity.com/paper/2405.11055/) (2024)

## Built on by (most cited first, 5 of 5)

- [Integrating Structural and Semantic Signals in Text-Attributed Graphs with BiGTex](https://mlsanity.com/paper/2504.12474/) (2025)
- [Detecting Hallucinations in Graph Retrieval-Augmented Generation via Attention Patterns and Semantic Alignment](https://mlsanity.com/paper/2512.09148/) (2025)
- [A document is worth a structured record: Principled inductive bias design for document recognition](https://mlsanity.com/paper/2507.08458/) (2025)
- [Is Implicit Knowledge Enough for LLMs? A RAG Approach for Tree-based Structures](https://mlsanity.com/paper/2510.10806/) (2025)
- [NAG: A Unified Native Architecture for Encoder-free Text-Graph Modeling in Language Models](https://mlsanity.com/paper/2601.22657/) (2026)

## Abstract (arXiv)

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.