Can LLMs Effectively Leverage Graph Structural Information through Prompts, and Why?
Authors: Jin Huang
Xingjian Zhang
Qiaozhu Mei
Jiaqi Ma
Venue: Accepted by TMLR ()

Abstract: Large language models (LLMs) are gaining increasing attention for their capability to process graphs with rich text attributes, especially in a zero-shot fashion. Recent studies demonstrate that LLMs obtain decent text classification performance on common text-rich graph benchmarks, and the performance can be improved by appending encoded structural information as natural languages into prompts. We aim to understand why the incorporation of structural information inherent in graph data can improve the prediction performance of LLMs. First, we rule out the concern of data leakage by curating a novel leakage-free dataset and conducting a comparative analysis alongside a previously widely-used dataset. Second, as past work usually encodes the ego-graph by describing the graph structure in natural language, we ask the question: do LLMs understand the prompts in graph structures? Third, we investigate why LLMs can improve their performance after incorporating structural information.
Our exploration of these questions reveals that (i) there is no substantial evidence that the performance of LLMs is significantly attributed to data leakage; (ii) instead of understanding prompts as graph structures, LLMs tend to process prompts more as contextual paragraphs and (iii) the most efficient elements of the local neighborhood included in the prompt are phrases that are pertinent to the node label, rather than the graph structure.

Qiaozhu Mei Published in Transactions on Machine Learning Research (06/2024)
Can LLMs Effectively Leverage Graph Structural Information through Prompts in Text-Attributed Graphs, and Why?
Jin Huang
huangjin@umich..e edu
University of Michigan, Ann Arbor
Xingjian Zhang
jimmyyzz@@hmicch.ete edu
University of Michigan, Ann Arbor
gmei@umich.com edu
University of Michigan, Ann Arbor
Jiaqi Ma
jigima@illinois. edu
University of Ilinois Urbana- Chaana--aa
Reviewed on OpenReview: //tp:r///opeeevvieet net/ forum? id- L2yRavIRas
Abstract
Large language models (LLMs) are gaining increasing attention for their capability to process graphs with rich text attributes, especially in zero-shot fashion. Recent studies demon- strate that LLMs obtain decent text classification performance common text-rich graph benchmarks, and the performance can be improved by appending encoded structural infor- mation as natural languages into prompts. We aim to understand why the incorporation of structural information inherent in graph data can improve the prediction performance of LLMs. First, we rule out the concern of data leakage by curating novel leakago-free dataset and conducting comparative analysis alongside previously widely-used dataset. Second, as past work usually encodes the ego-graph by describing the graph structure in natural language, ask the question: do LLMs understand the prompts in graph struc- tures? Third, we investigate why LLMs can improve their performance after incorporating structural information. Our exploration of these questions reveals that (i) there is no sub- stantial evidence that the performance LLMs is significantly attributed to data leakage; (ii) instead of understanding prompts as graph structures, LLMs tend to process prompts more as contextual paragraphs and (iii) the most efficient elements of the local neighborhood included in the prompt are phrases that pertinent to the node label, rather than the graph structure
1
Introduction
Large Language Models (LLMs) have gained great popularity for broad range of applications (Brown et al, 2020 OpenAl 2023). Recently, there have been few studics exploring LLMs' offoctiveness on graph data, particularly focusing on node classification in text-rich graphs. Consider citation networks as an example, where each node represents research paper, and each edge indicates citation relationship between papers. Previous studies have reported decent classification accuracy of LLMs on node-level information alone (Wang et al. 2023 He et al.] 2023] Chen et al. 2023). Moreover, recent work also suggests that the incorporation of structural information, e.g., describing the local graph structure and listing the neighboring papers' titles
in natural language, can further improve the accuracy (Chen et al. 2023 Guo et al. 2023 Hu et al. 2023
1 Coodes and datasets are at: http:::/ggttuu.c..../ Lab/LLM

---

Published in Transactions on Machine Learning Research (06/2024)
However, the benefit of incorporating structural information vary across datasets, and the underlying mechanisms remain not fully understood. Indeed, notable concern arises most node classification bench- marks have a data cut-off that predates the training data cut-off of LLMs like ChatGPT. This discrepancy raises concerns about data leakage-LLMs may have seen and memorized at least part of the test data of the common benchmark datasets which could undermine the reliability of studies using earlier benchmark datasets. Furthermore, the variation in performance across different datasets highlights the necessity of a deeper understanding of how LLMs process and benefit from the inclusion of structural information.
To this end, this paper focuses three concrete questions relevant to the incorporation of structural infor- mation into LLMs. First, we seek to understand whether the performance gain of LLMs on common node classification datasets comes from data leakage. Second, we investigate whether LLMs understand the graph structure as topological graphs or contextual paragraphs. Third, we investigate potential reasons why LLMs benefit from structural information.
For the first question, we investigate the exlent to which data leakage might artificially inflate the perfor- mance of LLMs in Section 3.2 To rigorously measure the data leakage effect, collect a new dataset, ensuring that the test nodes are sampled from time periods post the data cut-off of ChatGPT (OpenAl, 2022) and LLaMA-2 (Touvron et al. 2023).
For the second question, we investigate how LLMs process structural information as graphs or paragraphs by two adversarial settings in Section 3.3 Concretely, we linearize or randomly rewire the ego-graph and then compare the performance between LLMs and Message Passing Neural Networks (MPNNs). We conclude that L.MSs understand the input prompt more as linearized paragraphs than as graph-structured data, even though the prompts are intended to represent graph structural information.
For the third question, we probe into two related factors accounting for the improved performance: homophily and the richness of textual node features. In Section 3.4 we examine the impact of homophily (the tendency of similar nodes to connect) on the classification performance of LLMs. Through controlled experiments and correlation analyses, we eslablish a positive relationship between the local homophily ratio and the prediction accuracy of LLMs. also implies that homophily is important because it enables the local neighborhood to offer relevant phrases, thereby enhancing classification performance. In Section 3.5 we investigate the circumstances under which structural information provides minimal improvement, by varying the richness of textual information of the target node. Therefore, we discover that LLMSs benefit. from structural information primarily when the target node lacks sufficient textual information.
Our key findings are summarized as follows. (1) There is no strong evidence that data leakage is a major factor contributing to the performance of L.MSs on node classification benchmark datasets. (ii) LLMs understand the prompts as linearized paragraphs,rather than as explicit graph structures. (ili) The most efficient elements of the local neighborhood included in the prompt are phrases that are pertinent to the node label, rather than the graph structure.
Overall, this study investigate the underlying mechanism of how LLMs process graph data. Our findings clarify that data leakage does not significantly boost LLMs' performance on node classification tasks. While the performance does not come from data leakage, our study finds that LLMs do not benefit from the topo- logical structure of the ego-graph either. On the contrary, we discover that the effectiveness of incorporating structural information into the prompts largely depends on the phrases related to the node label. This insight opens new avenues for utilizing LLMSs in graph-based applications and for further exploration into advanced methods of incorporating structured data into LLM frameworks.
2
Related Literature
Data Icakage in LLMs. Data leakage in LLMs has become a focal point of discussion due to the models' intrinsic ability to memorize training data. As demonstrated by Carlini el al.) (2022), LLMs can emit memorized portions of their training data when appropriately prompted, a phenomenon that intensifies with increased model capacity and training data duplication. While memorization inherent to their function, it raises serious socurity and privacy concerns. A study by Carlini et al. (2021) shows that extraction attacks can recover sensitive information such as personally identifiable information (PIT) from GPT-2 (Radford et al.
2

---

Published in Transactions on Machine Learning Research (06/2024)
This capability to store and potentially leak personal data is further explored by Huang et al. (2022) confirming that although the risk is relatively low, there is tangible potential for information leakage. Specifically, [Crllii et al. (2022) show that the 6 billion parameter GPT-J model (Wang & Komatsuzaki] 2021 memorizes at least 1% of its training dataset. Furthermore, the issue of data leakage complicates the evaluation of these models. As highlighted by Aiyappa et al. (2023), the closed nature and continuous updates of models like ChatGPT make it challenging to prevent data contamination, affecting the reliability of evaluation on LLMs in various applications. In node classification tasks, & concurrent work by Chen et al. (2023) observe that specific prompt alteration significantly improved performance on OGBN-ARXIV, raising concerns about potential test data leakage. In this work, we take a rigorous approach by curating new dataset for node classification tasks, which is explicitly designed to address the data leakage issues in existing benchnarks.
2019).
LLMs on Text-Rich Graphs. Recently there has been a series of research on LLMs and text-rich graphs.
(2023) propose a mothod where LLMs perform zcro-shot prodictions along with generating cxplana- Gions for their decisions, which are then used to enhance node features for training Message Passing Neural
He ct al.
Networks (MPNNs) (Gilmer et al., 2017) to predict node categories. Chen al. (2023) extend the work of 2023 by using LLMs both as feature enhancers and as predictors for node classification. They offer several observations such Chain-of- oootghtsss is not contributing to performance gains. Guo et al.) (2023) perform an empirical study on using L.Ms to solve structure and semantic understanding tasks. More recently, Ye et al. (2023) propose InstructGLM for the instruction tuning of LLMs, like LLaMA (Touvron ct al. 2023). for node classification tasks. Zhao et al. (2023) introduces GraphText to encode graph into natural languages using a graph-syntax tree. Our study differs with this line of research in terms of the motivation: while we are using text-rich graph datasots as testbed, our primary goal is to gain deeper understanding of LLMs' capability of processing the graph modality, instead of leveraging LLMs to better solve node classification tasks.
He ct al.]
A few previous studics observe that LLMs have decent classification performance on text-rich graphs based on node-level feature only (He et al. 2023 Chen el al. 2023 Guo et al. 2023 Hu et al. 2023). For example, predicting the category of a paper based on its title and abstract. These investigations typically involve using manually crafted templates to describe neighborhood information around the target node hop-by-hop. Furthermore, several studies have noted that integrating structural information can moderately enhance prediction accuracy. Hu et al. (2023) observe that, "Incorporating structural information can slightly improve the performance of GPT in node-level tasks". Similarly, Chen et al. (2023) find that including neighborhood summarization could lead to performance gains, verified across four datascts. Guo et al. (2023) report a significant 10% improvement in prediction accuracy on OGEN-ARXIV when employing 2-hop summarization, compared to using only the target node. Moreover, they find that 2-hop summarization outperforms 1-hop summarization. However, these studies primarily focus on empirical observations without delving into the underlying reasons behind LLMs' improved performance with added structural information.
Homophily in graph learning. The concept of homophily (McPherson et al. 2001): 1 which describes
the tendeney of nodes to form connections with similar nodes, plays an important role in the effectiveness of
various graph learning methods [Zuu et al. 2020 Halcrow et al. 2020 Maurya et al. 2021 Lim et al. 2021)
The principle of homophily enables MPNNs to smooth node representations by aggregating features from their likely similarly-labeled neighboring nodes. This aggregation process is particularly effective in various types of real-workd graphs, such as political networks (Knoke) 1990), and citation networks (Ciotti el al., 2016). Despite its benefits, the reliance on homophily presents a challenge: MPNNs tend to underperform in graphs characterized by heterophily, where connected nodes are likely to differ propertics or labels (Zhu) (et al.] (020). Notably, the impact of homophily on the integration of structured data into LLMs remains an open area for exploration.
3

