Talk like a Graph: Encoding Graphs for Large Language Models
Authors: Bahare Fatemi
Jonathan Halcrow
Bryan Perozzi
Venue: ICLR 2024 poster (2024)
Keywords: Graph problems
large language models
encoding graphs
generative models
Primary area: generative models

Abstract: 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.

Published as a conference paper at ICLR 2024
TALK LIKE A GRAPH: ENCODING GRAPHS FOR LARGE LANGUAGE MODELS
Bahare Fatemi, Jonathan Halerow, Bryan Perozzi Google Research
(baharef, ha crow, bperozzi (egooiiiegggoogeeooooooooo
ABSTRACT
Graphs are a powerful tool for representing and analyzing complex relationships in real-world applications such social networks, recommender systems, and com- putational finance. Reasoning on graphs is essential for drawing inferences about the relationships between entities complex system, and identify hidden pat- terns and trends. Despite the remarkable progress in automated reasoning with natural text, reasoning on graphs with large language models (LL.Ms) 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) in- terestingly, 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.
INTRODUCTION
There has been remarkable recent progress in the research and applications of large language mod- els (LLMs) (Vaswani et al.) 2017 Devlin et al.] 2018: Brown et al., 2020aa] Ouyang et al. (022).
These generative models have captivated the artificial intelligence community and a plethora of models trained on variety of tasks and modalities have recently been released (Zhao et al., 2023).
All of these advancements have led a growing consensus that L.LMs are pivotal advancement on the path to artificial general intelligence (AGI) (Bubeck et al.) 2023).
However, despite all their successes, there are number of limitations with the current methodology of design and implementation of LLMs. One of the most obvious limitations is their reliance on unstructured text, causing the models to sometimes miss obvious logical entailments or hallucinate incorrect conclusions (Zhang et al.] (023b). Another is that LLMs are fundamentally limited by when they were trained, and it can be difficult to incorporate 'fresh" information about the state of the world which has changed (Lewis et al. 2020). Graph--ttructured data is one of the most flexible ways to represent information and could be promising solution to both challenges (Schneider et al. 2022] Pan et al. 2023). Graphs can provide LLMs with a more explicit representation of relationships and entities, enabling them to reason more effectively and avoid hallucinations. Graphs can be updated and expanded, allowing LLMs to incorporate new information as it becomes available.
Interestingly, despite this promise, the intersection of graphs and LLMs has been relatively under- studied. For example, while much work has focused on LLMs and graph databases (or knowledge graphs (Guu et al. 2020; Lewis et al. 2020)) there has not been much study about general purpose use of graph- signing graph benchmarking task for language models. While their task represents
data. More recently, Wang al. (202)) have sought to address this by de- exciting initial foray into measuring LLMs graph reasoning capabilities, there are still many open questions due to the omission of several natural graph tasks and lack of variety in the type of graph structure considered. Other recent work seeks to replace graph-structure, data with LLMs (Ye et al. 2023). but this does not address fundamental challenges with LLMs.
In this work, we perform the first comprchensive study about reasoning over graph-structured data text for consumption by LLMs. To analyze graph reasoning more closely, we decompose the

---

Published as a conference paper at ICLR 2024
Graph G
Graph enceder g
Prompt
describes graph among nodes
5,6.
grapie
Node connected to nodes 2 and Node connected nodes 2 and 6.
LLM:
Answer: A
Prompt question:
Graph task
Question: What ls the degree node 47
Figure 1: Overview of our framework for reasoning with graphs using LLMs.
problem into graph encoding and graph prompt engineering. Varying graph encoding methods allows us to understand how LLM's learned representations are leveraged in graph tasks. While studying prompt engineering techniques finds the most suitable way to get a desired solution to question from LLM. Our experimental results seek to uncover the situations where different prompt heuristics work well. To that end, we propose a new set benchmarks GraphQA for measuring LLM performance reasoning over graph data. GraphOA is distinguished by using graphs with much more varied and realistic graph structure than has previously been studied with LLM
Our Contributions: Specifically, the contributions of our work the following:
1. An extensive study of graph-structure prompting techniques for use in LLMs.
2. Insights and best practices for encoding graphs as text for use in LLMs.
3. A new graph benchmark (CraphoA) to aid the community in studying the effects of graph structure on LLM prompting further.
PROMPTING LLMS FOR GRAPH REASONING
Notation. Let f be the interface function generative AI model, which takes high-dimensiioal discrete input tokens W and produces output in the same token space (f W + W). Without loss of generality, we will colloquially refer f pre-trained Large Language Model (LLM) throughout this work, but note that our discussion here applies to any generative Al model with such discrete interface. In this work, consider encoding graphs G (V, E), where V is the set of vertices (or nodes) and E' E (V x V) is the set of edges connecting them.
2.1 PROMPT ENGINEERING
The goal in prompt engineering find the correct way phrase question Q such that an LLM (or other generative model) will return the corresponding answer A, (Q E W, E W). In other words, A f(Q). this work, our goal is to provide the LLM with graph information so that it can better reason about question/answer pairs that require access to arbitrarily structured relational information: A f(G. Q).
A variety of approaches exist for modifying the LLM f(-) so that it could perform better tasks with graph data such as fine-tuning (Clark al. 2020), soft prompting (Lester et al. (02T), and LoRA (Hu al. 2021). In addition, many approaches modify the model include graph informa- tion Muüller et al.) 2023; Zhang et al.) 2020 Dwivedi Bresson, 2020). However, these methods require access to the internals of the model (its weights gradients), which can limit their appli- cability many settings. In this work, we are instead interested the case where f() and its parameters fixed, and the system is available only for use in a black box setup where the LLM only consumes and produces text (i.e., the LLM f W + W). We believe this setting to be partic- ularly valuable the number of proprietary models available and their hardware demands increase.
To this end, we introduce the graph encoding function g(G) and question rephrasing function ((Q), where g G + W and q W + W (where W is the large discrete domain of tokens used train the LLM) as A GG) Q). Our training input D to the graph-based prompt system is set of G, Q, triples, where G is a graph, Q question asked the LLM,, and
solution to Q, (S E W). We seek to find g() and Q that maximize the expected score from the model (score,) of the answers over the training dataset D.
max EG.Q.SDD (core)()(G), 9-9
'The code generate the data is available
2

---

