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
unseen  domain
Venue: colmweb_org_COLM_2024_Conference
Published: 2024-03-22 15:57:28

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.

Main paper: 
 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 instruction-tuned 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. To facilitate the analysis of generalization, we build a 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 as a 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.• RQ2: 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-tuned model, we propose three levels of generalization, namely Unseen Sub-Task, Unseen Domain, and Unseen Answer Type, where each level tests the LLM on a 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 indicates that the LLM can generally be improved over a 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 is capable of handling tasks requiring 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.To summarize, our key contributions are threefold:• We create a benchmark with fine-grained 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 to investigate the generalization of the instruction-tuned LLMs. Our experiments reveal tasks where LLM could be overfitted or hard to generalize. Our experiments also show LLM can derive algorithms from the learned algorithms. 
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 on 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 graph-empowered 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 as 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.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 on texts, recently an 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) 3 Instruction Tuning on Graph 
preliminaries: 
 Formally, a general graph can be represented as G = (V, E, T V , T E , ϕ V , ϕ E ), where V is the set of nodes, E ⊆ V × V is the set of edges, T V and T E are the sets of node types and edge types, and ϕ V : V → T V and ϕ E : E → T E 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 v, P(u, v) to represent the set of paths connecting nodes u and v, p u,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.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 to 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/false answer to 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, we design a set of tasks, where each task requires a specific graph algorithm. All the tasks are listed in Table 1 , along with their category, mathematical description, and an 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 neighbors task can be subdivided into sub-tasks like finding the brand of a product and finding the "also view" product of a 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 Node Find neighbors {v ∈ N(u)|ϕ E (u, v) ∈ T ′ E } What are the products of brand1? Nodes shared neighbors {v|∀t e ∈ T ′ E , ∃w ∈ V, ϕ E (u, w) = ϕ E (v, w) = t e }What are the products that share "also view" products with product1? N-hop neighbors {v|ϕV (v) ∈ T ′ V , d(u, v) <= c}What are the product nodes within 3hop to product11?Pair Find pairs {(v 1 , v 2 )|ϕ(v 1 , v 2 ) ∈ T ′ E , u ∈ {v 1 , v 2 }}What are the pairs connected by "also view" edge and containing prod-uct11?Pairs shared neighbors {(v 1 , v 2 )|∃W ⊂ V : ∀w ∈ W, ϕ E (v 1 , w) = ϕ E (v 2 , w) ∈ T ′ E ∧ |W| = c}What are the pairs that share 3 "also buy" nodes?Count Degree count {|V ′ ||V ′ ⊆ N(u) : ∀v ∈ V ′ , ϕ E (u, v) ∈ T ′ E }How many "also view" nodes does product11 have? Node count within N-hop {|V ′ ||V ′ ⊂ V : ∀v ∈ V ′ , d(u, v) <= c}∈ P(u, v)|len(p ′ u,v ) = min(len(p u,v )|p u,v ∈ P(u, v))}What are the shortest paths between product11 and product12?Ego graph{(v 1 , v 2 ) ∈ E|d(u, v 1 ) <= c, d(u, v 2 ) <= c}What is the ego graph with radius 2 centered at product11?Link Prediction (E ′ , T ′ E ) → {0, 1} Predict whether there is a "also view" edge between product11 and prod-uct12.Table 1 : The overview of all tasks. T ′ E ⊆ T E , T ′ V ⊆ T V and c ∈ Z + are the edge types, node types, and number restrictions in the task.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 on novel challenges beyond its training data.Unseen sub-tasks evaluate the LLM's capacity to apply similar graph algorithms to subtasks slightly different from the ones seen during training. For instance, a model may be trained to 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 it 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.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 a 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 a maximum limit on the number of edges for each type or establishing a 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 a unique ID. For instance, a 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 a 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 an 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 remains independent of the task. Consequently, this approach facilitates the unbiased learning of general graph algorithms, irrespective of the graph's structural characteristics.Choosing the appropriate format for prompts is essential when utilizing LLMs, as it significantly 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.To graph instruction tune the LLMs, we concatenate each sample's question X q with its graph representation X g 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 isL = -∑ i log p θ (y i |X q , X g , Y <i )where y i is the ith token in the Y.  
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 buy", "also view", "brand", and "category". The graphs are built using metadata from the CDs and Vinyl, Movies and TV, and Arts Crafts and Sewing categories.MAPLE (Zhang et al., 2023b) is derived from the Microsoft Academic Graph, featuring 19 scientific fields. We extract the authors, papers, and venues as 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 a ratio of 7:1. The statistics of the collected graphs and datasets are presented in Table 2 .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.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 to 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 a separate training for the evaluation of unseen answer types.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 F1 for the Node, Pair, Path, and Graph tasks. For the Path task, we treat each path as a single value and calculate the F1 score between the extracted and the ground truth paths. Scalability Table 3 presents the average length in tokens and the maximum graph size in a 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 is shown that natural language has the most compact representation and can handle the largest graph in a limited context budget.Performance Table 4 presents the performance of both vanilla LLMs and graph instructiontuned 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-tuned 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.Llama-2-GraphInst-13bModel Scale Furthermore, we conduct studies to compare how different graph representations perform with different scales of LLMs. Concretely, we instruction-tune 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 on both scales.We postulate that this superiority of JSON representations stems from their clearer structural depiction compared to natural language. Moreover, JSON is a more prevalent format in the pre-training data compared to DOT. Consequently, models trained with graph instruct-tuning tend to find JSON particularly effective in comprehending and reasoning about complex graph structures.Given the consistently strong performance associated with the use of JSON format, our analysis in the following sections focuses primarily on models trained with JSON format. As mentioned in Section 3.3, we 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 on the unseen sub-tasks of Node, Pair, Bool, and Graph tasks, with a small 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 in 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 is 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. 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 subtasks 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 in 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.In Table 5 , we aim to assess the capacity of instruction-tuned LLMs for generalizing across different answer types. As highlighted in Section 3.3, this represents a particularly challenging 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-tune the LLM as Mistral-GraphInst-masked.Regarding the results, Mistral-GraphInst-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 effectively enables the LLM to grasp structural information and apply it to successfully tackle questions beyond its initial training scope. Task:Given the graph and text information, answer the question -What are the shortest paths between brand37 and category65? Treat the graph as undirected and list all the paths. The answer should only contain node ID sequences wrapped by '()' like '(node1, node2, node3, ...)' and the sequences are separated by space. The graph is represented in the json format.Graph:{"product17": {"also_buy": ["product16"], "product_of": ["brand37"], "belong_to": ["category61", "category62", "category63", "category64"]}, "product18": {"also_buy": ["product16", "product22", "product23", "product24"], "product_of": ["brand38"], "belong_to": ["category63", "category67", "category68", "category62"]}, "product19": {"also_buy": ["product16", "product26"], "product_of": ["brand37"], "belong_to": ["category62", "category63", "category64", "category61"]}, "product26": {"also_buy":["product19"]}, "product20": {"product_of": ["brand36"], "belong_to": ["category62", "category65", "category66"]}, "product21": {"product_of": ["brand36"], "belong_to": ["category62", "category65"]}, "product25": {"also_buy": ["product18", "product19"]}} (brand37, product17, category62, product21, category65) (brand37, product17, category62, product20, category65) (brand37, product19, category62, product21, category65) (brand37, product19, category62, product20, category65) (brand37, product19, category62, product20, category65) (brand37, product19, category62, product21, category65) (37, 65) Explanation: There is only one path between brand37 and category65. It is (37, 65).Expected ResponseFigure 5 : Case study on finding the shortest path between two non-product nodes in the Amazon dataset, depicted through a 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 , Mistral-GraphInst, with its specialized tuning for graph dataset analysis, 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-GraphInst 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 a few shortest paths, Mistral-GraphInst's capability of handling complex network dynamics positions it as a superior tool for tasks demanding in-depth exploration of graphs, thereby advancing our ability to 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-tuned LLMs to different kinds of unseen tasks. Future studies can consider applying such instruction-tuning techniques to graphs from other domains. 
 
 Appendix:  


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

