Talk like a Graph: Encoding Graphs for Large Language Models

Details on GraphQA

Thanks for the suggestion. We added some task descriptions in the main paper (Section 3.1). We also added a separate section for GraphQA in the appendix (A.2) and moved the descriptions under this section and also added more details on it. We are committed to open-source the code and data upon acceptance of the paper.

Equation 2

We updated Equation 2 to the following to better reflect the goal of this work:

Our training input $D$ to the graph-based prompt system is a set of ${G, Q, S}$ triples, where $G$ is a graph, $Q$ is a question asked to the LLM, and $S$ is a solution to $Q$, ($S \in W$). We seek to find a $g(.)$ and $Q$ that maximize the expected score from the model ($\text{score}_f$) of the answers over the training dataset $D$.

$

\max_{g, q} E_{G, Q, S \in D} \text{ score}_f(g(G), q(Q), S)

$

Please let us know if this is not clear and we can elaborate more.

Adding task descriptions

We added the task descriptions to the beginning of Section 3.1. We also added mode detail for the disconnected node task in Section 3.5.

Presenting Table 1 aggregated by graph encoding

Thanks for the great suggestion. We already reported aggregated results in Table 6 in the appendix as the average ranking of each encoder. We also added Table 7 with mean and standard deviation aggregated for each encoder. The results in Table 7 also confirms our hypothesis from Table 6 that the incident encoder outperforms the rest. We posit that the success of incident encoding can be attributed to two key factors. Firstly, it leverages integer node encoding (e.g., node 0 or node 1), as we previously emphasized the advantages of this approach in Section 3.1.1. Secondly, incident edge encoding effectively captures the one-hop neighbourhood around a graph, outperforming methods that simply list edges in a random order.

Uniqueness of some of the findings in this work

We agree that many of the findings are in-line with the existing work in the literature. We think that demonstrating the persistence of these (some established) results, in the context of graph reasoning is essential, especially given the widespread adoption of using LLMs for reasoning.

We also showed that linear scaling does not hold for some of the tasks studied here. We observed some non-linear scaling in cycle check (see Figure 3-cycle check) and also in the new results added for the path existence task (checking if a path exists from one node to the other) upon reviewer FDET’s suggestion :

Another finding of this work was that incident encoding performed the best across all the tasks (discussed in Section A.3).

Section 4 experiment setup

The generated graphs for this section are sampled randomly from the generator using similar statistics as input. To be able to report results for this section, we encoded graphs from each graph generator using the nine graph encoding functions and aggregated the results over the graph generator. We believe this setup gives us a controlled experiment to measure the effect of the graph generator. We reported some hypotheses in Section 4.2. Here’s a summary:

• For each of the tasks, LLMs have a prior bias about the problem. For instance, for the cycle check task, LLMs have a prior bias saying there is a cycle in the graph. For instance, for the cycle check task, LLMs have a prior bias that assumes there is a cycle in the graph. Therefore, the performance is better for graphs with cycles (e.g., complete graphs) compared to those with no cycles (e.g., star graphs) (Figure 4 visualizes how these graphs differ).

• For some of the tasks with counting (e.g., node degree, node count, and edge count), the fewer the number of edges in the graph, the easier it is for the LLM to reason. For instance, star graphs have the best performance, and complete graphs have the lowest (again, Figure 4 visualizes how these graphs differ).

Graph-to-text generation techniques (i.e. [1]) and diversity of the encoding functions

Wow, great suggestion! In this paper, we specifically studied the class of fixed text encoding functions because we observed that many users of LLM systems are relying on these fixed transformations. Our results show that your intuition is exactly right (fixed encodings have limitations), and investigating this area is very interesting follow up work!

For this particular reference [1], we searched for an existing model to try to use it “out of the box”, but could not find any available. Unfortunately we do not have time in the review cycle to appropriately train this as a baseline and collect its results (as running this experiment takes significant time already).

While we initially intended to explore fixed text encoding functions, our goal was to introduce diversity in node and edge encodings. This involved employing a range of node encodings (integers, alphabet letters, popular character names) and edge encodings (friendship, co-authorship, parentheses). By combining these, we achieved a diverse set of graph encoding functions (see Appendix A.1 for more details). The choice of the encoding functions was informed by the typical user practices associated with LLMs.

Introduce random graph generation methods in the appendix.

We added descriptions for the random graph generator functions in the appendix in Section A.2.2.

More challenging tasks

Thanks for the great suggestion! We have added a synthetic node classification task based on GraphWorld [2], and are currently waiting for the results of this experiment to complete. (We will update here when this is done)

We would like to note that some of the diverse tasks in our benchmark do share elements of graph classification (especially w.r.t. to motif detection). For example, The cycle check task needs to do multi-hop reasoning over the structure of the graph in order to determine the existence of a cycle. Also, note that the node degree counting could be viewed as the simplest node regression task. (More complex versions of this task might try to compute advanced node-level graph properties.) Similarly, the node and edge count and cycle check might be viewed as graph classification tasks. Upon your suggestion on adding more complex tasks, we conducted experiments on a new task for path existence which requires multi-hop reasoning. Here are the results:

