Depth-Width Tradeoffs for Transformers on Graph Tasks

We thank the reviewer for the thorough and positive review.

Weaknesses:

“What exactly is the output for the 2-cycle detection task?”: This is a binary classification task; the label is whether the input is a 1-cycle or 2-cycles. This is similar to the binary connectivity task, where the output is whether the graph is connected (1-cycle) or not (2-cycles).

“The paper adopts a node-adjacency input format “: The node adjacency embeddings are not permutation invariant. It is common in theoretical papers about the expressiveness of transformers on graph tasks to use non-permutation invariant encoding to analyze their expressive power. This is also done, for example, in [1] and [2], where the authors use edge-list encoding, which is also not permutation invariant. We also emphasize that using any permutation invariant encoding, solving connectivity problems on graphs with $n$ nodes requires at least $\Omega(n)$ layers, since such models are equivalent to the LOCAL distributed computing architecture, see [3]. To utilize the expressive power of transformers, which is equivalent to the MPC model and allows solving connectivity problems with $O(\log(n))$ layers, we must use non-permutation invariant encoding. We will emphasize this point in the final version.

“The paper states that each node's adjacency row is embedded as an input token.”: Yes, in the case of having node features (i.e., beyond combinatorial problems), each token also contains its node feature, and the transformer can interpret them in the early layers. We will clarify this in the final version. “The claimed generalization across different input formats”: Theoretically, it is possible to move from edge-list encoding to adjacency rows embedding using a constant-depth transformer. This transformer only needs to encode the edges relevant to each node and order them as an adjacency row. A translation in the other direction is also possible. We are happy to go into more details on this if the reviewer is interested. The conclusion of this is that for constant-depth transformers, theoretically, it doesn’t matter if we begin with an edge-list of adjacency-rows encoding, and our constructions will still work.

“The molecular graph classification results reported are significantly below the performance of standard GNNs”: We agree with the reviewer on this point. The goal of this experiment is to justify the use of adjacency row encoding, compared to edge-list or spectral encodings. We believe that the drop in accuracy is since GNNs are currently more successful than transformers on these tasks in general. We also haven’t used the most powerful or largest transformer architecture that may achieve SOTA results on these tasks. We will consider adding experiments on GNNs to have a more thorough comparison.

Questions:

“The graph inputs using adjacency rows resemble Graphormer-style encodings”: We consider the rows of the adjacency metric as sequence tokens as used in Transformers, each corresponding to a node in the graph. Also in Graphormer, tokens of nodes (with some PEs) are eventually fed into a transformer as tokens, and therefore this can be seen in the same way.

“Furthermore, they should explain why there is a significant performance gap between real-world applications, prior work, and the idealized results reported on synthetic tasks.“: Our experiments are not aimed at beating SOTA results, but rather to demonstrate and justify the use of the positional embedding we used. Thus, our hyperparameter grid and model size are smaller than those of SOTA models, which may be the cause of the difference. We will consider in the final version extending these experiments to larger models and attempting to achieve comparable results to the current SOTA.

[1] C. Sanford, D. Hsu, and M. Telgarsky. Transformers, parallel computation, and logarithmic depth, 2024

[2] C. Sanford, D. J. Hsu, and M. Telgarsky. Representational strengths and limitations of transformers, 2024

[3] Loukas, Andreas. What graph neural networks cannot learn: depth vs width, 2019

We thank the reviewer for the thorough and positive review.

Weaknesses:

1. We addmitingly study theoretically only combinatorial problems on graphs. The advantage of such problems is that analyzing them is tractable, and also well connected to other fields in CS such as distributed computing, and graph algorithms. The difficulty of analyzing problems on real datasets, such as molecules and social networks, is that the properties of the graphs and the tasks themselves are rather difficult to formulate and analyze. It would be interesting to extract properties of such tasks and analyze them theoretically, but this is beyond the scope of our paper.

2. We indeed don’t compare our results to GNN architectures, and focus only on transformers. The goal of our paper is more of a theoretical analysis, and the experiment on the molecular dataset is to justify the use of adjacency encoding. With that said, we will consider adding more comparisons to GNN architectures in the final version.

