Attention Mechanisms Perspective: Exploring LLM Processing of Graph-Structured Data

the bimodal trend mentioned in the text focuses on mean differences with t-tests while KS tests emphasize differences between overall distributions ("Given that the KS test focuses on the overall distribution and the t-test emphasizes the mean value:"). It would be better if relevant materials were provided as evidence.

Thank you for your suggestion. In paper [1], the KS test is compared with the Anderson-Darling test (both are distribution-based tests), pointing out that the KS test is sensitive to global differences in distributions, whereas the t-test focuses only on mean-based hypotheses.

[1] Chakraborti, S., & Lim, J. (2010). Comparing Distributions: The Two-Sample Anderson-Darling Test vs. the Kolmogorov-Smirnov Test. Journal of Applied Statistics, 37(1), 53–65.

In the Attention Window section of the paper, the authors mention training with k≠4 and then transferring to an attention window where k=4. When training with k≠4, will it introduce additional computational time consumption?

Thank you for your consideration. In our model's operation, we only modified the computation of the attention_mask by adding some masking (similar to causal masking). This has a negligible impact on the model's training speed.

The author designed a link information perturbation experiment (which is very interesting)， where the setup was based on gradually disrupting normal links. I wonder if there could be or if it's possible to add settings that enhance the link information?

First, your suggestion and idea are both highly feasible and significant. We have added an enhancement mode (V) to the perturbation experiment. Mode (V) uses a pre-trained GNN model to perform initial node filtering.

The specific results are as follows:

The experimental setup for (V) may require further consideration, and we will conduct more repeated experiments and validations in the future. Thank you for your valuable suggestions regarding the perturbation experiment.

Descriptions of the specific methods for calculating attention scores and conducting perturbation operations are not detailed enough.

Thank you for considering the reproducibility of the experiments. We will provide preliminary explanations here.

Calculating attention scores: In our padding operation, we chose to discard the calculation of attention scores for pad tokens because this does not contribute to node attention calculations. Additionally, to avoid potential interference, we directly masked these tokens in the attention_mask.

conducting perturbation operations：(II) Exchanging random numbers of child nodes between first-order nodes and further disrupting the information structure: Unlike (I), this operation involves transferring a random subset of child nodes between first-order nodes. Additionally, it introduces further disruptions to the overall structure.

(III) Randomly shuffling the positions of first-order and second-order nodes, even allowing original second-order nodes to become first-order nodes: This operation randomizes the hierarchy and positions of nodes, potentially altering their roles (e.g., promoting second-order nodes to first-order status).

In some of the experimental demonstrations (Figure 1,2,3,5), three datasetswere selected and showed different forms of performance. Could you comprehensively explain how these different datasets performed across multiple experiments?

We are happy to address your question. In our experimental demonstrations, the LLM exhibited strong performance on the Roman-Empire dataset (Table 2 - overcoming confounding factors, Figure 2 - enhancing attention scores for structural information). Additionally, in other visualization analyses, it demonstrated an understanding of graph structures. However, on other datasets (Pubmed, Wikics), the model showed disordered and difficult-to-understand behavior.

The article repeatedly mentions attention scores between different tokens. Can you elaborate on how these scores are specifically calculated? Are they calculated as normal attention layer scores? Are there any special cases?

As mentioned in our previous response, we selected datasets that the LLM could handle well (Roman-Empire) and those it struggled with (Pubmed, Wikics). The goal was to identify differences between the two and explore how the LLM successfully understood graph structures.

The appendix shows charts of attention scores for first-order nodes and their child nodes at different layers (Layer 1 and Layer 3). In deeper network layers, would this pattern of attention scores differ?

Indeed, during our experiments, we observed that the unique behaviors of deeper attention networks became more pronounced compared to shallower ones, such as the "attention sink" and "Skewed Line Sink."

Some professional or targeted concepts ("bimodal trend", Kolmogorov-Smirnov, etc.) are insufficiently described. It is hoped that explanations can be strengthened.

Thank you for pointing this out. Insufficient explanation of certain professional terms and concepts may indeed cause difficulties for readers. Below are more detailed explanations of the mentioned concepts:

Bimodal Trend: The appearance of a bimodal trend in the distribution of attention scores might indicate that the model pays particular attention to specific types of nodes or positions, while others form another cluster. Kolmogorov-Smirnov Test: This is a non-parametric test used to compare whether two samples come from the same distribution. The KS test is most commonly used to determine whether two sets of observations are significantly different or whether one set of observations differs significantly from a theoretical distribution.

In addition, we have further revised Attention Window and JS.

Although the authors have open-sourced the experiment code, reproducing the experiments still requires some hyperparameter settings. Detailed hyperparameter settings for each experiment are hoped to be provided by the authors.

Thank you for your thorough consideration. Due to the length constraints of the rebuttal, we have made corrections in the revised version.

Please discuss the prompts used and their impact on your findings. I see that Appendix J presents the prompt, but does not analyze the impact of changing it, especially because the assistant part can be significantly modified.

Thank you for your suggestions regarding the experimental section of our paper. We designed various Prompt formats for analysis and discussion, inspired by the recommended paper (TALK LIKE A GRAPH), and supplemented these into our experiments.

(1) Our standard prompt (Appendix J Prompt) (2) Adjacency. Using integer node encoding and parenthesis edge encoding. (3) Expert. Employing alphabet letters for node encoding and arrows as edge encoding. The encoding starts with “You are a graph analyst” (4) Incident. Using integer node encoding and incident edge encoding.

