- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies the expressive power of graph transformers. Specifically, the work shows that graph transformers with 'basic' structural encodings can express MSO in the non-uniform setting and over graphs of bounded treewidth. The resulting graph transformers are shown to run in FPT time O(n^3log(n)), and FPT time O(nlog(n)) when a 'nice' and 'balanced' tree decomposition is given.
Critical strengths
-
Showing that graph transformers can compute tree decompositions in fixed parameter tractable time is a novel contribution and argues for the 'naturalness' of the MSO lower-bound.
-
The notion of 'expressing a property' is strong. I.e. there is some constant c for which f(G) = c iff G has property P.
-
The paper is candid regarding its limitations.
Critical weaknesses
-
The structural encoding is quite strong in that it encodes the whole graph structure. Having this combined with the non-uniform setting, it leaves the question whether obtaining an MSO lower-bound is surprising as the option of 'memorizing' all of the finitely many graph is seemingly left possible.
-
The tokenization of graphs not being permutation invariant, whilst seemingly not affecting the characterisation, raises the question to whether this encoding is natural.
-
No converse to the expressivity lower-bound is established thus leaving this a partial characterisation.
Suggestions:
-
Line 068 and other places: it is unclear that 'graph transformers can express MSO in FPT ... time' is referring to the runtime of the graph transformer.
-
Line 195: the conjunct (X_i v \wedge X_i w) should be negated.
-
It would be interesting to see if a graph transformer can be trained to compute tree decompositions.
Questions for authors
-
Is it not the case that, in the non-uniform setting with the assumed structural encoding, graph transformers can capture all graph properties (or at least some superset of MSO-properties)? If so, is the 'connection to MSO' argument based solely on fixed parameter tractability?
-
To what extent does the characterisation depend on the specific structural encoding? Is any characterisation known for, e.g. spectral or random walk encodings?
-
Less important than the other question, but it would be nice to know what is preventing a uniform characterisation?
2 comments
- Is it not the case that, in the non-uniform setting with the assumed structural encoding, graph transformers can capture all graph properties (or at least some superset of MSO-properties)? If so, is the 'connection to MSO' argument based solely on fixed parameter tractability?
Yes, in the non-uniform setting and with our encoding, sufficiently large transformers can express every graph property on graphs of size at most , e.g., by memorization, at exponential size. The connection to MSO via automata simulation is therefore not only about which properties are expressible in principle, but about the required resources. For a fixed MSO formula , our construction yields transformers of size polynomial in (with a factor independent of ) and FPT running time. Our result is thus not intended as a tight characterization, but as a constructive lower bound with explicit time and size requirements.
- To what extent does the characterisation depend on the specific structural encoding? Is any characterisation known for, e.g. spectral or random walk encodings?
Our result is specific to the sequence-based encoding with node and edge tokens. Known results for spectral and random-walk encodings typically characterize expressivity via Weisfeiler-Leman variants rather than logics (Black et al., 2024 and Stoll et al., 2025). Whether such encodings suffice for an MSO lower bound is, to our knowledge, an open and interesting question.
- Less important than the other question, but it would be nice to know what is preventing a uniform characterisation?
In our construction, the number of layers grows with : computing the tree decomposition requires layers, and simulating the tree automaton requires layers, determined by the depth of the balanced tree decomposition. Given a tree decomposition, our looped construction is already uniform in its parameters: only the number of iterations depends on (Theorem 4.5 and Remark A.5). We believe that a uniform constant-depth result is unlikely: constant-depth transformers with logarithmic precision are contained in TC$^0$ (see, e.g., Merrill et al., 2022), whereas some MSO-definable properties, such as having a perfect matching, are L-hard on bounded-treewidth graphs (Das et al., 2013). Thank you for the question, we consider this an interesting direction for future work!
Veeti Ahvonen, Maurice Funk, Damian Heiman, Antti Kuusisto, and Carsten Lutz. Expressive power of graph transformers via logic. AAAI 2026.
Mitchell Black, Zhengchao Wan, Gal Mishne, Amir Nayyeri, and Yusu Wang. Comparing graph transformers via positional encodings. ICML 2024.
Timo Stoll, Luis Müller, and Christopher Morris. Generalizable insights for graph transformers in theory and practice. NeurIPS 2025.
William Merrill, Ashish Sabharwal, and Noah A. Smith. Saturated Transformers are Constant-Depth Threshold Circuits. TACL 2022.
Bireswar Das, Samir Datta, Prajakta Nimbhorkar. Log-Space Algorithms for Paths and Matchings in k-Trees. Theory of Computing Systems 2013.
We thank the reviewer for their detailed comments, and for highlighting the novelty of our theoretical contributions!
We address each of the weaknesses and questions below.
We agree that the encoding provides the full graph structure, deliberately so, to complement Ahvonen et al. (2026), who study graph transformers without structural information. Indeed, in the non-uniform setting, any property of the finitely many graphs of size at most n can in principle be memorized. However, this requires transformers whose size grows exponentially with n. Our result is meaningful precisely because, for a fixed MSO formula φ, the transformer has size polynomial in n, with a factor g(k,φ) independent of n. Given a tree decomposition, a looped transformer even has parameter count independent of n (cf. Theorem 4.5).
Our encoding follows Sanford et al. (2024): the graph is serialized as node and edge tokens, as it would be for a standard sequence transformer. This allows us to connect graph transformer expressivity with the sequence-based transformer literature, where such order-dependent encodings are standard. Importantly, the transformer’s output is invariant: all vertex orderings of the same graph are mapped to the same output. Only intermediate objects, such as the tree decomposition, may depend on the ordering. We have clarified this in the revised paper.
Indeed, our results provide a lower bound on expressivity rather than a full characterization. We show that graph transformers with a standard sequence-based encoding can express all MSO-definable properties on bounded-treewidth graphs, and quantify the transformer size required to do so. We consider a full characterization as an interesting direction for future work.
Thanks for bringing this up, we have added some explanation on the time complexity and made this more explicit throughout the paper.
Thanks for pointing this out, we fixed it.
We believe this is outside of the scope of our submission but agree that this would be great follow-up work, thank you for the suggestion!