# TinyGraphEstimator: Adapting Lightweight Language Models for Graph Structure Inference

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 36 references that are in the map.
- First posted on arXiv 9 Oct 2025.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Parameter-Efficient Transfer Learning for NLP](https://mlsanity.com/paper/1902.00751/) (2019)
- [Prefix-Tuning: Optimizing Continuous Prompts for Generation](https://mlsanity.com/paper/2101.00190/) (2021)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Phi-4 Technical Report](https://mlsanity.com/paper/2412.08905/) (2024)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Parameter-Efficient Fine-Tuning for Large Models: A Comprehensive Survey](https://mlsanity.com/paper/2403.14608/) (2024)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (2021)
- [GraphGPT: Graph Instruction Tuning for Large Language Models](https://mlsanity.com/paper/2310.13023/) (2023)
- [GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking](https://mlsanity.com/paper/2305.15066/) (2023)
- [Fine-tuning large language models for domain adaptation: Exploration of training strategies, scaling, model merging and synergistic capabilities](https://mlsanity.com/paper/2409.03444/) (2024)
- [GraphEdit: Large Language Models for Graph Structure Learning](https://mlsanity.com/paper/2402.15183/) (2024)
- [Can LLMs Effectively Leverage Graph Structural Information through Prompts, and Why?](https://mlsanity.com/paper/2309.16595/) (2023)
- [Reasoning of Large Language Models over Knowledge Graphs with Super-Relations](https://mlsanity.com/paper/2503.22166/) (2025)
- [Graph Generative Pre-trained Transformer](https://mlsanity.com/paper/2501.01073/) (2025)
- [Enhancing the Reasoning Capabilities of Small Language Models via Solution Guidance Fine-Tuning](https://mlsanity.com/paper/2412.09906/) (2024)
- [Can LLMs perform structured graph reasoning?](https://mlsanity.com/paper/2402.01805/) (2024)
- [Rethinking and Benchmarking Large Language Models for Graph Reasoning](https://mlsanity.com/paper/2509.24260/) (2025)
- [Applying Text Embedding Models for Efficient Analysis in Labeled Property Graphs](https://mlsanity.com/paper/2507.10772/) (2025)

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

- [Graph Property Inference in Small Language Models: Effects of Representation and Reasoning Strategy](https://mlsanity.com/paper/2603.06635/) (2026)
- [Generalization Boundaries of Fine-Tuned Small Language Models for Graph Structural Inference](https://mlsanity.com/paper/2604.18092/) (2026)
- [Closed-Loop Graph Algorithm Execution with Small Language Models: Step Accuracy and Rollout Reliability](https://mlsanity.com/paper/2606.24980/) (2026)

## Abstract (arXiv)

Graphs provide a universal framework for representing complex relational systems, and inferring their structural properties is a core challenge in graph analysis and reasoning. While large language models have recently demonstrated emerging abilities to perform symbolic and numerical reasoning, the potential of smaller, resource-efficient models in this context remains largely unexplored. This paper investigates whether compact transformer-based language models can infer graph-theoretic parameters directly from graph representations. To enable systematic evaluation, we introduce the TinyGraphEstimator dataset - a balanced collection of connected graphs generated from multiple random graph models and annotated with detailed structural metadata. We evaluate several small open models on their ability to predict key graph parameters such as density, clustering, and chromatic number. Furthermore, we apply lightweight fine-tuning using the Low-Rank Adaptation (LoRA) technique, achieving consistent improvements across all evaluated metrics. The results demonstrate that small language models possess non-trivial reasoning capacity over graph-structured data and can be effectively adapted for structural inference tasks through efficient parameter tuning.