Investigating Instruction Tuning Large Language Models on Graphs
Authors: Kerui Zhu
Bo-Wei Huang
Bowen Jin
Yizhu Jiao
Ming Zhong
Kevin Chang
Shou-De Lin
Jiawei Han
Venue: COLM (2024)
Keywords: instruction tuning, graph understanding, dataset, graph representation
TL;DR: We investigate instruction tuning Large Language Models on graphs.

Abstract: Inspired by the recent advancements of Large Language Models (LLMs) in NLP tasks, there's growing interest in applying LLMs to graph-related tasks. This study delves into the capabilities of instruction-following LLMs for engaging with real-world graphs, aiming to offer empirical insights into how LLMs can effectively interact with graphs and generalize across graph tasks. We begin by constructing a dataset designed for instruction tuning, which comprises a diverse collection of 79 graph-related tasks from academic and e-commerce domains, featuring 44,240 training instances and 18,960 test samples. Utilizing this benchmark, our initial investigation focuses on identifying the optimal graph representation that serves as a conduit for LLMs to understand complex graph structures. Our findings indicate that JSON format for graph representation consistently outperforms natural language and code formats across various LLMs and graph types. Furthermore, we examine the key factors that influence the generalization abilities of instruction-tuned LLMs by evaluating their performance on both in-domain and out-of-domain graph tasks.

