  Graphs are a powerful tool for representing and analyzing complex
relationships in real-world applications such as social networks, recommender
systems, and computational finance. Reasoning on graphs is essential for
drawing inferences about the relationships between entities in a complex
system, and to identify hidden patterns and trends. Despite the remarkable
progress in automated reasoning with natural text, reasoning on graphs with
large language models (LLMs) remains an understudied problem. In this work, we
perform the first comprehensive study of encoding graph-structured data as text
for consumption by LLMs. We show that LLM performance on graph reasoning tasks
varies on three fundamental levels: (1) the graph encoding method, (2) the
nature of the graph task itself, and (3) interestingly, the very structure of
the graph considered. These novel results provide valuable insight on
strategies for encoding graphs as text. Using these insights we illustrate how
the correct choice of encoders can boost performance on graph reasoning tasks
inside LLMs by 4.8% to 61.8%, depending on the task.