Published as a conference paper at ICLR 2024
As W is very large discrete space, many current approaches use heuristies for this optimization (by changing the prompt Q). The novel contribution of this work is to consider the role of the graph en- coding function g(.), question rephrasing function q(),, and the graph structure G' in the optimization of Equation
2.2 PROMPTING HEURISTICS
The vast majority of prompting heuristics operate by optimizing the prompt text Q used to query the model. We briefly introduce the methods examine further in the paper here:
Zero-shot prompting (ZERO-SHOT): This approach simply provides the model with a task descrip- tion and asks it to generate the desired output, without any prior training on the task. Few-shot in-context learning (FEW-SHOT) (Brown et al. (020bb: This approach provides the model with a small number of examples of the task, along with the desired outputs. The model then learns from (CoT) prompting (COT) (Wei al. 2022): This approach provides the model with a sequence examples, each of which shows how to solve the task step-by-step. The model then learns to generate its Co'Ss to solve new prob- lems. Zero-shot CoT prompting (ZERO-COT) (Kojima CoT prompting, but it does not require any prior training examples. Instead, the model uses a sim- ple prompt to generate its own CoT' As suggested by the original paper, we used "Let's think step by step". Bag prompting (COT-BL BAG) (Wang al. 2023): This technique is proposed improve the performance of LLMs on graph-related tasks. It works by appending "Let's 's construct a graph with the nodes and edges first" to the graph description.
these examples to perform the task on new inputs. Chain-of-thougee
al. 2022): This approach similar to
We note that there also popular recent extension of this family of methods, based on iterative prompting. These methods
series of iterative LLM queries optimize the prompt ques- tion (e.g., (Zhou et al. 2022b; Pryzant et al., [203]] Yang et al. 2023)). However, our initial ex- periments showed that iterative prompting methods performed much worse for our tasks, due to cascading errors. Consequently, we chose to concentrate our efforts on the methods outlined above. In this study, the goal to optimize the graph encoding function on basic graph tasks. Such basic tasks are essential intermediate steps for more complex reasoning tasks on graphs. We conduct ex- tensive experiments on graph encoding function, question, and graph generator functions, providing a study of graph encoding methods for black-box LLM usage.
3 TALK LIKE A GRAPH: ENCODING GRAPHS VIA TEXT
Graph encoding is a necessary step for turning graph-structured information into a sequence for consumption by language models. In this section, we will study the details of graph encoding function 9(.) which maps graph data into tokens for consumption by an LLM. Our experimental results in this section seek to understand the best form of graph encoding and prompt engineering to maximize the performance graph reasoning tasks.
We begin by highlighting some of the most exciting results from our analysis here:
R1: LLMs perform poorly on basic graph tasks ($3.
R2: The graph encoding function has a significant impact on LLM graph reasoning ($3.1
R3: Incident graph encoding outperforms the rest in most of the setups (:3.T)
R4: Model capacity has a significant effect on graph reasoning capabilities of LLMs (3.4))
Graph encoding function. This section is an investigation into various methodologies for rep- resenting graphs as text. This process of encoding graphs as text can be separated into two key inquiries: First, the encoding of nodes in the graph, and second the encoding of edges between the nodes. Regarding the encoding of nodes and edges, we examine several techniques. Figure 2 shows an overview of the graph encoding functions used. For brevity's 's sake, full description and examples of the graph encoding functions considered are explained in Appendix A
Graph structure. We briefly note that the design of this experiment follows that of Wang et al. (2023), who use vedōss-Réní: (ER) graphs (Erdös & Rényi 1959). One contribution our work is to consider the effect of more complex graph structures reasoning in LLMs (covered in Section 4
3

---

Published as a conference paper at ICLR 2024
Pxpprt) Yes andyet hown tean pier agein sanog R. E. F-O. Air Aard, o C.... Hi
Adpcency: hue wead graat merra End roce! cornectd
Padticarc calcitee soohi neoerr preh smong dioeaat ken We trin hicaaing acgas Flrnbwr Jonn
Jeeny
descise soran anaing 2 4.5. soda
conpecte
Socad aatoork desct socal relleris goott Fra the and We hewe sitw no sdyen Lanc see comedded
7.7 und & tis grart hode by cor correddd rodex
Graph G
rodes 6 3 4.5 Te.. Node la connectad to noces 2.7.
Frendetie ceanthes ha grash among
John, Davi,
and
Darnays, Jon Bise Sanos Avys dansel and Jains
We have the buing scies Robat Lanvoee and Herds
bonnayy beers Car and Coanneys zas mode
dopcrt inecclty pash usang Eas Herey Myl Shirs tellss has Iude Lara, Shave, himbeli
iknea Hobet Jois, Wiched Usvil Many Pharcia lbocat vnaa paper bogillee samilil and Linds veote
bik Teld Bape maans Babee and fericc, Lare and Stannore Foolds
Figure 2: Overview of our framework for encoding graphs via text.
3.1
EXPERIMENT 1: VARYING GRAPH ENCODING FUNCTION
In this experiment, we measure the performance of pre-trained LLMs on graph tasks: edge existence, node degree, node count, edge count, connected nodes, and cycle check. We describe these tasks and our graph benehmark that contains them (GraphOA) in detail in Appendix (A.2
3.1.1 RESULTS
Table shows the results of this experiment varying graph encoding and prompting techniques. These results show several interesting conclusions, which we briefly summarize here:
LLMs perform poorly on basic graph tasks. Let's start by examining the overall results. LLMs performed poorly on almost all the basic graph tasks we experimented with. This is especially interesting for edge existence and cycle check, where there is not an edge 53.96% of the time for edge existence and there is a cycle 81.96% of the time for cycle check. Therefore. LLMs perform worse than the majority baseline. Note that we experimented with ER graphs in this experiment, and it is very likely for an ER graph to have cycle.
Simple prompts are best for simple tasks. We see that ZERO-COT prompting has worse model performance than ZERO-SHOT prompting on basic graph tasks. This is likely because ZERO-SHOT prompting is sufficient for these tasks, which do not require multi-hop reasoning. ZERO-COT prompting can be effective for tasks that require multi-hop reasoning, such as arithmetic problems, but not necessary for most basic graph tasks, which only require the LLM to have an under- standing of the graph structure (nodes, edges, paths, etc.) and the graph task. However for more complex tasks, adding few-shot examples and CoT prompting generally improved the performance of the model. This is mainly because few-shot examples provide the LLM with better understand- ing of the task it is solving. CoT prompting can also improve performance by helping the LLM to find out how to get to the answer to the problem.
Graph encoding function has significant impact on LLM reasoning. As the results indicate, the choice of the graph encoding function has significant impact on the performance of LLMs on graph-related tasks. This is because different encoding functions capture different aspects of the graph structure. For instance, for finding connected nodes node in a graph, adjacency achieves 19.8% accuracy and incident achieves 53.8% accuracy. For both node degree and connected nodes, incident encoding outperforms the rest of the encoding functions. This is likely because the incident encoding encodes the graph structure in a way that makes the relevant information more accessible, i.e., in close proximity, to the LLM.
Integer node encoding improves arithmetic performance. Another finding here is that integer encoding of nodes (e.g., node 0) can improve the performance of LLMMs on integer output tasks, such predicting node degree, node count, and edge count. This is because the input and output of the LLM are then in the same space, making it casier for the model to learn the relationship between the two. Interestingly however, encoder functions with specific names (e.g., David) worked better in non-integer output tasks such as GOT for edge existence or F Friendship for cycle check.
Aggregated results. To provide recommendations about the best encoding function for each prompt, we rank the encoders by their average standing (in rank order) on each graph task. For most prompt- ing methods, incident encoding performed the best. However, for ZERO-SHOT graph prompting,
4

---

Published as conference paper at ICLR 2024
Table 1: Comparison of various graph encoding functions based their accuracy different graph tasks using PaLM 62B. The most effective prompting heuristic is highlighted with an underline, and the top-performing graph encoding function for it is highlighted in bold. The overall result is represented its average ((4) and an absolute difference (d) of its best and worst graph encoding.
Method
Encoding
Edge existence
Node degree
Node count Edge count
Connected nodes
Cycle check
Overall (p/66
44.5/9.4
14.0/I6.0
8.6
12.4/4.8
14.7/1110
76.0 13.2
Adjacenec
45.8
12.4
18.8
14.0
19.8
71.6
ZERO SHOT
Incident
39.6
25.0
15.6
Co-authorship
13.8
22.0
11.4
70.8
Friendship
46.6
11.2
23.0
10.2
82.0
SP
46.4
9.0
22.4
15.0
6.2
80.4
GOT
49.0
13.6
22.8
13.2
7.6
79.0
Social network
43.2
16.0
22.8
10.8
8.2
81.2
Politician
44.6
15.2
24.2
11.6
8.8
81.0
Expert
41.2
10.0
24.0
14.8
16.4
69.6
Overall (2//8)
31.6/
10.4/22.
14.679.4
9,4/4.8
8.8 9.2
3 23.2
Adjacency
34.2
15.4
11.0
12.2
46.2
ZERO- cor
Incident
41.4
26.6
10.0
12.2
35.2
39.0
Co-authorship
29.8
9.8
15.6
8.2
28.2
Friendship
28.4
7.0
19.4
7.4
3.0
31.2
SP
32.6
9.2
15.6
8.4
5.0
34.8
GOT
34.6
8.4
16.2
8.4
5,4
33.4
Social network
30.8
6.6
14.0
9.2
388
26.0
Politician
38.0
4.2
14.6
8.6
3.2
23.0
Expert
6.0
14.8
28.8
Overall (p//8)
36.8/13.8
17.4/2344
25.6/35.6
12.079.0
12.4/15.2
37.4/
Adjacency
42.8
15.4
47.2
18.6
22.2
47.8
FEW SHWT
Incident
38.8
33.6
51.2
14.6
36.6
45.0
Co-authorship
29.4
15.6
15.6
10.2
9.0
46.8
Friendship
40.6
12.2
18.4
9.8
6.4
41.4
SP
34.6
18.0
18.0
12.0
6.8
38.2
GOT
40.6
17.2
14.2
12.0
28.6
Social network
37.4
15.0
21.2
10.2
34.2
Politician
13.4
21.4
30,8
Expert
29.0
16.6
20.4
23.8
Overall (u/8)
42.877.0
29.2/60. 60.4
27.6/42.4
12.8/17.8
13.1 18800
58.0/ 16.4
Adjacency
42.8
71.2
57.0
25.2
22.4
56.6
Incident
41.6
75.0
57.6
21.4
30.2
62.6
COT
Co-authorship
43.2
16.4
15.2
8.8
8.4
54.8
Friendship
46.6
14.6
23.0
7.8
9.6
61.8
42.6
17.4
17.0
10.6
59.4
GOT
44.0
17.8
16.2
11.8
60.4
Social network
42.6
16.4
21.6
Politician
42.2
16.6
22.6
9.2
59.4
Expert
39.6
17.4
18.0
12.4
14.4
46.2
Overall (u/8)
37.3/16.6
28.0/61.8
26.9/ 33.8
12.5 17.8
15.8 /318
/2.1/26.0
Adjacency
45.8
66.8
48.6
25.0
20.6
56.8
COT-BAS BAG
Incident
45.6
75.2
51.2
21.8
41.0
63.0
Co-authorship
25.0
14.6
17.4
7.2
9.2
37.0
Friendship
39.0
16.2
21.8
7.4
9.8
$2.0
17.0
21.6
11.4
GOT
32.6
15.6
18.0
$4.6
Social network
44.8
13.4
19.6
9.0
10.0
51.2
Politician
40.4
17.6
22.8
8.2
10.2
$7.2
Expert
29.2
15.8
20.8
11.6
20.4
45.0
node tokens with more established representations (such as politicians) outperformed incident. The results are deferred to T the appendix.
Choosing the right graph encoding function significantly affects the performance of LLMs graph algorithms. Therefore, it important select function carefully and appropriately for the specific task. This finding is especially important because many reasoning tasks involve graph problems. For example, finding influential nodes in a social network similar to finding the degree of the nodes in the graph. Encoding such graphs in the right way for the task can improve the task.
Summary:
3.2 EXPERIMENT 2: VARYING PROMPT QUESTIONS
The motivation for this experiment is to measure the effect of the question encoder in the prompt on different graph tasks. In this experiment, maintained the graph encoding function constant

---

Published as a conference paper at ICLR 2024
Table 2: Comparing two question encoders based their accuracy for PaLM 2 XXS and PaLM 62B. The top- perffforrmin question encoder for the respective LLM is highlighted bold.
Method
Question encoder
LLM
Edge Existence
Node degree
Node count
Edge count
Connected nodes
Graph
PaLM 2-XXS
42,8
10.8
5.4
5.6
Application
PaLM 2-XXS
60.8
14,0
9.4
4,4
11.4
ZERO-SHOT
Graph
PaLM 62B
46.6
11.2
23.0
10.2
4.0
Application
16.6
Graph
M2 XXS
50.4
8.8
8.4
4.2
10.2
Application
P2LM2 XXS
56.4
12.2
8.6
5.4
11.0
Graph
PaLM 62B
46.6
14.6
7.8
9.6
Application
PaLM 62B
38.6
16.6
16.0
12.2
10.0
Same relation
Multiple relations
Edge Existance
Node Degree
Node
Task
100
Edge Existence
42.8
39.8
Accuracy
ZERO-SHOP
Node degree
10.8
11.6
50
Node count
6.6
25
Edge count
5,4
Connected nodes
1.6
3.4
Cycle Check
65.2
84.4
Edge Count
Connected Nodes
Cycle Check
Edge Existence 50.4
50.8
75
Node degree
8.8
10.0
Accuracy
Node count
8.4
5.8
50
Edge count
4.2
5.0
Connected nodes
10.2
7.2
Cycle Check
77.4
74.4
Size
PaLM
Few-shot
Zero-COT
COT
Baseline
Table Results on multiple relations for edge encoding with PaLM 2 XXS.
Figure Effect Model Capacity on graph rea- soning task for PaLM 2-XXS, XS, S, and L.
for the concept of friendship and conducted experiments using two distinct question encoder func- tions: the graph question encoder and the application question encoder. The graph question encoder is responsible for encoding graph-related tasks, such determining the degree of specific node (e.g.. "What the degree node i?"). This encoder is used for obtaining results Section 3.1 On the other hand, the application question encoder interprets graph questions in cal, day-to-day context. the application scenario, we used a friendship-bard scenario where we transformed the questions for each graph task as stated in Table
practi-
Table 2 summarizes the results our experiment on question encoder functions. As the results show, the application encoder outperforms the graph encoder almost all tasks, despite both encoders having the same graph encoder function and only differing slightly in how they ask the question. For example, on the ZERO-SHIOT edge existence using PALM 2 XXS, the graph encoder obtained 42.8% accuracy, while the application encoder obtained 60.8%.
Results:
The selection of the question encoder function affects the performance of LLMs when handling basic graph algorithms. As result, it becomes important to translate given task into more contextually meaningful textual information when employing LLMs for inference.
Summary:
3.3 EXPERIMENT MULTIPLEE RELATION ENCODING
In this experiment setup. we introduce modification to the friendship graph encoding function, which characterizes edges based on range of distinct relation types, including friends, colleagues, spouses, siblings, neighbors, acquaintances, teammates, classmates, coworkers, or roommates. The selection of the relation type randomized from this predefined set, thereby using multiple words to reference the existence relationship between nodes. This is departure from using the same token(s) for edge representation in prior graph encoding experiments.
Results: As Table shows, using multiple words to represent relationships did not hurt LLM per- formance and improved it in some cases. This improvement is likely because the diverse set of relations provides the LLM with more textual information to perform the task, and the final encoding closer to the text that the LLM may have seen during training, compared to the prior setup.

---

Published as a conference paper at ICLR 2024
ER
SBM
9FN
Path
Star
Complete
Figure 4: Samples of graphs generated with different graph generators from Graph@A.
3.4 EXPERIMENT 4: MODEL CAPACITY AND GRAPH REASONING ABILITY
In this experiment, measure the effect of model capacity the graph tasks. We compare the results of PaLM (Anil et al. 2023) XXS, XS, S, and L,, which have different number of parameters and therefore different capacity. We report the majority baseline for reference.
Results: Model capacity has a significant effect on the graph reasoning ability of an LLM. The results of this experiment, reported in Figure show the larger model generally better at graph reasoning tasks. This is because it has more capacity to learn and store complex information. The model capacity has less effect on edge existence. The results also show that the model was not able to beat the majority baseline for edge existence even with large capacity.
3.5 EXPERIMENT 5: REASONING IN THE ABSENCE OF EDGES
In this experiment, evaluate the performance of LLMs disconnected nodes. In this task, provide a graph description to the LLM, specifying the nodes and edges, and ask about the nodes that are not directly connected to given node. This task differs from the previous ones in that requires reasoning about information that is implicit in the graph, i.e., information that is not explicitly mentioned in the output of the graph encoding function.
Results: LLMs lack a global model of a graph. The ZERO-SHOT prompting method achieved an accuracy of 0.5%, while the ZERO-COT, FEW-SHOT, COT, and COT-RAG methods achieved close 0.0% accuracy. These results suggest that L.Mss perform significantly worse on the disconnected nodes task than on the connected nodes task. We believe that this is because the graph encoding functions primarily encode information about connected nodes, while not explicitly encoding infor- mation about nodes that are not connected. As a result, LLMs are better at processing relationships among connected nodes than at capturing the absence of connections, leading to sub-optimal per- formance disconnectivity related tasks.
4 DOES THE STRUCTURE OF THE GRAPH MATTER FOR THE LLM?
It is natural to wonder if the structure of the graph itself might effect LLM''s ability to reason over it. Inspired by recent work analyzing graph neural networks (Palowitch et af., [0222] Yasir al.] 2023) this section seeks to measure LLM's reasoning capabilities over graph with distinct struc- tures. this section, we show that graph structure can have significance influence on an LLM's reasoning performance. Figure 4 illustrates graphs created through different generative processes.
4.1 RANDOM GRAPH GENERATION
To be able experiment with LLMs on graphs, we generate random graphs using various graph gen- erator algorithms. This allows us to: Cover a wide range of properties. Different graph generators produce graphs with different properties. For example, Erdös-Rényl Rényi graphs tend be sparse and have a small average degree. while Barabási-Alber graphs tend to be dense and have a power-law degree distribution. By using a diverse set of generators, we ensure that the Graph@A benchmark includes graphs with wide range of properties. Avoid bias in graph problem evaluation. The goal of generating such graphs is to test the ability of LLMS to solve graph problems. Graph prob- lems can vary in difficulty depending graphs to avoid bias. Provide realistic benchmarks. Real-world graphs exhibit a wide range of properties, and single graph generator capture all of these properties perfectly. By using diverse set of generators, we create a benchmark that is more representative of real-world graphs. To generate random graphs, Frdös-Rényi (ER) graphs (Erdös & Rényi 1959), scale-free net-
the properties of the graphs, we use diverse set of

---

Published as conference paper at ICLR 2024
Table 4: Comparing graph generators with PaLM 62B. Underline and bold represent the most effee- tive prompting heuristic and the top performing graph generator respectively.
Method Graph generator
Edge Existence
Node degree
Node count
Edge count
Connected nodes
Cycle check
Overall
49.1
17.6
23.0
12.1
23.3
75.2
22.1
11.7
14.9
76.3
ZERO SIIS
50.2
18.0
24,9
13.6
20.1
72.0
SBM
45.0
13.8
21.9
9.2
13.8
86.5
Star
58.0
34.0
32.8
31.7
61.7
8.1
SFN
57.6
23.1
19.9
8.0
38.1
90.0
60.9
31.9
28.8
26.6
Complete
20.7
6.2
13.3
Overall
40.4
31,7
12.2
24.3
59.5
ER
41.2
28.4
28.8
12.6
12.8
61.2
BA
40.0
30.0
35.0
14.3
20.8
58.5
CDT
SBM
40.3
26.5
30.2
8.7
13.0
65.8
Star
40.3
38.0
41.8
31.6
68.6
21.3
40.2
32.2
30.8
7.1
43.2
Path
42.0
35.1
35.3
31.1
27.6
Complete
39.6
21.9
28.9
3.9
14.6
69.3
works (SFN) (Barabási & Albert, 1999), Barabási-Albert (BA) model (Albert & Barabási] 2002). and stochastic block model (SBM) (Holland et al.) 1983), in addition star, path, and complete graph generators. We use NetworkX (Hagberg et al. 2008) to generate the random graphs. The details are reported in Appendix A.8
4.2 RESULTS RANDOM GRAPH GENERATORS
Previous experiments have studied the performance of LLMs on basic graph tasks using random graphs generated using the Erdós-Rényí (ER) model. However, ER graphs often not accurately represent the characteristics of real-world graphs. In this experiment, investigate the effect of different random graph generators on the performance
LLMs on graph reasoning tasks. To make the experiment more realistic, sample the few-shot examples randomly from graphs generated using different algorithms. We report the results this experiment Table
Graph structure has significant impact the LLM's performance. The results show that the algorithm used to generate the graph has a significant impact on the performance of the LLM on graph tasks. For example, the cycle check task achieves 91.7% accuracy 5.9% accuracy on path graphs. This is because the LLM has a strong prior towards graphs having cycles. Therefore, the accuracy is high for complete graphs, which always have cycles, and very low for path graphs, which never have cycles. By adding few-shot examples some having a cycle and some not, the accuracy of cycle check on path graphs increased from 5.9% to 19.7%. As another example, edge existence, the LLM achieves 60.0% accuracy path graphs. which are less likely have an edge between two nodes, and 19.8% accuracy on complete graphs, which have edges between all pairs of nodes. This shows that the LLM has a prior that two nodes in graph are more likely to be disconnected.
complete graphs and
Distractive statements in the graph encoding function disrupt the performance of the LLM. The accuracy node degree, node count, and connected nodes tasks is highest for star and path graphs. This is likely because the star and path graphs are more likely to have fewer edges and their graph encoding is most likely shorter with less distracting statements to these tasks. This is also evident from the accuracy of these tasks being among the lowest in complete graphs, which have many edges to specify and therefore many distractors.
Adding nut-of-distribution few-shot examples helped the LLM. Similarly to the experiment in Section [.I adding few-shot examples and their chain of thought in COT prompting helped on most tasks. The key difference between the few-shot examples in this experiment and the previous one is that in this case, the examples are not required to come from the same graph generator algorithm. This shows that shotshot examples do not need come from the same generator for the LLM be helpful, and their main role is to explain the task to the LLM.
Summary: The performance of large language models (LLMs) on graph tasks is significantly im- pacted by the graph structure and the distracting statements in the graph encoding function. Graphs
8

---

Published as a conference paper at ICLR 2024
with fewer edges and less complex encodings tend to perform better most tasks. Adding few-shot examples, even if they are out-of--istribuu can help the LLM to perform better on most tasks.
5 RELATED WORK
In-context learning. One approach for reasoning with LLMs is to pre-train it on a large corpus of text that is closely related the task. This has been shown to improve the performance (Hendrycks) et al., [2221] (Shen et al.] (02T). but it can be computationally expensive, especially for larger mod- els. Additionally, fine-tuning often demands domain-specific data and human expertise, adding to the cost. Brown et al. (2020b) has demonstrated the capabilities of LLMs in tackling novel tasks with little or no training data. The FEW-SHOT method inserts k in-context input-output pairs before the test input and has been shown significantly improve the performance of the LLM on unseen tasks. Recent research has proposed strategies to improve the selection of in-context demonstrations, such retrieving semantically similar examples (Liu et al. (02T), employing
rea- soning (Wei et al. 2022). and decomposing tasks into sub-problems using least-to-mos prompt- ing (Zhou al. 2022a). In this work, we focus on evaluating and enhancing LLMs on basic graph reasoning tasks. We exploit some of the ideas in the literature and compare their results.
Text-based reasoning with LLMs. Numerous models have been proposed for text-based reasoning employing LLMs (see (Huang & Chang 2022) for survey). One approach to reasoning with LLMs modular reasoning. This methodology divides the problem into smaller modules, utilizing distinct
LMs to address each module (Zhou et al., 2022a; Kazerni et al.) [222 Khot et al. (022). Another approach to reasoning with LLMs aims to predict the output of a question single LM call. This study primarily focuses on the latter method.
Knowledge-Augmentte LLMs. Another body of work is concerned with the use of knowledge (frequently stored in knowledge graphs (KGs)) to improve LLM understanding of the world (Pan) jet al., (023). Several different methodologies have been proposed which range from generating
additional training data from KGs (Guu et al.) 2020 Lewis et al. 2020 Agarwal et al., 2021 to
extending pretraining (Yasunaga et al.) 2022: Jin et al. 2023).
Reasoning on graphs using LLMs. The combination of graph learning and reasoning with LLMs is a rapidly growing area. InstructGL. (Ye et al. 2023) proposed an instruction-finen finetunedd LLM for performing node classification. Chen et al. (2023) used LLMs enhancers to exploit text attributes to be used in a graph learning model or as predictors for node classification on text-attributed graphs Sanchez al. (2023) encode text sequences into graphs (and back), and leverage LLMS as the mapping functions between them to aid commonsense reasoning. The closest work to ours is Wang al. (2023), which proposed set of tasks for benchmarking LLMs on graphs. However, this work omitted several natural graph tasks, lacked variety in the type of graph structure considered, and fixed the graph and question encoder function. They conclude that LLMs have preliminary graph reasoning abilities on somewhat complex graph tasks.
Present work. this study, we focus on basic graph tasks, which are essential intermediate steps for more complex reasoning tasks on graphs. We conduct extensive experiments graph and question encoder functions, as well as a wide range of graph generator functions. We provide an extensive study of graph encoding methods for black-box LLM usage, and introduce Graph@A, new graph benchmark that illustrates the effect of graph structure on LLM encoding. We also provide insights and best practices for encoding graphs as text for use in LLMs.
6 CONCLUSIONS
In this work, we have presented 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: (I) the graph encoding method, (2) the nature of the graph task it- self, and (3) interestingly. the very structure of the graph considered. These novel results provide graph
valuable insight strategies for encoding graphs as text which can boost performance reasoning tasks inside LLMs by 4.8% to 61.8%. We believe that this is a fruitful avenue for further investigation, and hope that our Graph@A benchmark tasks inspire additional work in the area.

---

Published as a conference paper at ICLR 2024
7 ACKNOWLEDGEMENT
We express our sincere gratitude to Anton Tsitsulin, Dustin Zelle, Silvio Lattanzi, Vahab Mirrokni, and the entire graph mining team at Google Research, for their insightful comments, thorough proof- reading, and constructive feedback which greatly enhanced the quality of our work. Furthermore, we extend our appreciation the anonymous ICLR reviewers for their constructive suggestions. Their expertise and feedback played crucial role in refining our paper.
REFERENCES
Oshin Agarwal, Heming Ge, Siamak Shakeri, and Rami Al-Rfou. Knowledge graph based synthetic corpus generation for knowledge-enhanced language model pre-training, 2021.
Réka Albert and Lászóó Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
Rohan Anil, Andrew M Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, al. Palm 2 technical report. arXiv preprint 2rXiv:2305.10444 2023.
Albert-LászIó Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-55) 1999.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020a.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 13:1877-1 2020b.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Ka- mar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:2303. 2023.
Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, et al. Exploring the potential of large language models (Imms) in learning on graphs. arXiv preprint arXiv:2307.03399 2023.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.023111 2022.
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al. Scaling iintrucctio-finetttii language mod- els. arXiv preprint arXiv:22100 /4411 2022.
Peter Clark, Oyvind Tafjord, and Kyle Richardson. Transformers as soft reasoners over language. arXiv preprint arXiv:2002.05867, 2020.
Jacob Devlin, Ming-Was Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, 2018.
Vijay Prakash Dwivedi and Xavier Bresson. generalization of transformer networks to graphs.
arXiv preprint arXiv:2012.09699 2020.
Paul Erdös and Alfred Rényi On random graphs. Publicationes Mathematicae Debrecen, 6:290- 297, 1959.
Jiayan Guo, Lun Du, and Hengyu Liu. Gpt4graph: Can large language models understand graph structured data? an empirical evaluation and benchmarking. arXiv preprint 2tt::2305.15666 2023.
10

---

Published as a conference paper at ICLR 2024
Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Mingwei Chang. Retrieval augmented language model pre-training, In International conference on machine learning, pp. 3929-3938. PMLR. 2020.
Aric Hagberg, Pieter Swart, and Daniel S Chult. Exploring network structure, dynamics, and func- tion using networkx. Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv preprint ar 003. 03874, 2021.
Paul W Holland, Kathryn Blackmond I Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983.
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv preprini arXiv:2106.09685, 2021.
Jie Huang and Kevin Chen-Chuan Chang. Towards reasoning in large language models: A survey. arXiv preprint arXiv:2212.10400 2022.
Bowen Jin, Wentao Zhang, Yu Zhang, Yu Meng, Xinyang Zhang, Qi Zhu, and Jiawei Han. Patton: Language model pretraining on text-rich networks. arXiv preprint arXiv:2305. 12268, 2023.
Seyed Mehran Kazemi, Najoung Kim. Deepti Bhatia, Xin Xu, and Deepak Ramachandran. Lambada: Backward chaining for automated reasoning in natural language. arXiv preprint arXiv:2212.13894, 2022.
Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal. Decomposed prompting: A modular approach for solving complex tasks. arXiv preprint arXiv:2210.02406, 2022.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199 222133, 2022.
Brian Lester, Rami AI-Rfou, and Noah Constant. The power of scale for parameter-efficient prompt tuning. arXiv preprint (iti::20040069/// 2021.
Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. detrieval-augmenter genera- tion for inowledge-nttensive nlp tasks. Advances in Neural Information P Processing Systems, 33; 9459-9474, 2020.
Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen. What makes good in-context examples for gpt-3? arXiv preprint arXiv:2101.06804 2021.
Luis Müller, Mikhail Galkin, Christopher Morris, and Ladislav Rampášek. Attending graph transformers. arXiv preprint arXiv:2302.04181, 2023.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730-27744, 2022.
John Palowitch, Anton Tsitsulin, Brandon Mayer, and Bryan Perozzi. Graphworld: Fake graphs bring real insights for gnns. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3691-3701, 2022.
Shirui Pan, Linhao Luo, Yufci Wang, Chen Chen, Jiapu Wang, and Xindong Wu. Unifying large language models and knowledge graphs: A roadmap, 2023.

---

Published as a conference paper at ICLR 2024
Reid Pryzant, Dan Iter, Jerry Li, Yin Tat Lee, Chenguang Zhu, and Michael Zeng. Automatic prompt optimization with" gradient descent" and beam search. arXiv preprint arXiv:2305.03495, 2023.
Ramses Sanchez, Lukas Conrads, Pascal Welke, Kostadin Cvejoski, and Cesar Ojeda Marin. Hidden schema networks. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceed- ings of the sl Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 4764-4798, Toronto, Canada, July 2023. Association for Computational Lin- guistics. doi: 10. acl acl-long.263
Phillip Schneider, Tim Schopf, Juraj Vladika, Mikhail Galkin, Elena Simperl, and Florian Matthes. A decade of knowledge graphs in natural language processing: A survey. arXiv preprint arXiv:2210.001055 2022.
Jianhao Shen, Yichun Yin, Lin Li, Lifeng Shang, Xin Jiang, Ming Zhang, and Qun Liu. Generate & rank: A multi-task framework for math word problems. arXiv preprint arXiv:2109.0300 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural informa- fion processing systems, 30, 2017.
Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language? In Thirty-seventh Conference on Neural Information Processing Systems, 2023. httttss://oppnrevieeeeee net.e//wwwwweeeeeeeeeee....eeeee ner.rruummmmm
id UdUDihhhqyJJV
Jason
Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. -hain-of-thouugt prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35:24824-24837, 2022.
Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le. Denny Zhou, and Xinyun Chen. Large language models as optimizers. arXiv preprint arXiv:2309.034 03449, 2023.
Mustafa Yasir, John Palowitch, Anton Tsitsulin, Long Tran-Thanh, and Bryan Perozzi. Examining the effects of degree distribution and homophily in graph learning models, 2023.
Michihiro Yasunaga, Antoine Bosselut, Hongyu Ren, Xikun Zhang, Christopher D Manning. Percy graph pretraining, 2022.
Liang, and Jure Leskovec. Deep bidirectional
Ruosong Ye, Caiqi Zhang, Runhui Wang, Shuyuan Xu, and Yongfeng Zhang. Natural language is all graph needs. arXiv preprint 23Xiv:2308007133 2023.
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001.05 140, 2020.
Sarah J Zhang, Samuel Florin, Ariel N Lee, Eamon Niknafs, Andrei Marginean, Annie Wang. Keith Tyser, Zad Chin, Yann Hicke, Nikhil Singh, et al. Exploring the mit mathematics and eecs cur- riculum using large language models. arXiv preprint arXiv:2306.0899) 2023a.
Yue Zhang, Yafu Li, Leyang Cui, Deng Cai, Lemao Liu, Tingchen Fu, Xinting Huang, Enbo Zhao, Yu Zhang, Yulong Chen, al. Siren's song the ai ocean: A survey on hallucination in large language models. arXiv preprint arXiv:2309.0122 20232
Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yinggian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et survey of large language models. arXiv preprint arXiv:2303. 18223, 2023.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuur- mans, Claire Cui, Olivier Bousquet, Quoc Le, et al. Least-to-mos prompting enables complex reasoning in large language models. arXiv preprint 2XX::2205..0625 2022a.
Yongchao Zhou, Andrei Ioan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. Large language models are human-level prompt engineers. arXiv preprint arXiv:2211.01910. 2022b.
12

---

Published as a conference paper at ICLR 2024
A APPENDIX
A.1 GRAPH ENCODING FUNCTION
We conducted an investigation into various methodologies for representing graphs as text. This process of encoding graphs text be separated into two key inquiries: First, the encoding of nodes within the graph, and second the encoding of edges between the nodes.
Encoding Nodes. Regarding the encoding of nodes, examined several techniques, including:
Integer encoding (e.g., Node 0).
Utilizing well-known English first names (e.g., David).
Utilizing popular character names in television series Game of Thrones and South Park.
Incorporating the first names of American politicians.
Employing alphabet letters for representation.
Representing Edges. Regarding the encoding of the edges, examined the following techniques:
Parenthesis: describing edges as (source node, target node).
Friendship: source node and target node are friends.
Coauthorship: source node and target node wrote a paper together.
Social network: source node and target node are connected.
Arrows: source node + target node.
Incident: source node is connected to target nodes.
Combining the node and edge encoding, we start with the following list of graph encoding functions:
Adjacency. using integer node encoding and parenthesis edge encoding.
Incident. using integer node encoding and incident edge encoding.
Friendship. using well-known english first names as node encoding and friendship edge encoding.
Co-authorship. using well-known english first names node encoding and coauthorship edge encoding.
SP. using South Park character names as node encoding and friendship as edge encoding.
GOT. using Game of Thrones character names as node encoding and friendship as edge encoding.
Social network. using well-known English first names and social network edge encoding.
Politician. using politician American politician first names and social network edge en- coding.
Expert. employing alphabet letters for node encoding and arrows as edge encoding. The encoding starts with "You are graph analyst" (expert prompting (Zhang et al. 2023a)).
Here, we provide the full details for the graph encoding functions for the graph example in Figure
Adjacency: In an undirected graph, (i.j) means that node and node j are connected with an undi- rected edge. describes graph among nodes 2, 3, 4, 6, 7, and The edges in G are: (0, 1) (0, 2) (1, 2) (2, (2, 4) (2, 5) (2, 7) (3, 8) (5, 6) (6, 7) (7, 8).
13

---

Published as a conference paper at ICLR 2024
Figure 5: Running example graph for all graph encoding functions.
Incident: G describes graph among 0, 1, 2, 4, 6, 7, and 8.
In this graph:
Node 0 is connected to nodes 1, 2.
Node 1 is connected to nodes 0,
Node 2 is connected to nodes 0, 1, 3, 4, 5, 7.
Node 3 is connected to nodes 2,
Node 4 is connected to node 2.
Node 5 is connected to nodes 2,
Node 6 is connected to nodes 7, 5.
Node 7 is connected to nodes 2, 8,
Node 8 is connected to nodes 3,
G describes co-authorship graph among James, Robert, John, Michael, David, Mary, Patricia, Jennifer, and Linda.
Co-authorship:
In this co-authorship graph:
James and Robert wrote paper together.
James and John wrote paper together.
Robert and John wrote paper together.
John and Michael wrote a paper together.
John and David wrote paper together. John and Mary wrote paper together. John and Jennifer wrote paper together. Michael and Linda wrote paper together. Mary and Patricia wrote paper together. Patricia and Jennifer wrote paper together. Jennifer and Linda wrote paper together.
Friendship: describes friendship graph among James, Robert, John, Michael, David, Mary. Patricia, Jennifer, and Linda.
We have the following edges G: James and Robert are friends.
James and John are friends.
Robert and John friends.
John and Michael are friends.
John and David are friends.
John and Mary are friends.
John and Jennifer are friends.
Michael and Linda are friends.
Mary and Patricia are friends.
Patricia and Jennifer are friends.
Jennifer and Linda are friends.
14

---

Published as a conference paper at ICLR 2024
SP: G describes friendship graph among Eric, Kenny, Kyle, Stan, Tolkien, Heidi, Bebe, Liane, and Sharon.
In this friendship graph:
Eric and Kenny are friends, Eric and Kyle are friends. Kenny and Kyle are friends, Kyle and Stan are friends, Kyle and Tolkien are friends, Kyle and Heidi are friends, Kyle and Liane are friends, Stan and Sharon are friends, Heidi and Bebe are friends, Bebe and Liane are friends, Liane and Sharon are friends.
GOT: G describes friendship graph among Ned, Cat, Daenerys, Jon, Bran, Sansa, Arya, Cersei, and Jaime.
In this friendship graph: Ned and Cat are friends, Ned and Daenerys friends, Cat and Daenerys are friends, Daenerys and Jon are friends, Daenerys and Bran are friends, Daenerys and Sansa are friends, Daenerys and Cersei friends, Jon and Jaime friends, Sansa and Arya friends, Arya and Cersei are friends, Cersei and Jaime are friends.
Social Network: G describes social network graph among James, Robert, John, Michael, David, Mary, Patricia, Jennifer, and Linda.
We have the following edges in G:
James and Robert are connected. James and John are connected.
Robert and John are connected.
John and Michael are connected. John and David are connected.
John and Mary are connected.
John and Jennifer are connected. Michael and Linda are connected. connected. Mary and Patricia
Patricia and Jennifer are connected. Jennifer and Linda connected.
Politician: G describes a social network graph among Barack, Jimmy, Arnold, Bernie, Bill, Kamala, Hillary, Elizabeth, and John.
We have the following edges in G:
Barack and Jimmy are connected. Barack and Arnold are connected. Jimmy and Aroll are connected. Amoll and Bernie connected. Amold and Bill are connected.
Arnold and Kamala connected, Aroold and Elizabeth are connected. Bernie and John are connected.
Kamala and Hillary are connected. Hillary and Elizabeth are connected. Elizabeth and John are connected.
Expert: You are a graph analyst and you have been given a graph among A, B, C, E, and I. G has the following undirected edges:
A-> B
A-> C
B-> C
C-> D
C-> E
C-> F
C-> H
D->I
G
G->H
H*>
15

---

Published as a conference paper at ICLR 2024
A.2
DETAILS ON GRAPHOA
A.2.1
GRAPH TASKS
GraphQA consists of a diverse set of basic graph problems, including:
Edge existence. Determine whether given edge exists in graph.
Node degree. Calculate the degree of a given node in graph.
Node count. Count the number of nodes graph.
Edge count. Count the number of edges in graph.
Connected nodes. Find all the nodes that are connected to a given node graph.
Cycle check. Determine whether graph contains cycle.
Disconnected nodes. Find all the nodes that are not connected to given node in a graph.
Reachability, Determine whether there is path from one node to another.
Shortest path. Calculate the length of the shortest path from one node to another.
Maximum flow. Calculate the maximum feasible flow from one node to another.
Triangle counting. Count the number of triangles in the graph.
Node classification. For this task. we used the stochastic block model graph generator to create two distinct blocks representing soccer and baseball enthusiasts. We then label subset of nodes and ask the LLM to determine whether an unspecified node belonged to the soccer or baseball group. This exercise aimed assess the LLM's ability exploit the homophily in a given graph.
These tasks are all relatively simple, but they require LLMs be able reason about the rela- tionships between nodes and edges in graph. While adhering to basic graph tasks, we aimed for a diverse set of tasks, including discriminative (e.g., cycle check) and generative (e.g., connected or disconnected nodes) challenges. These tasks covered various aspects of graph analysis, from existence checks (e.g., edge existence) to quantitative assessments (e.g., node count), path analysis (e.g., (e.g.,cycle check), recall-based tasks (e.g., connected nodes), and null space exploration (e.g., dis- connected nodes).
The basic graph tasks listed above are all essential intermediate steps for more complex reasoning tasks on graphs. For example, to determine the shortest path between two nodes in graph, we must first be able to find all the nodes that are connected to given node. To detect communities in graph, we must first be able identify all the cycles in the graph. To find the most influential node in graph, must first be able calculate the degree of each node. These tasks essential building blocks for more complex reasoning tasks on graphs.
A.2.2 GRAPH GENERATION
To generate random graphs, use Erdös-Rényi (ER) graphs (Erdōs Rényi 1959), scale-free networks (SFN) (Barabási & Albert 1999). Barabási Albert (BA) model (Albert & Barabási] 2002), and stochastic block model (SBM) (Holland et al.) 1983). in addition star, path, and complete graph generators. Here, we briefly describe these graph generator algorithms:
ER takes two parameters: the number of vertices and the probability of an edge existing between any two vertices p. For each pair of vertices, the generator randomly decides whether create edge between them with probability p. This process results in graph with an average edge density of p.
SFN graphs are type of network whose degree distribution follows power law. This means that small number of nodes (hubs) have very large number of connections, while the vast majority of nodes have very few connections. SFNs are found in many real-world networks, such the World Wide Web, social networks, and biological networks.
BA model creates seale-free networks by adding new nodes that connect to existing nodes with probability proportional to their degree. In other words. nodes more likely to connect to nodes that already have many connections. This results in a network with a few highly connected nodes and many sparsely connected nodes.
16

---

Published as a conference paper at ICLR 2024
SBM is a generative model for random graphs that assumes the presence of underlying communities or groups of nodes within the network. It characterizes these communities by assigning probability each pair of nodes being connected, with higher probabili- ties for nodes within the same community and lower probabilities for nodes in different communities.
A star graph is a type of graph in which one vertex, called the central vertex, is connected to all other vertices, which are called leaves. The central vertex has degree of n-1, where n the number of vertices in the graph. The leaves all have degree of 1.
A path graph a type of graph in which the vertices can be listed in a linear order such that every edge connects two consecutive vertices in the list. In other words, path graph is simple chain of vertices connected by edges.
A complete graph is type of graph in which every pair of distinct vertices is connected by unique edge.
To generate graphs, we sampled 500 graphs for each of the following algorithms: ER, BA, SFN, and SBM. We sampled 100 graphs for path, complete, and star graphs, as these have less variety. All graphs had between 5 and 20 nodes. For ER graphs, we sampled the probability for edge creation from [0, 1]. For SBM graphs, number of communities has been sampled from 2 to 10.
A.2.3 GRAPH STATISTICS
Table 5 reports the statises of the graph generated. We are commited to open-source the code
Table 5: Ranking of graph encoding functions from experiment in Section 3.1 (lower better).
Graph generator
Number of nodes
Number of edges
Node degree
ER
12.37
39.79
5.70
SPN
12.31
23.28
3.70
BA
12.25
30.02
4.40
SBM
12.27
38.68
5.59
Star
11.60
10.60
1.80
Path
11.60
10.60
1.80
Complete
11.60
70.51
10.60
A.3 AGGREGATED RESULTS ON GRAPH ENCODING FUNCTIONS
To provide recommendations about the best graph encoding function to use for each prompt type, we rank the encoders by their average standing (in rank order) on each graph task. The results are presented in Table 6 where lower number is better (the encoder ranked higher average). We note that for most prompting methods, incident encoding performed the best. However, for ZERO- SHOT graph prompting, node tokens with more established representations (such as politicians or popular fantasy characters) outperformed incident encoding. (able'rrepune dard deviation) of the reported results in Section 3.1 aggregated over the graph encoding function. In terms of the average results, incident encoding performed the best across all the tasks. We posit that the success of incident encoding can be attributed two key factors. Firstly, it leverages integer node encoding (c.g., node 0 or node 1), as we previously emphasized the advantages of this approach in Section B.I.I Secondly, incident edge encoding effectively captures the one-hop neighborhood around a graph, outperforming methods that simply list edges in random order.
the average (and stan-
A.4 EXPERIMENT 2: VARYING PROMPT QUESTION
In experiment 2 in the main body of the paper, maintained the graph encoding function con- stant for the concept friendship and conducted experiments using two distinct question encoder functions: the graph question encoder and the application question encoder. Table question encoder function varies for each graph task. In summary, edge existence became "assess- ing friendship existence", node degree became "counting the number of friends for individual".
8 states how the
17

---

Published as a conference paper at ICLR 2024
Table 6: Ranking of graph encoding functions from experiment in Section 3.1 (lower better).
Encoding
ZERO-SHOT
ZERO-COT
FEW-SHOT
COT
COT-BA BAT
Adjacency
4.83
3.25
2.16
3.00
1.83
Incident
6.16
2.58
2.00
2.33
1.33
Co-authorship
6.08
6.33
5.58
6.75
8.83
Friendship
5.16
6,41
6.25
4.66
6.00
SP
5.16
4.50
5.25
5.75
4.66
GOT
4.33
4.08
5.83
5.00
6.25
Social Network
4.58
6.50
5,83
6.16
6,41
Politician
3.50
6.33
6.25
5.58
4.00
Expert
5.16
5.00
5.83
5.75
5.66
Table 7: Aggregated results from experiment in Section 3.1 mean and standard deviation (higher mean better).
graph encoding funetions with
Graph Encoding
ZERO-SHOT
ZERO-COT
FEW-SHOT
COT
COT-BAG
Adjacency
30.4 (21.5)
20.8 (14.4)
32.3 (13.8)
45.9 (17.6)
43.9 (16.4)
Incident
35.6 (20.8)
(12.4)
(11.4)
48.1 (18.7)
49.6 (16.8)
Co-authorship
28.3 (22.4)
15.8 (10.1)
21.1 213.3)3.3)
18..) 217.9
Friendship
29.5 (27.2)
16.1
214.3)
2161) (20.1)
SP
29.9 (26.1)
(11.8)))))
(11.4)
21.97)
24.5 (14.5)
GOT
30.9 (25.4)
17.7 (12.0)
(12.)
219.3)
23.6 (15.7)
Social Network
30.4 (25.5)
15.1 (10.0)
211.3
26.3
24.7 (16.9)
Politician
30.9 (25.3)
15.3 (12.2)
20.2
(18.4)
26.1 (17.5)
Expert
29.3 (20.6)
(7.6
18.8 (6.4)
24.7 (13.2)
23.8 (10.9)
node count became "counting the number of people mentioned", edge count became "counting the number of friendships mentioned", and connected nodes became "listing friends".
Table 8: Examples for graph tasks and their corresponding graph question encoder and application question encoder.
Gruph question encuder
Application question encoder
Edge existence
Is mode Christopher connected to node Michael?
Are Christopher and Michael friends?
Node degree
What is the degree node 14?
How many friends does Christopher lave?
Node count
How many nodes are in this graph?
How many people are mentioned in this information?
Edgge
many edges
graph??
many friemdships given this information?
Connected nodes
List all the nodes connected to node Christopher.
List all the people who are friends with Christopher.
A.5 MORE COMPLEX GRAPH REASONING TASKS
In this experiment, we expand our experiments with Graph@A to encompass a wider range of com- plex graph reasoning tasks, including reachability, shorfest path, maximum flow, triangle counting, and node classification. Results from these additional tasks are shown Table 9 Our core findings remain consistent: the chosen graph encoding function plays crucial role in influencing the LLM's graph reasoning performance. For instance, in triangle counting, the social network encoding yields 7.0% accuracy, while the adjacency encoding resulted in significantly higher 27.0% accuracy. The main results hold for these complex tasks as well. Mainly, the graph encoding function has a sig- nificant impact on LLM graph reasoning e.g., triangle counting gets 7.0% with social network and 27.0% with adjacency.
A.6 EXPERIMENTING WITH GPT-3.5-TURBO
In this section, we conduct experiments using gpt-3.5-turbo (Brown et al.) 2020a) and report the results in Table TO This additional evaluation provides further insights into the performance of
18