---

Published in Transactions on Machine Learning Research (06/2024)
Table 1: Prompt styles and their corresponding templates. For the style "k-hop title+labell, we only include the labels for neighbor nodes in training set validation set. The "attention extraction" and "attention prediction" are respectively the two steps of prompts for the k-hop attention strategy.
Prompt Style
Prompt Template
Zero-shot
Abstract: Sabstrac>>/aTibbe <title>> (D not give any reasoning logic for your
AnAnswer: |uln
Zero-shot CoT
Abstract: <abstract> AnTitle: <title>> nAnswer: LninLet's think step by step, \n
Few-shot
Abstract: <few-shot ahstract>>)n... AnAnswer: (nfn<cfew-shot label> I.... (more few-shot.
(vamples)(nAbstinnn <abstract>... AnAnswer: Anin
k-hop title, k-hopp title+llabll
Abstract: <abstract>> \nTiitl: <title'> mlI has following neighbor papers hop 1:/m
Paper title: <paper title> (nLabel:: <paper label>>)nIt is linked to paper <list papers linked to paper 1>\n
title>\nLabcl: Paper title: <paper 2 title> \LLabel: <paper 2 label>))ntt is linked to paper <list papers
linked to paper 2>
... (more 1-hop neighbons))n
It has following neighbor papers at hop 2:)n
(more 2-hop neighbors))
Do not give any reasoning or logic for your answer. \nAnswer: \nin
k-hop attention. Step Attention extraction
The paper interest <title>, Please return Python list of at most <k> indices the most related papers among the following neighbors, ordered from most related to least related. there are fewer than <k> neighbors, just rank the neighbors by relevance. The should look like this: [1, 2, 3, ...]: <neighhor title 1> (n.. (more 1-hop neighbors) \n
k-hop attention. Step Attention prediction
Abstract: <abstract>>> < <title>>> InIt has following important neighbors, from most lated to least related: [elate::\(mmore neighbors chosen by attention) (nDo not give any reasoning or logic for your answer.
Annwerr: \nin
Linearized h-p title, k-hop litle+label::
Abstract:
<abstract>>> ATTile: <title>> \n
<paper 1 LLLbel: <paper label>'n
<paper 2 title>>
Laaabll: <paper label>\n (more 1-hop neighbors))u
(more 2-hop neighbors)
not give any reasoning or logic for your answer. \nAnswer: Inin
3
Why Can LLMs Benefit from Structural Information?
3.1 Research Questions
In this section, we aim to gain a deeper understanding of three central questions. First, does the classification performance of LLMs on common node classification datasels come from data leakage? Second, do LLMs understand the prompts as graph structures? Third, what factors contribute LLMs benefiting from structural information? To ground our study, experiment with the ChatGPT API and LLaMA-2-7B model on node classification datasets that have textual node features.
For the first question, we investigate the potential impact of data leakage in Section 3.2 For the second question, we first investigate whether LLMs understand the input prompts as graph structure in Section 3.3 Building on this insight that LLMs actually understand the input prompls more as a linearized paragraph, we explore two contributing factors of LLMs performance after incorporating structural information. In Section 3.4 we explore the influence of homophily on LLMs performance. In Section 3.5 we assess how the feature richness of target node affects the performance of LLMs.
3.2 Data Leakage as a Potential Contributor of Performance
While LLMs have achieved decent classification performance on common node classification datasets, there is a risk that the performance of LIMs is artificially inflated by data leakage (He al. 20223 Guo et al. 2023 Hu
et al. 2023). Note that most node classification benchmark datasets have a data cut-off 2019 (see Table g
in Appendix B.1,, but ChatGPT (the model used throughout the paper is gpt-3. 1ptt3.5-turrb-oe --tuubbo0013)) trained
4

---

Published in Transactions on Machine Learning Research (06/2024)
Table 2: Statisties of OGBN-ARXIV and ARXIV-2023 datasets. Both represent directed citation networks where each node corresponds to paper published arXiv and each edge indicates one paper citing another. The metrics LDDerree/OuttDeegeee Average Degree, and Published Year are presented for test nodes.
Full Dataset
Test Set
Dataset
#Nodes
#Edges
In-Degree/ Deegree/Outt-egres
Average Degree
Published Year
OGBN-ARXIV
169343
1166243
1.33/11.1
12.43
2019 2023
ARXIV-2023
33868
305672
0.16/10.6
10.76
on data up to September 2021 (OpenAT 2023 and LLaMA-2 was trained on data up to September 2022 While the training datasets of ChatGPT and LLaMA-2 are not publicly available, given the widespread of these datasets on the internet and the enormous training corpus of ChatGPT and LLaMA-2, it is reasonable to worry about the data leakage issue on these datasets.
To this end, curate new node classification dataset, ARXIV-2023, which is designed to resemble another widely-used dataset, OGBN-ARXIV (Hu et al.) (0200] as much as possible except that the test nodes are chosen as arXiv Computer Science (CS) papers published in 2023. With the new dataset, we can rigorously investigate the influence data leakage by comparing the LLM performance between ARXIV-2023 and OGBN-ARXIV.
While, idcally, we should curate the new dataset by simply extending OGBN-ARXIV by including new papers, this is practically challenging for a couple of reasons. In particular, OGDN-ARXIV rep- resents arXiv CS papers in the Microsoft Academic Graph (MAG) until 2019 (Hu et al. 2020), where MAG is a heterogeneous graph representing scholarly communications (Wang et al. 2020). Unfortunately, MAG and its APIs were retired in 2021 and no subsoquent data is available Furthermore, the pipeline collect and construct MAG is not publicly released. Consequently, we develop our own data collection pipeline to create 2023, Specifically, we first sample test nodes from arXiv CS papers published in 2023, and then gather papers within a 2-hop of these test nodes to create a citation network. More details about collection can be lound in Appendix B.2
Dataset collection.
Comparison between arxiv-2023 and ogbn-arxiv. As can be seen in Table 2 ARXIV-2023 and OGBN- ARXIV share great similarities in their network characteristics, with consistent hi-degreeouut-deee to analogous citation behaviors. ARXIV-2023 shows a lower average in-dogree in the test sct, which is likely because the test papers in ARXIV-2023 are new and have not had much time to accumulate citations. Additionally, Figure iillustrate that the label distributions of the two datasets are comparable. notable trend from 2022,-2023, in alignment. with arxiv statistics indicates rise in AI-related categories like ML, LG, CL, reflecting the current academic focus.
pointing
Furthermore, we compare the performance of MPNNs on the two datasets. As can be seen from the two bottom rows in Table 3 we observe that the performance metrics for MPNNs (GCN and SAGE) across both datasets are closely matched, suggesting that both datasets present comparable challenges for classification. For a more comprehensive setting of MPNNs, one can refer to Appendix C
LLM performance arxiv-2023 and ogbn-arxiv. To test LLMs ARXIV-2029 and OGEN-ARXIV, we create prompts that encode both the textual features and the local graph structure of a target node in natural language as in Table and then request ChatGPT API or LLaMA-2-7B to make predictions for the target node The prompt for each node is formulated in one of several styles, as we introduce in details in Appendix Additionally, a fixed dataset-level instruction is attached to the prompt when the prompt is sent to all L.Mss. The datasct-lovel instructions are listed in Table g Appendix
https: http://///gttttoo////aaaatrrrrrr http://tth...cceeeee/o///////a// CAROOEEDELLAAAAAAEEE
htttp://wwee www.wooccctooooomoomooooow www.:at..cooooooaeeeeeeeeottttee htt.://....ooo..cooo///aaaaaaaaa
We have used gpt-3. S-tuboo--tr LLMMA-2-7B-chat for throughout the experiments, unless stated otherwise.
5

---

Published in Transactions on Machine Learning Research (06/2024)
arxiv arxiv-2023
0.25
0.20
Praportion
0.15
0.10
0.05
lra. MOORES 2000 Sepss & C CeRAero for g
0.00
Labels
Figure 1: Proportional distribution of labels in OGBN-ARXIV and ARXIV-2023 datasels. Each label represents an arXiv Computer Science Category.
Table 3: Comparison between ChatGPT's performance OGBN-ARXIV and ARXIV-2023. Best results in prompting methods are in bold. 1-hop attention means attention extraction and prediction over 1-hop neighbors
Rich context
Scarce context
Prompt style
OGEN-ARXUS ARXIV
ARXIV-200 2023
Prompt style
AGBN-ARXIV
ARXIV-2022
Zero-shot
74.0
73.5
Zero-shot
66.6
Few-shot
72.9
73.6
1-hop title
72.3
70.7
Zero-shot CoT
71.8
73.7
1-hop litle++labll
74.3
70.4
1-hop title-tlabel
75.1
73.8
2-hop title
71.3
68.9
2-hop title I label
74.5
73.2
2-hop title label
74.2
68.5
1-hop attention
74.7
73.7
1-hop attention
71.3
69.6
GCN SAGE
75.4
70.3
GCN
74.8
70.3
75.0
70.9
SAGE
74.4
69.1
If data leakage is major contributor of performance OGBN-ARXIV, would expect the performance drop of LLMs between OGEN-ARXIV (may have Icakage 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, but this advantage is not likely on ARXIV-2023. However, as shown in Table 3 we observe the contrary: the performance drop ChatGPT between OGBN-ARXIV and ARXIV-2023 is less than the drop on MPNNs on two datasets (1.3% compared to 5.1% rich context, 3.6% compared 4.5% scarce context). For L.LaMA--7BB, we also observe no significant drop compared to MPNNs (6.7% compared to 5.1% in rich context, 4% compared to 4.5% in scarce context. See Appendix D.2 that LLMs actually generalize well to leakage-free data.
Table 10p. This means
To conclude, the observed results neither offer clear evidence in favor data leakage nor does it advocate that data leakage prodominantly improves LLM's performance. Instead, LLM's consistent performance across both datasets resses its resilience and ability generalize across varying distribution domains.
3.3 Are LLMs Treating the Prompts as Graphs or Paragraphs on Text-attributed Graphs
Previous works design templates to encode the ego-graph around the target node into natural languages by listing neighboring nodes' text information (Chen al. 2023 Hu et al. 2023 or giving edge indexes (Tang et al. 2023).. adjacency lists (Das al.) 2023) or neighborhood summary (Guo al. (023). It is implied that previous works hold that LLMs may benefit from describing the explicit graph structures. However, it

---

Published in Transactions on Machine Learning Research (06/2024)
is unclear whether LLMs actually understand the prompt as intended. Thus, ask the question: do LLMs treat the input prompt as graph, or merely paragraph of text with augmented keywords? This question is fundamental in understanding the performance gain after incorporating structural information. If LLMs just process the prompt as a paragraph consisting of neighboring papers' titles, then the performance gain can only come from the extra phrases included in neighboring nodes, instead of the topological information. We investigate this question by two adversarial experiments:
1. Linearize ego-graph. We create lincarized version of the grapb-structured prompts by only koeping all neighbors' text attributes in the prompls. We then test the linearized prompls against the graph-structured prompts. Templates of both linearized and graph-structured prompts are shown in Table D
2. Rewire ego-graph. We randomly rewire the ego-graph by different strategies. Then we compare the performance of MPNNs and LLMs under each strategy.
Table 4: Comparison of classification accuracy between graph-structured prompts and lincarized prompts on ARXIV-2023. The performance difference is negligible between two prompt styles, implying that LLMs are treating prompts simply as linearized paragraphs.
Prompt Style
1-hop title 1-hop title
2-hop title 2-hop title
1-hop attention
Graph-structured prompt
71.1
67.3
69.6
67.7
74.7
Linearized prompt
70.9
69.1
70.8
68.2
74.9
Adversarial Experiment on Lincarizing the Ego-graph. To verify whether prompts are processed as linearized paragraphs, we create linearized version of k-hop title, k-hop title+labell and k-hop attention by stripping away descriptive text about the ego-graph structure from the original prompt. For instance, in the original k-hop title, a typical introduction like "It has the following neighbor papers at hop k:" is removed. In the linearized version, we condense this to a single paragraph comprising all neighbors' titles, as shown in the last row of Table We then compare the performance of the graph-structured and linearized prompts on ChatGPT. As indicated in Table g the results reveal minimal performance disparity across all five prompt styles after linearization.
notable finding is that in the I-hop attention calegory, even the elimination of text specifying neighbors' importance ranking ("It has the following important neighbors, from most related to least related") has little impact. These findings imply that LLMs tend to process prompts in lincarized paragraph format.
Adversarial Experiment on Rewiring the Ego-graph. We evaluate both MPNNs and LLMs in an adversarial setting where the ego-graph is randomly rewired using three different strategies: "Random" keeps 1-hop neighbors and randomly connects 2-hop neighbors to 1-hop neighbors; "Extreme" retains 1-hop neighbors and connects all h-hop neighbors to a random 1-hop neighbor; "Path" randomly connects all 1-hop neighbors into a path, as shown in Figure 2 For LLMs, we use the 2-hop title as the prompting style. The results in Table show that LLMs experience a notably smaller average performance drop compared to MPNNs when subjected to ego-graph rewiring. The average drop of LLMs is -0.25%, compared to -5.55% MPNNs. When the prompt encompasses all neighborhood textual information, surprisingly the explicit ego- ago-graph structure has minimal impact on LLMs' performance. LLMs' resilience to changes in ego-graph structures suggests that LLMs may process prompts more like paragraphs than graphs.
In summary, our study suggests that LLMs interpret inputs more as contextual paragraphs than as graphs with topological structures. By two adversarial experiments, we show that neither linearizing nor rewiring ego-graph has significant impact on the classification performance of LLMs.
3.4 Impact of Homophily on LLMs Classification Accuracy
In the precoding section, we established that LLMs understand the input prompts more as a lincarized paragraph. Thus, we hypothesize that relevance of these paragraph prompts to the target node might influence the predictive accuracy of LLMs. Here, we investigate related factor contributing the improved
7

---

Published in Transactions on Machine Learning Research (06/2024)
Original
Random
Extreme
Path
Figure 2: Example of rewiring ego-graphs for node 0. Three rewiring strategies evaluated: "random" keeps 1-hop neighbors and randomly connect 2-hop neighbors to 1-hop neighbors; "extreme" keeps 1-hop neighbors and connecls all 2-hop neighbors connect to random 1-hop neighbor; "Path" randomly connects I-hop neighbors as a path.
Table 5: Performance of MPNNs and LLMs under adversarial settings, where randomly rewire the ego-graph. The last column AAeerage Drop" denotes the average change of performance in three rewiring strategies compared to the original graph. A larger drop in the last column indicates greater influence from rewiring the ego-graph.
Dataset
Model
Original
Random
Extreme
Path
Average Drop
GON
84.6
85.2
78.4
SAGE
84.1
83.8
78.5
Cora
ChatGPT
68.3
68.6
68.6
0.6
LLaMA-2-7B
52.2
53.5
54.1
1.5
GCN
74.7
65.2
68.2
50.3
-10.5
SAGE
75.2
71.0
67.0
66.2
-7.1
Arxiv
ChatCPT
71.5
71.4
71.1
69.0
-1
LaMMA-2-7B
48.3
48.9
49.2
44.4
-0.8
GON
69.8
64.5
66.1
59.9
-6.3
SAGE
68.1
66.5
63.4
60.8
-4.5
Arxiv-2023
ChatCPT
68.7
69.0
69.1
67.8
0
LLaMA-2-7B
47.6
48.1
47.9
41.3
-1,8
performance after incorporating structural information, particularly homophily. Homophily, the tendency of nodes with similar characteristics to connect, is foundational for many MPNNs. In fact, the degree of homophily in a dataset often correlates with the efficacy of MPNNs in classification tasks (Zhu et al. 2020: Lim el al. 2021 Maurya et al. 2021 Given this significance, it becomes imperative to explore il and how homophily impacts the efficacy of LLMs in similar classification contexts, drawing potential parallels or contrasts with MPNN behaviors.
2021
Since LLM performs node-wise prediction over the neighborhood surrounding the target node, homophily ratio (Loveland et al. 2023) to measure the degree of homophily with respect to the target node. For prompt to predict the category of a target node, the local homophily ratio is defined the fraction of neighbors sharing the same groundtruth label as the target node over the total number of neighbors included in the prompt. Intuitively, a higher local homophily ratio signals scenarios where a node is surrounded by a greater proportion of neighbors from the same category.
local
The neighbor dropping experiment. We design controlled experiment to demonstrate the effect of local homophily ratio on prediction accuracy. We gradually drop neighbors in three different ways: a) drop the neighbors with same label as the target node; b) drop the neighbors with different label as the target node; and c) drop neighbors randomly. We include details about the neighbor dropping strategics in Appendix E.
The experimental results are shown in Figure 3 where we observe an evident trend: we selectively remove neighbors sharing the same labels, there's ' decrease in prediction accuracy. Conversely, discarding

---

Published in Transactions on Machine Learning Research (06/2024)
Arxiv-2023
Cora
Obgn-product
Performance (Accuracy)
0.8
0.90
0.75
0.85
0.7
0.70
0.80
0.65
0.6
0.75
0.60
0.70
0.5
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Percentage Dropped
Percentage Dropped
Percentage Dropped
drop same
drop different
drop random
Figure 3: Performance comparison of dropping neighbors using different strategies across ARXIV-2023, CORA, and OGEN-PRODUCT datasets. Three dropping strategies are evaluated: "drop same" removes neighbors with the same label as the target node; "drop different" removes neighbors with different labels as the target node; and "drop random" randomly selects neighbors for removal. When percentage 1, "drop same" strategy drops all same-label neighbors but preserves all different-label neighbors, and "drop different strategy drops all different-label neighbors but preserves all same-label neighbors. Details about the strategies are stated in Appendix E
Table 6: Point biserial correlation between local homophily ratio and prediction correctness across five datasets (p-values in brackets). Point biserial correlation ranges between [-1, 1], where value of 1 indicates a perfect positive relationship. A higher correlation value indicates that the local homophily ratio and prediction correctness are more positively related.
Prompt Style
ogbn-arxiv
cora 0.070 (0.106)
pubmed
arxiv-2023
ogbn-product
Zero-shot
0.440 (0.000)
0.278 (0.000)
0.367 (0.000)
0.387 (0.000)
1-hop litle+label
0.518 (0.000)
0.222 (0.000)
0.443 (0.000)
0.481 (0.000)
0.560 (0.000)
neighbors with different labels leads to an increase in accuracy. This selective dropping inherently modifies the local homophily ratio within the prompts. The results show that accuracy of predictions made by LLMs is positively related to local homophily ratio. similar experiment adding neighbors instead of dropping neighbors in Appendix E also shows similar trend. Combine this observation with the premise that LLMs actually understand the prompts a paragraph, we propose that the significance of homophily is intrinsic.
This is because LLMs benefit from structural information only when the neighborhood is homophilous, meaning the neighbors contain phrases related to the groundtruth label of the target node. Conversely, diminishing the local homophily ratio by excluding such neighbors can adversely affect prediction accuracy.
Correlation study. Building on the insights from the dropping neighbors experiment, we further investi- gate the relationship between local homophily ratio and the prediction correctness across different datasets. Each node possesses two key attributes: a) its local homophily ratio, which continuous random variable in [0, 1), and b) its prediction correctness, which is binary random variable (0 indicating an incorrect pre- diction and indicating correct prediction). To quantify the correlation between these two attributes, we employ the point biscrial correlation method [Kornbrot] 2014). This correlation coefficient ranges between -1 and 1, where a value of 1 signifies a perfect positive relationship. The results of our analysis across five datasets are detailed in Table D
For the CORA dataset, we observe no significant correlation when only the title used in prompts. However, positive correlation emerges when neighbors are included alongside the title. This suggests that the more homophily is incorporated into the prompt, the more accurate the prediction becomes.
9

