# GraphSOS: Graph Sampling and Order Selection to Help LLMs Understand Graphs Better

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 49 references that are in the map.
- First posted on arXiv 24 Jan 2025.

## Builds on (most cited first, 30 of 36)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivity](https://mlsanity.com/paper/2104.08786/) (2021)
- [How Can We Know What Language Models Know?](https://mlsanity.com/paper/1911.12543/) (2019)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs](https://mlsanity.com/paper/2307.03393/) (2023)
- [GraphGPT: Graph Instruction Tuning for Large Language Models](https://mlsanity.com/paper/2310.13023/) (2023)
- [G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering](https://mlsanity.com/paper/2402.07630/) (2024)
- [GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking](https://mlsanity.com/paper/2305.15066/) (2023)
- [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](https://mlsanity.com/paper/2306.08385/) (2023)
- [Talk like a Graph: Encoding Graphs for Large Language Models](https://mlsanity.com/paper/2310.04560/) (2023)
- [Variational Reasoning for Question Answering with Knowledge Graph](https://mlsanity.com/paper/1709.04071/) (2017)
- [Graph-less Neural Networks: Teaching Old MLPs New Tricks via Distillation](https://mlsanity.com/paper/2110.08727/) (2021)
- [ChartX & ChartVLM: A Versatile Benchmark and Foundation Model for Complicated Chart Reasoning](https://mlsanity.com/paper/2402.12185/) (2024)
- [Make Your LLM Fully Utilize the Context](https://mlsanity.com/paper/2404.16811/) (2024)

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

- [Lost in Serialization: Invariance and Generalization of LLM Graph Reasoners](https://mlsanity.com/paper/2511.10234/) (2025)
- [Towards Order Fairness: Mitigating LLMs Order Sensitivity through Dual Group Advantage Optimization](https://mlsanity.com/paper/2605.11974/) (2026)
- [FOCUS: Decoupling Expert Personas in LLMs to Enhance Domain Expert Capabilities](https://mlsanity.com/paper/2608.05611/) (2026)
- [GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs](https://mlsanity.com/paper/2609.12265/) (2026)

## Abstract (arXiv)

The success of Large Language Models (LLMs) in various domains has led researchers to apply them to graph-related problems by converting graph data into natural language text. However, unlike graph data, natural language inherently has sequential order. We observe a counter-intuitive fact that when the order of nodes or edges in the natural language description of a graph is shuffled, despite describing the same graph, model performance fluctuates between high performance and random guessing. Additionally, due to LLMs' limited input context length, current methods typically randomly sample neighbors of target nodes as representatives of their neighborhood, which may not always be effective for accurate reasoning. To address these gaps, we introduce GraphSOS (Graph Sampling and Order Selection). This novel model framework features an Order Selector Module to ensure proper serialization order of the graph and a Subgraph Sampling Module to sample subgraphs with better structure for better reasoning. Furthermore, we propose Graph CoT obtained through distillation, and enhance LLM's reasoning and zero-shot learning capabilities for graph tasks through instruction tuning. Experiments on multiple datasets for node classification and graph question-answering demonstrate that GraphSOS improves LLMs' performance and generalization ability on graph tasks.