Published as a conference paper at COLM 2024
Investigating Instruction Tuning Large Language Models on Graphs
Kerui Zhu", Bo-Wei Huang", Bowen Jin"', Yizhu Jiao, Ming Zhong, Kevin Chang
Shou-De Lin, Jiawei Han University of Illinois at Urbana- -hhamaaaaa,,,,,,, National Taiwan University {keruiz2, boweiwh2, b
Abstract
Inspired by the recent advancements of Large Language Models (LLMs) in NLP tasks, there's growing interest in applying LLMs to graph-related tasks. This study delves into the capabilities of instruction-follooinn LLMs for engaging with real-world graphs, aiming offer empirical insights into how LLMs can effectively interact with graphs and generalize across graph tasks. We begin by constructing a dataset designed for instruction tuning, which comprises a diverse collection of 79 graph-related tasks from academic and e-commerce domains, featuring 44,240 training instances and 18,960 test samples. Utilizing this benchmark, our initial investigation focuses on identifying the optimal graph representation that serves as a conduit for LLMs to understand complex graph structures. Our findings in- dicate that JSON format for graph representation consistently outperforms natural language and code formats across various LLMs and graph types. Furthermore, we examine the key factors that influence the generalization abilities of instruction-turet LLMs by evaluating their performance on both in-domain and out-of-domain graph tasks.
Introduction
The success of Large language models (LLMs) in understanding and reasoning the semantic structure in natural language has brought a great interest in applying this capability to assist tasks with other modalities such as graphs. Graph stores information through the explicit connections between nodes and the attributes associated with the nodes and edges, which is quite different from natural language. To fill the gap between graph and LLM, Ye et al. (2023); Wang et al. (2024b); He & Hooi (2024); Luo et al. (2024) focus on instruction tuning LLM on linearized graph representations so that the LLM can learn the graph structure and solve graph-related tasks based on instructions. Results show that graph instruction-tuned LLMs outperform traditional Graph Neural Networks (GNNs) (Ye et al., 2023).
However, we notice a lack of fundamental study of the graph representation and deeper analysis of the iastree LLM's generalization ability over empirical graph tasks. For the graph representation, Chen et al. (2023); Zhao et al. (2023); Wang et al. (2024a) translate graphs into natural language, while Wang et al. (2024b) represents the graph in a code-like format. However, it is still unclear how the choice of graph representation would affect the efficiency of graph instruction tuning. For the generalization, the LLMs are expected to solve tasks with new requirements, new graph structure distribution, and even unseen algorithms. This is critical for a general graph problem solver due to the complexity and variety of graph-related problems. Guo et al. (2023) establish a benchmark with 10 tasks to assess the proficiency of LLMs in understanding graph data. In this work, we instruction-tune LLMs on graphs with more fine-grained tasks and comprehensively analyze their capability concerning generalization.
"The first three authors contribute equally.
I Code is available https: //gi thub.
1

---

Published as a conference paper at COLM 2024
Graph sample
Graph represeriation
Task Generalication
Amazon Netadata
JSON
Podge113
Perracettr "arobcttrrl "bras": "2000% "prstictio"s thalogsieee
Froducti,, Productis
Unosen Sub-Tack
Ratural berguge
Product1??
Braes?
prosaCTEs, pratet of brassi, producti is prodectts.
Uneean Coman Aestora, sathord
wrateruyy Peperot
0OT
Tapw?
prodact22 (anand) Tlabe bredact
2: Nov may stio bay neces dees Producti2 bave? A1
Unawer Amsoer Typm
Figure 1: Examples of graph representations and three levels of generalization.
To facilitate the analysis of generalization, build benchmark for graph instruction tuning consisting of 14 tasks with 7 categories. We further derive 79 sub-tasks from the 14 tasks and sample 63.2k question-graph pairs from academic and e-commerce networks.
In general, our work focuses on two research questions regarding graph instruction-tuning:
RQ1: What is the optimal graph representation that serves conduit for LLMs to learn graph structures effectively? For the first question, we experiment with three types of graph representation: natural language, structured text representation (JSON), and code (DOT). Figure 1 shows an example of each representation. We instruction-tune LLMs with each representation separately and evaluate their performance on our constructed benchmark. The result shows the JSON format offers the best performance across various LLMs and graph domains.
To what extent can LLMs fine-tuned on limited graph-related tasks generalize to unseen tasks? To further analyze the generalization of the graph instruction-tunce model, we propose three levels of generalization, namely Unseen Sub-Task, Unseen Domain, and Unseen Answer Type, where each level tests the LLM on scenario not seen during the training. Figure 1 shows an example question at each level. We conduct comprehensive experiments on the LLM's capability to the three levels of generalization. The result indi- cates that the LLM can generally be improved over wide range of graph-related tasks after a limited graph instruction tuning. However, the LLM may easily get overfitted on simple counting tasks and doesn't generalize well on inductive reasoning tasks like link prediction. In addition, our findings also reveal LLM capable of handling tasks requir- ing graph algorithms not seen during training, which indicates that graph instruction tuning enables LLM to derive new algorithms itself based on its understanding of the graph and the algorithms learned during training.
RQ2:
To summarize, our key contributions are threefold:
We create benchmark with fine finengraeedd tasks from two different domain networks, which allows a comprehensive study of the generalization problem.
We investigate the influence of different graph representations in graph instruction tuning, including natural language, JSON, and code. The result shows the JSON format gives the LLMs the best performance after tuning.
We propose three levels of generalization for graph-related tasks and conduct extensive experiments investigate the generalization of the instruction-tuned LLMs. Our experi- ments reveal tasks where LLM could be overfitted or hard to generalize. Our experiments also show LLM can derive algorithms from the learned algorithms.
2

---

Published as a conference paper at COLM 2024
2 Related Work
2.1 LLMs on Graphs
Inspired by the recent achievements of large language models (LLMs) in natural language processing tasks, researchers are investigating the use of LLMs for tackling graph-related tasks (Jin et al., 2023a). Existing works can be organized into two categories depending the functions of LLMs. The first category typically relies on LLMs to serve as pretrained feature extractors (Chien et al., 2021) for graph neural networks (GNNs) (Wu et al., 2020). For example, TextGNN (Zhu et al., 2021) proposes to conduct LLM text feature extraction before GNNs for sponsored search tasks. TAPE (He et al., 2023) adopts LLMs to generate augmented texts before feeding into medium-scale LMs and GNNs. The second category is graph-incorporated LLM architectures (Jin et al., 2023b). Specifically, GraphFormers (Yang et al., 2021) and Edgeformers (Jin et al., 2023c) propose weapheempowered language model architecture for homogeneous text-attributed graphs and textual-edge graphs respectively. Heterformer (Jin et al., 2023d) further introduces textless node encoding and proposes an architecture for heterogeneous text-attributed graphs. However, most existing works mainly focus on applying LLMs off-the-shelf encoders or exploring LLM architecture improvement for graphs. In our work, we investigate the problem of instruction tuning large language models on graphs.
2.2 Instruction Tuning for LLMs
Instruction tuning (Ouyang et al., 2022; Sanh et al., 2022) is crucial for the latest generation of LLMs to cater to explicit user commands. In this stage, LLMs are trained using datasets with specific instructions and the expected responses, which improves LLMs in understanding and reacting to various human queries in natural language. Instruction tuning can be seen as a form of meta-learning where the model learns to adapt using the instructions (Zhang et al., 2023a; Longpre et al., 2023). As a result, these models acquire zero-shot learning ability which emerges as natural interactions with users. Currently, this paradigm has already demonstrated its impressive effectiveness across a wide range of natural language tasks, such as coding generation (Luo et al., 2023), complex reasoning (Mukherjee et al., 2023), information extraction (Jiao et al., 2023), and creative writing (Li et al., 2023).
Inspired by the success of instruction tuning texts, recently increasing research interest has tried to enable LLMs to generate more accurate and contextually appropriate responses for graph-structured data. These works typically align the language capacity of LLMs with the nuances of graph learning tasks. Specifically, Ye et al. (2023) instruction tunes the LLMs to perform graph tasks with graph structure described in natural language through highly scalable prompts. Wang et al. (2024b) uses a code-like format to describe graph information. Luo al. (2024)
concurrent work closest to ours. instruction tunes LLM on homogeneous graphs and studies the generalization to the graph size, graph description languages, node ID representation, and out-of-domain tasks. In contrast, we instruction tunes L.MSs on heterogeneous graphs and design fine-grained sub-tasks to study the generalization. Besides, our work discusses the effect of graph representation on instruction tuning, which is not well-studied yet.
3 Instruction Tuning on Graph
3.1 Preliminaries
Formally, general graph can be represented as G - EV,E,Tv, Ty, (v. where V is the set of nodes, E C V x is the set of edges, Ty and TE are the sets of node types and edge types, and Φv V + Ty and &E E + TE are functions that map each node and edge to its respective type. To facilitate the expression of graph relationships, we introduce the notation N(v) to denote the set of neighbors of node P(u,, v) to represent the set of paths connecting nodes ı/ and v, Pu,v as a specific path between nodes u and v, and d(u, v) as the minimum number of edges on any path between nodes u and v.
3

---

Published as a conference paper at COLM 2024
3.2 Task Definition
The core of instruction tuning is to involve as diverse a range of tasks as possible to enhance the model's generalization capabilities across different tasks. Therefore, in the context of graphs, we collect various graph tasks with diverse challenges, spanning from structural analysis to predictive inference. To comprehensively assess LLM's capabilities in addressing graph tasks, we categorize tasks according to their target answer type. The answer type delineates the nature of the output required for a graph task. We identify seven distinct answer types: node, pair, count, boolean, path, graph and link prediction. Node task seeks to identify specific nodes within the graph. Pair task seeks identify node pairs connected by specific relationships or properties. Count task requires counting the number of certain nodes or paths. Boolean task provides a true/falss answer indicate the existence of specific structures. Path task necessitates finding a sequence of nodes that connect two specified nodes. Graph task demands extracting a subgraph represented as a set of node pairs. Link prediction task, different from previous answer types, aims to infer missing edges between nodes based on observed patterns of existing data.
For each answer type, design set of tasks, where each task requires specific graph algorithm. All the tasks are listed in Table 1, along with their category, mathematical description, and example. Furthermore, we subdivided each task into 2 to 4 sub-tasks, which share the same graph algorithm but focus on different node or edge types. For example, the Find neighhors task can be subdivided into sub-tasks like finding the brand of product and finding the " "also-view" product of product. These fine-grained sub-tasks could facilitate a more detailed analysis of generalization, which will be introduced in Section 3.3.
Answer Type
Task
Description
Examples
Find neighbors
{o Mai)ldr(a, TE)
What are the products of brand1?
Node
Nodes shared
(ultt, E Tj. 3w V, (a(w,)) (e(u,w) = 6))
What are the products that share "also_view" products with product1?
neighbbrrs
N-hop neighbors
(o]oy(0) Tp d(w,)) c=
What are the product nodes within 3- hop to productl1?
Find pairs
((.r e Ti. (or
What are the pairs connected by "also.view" edge and containing prod- uctll?
Pair
Pairs shared neighbors
FW C V (P AA =c)
Ve (E(p).))
What are the pairs that share 3 "also_buy" nodes?
Degree count
[VIIV ((O) to (.AE T.)
How many "also_view" nodes does product11 have?
Count
count within N-hop
(V'IV CV d(u,)) <-c)
How many brand nodes are within 3- hop producti1?
Path count
PT P(C.)IIVP E pen =
How many 3-hop simple paths exist be- tween product11 and product12?
Linked by edge
(p((we) e TE
Does a "vie" edge exist between product]l and product12?
Bool
Has path
(P(a,e) #0)
Does path exist between product1 and product12?
Find paths
(P' g P(u,o)]len(pa.)) - eu e P')
paths What the paths between prod-
Path
uctll and product12?
Shortest path
Whe E M(a
What are the shortest paths between productil and producti2?
min(ten(pw>)lp.. P(a,o)))
Graph
Ego graph
((m))2)) e Edd(m))
What egn graph with radius centered at product11?
(,d(1,))) <=c) (E'TT) (0,1)
Link Prediction
Link Prediction
Predict whether there is "also_view" edge between productll and prod- uct12.
Table 1: The overview of all tasks. T C TF, Tr S Tv and c E z are the edge types, node types, and number restrictions in the task.
4

---

Published as a conference paper at COLM 2024
3.3 Evaluation Splits
To assess the generalization capabilities of the fine-tuned LLM on graph tasks, we propose three distinct types of unseen tasks: unseen sub-tasks, unseen domain, and unseen answer type. Each unseen type offers unique insights into the LLM's ability to adapt and perform novel challenges beyond its training data.
Unseen sub-tasks evaluate the LLM's capacity apply similar graph algorithms to sub- tasks slightly different from the ones seen during training. For instance, a model may be trained find the shortest path between products and tested to find the shortest path between brands in an e-commerce network.
Unseen domain tasks evaluate the LLM's adaptability with graphs from out-of-domain networks, While the algorithms remain consistent with those learned during training, new node and edge types, and graph structures are introduced, testing the LLM's generalization across different domains.
Unseen answer type tasks push the boundaries of the LLM's capabilities by requiring to generate answer types not encountered during training. Evaluating the model on these tasks assesses its capacity to innovate and extrapolate beyond its training data to develop new graph algorithms.
Generally, these three evaluation types collectively provide a comprehensive assessment of the LLM's generalization abilities across various dimensions of unseen tasks, which may bring useful insights into graph instruction tuning.
3.4 Data Collection
In this section, we outline the strategies and pipelines used to collect our dataset.
Graph Sampling. Given the impractical size of the original network against LLMs' limited context, we sample subgraphs from the original network and task LLMs over the subgraphs. To generate a subgraph, we sample an ego graph with a radius of 2, centered around designated set of nodes. However, it's imperative to note that the number of nodes grows exponentially with each increment in hop count. Thus, we implement edge downsampling at each step. This downsampling process involves imposing maximum limit on the number of edges for each type or establishing ratio for downsampling, Different downsampling strategies can yield different graph structure distributions, which is useful for cross-domain generalization analysis.
Node De-identification. Given our objective of assessing LLMs' capacity for reasoning graph structures, textual information such as node names or titles becomes extraneous. To mitigate the potential influence of such textual data, we opt to de-identify nodes by representing them solely with their node type and unique ID. For instance, product in an e-commerce network might be denoted as "product11".
Question-Graph Collection. Each sample in our dataset contains a question as input and graph as the context. Given that link prediction necessitates inductive reasoning, while the other answer types involve structure-based queries, distinct pipelines are developed to generate question-graph pairs.
For link prediction, we initiate by randomly sampling positive and negative samples in the form of (head, relation, tail) triples. Then, to augment the local structural understanding of the head and tail nodes, we sample a subgraph centered at each of these nodes.
Conversely, for the structure-based query tasks, we start by selecting two random nodes from the original graph and subsequently sampling subgraphs. Task-specific requirements dictate the identification of nodes within the subgraph that may harbor answer, and graph algorithms are applied accordingly to uncover these answers. It is noteworthy that since the subgraph is sampled without considering the specific task, the resultant graph structure
5

---

Published as a conference paper at COLM 2024
remains independent of the task. Consequently, this approach facilitates the unbiased learning general graph algorithms, irrespective of the graph's structural characteristics.
3.5 Graph Representation
Choosing the appropriate format for prompts is essential when utilizing LLMs, as it signifi- cantly affects the model's capacity to accurately interpret and process the information. We explore three primary prompt types: natural language, JSON, and DOT format.
Natural language prompts are versatile and intuitive for LLMs, offering a broad range of applications due to their human-like conversational style. Meanwhile, the JSON format for adjacency lists offers a structured, efficient means of information representation, aligning with LLMs' systematic processing capabilities for precise tasks. Additionally, the DOT format, a standard graph description language (code), enables a visual depiction of network relationships, beneficial for analyzing complex connections. We will delve deeper into their implications for LLM performance in Section 4.
3.6 Graph Instruction Tuning
To graph instruction tune the LLMs, concatenate each sample's question Xq with its graph representation Xg to form the prompt and train the LLM to predict the answer Y based on the prompt. We follow the implementation of Wang et al. (2023) to use the original auto-regressive training objective and mask the prompt tokens from loss computation. The loss function
=
Σ log HogpolyilXpp Xg. Yei)
loog
where y; is the ith token in the Y.
Experiments
Node
# Edge
Training size
Testing size
#SbbTask
# Avg Nodes
# Aug Edges
Amazon MetaData
2.07 m
16.3 m
22.4
9.6 k
40
87.14
111.63
21
Table 2: Dataset statistics
4.1
Experiment Settings
4.1.1 Datasets
We construct two separate domain graphs from two distinct datasets:
Amazon Metadata (Ni et al., 2019) contains product metadata across 29 general categories on Amazon. We extract products, brands, and categories as nodes, connecting them via attributes "also balso.byy", "also view", "brand", and "category". The graphs are built using metadata from the lis_an__imya Movies_and TV, and Arts. ArtssCrafts_r and SewwiinnndSSewwnnggggg categories.
MAPLE (Zhang et al., 2023b) is derived from the Microsoft Academic Graph, featuring 19 scientific fields. We extract the authors, papers, and venues nodes, and created edges using the "citation", "authorship", and "publication" relationships. This graph utilizes subjects Political Science, Computer Science, and Geology from this dataset.
We collect 800 samples for each sub-task and divide them into training and test sets with ratio of 7:1. The statistics of the collected graphs and datasets presented in Table 2.

---

Published as a conference paper at COLM 2024
4.1.2 Models and Training
Models We perform graph instruction tuning with the Llama-2 7B (Touvron et al., 2023), Mistral 7B (Jiang et al., 2023), and Gemma 7B (Team et al., 2024) models and compared them with their instruction-tuned versions, which are not explicitly tailored to process structural information, to illustrate the benefits of our special graph instruction tuning.
Fine-tuning We employ LoRA (Hu et al., 2021) as our parameter-efficient fine-tuning approach. To ensure all models can access complete graph information, we train and test all models using samples that could fit within Llama-2's 4k context window. To assess the LLM's generalization
unseen sub-tasks and unseen domains, we train the models on part of the sub-tasks for each task, leaving the rest as the unseen sub-tasks. We also train the models on each domain separately, leaving the other domain as the unseen domain. We conduct separate training for the evaluation of unseen answer types.
4.1.3 Metrics
In our experiments, we evaluate performance using two key metrics, the Exact Match (EM) and the F1 score. Specifically, we use EM for the Count, Boolean, and Link prediction tasks, and Fl for the Node, Pair, Path, and Graph tasks. For the Path task, treat each path as single value and calculate the F1 score between the extracted and the ground truth paths.
4.2 Results
Amazon
Maple
Avg Tokens
# Nodes
Edges
Avg Tokens
# Nodes
# Edges
NT. JSON
1869.56
226
324
1033.61
280
326
1972.44
199
289
1161.03
277
321
DOT
2011.01
192
288
1181.22
277
321
Table 3: Statistics of different graph representations in 4k context
Amazon
Maple
Node Pair Count Bool Path Graph
AVG Node
Pair Count Bool
Path Graph
LP AVG
Baselines
Llama Jlama-2-chaty
1.97
2,08
0.00
62.83
15.39
10:98
41.79
12.91
2.85
3.26
0.16
58.91
16.21
18.96
47.33
14.56
Llama-2-chatysu
2.16
2.04
0.00
62.85
3.87
7.78
11.79
11.48
4.12
1.90
0.00
58.91
8.32
10.68
47.35
12.98
2.48
1.66
62.83
1.56
12.78
41.79
11.78
2.31
2.34
0.00
58.91
4.42
22.16
47.33
13.36
Mistral-Instw.
0.03
15.04
Mistral-Instyson
2.91
8.38
12.43
37.30
12.29
8,86
58.21
14.75
4.24
10.81
14.45
41.09
9.74
7.74
52.67
15.77
Mistral-Instpor
1.65
5.28
37.17
18.43
12.50
58.21
14.02
3.07
4.85
12.41
41.09
23.34
9.72
52.66
15.74
Gemma-Instyu
13,85
25.19
2.59
65.92
34,64
28.85
44.96
24.42
15.17
29.95
3.53
72.75
34.65
23.03
48.72
26.35
Gemma-Inst;aov
15.50
26.54
65.14
30.00
45
36.00
24.74
8.51
26.45
8.42
65.61
29.32
22.19
45.39
23.50
Gemma-Instoer
16.83
35.91
4.06
64.76
31.19
37.69
60.33
28.72
18.17
34.76
2.38
64.99
29.22
36.98
42. 86
27.25
Finetuned
Llama Maaap---rrph
74.34
65.97
45.76
93.57
95.16
64.83
85.47
67.26
73.28
67.78
44.05
96.13
53.65
77.
67.07
666.7
Llama-2- Mamaa-2-rrpplnnstyggn
80.20
68.49
46.48
96.48
52.75
65.39
85.02
69.46
75.33
68.42
46.62
98.11
55.21
80.06
64.42
68.30
64.26
50.07
64.69
70.59
63.69
47.32
69.06
665.6
Mistral-Graphhnsst..
87.43
75.38
48.47
98.13
66.55
80.09
75.23
75.16
86.17
76.39
48.86
97.80
68.55
86.14
76.97
75.69
Mistral Distral-Graphlnstsssx
89.63
81.18
50.77
98.73
62.16
83.32
76.15
77.11
82.96
79.58
50.94
99.16
68.61
84.13
75.95
75.64
Mistral- Saatral-rmphhnstporr
86.30
72.91
46.24
96.97
68.71
81.01
77.98
74.44
79.01
74.96
50.74
98.95
66.47
85.69
79.02
74.03
Gemma Grama--Gapllnsty..
87.34
76.30
46.51
97.36
68.06
77.31
85.17
75.43
88.90
74.76
47.84
97.49
61.50
86.04
77.53
75.20
Gemma Gamma-Graphhnsttson
78.11
99.23
65.68
78.08
76.98
86.50
75.33
51.74
83.15
70.91
75.50
Gemma-Graphinstzor
87.43 78.09
47.96
96.36
67 43
83.50
83.94
76.37
85.75
74.00
50.14
98.43
68.14
88.71
70.77
73.29
Table 4: Experimental results of three graph representations, including natural languages (NL), JSON, and DOT.
7

---

Published as a conference paper at COLM 2024
4.2.1 Graph Representation
Scalability Table presents the average length in tokens and the maximum graph size in 4k context concerning node and edge number for each of the three graph representations, natural language (NL), JSON, and DOT, in the two datasets. It shown that natural language has the most compact representation and can handle the largest graph in limited context budget.
Performance Table 4 presents the performance of both vanilla LLMs and graph instruction- tuned LLMs on the test sets of two datasets. The results reveal notable improvements in all tasks when comparing the graph instruction-tuned models with their text instruction-tunee counterparts. This suggests that the LLMs fine-tuned on our benchmark exhibit an enhanced understanding of graph structures, leading to improved reasoning capabilities for answering questions. Notably, the graph representations in JSON format consistently outperform those in other formats across various tasks, yielding the best overall performance for all three models.
Furthermore, we conduct studies to compare how differ- ent graph representations perform with different scales of LLMs. Concretely, we instruction-tume both Llama- 2-7b and Llama-2-13b on the Amazon dataset with the three graph representations. As illustrated in Figure 2, the observation is in line with our previous finding that JSON format is the best bridge for LLMs interacting with graphs and can yield the best performance both scales.
Graph Represenbation
We postulate that this superiority of JSON representations stems from their clearer structural depiction compared to natural language. Moreover, JSON is more prevalent format in the pre-training data compared DOT. Conse- quently, models trained with graph instruct-tune tend to find JSON particularly effective in comprehending and reasoning about complex graph structures.
Llam- Ulww-3-Grpphuur-- Scale
Figure 2: Compare LLMs of dif- ferent scales using three graph representations.
Given the consistently strong performance associated with the use of JSON format, our analysis in the following sections focuses primarily models trained with JSON format.
4.2.2 Sub-task Generalization
Maple
100
Llama Grephpus
1.00
Seen
Ussees
1.00
Gemma Gamea- Graphinst
Answer type
Anewer type
Figure 3: Experiment results of sub-task generalization on two datasets.
As mentioned in Section 3.3, show the performance of models over the in-domain seen and unseen sub-tasks under each answer type. In Figure 3, all models present an excellent generalization the unseen sub-tasks of Node, Pair, Bool, and Graph tasks, with small
8

---

Published as a conference paper at COLM 2024
drop in the performance, but fail to generalize to the unseen sub-tasks of Count, Path, and Link prediction tasks. We examine the failure cases and conclude the following reasons for the failure of these three types.
For the Count task, the greatest performance drops occur in sub-tasks of Degree count, which require only single-hop information of the queried node. Compared to the sub-tasks of Find neighbors, which also requires only single-hop information but returns a set of nodes, the Count answer type is more abstract, and thus, overfits the model to the seen sub-tasks. For the Path task, the most significant cause of failure in unseen sub-tasks is the incorrect starting nodes in the generated paths. For example, for the Llama-2 model trained on the MAPLE dataset, around 77.12% of the generated paths fail to start with the queried source node and 71.46% of the failure cases start with the paper node, which is the source node type in the seen sub-tasks. Our manual checking confirms that the model can still generate partially correct paths the unseen sub-tasks, indicating that the model does learn the path-finding algorithm, but fails due to the overfit in the starting node. For the link prediction task, this failure makes sense because the model only trained to infer the existence of a subset of edge types, while different edge types may be inferred from different graph patterns, the model fails to generalize this inductive reasoning to the unseen edge types.
4.2.3 Domain Generalization
Llama-2-Graphinst
Gistral-Graphinst
Gamma-Graphlnst
71.81
$7.38
78.84
69.46 61.17
19.3
Training Domain
Amazon
Mapls
59.8
Test Domain
Test Domain
Demain
Figure 4: Compare LLMs of different scales on domain generalization.
To evaluate the domain generalization of the instruction-tuned model, we compare the models separately trained on the two datasets by their performance on the unseen sub- tasks of both in-domain and out-of-domain datasets. This approach allows us to assess their performance on unseen tasks in cross-domain scenarios. Figure 4 demonstrates the averaged performance of all unseen sub-tasks the corresponding dataset except for the link prediction due to the conclusion from Section 4.2.2. In most scenarios, the model trained on a different domain has an acceptable performance drop compared to the model trained on the tested domain. In addition, the models trained on the Amazon Metadata network have a smaller performance drop (6.43% for Llama-2, 1.41% % for Mistral and -0.49% for Gemma) than the models trained on the Maple network (10.62% for Llama-2, 3.67% for Mistral and 4.53% for Gemma). According to the statistics in Table 2, the subgraphs from the Amazon Metadata network are generally larger than the subgraphs from the Maple network. This may indicate that training on larger graphs can better generalize the model to smaller out-of-domain graphs.
4.2.4 Answer type Generalization
In Table 5, we aim to assess the capacity of instruction-tunnd LLMs for generalizing across different answer types. As highlighted in Section 3.3, this represents a particularly chal- lenging scenario due to the potentially large discrepancy between the training tasks and the testing tasks. To this end, we specifically exclude Pair, Bool and Graph from the training dataset, and subsequently instruction-tur -uune the LLM Mistral- Siiiral--Gaahllnt-mmmsssss
Regarding the results, Misstra-Graphllst-mmne masked indicates compromised performance on the unseen Pair, Bool, and Graph tasks, a direct consequence of their absence during training. Despite this, it still manages to surpass Mistral-Inst, which is not fine-tuned with graph structures, in terms of performance. The findings suggest that our instruction design

---

Published as a conference paper at COLM 2024
effectively enables the LLM to grasp structural information and apply it to successfully tackle questions beyond its initial training scope.
Amazon
Node
Pair'
Count
Bool'
Path
Graph
Mistral-Insfpsey
2.91
8.38
12.43
37.30
12.29
8.86
Mistral-Grraphlnssgggoo
89.63
81.18
50.77
98.73
62.16
83.32
Mistral Sratia--raaaiin-n-ssseeeeeee
88.09
90.18
Maple
Mistral-Instiaon
4.24
10.81
14.45
41.09
9.74
7.74
Mistral-Graphhnnstssxx
82.96
79.58
50.94
99.16
68.61
84.13
Mistral-Graphlnn---msskeee
79.70
40.90
50.48
77.15
64.30
36.64
Table 5: Answer Type Generalization, where tasks Pair, Bool and Graph are unseen when
training Mistral Mhitral-Graphhnst-maaee
4.2.5 Case Study
bowdl: proact) compunt prskstt aapaasii (oanl)) podactts craporet producto aakges
potte brtwdrr ctegs your grap
Yoiden redid caggu expaodecc quiin grgg
hamea
Grapk
g
Oonduct Palo, (wrokurog "arcuct [haan)7) "akerg beoketir (nakedo lnckustin
Jenel?: produrt casganyl produc30 casgesad
lad Snnducett Teooud (aaraan
Hpp Phomot
Ciic Prosuate" yeodccor "posed.s (bwad5r) bekrajk
[pokkiorts "pocudar: (arckei (bradd0)) be heoggss PolageyAr
Faceeitic Them ooe yam kenwoe boucti
[odppeet: "akkgasd Toon (1i9, Juy" (rreeatte "poewiif"
Figure 5: Case study on finding the shortest path between two non-product nodes in the Amazon dataset, depicted through graph in JSON format.
To demonstrate the effectiveness of graph-based instruction tuning, we explore the model's effectiveness in identifying the shortest path between two non-product nodes within an undirected graph from the Amazon dataset. This task highlights the significant challenges faced by LLMs, including the need to comprehend complex graph structures and apply graph theory algorithms within a computational environment that requires processing large amounts of data and evaluating many pathways at once.
As depicted in Figure 5, W-MMMMil-Graapie Mistrul-Graphhiss, with its specialized tuning for graph dataset analy- sis, can better overcome these challenges by bridging the gap between natural language and computational graph theory. Unlike Mistral-Instruct mainly optimized for broad language tasks, Mistral-Graphlnss is adept at navigating the intricacies of graph structures, enabling it to perform sophisticated analyses like shortest path discovery with higher precision and efficiency. Despite still occasionally missing few shortest paths, Mistral-Graphunnst capability of handling complex network dynamics positions it as a superior tool for tasks demanding in-depth exploration of graphs, thereby advancing our ability interpret and analyze complex data structures.
Conclusion
In this paper, we investigate instruction-tuning LLMs on graph-related tasks. We first construct a dataset that contains comprehensive graph-related tasks from the academic and e-commerce domains. We then conduct extensive experiments to explore the best representation for LLMs to understand graphs and gain insights into the generalization of graph instruction-tunele LLMs to different kinds of unseen tasks. Future studies can consider applying such instruction-tuning techniques to graphs from other domains.
10

---

Published as a conference paper at COLM 2024
Acknowledgments
The research was supported in part by US DARPA KAIROS Program No. FA8750-19-2-1004 and INCAS Program No. HR001121Č0165, National Science Foundation IIS-19-56151, and the Molecule Maker Lab Institute: An Al Research Institutes program supported by NSF under Award No. 2019897, and the Institute for Geospatial Understanding through an Integrative Discovery Environment (I-GUIDE) by NSF under Award No. 2118329. Any opinions, findings, and conclusions recommendations expressed herein are those of the authors and do not necessarily represent the views, either expressed or implied, of DARPA or the U.S. Government.
References
Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Haifang Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, and Jiliing Tang. Exploring the potential of large language models (IIms) in learning on graphs. ArXie, abs/ 22/22300033333 2023. URL https: //api. semanti semanticscholar ccschllar...... org/ Brrg/CorpssI:: CorpusID:2593778224 259375824.
Eli Chien, Wei-Cheng Chang, Cho-Jui Hsieh, Hsiang-Fu Yu, Jiong Zhang, Olgica Milenkovic, and Inderjit S Dhillon. Node feature extraction by self-supervised multi-scale neighbor- hood prediction. ar Xio preprint ar XrX::22111.0000 2021.
Jiayan Guo, Lun Du, and Hengyu Liu. Gpt4graph: Can large language models under- stand graph structured data? an empirical evaluation and benchmarking. arXiv preprint arXiv:2305.1500 1.00.. 2023.
Xiaoxin He, Xavier Bresson, Thomas Laurent, Adam Perold, Yann LeCun, and Bryan Hooi. Harnessing explanations: LIm-to-lm interpreter for enhanced text-attributed graph representation learning. In The Twelfth International Conference on Learning Representations, 2023.
Yufei He and Bryan Hooi. Unigraph: Learning cross-domain graph foundation model from natural language. arXiv preprint ar arXio:2402.13630, 2024.
J. Edward Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. ArXiv, abs/ Abb/2210.09685, 2021. URL https://api. www.ppiscsaaatntslll.l.....
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. Xiv preprint ar Xri::2230006625,, 2023.
Yizhu Jiao, Ming Zhong, Sha Li, Ruining Zhao, Siru Ouyang, Heng Ji, and Jiawei Han. Instruct and extract: Instruction tuning for on-demand information extraction. In Pro- ceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 10030-10051, 2023.
Bowen Jin, Gang Liu, Chi Han, Meng Jiang, Heng Ji, and Jiawei Han. Large language models on graphs: A comprehensive survey. ari preprint arXio:2312.02783 2023a.
Bowen Jin, Wentao Zhang, Yu Zhang, Yu Meng, Xinyang Zhang, Qi Zhu, and Jiawei Han. Patton: Language model pretraining on text-rich networks. ar Xrv preprint arXiv:2305.12268, 2023b.
Bowen Jin, Yu Zhang, Yu Meng, and Jiawei Han. Edgeformers: Graph-empowered transformers for representation learning textual-edge networks. arXio preprint ar arXit:2302.11050, 2023c.
Bowen Jin, Yu Zhang, Qi Zhu, and Jiawei Han. Heterformer: Transformer-basedd deep node representation learning on heterogeneous text-rich networks. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 1020-1031, 2023d.
11

---

Published as a conference paper at COLM 2024
Yuanzhi Li, Sébastien Bubeck, Ronen Eldan, Allie Del Giorno, Suriya Gunasekar, and Yin Tat Lee. Textbooks are all you need ii: phi-1.5 technical report. arXiv preprint (xXv:2309.054633 2023.
Shayne Longpre, Le Hou, Tu Vu, Albert Webson, Hyung Won Chung, Yi Tay, Denny Zhou, Quoe V Le, Barret Zoph, Jason Wei, et al. The flan collection: designing data and methods for effective instruction tuning. In Proceedings of the 40th International Conference on Machine Learning, pp. 22631-22648, 2023.
Zihan Luo, Xiran Song, Hong Huang, Jianxun Lian, Chenhao Zhang, Jinqi Jiang, Xing Xie, and Hai Jin. Graphinstruct: Empowering large language models with graph understand- ing and reasoning capability, Xiv preprint ar arXiv:2403.04483 2024.
Ziyang Luo, Can Xu, Pu Zhao, Qingfeng Sun, Xiubo Geng, Wenxiang Hu, Chongyang Tao, Jing Ma, Qingwei Lin, and Daxin Jiang. Wizardcoder: Empowering code large language models with evol-instruct. In The Twelfth International Conference on Learning Representations, 2023.
Subhabrata Mukherjee, Arindam Mitra, Ganesh Jawahar, Sahaj Agarwal, Hamid Palangi, and Ahmed Awadallah. Orca: Progressive learning from complex explanation traces of gpt-4. arviv preprint arXio:2306.02707, 2023.
Jianmo Ni, Jiacheng Li, and Julian McAuley. Justifying recommendations using distantly- labeled reviews and fine-grained aspects. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)), pp. 188-197, Hong Kong, China, November 2019. Association for Computational Linguistics. doi: 10.18653/v1 /v//////11111111 URL https: wrwpaanthooooy.og/0011----- 1018.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul E. Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. In NeurIPS, 2022. URL http://papers nips. wctppper..ppppppccecp -wwe--aatt-toteeeeeaeeeee html.
Victor Sanh, Albert Webson, Colin Raffel, Stephen H. Bach, Lintang Sutawika, Zaid Alyafeai, Antoine Chaffin, Arnaud Stiegler, Arun Raja, Manan Dey, M Saiful Bari, Canwen Xu, Urmish Thakker, Shanya Sharma Sharma, Eliza Szczechla, Taewoon Kim, Gunjan Chh- ablani, Nihal V. Nayak, Debajyoti Datta, Jonathan Chang, Mike Tian-Jian Jiang, Han Wang, Matteo Manica, Sheng Shen, Zheng Xin Yong, Harshit Pandey, Rachel Bawden, Thomas Wang, Trishala Neeraj, Jos Rozen, Abheesht Sharma, Andrea Santilli, Thibault Févry, Ja- son Alan Fries, Ryan Teehan, Teven Le Scao, Stella Biderman, Leo Gao, Thomas Wolf, and Alexander M. Rush. Multitask prompted training enables zero-shot task generalization. In The Tenth International Conference Learning Representattons, ICLR 2022, Virtual Event, April 25-29, 2022. OpenKeview.net, 2022. URL httpps://opeereeeeeee
net/forum? wtt.forrmmiiioobbseee......
Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, et al. Gemma: Open models based on gemini research and technology. arXiv preprint drXiv:2403.08295, 2024.
Hugo Touvron, Louis Martin, Kevin R. Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Daniel M. Bikel, Lukas Blecher, Cristian Cantón Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony S. Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel M. Kloumann, A. V. Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, R. Subramanian, Xia Tan, Binh Tang, Ross Taylor,
12

---

Published as a conference paper at COLM 2024
Adina Williams, Jian Xiang Kuan, Puxin Xu, Zhengxu Yan, lliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models. ArXiv, abs/ 2222230099928 2023. URL pottps://app semanticscholas .org/ org/CorppsID. 259950998.
Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language? Advances in Neural Information Processing Systems, 36, 2024a.
Jianing Wang, Junda Wu, Yupeng Hou, Yao Liu, Ming Gao, and Julian McAuley. In- structgraph: Boosting large language models via graph-centric instruction tuning and preference alignment. arviv preprint ar Xxx::24022.08785 2024b.
Yizhong Wang, Hamish Ivison, Pradeep Dasigi, Jack Hessel, Tushar Khot, Khyathi Raghavi Chandu, David Wadden, Kelsey MacMillan, Noah A. Smith, Iz Beltagy, and Hannaneh Hajishirzi. How far can camels go? exploring the state of instruction tuning on open resources, 2023.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4-24, 2020.
Junhan Yang, Zheng Liu, Shitao Xiao, Chaozhuo Li, Defu Lian, Sanjay Agrawal, Amit Singh, Guangzhong Sun, and Xing Xie. Graphformers: Gnn-nested transformers for representation learning on textual graph. Advances in Neural Information Processing Systems, 34:28798-28811 2021.
Ruosong Ye, Caiqi Zhang, Runhui Wang, Shuyuan Xu, and Yongfeng Zhang. Natu- ral language is all graph needs. ArXiv, 0bs/2238.07111 2023. URL https://api.
semanticscholar. wwwa..org/oorrooo Crrg/CorpusID::000 26088732..
Shengyu Zhang, Linfeng Dong, Xiaoya Li, Sen Zhang, Xiaofei Sun, Shuhe Wang, Jiwei Li, Runyi Hu, Tianwei Zhang, Fei Wu, et al. Instruction tuning for large language models: A survey. Xrviv preprint ar arXiv:2308.10792 2023a.
Yu Zhang, Bowen Jin, Qi Zhu, Yu Meng, and Jiawei Han. The effect of metadata on scientific literature tagging: A cross-field cross-model study. In Proceedings of the ACM Web Conference 2023, pp. 1626-1637, 2023b.
Jianan Zhao, Le Zhuo, Yikang Shen, Meng Qu, Kai Liu, Michael Bronstein, Zhaocheng Zhu, and Jian Tang. Graphtext: Graph reasoning in text space. ar Xiv preprint arXiv:2310001089, 2023.
Jason Zhu, Yanling Cui, Yuming Liu, Hao Sun, Xue Li, Markus Pelger, Tianqi Yang, Liangjie Zhang, Ruofei Zhang, and Huasha Zhao. Textgnn: Improving text encoder via graph neural network in sponsored search. In Proceedings of the Web Conference 2021, pp. 2848- 2857, 2021.
13


Reviews:
[{"review_id": "KMZHkZ2eFb", "reviewer": "Reviewer_172j", "summary": "Authors propose a new dataset of graphs with associated tasks to answer given a graph representation. Authors use LORA to adapt LLM to enhance its understanding of the graphs. Graphs represented by one of three formats.\n\nAuthors conclude that JSON is the best format with advnatage for adapted LLMs in performance.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Reasons To Reject:\n1. Using a graph encoder to generate the graph representation is an interesting and novel approach. However, currently, there are many works still using the rule-based linearization approach, which can directly make use of the knowledge in the popular decoder-only LLM. Therefore, one of our goals in the paper is to provide insights into how different rule-based graph representations will affect the performance under the setting of graph instruction tuning so that it may help other researchers when choosing their graph representation.\n2. Maybe this is not a drawback? Since LLM can be easily adapted to specific tasks with a few thousand training examples, a small and diverse dataset may be appropriate to study the generalization of LLM in graph-related problems.\n\nQuestions To Authors:\n1. Yes, we do have a few queries written in natural language. For example, when asking for the products of a brand, the query is formulated as “What are the products of brandxxx?”. We mostly use the edge types because we can use some templates to generate different sub-tasks that share the same graph algorithm but focus on different node types or edge types. \n1. This is an interesting direction to explore! However, we didn’t allow this. We test the LLM’s understanding of graph and graph algorithm by evaluating how well it can generate correct answers for any graph-related query so that we can decide whether LLM can be trusted as an independent graph problem solver. Therefore, we didn’t consider the approach of scoring over the possible outcomes. Since this may involve changing the dataset, we may not be able to test this during the rebuttal, but we may consider this as a future work.", "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": "(1) Understanding strcutured data within the context of LLMs is quite important with wide set of applications\n\n(2) Authors propose a useful dataset that will help other researchers studying the problem.", "reasons_to_reject": "(1) Graph representation approaches proposed are all rule based, it would have been great to propose a learnable approach to graph such as an encoder based representation.\n\n(2) The datasets are small and diverse enough.", "questions_to_authors": "(1) Could you have written the queries in natural language, is there a need to use phrases such as 'also_buy' or 'product_of'?\n\n(2) Was the LLM allowed to generate tokens that are out of the possible set of answers? For example, if the task is counting, could the LLM generate an answer than is not in digits? Could you have tested the performance of the LLM scoring the possible outcomes instead of generating novel responses?\n\n\n(3)", "extra_scores": {}}, {"review_id": "DTuyyEhcsL", "reviewer": "Reviewer_zHpC", "summary": "This paper presents a benchmark to evaluate the ability of large language models (LLM) in understanding graph structures. This benchmark contrains a diverse collection of 79 graph-related tasks from academic and e-commerce domains, featuring 44,240 training instances and 18,960 test samples. Besides the benchmark, the author also study the impact of different graph representations in affecting the performance of LLM and find that JSON is a better choice. In addition to that, the author also study how LLM can generalize to unseen examples.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Reasons To Reject:\n1. Thank you for your suggestion! We agree that there are many networks from domains like chemistry and biology, which can make the benchmark more diverse and raise more general interests. Since one of our research questions is “To what extent can LLMs fine-tuned on limited graph-related tasks generalize to unseen tasks?”, the graph-related tasks can be “limited” for limited queried information (only a few node types and edge types) or limited graph structure distribution (a few distinct domains). This is why we choose the Amazon Metadata and MAPLE, where both contain 3 to 4 common node and edge types and have different graph structure distributions against each other. We will try to include more networks in our dataset if they satisfy these requirements.\n\n2. We may have different ideas at this point. Our benchmark is built for two purposes: first, to find the optimal graph representation that helps LLMs learn graph structures effectively; second: to analyze the generalization capability of LLMs fine-tuned on limited graph-related tasks to unseen tasks. These are the novelty of our work.\n\nQuestions To Authors:\n1. Yes, we have recently conducted some experiments with another LLM, Google’s Gemma-7b. The current results on the Amazon Metadata network also support our following observation in the paper: JSON format gives the LLMs the best performance after tuning. The model presents an excellent generalization on the unseen sub-tasks of Node, Pair, Bool, and Graph tasks, with a small drop in the performance, but fails to generalize to the unseen sub-tasks of Count, Path, and Link prediction tasks. More models and results will be added to the final version of the paper.\n\n2. Our technique contributions are:\n+ We create a benchmark for investigating the influence of different graph representations in graph instruction tuning and the generalization capability of the LLM instruction tuned on limited graph-related tasks.\n+ Our result shows the JSON format gives the LLMs the best performance after tuning.\n+ Our experiments on generalization reveal tasks where LLM could be overfitted or hard to generalize. Our experiments also show LLM can derive algorithms from the learned algorithms.\n\n3. We think the small models could be fine-tuned to each specific task with a specific network but is hard to generalize to a different task. On the other hand, LLM with strong capability in reasoning and understanding, can generalize better in unseen tasks.", "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": "1. Present a solid benchmark containing a diverse collection of 79 graph-related tasks from academic and e-commerce domains, featuring 44,240 training instances and 18,960 test samples.\n\n2. The paper is good written and easy to follow. Every detail is presented clearly and reading friendly for unfamiliar readers. \n\n3. The analysis about different graph representations and the ability on unseen examples gives new insights.", "reasons_to_reject": "1. The proposed benchmark only consider network data in academy and e-commerce and ignore widely used graph data in the domain of chemistry and biology.\n\n2. About novelty. This is not a brand new benchmark. Many previous works has already considered the ability of LLM in understanding graph structures. For example \n\n3. The paper only evaluates the ability of Llama2 and Mistral, which is hard to cover all representive LLMs.\n\n4. Limited technique contribution. This paper only gives evaluation results and insights and the technique used here on how to integrate LLM and graph follows previous methods.", "questions_to_authors": "1. Can you compare more LLMs beyond Llama 2 and Mistral?\n\n2. Can you elaborate on the technique contribution?\n\n3. What is the gap between small models on graphs and LLM in understanding graph structure?", "extra_scores": {"ethics_concerns_details": "No"}}, {"review_id": "GSfUlo2OMv", "reviewer": "Reviewer_zfbk", "summary": "This paper explores the application of LLMs to graph-related tasks through instruction tuning. A dataset including 14 graph tasks and approximately 63k question-graph pairs across academic and e-commerce domains is utilized to evaluate different graph representations and their impact on LLM performance. The study identifies JSON as the most effective format, achieving superior results across a range of graph types and tasks. It also examines the generalization capabilities of LLMs across three dimensions: unseen sub-tasks, domains, and answer types. The findings indicate that while LLMs exhibit strong generalization in some areas, they face challenges in others, notably inductive reasoning tasks such as link prediction.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Reason to reject\n1. Thank you for your suggestion. In our final version, we will update this part by adding more details about the graph instruction tuning.\n2. Thank you for suggesting a broader comparative analysis. We have recently conducted some experiments with another LLM, Google’s Gemma-7b. The current results on the Amazon Metadata network also support our following observation in the paper:\nJSON format gives the LLMs the best performance after tuning.\nThe model presents an excellent generalization on the unseen sub-tasks of Node, Pair, Bool, and Graph tasks, with a small drop in the performance, but fails to generalize to the unseen sub-tasks of Count, Path, and Link prediction tasks.\nMore models and results will be added to the final version of the paper.\n\nQuestions To Authors:\n1. One of our research questions is “To what extent can LLMs fine-tuned on limited graph-related tasks generalize to unseen tasks?”, the graph-related tasks can be “limited” from several perspectives: limited queried information (only a few node types and edge types), limited graph structure distribution (a few distinct domains) and limited trained graph algorithm. Therefore, we would like to choose graph datasets that have only a few node and edge types and the datasets should be from distinct domains. Also, to study the LLM generalization capability with its general world knowledge, we would like the graph datasets to contain some general types, like paper and products, rather than some specialized types like diseases and pharmacology. Therefore, we choose the Amazon Metadata and MAPLE, where both contain 3 to 4 common node and edge types and have different graph structure distributions against each other.\n\n2. We have collected some statistics of the graphs in both datasets. Below are the statistics of the Amazon Metadata training dataset using JSON format:\nmax node #: 176,\nmax edge #: 276,\n80% have between 29 - 107 nodes,\n80% have between 30 - 140 edges.\nWe also observe that the instruction-tuned LLM’s performance on different tasks decreases differently as the number of nodes or edges increases. We will include more detailed data and discussion in our final version.\n\n3. In most of the failure cases, the outputs are some meaningless text like “node1, node2, …”. We hypothesize that this is because LLM didn't understand the graph structure from our prompt. We will try different prompts with more detailed explanations and report any influence in the final version.", "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": "1. The exploration of representing graphs in JSON and DOT formats is innovative and provides valuable insights into optimizing LLM performance across complex graph structures.\n2. The examination of domain generalization offers meaningful contributions to the field, demonstrating how LLMs can adapt to different graph structures and domains without prior exposure.\n3. This paper adeptly highlights both the potential and the limitations of applying LLMs to complex graph-based problem-solving.", "reasons_to_reject": "1. The methodology employed in graph instruction tuning is inadequately detailed and only briefly introduced in section 4.1.2. To enhance clarity and understanding, this method should be thoroughly described earlier in the paper, ideally in section 3, alongside a comprehensive explanation of the techniques and processes involved in graph instruction tuning, e.g., which loss is used.\n2. The paper lacks a broad comparative analysis. It only evaluates the performance of two LLM backbones, neglecting other popular language model variants, such as those from the GPT series, which could serve as valuable baselines. Additionally, comparing these results with traditional graph methods and graph neural networks would significantly enrich the study’s insights and implications for the field.\n3. There is no analysis of the scalability of the methods, which is a critical aspect to consider for practical applications. It is unkown the maximum graph size the methods can handle.", "questions_to_authors": "1. Given the wide variety of graph datasets available, what motivated the choice of Amazon Metadata and MAPLE for your evaluation? Could you elaborate on how these particular datasets align with the objectives of your study?\n2. Regarding scalability, could you detail the maximum graph size that your graph representation methods can effectively handle? What are the limitations in terms of node and edge count for each representation method?\n3. The performance figures for LLaMA-2 and Mistral models without instruction tuning appear unusually low in Table 3, and seems like random guess. Could you provide some insights?", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces a valuable dataset and benchmark for evaluating large language models (LLMs) on graph-related tasks, which is a significant contribution given the importance of understanding structured data in various applications. The dataset is diverse, covering 79 graph-related tasks from academic and e-commerce domains, and provides a comprehensive evaluation platform for future research. The study also innovatively explores different graph representation formats, concluding that JSON is the most effective for enhancing LLM performance. Additionally, the paper examines the generalization capabilities of LLMs across unseen sub-tasks, domains, and answer types, offering insightful analyses and highlighting both potential and limitations in applying LLMs to complex graph-based problem-solving. The clear and accessible writing style makes the paper easy to follow, even for readers unfamiliar with the topic.

Despite its contributions, the paper has several limitations. The proposed graph representation approaches are all rule-based, lacking a learnable approach such as encoder-based representations, which could have added more depth to the study. The methodology for graph instruction tuning is inadequately detailed, and the lack of a comprehensive comparative analysis with other popular LLM variants and traditional graph methods diminishes the robustness of the findings. The paper also overlooks scalability issues, failing to address the maximum graph sizes the methods can handle, which is crucial for practical applications. Furthermore, the benchmark focuses only on academic and e-commerce domains, neglecting other important areas like chemistry and biology. The limited evaluation of only two LLMs (LLaMA-2 and Mistral) restricts the generalizability of the results, and the paper's overall technical contributions are minimal, primarily offering evaluation results and insights rather than novel methodologies.

[comments from the PCs] It's advised to discuss scalability issues in the paper, as the AC notes this important aspect is overlooked.
Decision: Accept