---

Published in Transactions on Machine Learning Research (06/2024)
For the other datasets, positive correlation is evident in both the zero-shot and 1-hop tatle+llabel settings. In Table G zero-shot prediction (the one that doesn't use structural information at all) also showed high correlation with the homophily ratio of the node. This suggests a complicated mechanism for LLMs to perform better on homophilous nodes: those nodes are casier to be classified in the first place; the added structural information has some additional contributions. Homophilous nodes are easier to classify potentially because nodes that are not homophilous often blend various topics, which makes predicting their category more challenging than homophilous nodes.
In summary, findings underline the critical role of homophily in inftuencing LLM's text classification performance with extra structural information. The experiments and analyses consistently point to positive relationship between local homophily ratio and prediction correctness. It further suggests that homophily matters because, only with homophily, the local neighborhood can provide relevant phrases, thus improving the overall performance.
3.5 Influence of Structural Information on LLMs Under Varying Textual Contexts
In Sections 3.3 and 3.4| show that LLMs understand the prompt describing the ego-graph more paragraph. Moreover, the benefit of incorporating the structural information is positively related to how homophilous the ego-graph is. Building on these findings, we want to investigate when this benefit might deminish given a fixed set of neighboring nodes. In particular, we are examining the influence of the textual feature richness of the target node. Our study involves experiments on four node classification benchmark
datasets with textual node features: CORA (McCallum et al. 2000 Tu Getoor 2003) Sen et al. 2008
Yang al. 2016), PUBMED NNamata et al. 2012 Yang ct al. 2016). OGBN-ARXIV (Hu al. 2020 and
OGEN-PRODUCT (Hu al. 2020
Richness of textual node features. To examine how the richness of the target node's textual features affects text classification accuracy, we compare two different settings:
Rich tertual content. In this setting, the nodes are associated with abundant textual features. Specif- ically, in citation networks (CORA, PUBMED and OGBN-ARXIV), both the paper title and abstract are associated with each node as textual features. In the co-purchasing network (OGEN-PRODUCT)
both the product title and product content associated with each node as textual features. This
setting is adopted by several prior studies (Chen et al. 2023 Ye et al. 2023 Guo et al. 2023 Wang
lt al. 2023 He et al. 2023).
Searce teztual context. In this setting, the nodes are associated with limited textual features. In citation networks (CORA, PUBMED and OGEN-ARXIV), only the paper title is used as textual features. In product networks (OGEN-PRODUCT), only the product name is associated with each node as textual features. While this setting is less explored in the literature, it is of grea practical importance due to the prevalence of short texts in social networks (Alsmadi & Gan 2019). Such limited textual features present challenges like feature sparseness and non-standardization. reducing the effectiveness of traditional methods (Song et al. 2014). In such scenarios, we expect the structural information becomes more useful for the predictions.
Experimental results. The experimental results of different prompting methods under the two settings with different richness of textual context are shown in Table 7 We have the following observations: When LLMs are powerful enough, they only benefit from structural information when node feature are scarce: if the node has enough relevant phrases in its own features, the local neighborhood won't be useful anymore. For ChatGPT under rich textual context, the improvement from structural information minimal. While this improvement significantly larger when the node level features are scarce.
In conclusion, LLMs only benefit. from structural information when the target node does not contain enough phrases for the model to make reasonable prediction.
6leaae see Appendix R.1 for the details of the datasets.
10

---

Published in Transactions on Machine Learning Research (06/2024)
Table 7: Classification accuracy of ChatGPT API for the OGBN-ARNIV, CORA, PUBMED, and OGBN-PRODUCT datasets. denotes the improvements of best prompt style that leverages structural information over shot method. Best results are in bold.
Textual context
Prompt style
OGBN-ARXIV
CORA
PUBMED
OGBN-PRODUCT
Zero-shot
74.0
66.1
88.6
83.7
Few-shot
72.9
65.1
85.0
83.8
Zero-shot CoT
71.8
56.6
81.9
80.5
Rich
1-hop title+label
75.1
72.5
89.1
85.2
2-hop title+label
74.5
74.7
89.7
86.2
1-hop attention
74.7
72.5
88.8
86.2
1.1
2.5
Zero-shot
69.8
61.8
85.7
78.5
1-hop title
72.3
69.6
84.8
80.5
1-hop title=label
74.3
73.9
86.4
85.3
Scarce
2-hop title
71.3
69.9
86.2
80.6
2-hop title label
74.2
74.5
86.9
85.4
1-hop attention
71.3
74.7
85.1
83.9
4.5
12.9
1.2
6.9
4 Conclusions and Future Work
In conclusion, our study provides key insights into the application of LLMs in processing structured data, particularly in node classification tasks on text-rich graphs. In this study, we have adapted node classification datasets with textual features from graph learning benchmarks establish testbed for LLMs augmented dataset, show that data leakage is not the major contributor
with structured data. By curating of LLMs on common node classification benchmarks. Our findings also raise critical concerns regarding the actual depth of understanding that LLMs have of structured data. By two adversarial experiments, we show that LLMs actually do not understand the prompts as graphs structures. On the contrary, LLMs understand the prompts more as paragraphs with augmented keywords. As a consequence, LLMs only show improvement from structural information when the neighborhood is homophilous. Morcover, our findings suggest that when the target node itself contains wealth of relevant phrases, the additional structural information becomes redundant.
This study also opens several avenues for future research. Firstly, the findings of this study, as well as the new dataset curated by this work, establish a proper benchmark setup for more advanced methods to encode structural information for LLMs, such as finetuning or adapter training. Secondly, while we find that data leakage not major concern for the prompting methods examined this paper, is still possible that more advanced methods can elicit the memory of the LLMs from training corpus. We may need further investigation the data leakage issue when proceeding with evaluating other methods. Finally, imply that LLMs might be relying shallow, surface-level patterns rather than grasping the underlying relational complexity of graph structures. Future research may be aimed at developing methods that enable LLMs to deeply parse and comprehend graph topologies.
results
References
Rachith Aiyappa, Jisun An, Haewoon Kwak, and Yong-yeol Ahn. Can we trust the evaluation on ChatGPT? Proceedings of the 3rd Workshop on Trustworthy Natural Language Processing (TrustNLP 2023), pp. 47-54, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10.18653/v1 v05653/v1/203..... trustnlp-1.5. URL http:::://acaaaaooooog.... wttp:thhhooogyor//22223333 http://rrr/2....tuttp---11...
trustnlp-1.5
Issa Alsmadi and Keng Hoon Gan. Review of short-text classification. International Journal of Web Infor- mation Systems, 1552)1155-182, 2019.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanic Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss.
11

---

Published in Transactions on Machine Learning Research (06/2024)
Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, lyya Sutskever, and Dario Amodei. Language models are few-shot learners, 2020.
Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert- Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 21), pp.
2021.
Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang, Quantifying memorization across neural language models. arXiv preprint arXiv:2202.070 07646, 2022.
Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, et al. Exploring the potential of large language models (Ilms) in learning on graphs. arXiv preprint arXiv:2307.03393 2023.
Valerio Ciotti, Moreno Bonaventura, Vincenzo Nicosia, Pietro Panzarasa, and Vito Latora. Homophily and missing links in citation networks. EPJ Data Science, 5:1 14, 2016.
Colin B. Clement, Matthew Bierbaum, Kevin P. O'Keeffe, and Alexander A. Alemi On the use of arxiv as a dataset, 2019.
Debarati Das, Ishaan Gupta, Jaideep Srivastava, and Dongyeop Kang. Which modality should use text, motif, or image?: Understanding graphs with large language models. orXiv preprinl arXiv:2311.0950 0986622 2023.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometrie. arXiv preprint 1rv: 02428,, 2019.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1263-1272 PMLR, 06-11 Aug 2017. URL httts::/
mlr. wttppp/e/////wllseeeeeesee 1ww.aeerr1............ html
Jiayan Guo, Lun Du, and Hengyu Liu. Gpt4graph: Can large language models understand graph structured data? an empirical evaluation and benchmarking. arXiv preprint arXin:2305.15066 2023.
Jonathan Halerow, Alexandru Mosoi, Sam Ruth, and Bryan Perozzi. Grale: Designing networks for graph learning. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2523 2032-552222 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in neural information processing systems, 30, 2017.
Xiaoxin He, Xavier Bresson, Thomas Laurent, and Bryan Hooi. Explanations as features: Llm-based features for text-attributed graphs. arXie preprint arXiv:2305. 19523, 2023.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Teskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in meuraa information processing systems, 33:22118 2213222133122 2020.
Yuntong Hu, Zheng Zhang, and Liang Zhao. Beyond text: deep dive into large language models' ability on understanding graph data. arXiv preprint orXic:2310. 04,44, 2023.
Jie Huang, Hanyin Shao, and Kevin your personal information? Xix preprinl ar 2rxiv:2005.1 12628, 2022.
Chang. Are large pre-trained language models leaking
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint ar Xie: 609.00900000 02907, 2016.
12

