Wang, Yu; Rossi, Ryan A.; Park, Namyong; Ahmed, Nesreen K.; Koutra, Danai; Dernoncourt, Franck; & Derr, Tyler. (2025). Demystifying the power of large language models in graph structure generation. 2025 Annual Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Proceedings of the Conference Findings, NAACL 2025, 8189–8204. https://doi.org/10.18653/v1/2025.findings-naacl.456
Large Language Models (LLMs) have been very successful at analyzing graphs—such as predicting node classification (labeling items in a network) and link prediction (predicting missing connections). However, little research has explored whether LLMs can actually generate new graph structures. This study investigates that question.
We designed prompts that guide LLMs to write code that creates graphs with specific structural properties, using ideas from network science. Different types of networks—such as social networks or transportation networks—have different structural patterns. For example, the clustering coefficient measures how often triangles appear in social networks, while square patterns may reflect road layouts in transportation systems. We first tested whether LLMs could generate graphs that match these kinds of domain-specific structural properties.
Next, we selected the best-performing configurations and compared LLM-generated graphs with those produced by established graph generative models across multiple domains. Our results provide insight into how well LLMs can generate realistic network structures and where their strengths and limitations lie.
