Solving Graph Problems with Large Language Models

This thesis investigates how large language models (LLMs) can be used to solve classical computational problems on graphs. Graphs are a fundamental abstraction for representing real-world systems, such as social, transportation, and communication networks, but they pose unique challenges: their structure is not tied to any fixed ordering of nodes (graph isomorphism), and different tasks (such as reachability, shortest paths, flows, or substructure counting) require very different reasoning patterns. With the advent of large language models, there is growing interest in replacing or complementing traditional graph neural networks with text-based models. Recent work shows that LLMs can exhibit human-like behaviors in specific settings, which raises a key question: can we design graph representations that better align with how humans (and thus LLMs) naturally interpret structure? The first contribution of this thesis is the proposal of new techniques for augmenting node-level information with structural signals derived from the graph itself. These methods are orthogonal to the specific graph characteristics, thus are applicable to any graph dataset. The second contribution is the design of a systematic evaluation framework. I construct a synthetic benchmark covering multiple graph families and a diverse set of tasks, including computationally challenging ones, and develop an end-to-end pipeline to generate datasets, construct prompts, query LLMs, and analyze responses. The proposed representations are assessed through theoretical analysis and extensive experiments, giving additional insights on whether human-interpretable structural augmentation can improve LLM performance on non-trivial graph problems.