---

Published in Transactions on Machine Learning Research (06/2024)
David Knoke. Political networks: the structural perspective, volume 4. Cambridge University Press, 1990.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199-22231 2022.
Diana Kornbrot. Point biserial correlation. Wiley StatsRef: Statistics Reference Online, 2014.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances Neural Information Processing Systems, 14:20887-20902 2021.
Donald Loveland, Jiong Zhu, Mark Heimann, Benjamin Fish, Michael T Shaub, and Danai Koutra. On performance discrepancies across local homophily levels in graph neural networks. arXiv preprint arXiv:2306.0m 05557,, 2023.
Qing Lu and Lise Getoor. Link-based classification. In International Conference on Machine Learning (ICML), Washington, DC, USA, 2003.
Jiaqi Ma, Xingjian Zhang, Hezheng Fan, Jin Huang, Tianyue Li, Ting Wei Li, Yiwen Tu, Chenshu Zhu, and Qiaozhu Mei. Graph learning indexer: A contributor-frienlly and metadata-rich platform for graph learning benchmarks. In Learning on Graphs Conference, pp. 7-1. PMLR, 2022.
Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. Improving graph neural networks with simple archi- tecture design. arXiv preprint erXix:2105.0m 076634, 2021.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Scymore. Autonating the construc- tion of internet portals with machine learning. Information Retrieval, 322):127-163, 2000.
Miller McPherson, Lynn Smith-Lovin and James M Cook. Birds of feather: Homophily in social networks. Annual review of sociology, 27(1):415 444, 2001.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. Advances in neural information processing systems, 26, 2013.
Frederic P. Miller, Agnes F. Vandome, and John McBrewster. Levenshtein Distance: Information The- ory, Computer Science, String (Compuler Science), String Metrie, Damerou@lewenshhein Distance, Spell Checker, Hamming Distance. Alpha Press, 2009. TSBN 6130216904.
Galileo Mark Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collec- tive classification. In International Workshop on Mining and Learning with Graphs (MLG), Edinburgh, Scotland, 2012.
OpenAI. Introducing chatgpt, 2022. URL http::///penii.com/blggg/ chatgpt
OpenAL. Gpt-4 technical report, 2023.
Alee Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Nyy Sutskever, et al. Language models are unsupervised multitask learners. OpenA/ blog, 1(8):9, 2019.
Prithviraj Sen, Galileo Namala, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collec- tive classification network data. Al magazine, (9(3):93 00993993.200 2008.
Ge Song, Yunming Ye, Xiaolin Du, Xiaohui Huang, and Shifu Bie. Short text classification: a survey, Journal of multimedia, 9(5), 2014.
Jiabin Tang, Yuhao Yang, Wei Wei, Lei Shi, Lixin Su, Suqi Cheng, Dawei Yin, and Chao Huang. Graphgpt: Graph instruction tuning for large language models. arXio preprint or Xiv:2300. 13023, 2023.
13

---

Published in Transactions on Machine Learning Research (06/2024)
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Maric-Amm Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Fric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint (rXim:2302.3397) 2023.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph allention networks. arXiv preprint arXiv:1710. 10903, 2017.
Ben Wang and Aran Komatsuzaki. GPT-J-6B: A Billion Parameter Autoregressive Language Model. jax, May 2021.
https://github.com httpss///gttaub..o///igsgtttoo https//wwww.a//iooooo/o///aaaaaa
Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language? arXiv preprint ar xrXi::335510037, 2023.
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chich-Han Han Wu, Yuxiao Dong, and Anshul Kanakia. Mi- crosoft academic graph: When experts are not enough. Quontitative Science Studies, 1(1):396-44) 2020.
Jason Wei, Xuezhi Wang, Dale Schnurmans, Maarten Bosma, Fei Xia, Fd Chi, Quoc V VLe Denny Zhou, et al. Chain--ffthought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 85:24824-24833 2022.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp- 40-48. PMLR, 2016.
Ruosong Ye, Caiqi Zhang, Runhui Wang, Shuyuan Xu, and Yongfeng Zhang. Natural language is all graph needs. arXiv preprint XrXiv:2308.00 07134, 2023.
Jianan Zhao, Le Zhuo, Yikang Shen, Meng Qu, Kai Liu, Michael Bronstein, Zhaocheng Zhu, and Jian Tang. Graphtext: Graph reasoning in text space. arXiv preprint arXi:2230. Xii:2310.01089, 2023.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances neural information processing systems, 33:7793- 7804, 2020.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI conference artificial intelligence, volume 35, pp. 11168-11176, 2021.
A Details about Prompting Format and Settings
We utilize a two-part prompt structure, in line with the CharGPT Chat Completions AP and LLaMA-2-7B format. Each call involves a system prompt and a user prompt. The system prompt., detailed in Table S LLM's objective and return format. The user prompt, outlined in Table [ provides information on the target node and its neighborhood for prediction. To standardize LLM's output format, append "Do not give any reasoning or logic for your answer" to the end of all prompts, except zero-shot CoT prompts.
Prompt styles. Here introduce the design of prompt styles in experiments. The exact prompt templates can be found in Table D
We first have a few prompt styles that do not encode structural information.
Zero-shot: LLMs make zero-shot predictions based on the target node's textual features only.
Few-shot: LLMSs make predictions on nodes' textual features only but with few-shot examples from the training set.
htttps///platform. openaii ptapa//ww..e.eeeeelall///////aar
14