Reviews: review: paper_summary: paper_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.

Authors conclude that JSON is the best format with advnatage for adapted LLMs in performance.
strength_weakness: strength_weakness: (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.

(2) The datasets are small and diverse enough.
questions: questions: (1) Could you have written the queries in natural language, is there a need to use phrases such as 'also_buy' or 'product_of'?

(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?


(3)
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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 

3. The paper only evaluates the ability of Llama2 and Mistral, which is hard to cover all representive LLMs.

4. 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: questions: 1. Can you compare more LLMs beyond Llama 2 and Mistral?

2. Can you elaborate on the technique contribution?

3. What is the gap between small models on graphs and LLM in understanding graph structure?
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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: questions: 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?
2. 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?
3. 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?

Comments: title: Response of Reviewer zfbk
Some current experiment results of Gemma-7b on Amazon Metadata dataset
Some current experiment results of Gemma-7b on Amazon Metadata dataset
comment: Thank you for your detailed response. Most of my concerns have been resolved. I will maintain the score.
> 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.

You only test three small-scale LLMs less than 10B. From my opinion, which data format for graphs is better is more likely model-independent and a such conclusion may be misleading. You can also recommended to test larger LLMs or APIs to convince the readers.

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

From my experience with LLMs for graph problems, this behavior seems unusual. It likes the behavior of LLaMA 2 7b without the chat version. The chat version can follow your insturctions and make a prediction. Please double check it, and also consider providing some examples in prompts.

Overall, I think the paper has some merits and interesting findings that worth an accept. So I raised my score.
**Add to Table 3:**

|                         | Node  | Pair  | Count | Bool  | Path  | Graph | LP    | AVG   |
| ----------------------- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- |
| Gemma-Inst_natural | 13.85 | 25.20 | 2.59  | **65.92** | **34.64** | 28.85 | 44.96 | 24.42 |
| Gemma-Inst_json    | 15.50 | 26.54 | **6.67**  | 65.15 | 30.00 | 29.45 | 36.00 | 24.74 |
| Gemma-Inst_dot     | **16.83** | **35.91** | 4.06  | 64.76 | 31.19 | **37.69** | **60.33** | **28.72** |
| Gemma-GraphInst_natural | 87.34 | 76.30 | 46.51 | 97.36 | **68.06** | 77.32 | **85.17** | 75.43 |
| Gemma-GraphInst_json    | **90.15** | **78.11** | **49.98** | **99.24** | 65.68 | 78.08 | 82.42 | **76.98** |
| Gemma-GraphInst_dot     | 87.43 | 78.09 | 47.96 | 96.36 | 67.43 | **83.51** | 83.94 | 76.37 |

The results show JSON format provides the best performance after graph instruction tuning.

**Add to Figure 3:**
|                      |        | Node  | Pair  | Count | Bool   | Path  | Graph | LP     | AVG   |
| -------------------- | ------ | ----- | ----- | ----- | ------ | ----- | ----- | ------ | ----- |
| Gemma-GraphInst_json | Seen   | 93.69 | 82.97 | 62.60 | 100.00 | 81.07 | 84.22 | 100.00 | 85.02 |
|                      | Unseen | 87.19 | 75.69 | 37.36 | 98.47  | 50.30 | 71.94 | 47.25  | 69.71 |

The results show the graph instruction tuned LLM generalizes well on 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.
**Add to Table 3:**

|                         | Node  | Pair  | Count | Bool  | Path  | Graph | LP    | AVG   |
| ----------------------- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- |
| Gemma-Inst_natural | 13.85 | 25.20 | 2.59  | **65.92** | **34.64** | 28.85 | 44.96 | 24.42 |
| Gemma-Inst_json    | 15.50 | 26.54 | **6.67**  | 65.15 | 30.00 | 29.45 | 36.00 | 24.74 |
| Gemma-Inst_dot     | **16.83** | **35.91** | 4.06  | 64.76 | 31.19 | **37.69** | **60.33** | **28.72** |
| Gemma-GraphInst_natural | 87.34 | 76.30 | 46.51 | 97.36 | **68.06** | 77.32 | **85.17** | 75.43 |
| Gemma-GraphInst_json    | **90.15** | **78.11** | **49.98** | **99.24** | 65.68 | 78.08 | 82.42 | **76.98** |
| Gemma-GraphInst_dot     | 87.43 | 78.09 | 47.96 | 96.36 | 67.43 | **83.51** | 83.94 | 76.37 |

The results show JSON format provides the best performance after graph instruction tuning.

**Add to Figure 3:**
|                      |        | Node  | Pair  | Count | Bool   | Path  | Graph | LP     | AVG   |
| -------------------- | ------ | ----- | ----- | ----- | ------ | ----- | ----- | ------ | ----- |
| Gemma-GraphInst_json | Seen   | 93.69 | 82.97 | 62.60 | 100.00 | 81.07 | 84.22 | 100.00 | 85.02 |
|                      | Unseen | 87.19 | 75.69 | 37.36 | 98.47  | 50.30 | 71.94 | 47.25  | 69.71 |

The results show the graph instruction tuned LLM generalizes well on 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.