Can LLMs Effectively Leverage Graph Structural Information: When and Why

Thank you for your thorough review and insightful feedback on our paper. We are grateful for your recognition of the paper's significance on timely topics on “increasing prominence of Graph+LLMs in various applications”, quality of “rigorous experimental and analytical support”, and clarity.

We address your concerns in detail below.

“Overlap with Previous Work. Several experiments and observations made in the paper have already been addressed in previous or concurrent works, such as [1], [2], and [3]. These prior works have explored topics like the effect of different prompt designs and settings, including zero-shot, few-shot, with k-hop neighbor information, and with title or title and abstract. It is acknowledged that the paper does introduce some unique elements, such as prompt designs with attention analogous to Graph Attention Networks (GAT) and providing more in-depth analysis. However, the experiments appear to have significant overlaps with existing research, leading to a perception of a relatively trivial contribution.”

While we acknowledge these papers, developing new prompts is not our main focus. For example, one of the major questions that we want to answer here is how does the richness of target nodes’ textual features affect LLMs’ benefit from structural information. And the take-away is that LLMs can benefit more from structural information when textual node features are scarce. In our experiment, we compared two settings: Rich textual context (e.g. paper title and abstract are given) and Scarce textual context (only title is given), to show this (Page 6, Table 2).

The above question is not overlapping with previous works mentioned.

1. The prompts designed in [1] always use title and abstract (Table 7,8), lacking comparison in terms of node-level feature richness.
2. [2] also regards the textual features of the target node as a whole, without any control over the richness of the features.
3. Although [3] includes a comparison between “feature+label” and “label” in Table. 1, there is no control over the richness of the feature. Moreover, [3] is published on arXiv on 10/02/23, which is later than the submission deadline of ICLR 2024 (09/28/23).

“Q1: "If data leakage is a major contributor of performance on OGBN-ARXIV, we would expect prompting methods based on LLMs to perform worse than MPNNs on ARXIV-2023." This argument regarding data leakage and the expected performance of LLMs compared to MPNNs on a new dataset is not convincingly made. We would expect LLMs to perform worse than MPNNs on ARXIV-2023 because there might be no causality between MPNN doing good/bad and LLM also doing good/bad.”

Sorry for the confusion in L 255, we are not assuming there is a strict relationship between MPNNs performance and LLMs performance. Our logic to support the argument that “there is no substantial evidence indicating that the performance of LLMs is significantly attributed to data leakage” is elaborated in the common response to all authors.

“Q2: The statement, "our findings underline the critical role of homophily in influencing LLM’s node classification performance," is made, but it may oversimplify the issue. While homophily's influence is acknowledged, it's essential to delve deeper into why LLMs are affected by homophily. It is suggested that LLMs tend to employ a simple majority vote approach when provided with neighbor information, regardless of the design of prompts, due to not being directly trained on structured (graph) data.”

We acknowledge your suggestion to delve deeper into why homophily affects LLMs' performance in node classification. To address the concern that “LLMs tend to employ a simple majority vote approach when provided with neighbor information”, we develop a new neighbor dropping experiment with three new setting with different prompt for neighbors: i) 1-hop title+label, (ii) 1-hop title and (iii) 1-hop label. “1-hop label” means that we only include the label of the neighboring papers. This special design is to gauge whether LLM is performing a majority vote with extra neighborhood information. Please refer to Page 17, Figure. 7,8 in the update paper.

If LLMs do rely on a majority vote to determine its prediction. We would expect that the “drop different” curve with 1-hop label goes up to 100% accuracy. However, we are not observing this, and the 1-hop label curve is lower than 1-hop title+label curve. This observation refutes the hypothesis that LLMs rely on simple majority vote for prediction. Instead, including more context information will help LLMs to make more accurate predictions as 1-hop title+label curve is higher than 1-hop label curve on both cora and arxiv-2023 datasets. Reference:

[1] Harnessing Explanations: LLM-to-LM Interpreter for Enhanced Text-Attributed Graph Representation Learning

[2] Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs

[3] GraphText: Graph Reasoning in Text Space

Thank you for your thoughtful review. We appreciate your acknowledgment of our paper's detailed experimental study, which delves into the impact of structural information on LLMs in node classification tasks.

We address your concerns in detail below.

W1.1: “Lack of significant contributions. My biggest concern about this paper is that the conclusions derived from the paper are quite trivial and unsurprising. For instance, the observation that stronger improvements in the performance on data with scarce textual features have been made even in the context of language models prior to LMs. I don't see why this wouldn't have hold for LLMs? Similarly, the observation regarding higher accuracies of LLM predictions on nodes with higher local homophilic ratio is also a common observation in the graph-mining literature.”

Our intention is to investigate if LLMs can be augmented with appropriate structural information for text classification tasks, which is not reiterating known concepts from graph-mining.