We conducted analyses for Table 2 (disruption experiment) and Figure 3 (attention distribution) from the paper.

The results of the disruption experiment (Table 2) are as follows. From the results, it can be seen that although different templates have varying model performances, the overall trend is consistent, showing utilization of link information specifically on the Roman dataset, while link information did not play a role on most other datasets. (PS: Our initial template (1) remains the best performing and makes the best use of link information.)

The visualization for attention distribution (Figure 3) has been placed in an anonymous link anonymous link

Additionally, it should be noted that the input method we selected (Appendix J Prompt) was inspired by LLaGa (ICML), InstructGLM (EACL). This is a recognized direct method within the research community to better assess the LLM's understanding of every node in the graph structure input. It possesses uniqueness in positional certainty: it will not cause changes in LLM understanding due to different embedding methods; graph structure position determinability: the graph location of nodes can be determined through prompts, and passes the WL-test.

The clarify of the paper can be significantly improved. For instance, what first-order and second-order nodes are is never introduced. From the context, sometimes it refers to first-order and second-order neighbors, while other times it is unclear.

Thank you for your revision suggestions. We have corrected the clarity throughout the paper and standardized the naming of first-order nodes.

Please change the running title in the submission, as it currently is Submission and Formatting Instructions for ICML 2025.

Thank you for your advice. We have revised this accordingly.

I think you should replace training with finetuning in Q1, as if I understand correctly you are not training the LLM from scratch.

We have revised the expressions throughout the paper to more accurately reflect fine-tuning, thanks for your suggestion.

Thank you for your valuable feedback. However, there seems to be some misunderstanding regarding our study's objectives. The content you claimed is missing is mentioned in the appendices. Below are our responses to clarify the points raised.

What does "node sampling configured as 8x8" mean?

Node sampling is a common technique in graph machine learning used for efficient model training. To avoid high computational costs associated with training on an entire graph, node sampling selects a subset of nodes and their neighbors for training. Specifically, we sample 8 neighbors for a central node (forming first-order nodes) and then sample 8 more nodes for each of these first-order nodes (forming second-order nodes). This results in a total of 1 (central node) + 8 (first-order nodes) + 64 (second-order nodes). For LLMs processing graph data, an 8x8 sampling configuration is widely considered reasonable [1][2].

This paper makes very general claims based on very specific experiments. It only considers one approach to inputting graphs into LLMs and then claims that LLMs don't understand graphs well.

The method we chose for input (Appendix J Prompt) is based on LLaMA (ICML) [1] and InstructGLM (EACL) [2], which are recognized by the research community as straightforward approaches that can better evaluate an LLM's ability to understand each node in graph-structured inputs. This method has unique positional properties: it does not alter the LLM’s understanding due to different embedding methods, offers graph structural position certainty (the graph position of a node can determine its prompt position, and vice versa), and can pass the WL-test. Additionally, we arrived at general conclusions after conducting extensive experiments, including perturbation tests, shuffling experiments, attention window analyses, and various visualization studies, which align with common research paradigms. Meanwhile, we have added experimental comparisons of different input methods under the first response to Reviewer pYJ8.

The paper reads as if the authors forgot to include a section on the model. Even after looking at the Appendix, I couldn't figure out how they input the graph connectivity to the LLM.

In lines 267-269, we reference LLaMA [1] and InstructGLM [2], foundational works in the LLM4Graph field that have gained broad acceptance. Detailed Prompt templates are provided in Appendix J, which is referenced in the "Other work in Appendix" section of the main text.

Many citations do not appear to be reviewed publications; almost all are from the past two years.

LLM4Graph is a rapidly evolving field where many impactful papers first appear on Arxiv. All 10 Arxiv references we cited have been accepted to conferences such as ICML, NIPS, and KDD, awaiting publication. Only 2 papers remain under review. Given that LLMs were introduced to the GNN community around early 2023, most citations are recent.

There is substantial literature on processing graphs with transformer architectures ("graph transformers"), which the authors seem unaware of.

It may be noted that we discuss the application of transformer architectures (not just LLMs) to graph data in Appendix C, referenced in the "Other work in Appendix" section of the main text.

Given the results, I conclude that this way of inputting graph connectivity simply doesn't work very well.

We agree that simply input methods may not yield optimal performance, but our aim was to straightforwardly analyze underlying issues rather than achieve sota results. Our chosen method serves as a recognized baseline for further research.

I don't see any U-shaped curves in Figure 3.

As explained in our paper, "attention towards node tokens exhibits a U-shaped distribution or slash trend." Lower attention scores for initial nodes are attributed to their position towards the end of the text, resulting in less pronounced U-shapes or trends leaning towards slashes, a common observation also noted in similar studies [3]. We maintained this representation without adjustments, as detailed in our text.

[1] Chen R, Zhao T, JAISWAL A K, et al. LLaGA: Large Language and Graph Assistant[C]//Forty-first International Conference on Machine Learning. [2] Ye R, Zhang C, Wang R, et al. Language is All a Graph Needs[C]//18th Conference of the European Chapter of the Association for Computational Linguistics, EACL 2024-Findings of EACL 2024. Association for Computational Linguistics (ACL), 2024: 1955-1973. [3] Hsieh C Y, Chuang Y S, Li C L, et al. Found in the middle: Calibrating Positional Attention Bias Improves Long Context Utilization[C]//Findings of the Association for Computational Linguistics ACL 2024. 2024: 14982-14995.