- 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 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 -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 , 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 . 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 , 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 depth lower bound? Is the theorem intended to apply only to odd ?
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 n walk lengths they have n2 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.