Comment by Authors
### 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$.
\begin{equation}
\max_{g, q} E_{G, Q, S \in D} \text{ score}_f(g(G), q(Q), S)
\end{equation}
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 :
| | Palm 2 XXS | PaLM 2 XS | PaLM 2 S |
|------------|------------|-----------|----------|
| zero-shot | **80.9** | 57.5 | **83.7** |
| zero-cot | 53.9 | 25.9 | 83.2 |
| few-shot | 44.8 | 60.5 | 81.9 |
| cot | 53.0 | **63.6** | 82.4 |
| cot-bag | 54.9 | 44.3 | 81.7 |
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).