3. The use of a highly expressive MLP and exact control of the attention weights was also done in previous works on the theoretical capabilities of transformers on graph tasks, e.g., in [1] and [2]. But, this is done only in our upper bounds; our lower bounds apply even under these assumptions, thus they also apply to practical settings and demonstrate several expressiveness limitations of the transformer architecture itself.

Questions:

1. Although it is difficult to exactly formalize property detection tasks on molecules (or other practical tasks on real datasets), we believe they inherently require solving a combinatorial problem on the graph itself. For example, detecting sub-structures that manifest the property, or identifying other combinatorial properties of the graph, such as whether it is connected, contains cycles of certain types, etc. Also, studying such tasks reveals inherent limitations of the architecture itself, which apply to any possible task.

2. For example, if we know a certain molecular property appears in a structure containing 4 atoms, our work provides bounds for the width of the transformer to detect such structures. These bounds are, of course, not tight for such tasks, as they may include other properties such as features of each atom, but can provide rough estimates on the required size of the architecture. That’s a good suggestion. In the original manuscript, we focused on comparisons only to other transformer architectures, but we will consider adding comparisons also to GNN architectures in the final version.

3. The intention of this work is to comment on the fundamental capabilities of transformers as their widths and to tightly capture those quantitative trade-offs, and our assumptions (in particular, arbitrary MLPs and positional encodings) are selected with these goals in mind. These assumptions cover a wide range of transformers architectural decisions, and thus, our negative results are particularly expansive. If future work seeks to capture the abilities of transformers to learn these tasks under optimization constraints, we believe it would be possible to do so with more fine-grained constructions that rely on bounded-norm MLPs and standard learnable or sinusoidal positional encodings. If there are particular constraints the reviewer is interested in, we are happy to discuss in more detail.

[1] C. Sanford, D. Hsu, and M. Telgarsky. Transformers, parallel computation, and logarithmic depth, 2024

[2] C. Sanford, D. J. Hsu, and M. Telgarsky. Representational strengths and limitations of transformers, 2024

We thank the reviewer for the thorough and positive review.

To answer the questions:

• Indeed, the adjacency positional embeddings are not permutation invariant. We note this is also the case for the edge list positional embeddings, which were previously used to study the connection between transformers and the MPC model (in [1] and [2]). We use this embedding for technical convenience, especially since spectral embedding, although useful in practice, are difficult to analyze for combinatorial problems (such as connectivity, subgraph counting etc.). The experiment presented in Table 1 is not aimed at beating or achieving comparable results to SOTA, but rather to justify, even in a small setting that the adjacency encoding is not worse than other encodings such as edge-list and spectral.

• This is a good point. We can generalize the 1-cycle vs. 2-cycles results to the general problem of detecting whether a graph is connected. This is outlined in lines 184-196 in the paper, and uses the method of linear sketching. We will consider formalizing this and presenting the result as a theorem in the final version.

• The 1-cycle vs. 2-cycles problem is the following: Given a graph which is either (1) One cycle with $n$ nodes; or (2) Two cycles, each with $n/2$ nodes, determine which of the two options it is. This problem can be solved by a distributed algorithm in the MPC model by having at most $O(\log(n))$ communication rounds. The 1-cycle vs. 2-cycles conjecture states that it cannot be solved by less than $O(\log(n)) rounds. This is the most commonly assumed conjecture in the context of MPC; see also the Wikipedia page called “1-vs-2 cycles problem” (due to the new NeurIPS policy, we don’t add links in the rebuttal). Many lower bounds and hardness results in the context of MPC rely on this conjecture, and to translate these hardness results, we assume it as well. In the final version, we will add a further discussion and formal definition of this conjecture.

• In Section 5.2 we consider non-induced subgraphs. In [3] the authors distinguish between the two cases, but that is a paper focused entirely on sub-graph counting. Since this is not the main focus of our paper, we focused only on one case, although it may be interesting to study induced sub-graph counting since the results there may differ.

• In the literature of distributed computing (i.e., related to MPC) if the lower bound applies in the case of $n^{2-\epsilon}$ for any $\epsilon > 0$, it is considered only nearly quadratic, rather than quadratic. It is more a matter of terminology.