Some other interesting/non-trivial observations:

1. Paper with high homophily is easier for LLMs to classify even without any structural information (Page 9, Table 5, row 2). With zero-shot prompts (only the title of the paper is given), we observe a significant positive correlation between local homophily ratio and prediction correctness on 4 datasets. This is actually very interesting.
2. The benefit of structural information saturates earlier on LLMs than MPNNs. To show this, we add an experiment to compare the performance increase from incorporating structural information for LLMs and MPNNs respectively. The results are shown in below table and included in Appendix D.2, Page 16, Table 9.

The average increase from structural data of LLMs on 4 datasets is 2.78% (rich context) and 5.44% (scarce context). But the increase from structural data of MPNNs is 6.98% (rich context) and 14.07% (scarce context), which is significantly higher than the gain of LLMs. It means that The benefit of structural information saturates earlier on LLMs than MPNNs. This may be explained by LLMs have potential advantages in handling rich text features compared to MPNNs.

Table 9: Classification accuracy for the OGBN-ARXIV, CORA, ARXIV-2023, PUBMED on ChatGPT as well as GCN, SAGE and MLP. ↑ (LLMs) denotes the improvements of best prompt style that leverages structural information over zero-shot method. ↑ (MPNNs) denotes the improvements of the best MPNNs over MLP (without structural information).

Thank you for your thoughtful feedback! We appreciate your recognition of the paper's clarity and the novelty of combining graphs and LLMs. We address your concerns in detail below.

W1: “The review feels the motivation of this paper is not clear. Although LLM is popular, why we need LLMs for node classification tasks is not well-explained. The authors only focus on one node classification task. Given that a simple GNN can already yield satisfactory results for this task, the rationale for introducing LLM, which may be slower in inference, is unclear.”

Our intention is to investigate if LLMs, known for their versatility and robustness in text processing, can be augmented with appropriate structural information, instead of simply applying LLMs to solve graph tasks. Our motivation can be summarized as follows:

1. LLMs can serve as a zero-shot or few-shot classifier without any training, compared to GNNs, which is advantageous in some real-life scenarios such as online recommendations.
2. While GNNs are efficient for graph-structured data, LLMs offer potential advantages in handling rich text features within nodes, which might not be fully leveraged by GNNs.
3. The conditions under which LLMs can benefit from structural information is underexplored in current literature.

We refined the introduction and discussion sections to better clarify this motivation (L5, L47-48, L135, L142).

W2.1: “This paper lacks solid explanations and analysis of the experimental results. For example, why do different prompts result in different performance? Is there any theoretical analysis or intuitions?”

It may be explained by that different prompts may encapsulate varying degrees of contextual relevance to the target node, impacting the LLM's ability to utilize the provided information effectively. This is further discussed in Section 3.4: Impact of Homophily on LLMs Classification Accuracy.

W2.2: "Why can LLM outperform GNN on ARXIV-2023 while not on OGBN-ARXIV?"

The relationship of performance of GNNs and LLMs are dependent on datasets and prompts. The observation that "LLM outperforms GNN on ARXIV-2023 while not on OGBN-ARXIV" may be explained by that LLMs are better at classifying certain types of papers. And the two datasets have different label distribution.

W3. “The experimental analysis is also weak. The experiments in section 3.4 cannot really show the impact of homophily on LLM's classification accuracy. It may show that incorporating the context information with the same label can improve performance. The authors should compare more ablations with context samples which have the same label.”

In Section 3.4, two key experiments were conducted to investigate the impact of homophily on LLM classification accuracy.

1. The first experiment involved dropping neighbors of a target node in three ways: those with the same label, different labels, and randomly. This demonstrated that a higher local homophily ratio, where more neighbors share the same label as the target node, positively influences LLM's prediction accuracy.
2. The second correlation study revealed a positive correlation between local homophily ratio and prediction correctness in all 5 datasets with p value less than 0.001 (Page 9, Table 6). Notice this experiment does not involve any dropping of neighbors and is calculated in the original dataset. This further emphasizes the significance of homophily in improving the accuracy of LLM classifications.

While we believe the results of the two experiments are fairly strong evidence of the impact of homophily, we still appreciate it if you could elaborate on the details of the ablation setting suggested in your review, so that we can further improve our experiments. Thanks!

W4. “The authors study the problem of incorporating structural information (such as graphs) to improve the predictive accuracy of LLMs but only conduct experiments in node classification. Some experimental results might provide better understanding. For example, checking the performance of other competitive LLM methods on graphs and downstream tasks.”

Thank you for your advice on checking “other competitive LLM methods on graphs and downstream tasks”. We acknowledge that other graph-related problems are important to understand how LLMs can benefit from structural information. However, as an early study on this topic, we aim to focus more on the depth of the analysis (answering the why question) rather than the breadth. We believe narrowing down the type of prediction tasks could provide us a better testbed for our analysis. That being said, we plan to extend our research to encompass a broader range of graph-related tasks, including link prediction, in future work.