---

Published in Transactions on Machine Learning Research (06/2024)
Zero-shot Chain-of- Thought (CoT); Adding "Let's think step by step" to the end of the zero-shot prompt (Kojima et al. 2022). This simple change has been shown to boost LLMs performance on various tasks comparable to CoT prompts (Wei et al. 2022).
Then we have two strategies for prompt design conceptually inspired by MPNNs, where information from neighboring nodes aggregated enhance the representation of the target node:
The first strategy incorporates randomly selected neighbors into the prompt. The idea behind this strategy is to aggregate information from neighboring nodes, following the paradigms of GCN (Kipf & Welling 2016) and GraphSAGE (Hamilton et al. 2017]. The inclusion of 1-hop neighborhood information in the prompt can be seen as an analogous operation to single-layer aggregation in GCN, where messages from direct neighbors are aggregated. Specifically, we have two styles:
k-hop title: LLMs make predictions based on the target node's textual features as well as titles of neighbors up to k-hop.
k-hop taael: In addition to k-hop title, we include the labels for neighbors in training set or validation set.
The second strategy is designed to weigh the influence of neighboring nodes during the prediction pro- cess. This strategy inspired by Graph Attention Networks (GAT) (Veličković et al. 2017), which employ attention mechanisms to dynamically allocate weights to neighboring nodes based on their task-specific im- portance. The strategy consists of two steps. a) Attention extraction: the LLM ranks neighbors based on their relevance to the target node. b) Attention prediction: the LLM makes predictions based the target node and top-ranked neighbors. We name the whole strategy k-hop attention in our experiment results.
Table 8: System prompts for each dataset.
Datasct
System Prompt
OGEN-ARXIV,
Please predict the most appropriate arXiv Computer Science (CS) sub-category for the paper. The predicted sub-category should be in the format 'es.XX'
ARXIV-2023
CORA
Please predict the most appropriate category for the paper. Choose from the fol- lowing Aategories:)nnulee Learning's Learniag.,Neurall nnNeural Networks pCsse Based GGenetic Algo- Methods)
rithms),nTheorg hnw.lrhhooooooyoooooooeeeeee Reiifoorremmnt "earring'
PUBMED
Please predict the most likely type of the paper. Your answer should be chosen from:)u diabetes n'Tye diabetes') diiabetessnEEpperfee |nExperimentally induced diabetes. {n
OGHN-PRODUCT
Please predict the most likely calegory of this product from Amazon. Your answer should chosen from the list: Hoome & Kitchen nHealth & Personal Care n....
We outline the details for each prompting method as follows:
Few-shot: Two correct example predictions from ChatGPT are added before the target node infor- mation.
Target node with neighbors: For datasets OGBN-ARXIV, CORA, PUBMED and ARXIV-2023, prompts include up to 20 one-hop and 5 two-hop neighbors. For OGBN-PRODUCT, up to onc-hop and 10 two-hop neighbors included.
3. Attention extraction: The maximum number of neighbors is the same Target node with neighbors. We only consider one-hop attention in this study, setting the attention number k to 5.
Common settings for all methods include a temperature of 0 and a maximum output token limit of 500. If neighbor belongs to the training validation set, its label is included in the prompt.
15

---

Published in Transactions on Machine Learning Research (06/2024)
B Datasets Information
In this section we detail the information about benchmark datasets and the collection pipeline of ARXIV- 2023.
B.1 Datasets Statistics and Splits
Table 9 presents basic statistios for each dataset. For detailed information on datasets and methods to obtain raw text attributes, please see Appendix A in Chen et al. (2023).
Table 9: Statistics of datasets. Data cut-off indicates the latest data coverage of the dataset.
Dataset
#Nodes
#Edges
# Task
Metric
#Test Nodes
Data Cut-OFi
CORA
2,708
5,429
Accuracy
542
2000
PUBMED
19,717
44,338
Accuracy
1,000
2000
OGBN-ARXIV
169,343
1,166,243
40
Accuracy
1,000
2019
OGBN-PRODUCT
2,449,029
61,859,140
Accuracy
1,000
2019
ARXIV-2023
33,868
305,672
40
Accuracy
668
2023
The dataset splits are as follows:
CORA: Training/ Training/Validationnn /VaaiidaaiioTeeetiin ratios are 0.1/0.2/0.2.
2. PUBMED; Training/Valldatiinnn Ialidattion/Testingg ratios are 0.6/0.2/0.2, following He et al. 2023
3. OGEN-ARXIV: Original OGB HHu et al. 2020) splits are used, categorizing papers by their publication year: training (pre-2017), validation (2018), and testing (2019).
4. OGEN-PRODUCT: Original OGB splits are used based on sales ranking: top 8% for training, next 2% for validation, and the remainder for testing.
5. ARXIV-2023: Year-based splits similar to OGBN-ARXIViS adopted: training (pre-2019), validation (2020), and testing (2023).
Due to API cost and rate limits, we test on random sample of 1,000 nodes for PUBMED, OGEN-ARXIV, and OGHN-PRODUCT, using a fixed seed for reproducibility.
B.2 Collection of arxiv-2023
The detailed pipeline is as follows:
Sample 668 test. nodes from around 46,000 arXiv CS papers published from January to August 22, 2023.
Extract references to identify one-hop and two-hop neighbors. References were obtained by two steps. First, we search for valid arXiv IDs within each paper, following method similar (Clement al. 2019). Second, we use AnyStyle extract the titles of the references which we then search for via the arXiv API Titles found arXiv are considered valid citations if they have small levenshtein distance (Miller et al.] 2009) from the searched title. To prevent duplicate searches, we skip any references that already have a matched arXiv ID. To comply with the arXiv API's rate limit, each paper restricted to a maximum of 30 searches. For papers published before 2019, we attempt to match them to nodes in the OGEN-ARXIV based on titles. Unmatched pre-2019 nodes are excluded from our datasct.
16

