acceptodds
Withdrawn from ICLR 2027

Bridging Graph and Language Structures: Structure-Aware Fine-Tuning for Graph Reasoning with LLMs

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Serializing graphs as text enables large language models (LLMs) to perform graph reasoning, but structural differences between graphs and sequences limit effective use of graph information. We propose a structure-aware fine-tuning framework for decoder LLMs that addresses three key issues: insufficient global readouts, mismatch between sequence positions and graph relations, and unequal information aggregation under causal attention. The framework introduces hierarchical graph serialization to organize local and global structural information, structural role rotary position encoding to reduce permutation-sensitive positional bias, and a structural visibility mask with learnable attention biases to control information flow across edge, node, and graph levels. A thresholded readout decorrelation loss further encourages complementary global representations while retaining necessary information sharing. The framework requires no additional graph encoder and supports parameter-efficient fine-tuning of pretrained LLMs. Under the specified evaluation protocol, it improves macro-average accuracy by 20.88 and 14.11 percentage points on GraphInstruct and MolecularNet, respectively, over a recent attention-sink-based method, while achieving competitive performance on node classification and link prediction. Ablation studies further confirm the contribution of each component. These results demonstrate that jointly adapting graph serialization, positional relations, and structural information flow can substantially improve graph reasoning with LLMs.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
large language models, graph reasoning, graph serialization, structural attention, positional encoding, multiple readouts

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_3T1nOpenReview ↗
Rating
1(−1)
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper introduces a structure-aware fine-tuning framework for decoder-only LLMs. It is motivated by a widely discussed observation: serializing a graph imposes an arbitrary linear order on it, which misaligns positions with graph relations and biases aggregation by letting later tokens see more under causal attention. To address this, it provides a) summary and readout tokens, b) a role-based RoPE variant (SR-RoPE), c) a structural attention mask with learnable biases, and d) a decorrelation loss on the readouts. Evaluated on GraphInstruct, MolecularNet, node classification, and link prediction, the proposed framework is competitive with the listed baselines.

Critical strengths
  1. The method does not require a separate graph encoder.
  2. The presented empirical results appear competitive across the evaluated tasks and included baselines.
Critical weaknesses
  1. The narrative is not fluent, making the core methodologies harder to digest than they should be. As far as I can tell, the method splits the graph into isolated node blocks, like Block-Attention for RAG [1] or Set-LLM [2], with each block listing the node's incident edges to inject connectivity. These blocks do not propagate messages directly; cross-node information is combined through a single global readout step and causal generation. The remaining components, i.e., its core contributions (summary tokens, SR-RoPE, and structural mask), mostly refine how each block is encoded and read out by global tokens. As a result, the method appears more complex than its core idea requires.

  2. One core technical contribution of this paper is SR-RoPE. However, it mixes role and position into a single 1D coordinate (Eq. 4, 5), which may cause positional collisions for variable-length sequences. It is also unclear why roles need to enter RoPE, rather than using simpler role embeddings or attention biases. Moreover, the global-position term lets block order back into the encoding, weakening the paper's own motivation.

  3. The empirical results are not convincing. Important Graph-LLM baselines such as GOFA [3] are cited but missing from comparison. The reported Cora accuracy (51.62%) is significantly lower than GOFA's zero-shot performance (70.81%). This is possibly due to the collisions mentioned in W2 or the highly isolated masks. Also, the main baseline SLASH is a training-free method, while the proposed method is reported finetuned with LoRA (Sec. 3.1).

[1] Dongyang Ma, Yan Wang, and Tian Lan. Block-Attention for Efficient Prefilling. ICLR 2025.

[2] Beni Egressy and Jan Stühmer. Set-LLM: A Permutation-Invariant LLM. NeurIPS 2025.

[3] Lecheng Kong, Jiarui Feng, Hao Liu, Chengsong Huang, Jiaxin Huang, Yixin Chen, and Muhan Zhang. GOFA: A Generative One-For-All Model for Joint Graph Language Modeling. ICLR 2025.

Questions for authors
  1. Regarding balancing aggregation, one of the core motivations and design goals, why is it realized through only a single global readout?
  2. Can the authors provide results comparing with the simpler baseline, i.e., Block Attention + listing each node's incident edges within its block?
7 comments

Response to W1

Thank you for your suggestion. To address your concern that “the narrative is not fluent,” we have rewritten the introduction and the method description. Please refer to the revised manuscript for the details; the specific changes are shown in blue.

Overall, for the introduction, we have focused on revising the description of related work to highlight the limitations of existing research. In particular, we emphasize the theoretical differences between our work and the most closely related methods, GaLA, UniGTE, and SLASH. On this basis, we outline how our method addresses these limitations. The key revised paragraphs are shown below:

Prior work addresses different parts of this problem. Regarding graph serialization, [4] analyze the internal computation of decoder Transformer models through substructure extraction tasks.... Regarding positional encoding, [5] additionally assigns a shared position to graph tokens and uses structural biases and alignment tokens in an encoder–decoder framework.... Regarding attention aggregation, [6] analyzes distortions caused by linearization and RoPE, and adds graph distance attention biases to a frozen LLM. Such biases adjust scores on visible connections while retaining the backbone's positional coordinates.... we explore these three aspects further in Appendix A.

While the aforementioned studies have advanced the integration of graphs and LLMs through approaches such as graph serialization, positional encoding, and attention aggregation, they have yet to consider these three components as an integrated, cohesive whole. For instance, [6] focuses exclusively on attention aggregation by adjusting attention scores between graph tokens, yet it overlooks the influence of sequence organization and positional encoding....In reality, these three elements exist in a progressive, hierarchical relationship: the organization of a graph sequence serves as the foundation for both positional encoding and attention aggregation. Building upon this, positional encoding can mitigate a model's sensitivity to the specific order of graph tokens, while the attention aggregation mechanism dictates the visibility between these tokens.... Going a step further, we observe several limitations: in terms of graph serialization, current methods often lack an explicitly organized global readout position; regarding positional encoding, there is a misalignment between physical sequence positions and the underlying graph structural relationships; and concerning attention aggregation, the use of causal masking leads to inconsistencies in the visibility range of structural information. Appendix B provides further elaboration on these three limitations.

For the method section, we particularly agree with your summary of our method: “Building on hierarchical graph serialization, SR-RoPE and the structural mask mainly adjust the positional relationships and reading permissions among tokens, including edge summaries, node summaries, and global readouts.” Accordingly, we have mainly rewritten the first paragraph of the method section to clearly present the overall logic of our method. The key revised paragraph is shown below:

As shown in Figure 1, our structure-aware fine-tuning integrates graph hierarchies into a decoder LLM via four coordinated modules without any extra graph encoder. Our method follows a local-to-global computation: each node block lists incident edges, edge summaries feed a node summary, and multiple global readouts aggregate the node summaries. Different node blocks do not exchange hidden states directly. The hierarchical graph serialization (Section 2.1) provides a way to organize graph tokens, establishing a foundation for subsequent operations. SR-RoPE (Section 2.2) specifies which token positions retain local order and which summaries share a role anchor. Structural attention (Section 2.3) specifies the allowed reading paths and their biases. A thresholded decorrelation loss (Section 2.4) encourages distinct readout representations.

Response to W2

Thank you for your suggestion. Please allow us to clarify this issue.

(1) We agree that one-dimensional coordinates are not collision-free. In fact, we introduced “role anchors” in the original manuscript to address this issue. For example, when the global coefficient αci\alpha_{c_i} is zero, an NH token at local index 2 and an ER token at local index 2 both receive local coordinate 2. Although a positional collision occurs at this point, the coordinates of the NH and ER tokens change further because we introduce “role anchors.” Specifically, the new coordinate of the NH token is sNH=p⟨G⟩+1+softplus⁡(δNH)s_{\mathrm{NH}}=p_{\langle G\rangle}+1+\operatorname{softplus}(\delta_{\mathrm{NH}}); that is, the position of the graph start token, 1, and a positive number are added to the original coordinate 2. Similarly, the new coordinate of the ER token is sER=sNH+softplus⁡(δER)s_{\mathrm{ER}}=s_{\mathrm{NH}}+\operatorname{softplus}(\delta_{\mathrm{ER}}); that is, a positive number is added to the last sNHs_{\mathrm{NH}}. We noticed that Equation (5) did not describe this point rigorously enough and have corrected it in the revised manuscript. We hope this explanation addresses your concern.

(2) Regarding “why roles need to be introduced into RoPE and why simpler role embeddings are not used,” we hope the following explanation resolves your confusion:

Standard RoPE directly uses global physical sequence positions. This mechanism is naturally suited to language sequences because word order and relative distances usually carry actual semantic meaning. However, different regions of a serialized graph have different ordering properties. Specifically, natural-language queries and answers have a strict semantic order, as do the contents of an individual edge record. In contrast, the multiple incident edges of the same node, different node summaries, and multiple global graph readout tokens are inherently closer to unordered sets. If all tokens use a uniform physical-position scheme, tokens that have no semantic order in the graph structure will be incorrectly assigned relative distances. For example, multiple edge summaries within a node block are inherently closer to an unordered set and do not require explicit positional attributes. Different orderings of the edge records within a node block change the positions of the edge summaries, which in turn change the attention scores assigned to them by the node summary. It is therefore necessary to reduce the differences in relative positions between a node summary and all edge summaries within the same node block.

On this basis, we further introduce “roles” into RoPE to distinguish different regions of the graph sequence. We use an explicit set of rules, based on the inherent general relationships among roles, to determine role embeddings and accommodate different “relative-position requirements.” In contrast, simple role embeddings, such as randomly initialized embeddings, may deliberately distinguish “roles” at the beginning of training, but the differences among these “roles” will become blurred as training progresses because there are no explicit rule-based constraints.

(3) Regarding the concern that “global positions weaken the paper's own motivation,” we fully agree with your perceptive observation. We must acknowledge that global positions do weaken the paper's motivation to some extent. At the same time, we would like to clarify that this weakening is relatively limited in magnitude and is controllable. On the one hand, as stated in Equation (4), only the Global role retains the full global position, and this part accounts for a relatively limited proportion of the entire graph sequence. On the other hand, in Equation (4), only NH and ER have weighted global positions, whereas ES, NS, and U, which are more closely related to reasoning, have no global positions at all.

Response to W3

Thank you for your suggestion. Please allow us to clarify this issue.

(1) First, we explain the “performance difference between our method and GOFA”:

For the first stage of large-scale pretraining, GOFA uses data from MAG240M, Arxiv, PubMed, Wikikg90mv2, Ultrachat200k, and WikiGraph. Each epoch contains 935,000 sampled training instances, and there are three epochs, giving approximately 2.805 million instance presentations in total. In contrast, our pretraining data come from seven of the following eight datasets: Wisconsin, Cornell, Citeseer, Cora, Pubmed, Amazon-Computers, Amazon-Photos, and Texas. When testing on Cora, for example, the other seven datasets, excluding Cora, serve as the training set. These eight datasets contain a total of 26,839 samples; detailed statistics are provided in Table 15. Therefore, our method and GOFA are not on the same scale in terms of pretraining. In particular, Arxiv, which is closely related to Cora, itself contains approximately 169,000 nodes, over one million edges, and as many as 40 classes.

For the second stage of instruction tuning, although GOFA does not train or fine-tune on the test dataset, it still performs extensive instruction tuning on its pretraining datasets. For example, it performs “natural-language instruction–answer” instruction tuning on 80,000 Arxiv samples. By comparison, our method follows the R-GFM setting: we do not perform “natural-language instruction–answer” instruction tuning on the pretraining datasets, and instead select only one sample per class from the target test dataset for such instruction tuning.

In summary, the performance difference between our method and GOFA on the same test dataset does not arise from the models themselves, but rather from different data splits and training settings. Nevertheless, we did overlook a comparison with GOFA, and we sincerely appreciate this constructive suggestion. In the revised manuscript, we have added a comparison with GOFA (Graph Foundation Models) under our experimental configuration. The detailed results are shown below and correspond to Tables 7, 8, and 9 in the revised manuscript:

Node classification

MethodWisconsinCornellCiteseerCora
GOFA34.26 ± 2.1432.07 ± 3.0637.46 ± 4.1043.36 ± 1.92
MethodPubmedComputersPhotosTexasAvg.
GOFA47.24 ± 3.6748.60 ± 3.7658.13 ± 6.7629.53 ± 1.2241.33

Link prediction

MethodWisconsinCornellCiteseerPubmed
GOFA81.45 ± 1.3282.66 ± 1.0989.07 ± 1.2486.37 ± 0.73
MethodCoraPhotosTexasAvg.
GOFA86.09 ± 0.6480.35 ± 0.8085.26 ± 1.5184.46

(2) Second, please allow us to explain the concern that “the main baseline, SLASH, is a training-free method, whereas the proposed method is reported to have been fine-tuned with LoRA”:

As stated in RQ1 in Appendix E, “How does our method perform with decoder LLMs across different model families and parameter scales?” The main purpose of Section 3.2.1 is to verify whether our method consistently improves performance across different LLMs, whereas comparisons with other models are presented in Section 3.2.2. We fully understand your confusion. In fact, our primary purpose is to compare against the Vanilla results already reported in SLASH, while SLASH itself serves more as an additional point of comparison.

Response to Q1

Thank you for your suggestion. Please allow us to address your confusion. In fact, the “balance” we seek refers to “equality in the scope of aggregation”: each readout unit can see the complete set of node summaries but cannot see the other readout units, while each node summary can see all edge summaries within its own block but cannot see content in other node blocks. This design aims to eliminate the asymmetric prefix-access pattern inherent in LLMs. The “global readout” is actually one of the components that serve this motivation. In fact, the “global readout” in our method consists of multiple tokens, each of which performs a “global readout” with the same visibility scope.

Response to Q2

Thank you very much for this constructive suggestion. We fully agree that this is a crucial simple baseline. In fact, your suggestion also reflects Reviewer ohrD's observation that “sequential component-addition experiments measure only conditional increments under a particular ordering and cannot clearly identify the independent contributions or interactions of individual components,” especially the “Structural Mask” component. To address this issue, we fix “Hierarchical serialization” and “SR-RoPE” and design four simpler comparison baselines for the “Structural Mask” component: fully causal attention among all tokens within node blocks and across node blocks, with all other parts following the “Structural Mask” setting (denoted Causal-All); fully causal attention among all tokens within each node block, with all other parts following the “Structural Mask” setting (denoted Causal-Intra); fully causal attention across all node blocks, with all other parts following the “Structural Mask” setting (denoted Causal-Inter); and our Structural Mask. The experimental results are shown below and correspond to Section 3.3 and Appendix K.2 of the revised manuscript:

Llama-3.1-8B

Attention maskGIMNNCLP
Causal-All0.4150.71738.3783.39
Causal-Inter0.4340.73742.1184.72
Causal-Intra0.4450.74042.0285.66
Structural Mask0.5050.78046.1886.82

Qwen3-8B

Attention maskGIMNNCLP
Causal-All0.3360.60039.7184.27
Causal-Inter0.3880.63443.5085.06
Causal-Intra0.3850.62544.4886.02
Structural Mask0.4650.72546.9287.04
Reviewer_1BLjOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a structure aware fine tuning framework for graph reasoning with decoder LLMs, addressing differences in readout organization, positional dependencies, and prefix visibility. The framework integrates hierarchical graph serialization, structural role rotary position encoding, structural attention, and a thresholded readout decorrelation loss without introducing an additional graph encoder. Experiments across multiple backbones report improved macro average accuracy on GraphInstruct and MolecularNet and competitive performance on node classification and link prediction under the specified evaluation protocols.

Critical strengths
  1. The framework connects the stated differences between graphs and sequences to concrete changes in serialization, positional relations, and attention information flow.
  2. The method requires no additional graph encoder and supports parameter efficient fine tuning of pretrained decoder LLMs.
  3. The evaluation covers multiple Llama and Qwen3 backbones and four task categories.
Critical weaknesses
  1. The reported accuracy gains over SLASH rely on published results obtained with different training budgets and preprocessing pipelines. Matched evaluations should report accuracy, adaptation cost, inference latency, realized token counts, and peak GPU memory under the same inputs and hardware.
  2. The absence of direct or controlled comparisons with UniGTE and GaLA makes it difficult to assess the additional gains over existing structural adaptation methods.
  3. The answer region can directly read the graph description, and global readouts can access it through the graph end marker, leaving the contribution of hierarchical aggregation unclear. Ablations that remove these connections separately under matched token counts and training budgets would help distinguish the contributions of hierarchical summaries and these alternative paths.
Questions for authors

See Critical Weaknesses

3 comments

Response to W1

Thank you for your suggestion. This suggestion is essentially consistent with Comment 3 from Reviewer ohrD. Please allow us to explain again the use of “different training budgets and preprocessing pipelines.” In fact, the “training budget” and “preprocessing pipeline” are primarily constrained by the “organization of the graph sequence.” Since the “organization of the graph sequence” is itself an important component of our proposed method, we must use the “training budget” and the “preprocessing pipeline” to transform the data into the sequence organization predefined by our method. In fact, different methods each have a specific “organization of the graph sequence”; for example, UniGTE organizes the graph sequence by directly concatenating all nodes in a subgraph. The “training budget” and “preprocessing pipeline” determined by this “organization of the graph sequence” are themselves a core module of the proposed method. For this reason, we did not deliberately control the training budget and preprocessing pipeline, because these two elements can themselves be regarded as a particular kind of “structural mechanism.”

In addition, we note that the improvements over SLASH reported in the original manuscript actually combine differences in adaptation, preprocessing, and architecture. In the revised manuscript, we will emphasize this particular kind of “structural mechanism” to prevent readers from interpreting the improvements as arising from model architecture in the conventional sense. We have added explanations of this issue in Section 3.1 and Appendix E.3 of the revised manuscript, with the changes shown in blue.

Response to W2

Thank you for your suggestion. We have included GaLA (Prompt-based Adaptation) and UniGTE (Graph Foundation Models) in the comparisons in Section 3.2.2 of the revised manuscript. As shown in the tables below, which correspond to Tables 7, 8, and 9 in the revised manuscript, GaLA considers only “attention aggregation,” whereas UniGTE considers both “attention aggregation” and “positional encoding.” In comparison, our method progressively considers all three aspects—“sequence organization, positional encoding, and attention aggregation”—and therefore demonstrates stronger competitiveness.

Node classification

MethodWisconsinCornellCiteseerCora
GaLA33.51 ± 2.4431.54 ± 4.8639.60 ± 3.3644.78 ± 3.17
UniGTE34.21 ± 6.7234.67 ± 5.3353.49 ± 6.0846.15 ± 5.34
MethodPubmedComputersPhotosTexasAvg.
GaLA46.05 ± 1.9547.13 ± 2.5258.16 ± 0.7328.64 ± 2.3141.18
UniGTE48.06 ± 5.6750.68 ± 6.8258.84 ± 7.5030.55 ± 4.6544.58

Link prediction

MethodWisconsinCornellCiteseerPubmed
UniGTE77.52 ± 2.3681.08 ± 1.4690.56 ± 2.3586.73 ± 0.92
MethodCoraPhotosTexasAvg.
UniGTE88.34 ± 0.7881.27 ± 1.3680.96 ± 2.0483.78

Response to W3

Thank you for your suggestion. Your observation is very accurate. As you noted, both the “global readouts” and the “answer region” can access all graph information, and the absence of an ablation on the “global readouts” weakens the evidence for their contribution. In the revised manuscript, we have designed the following ablation on the “global readouts”:

Starting from the complete model, we design a 2×22\times2 intervention with two independent switches: one controls the “answer region's” access to the “global readouts” (Allow or Deny), and the other controls the “answer region's” access to the “graph end marker” (Allow or Deny). This intervention can be used to verify the independent contributions of the “global readouts” and the “graph end marker” to the final prediction. The experimental results are shown below and correspond to Appendix K.3 of the revised manuscript:

Llama-3.1-8B

Answer access to global readoutsAnswer access to graph end markerGIMNNCLP
DenyAllow0.5110.78445.9586.46
DenyDeny0.5080.77946.0286.43
AllowDeny0.5260.79346.6987.25
AllowAllow0.5280.79646.7587.37

Qwen3-8B

Answer access to global readoutsAnswer access to graph end markerGIMNNCLP
DenyAllow0.4710.72847.0487.20
DenyDeny0.4750.72646.9887.13
AllowDeny0.5100.77647.7187.47
AllowAllow0.5110.78547.7687.50

I appreciate the authors' efforts in the rebuttal. It has resolved some of my confusion. However, the cost measurement aspects remain unaddressed, for example, token counts and inference latency.

After considering the reply, I'd like to maintain my score.

Thank you for the follow-up and for acknowledging the clarifications in our rebuttal. We respect the reviewer's decision to maintain the score and thank the reviewer again for the careful evaluation.

Reviewer_ohrDOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a structure-aware fine-tuning framework for graph reasoning with decoder-only LLMs. It integrates hierarchical graph serialization, structural role rotary position encoding (SR-RoPE), structural attention, and a thresholded readout decorrelation loss. Experiments across multiple graph reasoning benchmarks demonstrate promising performance improvements.

Critical strengths
  1. The paper addresses an important problem concerning the structural mismatch between graph representations and sequential language models.

  2. SR-RoPE provides an interesting approach to mitigating permutation-sensitive positional biases, while structural attention enables hierarchical information aggregation.

  3. The experiments cover multiple backbones and graph tasks, with substantial performance improvements and useful component-wise ablations.

Critical weaknesses
  1. Several components, including hierarchical aggregation, structural attention masks, and representation decorrelation, build upon established techniques. The paper should more clearly distinguish its contributions from closely related works such as UniGTE and GaLA. In particular, I would appreciate a more explicit discussion of which limitations of these existing approaches are addressed by the proposed framework and why the proposed designs are necessary. If the authors can convincingly demonstrate that their method addresses important challenges left unresolved by these prior works, I would be willing to reconsider my assessment of the paper’s novelty and potentially raise my score.

  2. Although SR-RoPE aims to improve permutation robustness, the paper provides no formal guarantees or sufficiently rigorous analysis of its structural properties.

  3. Comparisons with published baselines do not fully control for training budgets and preprocessing pipelines, making it difficult to attribute the reported improvements solely to the proposed structural mechanisms.

  4. The sequential ablations demonstrate incremental improvements but do not adequately isolate the contributions and interactions of individual components. Comparisons with simpler positional encoding and attention masking alternatives would strengthen the claims.

Questions for authors

Please refer to the weaknesses.

3 comments

Response to W1

Thank you for your suggestion. We agree that individual concepts such as “hierarchical graph serialization,” “structural masks,” “aggregation tokens,” and “decorrelation” have appeared in existing work. However, we would like to clarify that these individual concepts are often scattered across different studies and lack a systematic treatment. We explain this in detail from the following two perspectives:

(1) First, we explain the differences in theoretical mechanisms between our work and GaLA and UniGTE:

For a pair of nodes (A,B) directly connected in the graph but far apart in the token sequence: GaLA addresses this only via attention aggregation—introducing an attention bias (reciprocal of shortest-path distance) to adjust attention scores—but overlooks how sequence organization and positional encoding affect attention. Even with this bias, GaLA cannot guarantee that the attention score between A and B remains unchanged under different sequence organizations, since their positional encodings differ. UniGTE also introduces an attention bias, and further recognizes that different sequence organizations change relative positional encoding; it removes all relative positional information (sets RoPE to zero) to eliminate order sensitivity. However, this completely disregards linguistic order within the graph—e.g., a directed edge inherently has an order analogous to language, and fully removing relative positional information is overly absolute.

In contrast, our method integrates sequence organization, positional encoding, and attention aggregation into a cohesive whole: Section 2.1's sequence organization provides a foundation for the latter two; Section 2.2's positional encoding removes order sensitivity only for specific graph tokens; and Section 2.3's attention aggregation introduces attention biases through visibility among graph tokens, since positional encoding determines only positional relationships and cannot change the scope of information visibility imposed by the causal mask. We have strengthened discussion of these differences in the Introduction and Related Work, with changes shown in blue.

(2) In addition, we have included GaLA (Prompt-based Adaptation) and UniGTE (Graph Foundation Models) in the comparisons in Section 3.2.2. As shown in the tables below, which correspond to Tables 7, 8, and 9 in the revised manuscript, GaLA considers only “attention aggregation,” whereas UniGTE considers both “attention aggregation” and “positional encoding.” In comparison, our method progressively considers all three aspects, and therefore demonstrates stronger competitiveness.

Node classification

MethodWisconsinCornellCiteseerCora
GaLA33.51 ± 2.4431.54 ± 4.8639.60 ± 3.3644.78 ± 3.17
UniGTE34.21 ± 6.7234.67 ± 5.3353.49 ± 6.0846.15 ± 5.34
MethodPubmedComputersPhotosTexasAvg.
GaLA46.05 ± 1.9547.13 ± 2.5258.16 ± 0.7328.64 ± 2.3141.18
UniGTE48.06 ± 5.6750.68 ± 6.8258.84 ± 7.5030.55 ± 4.6544.58

Link prediction

MethodWisconsinCornellCiteseerPubmed
UniGTE77.52 ± 2.3681.08 ± 1.4690.56 ± 2.3586.73 ± 0.92
MethodCoraPhotosTexasAvg.
UniGTE88.34 ± 0.7881.27 ± 1.3680.96 ± 2.0483.78

Response to W2

Thank you for your suggestion. Please allow us to clarify this issue. In fact, at an early stage of this work, we developed a rigorous formal proof of permutation invariance. However, as stated in Equation (4) in Section 2.2.1, the ordering of tokens with set-like roles generally carries no structural semantics, and we therefore want their attention scores to be unaffected by positional factors. We further generalize αc\alpha_c and βc\beta_c to learnable scaling factors for different roles. Clearly, this condition can break permutation invariance. This consideration made us hesitate over whether a rigorous proof of permutation invariance was necessary, which is also why we claimed “permutation robustness” rather than “permutation invariance” in the paper. Your suggestion has convinced us of the necessity of this proof. In the revised manuscript, we provide the proof in Appendix L and describe its scope of applicability in detail.

Response to W3

Thank you for your suggestion. Please allow us to explain why “training budgets and preprocessing pipelines are not fully controlled.” In fact, both the “training budget” and the “preprocessing pipeline” are primarily constrained by the “organization of the graph sequence,” as discussed in our response to W1. Since the “organization of the graph sequence” is itself an important component of our proposed method, we must use the “training budget” and the “preprocessing pipeline” to transform the data into the sequence organization predefined by our method. Different methods each have a specific “organization of the graph sequence”; for example, UniGTE organizes the graph sequence by directly concatenating all nodes in a subgraph. The “training budget” and “preprocessing pipeline” determined by this “organization of the graph sequence” are themselves a core module of the proposed method. For this reason, we did not deliberately control the training budget and preprocessing pipeline, because these two elements can themselves be regarded as a particular kind of “structural mechanism.”

Response to W4

Thank you for your suggestion. We agree that “sequential component-addition experiments measure only conditional increments under a particular ordering and cannot clearly identify the independent contributions or interactions of individual components.” In particular, the utility of an added component may arise from its “interactions” with other components rather than from the component itself. As stated in Section 3.3 of the original manuscript, we were already aware of this issue at submission, but the corresponding experiments had not yet been completed. We therefore emphasized this limitation in the original manuscript. During the review period, we completed these experiments. In the revised manuscript, we have added them in full in Section 3.3, Appendix K.1, and Appendix K.2. A brief description follows:

We fix “Hierarchical serialization” and conduct ablations on “positional encoding.” We then fix both “Hierarchical serialization” and “SR-RoPE” and conduct ablations on the “attention mask.”

(1) For the “positional encoding” comparison, we consider four alternatives: sinusoidal positional encoding, linear bias, RoPE, and our SR-RoPE. The experimental results are shown below:

Llama-3.1-8B

Positional encodingGIMNNCLP
Sinusoidal0.3320.64736.2681.47
Linear bias0.3790.70539.0382.46
RoPE0.3850.69538.5683.28
SR-RoPE0.4450.74042.0285.66

Qwen3-8B

Positional encodingGIMNNCLP
Sinusoidal0.2400.47337.1482.81
Linear bias0.2920.54740.9284.69
RoPE0.3050.52539.1284.36
SR-RoPE0.3850.62544.4886.02

(2) For the “attention mask” comparison, we consider four alternatives: fully causal attention among all tokens within node blocks and across node blocks, with all other parts following the “Structural Mask” setting (denoted Causal-All); fully causal attention among all tokens within each node block, with all other parts following the “Structural Mask” setting (denoted Causal-Intra); fully causal attention across all node blocks, with all other parts following the “Structural Mask” setting (denoted Causal-Inter); and our Structural Mask. The experimental results are shown below:

Llama-3.1-8B

Attention maskGIMNNCLP
Causal-All0.4150.71738.3783.39
Causal-Inter0.4340.73742.1184.72
Causal-Intra0.4620.74944.1685.90
Structural Mask0.5050.78046.1886.82

Qwen3-8B

Attention maskGIMNNCLP
Causal-All0.3360.60039.7184.27
Causal-Inter0.3880.63443.5085.06
Causal-Intra0.4070.67844.7186.53
Structural Mask0.4650.72546.9287.04

Dear Reviewer ohrD,

The authors posted the rebuttal. Please read the rebuttal and respond. Please also check whether the rebuttal addresses your concerns.

Best regards, Your AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.