---

Published as a conference paper at ICLR 2024
Table 9: Comparison of various graph encoding functions based their accuracy on different graph tasks using PaLM 62B. The most effective prompting heuristic highlighted with an underline, and the top-performing graph encoding function for it is highlighted in bold.
Method
Encoding
Reachability
Shortest path Maximum flow
Triangle counting
Node classification
Overall
84.9
11.5
12.2
1.5
12.0
Adjacency
83.8
10.2
12.0
16.4
Incident
84.6
9.8
12.2
1.2
15.8
ZERO-SHOO
Co-authorship
84.2
18.0
12.8
1.8
9.2
Friendship
83.8
11.0
12.2
1.6
3.0
SP
85.4
12.4
13.2
0.8
10.8
GOT
86.8
9.6
11.4
0.8
4.6
Social network
85.8
13.0
12.8
2.0
5.4
Politician
81.6
13.2
11.8
1.2
24.4
Expert
87.8
6.4
11.4
1.8
18.4
Overall
73.5
33.6
37.9
12.7
77.4
Adjacency
72.4
37.2
50.2
27.0
79.8
ZERO- CORO-COT
Incident
77.2
35.4
56.0
25.6
80.6
Co-authorship
71.6
35.8
33.4
9.2
73.6
Friendship
75.0
32,4
32.4
8.6
81.0
SP
79.8
39.6
33.2
10.2
68.6
GOT
77.0
34.8
33.4
8.2
70.8
Social network
79.8
29.4
36.4
7.0
83.4
Politician
52.6
26.8
34,6
8.2
76.4
Expert
76.4
31.4
31.8
10.4
82.2
Overall
79.4
22.7
10.8
3.0
43.4
Adjacency
76.8
19.8
12.2
3.8
34.2
FEW SHOT
Incident
65.0
20.8
13.2
2,4
43.2
Co-authorship
80.8
24.0
12.0
3,4
46.2
Friendship
82.6
29.6
10.4
3,4
50.6
SP
82,4
22.2
11.8
2.6
49.2
GOT
82.0
20.6
10.2
2.8
49.4
Social network
82.2
26.2
10.4
2,2
47.8
Politician
82.4
24.6
9.2
3,2
49.6
Expert
80.8
16.8
8.2
3,4
20.8
Overall
45.2
38.6
45.0
8.1
54.4
Adjacency
53.8
36.4
49.2
21.6
53.6
Incident
39.4
35.2
47.2
19.8
54.4
Co-authorship
52.0
43.8
43.8
5.6
50.2
COT
Friendship
40.2
46.6
41.4
5.0
57.2
SP
46.2
37.4
43.2
4.2
60.2
GOT
48.2
35.4
41.6
4.2
56.4
Social network
43.8
42.8
44.8
3.2
56.0
Politician
45.8
39.2
42.2
4.0
55.8
Expert
37.6
30.2
51.8
5.6
46.0
Overall
45.2
40.4
44.4
52.1
Adjacency
53.8
38.0
49.6
20.8
50.2
COT-BAG
Incident
39.4
38.2
44.6
19.4
52.6
Co-authorship
52.0
45.6
39.6
52.6
Friendship
40.2
48.4
42.4
53.0
SP
46.2
35.8
42.0
55.4
GOT
48.2
40.0
42.0
55.2
Social network
43.8
44.0
46.8
51.8
Politician
45.8
40.6
41.4
54.4
Expert
37.6
33.4
51.6
43.8
our approach and confirms the key findings observed on Palm and 2. particular, graph encoding functions have substantial impact on the performance of LLMs graph-based tasks, with the node degree task exhibiting a performance variance of 5.4% to 66.4%. Integer node encoding enhances arithmetic performance for node degree, node count, and edge count tasks. The incident encoding outperforms other encoding functions by a significant margin on the connected node task due to its ability to make information more readily accessible for LLM utilization.
19

