TinyGraphEstimator: Adapting Lightweight Language Models for Graph Structure Inference
This work addresses the challenge of resource-efficient graph structure inference for applications in graph analysis and reasoning, though it is incremental in exploring smaller models for an existing task.
The paper tackled the problem of using compact transformer-based language models to infer graph-theoretic parameters from graph representations, and the result showed that lightweight fine-tuning with LoRA achieved consistent improvements across metrics like density, clustering, and chromatic number.
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.