Thank you for recognizing the “valuable insights” in our work and clear writing. We address your detailed concerns below.

One of the limitations is that the study only focuses on node classification tasks and does not explore other graph-related tasks. It is unclear whether these techniques can be generalized to other tasks.

See common response.

Question: "Do you think other Large language models such as LLaMA or Falcon are robust against data leakage?"

Similar to ChatGPT, There is no significant evidence that the performance of LLaMA-2 is significantly attributed to data leakage.

We run the classification experiment on LLaMA-2-7B-chat [1] and include the results below as well as in Appendix D, Page 16, Table 8. Notice that the pretraining data of LLaMA-2 has a cutoff of September 2022 (Page 77) and the test data in arxiv-2023 are arXiv papers published in 2023.

If LLaMA-2-7B-chat rely on data leakage to make accurate prediction, the performance drop of LLaMA-2-7B-chat between ogbn-arxiv (may have leakage problem) and arxiv-2023 (leakage-free) should be significantly greater than the drop on MPNNs on two datasets. This is because LLMs may benefit from their memory on ogbn-arxiv from data leakage to have higher accuracy. But this advantage is not likely on arxiv-2023. However, in Table 8 (below), we do not observe this: the performance drop of LLMs between ogbn-arxiv and arxiv-2023 is less than the drop on MPNNs in scarce context (6.7% vs 4.5%), and slightly higher in rich context (4.6% vs 5.1%). From this, we argue that there is no significant evidence that the performance of LLaMA-2 is significantly attributed to data leakage.

[1] Llama 2: Open Foundation and Fine-Tuned Chat Models, https://arxiv.org/abs/2307.09288

Thank you for recognizing the timeliness and good organization of our work, and the novel aspect of data leakage. We address your detailed concerns below.

it would be better if the authors can also perform experiments on open-source models, such as LLaMA.

See common response. We added experiments on LLaMA-2-7B-chat [1].

Question1: "Do you observe cases where ChatGPT fails to follow the instructions and generates stuff that cannot be automatically parsed? How do you deal with these samples?"

We did not observe that ChatGPT failed to follow the instructions. For example on dataset ogbn-arxiv, our instruction is "Please predict the most appropriate arXiv Computer Science (CS) sub-category for the paper. The predicted sub-category should be in the format ’cs.XX’.". ChatGPT always prints out 'cs.XX' as its answer without extra text. On the other hand, LLaMA-2-7B-chat sometimes provides extra explanation text in addition to its prediction. In this case, we matched the last appeared category as its prediction. This parsing strategy worked throughout our experiment.

Question 2: "LLMs may be sensitive to the order of contexts. Have you tried to modify the order of 1-hop, 2-hop neighbors in the 1/2-hop title+label setting? Does it lead to significant performance changes?"

Shuffling the order of neighbors in prompt has a negligible effect on prediction performance. We have conducted the shuffling experiment on Cora, and the results show small standard deviations after shuffling the order of neighbors over 3 runs: $0.7281 \pm 0.0031$, (1-hop title+label), $0.6359 \pm 0.0008$ (1-hop title), $0.7577 \pm 0.0031$ (2-hop title+label). This observation also holds for other datasets in our experiments.

[1] Llama 2: Open Foundation and Fine-Tuned Chat Models, https://arxiv.org/abs/2307.09288

@Reviewer Ayoh, vRFw: The logic behind the data leakage experiment is not clear/may not generalize.

1. We tried quite a few different prompt styles including zero-shot, few-shot, Chain-of-Thought, 1/2-hop title(+label) and 1-hop attention prompts (Table 4). The conclusion of data leakage based on these prompts may generalize to other prompting styles.

2. We did have concrete evidence of the minor effect of potential data leakage for the prompting styles that we tried. If LLMs rely on data leakage to make accurate prediction, the performance drop of LLMs between OGBN-ARXIV (may have leakage problem) and ARXIV-2023 (leakage-free) should be significantly greater than the drop on MPNNs on two datasets. This is because LLMs may benefit from their memory on OGBN-ARXIV from data leakage to have higher accuracy. But this advantage is not likely on ARXIV-2023. However, in Table 4, we observe exactly the contrary: the performance drop of LLMs between OGBN-ARXIV and ARXIV-2023 is less than the drop on MPNNs on two datasets (1.3% compared to 5.1% in rich context, 3.6% vs 4.5% in scarce context). This means that LLMs actually generalize well to leakage-free data. We have revised the paper to make this argument more clear (L 256-262).

[1] Llama 2: Open Foundation and Fine-Tuned Chat Models, https://arxiv.org/abs/2307.09288