---

Published in Transactions on Machine Learning Research (06/2024)
3. Construct citation network using nodes from step 2. Basically for each node need list of paper it cites. While references for test nodes and one-hop nodes are obtained through both arXiv ID matching and title searching, the references for two-hop nodes are solely determined by arXiv ID matching, due to rate limit constraints. Dataset statistics are in Table We have similar test node degrees wet OGBN-ARXIV and ARXIV-2023.
C MPNNs as Baselines
Embedding generation. We adapt the embedding generation pipeline from Hu et al. (020)) to train a skip-gram model (Mikolov al. 2013) on corpus comprising titles and abstracts from both OGEN-ARXIV and ARXIV-2023. Each paper's 128-dinnnniioall feature vector is then obtained by averaging the word embeddings in its title.
Hyperparameter tunning. Baseline models GCN and SAGE are implemented with PyG (Fey & Lenssen 2019 For hyperparameter tunning, we perform random search on the following hyperparameter tuning range for every model following Ma et al. (2022)
Number of layers: (2,3).
Hidden size: 632.64).
Learning rate:
f.001, 001,.1..
Dropout rate:
f.2,.4, .6.
Weight decay: {.0001, 01,,
Each model run on 100 random configurations and cach random configuration is run for times on OGBN- ARXIV and ARXIV-2023. The max training epoch number 2000. When training finished, we use the model with highest average validation accuracy the dataset for testing.
D Additional Analysis on the influence of structural information LLMs.
D.1 Classification accuracy LLaMA-2-7B-char
The results in the main paper are based 3pt-3.5-turboo LLaMA-2-7B-chat. The results are shown in Table 10 The model gains significant improvement after incorporating structural information in both rich and scarce textual context. The results align with our ob- servation in the paper with ChatGPT that incorporating structural information actually brings performance improvement in both rich and scarce contexts. But a different observation that the improvement in scarce textual context is not necessarily higher than the improvement LLaMA-2-7B is able to sufficienlly leverage the entire text for the prediction in zero-shot prediction. Combining the results of ChatGPT, the conclusion is that, with powerful enough LLM and rich text (c.g. GPa with rich context), the structural information is marginal. But when the text information is scarce or if the LLM cannot fully utilize the text information, structural information can be significantly helpful.
Here test the performance of
rich textual context. This may be because
D.2 The Nuances of When Structural Information Saturates on LLMs and MPNNs.
We compare the performance increase from incorporating structural information for LLMs and MPNNs respectively in Table 11 The average increase from structural data of ChatGPT on 4 datascts 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 significantly higher than the gain of LLMs. means that The benefit of structural information saturates earlier on ChatGPT than MPNNs.
While it's true that structural information is generally more helpful when text scarce, quantitatively GhatGPT behaves differently from GNNs: the benefit of structural information saturates much earlier
17

---

Published in Transactions on Machine Learning Research (06/2024)
Table 10: Classification accuracy for the OGBN-ARXIV, CORA, ARXIV-2023, PUBMED, and OGBN-
PRODUCT datasets LLaMA-2-7B-chat 1 denotes the improvements of best prompt style that leverages structural information over zero-shot method. Best results are in bold.
Textual Context
Prompt Style OGBN-ARXIV
CORA
ARXIV-2023
PUBMED
DGEN-PRODUCT
Zero-shot
38.8
38.2
1-hop title
51.5
44.8
45.5
70.9
Scarce
1 1hhop latee+
58.0
71.0
53.4
75.5
78.9
19.2
46.5
15.2
5.4
27.2
Zero-shot
45.1
18.1
45.1
71.6
51.3
1-hop title
50.0
Rich
1-hop title I Habel
66.9
60.2
73.0
77.2
15.1
1.4
Table 11: Classification accuracy for the OGBN-ARXIV, CORA, ARXIV-2023, PUBMED on ChatGPT as well GCN, SAGE and MLP. 1 (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).
Textual Context
Prompt Style
OGBN-ARXIV
CORA
ARXIV-2023
PUBMED
Rich
Zero-shot
74.0
66.1
73.5
88.6
1-hop title+Hlabll
75.1
72.5
73.8
89.1
2-hop title+label
74.5
74.7
73.2
89.7
1-hop title label, attention
74.7
72.5
73.7
88.8
t (LLMs)
1.1
8.6
0.3
1.1
MLP
69.9
65.4
69.7
86.2
GCN
75.4
83.0
70.3
88.4
SAGE
75.0
83.2
70.9
90.0
(MPNNs)
5.5
17.8
1.3
3.8
Scarce
Zero-shot
69.8
61.8
1-hop title
72.3
69.6
70.7
80.8
1-hop title+label
74.3
73.9
70.4
84.7
2-hop title
71.3
69.9
68.9
83.5
2-hop title+tlabel
74.2
74.5
68.5
86.4
+ (LLMs)
4.5
12.7
4.1
0.5
MLP
61.9
55.7
58.5
82.0
GCN
74.8
81.2
70.3
87.1
SAGE
74.4
78.8
69.1
87.9
(MPNNs)
13.0
25.6
11.8
6.0
than GNNs with moderate rich textual features; and this is non-trivial since LLaMA-2 doesn't saturate as early as ChatGPT. The average increase from structural data on datasets for ChatPPT/MPNs//LLMMM 2-7B-chat are 2.78%/6.88%// 221 .7% respectively.
E
Additional Analysis for Dropping experiments
Details about dropping experiments. We have three different strategies: a) drop the neighbors with same label (drop same), b) drop the neighbors with different label (drop different), c) drop neighbors ran- domly (drop random). Let's define as the number of neighbors with the same ground truth label as the target node, and y as the number of neighbors with different label from the target node. Given dropping percentage p, elaborate on the three strategies:
drop random: We randomly drop (x y)p neighbors.
2. drop same: We retain max(r - (z + v)p, 0) neighbors with the same labels the target node while preserving all neighbors with different labels.
drop different: We retain max(y (a + y)p, 0) neighbors with the different labels from the target node while preserving all neighbors with same labels.
18