---

Published as a conference paper at ICLR 2024
Table 10: Comparing different graph encoding functions different graph tasks for 3pt-3.5-turbo on ZERO-SHOT prompting. The cop-eerforning graph function encoder for is highlighted in bold.
Encoding function
Edge Existence
Node degree
Node count
Edge count
Connected nodes
Cycle check
Overall 77.0
42.2
98.8
37.6
46.7
86.1
Adjacency
73.0
99.2
46.2
59.2
84.2
Incident
80.2
66.4
96.2
12.6
75.2
84.6
Co-authorship
82.0
42.6
99.8
39.4
37.2
86,4
Friendship
73.8
43.8
100.0
41.8
41.2
87.4
SP
74.0
44.2
39.0
38.6
GOT
75.8
41.0
99.0
39.4
38.6
88.6
Social Network
78.6
47.6
99.8
38.6
40.6
86.6
Politician
78.6
45.4
100.0
39.8
40.2
84.2
Expert
75.7
43.5
95.3
41.7
49.2
86.6
A.7 COMPARISON WITH EXISTING WORKS
In this section, we highlight the contributions this paper by comparing it to some of the existing works in the literature. Our work uniquely investigates how properties of the graph structure (via synthetic generation) influence the choice graph encoding function. This is completely novel, as no other related work examines these interactions. This novel approach enables to systematically study these interactions, which have not been explored in previous research. Additionally, we con- ducted extensive scaling experiments with LLMs of varying parameter sizes which other work has done. Finally, we have significant differences from each work individually, for example: unlike (Guo al., 2023). we study a diversity LLMs (and have added more models in the rebuttal), unlike (Chen et al. 2023) we vary prompting and graph tasks, and unlike (Ye et al.) (202)). we use black box model without model weights. Furthermore, we conducted experiments on varying ques- tion encoder functions to evaluate their impact on performance. Table [1 clearly states the novelty of our work.
Table 11: Comparing this work to existing works in the literature.
Guo ct al
2023
Chen et al
2023
Ye al
2023
Ours
Synthetic generation
Black-box model
Scaling experiments
Varying question encoding fanction
x
Varying graph encoding function
X
Varying node eucoding function
X
Varying edge encoding
Varying graph structure
X
A.8 IMPLEMENTATION DETAILS
For our experiments, we used PaLM 62B and PaLM 2 (various sizes) served on a 4 x 4 TPU v4 architecture. The decoding temperature was zero. GPT results are obtained by connecting to the OpenAl API. We used the NetworkX library (Hagberg et al. 2008) to generate the random graphs and find the answers to the graph tasks. We are committed to open-soureing both our code and data upon the acceptance of our paper.
A.9 EVALUATING MORE LLMS FOR GRAPH TASKS WITH DIFFERENT GRAPH ENCODING FUNCTIONS
We compared different graph encoding functions on PaLM 62B (Chowdhery al. 2022 in Section 3.1 Here, we provide the results of the same experiment on PaLM XXS, XS, S, and Anil et 2023) in Tables 12 and [6] We also provide results for some cnerruction-iintttnnn
Flan (Chung et al. 2022) checkpoints of the same models in Tables I3 and 15
20

---

Published as a conference paper at ICLR 2024
Table 12: Comparing different graph encoding functions on different graph tasks for PaLM XXS.
The most effective prompting heuristic is highlighted with underline, and the top-performing graph function encoder for the respective heuristic is highlighted in bold.
Method Encoding function
Edge Existence
Node degree
Node count
Edge count
Connected nodes
Cycle check
Overall
47.2
11.3
8.7
6,4
7.2
61.5
Adjacency
48.4
14.4
6.2
4.0
17.6
82.6
ZERO SHOO-SHOT
Incident
45.2
13.4
11.2
Co-authorship
10.8
5.2
Friendship
42.8
10.8
SP
56.6
11.0
5.8
3.0
26.6
GOT
56.4
7.8
7.0
2.0
51.8
Social Network
51.2
11.0
7.8
5.4
5.2
74.4
Politician
40.6
12.0
9.4
6.8
10.0
73.2
Expert
38.0
10.4
21.4
12.8
9.0
45.2
Overall
34.1
8.6
1.7
2.2
6.0
13.7
Adjacency
20.2
19.0
2.4
2.0
9.0
16.4
PERO-COT
Incident
45.0
36.0
1.2
6.0
16.0
37.8
Co-authorship
48.8
22.0
4.4
11.8
31.6
Friendship
43.2
0.2
0.6
1.6
2.0
10.8
SP
30.8
0
1.0
3.0
2.6
Social Network
4.8
Politician
40.6
5.2
Expert
16.8
1.6
Overall
42.7
10.3
23.9
13.3
Adjacency
50.2
11.8
77.6
27.0
17.4
83.4
FEW FEW-SHOT SHOT
Incident
46.6
12.8
58.4
19.8
18.4
57.8
Co-authorship
44.2
7.6
31.0
11.8
11.4
31.0
Friendship
42.8
9.6
8.8
7.4
11.8
7.2
SP
29.4
10.4
9.6
4.6
11.6
7.0
GOT
26.0
10.0
8.2
5,4
9.0
9.8
Social Network
9.4
11.2
Politician
8.2
Expert
24.7
Adjacency
51.0
80.8
72.2
22.0
19.6
84.0
Incident
48.6
55.0
54.4
17.2
81.6
Co-authorship
51.4
31.2
29.8
10.0
12.2
80.6
COT
Friendship
50.4
8.8
8.4
4.2
10.2
77.4
SP
52.2
9.4
10.0
6.6
12.0
74,6
GOT
$1.4
9.2
8.0
5.6
10.4
70.4
Social Network
53.8
8.6
7.8
5.8
8.4
76.0
Politician
47.0
9.4
8.4
6,4
13.8
75.8
Expert
49.6
10.2
5.6
72.6
Overall
50.3
23.7
19.4
9.2
13.6
68.4
Adjacency
49.6
73.0
Incident
53.4
COT-BAG
Co-authorship
50.4
30.4
Friendship
48.8
8.4
5.2
9.2
65.8
SP
50.4
7.0
6.8
5.0
12.4
61.2
GOT
51.8
11.0
6.0
5.0
13.2
57.2
Social Network
55.8
10.6
9.4
4.6
11.0
59.4
Politician
49.2
9.4
6.0
6.6
16.0
69.6
Expert
47.4
10.2
7.4
6.2
14.2
68.6
21

---

Published as a conference paper at ICLR 2024
Table 13: Comparing different graph encoding functions on different graph tasks for Flan-PaLA 2 XXS. The most effective prompting heuristic is highlighted with underline, and the top- performing graph function encoder for the respective heuristic is highlighted in bold.
Method Encoding function
Edge Existence
Node degree
Node count
Edge count
Connected nodes
Cycle check
Overall
56.6
11.1
11.7
3.9
8.2
20.8
Adjacency
$7.6
10.4
10.0
4.6
13.6
23.4
ZERO ZERO-SHOT SHOT
Incident
59.8
12.2
11.8
Co-authorship Friendship
10.8
6.8
$7.2
11.0
3.0
SP
54.8
11.4
15.4
5.8
17.0
GOT
51.2
9.0
16.2
3.4
5.2
16.6
Social Network
54.4
11.8
11.0
3.2
6.6
15.2
Politician
55.8
12.2
8.0
4.8
7.6
18.4
Expert
60.2
11.0
11.8
4.0
11.4
19.6
Overall
45.9
17.6
11.2
9.7
14.4
33.9
Adjacency
51.2
26.2
3.2
16.6
19.2
70.6
PERO-COT
Incident
52.4
38.8
6.0
13.6
16.8
46.4
Co-authorship
47.0
25.0
10.8
12.4
13.8
32.8
Friendship
47.2
10.0
16.6
9.2
11.4
21.4
SP
39.4
9.0
12.8
9.2
9.4
7.8
11.0
Social Network
10.0
Politician
48.2
13.0
13.6
6.2
12.8
22.8
Expert
39.8
16.8
11.6
4.8
19.0
56.2
Overall
54.1
10.0
11.9
8.6
82.6
Adjacency
53.2
11.2
16.2
4.6
9.2
82.8
FEW FEW-SHOT SHOT
Incident
53.2
11.4
23.0
5.6
9.0
80.2
Co-authorship
54.2
10.8
13,0
4.6
8.4
84.4
Friendship
56.0
8.4
9,4
4,8
8.4
81.0
SP
59.0
9.0
10.4
5.4
8.8
84.2
GOT
52.8
8.8
9.4
5,8
8.6
84.6
Social Network
50.6
9.8
4.2
7.8
Politician
7.6
5.2
9.4
Expert
12.8
20.0
82.7
Adjacency
37.4
51.6
10.4
80.0
Incident
56.4
41.0
37.0
10.8
11.2
80.8
COT
Co-authorship
54.4
28.6
19.6
7.2
7.6
83.4
Friendship
58.0
11.0
11.6
4.0
6.0
81.6
SP
62.4
10.4
12.2
3.4
5.4
84.4
GOT
$4.4
11.2
13.2
4.2
5.4
84.0
Social Network
56.0
8.2
12.4
3.8
6.0
86.0
Politician
53.8
8.4
9.6
6,4
8.2
80.8
Expert
9.8
5.0
83.0
Overall
32.6
19.6
17.7
8.1
8.1
82.1
Adjacency
50.2
10.2
Incident
44.0
9.0
79.8
COT-BAG
Co-authorship
52.4
26.4
8.4
7.0
85.2
Friendship
50.8
10.2
12.6
5.2
80.0
SP
56.6
8.8
13.4
4.0
5,8
82.4
GOT
52.6
11.0
12.8
5.4
6.4
82.4
Social Network
54.0
8.0
12.6
5.4
7.8
82.2
Politician
51.0
9.2
10.8
5.0
9.2
83.0
Expert
53.2
9.0
10.6
5.8
12.6
82.8
22

---

Published as a conference paper at ICLR 2024
Table 14: Comparing different graph encoding functions on different graph tasks for PaLM XS.
The most effective prompting heuristic is highlighted with underline, and the nop-performing graph function encoder for the respective heuristic is highlighted bold.
Method Encoding function
Edge Existence
Node degree
Node count
Edge count
Connected nodes
Cycle check
Overall
49.9
23.0
28.7
21.3
10.1
15.6
Adjacency
50.8
22.4
11.4
22.2
23.8
21.8
ZERO SHOO-SHOT
Incident
36.6
11.2
31.0
Co-authorship Friendship
21.4
11.6
20.6
4.2
SP
52.4
22.6
25.8
2.8
GOT
53.8
17.8
32.2
25.8
1.8
Social Network
44.6
22.4
35.8
24.4
2.0
Politician
49.0
21.4
32.8
21.8
5.2
15.2
Expert
50.2
22.0
29.6
18.6
6,6
65,4
Overall
43.7
3.8
16.9
9.9
15.2
14.2
Adjacency
48.2
16.6
3.0
18.4
26.6
40.4
ZERO-COT
Incident
53.6
10.6
2.6
6.2
50.8
43.6
Co-authorship
46.8
2.6
9.2
2.2
19.6
8.6
Friendship
32.8
0.4
18.4
12.6
3.2
3.6
SP
0.4
4.8
7.6
41.2
0.2
3.8
3.6
Social Network
3.8
Politician
47.0
0.8
15.6
4.8
10.0
Expert
36.0
3.0
23.8
14.0
19.4
10.2
Overall
40.4
22.3
26.0
18.7
16.5
27.2
Adjacency
42.2
23.2
43.2
29.6
21.4
58.0
FEW FEW-SHOT SHOT
Incident
48.6
35.4
58.8
31.8
34.0
41.2
Co-suthorship
42.6
24.0
22.2
18.2
15.2
29.4
Friendship
45.0
17.4
16.8
13.8
13.2
18.2
SP
36.6
23.6
16.2
16.0
13.0
20.2
GOT
32.4
19.6
17.2
17.8
10.6
17.0
Social Network
41.6
20.8
12.8
21.0
Politician
16.2
Expert
20.2
57.8
30.2
19.7
Adjacency
43.4
63.0
33.0
69.8
Incident
55.8
63.8
54.4
24.6
44.2
38.8
COT
Co-authorship
59.6
27.2
25.2
13.4
17.2
40.6
Friendship
64.2
19.0
20.2
12.8
13.0
40.8
SP
62.0
19.2
18.0
16.6
15.0
10.2
GOT
62.4
19.6
20.6
17.4
12.2
6.2
Social Network
61.0
21.4
23.0
13.2
10.4
42,6
Politician
55.2
18.4
21.4
14.0
13.6
61.4
Expert
20.0
18.8
17.4
Overall
58.9
29.6
30.0
15.8
20.0
37.1
Adjacency
49.8
37.8
52.8
Incident
61.8
COT-BAG
Co-authorship
59.0
27.0
17.6
34,8
Friendship
66.2
22.6
22.6
10.2
38.2
SP
61.2
18.4
23.8
15.2
13.4
15.6
GOT
61.2
20.4
27.2
15.0
13.6
9.8
Social Network
60.6
19.2
24.8
10.8
13.4
35.8
Politician
54,8
17.8
23.2
11.2
15.4
53.6
Expert
60.0
21.4
29.6
14.4
21.8
19.2
23

---

Published as a conference paper at ICLR 2024
Table 13: Comparing different graph encoding functions on different graph tasks for Flan-PaLM XS. The most effective prompting heuristic is highlighted with underline, and the top- nop-performing graph function encoder for the respective heuristic is highlighted bold.
Method Encoding function
Edge Existence
Node degree
Node count
Edge count
Connected nodes
Cycle check
Overall
68.4
10.2
26.8
4.4
23.0
84.4
Adjacency
78.0
17.6
39.0
7.2
34,4
87.2
ZERO SHOO-SHOT
Incident
76.2
29.6
3.8
45.8
Co-authorship
11.2
3.4
20.8
Friendship
63.4
5.4
15.2
SP
59.2
5.4
16.8
2.8
16.0
84.0
GOT
62.6
4.6
19.6
3.2
18.2
83.2
Social Network
72.0
4.4
17.6
4.0
17.8
84,0
Politician
69.0
5.6
20.0
4.4
17.2
84.6
Expert
70.6
7.6
35.4
7.2
21.4
84.0
Overall
54.3
16.4
32.2
13.4
25.1
59.9
Adjacency
68.6
34.8
23.0
16.6
36.8
82.0
ZERO-COT
Incident
59.4
51.2
24.2
11.0
55.8
67.4
Co-authorship
51.8
15.0
25.8
11.8
26.6
41.4
Friendship
53.8
6.2
41.6
12.2
19.6
70.6
SP
49.4
5.8
33.6
13.8
14.4
37.0
7.6
16.6
Social Network
8.0
Politician
55.6
8.8
14.6
53.8
Expert
51.8
10.6
44.2
17.0
23.2
74.6
Overall
70.9
13.2
21.4
10.4
87.2
Adjacency
72.0
22.4
33,2
14.4
12.2
86.6
FEW FEW-SHOT SHOT
Incident
81.8
27.0
33.6
7.2
22.0
83.4
Co-authorship
68.0
17.8
20.2
11.2
8.0
89.4
Friendship
66.8
7.2
17.0
9,0
4.8
86.8
SP
67.6
7.0
15.8
10.0
6.0
88.6
GOT
67.6
5.0
15.2
9.2
6.8
88.0
Social Network
70.6
10.2
14.6
9.0
6.6
88.2
Politician
71.2
8.6
Expert
13.6
23.8
86.7
Adjacency
76.0
72.4
25.6
16.6
Incident
77.0
63.4
32.8
18.0
23.2
82.2
COT
Co-authorship
67.4
22.6
19,0
13.8
9.4
84,2
Friendship
69.0
7.4
17.6
7.8
10.2
88.8
SP
71.2
7.4
15.4
9.6
9.4
87.4
GOT
71.0
9.8
16.4
7.4
10.2
89.4
Social Network
75.0
6.8
11.4
8.0
8.0
88.4
Politician
72.4
10.2
15.4
11.0
13.4
89.8
Expert
14.6
11.8
25.2
84.8
Overall
74.7
25.0
27.9
14.1
14.8
88.8
Adjacency
73.8
16.2
Incident
63.4
COT-BAG
Co-authorship
72.4
25.2
Friendship
74.6
8.6
25.0
8.6
90.4
SP
74.4
9.0
23.6
10.6
9.6
90.0
GOT
75.6
8.0
24.8
10.2
12.4
91.8
Social Network
76.8
9.2
19.6
9.6
12.2
90.4
Politician
71.2
12.6
22.2
11.8
13.4
91.8
Expert
74.4
15.4
34.6
13.8
26.6
88.0
24

---

Published as a conference paper at ICLR 2024
Table 16: Comparing different graph encoding functions on different graph tasks for PaLM The most effective prompting heuristic is highlighted with underline, and the top-performing graph function encoder for the respective heuristic is highlighted bold.
Method Encoding function
Edge Existence
Node degree
Node count
Edge count
Connected nodes
Cycle check
Overall
48.2
41.4
36.5
12.1
25.0
74.7
Adjacency
47.2
33.6
14.0
19.0
32.8
83.6
ZERO SHRO-SHOT
Incident
44.0
68.8
72.2
Co-authorship
49.2
36.2
41.6
14.0
Friendship
50.4
36.8
17.0
SP
50.0
35.6
51.6
18.2
40.6
GOT
51.6
36.4
49.0
11.2
15.8
75.0
Social Network
47.0
42.0
48.4
9.6
19.0
83.2
Politician
49.0
41.2
37.8
7.6
14.2
83.6
Expert
45.8
41.8
24.8
12.4
22.0
82.6
Overall
37.0
7.4
31.3
13.1
14.7
16.5
Adjacency
46.0
36.0
20.4
20.4
15.6
69.6
PERO-COT
Incident
51.2
26.8
7.8
12.0
72.4
46.6
Co-authorship
53.6
0.6
44.2
9.8
16.2
5.8
Friendship
34,6
0.4
36.4
15.8
5.2
4.8
SP
43.8
2.6
5.6
2.8
Social Network
2.6
Politician
30.4
2.2
Expert
20.0
0.4
17.0
3.0
9.6
16.4
Overall
47.5
36.9
16.9
22.9
40.4
Adjacency
61.4
37.2
81.2
18.4
37.8
43,8
FEW FEW-SHOT SHOT
Incident
69.4
61.2
83.2
20.4
80.4
45.8
Co-authorship
28.2
33.4
31.2
15.8
12.2
20.2
Friendship
47.2
36.0
25.6
17.4
12.8
47.2
SP
45.6
30.6
29.4
15.8
13.8
46.4
GOT
26.2
29.2
27.4
18.2
12.0
37.8
Social Network
35.8
30.8
16.6
13.8
Politician
30.4
13.6
Expert
38.2
44.3
Adjacency
62.6
69.4
23.8
41.8
41.0
Incident
68.2
78.4
80.8
26.6
79.6
44.4
COT
Co-authorship
46.8
36.0
35.2
16.6
12.8
34.6
Friendship
66.2
38.0
29.0
17.4
9.6
46.4
SP
66.4
32.4
29.2
17.6
13.8
45.6
GOT
50.6
30,4
28.0
19.2
8.2
24.2
Social Network
52.2
40.4
31.4
17.0
11.0
50.4
Politician
43.6
32.2
30.8
16.4
8.0
44.8
Expert
62.0
41.8
22.0
51.0
Overall
55.2
43.7
44.4
20.8
22.7
39.6
Adjacency
66.2
40.6
41.6
Incident
77.2
COT-BAG
Co-authorship
41.8
38.4
29.4
Friendship
66.0
36.8
31.8
22.2
6.6
48.8
SP
63.8
30.2
31.0
17.8
10.2
33.8
GOT
59.2
32.2
31.0
19.4
10.0
21.4
Social Network
49.8
39.4
34.0
20.6
12.2
47.6
Politician
47.8
32.4
32.8
16.8
6.2
38.6
Expert
55.4
40.6
30.0
21.0
25.4
52.8
25

---

Published as a conference paper at ICLR 2024
Table 17: Comparing different graph encoding functions on different graph tasks for PaLM L. The most effective prompting heuristic is highlighted with underline, and the top-performing graph function encoder for the respective heuristic is highlighted bold.
Method Encoding function
Edge Existence
Node degree
Node count
Edge count
Connected nodes
Cycle check
Overall
47.5
55.1
76.3
30.6
19.5
83.3
Adjacency
43.6
49.6
100.0
36.8
35.6
83,8
ZERO SHRO-SHOT
Incident
48.6
85.0
88.0
Co-authorship Friendship
55.2
32.4
1.6
50.8
0.2
SP
49.2
49.8
30.8
6.6
83.2
GOT
51.0
52.6
70.6
34.8
6.2
83.2
Social Network
46.0
50.2
61.0
31.6
0
83.2
Politician
50.0
52.8
70.8
32.2
1.0
83.2
Expert
43.0
50,2
98.6
39.4
16.0
83.2
Overall
41.6
7.9
73.9
24.4
39.5
22.4
Adjacency
31.6
13.2
66.4
25.2
61.6
52.0
PERO-COT
Incident
52.0
54.8
75.0
9.8
84.4
55.2
Co-authorship
43.4
0.8
81.8
31.6
27.8
9.0
Friendship
46.0
0.6
80.2
26.2
20.4
8.4
SP
38.6
0
27.6
41.0
0.2
0.4
Social Network
28.2
Politician
51.4
1.2
29.2
17.2
11.6
Expert
24.8
0.2
9.6
45.0
57.4
Overall
41.5
55.8
60.3
35.9
46.1
73.8
Adjacency
49.2
61.0
97.6
43.2
66.4
78.4
FEW FEW-SHOT SHOT
Incident
73.2
82.4
99.2
37.4
85.6
78.4
Co-suthorship
16.4
51.4
45.4
32.2
36.8
73.6
Friendship
32.6
53.0
45.6
35.2
44.2
79.4
SP
33.2
45.6
40.6
35.2
30.6
57.8
GOT
30.0
48.6
41.6
38.2
36.0
61.4
Social Network
51.4
38.2
79.0
Politician
53.6
32.2
Expert
55.0
45.0
59.7
72.7
Adjacency
53.6
81.4
42.2
66.6
66.8
Incident
72.4
94.6
98.8
29.8
87.2
68.6
Co-authorship
42.4
55.0
45.0
33.8
37.0
69.4
COT
Friendship
55.0
48.8
45.0
33.4
40.8
80.6
SP
54.4
48.4
44.6
34,2
26.2
71.0
GOT
51.4
51.2
46.2
35.2
29.4
65.4
Social Network
42.8
51.4
43.6
32.4
39.8
77.0
Politician
36.8
53.0
50.4
33.0
30.2
76.8
Expert
60.8
53.2
35.8
49.6
78.6
Overall
60.4
60.0
63.1
34.6
45.0
69.2
Adjacency
64.6
78.0
64.2
Incident
95.4
32.2
COT-BAG
Co-authorship
$2.0
55.8
36.8
63.0
Friendship
64.8
49.6
32.6
36.4
71.8
SP
65.8
51.6
44.2
33.0
26.4
69.4
GOT
65.00
50.2
44.6
38.6
29.6
64.0
Social Network
48.4
53.6
46.4
31.2
45.6
72.0
Politician
50.4
53.0
$1.0
33.8
24.2
63.4
Expert
61.2
52.6
89.6
37.2
52.8
78.4
26


Reviews:
[{"review_id": "qgGSyqk07R", "reviewer": "Reviewer_PSY3", "summary": "This work presents the first comprehensive study on encoding graph-structured data as text for large language models (LLMs). Graphs are widely used to represent complex relationships in various applications, and reasoning on graphs is crucial for uncovering patterns and trends. The study reveals that LLM performance in graph reasoning tasks depends on three key factors: the graph encoding method, the nature of the graph task itself, and the structure of the graph considered. These findings provide valuable insights into strategies for improving LLM performance on graph reasoning tasks, with potential performance boosts ranging from 4.8% to 61.8%, depending on the specific task.", "questions": "See Weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* It is a valuable problem for encoding graph-structured data as text for LLMs.\n* Many factors are taken into considerations, and detailed analyses are provided. \n* The findings provide valuable insights into strategies for improving LLM performance on graph reasoning tasks.", "weaknesses": "1. One concern is about the experiment. The paper explores encoding graph-structured data as text for **LLMs**. However, only one type of LLM is compared (PaLM). It would be better to make comparisons with other LLMs, like GPT3/4 and Llama to make the findings more convincing.\n\n2. Another concern is about the novelty. The proposed graph encoder function g() in this paper is a mapping from graph space to textual space. Several previous paper [1-3] explores describing graph neighbors in natural language, and it would be better to tell the difference of this work. \n\n[1] Guo, Jiayan, Lun Du, and Hengyu Liu. \"GPT4Graph: Can Large Language Models Understand Graph Structured Data? An Empirical Evaluation and Benchmarking.\" arXiv preprint arXiv:2305.15066 (2023).\n\n[2] Chen, Zhikai, et al. \"Exploring the potential of large language models (llms) in learning on graphs.\" arXiv preprint arXiv:2307.03393 (2023).\n\n[3] Ye, Ruosong, et al. \"Natural language is all a graph needs.\" arXiv preprint arXiv:2308.07134 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "E1sFug9eat", "reviewer": "Reviewer_52xH", "summary": "This paper provides an extensive investigation into the capabilities of LLMs in understanding graph structure. The authors explore various factors such as the graph encoding function, prompting questions paradigm, relation encoding, model capacity, and reasoning in the presence of missing edges. The implications of these variables on LLM's graph reasoning and understanding abilities are also carefully examined. Moreover, the authors also investigate the implications of graph structure by randomly generating diverse graphs for evaluation and analyze the results from the impact of graph structure, distractive statements in graph encoding, and the selection of few-shot examples in few-shot learning. This work presents some interesting findings in graph encoding methods, the nature of graph tasks, and the graph structure. The paper yields intriguing findings concerning graph encoding methods, the nature of graph tasks, and the graph structure itself.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is overall well-written and well-organized, I enjoy reading it.\n2. The experiment results are extensive, making it a solid work.\n3. I like the analysis in bulletin list style, which helps readers to capture the most important information.\n4. There are some interesting findings in this paper.", "weaknesses": "1. In the introduction, the authors mention two limitations in the existing LLMs and one of them is difficulty in incorporating fresh information, but how could the graph structure data solve this problem? I would encourage authors to elaborate more on this statement.\n2. In section 3.5 experiment 5, the task description is too brief for readers to understand the experimental settings. What is specifically the \"disconnected nodes task\" and how to generate this data is not clear.\n3. The motivation for each experiment setting is not clear enough, I encourage authors to give their motivation in each experiment to help readers understand the necessity for the experiment.\n4. For simple tasks such as node degree, node count, edge count, etc. There are some efficient, accurate, and reliable algorithms to do that with programming, so why not just let LLMs write code for these tasks and execute the code to solve these problems? \n5. I believe the motivation of this work is not strong enough. Yes, there are graphs everywhere, and reasoning on graphs is essential, but why do we need LLMs to do reasoning on graphs? The LLMs are trained on unstructured textual data, making it hard to generalize to graph data. Moreover, we also have reliable and fast algorithms to solve these basic graph problems, so I believe LLMs might not be a good tool for these basic graph problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xykE9kudcU", "reviewer": "Reviewer_FDET", "summary": "The paper addresses the problem of reasoning on graphs with large language\nmodels (LLMs) and provides a comprehensive exploration of encoding graph-\nstructured data as text that can use LLMs. The paper claims that the LLM\nperformance in graph reasoning tasks varies on three crucial fronts: (1) the\nmethod used to encode the graph, (2) the nature of the graph task itself, and\n(3) the inherent structure of the graph. The paper has provided comprehensive\nexperiments on graph reasoning using LLMs by providing them with text prompts\nthat are constructed from the graphs. In these, the paper analyzes the effect of\na variety of graph-to-text encoding and question encoding functions as well as\ngraph structures on LLMs performance. Different methods such as Zero-shot,\nFew-shot, and Chain-of-Thought methods have been considered for prompting.\nTo analyze the impact of different graph structures on performance, the paper\nhas generated random graphs using previous approaches.", "questions": "It would be great if some of the points raised in the weakness section are addressed.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- The paper has provided detailed discussions of their results along with\nreasonable and meaningful conclusions.\n\n- The paper is also well-organized and easy to read.\n\n- The experiments are comprehensive as they include important factors\nthat can impact the performance of LLMs on graph reasoning. These\nare encoding the input graph to text, the structure of the input graph,\nrephrasing the question, complexity of the LLM, and prompting method.", "weaknesses": "- The graph, node, and edge encoding functions are simple and inefficient.\nThe paper could use more advanced and recent graph-to-text generation\ntechniques (i.e. [1]). Evaluating only the defined encoding methods cannot\nsupport the general claims about the power of LLMs in graph reasoning.\n\n\n- The proposed graph encoding approaches are similar i.e. the Friendship,\nPolitician, Social network, GOT, and SP all depict alternative ways of\nstating two nodes are “connected”. Therefore, evaluating them shows\nthe power of LLMs in interpreting the names rather than exhibiting their\nability to understand underlying relations and exploit neighborhoods within\na graph. This could have been considered in increasing the diversity of\nencoding functions.\n\n- It might be good to introduce previous random graph generation methods.\nAdding some detail of these methods (even in the appendix) can be helpful\nto understand how they are different.\n\n- The proposed benchmark tasks (except for edge existence) do not involve\nreasoning. They can be inferred without reasoning (by counting, simple arithmetic operations, and memorizing the graph structure). More\nchallenging tasks (e.g., node classification) can enrich the experiments.\n\n- In Experiment 2, authors compare question and application rephrasing\nmethods, while the difference between these two is not clear. Authors can\nadd a few examples of rephrasing a question with these methods in the\nmain body or appendix of their paper.\n\n[1] Yi Luan Mirella Lapata Rik Koncel-Kedziorski, Dhanush Bekal and Han-\nnaneh Hajishirzi. Text Generation from Knowledge Graphs with Graph\nTransformers. In NAACL, 2019.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yPVtn9xVCg", "reviewer": "Reviewer_SLdh", "summary": "This work proposes to understand the graph reasoning abilities of LLMs through a benchmark and experiments. Compared to existing works, this paper uniquely focuses on how to encode graph structures in natural language and different types of graphs, as well as their impact on model performance. Experiments demonstrate that the choice of natural language instantiation and graph structures indeed have an impact on LLMs' ability for graph reasoning.", "questions": "please see above", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+ reasoning on graphs with LLMs is an important research question\n+ the experiments are extensive", "weaknesses": "- Since the authors claim the GraphQA benchmark as a novel contribution, it would be great to include at least some description of the benchmark dataset in the main paper. How is the benchmark constructed? What are the hyperparameters in random graph generation? What are the statistics of GraphQA? A brief description of the benchmark in the main paper, accompanied by full details in the appendix, will best help readers understand the scale and validity of the study.\n\n- In equ(2), is it $\\max_{g}$ instead of $\\max_{g,Q}$?\n\n- It would be nice to have at least a one-sentence description of each graph task in section 3.1. In section 3.5, the *disconnected graph task* is mentioned but it is not introduced at the beginning of section 3.1.\n\n- Since one of the main arguments of this work is \"how to encode graphs in natural language affect performance\", it would be great to present Table 1 results aggregated by graph encoding functions. It would also be nice to provide hypotheses as to why certain encoding approaches are particularly bad for LLM performance.\n\n- I'm not sure about the uniqueness of some of the findings in this work. Experiments 1-4 in Section 3.1 basically prove two things: 1) LLMs are sensitive to variations in prompt, and 2) larger LMs are generally more capable. While these findings are well established in LLM research, the four experiments simply corroborate them in the graph reasoning domain. I wonder if the authors might have more interpretations of these results beyond those already established in general LLM research.\n\n- For section 4, I wonder if the authors conducted a control experiment, i.e. the only difference among problem subsets is the graph construction algorithm. What factors are specifically fixed in Section 4? It would also be great to provide hypotheses as to why LLMs are better/worse at handling certain graph types.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)