• As in these experiments, we fix the width and depth of the network in each configuration, we observed that some settings failed to converge with just one attention head. To ensure a fair comparison we wished to fix the number of attention heads, and therefore we used two attention heads across all settings as this ensured convergence. We will make sure to clarify this in the camera-ready version.

• That’s a good point, and we believe there are. Assuming that the graph is sparse, the adjacency encoding is rather superfluous. It may be replaced by a smaller-dimensional embedding, for example, by projecting each adjacency row using a random or specially crafted projection. This is also the case of bounded-degree graphs, where the adjacency matrix is sparse. In our work, we haven’t specifically tested the effect of width for sparse graphs, but rather provide bounds for general graphs (except for Section 4.3, which focuses on sparse graphs and the 2-cycle detection problem). It is a very interesting future direction to study such bounds on sparse graphs, which are commonly encountered in practice, and whether they improve on the general case, which is explored in our paper.

Regarding the limitations:

Our work indeed assumes universal approximation of the MLP part; this is also done in previous works studying the expressiveness of transformers on graph tasks, e.g., in [1] and [2]. The reason for this is to align with the distributed computing literature, which takes into account global communication rounds, but not local computations. It will be interesting to do a more fine-grained analysis in the case of whether the MLPs are bounded, and how it affects the different bounds. We conjecture that in this case, we would face circuit complexity bounds, which are studied, for example, in [4].

Regarding non-uniformity, this is a general limitation of computational complexity problems. Namely, it is not possible to construct a transformer with constant size (depth, width and bit-precision) that can solve connectivity, sub-graph counting, or other similar combinatorial problems on graphs of any size. Even counting the degree of a single node would require, in the general case, constructing a transformer that counts up to $n$, which requires at least $log(n)$ bits.

Regarding the weaknesses:

About the non-premutation-invariant encodings, it is the same answer as above in the “questions” section. Regarding the paper “Comparing Graph Transformers via Positional Encodings", this is indeed useful, and we will add a citation. We admit we haven’t made a thorough experimental study on different graph embeddings, but rather made an experiment to justify the use of the adjacency encoding we used. About the presentation, thank you for the remark. We will try to make the introduction more precise. Also, in the final version, we will add a more thorough overview of the MPC model, the assumption we use (e.g. 1-cycle vs. 2-cycles), and be clearer about the restrictions we make on graphs. We will also change the title of Section 4.2 to make it more precise.

Thank you for carefully reading our paper and spotting the typos, they will be fixed in the final version. We will rewrite the statement in lines 230-231, to check all the powers of the adjacency. Figures 4 and 5 contain a typo in caption; Figure 4 presents the results for 50-nodes on the connectivity task.

We apologize for the missing references, and thank you for the additional question. The references are:

[1] C. Sanford, D. Hsu, and M. Telgarsky. Transformers, parallel computation, and logarithmic depth, 2024

[2] C. Sanford, D. J. Hsu, and M. Telgarsky. Representational strengths and limitations of transformers, 2024

[3] Z. Chen, L. Chen, S. Villar, and J. Bruna. Can graph neural networks count substructures?, 2020

[4] W. Merrill, William, and A. Sabharwal. A little depth goes a long way: The expressive power of log-depth transformers, 2025 ‏

Regarding the question: The experiment in Section 6.1 (Figure 2) tested different depth/width combinations. With one head, the experiment converged only if the width was larger than 63 (the middle column), even though the depth was large. With two heads, it converged for all the depth and width combinations that we tested. Since the goal of this experiment is to test the convergence time, we used the two-heads setting, where all experiments converged, to ensure a fair comparison. Regarding the experiment in Section 6.2, we employed a similar two-head setting to maintain consistency with the previous experiment.

As to why two heads practically work better than a single head, we believe this is quite interesting and underexplored, and probably goes beyond the context of graph tasks and the scope of our paper. We conjecture that it is related to optimization issues rather than expressive capabilities. In the original "Attention is all you need" paper, the authors explicitly state that they found multi-head attention to be more beneficial than single-head attention, but they don't provide a reason for that, see Section 3.2.2 there. Since then, using multi-head attention is the common practice, but the theoretical reason for that remains a mystery as far as we know.