---

Published in Transactions on Machine Learning Research (06/2024)
1-hop title+label
1-hop title
1-hop label label
Performance (Accuracy)
0.75
0.75
0.75
0.70
0.70
0.70
0.65
0.65
0.65
0.60
0.60
0.60
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Percentage Dropped
Percentage Dropped
Percentage Dropped
drop same
drop different
drop random
Figure 4: Performance comparison of dropping neighbors using different strategies CORA dataset. Three
dropping strategies are evaluated: (1) 1-hop litle+ (ii) 1-hop title and (iii) 1-hop label
1-hop title+llbbll
1-hop title
1-hop label
Performance (Accuracy)
0.75
0.75
0.75
0.70
0.70
0.70
0.65
0.65
0.65
0.60
0.60
0.60
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Percentage Dropped
Percentage Dropped
Percentage Dropped
same
same
drop different
drop random
Figure 5: Performance comparison of dropping neighbors using different strategies on ARXIV-2023 dataset.
Three dropping strategies are evaluated: (i) 1-hop titlc+labol, (ii) 1-hop title and (iii) 1-hop label
We further explain this by an example. Assume node has 10 neighbors and 6 of the neighbors have same labels A. When dropping percentage is 0.5, drop same strategy drops 5 nodes with same label, resulting in 1 neighbor with same label and 4 neighbors with different labels. drop different strategy drops all 4 nodes with different labels, resulting in 6 neighbors with same label.
Ablation study the effect of labels in the prompt We investigate the possibility that LLMs are relying on a simple majority vote in its prediction. We propose new neighbor dropping experiment with three different prompting styles for neighbors: (i) I-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, which is used as an ablation study to gauge whether LLM performing a majority vote based on label information.
If LLMs do rely on majority vote to determine its prediction. We would expect that the "drop different curve with 1-hop label goes higher than 1-hop title+label because are dropping more and more neighbors with different labels. However, than 1-hop title+Hlaell 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+llbel "drop different" curve is higher than 1-hop label "drop different" " curve.
not observing this in Figure | and 5 and the 1-hop label curve is lower
Adding Neighbors instead of Dropping. To further investigate whether LLMs are benefiting from structural information, we conducted an additional experiment of adding neighbors instead of dropping neighbors. One could argue that adding neighbors that has different groundtruth labels the target node can still provide some benefits. The results is shown in o For all three datasets, adding neighbors with different labels will decrease the prediction performance.
19

---

Published in Transactions on Machine Learning Research (06/2024)
Arxiv-2023
Cora
Obgnnproduce
Performance (Accuracy)
0.90
0.75
0.75
0.70
0.70
0.80
0.65
0.65
0.75
0.60
0.70
0.60
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Percentage Added
Percentage Added
Percentage Added
add same
add different
add random
Figure 6: Performance comparison of adding neighbors using different strategics across ARXIV-2023, CORA, and OGEN-PRODUCT datasets. Three adding strategies are evaluated: "add same" adds neighbors with the same label as the target node; "add different. adds neighbors with different labels as the target node; and "add random" randomly selects neighbors for addition. When percentage is 1, "add same" strategy adds all same-label neighbors but excludes all different-label neighbors, and "add different" strategy adds all different-label neighbors but excludes all same-label neighbors.
F
Additional Analysis for Data Leakage
Investigating data leakage through prompt variability. Chen al. (2023) reveal considerable fluc- tuations in Language Model (LLM) performance on OGBN-ARXIVWhen using three distinct prompt words: 'arXiv subeategory," "arXiv identifier, and natural language. These variations have been interpreted potential indicators of data leakage.
To delve deeper into this issue, we expand upon their experiments by testing additional prompt words. We also introduce two experimental scttings: one with label options provided and another without. As displayed in Table [2] the relative efficacy of various prompts on OGBN-ARXIV mirrors their performance on ARXIV-2023. Importantly, prompts with options underperform on both datasets, underscoring a consistent trend.
Also, utilizing structural information in the prompts somewhat mitigate the performance drop from less effective prompts. Indicate that LLMs can leverage structural information to improve predictions. This further supports that there is no conclusive evidence for data leakage.
20

---

Published in Transactions on Machine Learning Research (06/2024)
Table 12: Performance across different prompt types between OGBN-ARXIV and ARXIV-2023.
Zera-shot
I-hop title+label
System Prompt
OGBN-ARXIV
ARXIV-2022 2023
OGEN-ARXIV
ARXIV-2U23
Please predict the most appropriate arXiv Computer Science (CS) sub-category for the paper. The predicted sub-category should be in the format 'es.XX:
74.0
73.7
74.3
70.4
Please predict the most appropriate arXiv Computer Science (CS) sub-category for the paper. Your answer should be chosen from cs.Al, .c..SY. The predicted sub-category should be in the format 'cs.XX.
66.0
68.1
70.7
67.9
Please predict the most appropriate original arXiv identifier for the paper. The predicted arxiv identifier should be in the format 'arxiv cs.xx!.
71.3
70.8
73.7
67.5
Please predict the most appropriate original arXiv identifier the paper. Your answer should be chosen from cs.ai,.. cs.sy. The predicted arxiv identifier should be in the format 'arxiv esxx!!
58.4
57.2
71.7
64.2
Please predict most appropriate category paper. Your answer should be chosen from "Artificial Intelligence"... ... "Systems Control".
54.6
53.4
74.1
21