Adding examples for experiment 2.

We added this to the paper. Please let us know if this is not clear. Here’s the examples for your references:

[1] Yi Luan Mirella Lapata Rik Koncel-Kedziorski, Dhanush Bekal and Han- naneh Hajishirzi. Text Generation from Knowledge Graphs with Graph Transformers. In NAACL, 2019.

[2] Palowitch, John, Anton Tsitsulin, Brandon Mayer, and Bryan Perozzi. "Graphworld: Fake graphs bring real insights for gnns." In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3691-3701. 2022.

Your suggestion to explore a node classification task proved to be immensely valuable. Inspired by your suggestion, we used our stochastic block model graph generator to create two distinct blocks representing soccer and baseball enthusiasts. We then labeled a subset of nodes and asked the LLM to determine whether an unspecified node belonged to the soccer or baseball group. This exercise aimed to assess the LLM's ability to exploit the homophily in a given graph.

The results for various encoders were as follows:

The results of this experiment also confirm the major findings in the paper. First, the LLM didn't do well on the node classification task either and only just beat the majority baseline by a small amount (51.2% to 58.4%). Second, the choice of the graph encoder has a significant impact on the LLM reasoning. As this task requires more reasoning (compared to some of the tasks that require more of memorization), some of the encoders with more textual information (e.g., friendship) proved to be more powerful. We can add this experiment to the main paper.

This exercise further demonstrated the versatility of our benchmark, accommodating new tasks and effectively evaluating the performance of LLMs across diverse graph generators. We will open-source the code and data to facilitate future research in this direction.

1. How can graphs help LLMs maintain freshness of information?

Graphs are very general data structures -- in this work we are measuring how well structured data can be injected into and interpreted by LLMs. The connection to freshness goes as follows:

Consider the example of question answering with a LLM which has access to a knowledge graph (KG) or other structured database. We can either perform a one-time update [via pre-training or fine-tuning] of the LLMs with the KG information or instead we can provide the KG as in-context information as part of the LLM’s prompt. With the former case, it’s more difficult to update the LLM with fresh information. However, in the latter case, it’s easier to update the database (and the in-context information) as new information becomes available. We updated the second paragraph in the introduction to elaborate on this.

2. Section 3.5 experiment 5: disconnected nodes task

In this task, we provide a graph description to the LLM, specifying the nodes and edges, and ask about the nodes that are not directly connected to a given node. We updated Section 3.5 to better explain this.

3. Adding motivations for each experiment.

Thanks! We highlighted the motivation for our experiments in the paper.

4 and 5. Motivation for using LLMs for graph tasks.

Great question! Our motivation is not to suggest that LLMs replace the reliable and efficient graph algorithms we all grew up with -- instead it's quite the opposite. We believe that graph tasks are an ideal lens for understanding multi-step reasoning with LLMs. By quantifying LLMs (poor) performance on these tasks, we highlight a significant gap with current technologies and open the door for future research in the area.

This is especially interesting, because many tasks that people ask of LLMs today reduce to graph algorithms (or have graph algorithms as essential components of their solution). For instance, when using LLMs in problems requiring deductive logical reasoning, the LLM should be able to perform edge existence, and reason about connected/disconnected nodes. However, there is not much work actually evaluating these capabilities. This is especially important for cases when the question is textual (and therefore common sense knowledge is needed) and it is not obvious what out-of-the-box graph algorithm might even apply.

comparisons with other LLMs

We appreciate the reviewer's valuable suggestion to conduct experiments on other LLMs. We run our experiments using GPT3.5. This additional evaluation provides further insights into the performance of our approach and confirms the key findings observed on Palm 1 and 2.

Graph encoder functions have a substantial impact on the performance of LLMs on graph-based tasks, with the node degree task exhibiting a performance variance of 5.4% to 66.4%. Integer node encoding enhances arithmetic performance for node degree, node count, and edge count tasks. The incident encoding outperforms other encoding functions by a significant margin on the connected node task due to its ability to make information more readily accessible for LLM utilization.

Novelty wrt [1, 2, 3]:

Thanks for the great question. Our work uniquely investigates how properties of the graph structure (via synthetic generation) influence the choice of graph encoding function. This is completely novel, as no other related work examines these interactions. This novel approach enables us to systematically study these interactions, which have not been explored in previous research. Additionally, we conducted extensive scaling experiments with LLMs of varying parameter sizes which no other work has done. Finally, we have significant differences from each work individually, for example: unlike [1], we study a diversity of LLMs (and have added more models in the rebuttal), unlike [2] we vary prompting and graph tasks, and unlike [3], we use a black box model without model weights.. Furthermore, we conducted experiments on varying question encoder functions to evaluate their impact on performance.

In order to clearly state the novelty of our work, we have added this following comparison table to the paper: