acceptodds
Under review as a conference paper at ICLR 2027

Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers

Abstract

Transformers have become a central architecture for graph learning, but their application to graphs requires first choosing a tokenization: a graph-to-token map that determines which structural information is exposed at the input. In this work, we show that this choice is a fundamental component of transformer expressivity. We examine three tokenizations that serve as building blocks for many existing graph tokenizations: spectral, random-walk, and adjacency tokenizations. We prove that different tokenizations induce distinct depth regimes: the same graph computation may be realizable by a shallow transformer under one tokenization, while requiring substantially larger depth under another. For example, we prove that random-walk tokenization is lossy for any walk length, making it impossible in general to recover the graph from it, and that while spectral tokenization is lossless, it is ill-conditioned for local tasks. We further show that although both random-walk and spectral tokenizations are derived from adjacency information, it is impossible for a limited-depth transformer to convert between tokenization families in general. In particular, we establish lower bounds and impossibility results showing that unfavorable tokenizations may preclude the efficient recovery of more suitable structural representations. Finally, we complement our theory with controlled experiments on synthetic and real-world tasks, validating the predicted separations and showing that different tasks favor different structural views, and combining complementary tokenizations allows the transformer to leverage distinct signals from each representation.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Transformers, theory, graphs

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_JFscOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies how graph tokenization affects the expressivity of Transformers. The authors theoretically analyze adjacency, spectral, and random-walk tokenizations, showing how different graph tokenizations influence the ability of Transformers to solve graph tasks. They also evaluate different tokenizations on synthetic and real-world graph tasks to empirically examine the predicted trade-offs.

Critical strengths
  • The paper provides a theoretical analysis of how different graph tokenizations affect Transformer expressivity.
  • The evaluation covers both synthetic and real-world graph tasks to empirically demonstrate the expected trade-offs between tokenizations.
Critical weaknesses
  • Although the theoretical analysis is interesting, many of them align with established intuitions about the compared graph tokenizations. The paper could better explain what additional insights the theoretical results provide.
  • The experiments seems to show limited evidence for the benefits of combining different tokenization methods.

Additional minor concerns:

  • The definition of k-closed-walk detection in Sec 4.1 could be clarified, probably not to allow repeated edges.
  • The related work could include works on node-and-edge graph tokenizations. For example, TokenGT (Kim et al., 2022) proposed representing nodes and edges as independent tokens and also provided the theoretical expressivity analyses of standard Transformer.
Questions for authors
  • What additional insights do the theoretical results provide for selecting graph tokenizations beyond their established intuition?
  • Could the authors further explain when combining tokenizations is beneficial, given the mixed experiment results?
5 comments

Part 1/2

We thank the reviewer for the feedback and for the pointer to TokenGT.

"Although the theoretical analysis is interesting, many of them align with established intuitions..." and "What additional insights do the theoretical results provide..." We respectfully disagree. Existing comparisons of tokenizations focus on the information they contain, e.g., which graphs they can distinguish [2, 3]. Our main insight is that this view misses what matters for a transformer: how much depth and weight size it needs to use that information, and whether common tokenizations contain enough information in the first place. Below are four common beliefs that our results refute.

(1) Common belief: tokenizations that contain the same information about the graph are equally good. This seems natural, since a large enough transformer can compute any function of an input from which the graph can be reconstructed [1]. We show that it fails once depth and weights are bounded. Adjacency and full spectral tokenizations (all eigenvectors and eigenvalues) contain the same information: the graph can be reconstructed from either one. Yet they behave in opposite ways. With adjacency tokens, connectivity requires depth that grows with the number of nodes (Theorem 4), while with spectral tokens a single layer suffices. Fig. 2a shows this empirically. Conversely, detecting a single edge, i.e., whether two given nodes are adjacent, is a direct lookup with adjacency tokens, but with spectral tokens it requires weights whose norm grows with the maximum degree (Theorem 5, Fig. 3).

(2) Common belief: with long enough random walks, random-walk tokens contain all the information about the graph. Random-walk encodings are among the most widely used structural encodings in graph transformers, e.g., in GraphGPS [4], and with nn walk lengths they have n2n^2 entries, as many as the adjacency matrix. We show that this is false. For every walk length, there are a planar graph and a non-planar graph with identical random-walk tokens (Theorem 2), so no transformer of any size can decide planarity from them.

(3) Common belief: truncating the spectrum to the first few eigenvectors loses only fine details of the graph. This is how spectral encodings are used in practice, e.g., [6]. We show that truncation is much more fragile: removing only two eigenpairs, either the two largest or the two smallest, already makes it impossible to count triangles (Theorem 3).

(4) Common belief: a deep enough transformer can convert one tokenization into another, so the choice of tokenization matters little. This seems natural, since all tokenizations are computed from the adjacency matrix. We show that such conversions require depth that grows with the size of the problem (Theorems 1 and 4), and that some are impossible at any depth (Theorem 2).

These results translate into concrete guidance for selecting tokenizations: use spectral tokens for global properties such as connectivity; do not rely on a truncated spectrum alone for exact substructure counts, or on random-walk tokens alone for global topology; do not expect added depth to compensate for an unsuitable tokenization; and combine tokenizations when the structure the task needs is not known in advance.

References

[1] C. Yun, S. Bhojanapalli, A. S. Rawat, S. J. Reddi, S. Kumar. Are Transformers Universal Approximators of Sequence-to-Sequence Functions? ICLR 2020.

[2] M. Black, Z. Wan, G. Mishne, A. Nayyeri, Y. Wang. Comparing Graph Transformers via Positional Encodings. ICML 2024.

[3] B. Zhang, L. Zhao, H. Maron. On the Expressive Power of Spectral Invariant Graph Neural Networks. ICML 2024.

[4] L. Rampasek, M. Galkin, V. P. Dwivedi, A. T. Luu, G. Wolf, D. Beaini. Recipe for a General, Powerful, Scalable Graph Transformer. NeurIPS 2022.

[6] V. P. Dwivedi, X. Bresson. A Generalization of Transformer Networks to Graphs. AAAI Workshop on Deep Learning on Graphs, 2021.

Part 2/2

"The experiments seems to show limited evidence for the benefits of combining..." and "when combining tokenizations is beneficial". In Table 1, the combined tokenization is the best overall. Taking the better of the padded and truncated versions of each tokenization, its average rank over the 8 datasets is 1.7 out of 4, against 2.3 for the next best, adjacency. It is the best or tied for best on 4 datasets, and within one standard deviation of the best on 2 more. This is what the theory predicts: for each single tokenization there is a task on which it provably needs more depth, needs larger weights, or fails at any size (Theorems 1 to 5), and the combined tokenization contains all of them. On the remaining 2 datasets, ZINC and Tox21, it is behind the best single tokenization. The combined input is three times wider than every single tokenization alone, so the model has more parameters to fit with the same data. In practice, one usually does not know in advance which structure a task depends on. The combined tokenization then lets one train a single model, instead of training one model per tokenization and picking the best. We will add this summary to Section 5.

"The definition of kk-closed-walk detection in Sec 4.1 could be clarified, probably not to allow repeated edges." Repeated vertices and edges are allowed. The task asks for a closed walk of length kk, and a walk may repeat both. This is exactly what random-walk return probabilities count, and what the construction of Theorem 6 uses for odd kk. Forbidding repetitions would turn the task into cycle detection, which is a different problem. We will state the definition explicitly in Section 4.1.

"The related work could include works on node-and-edge graph tokenizations..." We will add TokenGT [5] to the related work. TokenGT proves that a transformer on node and edge tokens, with suitable node identifiers, can represent any function that a second-order invariant graph network can. This tells which functions the model can represent, given enough layers and width. Our results answer a more intricate question: how many layers and how large weights are needed. Our depth lower bounds (Theorems 1 and 4) also hold for TokenGT’s tokens with one-hot node identifiers, since these tokens can be computed from the adjacency matrix by a constant-depth circuit, we will add this in the final version. A full analysis of edge tokens is left for future work, as we mention in the Conclusion.

We hope this clarifies the contribution, and we would be grateful if the reviewer would reconsider their assessment.

References

[5] J. Kim, T. D. Nguyen, S. Min, S. Cho, M. Lee, H. Lee, S. Hong. Pure Transformers are Powerful Graph Learners. NeurIPS 2022.

Thank you for the detailed response. The distinction between information preservation and computational requirements is clearer now. The additional average-rank analysis also helps address my concern about combining tokenizations.

I still have one question about Theorem 1, specifically the even-length case. For any positive even kk, an undirected graph containing an edge admits a closed walk by repeatedly traversing that edge back and forth. Wouldn't this make even-length closed-walk detection equivalent to simply checking whether the graph contains an edge? If so, how does this align with the stated Ω(log⁡k)\Omega(\log k) depth lower bound? Is the theorem intended to apply only to odd kk?

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

In this paper, the authors provide theoretical analysis for Graph Transformers (GTs). Specifically, they focus on how the choice of graph tokenizations, which is a fundamental component of many GTs, can affect the structural expressive capability. Three common types of tokenization methods: spectral, random walk-based, and adjacency-based, are considered, and five main theorems associated with them are provided to cover the limitations, lower bounds, required depth, etc. for GTs under assumptions. The authors also conduct several control experiments to demonstrate the empirical results to support their theoretical analysis.

Critical strengths
  • S1: The perspective of considering graph tokenization as part of the GTs in theoretical analysis is useful. This provides new insights different from merely analyzing the expressivity of the tokenizer itself.
  • S2: The theoretical analysis is solid and provides intuition for choosing graph tokenization methods; the users can balance the computational efficiency with expressivity ability based on the difficulty of tasks and avoid overestimating or underestimating the chosen tokenization.
Critical weaknesses
  • W1: The assumptions focus on node tokenizations, however, many architectures utilize edge tokens or additional modules to inject structural information to GTs, which may enable them to exceed the bounds in this paper.
Questions for authors
  • Q1: Following W1, for example, TokenGT [1] uses both node and edge features extracted from Laplacian. Can this method exceed the bounds in theorem 5 as it is not just a deeper GT. Also, for other common techniques such as adding attention layer to the Laplacian features, do they also follow this theorem.
  • Q2: Figures 2 and 3 demonstrate scaling trends on synthetic data. I am curious if similar trends can be observed on real data.

[1] Pure Transformers are Powerful Graph Learners, 2022

3 comments

We thank the reviewer for the positive assessment and the questions.

Q1 / W1: Edge tokens and additional modules. Edge tokens do not break our bounds; they move part of the cost to the input size. First, our depth lower bounds (Theorems 1 and 4) also hold for edge tokens. Their proofs only use the fact that a constant-depth transformer can be simulated by a constant-depth threshold circuit (TC0\mathsf{TC}^0). Edge tokens with one-hot node identifiers, as in TokenGT [1], can be computed from the adjacency matrix by a constant-depth circuit. So if a constant-depth transformer could solve connectivity from these tokens, we would get a constant-depth circuit that solves it from the adjacency matrix, which is ruled out by the same complexity assumption as in Theorem 4. Hence TokenGT also needs depth that grows with the number of nodes to decide connectivity.

Second, Theorem 5 says that with Laplacian node tokens, checking whether two nodes uu and vv are adjacent requires weights that grow with the maximum degree dmax⁡d_{\max}, because the edge (u,v)(u, v) is spread over all the eigenvectors. In TokenGT, the edge (u,v)(u, v) is given as its own token, so checking it is a direct lookup. The cost moves to the input: TokenGT uses n+mn + m tokens instead of nn, and the number of edges mm is at least dmax⁡d_{\max}, the same quantity that lower-bounds the weights in Theorem 5. On dense graphs, mm is of order n2n^2, and the cost of attention grows quadratically with the input length. So edge tokens trade the weight size of Theorem 5 for a longer input.

Additional modules applied to the Laplacian features of each node, such as attention layers over its eigenvector entries, process the spectral token of each node separately, so the resulting token is still a function of the same spectral information. The bound of Theorem 5 then applies to the composed network, and by Remark 1, adding such modules or layers spreads the requirement across them: each needs weights of order the LL-th root of the maximum degree, but the requirement does not go away.

Q2: Trends on real data. We would like to show Figs. 2 and 3 on real data, but this is not possible. Those figures vary the number of nodes and the maximum degree while keeping the task fixed. In real datasets, these are fixed by the data, so there is no range of sizes along which to measure a trend. However, Table 1 shows on real data the same behavior that Figs. 2 and 3 show on synthetic data: Laplacian tokens do poorly on tasks that depend on exact edges, as Theorem 5 predicts. On MaxClq, whether a node belongs to a maximum clique depends on exact edges. There, the Laplacian tokenization reaches an F1 score of about 10, the same as DeepSet, which does not see the edges at all, while adjacency reaches about 25. On TopoOrd, the target depends on the directed edges, and adjacency has about 20% lower error than the Laplacian tokenization.

References

[1] J. Kim, T. D. Nguyen, S. Min, S. Cho, M. Lee, H. Lee, S. Hong. Pure Transformers are Powerful Graph Learners. NeurIPS 2022.

Thank you for the clarification. My initial positive assessment was for the potential of having a theoretical foundation for graph tokenization. However, I remain uncertain about the generality and the application to real data since both MaxClq and TopOrd are synthetic datasets. I will finalize my rating after further discussion.

Thank you for the follow-up. We agree that MaxClq and TopoOrd are synthetic combinatorial tasks. Both are standard tasks from GraphBench [1], a recent benchmark suite for graph learning, and were not designed for our paper. We used them in our answer because their targets depend on exact edges, which isolates the setting of Theorem 5.

The experiments in Table 1 also contain six other datasets: four molecular datasets from OGB [2] (BBBP, BACE, HIV, Tox21), ZINC, and electronic circuits (EC-5). The same picture holds there. On EC-5, whose target depends on how the components of the circuit are connected, adjacency is the best single tokenization (relative squared error 0.0510.051, against 0.0770.077 for the Laplacian and 0.2790.279 for random walks). On Tox21, BACE and HIV, whose labels depend on the molecule as a whole, which makes them global tasks, the Laplacian is the best single tokenization. On ZINC, whose target includes a ring-count term, random-walk tokens, which count closed walks, are the best. So on real data no single tokenization dominates, and the best one matches the structure the task depends on, as our theory predicts. Overall, this holds across 8 datasets from different domains: the 2 synthetic tasks noted by the reviewer and 6 real-world ones.

References

[1] T. Stoll, C. Qian, B. Finkelshtein, et al. GraphBench: Next-generation Graph Learning Benchmarking. ICML 2026.

[2] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, J. Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. NeurIPS 2020.

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

This paper studies how positional/structural encodings affect Graph Transformer’s ability to solve graph tasks. It compares adjacency, spectral, and random-walk encodings through theoretical analysis and experiments. The authors argue that each encoding makes some tasks easier and others harder, and show that combining encodings sometimes improves performance.

Critical strengths

The paper asks an important question: how much of a graph transformer’s capability comes from PE/SEs? The topic is important and timely to graph research.

The paper covers the 3 classes of typical PEs: adjacency, spectral, and random-walk encodings. The experiments show useful differences across tasks.

Critical weaknesses
  1. A theory-experiment gap: the theory in Sec. 3.2 uses eigenvectors and eigenvalues of the unnormalized Laplacian. The experiments use normalized-Laplacian eigenvectors instead. The link to the theory is unclear, and the paper does not provide a justification for this.

  2. Limited depth/insights: the paper does not explain which structural features each task needs or how the model uses them. For example, why does spectral encoding help on Tox21? Calling it “global geometry” does not answer the question clearly. An in-depth analysis or visuallization could help identify the deciding factors. Similarly, the "local information" is also not clearly established.

  3. Narrow experiment setup: the encoding comparison uses only one Transformer backbone, with depth and width varied. The experiments also omit edge features, including molecular bond information. This leaves the conclusions less generalizable across other architectures and richer graph inputs.

Questions for authors
  1. Could the authors carefully review the theories and experiments and their alignment? The current version seems to have contradicting descriptions. Is that a wording error, or a real mismatch?

  2. Could the authors provide more analysis, both qualitative and quantitative, to better support their claims in the functions of different PEs in different tasks?

  3. Could you explain why the experiments are limited to only one GT architecture?

  4. The term 'tokenization' sounds misleading to me. The paper mostly studies PE/SE differences while keeping a standard "one node, one token" input design. "tokenization" makes me think about how input tokens/sequences are constructed from graphs, which is not discussed in the paper. Consider adjusting the wording.

3 comments

Part 1/2

We thank the reviewer for the detailed review.

"A theory-experiment gap: the theory in Sec. 3.2 uses eigenvectors and eigenvalues of the unnormalized Laplacian..." and "Could the authors carefully review the theories and experiments and their alignment?..." There is no contradiction: the theorems behind our experiments, Theorems 4 and 5, hold for both normalized and unnormalized Laplacians with the same proofs. We state the theory in Section 3.2 for the unnormalized Laplacian. In the real-world experiments we used the normalized Laplacian with eigenvectors only, since it is the more common choice in practice [1, 2] (App. A.8 and Table 5). For connectivity (Theorem 4), a graph has kk connected components exactly when its Laplacian has kk zero eigenvalues. This is true for both Laplacians, so one layer suffices in both cases. For edge prediction (Theorem 5), the proof goes through for the normalized Laplacian, with the maximum degree replaced by the geometric mean of the degrees of the two endpoints. We will state this explicitly in Section 5.

Additional experiments with the unnormalized Laplacian. We also ran the experiments with the unnormalized Laplacian of Section 3.2 (eigenvectors and eigenvalues), next to the normalized one used in Table 1, and the normalized one with eigenvalues added. All variants were trained in the same code with the same protocol (3 seeds):

Laplacian tokenizationBBBP ROC-AUC (Pad. / Trunc.)BACE ROC-AUC (Pad. / Trunc.)Tox21 ROC-AUC (Pad. / Trunc.)Connectivity, 1 layer: accuracy at 64 / 256 nodes
Normalized, eigenvectors (Table 1)66.8 ± 0.8 / 69.4 ± 1.472.0 ± 2.7 / 73.5 ± 2.282.8 ± 0.4 / 82.7 ± 0.61.00 ± 0.00 / 1.00 ± 0.00
Normalized, eigenvectors + eigenvalues66.4 ± 0.3 / 68.8 ± 2.676.8 ± 1.6 / 72.2 ± 2.182.0 ± 1.2 / 83.0 ± 0.61.00 ± 0.00 / 1.00 ± 0.00
Unnormalized, eigenvectors + eigenvalues (Sec. 3.2)64.3 ± 1.1 / 69.0 ± 1.574.2 ± 1.1 / 74.4 ± 3.281.5 ± 0.7 / 82.3 ± 0.91.00 ± 0.00 / 1.00 ± 0.00 (*)

(*) For the unnormalized Laplacian, the eigenvalues are divided by the number of nodes, which keeps them bounded as the graph grows.

The normalized Laplacian used in the paper and the unnormalized one give similar results, so the choice of Laplacian does not change any of our conclusions. On the molecular benchmarks, no variant is consistently better: the three variants differ by at most 3 points on BBBP and Tox21, and by at most 5 points on BACE. On connectivity, a single spectral layer solves graphs of up to 256 nodes, while adjacency tokens are at chance from 32 nodes on, even with 7 layers, as Theorem 4 predicts.

"Limited depth/insights: the paper does not explain which structural features each task needs or how the model uses them..." and "Could the authors provide more analysis..." For real-world tasks, we cannot know in advance which structure a task needs. However, Table 1 shows that each task has a tokenization that works best for it. This suggests that the task depends on features that this tokenization is especially suited for, and our theory tells which features these are. Adjacency tokens contain the edges explicitly, so local constraints, such as whether two nodes are adjacent, can be checked directly. Global properties, such as connectivity, require combining paths of growing length, and therefore depth (Theorem 4). Spectral tokens behave in the opposite way. The number of connected components equals the number of zero eigenvalues, so connectivity is read off in one layer. A single edge, however, is spread over all eigenvectors, since Auv=−∑kλkVukVvkA_{uv} = -\sum_k \lambda_k V_{uk} V_{vk} for u≠vu \neq v, and recovering it requires large weights (Theorem 5). Fig. 3 and App. A.9 show this effect during training through the logit energy, the attention entropy and the gradient norm. Random-walk tokens count closed walks, so they capture cycles, but they miss global properties such as planarity (Theorem 2). The connectivity experiment above confirms the separation between adjacency and spectral tokens on graphs of up to 256 nodes.

This picture from the theory matches what we see on real data: in several cases, the domain suggests which features a task needs, and the best tokenization in Table 1 is the one suited to them. On MaxClq and TopoOrd, where the target depends on exact edges, adjacency is the best single tokenization. On ZINC, whose target includes a ring count term, random-walk tokens, which count closed walks, are the best single tokenization. On Tox21, BACE and HIV, three of the four molecular classification tasks, whose label depends on the molecule as a whole, the Laplacian is the best single tokenization, in line with spectral tokens capturing global structure. We do not aim to give a definitive answer, since real-world targets are likely to depend on a large variety of structures.

Part 2/2

Regarding "local": we use it for tasks whose answer at a node or an edge is determined by a bounded-radius neighborhood, such as edge prediction (Section 4.3) and triangle counting (Theorem 3), as opposed to global properties such as connectivity (Theorem 4). We will add this definition to Section 4.

"Narrow experiment setup..." and "Could you explain why the experiments are limited to only one GT architecture?" The paper uses a plain transformer whose only access to the graph is the tokenization (App. A.8). This isolates the effect of the tokenization, which is what our theory analyzes. Following the reviewer's suggestion, we also evaluated each tokenization with two widely used graph transformer backbones. GraphGPS [2] combines message passing over edge features with global attention, which also addresses the reviewer's point on edge features. Graphormer [3] adds the shortest-path distance between every two nodes as a bias to the attention scores. Both backbones therefore see the graph also through a channel other than the tokenization, which tests whether the tokenization still matters in this setting. Both use a fixed configuration and 3 seeds:

BackboneTokenizationMaxClq F1 ↑TopoOrd MAE ↓ZINC MAE ↓BBBP ROC-AUC ↑BACE ROC-AUC ↑
GraphGPSLaplacian11.2 ± 0.82.42 ± 1.090.170 ± 0.01065.0 ± 1.279.0 ± 3.7
GraphGPSAdjacency18.2 ± 1.60.73 ± 0.280.322 ± 0.00767.6 ± 1.474.0 ± 1.9
GraphGPSRandom walk10.4 ± 1.94.36 ± 3.220.128 ± 0.00264.7 ± 0.678.0 ± 0.0
GraphormerLaplacian12.8 ± 2.60.263 ± 0.0250.296 ± 0.06269.6 ± 1.177.8 ± 2.0
GraphormerAdjacency11.3 ± 3.10.232 ± 0.0080.402 ± 0.03867.7 ± 2.176.2 ± 1.0
GraphormerRandom walk13.0 ± 2.40.239 ± 0.0140.285 ± 0.06168.2 ± 2.178.3 ± 0.9

The results agree with those in the paper. With GraphGPS, the best tokenization on each of the 5 datasets is the same as the best single tokenization in Table 1: adjacency on MaxClq, TopoOrd and BBBP, random walk on ZINC, and Laplacian on BACE. Graphormer receives the shortest-path distances regardless of the tokenization, and accordingly the tokenizations are closer to each other. On MaxClq and BBBP, all three tokenizations are within one standard deviation. This fits the main message of the paper: what matters is which structures can be computed from the input with few layers and small weights. On MaxClq and TopoOrd, the test graphs have 128 nodes against 16 in training, which is why all models are weaker there. We will add these results to the paper.

"The term 'tokenization' sounds misleading to me..." Section 3.1 defines a tokenization as a general map from a graph to a sequence of tokens. In the node-level tokenizations we analyze, each node is represented by one token, which is a vector computed from the graph.

Specifically, these are the embeddings we consider: for each node, its row of the adjacency matrix, its entries in the Laplacian eigenvectors, or its random-walk return probabilities. The transformer receives only these vectors. There are no other node features, no message passing, and no structural bias in the attention, so these vectors are the only way the graph reaches the model. Choosing them therefore determines how the graph is converted into a sequence of tokens. Prior work uses "graph tokenization" in the same sense, and considers node-level tokenizations of this kind alongside edge-level ones [4, 5]. We agree that in the graph transformer literature these node vectors are usually called positional or structural encodings, and we will state this connection in Section 3.1.

We hope the new results and clarifications address the reviewer's concerns, and we would be grateful if the reviewer would reconsider their assessment.

References

[1] V. P. Dwivedi, X. Bresson. A Generalization of Transformer Networks to Graphs. AAAI Workshop on Deep Learning on Graphs, 2021.

[2] L. Rampasek, M. Galkin, V. P. Dwivedi, A. T. Luu, G. Wolf, D. Beaini. Recipe for a General, Powerful, Scalable Graph Transformer. NeurIPS 2022.

[3] C. Ying, T. Cai, S. Luo, S. Zheng, G. Ke, D. He, Y. Shen, T. Liu. Do Transformers Really Perform Badly for Graph Representation? NeurIPS 2021.

[4] C. Sanford, B. Fatemi, E. Hall, A. Tsitsulin, M. Kazemi, J. Halcrow, B. Perozzi, V. Mirrokni. Understanding Transformer Reasoning Capabilities via Graph Algorithms. NeurIPS 2024.

[5] C. Yuan, K. Zhao, E. E. Kuruoglu, L. Wang, T. Xu, W. Huang, D. Zhao, H. Cheng, Y. Rong. A Survey of Graph Transformers: Architectures, Theories and Applications. arXiv:2502.16533, 2025.

Dear Reviewer cCd8,

As the discussion period is coming to an end, we wanted to kindly check whether our response addressed your concerns. In short: (1) the theorems behind our experiments hold for both the normalized and unnormalized Laplacians, and we added experiments with the unnormalized Laplacian of Section 3.2, which give similar results; (2) we explained which structure each tokenization captures and how this matches the best tokenization on each dataset in Table 1; and (3) we evaluated all tokenizations with two widely used graph transformers, GraphGPS (which also uses edge features) and Graphormer, and the choice of tokenization still matters with both backbones, in line with the paper.

We would be happy to answer any remaining questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.