Reviews:
[{"review_id": "tmT31ycC7X", "reviewer": "Reviewer_5tBU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n- Studying the ability of LLMs to understand graphs is an important question as it is not clear as of today to what extent text-only training provides LLMs with a sense of physical and spatial information, graph understanding falling in the second category.\n- The writing of the paper is mostly clear.\n- For each question, the described protocol seems sound which makes me confident about the paper’s conclusions. \n\nWeakness:\n\nIt seems to me that this work is in a sense incomplete: the title is \"Can LLMs Effectively Leverage Graph Structural Information through Prompts, and Why?\", but the conclusion is that LLMs do not seem to leverage this information for the particular task of study. \n\nHence, it is not clear to me whether this is because they do not understand graph structure well (because of the prompts, or intrinsic limitations), or because this information is just not useful for the task for LLMs (because their good text understanding is enough). Some further investigations might be missing, e.g. try new prompts or focusing on text-scarce or even no text graphs! \n\nThat being said, even a “negative” conclusion can be very valuable, and I would understand that the paper focus on text-rich graphs if this is an important task in general. Coud the authors elaborate on this and / or revise some claims / title?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work aims at understanding whether LLMs can leverage graph structural information in some prediction tasks on text-rich graph, such as node label. \n\nTo do so, the authors try to understand: \n\n- The role of data leakage and memorization through experiments on a newer version of ogbn-arxiv. I think this question is important for obvious reasons, and it makes sense, instead of trying to measure contamination, which is rather difficult, to just create “unseen” tokens.\n- Wether the LLM leverages structural information in the task prompt, mostly by comparing performance with or without graph structure information, or modifying it.\n- The importance of graph homophily in LLMs prediction. \n\nFor all these sub questions, a clear answer is provided. The conclusion is that LLMs do not really leverage this information for the task of study (text-rich graphs).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above: the paper is called \"Can LLMs Effectively Leverage Graph Structural Information through Prompts, and Why?\". To have an answer to this, it feels the authors should either:\n- Do follow-up experiments as to why graph structure seems not useful to LLMs for the task (better prompts? LLMs limitations? Graph info useless to LLMs for this task since text-rich?). Without this, the title of the paper should rather be something like \"LLMs do not leverage graph structural information through simple prompts for text-rich tasks\". \n- Or, bring some clarifications as to why focusing on this particular task and setup.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "S9jWwwYZR2", "reviewer": "Reviewer_UYwb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n- The use of adversarial experiments to probe LLMs' understanding of graph structures offers insights into how LLMs process structured information, contributing to the broader understanding of LLM capabilities and limitations in this topic.\n\n- Another strength of this paper is its investigation of the potential impact of data leakage on the performance of LLMs in processing graph-structured data for node classification tasks.\n\n## Weaknesses\n\n- The organization could be improved to better guide the reader through the research questions, methodologies, findings, and implications of the study. It seems that the authors investigated many topics (data leakage, graph structure impact in LLMs.), without going in-depth into any of those.\n\n- The reliance on a single dataset to derive conclusions about the impact of data leakage and the processing of structural information by LLMs limits the generalizability of the findings. Additional experiments with diverse datasets are necessary to strengthen the claims.\n\n- The paper lacks a solid theoretical framework to explain the observed phenomena, especially concerning the processing of graph structures and the role of homophily. The absence of a theoretical rationale makes it difficult to understand the underlying mechanisms at play. Moreover, the paper also doesn't provide strong experimental results.  This combination of theoretical and empirical shortcomings significantly limits the paper's contribution.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper explores the capability of Large Language Models (LLMs) to utilize structural information of graph data to improve prediction performance, particularly in node classification tasks on text-rich graphs.  Firstly, the authors create a new dataset to address concerns about data leakage potentially inflating LLM performance.  They conclude that LLMs interpret prompts more as linearized paragraphs than graph structures, and argue that LLMs do not benefit from the topological structure of the ego-graph.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Expand the experimental setup to include multiple datasets with varying characteristics and complexities, such as purely structural graph datasets without text information and larger graphs. \n- Conduct focused analyses to explicitly explore the role of homophily in the performance of LLMs on graph-structured data. This could involve controlled experiments where the degree of homophily within the graph data is varied.\n\nOverall, I think the paper makes some interesting claims and studies important problems such as data leakage in LLMS, and the impact of graph structure in LLMs. However, it seems to approach these topics at a surface level, lacking in-depth exploration and analysis in both the theoretical and experimental parts.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "H1FqtRKUdP", "reviewer": "Reviewer_H17Y", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n### [S1] New graph dataset of recent papers, avoiding data leakage\n\nThe authors provide a new dataset, arxiv-2023, designed to control for data leakage in language models. This dataset follows the construction of the obgn-arxiv dataset as closely as possible, but is restricted to recent CS papers, making it a useful dataset for comparing models that potentially trained on papers in the obgn-arxiv dataset.\n\n### [S2] Thorough experimental results\n\nThe paper includes many experimental results studying multiple aspects of model performance. The authors carefully compare results for multiple prompting strategies and for two baseline MPNNs, between obgn-arxiv and arxiv-2023, between different graph modifications, across different amounts of homophily, and across different amounts of text content.\n\n### [S3] Interesting analyses of homophily and amount of text context\n\nThe results about homophily and text content are interesting. The authors find that dropping neighbors to increase or decrease homophily leads to an increase or decrease in predictive accuracy, showing that LLMs are using homophily in their classification. They also somewhat surprisingly find that homophilous nodes are easier to classify even without including the neighbors, indicating some sort of correlation between homophily and ease of classification. For the impact of text context, the authors find that models improve more by including structural information when there is less textual context available in the node features.\n\n## Weaknesses\n\n### [W1] Misleading claims and confusing experiment design in Sec. 3.3 (\"treating the prompts as graphs\")\n*Edit: Addressed by the authors in the revised submission.*\n\nSection 3.3 is claimed to demonstrate that \"LLMs interpret inputs more as contextual paragraphs than as graphs with topological structures, which contradicts the intention of prompt designers\". Based on the experiments the authors describe, this seems misleading and not fully correct.\n\nIt's not clear to me that the cited previous works on this topic expect the LLMs to fully understand the graph topology, so it's not clear that the findings here are really a contradiction. As far as I can tell, all three of the papers the authors cite that encode the ego-graph as prompts (Chen et al., 2023; Guo et al., 2023; Hu et al., 2023) are already using a linearized representation. So it seems that those prompt designers are already intentionally treating the inputs as \"contextual paragraphs\" and aren't relying on the ability of the model to pick out specific edges between neighbors.\n\nAlso, from my understanding of the \"k-hop title\" format, the prompt template doesn't include the edges between the 2-hop neighbors and the 1-hop neighbors at all? So it seems like reconnecting 2-hop neighbors to different 1-hop neighbors (e.g. in the \"random\" or \"extreme\" settings) would not affect the prompt. If you aren't even telling the model about those edges in the first place, isn't it obvious that the model performance would stay the same when you change those edges? (It's also possible I'm misunderstanding the prompt format; I found Table 1 very hard to understand.)\n\nAnd even so, it's not clear to me why doing this rewiring would significantly change performance even if the model was fully capable of using graph information. Even the \"extreme\" setting seems to preserve the relative distances between the ego-node and each other paper. The exact connections between the 1-hop neighbors and the 2-hop neighbors seem relatively much less important, and I don't see why a model would benefit from paying attention to these connections.\n\nOverall it seems like the takeaway here is that the LLMs get good performance even without edge information? But this seems like a different claim than saying LLMs *don't* interpret the inputs as graphs with topological structures. Perhaps they are fully capable of using that information, but it's either missing or not actually useful in this task, so they don't use it.\n\n### [W2] Possibility of data leakage in ChatGPT experiment\n*Edit: Addressed by the authors in the revised submission.*\n\nThe authors state that ChatGPT's training cutoff is September 2021. However, the current training cutoff for ChatGPT appears to be at least April 2023 (see https://chat.openai.com/share/3b088460-86f8-4fa6-afd1-802b7f9a5e9f). I couldn't find any discussion of this in the paper. When did you query ChatGPT, and did you make sure that its reported training cutoff was indeed prior to the cutoff date of your arxiv-2023 dataset?\n\n(Note that this doesn't affect the LLaMA-2 results, so I don't think it significantly weakens the paper. Also, if there was a large amount of data leakage in obgn-arxiv, I would have expected it to be weaker for the 2023 data, even if the time windows overlap a bit. But it seems important to be precise here about how sure you are that there is not any data leakage.)\n\n### [W3] Somewhat overly-broad claims about homophily\n*Edit: Addressed by the authors in the revised submission.*\n\nAlthough I think the homophily experiment is interesting, I'm not convinced by all the claims about it. The authors state \"LLMs benefit from structural information only when the neighborhood is homophilous, meaning the neighbors contain phrases related to the groundtruth label of the target node\" and \"LLMs only show improvement from structural information when the neighborhood is homophilous\". I don't think the experiment provides direct evidence for this? The experiment shows that removing nodes with the correct label reduces performance, but I don't think it shows that the LLM is not benefitting at all from graph structure, relative to the zero-shot setting. Perhaps they are still providing some benefit, but it's just a much smaller benefit than the ones with correct labels.\n\nI think properly supporting this claim would require comparing the performance between having no structural information and having non-homophilous structural information. If you start from zero neighbors, and you selectively add non-homophilous nodes to the context, does performance actually go down, or does it just increase more slowly?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the ways in which adding graph structural information to a language model's prompt improves prediction performance, and compares LLM models to message-passing neural networks across a number of graph variants. The authors study three aspects of the performance: (1) the impact of possible data leakage in previous benchmarks, (2) the importance of the topological graph information in the LLM prompts, and (3) the impact of graph homophily and of textual node features on the model performance. To study these, the authors introduce a new arxiv-2023 with a low chance of data leakage, and conduct a number of comparisons between MPNNs, ChatGPT, and LLaMA-2. Overall, the authors find that data leakage is unlikely to be a large factor, that LLM models do not strongly depend on the topology within 2-hop neighborhoods, that homophily is correlated with LLM performance, and that LLMs rely less on the graph structure if textual node features are informative.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Before recommending this paper for acceptance, I think the authors should:\n\n- Modify the claims about the experiments in section 3.3 to reflect the type of prompts used by previous work.\n- Clarify how the edge information in the \"random\" and \"extreme\" settings is actually being used in the prompts, if it is at all, and why it would be expected to have an impact. (If the prompts are exactly the same for these settings, I think the experiment doesn't really show anything useful.)\n- Add details about when and how the ChatGPT data was collected, and whether there is any possibility of data leakage due to model updates after ChatGPT's initial launch.\n- Either reword the claims about homophily to make them more speculative or more precise, or include some extra experiments to show that including non-homophilous nodes is actually worse than including no structural information at all.\n\nBeyond this, I think there are some other ways the paper could be improved as well:\n\n- I think the homophily section would benefit from having more discussion of the \"complicated mechanism\" by which more homophilous nodes are easier to classify. Is there any hypothesis about what this mechanism is, or any other property that these nodes share?\n- The conclusion states that the results \"imply that LLMs might be relying on shallow, surface-level patterns rather than grasping the underlying relational complexity of graph structures\". This seems to make a strong assumption that the LLMs are missing some deeper structure. Perhaps the text information already contains enough information to infer the graph structure, so the model is already using the graph structure even if it isn't being provided? Or perhaps the graph structure is actually not very useful for this task. Given that the LLM is matching or outperforming the MPNNs in the 1-hop title+label setting, it seems possible that the LLMs are already using the graph structure as much as they need to. I think this possibility could be discussed more.\n- I found Table 1 to be very difficult to understand, and it seems somewhat incomplete. For instance, what does \"It is linked to paper <list of neighbor papers>... (more 1-hop neighbors)\" mean? Does each paper in the list have it's own \"It is linked to paper\" statement or is it just a list of paper titles? Is paper 1 necessarily  a 1-hop neighbor? Also, for \"It has following neighbor papers at hop 2:\", are you including any actual edges in the prompt? Can the LLM tell anything about the topology beyond the set of 1-hop and 2-hop neighbors?\n- Some typos: \"rigorours\" on line 85, \"introduces=\" on line 95.", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper was reviewed by three experts and received mixed ratings, with one reviewer recommending acceptance, one recommending weak acceptance and one rejection. The reviewers initially raised several concerns about misleading claims. For example, since the paper focuses only on text-attributed graphs, its findings cannot be generalized to other types of graphs. Moreover, no clear explanations were given about the relationship between homophily ratio and the performance of LLMs. Most of those concerns were addressed by the authors in the revision. I believe that the submission now meets the TMLR acceptance criteria, and thus, I am recommending acceptance.
Decision: Accept (poster)