Depth-Width Tradeoffs for Transformers on Graph Tasks
Authors: Gilad Yehudai
Clayton Sanford
Maya Bechler-Speicher
Orr Fischer
Ran Gilad-Bachrach
Amir Globerson
Venue: NeurIPS 2025 spotlight ()
Keywords: Learning theory
graph transformers
expressiveness
self-attention
Primary area: theory
TL;DR: We show that transformers with linear width can solve many graph problems using constant depth, revealing a trade-off where increasing width enables shallower, faster models—though some tasks still demand quadratic width.

Abstract: Transformers have revolutionized the field of machine learning. In particular, they can be used to solve complex algorithmic problems, including graph-based tasks. In such algorithmic tasks a key question is what is the minimal size of a transformer that can implement the task. Recent work has begun to explore this problem for graph-based tasks, showing that for sub-linear embedding dimension (i.e., model width) logarithmic depth suffices. However, an open question, which we address here, is what happens if width is allowed to grow linearly, while depth is kept fixed. Here we analyze this setting, and provide the surprising result that with linear width, constant depth suffices for solving a host of graph-based problems.  This suggests that a moderate increase in width can allow much shallower models, which are advantageous in terms of inference and train time. For other problems, we show that quadratic width is required. Our results demonstrate the complex and intriguing landscape of transformer implementations of graph-based algorithms. 
We empirically investigate these trade-offs between the relative powers of depth and width and find tasks where wider models have the same accuracy as deep models, while having much faster train and inference time due to parallelizable hardware.

Depth-Width Tradeoffs for Transformers on Graph Tasks
Gilad Yehudai"
Clayton Sanford Google Research
Maya Bechler-Speicher Meta AI
Courant Institute of Mathematical Sciences,
New York University
gy2209@nyu. edu edu
Or Fischer Bar-Ilan University
Ran Gilad-Bachrach
Department of Bio-Medical Engineering.
Edmond J. Safra Center for Bioinformatics, Tel-Aviv University Tel Aviv University
Amir Globerson Google Research
Tel-Aviv University
Abstract
Transformers have revolutionized the field of machine learning. In particular, they can be used to solve complex algorithmic problems, including graph- based tasks. In such algorithmic tasks key question is what the minimal size of transformer that can implement the task. Recent work has begun to explore this problem for graph-based tasks, showing that for sub-linear embedding dimension (i.e., model width) logarithmic depth suffices. However, an open question, which we address here, what happens if width is allowed grow linearly, while depth is kept fixed. Here we analyze this setting, and provide the surprising result that with linear width, constant depth suffices for solving a host of graph-based problems. This suggests that moderate increase in width can allow much shallower models, which are advantageous in terms of inference and train time. For other problems, we show that quadratic width is required. Our results demonstrate the complex and intriguing landscape of transformer implementations We empirically investigate these trade-offss between the relative powers of depth and width and find tasks where wider models have the same accuracy as deep models, while having much faster train and inference time due to parallelizable hardware.
graph-based algorithms.
Introduction
The transformer architecture [Vaswani 2017], has emerged as the statc-of-the-an neural network architecture across many fields, including language [Bronn al. 2020), computer vision (Dosovitskiy et al. 2021] and molecular analysis (Jumper et al.] [021]] This success prompts basic question: which algorithms can be implemented using transformers, and how do specific architecture choices affect this capability. Understanding these questions could enable practitioners to design more computationally efficient models without compromising expressivity.
'Equal contribution
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Two significant architectural elements of transformers are the depth (the number of layers) and width (the dimension of their latent representation). Increasing either property increases the expressivity of the underlying architecture, but the qualitative differences between "shallow and wide" and "deep and narrow" architectures are poorly understood. Given the widespread use of specialized parallel hardware for training and serving modern language models, increasing the width has a limited effect on model latency, provided sufficient memory. A wide range of recent theoretical work [see e.g.. Merrill and Sabharwal 2023b Liu et al. [023) explores these fundamental expressivity questions for various benchmark tasks and transformer scaling regimes. However, a complete understanding of the interplay between architecture and algorithmic capabilities and in particular the fine- fineigd interplay between depth and mouth-rreminss elusive. In this work, we aim to crystallize the emergent algorithmic capabilities of transformers occasions when, contrary to conventional wisdom, the benefits of width eclipse those of depth. Specifically, we focus on the following question:
function of model depth and width, and demonstrate
What are the algorithmic capabilities obtained by increasing the width of transformer?
We ground this question in the context of graph algorithmic tasks, which provide a compelling testbed for understanding transformer reasoning. Graph algorithms serve natural "algorithmic playground." encompassing a wide range of well-known problems that span computational classes. Many of these tasks have already been investigated as benchmarks for language models [Fatemi et al.] 2023]. Furthermore, previous theoretical works have routinely employed these algorithmic tasks to unveil the capabilities and limitations of graph neural networks [GNNs, Gilmer et al. 2017]. For example, the theoretical analysis of Loukas (019 revealed lower bounds on the depth and width necessary to determine connectivity. (Sanford et al. [2024a] employed similar analysis to elucidate such trade-off's for transformers. However, their results pertain primarily to the powers of depth and specific edge-list representation. Other scaling regimes- variable width-have yet to be explored in the context of this toolkit.
as transformers with fixed depth and
For such graph reasoning tasks, we are principally concerned with the optimal transformer size scaling as a function of the graph size. Specifically, given graph with n nodes and an encoding of an algorithmic task, such as determining connectivity or counting the number of triangles, we investigate the width necessary and sufficient to solve the task as a function of n. This fixed-depth, variable width setting arguably more pertinent given the aforementioned benefits of width in computational efficiency. Indeed, practical applications of transformers to graphs have width that is often much larger than the number of vertices in the graph
Our theoretical contribution is a novel representational bierarchy that characterizes this depth-width dependence in transformers. Surprisingly, our results show that multiple problems of interest can be solved with fixed depth and linear width with respect to n. We provide empirical support for the advantage of these shallow and wide models.
Our results clucidate a hierarchy concerning the minimum width needed for constant-depth transform- ers to represent solutions to various graph algorithmic tasks. Section 5 esttabisshe the relevance of the linear sealing regime, where the width of the transformer increases linearly in the number of nodes n. Specifically, it considers tasks, such as graph connectivity and detection of fixed length cycles, for which linear width is necessary and sufficient for dense graph input. Section demonstrates that more complex tasks, including subgraph counting and Eulerian cycle verification, require super-linear and near-quadratic width respectively. The resulting hierarchy over transformer widths induced by our collection of positive and negative results is visualized in Figure ! which ranges from local can be solved with constant width (such as computing the degree of each node), to arbitrary functions that require quadratic width scaling. Some of the lower bounds are conditional on the well known one vs. two cycles conjecture (see appendix I.I for a formal statement).
node-level tasks that
The empirical results of Section @ddmonstradmana the relevance of our results in practice. We consider various graph problems, and experiment with varying the depth and width of the model under a constraint on the overall parameter count. Our results demonstrate that shallower and wider models are significantly faster than narrow and deep models.
SSee Table 3 for a list of commonly used graph datasets (including molecular datasets) where the average graph size in the data is less than 40.
2

---

2
Related Works
Expressive power of transformers Trans- former with arbitrary depth (Wei et al., 202T Yun et al. 2020 or arbitrarily many chain-of- thought tokens (Malach, 2023] are known to be universal approximators. Informally, these re- sults suggest that any algorithm can be simulated with sufficiently large transformer. They, how- ever, leave open more fine- fine-graing sree-graied questions about more compact transformer implementa- tions of given algorithm, particularly in terms of parameter count and depth.
Arbianay f(.4)
Fulerian sycle verilcation
Awanhgraph detection
Oue eyele vs two twolgyeles
Senort ond
Various theoretical techniques have been em- ployed to develop more precise understand- ing of the relevant scaling trade-offs. For in-
A' computation
fooen LM
thever SM
cycle desection (dogroewd)
stance, Merrill and Sabharwal [2033a] show that constant-depth transformers with polynomial width can be simulated by TC Boolean circuits, implying that they cannot solve problems like graph connectivity. These results provide essen- tial context for our paper, where we introduce scaling regimes where transformers can and can- not learn such fusks.Similarly, (Hao et al. [2022] identify formal language classes that can and cannot be recognized by hard-attention trans-
Node degree
(pee()))
O(v) (12-te)
O(n))
Figure 1: The width complexity hierarchy of graph tasks for transformers with constant depth. Each row visualizes the width regimes where the task is solvable (blue) or hard (red).
formers. Another way to augment transformer expressivity is to use chain-of- ofain-of-thought reasoning (Weil al. 2022 Indeed, it has been shown that sufficiently long chains reasoning can simulate finite-state
automata Liu et al. 2023 Li et al. 2024].
A different perspective frames transformers in terms of communication complexity. Sanford et al. [2024cbb draw an analogy between transformers and the Massively Parallel Computation (MPC) framework [Karloff et al.) (2010]. similar to prior work linking GNNs to the CONGEST model in distributed computing [Loukas] [219]. [Sanford al.] [2024 extend this analogy define transformer complexity hierarchy for graph tasks.
Graph transformers and GNNs Research in transformers and graph neural networks (GNNs) reveals a rich overlap. primarily because both are fundamentally message-passing models. Substantial research effort has been devoted to the study of hybrid architectures to combine GNNs intrinsic encoding of input graphs and transformers' empirical successes. A variety of approaches to model hybridization have been explored, including the incorporation of graph structure directly into attention layers /Veličković et al. 2018 Brody et al. 2022). as subgraph features in positional encodings (Zhang et al. 2020), and spectral features of the graph Laplacian matrix [Kreuzer al. 2021 The aim of this work to understand transformer architectural trade-offs rather than to introduce novel architecture. However, the graph encoding schemes employed in this paper draw upon key insights from this literature. We primarily utilize a simple adjacency encoding in order to isolate the focus of study to the impacts of changing the embedding dimension, but also investigate some theoretical and empirical trade-offs for spectral Laplacian -based encodings (Appendix A).
3
Problem setting and notations
3.1
Transformers
We consider the following setting of transformers: the input is sequence of N tokens Xi,..., X where X; E Rda, We denote by (0) E x the matrix where the i-th column is equal to x;- Each layer of the transformer applies self-attention mechanism the inputs, and then an MLP. We denote the input to layer e by X ((-1), The self-attention at layer l with H heads is parameterized by

---

matrices k/ 10 E ERaxm v E mm
It is defined as:
H
z
10 x (e-
SMM(((e-)) 1r x((-1),
h=1
where SM is row- wise softmax, and m is the hidden embedding dimension. The output is of dimension 7 E m This is followed by residual connection, so that the output of the self-attention layer is x = z + ((-1).
Finally, we apply MLP ; - R" with ReLU activations on each token separately (i.e. each column of (()). The output of the MLP is X and is the input the next layer. We let : RR + R denote the ReLU activation. Critically, we assume that the MIP layer can compute arbitrary functions of each individual token embedding x( While involved. this assumption is common in the theoretical literature [see e.g. [Sanford et al. 2024b] and enables a theoretical understanding of the modeling limitations imposed by the attention layer. However, we note that in all our constructions, the size of the MI.P is at most polynomial in the number nodes in the input graph. Our MI.P layers further incorporate arbitrary positional encodings of the index i N .N), for some g. This of each token embedding x i.e. (²((()))) = (o(X((, .).... g (x
formalism allows standard transformer positional encodings to be implemented in our theoretical model. Normalization layers-which are not explicitly accounted for in our transformer definition-
be similarly incorporated by taking advantage of the arbitrary MLP assumption without changing the results.
The bit- te--precision of all our transformers will be Ollogn). where is the number of input tokens. This is a common assumption in many previous works Sanford et al. (2024c b). Merrill and Sabharwal 2022b 2024], and is relatively mild. It is also a necessary requirement for representing number of size n, e.g. when having positional embeddings for n tokens. We will denote m = max(mo...... mL) the embedding dimension, and dn the input dimension.
Graph Inputs Because the network topology of transformers (unlike GNNs) does not encode the structure of an input graph, graph structure must be encoded explicitly into the input of the transformer. Choosing the format of this tokenization scheme for graph inputs is significant modeling decision. The most fundamental aspect of that choice involves deciding between edge-wise and node-wise schemes. (Sanford et al. [2024a] employ an edge-list tokenization that converts the graph into sequence of discrete edge tokens. However, this scheme suffers computationally for large graphs; the quadratic computational bottleneck of self-attention can result in an (2(n²) runtime for dense graphs with n nodes.
In contrast, we consider node-wise encodings, where each node corresponds exactly one input embedding. Our primary theoretical results use what is arguably the simplest such representation: the node-adjacency tokenization scheme. In this representation, each input embedding directly encodes a node's 8 edges as an adjacency vector. That is, for graph G with n nodes and adjacency matrix A E {0, 1]"xa, the ith token input x; E R" the transformer is defined as the ith row of A. An alternative node-wise scheme is the Laplacian eigenvector tokenization [Kreuzer et al. [021]. which captures global graph structure node-wise in lossy manner with the most significant eigenvectors of the Laplacian matrix. We empirically contrast the node-adjacency scheme with both alternatives in Section 6 and we further explore the representational properties of the Laplacian tokenization in Appendix
The adjacency node embedding is not permutation invariant, similar to the edge-list embedding used in Sanford et al. [2024a]. Namely, if the tokens contain positional embeddings, then changing the order of the tokens may also change the output. These embeddings are used for technical convenience, especially since spectral embeddings that are permutation invariant are difficult to analyze for combinatorial problems (such as connectivity, subgraph counting, etc.). In section provide experiments that justify the use of such embedding on real-world datasets.
Exceet for the first layer where k/. Q/00 ddo, vi00 mx

---

4 The Expressive Power of a Linear Embedding Dimension
In this section we focus on two graph reasoning tasks: the 1 vs. 2 cycle problem and the cycle detection problem. We show that a -eeeh transformer can solve these tasks with only linear width. We also show that these results are tight. All the proofs for the theorems in this section are in Appendix [B] Finally, in Sec, S.3. we show that for cycle detection in bounded degree graphs, sublinear width suffices. Note that the node degree task as appears in fig. (namely, calculating the degree of each node) can be easily solved with an (llo((n) embedding size, as shown e.g., Sanford et al. (2024a]
4.1 A linear width solution for 1 vs. 2 cycle detection
Previous works on the connection between the MPC model and transformers have shown conditional lower bounds for solving certain tasks. One such lower bound includes the vs. 2 cycle problem. Namely, determine whether an n-node graph is one cycle of length n or two cycles of length " Conjecture 13 from Sanford et al. [2024a] (see also Ghaffari et al. (2019) states that any MPC protocol with n 2- memory per machine for any E (0, 1) cannot distinguish between the two cases, unless the number of MPC rounds is 2(log n.). This condition implies that transformers with an embedding dimension of ((n--s) cannot solve this task. For a formal definition, see appendix B. We demonstrate the tightness of this bound by showing that a transformer with linear embedding dimension can solve this task:
Theorem 4.1. There exists a transformer with 2 layers of self-attention, and embedding dimension (n) that solves the 1 vs. 2 cycle problem.
The proof intuition is that the graph contains only n edges, can stack all of them into single token. After doing so, we can use the MLP to solve it. This demonstrates the brittleness of communication- based transformer lower bounds, since even a slight increase in the embedding dimension breaks them. With that said, this result is not surprising, since the graph in this task is very sparse.
The connectivity problem for general graphs cannot be solved in this manner. The reason is that for graphs with n nodes there are possibly Q(n²) edges, and thus it is not possible to compress the entire graph into single token with linear embedding dimension. However, the connectivity problem can still be solved by increasing the embedding dimension by polylog terms, as we explain below.
Ahn et al. [2012] uses linear sketching to solve the connectivity problem on general graphs with On log" (n)) total memory. The idea is to use linear sketching, which is a linear projection of the adjacency rows into vectors of dimension Oppoly log(n)). Although this is a lossy compression, still allows to solve the connectivity problem. As consequence, we can use a similar construction as in Theorem 4.1 where we first apply the sketching transformation to each token (i.e. row of the adjacency), then embed all the tokens, into single token and use the MLP to solve the problem using the algorithm from Ahn et al. (2012) (Theorem 3.1). Note that this construction works only in high probability rather than deterministically. since the linear sketching requires using a random matrix, which compresses successfully the adjacency matrix only with some high probability. Thus, we don't present it here formally, but rather proof sketch.
Our next results include problems that cannot be solved by simply compressing all the information of the graph into a single token, and require a more intricate use of the self- celf-attention layers.
4.2 Linear width is necessary and sufficient for 2-cycle detection
This section shows that for the problem of cycle detection, linear width is sufficient for solving the task with fixed-depth, and is also necessary. We consider the 2-cycle detection problem for directed graphs. The task is to find nodes u and v such that the edges (u, v) and (v, u) exist. We begin with the lower bound for this case.
Theorem 4.2. Let T be transformer with embedding dimension m depth L, bit-precision p and H attention heads in each layer. Also, assume that the imput graphs to T are embedded such that each token is equal to row of the adjacency matrix. Then, T can detect 2-cycles on directed graphs, the following must hold: (1) Tf has residual connections then mpH I. = Wn)); or (2) IfT doesn't have residual connections then mpli M(n).
5

---

The proof uses a communication complexity argument, and specifically a reduction to the set disjointeess problem. For a formal definition see Appendix B This lower bound is stronger than the lower bounds in Section 4.1 in the sense that they cannot be circumvented by logarithmic depth. For example, assume that the emhedding dimension is m = O(n²==) for some E (0, 1), and that H = O (Iog(n)) (which is often the case in practice). Then, transformers with residual connection require a depth of Q(n²) to solve this task, which is beyond logarithmic, while transformers without residual connections cannot solve it. This lower bound is also unconditional, compared to the lower bounds from Sanford et al. [2244] which are conditional on the hardness of the I vs. 2 cyclee problem (Conjecture 13 therein). The caveat of this lower bound is that it relies on having the input graph specifically embedded as rows of the adjacency matrix.
We now turn to show upper bound for this task. We will show an even more general claim than detecting 2-cycles. Namely, that depth I. transformers with (()) embedding dimension can calculate the T.-th power of an adjacency matrix of graphs. In particular, the trace of A equals the number of cycles of size L in the graph (multiplied by an appropriate constant). Thus, a 2-layer transformer with linear embedding dimension can already solve the directed 2-cycle problem.
Theorem 4.3. There exists an OLL)-layer transformer with embedding dimension m = O(n) such that, for any graph embedded rows of adjacency matrix A, the output of the transformer in the i-th token is the i-th row of A
The constructive proof of this theorem carefully selects key and query parameters to ensure that the output of the softmax matrix approximately equals A. This enables an inductive argument that encodes A in the value matrix of the 9th layer, in order to compute A++1
The above theorem shows that having a transformer with embedding dimension proportional the graph size is representationally powerful. Namely, At, counts the number of walks of length L form node to node j. This also allows determine whether a graph is connected, by checking whether A" doesn't contain any zero entries. Although. there are other algorithm (e.g. those presented in Section 4.1 that can solve the connectivity task more efficiently.
4.3 A sublinear width solution for cycle detection in bounded degree graphs
The results of the previous section establish that for worst-case graph instance, transformers with node-adjacency tokenizations require a linear embedding dimension to solve simple graph reasoning tasks, such 2-cycle detection. This fact is perhaps unsurprising because each node-adjacency tokenization input is a length-n boolean vector, which must be compressed in a lossy manner if the embedding dimension m and bit precision p satisfy mp = o(n). It is natural to ask whether such results apply to sparse graphs as well, such as graphs with bounded degree. Here, we show that requisite embedding dimension to detect 2-cycles scales linearly with the degree of the graph.
Theorem 4.4. For any n E N and S n, there exists a single-layer transformer with embedding dimension O(dlog n) that detects 2-cycles in any graph with node degree at most d. This embedding dimension is optimal up to logarithmic factors.
The proof reduces the dimensionality of the input adjacency matrix by incorporating vector em- beddings from Sanford et al. [2024c] into the key, query, and value matrices to produce a "sparse attention unit," whose activations are large when respective cycle exists.
5 The expressive power of sub-quadratic embedding dimension
Thus far, we showed that there are graph problems that can be solved with fixed depth and linear width. A natural question is if there are problems where larger width is necessary? Intuitively, quadratic width should suffice for solving any task, since it can be used to record the entire graph, and then a sufficiently expressive MLP can solve the task. But are there problems where quadratic width is necessary. In Sec. 5. show that for the problem of Eulerian cycle detection, quadratic width is necessary. This leads to the interesting question of whether there are problems that require super-linear but sub-quadratic width (i.e., between linear and quadratic). We offer first result in this direction by showing in Sec. 5.2 that such width is sufficient for the problem of sub-graph counting.

---

5.1 Necessity of nearly-quadratic width for Eulerian cycle detection
therefore As mentioned above, quadratic width trivially suffices for solving graph problems. interesting to understand whether this upper bound is tight for some graph problems. We affirmatively answer this question with the Eulerian cycle verification problem. Given a graph and list of "path fragments," " where each fragment consists of a pair of subsequent edges in a path, the goal of the Eulerian cycle verification problem is to determine whether the properly ordered fragments comprise an Eulerian cycle We establish the hardness of this problem on mulli-graphs under the well-accepted "I vs. cycle" conjecture.
Theorem 5.1. Under Conjecture 2.4 from Sanford et al. (2024b], the Eulerian cycle verification problem on multigraphs with self loops cannot be solved by transformers with adjacency matrix imputs if m = O (n²- for any constant > O, unless L = (loog(n)).
The proof relies on a novel reduction to the vs. cycle problem. The difficulty with the reduction is that the one vs. two cycles problem consists of a sparse graph with only edges and nodes, and to show a sub-quadratic lower bound need a dense graph with M(n²) edges and n nodes. To this end, we do a random projection of an instance of the one vs. two cycles problem with n² nodes to a multigraph with nodes, where each node represents nodes in the original graph, but keeping all the edges. This allows us to produce dense multigraph, for which solving the Eulerian cycle verification problem will solve the one vs. two cycles problem in the original graph, before the projection.
5.2 Sub-quadratic solutions to sub-graph counting
Subgraph detection and counting are central tasks for fields as diverse as biology, organic chemistry, and graph kernels (see Jin et al. [2020]] | Tiang al. (2010), Poope et al.] [2018), [Shervashidze et al. 2009]: see also the discussion in Chen et al. [2020). In what follows we show that this problem can be solved with transformers with fixed depth, but width that is between linear and quadratic.
Theorem 5.2. Let k. E N. and let G' be a graph with k nodes. There exists transformer with O(1) self-attention layers and embedding dimension O (n²-1/k) that, for any graph G of size n, counts the number of occurrences of G' as a subgraph of
In contrast, known GNN constructions [e.g.. see Chen al. 2020 entail higher-order constructions with k-IGN models, which require computing practically-ifeassibe
k-order tensors. These models require depth of k to recognize subgraph of size k; where each layer uses a k-tensor instead of standard matrices, which requires n² parameters each. Even for k = 3 or k = 4 this may be too large for graphs with few hundreds of nodes.
Our proof implements the seminal "tri-tri-again" algorithm [Dolev et al. 2012] using transformers. Given a graph with n nodes, we partition the nodes into n/ disjoint sets, each containing n 1/k nodes. For each possible combination of k such sets, we use an MLP to count the given subgraph in 1/k
it. There are (" A < 8-/R = n such combinations of sets, each one containing at most n 2-2k edges. Thus, each token with a large enough embedding dimension can simulate one combination of subsets, cumulating all the relevant edges. Note that subgraph detection is a sub-task of counting, where the number of occurrences is larger than O.
Theorem 5.2 can compared to Theorem 23 Sanford et al. [202a] that provides a construction for counting k-cliques using transformers with sub-linear memory and additional blank tokens. There, it was shown that it is possible to count k-cliques with a transformer of depth (log log(n)). however the number of blank tokens O(n^ in the worse case. Here, blank tokens refer to empty tokens that are appended to the input and used for scratch space as defined in Sanford et al. [2024a]. In our result, we require depth of O(1), and the total number of tokens is n, while the embedding dimension is super-linear (but sub-quadratic). Thus, our solution has better memory usage, since the increase in width is only polynomial, but the number of tokens is n instead of O(r²).
Remark 5.3. We note that the overall computation time of our depth ((1) model above is still exponential in l due to the size of the MLP. This is also the case in Theorem 23 from Sanford et al. [2024a]. In fact, is a common conjecture the literature that no (possibly randomized) algorithm
'Recall that Eulerian cycle is cycle over the entire graph that uses each edge exactly once.
7

---

Toltrog my (98))
Depth 1, Width 125
Depth 2. Width
Depth 4, Width 53
Acourway
Depth
Depth 10, Width 40
Depth 1, Widih
Desth 2, Widh 88
4,
Depth 8, Widhh 45
(1. 125)
12. 89)
16, 55)
18. 46)
(10, 40)
Dupth,
Epoch (b)
Epach
(a)
(c)
Figure 2: Training and inference times (a), training loss curves (b), and accuracy curves (c) for the connectivity task over graphs with 100 nodes, across transformers with approximately 100k parameters, varying in width and depth. While the loss and accuracies remain consistent, shallow and wide transformers demonstrate signifi- cantly faster training and inference times.
can detect k-cliques in time less than O(π22/3-c) for any e > (see Hypothesis (2018)).
Williams
6 Experiments
We showcase the effect of width growth in transformers by training variety of models synthetic graph algorithmic tasks. Section 6.T establishes the relative advantages scaling width over depth by training family of models with similar parameter counts and variable network topologies; results show that the shallower and wider models yield the same accuracy as the deeper models, but with faster training and inference. Section evaluates the critical width at which the substructure counting task becomes solvable, and shows that is roughly linear. Section 6.3 demonstrates the trade- offs of each graph encoding scheme adjaenay versus edge-list versus Laplacian-eigenvectorr on different tasks
In our experiments, we used a standard transformer architecture using Pytorch's transformer encoder layers [Paszke et al. 2019]. Specifically, each layer composed of Multi-Head Self-Attention, Feedforward Neural Network, Layer Normalization and Residual Connections. More experimental details are provided in Appendix
For all experiments in Section 6. and Section 6.2 we used the adjacency rows tokenization as described in Appendix D We considered the tasks of connectivity, triangles count, and 4-cycle count. For the counting tasks, we used the substructure counting dataset from Chen al. [2020), where each graph was labeled with the number of pre-defined substructures it contains, as graph regression task. For the connectivity tasks, we generated synthetic graphs, and the label indicates whether the graph connected or not. the datasets information is described in detail in Appendix
described in Section 5.2 Details of the implementation
6.1 Empirical trade-off's between width and depth
In this subsection, we examine the empirical trade-offs between depth and width in transformers. We show that when using transformers that are shallow and wide, the training and inference times significantly lower than when using deep and narrow transformers. This is while test error and training convergence rates are empirically similar.
We trained a transformer with a fixed amount of 100k parameters split between varying depth and width. We examine how the running time, loss, and generalization depend on the width and depth. We examine the following pairs of (depth, width): (1, 125), (2, 89), (4, 63), (8, 45), 40). We train each model for 100 epochs and examine the following: the total training time, the total inference time, the training loss and test performance (accuracy for classification and MAE for regression). We
Coode is provided in the Supplementary Material.

---

the model failed to fit the data. The critical width defined as the width where the training loss platcaued at more than 0.05, To determine the critical width, we conducted a grid search each combination of graph size and model width, and selected the model that fitted the data considered are repeat this experiment with graph sizes 50 and 100. We report the averages over 3 runs with random we tuned are provided in Appendix
seeds. The
The results for the connectivity task over 100 nodes are presented in Figure 2 Additional results for the counting tasks and different graph sizes, present the same trends, and are provided in Appendix [ due to space limitations, As shown in Figure 2(b) and Figure 2(c) the training loss and accuracy remain consistent across all depth and width configurations. However, Figure 2(a) reveals that shallow and wide transformers significantly reduce the total training and inference time compared to their deeper and narrower counterparts. This may be due the ability of GPUs to parallelize the computations across the width of the same layer, but not across different layers.
6.2 Minimum width for substructure counting
In this subsection, we show that the transformer width required to the substructure counting tasks increases sub- cuub-uddraticallyy with the num- ber of nodes, as argued Section [2.2 The experiments considered graphs with increasing numbers of nodes, ranging from 50 400 in
400
430
Crifical Width
830
increments of 50, and transformer widths vary-
ing from 100 to 800 in increments of 100. For each combination of graph size and transformer width, we determined the critical width which
50 130
100
200
200 300
30
Number of Nodes
(a)
Figure 3: Critical width evaluation for the 4-Cycle Count task, using transformer with layer. The points indicate the critical width at which the model fails to fit the data.
best. The typer-parameter provided in Appendix E
To isolate the effect of width, we used trans- former model with one layer. tention heads to ensure there exists width for which the model can the data for all the evaluated graph sizes. The results for the 4-Cycle count task are presented in Figure Due to space limitations, the results for the triangle count task deferred to Appendix Figure shows that the critical width increases roughly linearly with the graph size.
used two at-
6.3 Comparison of graph encodings
In this paper, we focus graph tokenization where each row of the graph's adjacency matrix treated as a token for the model. This tokenization offers significant efficiency advantages for dense graphs, as the edge-list representation requires O(n²) tokens, whereas the adjacency-row representation reduces this to On)). To validate the effectiveness of this tokenization approach in practice, we evaluate it real graph datasets.
We compared the adjacency-row representation to the edge-list representation by training a trans- former model on three Open Graph Benchmark (OGB) Hu et al. (2020) datasets: ogbg-molhiv, ogbg-molbbbp. and ogbg-molbace. ogbg-molhing the task is to predict whether a molecule inhibits HIV replication, a binary classification task based molecular graphs with atom-level features and bond-level edge features. ogbg-bbbp involves predicting blood-brain barrier permeability, a crucial property for drug development. ogbg-bace focuses predicting the ability of a molecule to bind to the BACE1 enzyme, associated with Alzheimer's 's disease. We also evaluated a tokenization using the eigenvectors and eigenvalues of the graph Laplacian, commonly used in the literature (Dwivedi and Bresson, 2021 Kreuzer et al. 2021 More experimental details, including the dataset statistics can be found in Appendix
The results of our evaluation are summarized in Table T In all three tasks, the adj-rows representation
achieved better ROC-AUC scores than the edge-list representation. In two out of the three, it also

---

Table 1: ROC-AUC performance metrics for different graph representations: Edge List, Adjacency Rows, and Laplacian Eigenvectors (LE), averaged over 3 random seeds.
Dataset
Tokenization
MOLHIV
MOLBBBP
MOLBECA
EigeList
54.01
64.73
66.06433.86
AdjRows
01.87+1.10
67.53
68. 68.64
LE
68. 1.52
55.31 L4.79
63.61 12.31
improved upon the commonly used Laplacian eigenvectors representations. The results suggest that the adjacency representation we use in this paper empirically effective, and should be considered alongside the commonly used Laplacian eigenvector representation.
7 Discussion and Future Work
This paper uses collection of graph algorithmic masks-includingg subgraph detection, one vs two cycles, and Eulerian cycle verification-tue demonstrate the powers of width bounded-depth transformers that take as input node adjacency encodings. These results include sharp theoretical thresholds that demonstrate the trade-offs between constant, linear, quadratic, and intermediate width regimes. Our empirical results validate the efficiency and accuracy of our choice of scaling regime and embedding strategy.
There numerous possible extensions of this work. One future direction study different graph tokenization schemes, beyond the node-adjacency encoding of this work and edge-list encoding of Sanford et al. [2024a] particularly notable alternative the smallest eigenvectors of the graph Laplacian, presented as vector of components for each node. This spectral embedding is a standard embedding scheme for GNNs, and the techniques and tasks developed in this paper would likely be relevant to proving similar bounds. We provide preliminary exploration of the trade-offs between the intrinsically local characteristics of adjacency- -haased tokenization schemes and more global spectral approaches in Appendix A Another future direction is to study the optimization and generalization capabilities of transformers to solve graph problems, beyond the expressiveness results presented in this work.
Acknowledgments
This work was supported in part by the Tel Aviv University Center for AI and Data Science (TAD), the Israeli Science Foundation grants 1186/18 and 1437/22. OF was partially supported by the Isracli Science Foundation (grant No. 1042/22 and 800/22). We thank Joan Bruna for the helpful discussions while this work was being completed.
References
K. J. Ahn, S. Guha, and A. McGregor. Analyzing graph structure via linear measurements. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 459-467. SIAM, 2012.
S. Brody, U. Alon, and E. Yahav. How attentive are graph attention networks?, 2022.
T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, al. Language models are few-shot learners. Advances in neural information processing systems, 13:1877-1901, 2020.
E. Candes and T. Tao. Decoding by linear programming, 2005.
Z. Chen, I.. Chen, Villar, and Bruna. Can graph neural networks count substructures?, 2020. URL https: //tpxiaxvvvv//////////aa///aaav/ org/ absp: 04025
10

---

G. Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
D. Dolev, C. Lenzen, and S. Peled. "tri, tri again": finding triangles and small subgraphs in distributed setting. In International Symposium on Distributed Computing, pages 195-209. Springer, 2012.
A. Dosovitskiy, L. Beyer, Kolesnikov, D. Weissenborn, X. Zhai, Unterthiner, M. Dehhhhnn. M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby. An image is worth 16x words: Transformers for image recognition at scale, 2021. URL http::tps:/ htapss://arxvv.ooo org abs/ 2010. 11929
V. Dwivedi and X. Bresson. A generalization of transformer networks to graphs, 2021. URL https://arxiv.oom org/ abs/2012. 09699
B. Fatemi, Halerow, and B. Perozzi. Talk like graph: Encoding graphs for large language models, 2023.
M. Ghaffari, Kuhn, and Uitto. Conditional hardness results for massively parallel computation from distributed lower bounds. In 20/9 IEFE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1650-1663, IEEE, 2019.
J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. International conference on machine learning, pages 1263-1272. PMLR, 2017.
Y. Hao, D. Angluin, and R. Frank. Formal language recognition by hard attention transform- ers: Perspectives from circuit complexity. Transactions of the Association for Computa- tional Linguistics, 10:800-810, 2022. ISSN 2307-387X. doi: 10.1162/ URL
http://das www.ddo....oo.oooo....... 10. we1116/2ccc... 00490
W. Hu, M. Fey, M. Zitnik, Y. Dong. H. Ren, B. Liu, M. Catasta, and Leskovec. Open graph benchmark: Datasets for machine learning graphs, 2020.
C. Jiang, F. Coenen, and M. Zito. Finding frequent subgraphs in longitudinal social network data using weighted graph mining approach. In Advanced Data Mining and Applications: 6th International Conference, ADMA 2010, Chongging, China, November 19-21, 2010, Proceedings, Part 6, pages Springer, 2010.
W. Jin, R. Barzilay, and T. Jaakkola. Composing molecules with multiple property constraints. arXiv preprint ar XXiv:2002.03244 2020.
Jumper, R. Evans, A. Pritzel, T. Green, M. Figurnov, O. Ronneberger, K. Tunyasuvunakool, R. Bates, A. Zidek, A. Potapenko, et Highly accurate protein structure prediction with alphafold. 2021.
nature, 596(7873):583-568
H. Karloff, S. Suri, and Vassilvitskii. A model of computation for mapreduce. In Proceedings of the Twenty-First Annual ACM-SIAM Symposiun on Discrete Algorithms, SODA '10 page 938 948, USA, 2010. Society for Industrial and Applied Mathematics. ISBN 978089871 16986.
D. Kreuzer, D. Beaini, W. I.. Hamilton, V. Létourneau, and P. Tossou. Rethinking graph transformers with spectral attention, 2021. URL hott:t:////s///tt hwtp:/ooggg/bbb//bbee 03893
M. Leshno, V. Y. Lin, A. Pinkus, and S. Schocken. Multilayer feedforward networks with nonpolynomial activation function can approximate any function. Neural networks, 6(6):861-867, 1993.
7. L., H. Liu, Zhou, and Ma. Chain of thought empowers transformers to solve inherently serial problems, 2024.
B. Liu, J. T. Ash, S. Goel, A. Krishnamurthy, and Zhang. Transformers learn shortcuts to automata, 2023. URL https:::::// // arxiv. org/ abs///ss/2221 10749

---

A. Loukas. What graph neural networks cannot learn: depth vs width. arXiv preprint arXiv:1907.03399, 2019.
E. Malach. Auto-regressive next-token predictors are universal learners, 2023.
Mendelson, A. Pajor, and N. Tomezak-Jaegerman. Reconstruction and subgaussian operators, 2005.
W. Merrill and A. Sabharwal. The parallelism tradeoff: Limitations of precision transformers. Transactions of the Association for Computational Linguistics, 11:531-544 2023a. ISSN 2307-
387X. doi: 10.1 162/tacllaa00aa555111111_1L21110 00562. URLhhttp::/dl dx www.dooo.o/ooo..ooooo..ooo...... www./..gg..... 10. www.1/t11ccccc. a_ a_00662
W. Merrill and A. Sabharwal. The parallelism tradeoff: Limitations of bog-prrcision transformers.
Transactions of the Association for Computational Linguistics, 11:3115455, 2023b.
W. Merrill and A. Sabharwal. A logic for expressing log-precision transformers. Advances in Neural Information Processing Systems, 36, 2024.
C. Morris, N. M. Kriege, F. Bause, K. Kersting, Mutzel, and M. Neumann. Tudataset: A collection of benchmark datasets for learning with graphs, 2020. URL httptttss////ii.ccoo org/ hwtggg//b//00077/ 08663
A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, I.. Antiga, et al. Pytorch: An imperative style, sigh-performance deep learning library. Advances in neural information processing systems, 32, 2019.
Pope, S. Kolouri, M. Rostrami, C. Martin, and H. Hoffmann. Discovering molecular functional groups using graph convolutional neural networks. arXiv preprint arXiv:1812.0026: 2018.
C. Sanford, B. Fatemi, E. Hall, A. Tsitsulin, M. Kazemi, J. Halcrow, B. Perozzi, and V. Mir- rokni. Understanding transformer reasoning capabilities via graph algorithms. arXiv preprint arXiv:2405.18512. 2024a.
C. Sanford, D. Hsu, and M. Telgarsky. Transformers, parallel computation, and logarithmic depth, 2024b.
C. Sanford, D. J. Hsu, and M. Telgarsky. Representational strengths and limitations of transformers. Advances in Neural Information Processing Systems, 36, 2024c.
N. Shervashidze, S. Vishwanathan, T. Petri, K. Mchlhom, and K. Borgwardt. Efficient graphlet kernels for large graph comparison. In Artificial intelligence and statistics, pages 488 495. PMLR, 2009.
A. Vaswani. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
C. Wei, Y. Chen, and T. Ma. Statistically meaningful approximation: a case study on approximating turing machines with transformers, 2021.
J. Wei, X. Wang, D. Schuurmans, M. Bosma, Xia, E. Chi, Le, D. Zhou, et al. Chain-of ofain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 00044844-48877 2022.
V. V. Williams. the international congress of mathematicians: Rio de janeiro 2018, pages 3447-3487. World Scientific, 2018.
On some fine-grained questions in algorithms and complexity. In Proceedings of
G. Yehudai, H. Kaplan, A. Ghandeharioun, M. Geva, and A. Globerson. When can transformers count to n? arXiv preprint arXiv:2407. 15160. 2024.
C. Yun, S. Bhojanapalli, A. S. Rawat, S. J. Reddi, and S. Kumar. Are transformers universal approximators of ggquence-to-sqqeeme functions?, 2020. URL https://arxivvorg/abbt 1912.100777
Zhang, H. Zhang, C. Xia, and I.. Sun. Graph-bert: Only attention is needed for learning graph representations, 2020. URL httpt::/t//attt wwwaaiiiwrgg/aaaaaaaaaa abs//001s/0011... 05140
12

---

A Alternative tokenization approaches
While the primary aim of this paper is to study the properties of the node-adjacency tokenization scheme in terms of its width and depth trade-off's, we also establish clear trade-off's between this scheme and other encoding schemes. The Laplcian-eigenvector tokenization passes as input to the transformer each node's d components of the most significant eigenvectors.
Concretely, let A R"x" be the adjacency matrix of graph and the diagonal degree metrix. A. Denote the eigenvectors of L as Vi..... S An. For some embedding dimension m, we let the m-dimensional Laplacian-eigenveeeee tokenization be V1,...Yu. where y; = (V1,6, Vm,i); we encode the eigenvalues as well as yo (A1.... Am). We contrast this with node-adjacency encodings of embedding dimension m. whose ith input is x; ((A)).
The Laplacian matrix is defined as L = D - -AA
with respective eigenvalues 0 = A S
We note several illustrative toy tasks that demonstrate trade-off's between the two graph tokenization schemes.
Node-adjacency advantage at local tasks The node-adjacency tokenization amenable for analyzing local structures around each node. Most simply, the degree of each node can be computed in a sequence-wise manner with node-adjacency tokenization with embedding dimension m
by simply computing the inner products (1n, x,). Constructions like Theorems 4.3 and 4.4 further demonstrate the abilities of adjacency encodings to aggregate local structures.
In contrast, choosing the smallest eigenvectors in the alternative encoding makes it impossible to even compute each node degree without having embedding dimension m growing linearly in the node count
Laplacian-eigenveede advantage at global tasks In contrast, the most significant graph Laplacian provide high-level information about the global structure of the graph. Most notably, the tokenization trivializes the connectivity task because a graph is disconnected if and only its second-smallest eigenvalue is zero; transformers with the adjjeenyy tokenization require either depth 2((lgg n) or width (T)) to solve the same problem.
Other properties of structured graphs reveal themselves with low-dimensional Laplacian-eigenvecee tokenizations. For instance, the relative position node in a lattice or ring graph are encoded in the most significant eigenvectors. Graph clustering algorithms could be inferred by transformers that take spectral encodings as input and simulate algorithms like k-means. The hardness of graph connectivity with the adjacency encoding translates to hardness results for efficiently simulating clustering algorithms.
Quadratic embedding equivalence Critically, the above trade-offs occur in small embedding di- mensions. In the regime where = ((n²) and MLPs are universal approximators, both tokenization schemes are universal. The entire graph can encoded in a single token, which can then convert between A and the spectrum of L.
B Proofs from section 4
B.1 The 2 cycle conjecture
The most notable conjecture in distributed computing is the vs. 2 cycle conjecture, which is common method for providing conditional lower bounds in the MPC model. See Definition 2 in Sanford et al. (2024a] for (7, 8P-M protocol. In simple words, this is a distributed computing protocol, where the input has length n, which is distributed to ((n!+>-)) machines, each having
'Consider the task computing the degree of a particular node a graph consisting of disconnected linear subgraphs, each with three nodes connected by two edges. The zero eigenvalue thus has multiplicity 3 and hence the eigenvectors Vi,... va/3 exist solely indicators of connected components. Therefore, if nodes i, j. & comprise cluster and S 5. then their embeddings yi. y,, Ye identical.
"
13

---

memory of s := (n²)). Each communication round, each machine calculates an arbitrary local message bounded by size s, and all the messages are sent simultaneously. The vs. cycle conjecture is the following:
Conjecture B.1 (Conjecture 13 in Sanford et al. (024aa), ). For any 7 0 and ö E (0,1), any (7, 8MP protocol that distinguishes single length-n cycle from two disjoint length-n/ uses (()) communication rounds.
B.2 Proof of Theorem 4.1
Theorem 4.1. There exists a transformer with 2 layers of self-attention, and embedding dimension O(n) that solves the vs. 2 cycle problem.
Proof. The proof idea is embed all the information about the graph into single token, and then offload the main bulk of the solution to the MLP. For that, the first layer will transform the input of each node from adjacency rows only indicate its two neighbors. The second layer will embed all the information over the entire graph into a single token.
We now define the construction of the transformer. The input to the transformer adjacency rows, where we concatenate positional encodings that include the row number. Namely, the i-th input token
is equal to self-attention will not effect the inputs. This can be thought of as choosing V = 0 (while K and Q are arbitrary), and using the residual connection so that the tokens remain the same as the input. We now use Lemma t.2 construct a 3-layer MLP that changes the embedding of each token such that includes for each node its neighbors. The MLP does not change the positional encoding, this can be done since ReLU networks can simulate the identity function by 2 + ((2) a( (-2), where represents the ReLU function. add another layer to the MLP that maps R 3 V; + u, E R3n
X i
where x; is the i-th row of the adjacency matrix of the graph. The first layer of
where (u; (u:)3(1-))))) 1))
and all the other entries of u, are equal to O.
The second layer of self-attention will have the following matrices: K = Q 3 V 13m- Since we used the zero attentions, all the tokens attend in the same way and using the exact same weight to all other tokens. The Softmax will normalize the output by the number of tokens, namely by n. Hence, after applying the V matrix, all the output tokens of the second layer of self-attention will be equal to the sum of all the tokens that were inputted to the second layer.
In total, we get that the output of the second layer of attention is a vector with 3n coordinates, where
represent the two edge (i, k), (j. k). Thus, the entire information each 3 coordinates of the form
of the graph is embedded in this vector. Finally,
the MLP determine whether the input graph, whose edges are embedded as list of edges, is connected, This can be done by an MLP since it has the universal approximation property Cybenko 1989] Leshno al. [199)]. Although we don't 't specify the exact size of this MLP, it can be bounded since there are efficient deterministic algorithms for determining connectivity. These algorithms can be simulated using ReLU networks.
Note that the output the connectivity problem is either 0 or 1, thus is enough to approximate a solution of this task up to a constant error (say, of }). and then use another layer to threshold over the answer.
Lemma B.2. There exists a 3-layer MLP N R" + I2.2 such that for every vector v where there are
i [n] with (v); = (v), = and (v); = 0 every every other entry we have that either N(v) = (3)
or Nrv(v)= = 1 i
14

---

Proof. The first layer of the MLP will implement the following function:
(ivi,(((v;1) Eー -_.)) ((v),
This is linear combination of indicators, where each indicator can be implemented by the function f()) = a (x) oz 1). Note that the input to the MLP is either 0 or in each coordinate, thus
(2 We have that i j and 12 + j determine the values i and j. This means that i +J1 i2 + j2 and oî + गी 2 + j then ii = ig or in = j2 and similarly for i2. Since there are O(n²) different possible values, we can construct a network with
the output of this function will be
J
()) up to changing the order of and j.
2-layers and (r²²) width that outputs
B.3 Proof of Theorem 4.2
Theorem 4.2. Let T be transformer with embedding dimension depth L, bit-precision p and H attention heads in each layer. Also, assume that the input graphs to T are embedded such that each token is equal to row of the adjacency matrix. Then, T can detect 2-cycles on directed graphs, the following must hold: (1) If has residual connections then mpH I. = S(n)) or (2) If doesn't t have residual connections then mpH (2()).
Proof. Our proof relies on communication complexity lower bound for the set disjointness problem, and is similar to the arguments from Sanford et al. [2024c), Yehudai et al.) (2024] The lower bound for communication complexity is the following: Alice and Bob are given inputs a, E {0.1)* respectively, and their goal is to find max agb; by sending single bit-messages each other in sequence of communication rounds. The lower bound says that any deterministic protocol for solving such a task requires at least s rounds of communication.
We set 8 = n², and design a graph G = (V, E) that has a directed 2-cycle iff max a.b; 1. The graph has V 2n, partition the vertices into 2 disjoint sets V/1 V/2 and number the vertices of each set between 1 and n. The inputs a and b encode the adjacency matrices between vertices in Vi and V22 and between vertices in 1/2 and V/2 respectively. Now, there exists directed 2-cycle iff there is some E [s] for which both a; = 1 and b, meaning that max a.b = 1.
Assume there exists transformer of depth T. with H heads, embedding dimension and bit precision p that successfully detects 2-cycles a directed graph. Denote the weights of head i layer & by Qf, K V E m for each i E [H]. and assume w.l.ogg. that they are of full rank, otherwise our lower bound would include the rank of these matrices instead of the embedding dimension (which can only strengthen the lower bound). We design a communication protocol for Alice and Bob to solve the set disjointness problem. The communication protocol will depend on whether T has residual connections or not. We begin with the case that it does have them, the protocol works follows:
1. Given input sequences a, b E 10, to Alice and Bob respectively, they calculate the input tokens .f....,,? .. and 2 #a+11..... 22 respectively. Note that the adjacency matrix have a block shape, thus both Alice and Bob can calculate the rows of the adjacency matrix corresponding the the edges which are known to them.
2. Bob calculates K}a9, )aae. Vise for every head j [H] and transmits them to Alice. The number of transmitted bits is O(mmHp)
3. Alice can now calculate the output of the r-th token after the first layer. Namely, for every head j [H] she calculates:
2n
exp(x
TT KJ" Q)a2))
i=1
2n
t5
Σ
exp(x1
K3 V3
15

---

The output of the j-th head on the r-th token equal 25. For the first n tokens, Alice use the residual connection which adds the tokens that are known only to her. She now passes the tokens through the MLP calculate zj. "i,...,,y,, By namely the output of the tokens known to her after the first layer.
4. Similarly to the previous 2 steps, Bob calculates the tokens x #n+1 ...... 22n which are known only to him.
5. For any additional layer, the same calculations are done so that Alice calculates ,i....,,,, and Bob calculates æf " 22n
In case there are no residual connections, after the third step above Alice have the information about all the tokens. Hence, there is no need for more communication rounds, and Alice can finish the rest of the calculations of the transformers using the output tokens of the first layer.
By the equivalence between the disjointness and the directed 2-cyele that described above, Alice returns iff the inputs max; 0₂b; = I, and 0 otherwise. The total number of bits transmitted in this protocol in the case there are residual connection O(nmpll L), since there are Onump!l) bits transferred in each layer. The lower bound is determined by the size of the input which is = n², hence mpll L Mn).. In the case there are residual connections there is no dependence on L, hence the lower bound becomes mpH = (2)
B.3.1 An extension to bounded degree graphs
In order to prove the optimality result in Theorem 4.4 for the task of determining the existence of 2-cycle in bounded-degree graphs, we state the following theorem.
Theorem B.3. Let I be a transformer with embedding dimension m depth L, bit-precision and H
attention heads in each layer. If can detect 2-cycles on d-degree directed graphs, then:
1. IfT has residual connections then mpHi (dd)).
2. IfT doesn't I have residual connections then mpH (2(d).
Proof. The proof is nearly identical to that of Theorem 4.2 except that we alter the reduction to ensure that that the graph possessed by Alice and Bob is of degree d.
As before, we design a graph G (V, E) with vertices partitioned into two sets Vi, V/2 satisfying [V/ = V22 = Let Eg denote the edges of a bipartite graph between V1 and V22 such that (1) every node has incident outgoing edges; and (2) (i. E Eg if and only (j. i) Eg.
Consider some instance of set disjointness with a, E (0. 13s for 8 = nd. We index the 2s edges in Eg as ef = (ut, vf)..... = (v), v²) and ei = (o? vf),.... . e = (v? vz). Then, we embed the instance by letting of E E if a, = and cf Ef 1. As before, there exists directed 2-cycle in G' if and only if max; a.d; = 1.
The analysis of the transformer remains unchanged. An L-layer transformer with embedding dimension m, heads H, and bit precision transmits OmmmpH L) bits between Alice and Bob. The hardness of set disjointness requires that at least nd bits be transmitted, which means that it must be the case that mphL = l(d).
B.4 Proof of Theorem f
We will need the following lemma for the proof.
Lemma B.4. Lel d1,..., , dge bi,.... by R where the oz are distinct. There exists a 2-luyer jully-connected neural network N IR + R with width O(k) such that N N(a)) = by
Proof. Let 8 = min; [k]la ayl. by the assumption 8 > Let:
1 f((x) I (a(x (a.- 26)) o(x (a, 5) + (a, + 25 x)
-0(0-aa- + -
6xx))
16

---

It is clear that f((a;) = and fi(a)) = 0 for any j # i. Thus, we define the network: N(x)
E b.f((z).
We are now ready to prove the theorem.
Theorem 4.3. There exists an O(L)-layer transformer with embedding dimension m = O(n) such that, for any graph embedded i-th token is the i-th row of A
of adjacency matrix A. the output of the transformer in the
Proof. We will first show the construction for the of L and then show inductively for
A
general L. We define the imput for the transformer X
I
R 3dxd
namely, there
Oaxa
Oaxd/
d tokens, each token contains a column of the adjacency matrix concatenated with positional embedding. The self-Attention layer contains one head with the following matrices:
K k-c- (" Oaxd
Odxd Q = Oaxa
(Oaxd
Q0(axx
Oaxd
V
I
Oaxd
Oaxd
Oaxa/
where e > is some sufficiently large constant the determines the temperature of the softmax. We first have that X KTQ TX A. Since all the values of A either 0 or 1, for sufficiently large > 0, the softmax behave similarly to the hardmax and we get that:
1A2 deg((A) (A)
VXSM(A)
A deg (A) -1
Oaxd
where deg(A) is diagonal matrix, where its i-th diagonal entry is equal to the degree of node i. Finally, apply MLP.V Radxd - Radxd that operates each token separately. We define the MLP such that:
((
A deg(A) (A)-1 deg ()) (4) )
Oaxd -0mma
0 Odxd
N/
N
A A. 0axd
A )()
Constructing such an MLP can be done by calculating the degree of each token from A (eg(A)- and multiplying the first coordinates of each token by this degree. This can be done since the entries of this matrix is either 0 or the inverse of the degree of node i, thus it requires only inverting an integer between and n. By Lemma B.4 this can be done by a 2-layer MLP with width n. This finishes the construction for calculating A².
For general L > we use the residual connection from the inputs. That is, the input the L-th
A I
layer of the transformer is equal to
We use a similar construction as the above, except
A4
Oaxd
)
that the matrix V
I
This way, the output of the self-attention layer is
Oaxd A deg(A) -1 AL+1 deg( A)
and we employ a similar MLP as before to eliminate the deg(A) term.
B.5 Proof of Theorem
Theorem 4.4. For any N and d < n, there exists single-layer transformer with embedding dimension O,dlog n) that detects 2-cycles any graph with node degree at most d. This embedding dimension is optimal up to logarithmic factors.
The optimality result is proved using the same methodology as Theorem 4.2 It is stated and proved formally Thcorem B.3
17

---

The proof of the construction adapts an argument from Theorem of Sanforrd et al. [202cc], which shows that sparse averaging task can be solved with bounded-width transtormers. We make use of the following fact, which is consequence of the Restricted Isometry Property analysis of Candes and Tao 2005], Mendelson et al. [005].
Lemma B.5. For any d v N and p lgd n.), there exist vectors - Yn RP such that for any x E {0, 13 with E; v d, there exists ((x) E TRP such that
(o(x), 1,
ifx; =
1
(0(x), S 2
ixx, O.
We use this fact to prove Theorem 4.4
Proof. Concretely, prove that some transformer T exiits that takes input
x [1]
Xn
(x++))xn
and only if the ith node in the graph whose adjacency matrix is A belongs to directed 2-cycle. We assume that no self-edges exist.
and returns T(X) 10, where 7(X,)
We first configure the input MLP to incorporate the above vectors for node identifiers and adjacency and produce the tokens X (K1.... .x.) m for 2p 2:
((x;) Vi
x;
1
We also introduce a constant-valued "dummy node" In+1, which has no edges and does not appear the output:
0,
0p
X,+1
0
We define linear transforms Q, K, V E Rdx= that satisfy the following, for any E [n]] and some sufficiently large temperature constant e:
o(x;)
Yi ((x))
0,p
0p
Yi
0,
0g
Q& =c
K&; =
KX,-1
VX: =
Vx,+1 = 0ms
Then, for any i,j [n] with * j. the individual elements of the query-key product are exactly
(XT K Q ((6(()))))) + (o(x)).y,))
By applying Lemma B.5 find that
(*T ( 2c,
if xi. 1 and Xj.
(X K (TTTX)),, S 2
otherwise.
In contrast, (KTTX)))4.. = ee for any i.
Thus, for sufficiently large c, all nonzero elements (after rounding) of SM(X KT (X)), be- longs to indices
[n] if there exist at least one 2-cycle containing node if not, then
SM(XTA KT Q())++1+ and all others are zero.
By our choice of value vectors, the ith output of the self-attention unit is e, if there exists 2-cycle and Om otherwise.
18

---

C Proofs from Section
C.1 Proof of Theorem 5.2
Theorem 5.2. Let n n E M, and let G' be a graph with k nodes. There exists a transformer with 0(1) self-attention layers and embedding dimension O (n²-1/k) that, for any graph G of size n, counts the number of occurrences of G' subgraph of G.
Proof. The main bulk the proof will use the transformer to prepare the inputs. We will first explain the layout of the construction, and then present it formally. Each input node is represented as of the adjacency matrix. We will split the nodes into n/// sets, where each set contains n nodes. The first layer will prepare the adjacency rows so that each token will include only edges other nodes from the same set. The second layer will combine all the nodes of each set into separate token. This will use n 1/x tokens, where each of them will contain at most n²² 2-2k/ edges. The last layer will use each token to represent each possible combination of such sets. There are at most (" S n such combinations, and each of them contains at most 2-2k edges. We need an additional n n/// entries for technical reasons do this embedding into all possible combinations of sets.
We now turn to the formal construction. Assume that the nodes are numbered as U1..... Uns and denote by x X,, the row of the adjacency matrix corresponding the nodes. The imput the
transformer of the node 2; will be
R"+1, where is the i-th standard unit vector.
Throughout the proof we assume that n 1/h and n' 1-1k are integers. Otherwise, replace them by their integral value.
Layer 1:
We begin the construction with an MLP that operates on each token separately. This can be viewed if use the self-attention layer have no effect on the inputs, by setting V 0 and using the residual connection. The MLP will implement the following function:
X;
Ra+1 3
W Z
E I
2/222//+22
Intuitively, split the nodes into n 1/k sets, each containing n-11/j nodes. X; will include pruned adjacency row for node with only edges from its own set. w; indicates to which set each node belongs to, and z; indicate the tokens that will store these sets. We first introduce the vectors 1-14
X; E pnn-i/
that are equal to:
3/6
(x:);
Σ ((x))) 1)-1((r-1))) sis r=l
Sis 1(0= +1 mm 2-1//
These vectors can be constructed using a 3-layer MLP. First, note that this function in our case operates only on integer value inputs, since i.j and all the entries of x; are integers, hence it is enough to approximate the indicator function up to a uniform error of z and it will suffice for our purposes. To this end, we define the function:
(2) = (xx - (r - 1)) o(z - r) + alx (s+ - o s). s).
Here = max (0.z) is the ReI.U function. If 2 r 2 We get that (x) = for SerSss = 8, and (2) 0) for <
or 2 + 1. This shows that the functions inside the indicators
be expressed (for integer valued inputs) using a 2-layer MI.. Expressing the multiplication of the indicators can be done using another layer:
g 22, 23) o (2 + 22 + 23 2) 1(2 = 1) 1(2 = 11 1223=11 1)
where 21, 23 E {0, 1}. The width of this construction is O(n) since for each of the n 1/k coordinates of the output we sum 1/k such functions as above.
We define 8; R== 2-2k for = jmod n 11k1/ to be equal to x; in the coordinates (j- 1111111////
until jn 1-1k and all the other coordinates are 0. These vectors will later be summed together across
19

---

all nodes in the same set, which provides an encoding of all the edges in the set. We also define W; e; In** for 1)n + S jn and z; =; E Rn for i 1, 1,... .... 2/k and
Z; 0 otherwise.
Layer 2: We define the weights of the second layer of self-attention in the following way:
0 n22-2/ (22-2/=x2222/2
0 //
K =
I
0₂2 2/ xn2
Q
0 Ont/kxma/K
V
0 02
xj w j
Given two vectors
Wi
which are outputs of the previous layer, we have that:
Zi
Z
T
X;
Xj
Wi
K KTQ
Q
Wj
= (z,, w2). This shows that the first n 1/k tokens, which represent each
Zi
of the n//k sets, will attend with a similar weight every node in their set. After applying the V matrix we use the residual connection only for the positional embedding vectors" (namely, the last 1/k + coordinates). Thus, the output of the self-attention layer for the first n 1/ tokens encodes all the edges in their set in their first 2-22/k coordinates. This encoding is such that there is 1 in the i-th coordinates if there is an edge between nodes va and v, in the set for where and are the unique integers such that i = r(mod n 1-1// and (s 1)n
< 2 Thus, the
Yi
output of the self-attention layer can be written
W;
E RR
42 where y; is either an
Z;
encoding as described above (for i S n// or some other vector (for 2 n 1/A) for which its exact value will not matter. The vector w, is positional embedding that is not needed anymore and will be removed by the MLP, and = for i < 1/k and = 0 otherwise.
We will now construct the MLP of the second layer. First, note that given 1/K sets, the number of all Denote all possible combinations by BI..... B, and let Vi...., Vn E IRnl/* such that (v.), = if B, includes the j-th set, and 0 otherwise. These vectors encode all the possible combinations of such sets. The MLP will apply the following map:
A combinations of such sets is bounded by (m))/)) S f-
yi W;
R //2 42m 12n
3
H
Vi
E
R
1/2
Z:
i
Z;
This map can be implemented by 3-layer MLP. Specifically, the only part coordinates that changes are those of w, which are replaced by v,. This can be done using the function f(i) = Σy= 1
j) Vj. and its construction is similar to the construction of the MLP in the previous layer.
"It is always possible done by doubling number of unaffected coordinates. using the matrix to move the unaffected entries to these new coordinates, and then using a 1-layer MLP to move the unaffected entries to their previous coordinates (which now include what was added through the residual connection). We omit this construction from here for brevity and since only changes the embedding dimension by constant factor.
the residual connection to affect only subset of the coordinates. This be
20

---

Layer 3:
The last self-attention layer will include the following weight matrices:
0 n22-1/K X/2-/1
K
O 0pt/txxarrn)
Q 012-1/4
O 0
V nI 0(2nl//+1))((22/43)
After applying this layer to the outputs of the previous layer, each token i will attend, with similar weight, to all the sets (out of the n 1/ sets of nodes) that appear in its positional embedding vector v, Thus, after applying this layer, The first n2 1/E contain an encoding (as described in the construction of the previous layer) of all the edges in the i-th combination of k sets B;.
Finally, the MLP will be used to detect whether the given subgraph of size k appears as a subgraph in the input graph (which is encoding of the edges). The output of the MLP will be 1 if the subgraph appears and 0 otherwise.
Note that any subgraph of size k must appear in one of those combination of sets. Thus, by summing all the tokens, if their sum is greater than the subgraph of size k appears as subgraph of
C.2 Proof of Theorem
We first define the Eulerian cycle verification problem multi-graphs.
Consider some directed multi-graph G EV for V (V....., on) and E {ei..... eNl, where each edge is labeled as
ej (32.1, E V V x [N].
We say that ej a successor edge of e; if 6.2 C₁, problem instance also contains fragmented path, which is expressed as a collection of ordered pairs of edges P {p) fp'.....p .......p) with
p' = (r/.P)) E E E,
where of and pg are successive edges (i.e. p¹,2 12,1) Let p be a successor path fragment of p p =rl.
We say that P verifies an Eulerian cycle if
1. every edge in E appears in exactly two pairs in P; and
2. there exists a permutation over pairs a [N] + [N] such that each ((+1) is successor of (r( (and (0) a successor of y (N)).
We treat Eulerian cycle detection sequential task adjacency- node tokenization inputs by setting the ith embedding to d(v, P.), where P: encodes all pairs incident to node v;, i.e.,
P. {p P1.2 P2,1 = =
Now, we prove that-condiiional on the hardness of distinguishing one-cycle and two-cycle graphs- no transformer can solve the Eulerian cycle verification problem of degree-n multi-graphs without sufficient width depth.
Theorem 5.1. Under Conjecture 2.4 from Sanford et al. (002bb), the Eulerian cycle verification problem on multigraphs with self loops cannot be solved by transformers with adjacency matrix inputs if m O n² 2=² for any constant > O, unless L = ((log(n)).
Proof. Consider some transformer with depth I. and embedding dimension m that solves the Eulerian cycle verification problem for any directed multi-graph with n nodes and at most n² edges.
21

---

We use this to construct transformer I with depth (1) and embedding dimension Om + that distinguishes between an undirected cycle graph of size N and two eycles of size NN for N / The claim of the theorem follows as an immediate consequence of the 1 vs. 2 cycle conjecture (as stated in Conjecture 13 of [Sanford et al. 2024a)
We prove that a transformer with O(1) layers and embedding dimension (n) can convert an N N-node eycle graph instance @ (23, e) into multi-graph G = (V, E) with paths P such that & is single cycle if and only if P represents an Fulerian path on G. We first define the transformation and then show that can be implemented by small transformer.
Assume without loss of generality that V [N] and V [n]. Let (i, (mod ;) be a many-to-one mapping from vertices in 2J to half of the vertices in V.
For each undirected edge e = {vi, D2) E E. we add two directed edges to E: e (vi), (D2); i); and e-; = (V2), &n (n()),
For an arbitrary turnrouund edge edge e; e" e. we replace C emg- with two self edges:
e (v2) i); and e_; (11), -i).
For edge E é as above with unique neighbors e; {Du, d1} and e {bz, DzJ. we add paths p' = (eg, Cak) and p (e-i, Cbj), where a and b are chosen such that eak and eaj succeed 6; and e- respectively.
We remark few properties of the constructed graph G. which satisfies [V| and [E] = |P| n². Any two adjacent edges in 6 create two "successor relationships" between pairs of path segments in P. Then, if a cyclic subgraph of O does not contain e", the path segments in P produced by the edges in the subgraph comprise two disjoint directed cycle paths. On the contrary, if the subgraph contains e", then its path segments comprise a single cycle path.
Therefore, if @ is contains a single cycle of length N, then P verifies an Eulerian cycle in that includes all n² edges Otherwise, if 6 has two cycles of length 2N, then P represents three cyclic paths, one of length 5 and two length n² Hence, there is one-to-one correspondence between the 1 vs. 2 cycle detection problem on & and the Eulerian cycle verification problem on G and P.
We conclude by outlining the construction of transformer I that solves the cycle distinction prob- lem. This can be implemented using elementary constructions or the existing equivalence between transformers and MPC.
I takes as input a stream of edges, eN E C, in no particular order. These are expressed in the edge tokenization, which means that the ith input to the transformer is (c,,1, cr,2, i). We arbitrarily denote e = e" with its positional embedding.
In the first attention layer, I retrieves the two adjacent edges of each edge embedding.
It does so with two attention heads. The first encodes 1, query vector (which is selected to be nearly orthogonal to those of each of the other N edge embeddings), e,11 + 4x22 as a key vector, and (c..1, 2, i) the value vector. The second does the same with c,22. Ollog embedding dimension suffices for this association.
Then, the ith output of this layer is processed by an MLP that computes p and pm
The second attention layer collects all path tokens incident to node j E [r]] (i.c., every p' E P2) the jth embedding. This can be treated as single communication operation in the Massively Parallel Computation (MPC) model of Karloff et al. [2010). where N machines each send (log n) bits of information to n machines, where each machine receives at most On log n) bits. Due to Theorem 1 of Sanford et al. (2024a), this attention layer can complete the routing task with embedding dimension m =(n
Now, the jth element computes d(u;; P3) and passes the embedding as input to T.
'The vs. 2 cycle conjecture applies only to undirected graphs
22

---

If T verifies an Eulerian cycle, let I output that @ is a single-cycle graph
Therefore, the existence of a transformer I' with depth olog n) width O(N2=c) that solves the Eulerian cycle verification problem contradicts the vs. cycle conjecture. This completes the proof.
D Additional Experiments
Here, we provide additional results of the experiment described in Section 6.1 The results for the 4-Cycle and Triangle Count with 50 and 100 nodes, as well the connectivity task with 50 nodes, presented in Figures 5 6
7 g These experiments present the same trend discussed in Section 6.
where the training loss and test accuracy and loss similar, while training and inference times drastically better for shallow-wide networks.
In Figure we present the critical width chart described in Section 6.1 for the Triangle Count task.
Depth 1, Width 125
idear line
Depth 89
Dapth 4, Width 8s
Depth 45
Tesd Loos
Depth 10, Width 40
Dest Weth Dazi won--5
Desnh 10, withion
(1. 125)
[10. 40)
Width
Epoch
Epoch (c)
(a)
(b)
Figure 4: Training and inference times (a). training loss curves (b), and accuracy curves (c) for the 4-Cycle count task over graphs with 100 nodes, across transformers with approximately 100k parameters, varying width and depth. While the loss and accuracies remain consistent, shallow and wide transformers demonstrate significantly faster training and inference times.
Trening
Depth 1, Widt
Dasth Walh
Depth 2, Width 89
Dazh wich 29
Desth with
4,
Depth 8, Width 45
Teee Loss
Depth
Deslh, Width
Epoch
Epoch
(c)
Figure 5: Training and inference times (a), training loss curves (b), and accuracy (c) for the 4-Cycle count task over graphs with 100 nodes, across transformers with approximately 100k parameters, varying width and depth. While the loss and accuracies remain consistent, shallow and wide transformers demonstrate significantly faster training and inference times.
E Experimental Details
Dataset information In Section 6.1 we used three synthetic datasets, including connectivity, Triangle Count and 4-Cycle Count. The Triangle Count and 4-Cycle Count were presented Chen et al. 2020 Each of these datasets contains 5000 graphs, and the number of nodes is set according configuration, as we tested graphs with increasing numbers of nodes. The counting datasets are generated using Erdós-Rén Rényi graphs with edge probability of 0.1.
23

---

Trinig
Depth 1, Width 125
Depth 2. Width 89
Depth 4, Width 83
Test Lose
Trein
Depth 10, Width 40
Desth Witth Descn 10, iiithh
(1.1
(2,88) 89)
14. 651
18. 46)
(10. 40)
Dapli,
Epoch
Epach (c)
(a)
(b)
Figure 6: Training and inference times (a), training loss curves (b), and accuracy curves (c) for the 4-Cycle count task graphs with 50 nodes, across transformers with approximately 100k parameters, varying in width and depth. While the loss and accuracies remain consistent, shallow and wide transformers demonstrate significantly faster training and inference times.
Depth 1, Width 125
Depth 2. Width
Depth 4, Width 53
Test Loos
Depth 10, Width 40
Dezth Withh Desrh 10, miithho0
11. 1251
891
(4, 631
35)
(10, 40)
Dapiit,
Epoch
Epach (c)
(a)
(b)
Figure 7: Training and inference times (a), training loss curves (b), and accuracy curves (c) for the Triangle Count task over graphs with 50 nodes, across transformers with approximately 100k parameters, varying in width and depth. While the loss and accuracies remain consistent, shallow and wide transformers demonstrate significantly faster training and inference times.
For the connectivity dataset, to avoid a correlation between connectivity and edge probability as exists in Erdös-Rényí Rényi graphs, we generated the datasets using diverse graph distributions, each with multiple distribution parameters. The dataset consists of graphs that are either connected disconnected, generated using different random graph models to ensure diversity. The Erdōs-Rény model G(n,, p) used, where each edge included independently with probability p. and connected graphs are ensured by choosing p 2 n
In while disconnected graphs use lower p. Random Geometric Graphs (RGGs) are also employed, where nodes are placed randomly in unit space, and edges are formed the Euclidean distance below a certain threshold r; connected graphs use a sufficiently high whereas disconnected graphs are created with lower r. Additionally. Scale-Free networks generated using the Barabási-Albes Albbrrt model are included, where new nodes attach preferentially to high-degree nodes, ensuring connectivity when enough edges per node (m) are allowed, while disconnected graphs are produced by limiting interconnections between components. Lastly, the Stochastic Block Model (SBM) is used to generate community- structured graphs, where intra-community connection probabilities (Pinra) are set high for connected graphs, and comer-community probabilities (pinse) set to zero to ensure disconnected graphs. Each type of graph is sampled in equal proportions, shuffled, and split into training, validation, and test sets to maintain class balance.
In Section 6.33 we used three molecular property prediction datasets from Open Graph Benchmark (OGB) Hu al. [2020).
molhiv, the task is to predict whether a molecule inhibits HIV replication, binary classification task based on molecular graphs with atom-level features and bond-level edge features. ogbg-bbby involves predicting blood-brain barrier permeability, a crucial property for drug development, while ogbg-bace -acc focuses on predicting the ability of molecule to bind to the BACEI enzyme, associated with Alzheimer's disease. Dataset statistics are presented in 2

---

Depth 1, Width 125
Depth 2. Width
Depth 4, Width 83
Text Lose
Depth 10, Width 40
Decth Witth Destnn 10, wiith
(1. 125)
(2, 89)
(4, 651
(8,
(10, 40)
Dapii,,
Epoch
Epach (c)
(a)
(b)
Figure 8: Training and inference times (a), training loss curves (b), and accuracy curves (c) for the Triangle Count task over graphs with 100 nodes, across transformers with approximately 100k parameters, varying in width and depth. While the loss and accuracies remain consistent, shallow and wide transformers demonstrate significantly faster training and inference times.
Critical Widti
Number of Nodes
(a)
Figure 9: Critical width evaluation for the Triangle count Task. The points indicate the critical width which the model fails to fit the data.
For all experiments, we use fixed drouput rate of 0.1 and Relu activations. In Section 6.1 we tuned the learning rate in (10-1,10000 4,5 10-5), $], batch size in (32, 64). In Section 66. we tuned the learning rate in (10-3,5 5. 10-3), number of layers in {3, 5, 6, 10, 12}. hidden dimensions in {32, 64). We used batch size of size 64.
Edge List tokenization Tokenization of the graph as list of edges is done follows. Assume graph over n nodes. Each node is represented by a one-hot encoding vector b; E R concatenated with the node input features 2; E Fdd. Then, each edge is represented by concatenating its node representations. Each edge representation is fed as an independent token to the transformer. As graphs vary in size, pad each node representation with zeros match the maximal graph size in the dataset.
Adjacency Rows tokenization Tokenization of the graph adjaceney is done follows. Assume graph over n nodes and adjacency matrix A. Fach node is associated with a vector of features 3; Rdd We concatenate each of A the node's corresponding feature vector. This results in vector of size n + d for each node, As graphs vary in size, we pad each node vector with zeros match the maximal graph size the dataset. Each such vector is used an input token to the transformer
Laplacian Eigenvectors tokenization Tokenization of the graph as Laplacian eigenvectors done as follows. Assume a graph over nodes and graph Laplacian L. Each node is associated with the graph's Laplacian.
vector of features v; d We compute the eigenvector decomposition Then, each node is associated an eigenvector and an eigenvalue. We concatenate these two for each node, resulting in a vector of size n We then concatenate to each these spectral vectors node's corresponding feature vector z;, This results in vector of size d + 1 for each node.
25

---

As graphs vary in size, we pad each node vector with zeros to match the maximal graph size in the dataset. Each such vector is used as imput token the transformer
Table 2: Summary statistics of datasets used in Section 6
Dataset
# Graphs
Avg Nodes
Avg # Edges
Node Features
Classes
ogbg-molhiv 41,127
25.5
27.5
9
ogbg-molbace 1,513
34.1
36.9
9
ogbg-molbbbp 2,039
24.1
26.0
9
Small and medium size graph commonly used datasets the main paper we mentioned that many commonly used graph datasets contain graphs of relatively small size. Therefore in many real-world cases, the embedding dimension of the model is larger than the size of the graph. Here list multiple such datasets from the Open Graph Benchmark (OGB) Hu et al. [2020] as well as TUdatasets Morris et al. [2020). The datasets, including their statistics, are listed in Table 3
Table Summary of commonly used graph datasets, where the average number of nodes is relatively small
Dataset
Graphs
Avg # Nodes
Avg # Edges
ogbg-molhiv
41,127
25.5
27.5
ogbg-molbace
1,513
34.1
36.9
ogbg-molbbbp
2,039
24.1
26.0
ogbg-tox21
7,831
18.6
19.3
ogbg-toxcast
8,576
18.8
19.3
ogbg-muv
93,087
24.2
26.3
ogbg-bace
1,513
34.1
36.9
ogbg-bbbp
2,039
24.1
26.0
ogbg-clintox
1,477
26.2
27.9
ogbg-sider
1,427
33.6
35.4
ogbg-esol
1,128
13.3
13.7
ogbg-freesoll
642
8.7
8.4
ogbg-lipo
4,200
27.0
29.5
IMDB-Binary
1000
19
96
IMDB-Multi
1500
13
65
Proteins
1113
39.06
72.82
NCII
4110
29.87
32.3
Enzymes
600
32.63
62.14
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
27

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
28

---

Answer: [Yes]
Justification:
We will provide in the final version a Github project with the code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
coiioooooolcyyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipp/.cc/pullc//uuuii wwwtii/gguie///eeeeceoocc CoodeSubeiiie ssi ssionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
29

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:::///euriieee http///urrs.cccppuip/i/e httpp//ssccppp..t.ttttttttteeeea
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
30

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswpptseeee whworee.wthcee....c.. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
31

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
32

---

Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy httess/s//eerrippoccc///o/rreees for what should or should not be described.
33


Reviews:
[{"review_id": "GEHXQJ43LL", "reviewer": "Reviewer_BMCf", "summary": "The paper characterizes the expressive power of transformers with constant depth and variable width for graph-reasoning tasks. It shows that linear width is sufficient for distinguishing $n$-vertex-cycle graphs from graphs comprised of two $n/2$-cycles, and sufficient and necessary for detecting 2-cycles in directed graphs. For the special case of bounded degree graphs with maximum degree $d$, the paper shows that constant depth and sublinear $O(d \\log n)$ width is sufficient to detect 2-cycles. For tasks that require superlinear width, two results are presented: $O(n^{2-1/k})$ width and constant depth is required for subgraph counting for subgraphs of size $k$, and $O(n^2)$ width is necessary for Eulerian cycle verification. Experiments on connectivity and $n$-cycle counting for $n=\\{3,4\\}$ demonstrate that shallow and wide transformers perform comparable to narrow and deep transformers but have significantly faster training and inference time.", "questions": "* If I understand the adjacency encodings correctly, they are not permutation invariant, which might lead to two identical graphs (with differently ordered nodes and thus different adjacency matrices) having different representations. This does not matter for, e.g., subgraph detection, but might have implications for graph-level tasks. Given that the results on the ogbg datasets are quite bad (cf. https://ogb.stanford.edu/docs/leader_graphprop/#ogbg-molhiv for ogbg-molhiv), do you think not being permutation-invariant could be an issue?\n* Have you considered/tried to generalize the 1-cycle vs. 2-cycle problem (e.g., considering biconnected components of a restricted graph class such as outerplanar graphs or cactus graphs)? This might strengthen your theoretical contribution.\n* What is the \"well-accepted\" one-cycle conjecture?\n* Could you clarify whether subgraphs are induced or not?\n* Theorem 5.1: Why is this considered nearly quadratic width (and not quadratic width)?\n* Could you provide more details on the following statement: \"We used two attention heads to ensure there exists a width for which the model can fit the data for all the evaluated graph sizes\". Why do we need two attention heads to fit graphs of all sizes?\n* Experiments: Given your focus on small, and thus mostly molecular, datasets, are there specific assumptions you can leverage for molecular graphs? For instance, molecular datasets are usually planar (or even outerplanar), and thus sparse. It might also make sense to explore the performance for the the bounded-degree case for molecules. What are your thoughts on this?", "limitations": "The theoretical results rely on the (common, but strong) assumption that the multi-layer perceptron is a universal approximator as well as arbitrary positional encodings. And the results appear to be non-uniform, i.e., they only hold for graphs up to a certain fixed size.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:  Overall, the paper is well-written, easy to follow, and covers a highly relevant topic: Analyzing the tradeoff between depth and width of transformers is a useful contribution that has the potential to better understand and improve transformer-based machine learning models. Moreover, the paper specifically looks at _graph_ tasks, which have so far only been explored to a limited extent. The experiments offer a promising takeaway for practitioners: For certain tasks, shallow and wide transformers might perform equally well to (narrow and) deep transformers, while being faster to train and at inference time.\n\n**Weaknesses**: One perceived weakness is that the proposed encoding schemes render the resulting transformer architecture non-permutation-invariant. This does not matter for tasks such as subgraph or cycle detection, but might be undesirable for graph-level prediction tasks. It is unclear to me whether this is also part of the reason that the results on the ogbg datasets are far away from state-of-the-art (e.g., Graphormer [2] has >80 ROC-AUC on ogbg-molhiv [3]). It could be useful to consult [1] for the comparison of different positional encodings and their expressive power for graph transformers. Another weakness is that some of the tasks (e.g., the 1-cycle vs. 2-cycle problem and the 2-cycle detection in directed graphs) are quite specific and would strengthen the theoretical contribution if generalized. With respect to clarity and structure, there is some room for improvement. The introduction could potentially be made more concise, which might create space to include an additional experimental result from the appendix in the main text. While the paper is easy to read, sometimes it would benefit from more technical details such as more rigorous preliminaries. At times, the paper is difficult to understand without consulting related work. For instance, it would make the paper more self-contained by stating conjectures that theorems depend on, providing some introduction to massively parallel computation (MPC) schemes and properly introducing assumptions and restrictions on the graphs (undirected or directed, simple or multi, etc.) considered in the different tasks. This also applies to, e.g., the title of section 4.2, which is a bit misleading as the lower bound only holds for 2-cycles in directed graphs. \n\n[1] Black, Mitchell, et al. \"Comparing Graph Transformers via Positional Encodings.\" Forty-first International Conference on Machine Learning.\n\n[2] Ying, Chengxuan, et al. \"Do Transformers Really Perform Badly for Graph Representation?.\" Advances in Neural Information Processing Systems.\n\n[3] https://ogb.stanford.edu/docs/leader_graphprop/#ogbg-molhiv\n\nPlease find some minor remarks and typos below.\n\n- Line 87: model -> models\n- Line 119: empirical tradeoffs \"for\" spectral Laplacian-based encodings\n- Section 3.1: $m$ not introduced\n- 198: typo in \"linear width is suffices\"\n- Last sentence in Theorem 4.1 would benefit from some rephrasing\n- Lines 230-231: Consider rewriting this statement, it does not seem fully correct to me. Shouldn't you have to check $A^i$ from $i=1,...,n$ to know about connectivity?\n- Line 257: graph problem -> graph problems\n- Line 281: such that -> that\n- Line 285: subgraph -> subgraphs\n- Lines 371-371: \"this figure\" -> Please consider referring to the actual figure\n- Line 563: effect -> affect\n- Line 566: typo in \"will does\"\n- Line 567: ReLU network -> ReLU networks; and please consider specifying that $\\sigma(z)$ is ReLU/$max(0,z)$\n- Line 578: whose embedded -> grammar sounds off\n- Line 809: appears exactly two pairs -> appears in exactly two pairs?\n- Line 922: Missing period at the end of sentence.\n- Fig. 1: Inconsistent capitalization of theorems\n- Fig. 4-5 have exactly the same caption; where are the results on the connectivity experiments?\n- Inconsistent usage of 1-cycle vs. one-cycle\n\n**Justification for score**: My current score reflects some concerns and unaddressed limitations that I have summarized in **Weaknesses** and **Questions**. I am happy to raise my score if these concerns get addressed.", "was_revised": true, "final_justification": "Given the authors' rebuttal, I decided to increase my score. I still consider the fact that the positional embeddings are not permutation-invariant as a weakness, but the overall contribution is sufficient for acceptance.", "rebuttal": "We thank the reviewer for the thorough and positive review.\n\nTo answer the questions:\n\n- 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.\n\n- 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.\n\n- 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.\n\n- 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.\n\n- 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.\n\n- 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. \n\n- 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. \n\nRegarding the limitations:\n\nOur 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].\n\nRegarding 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.\n\nRegarding the weaknesses:\n\nAbout 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.\nAbout 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.\n\nThank 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."}, {"review_id": "2yY1EYe9fH", "reviewer": "Reviewer_hADS", "summary": "The paper investigates the minimal size of a transformer needed to solve algorithmic problems, focusing specifically on graph-based tasks. It analyzes the expressive power of transformers under different depth and width settings. The authors show that with linear width and constant depth, transformers can handle tasks like connectivity and cycle detection, while more complex tasks require quadratic width. The paper offers both theoretical constructions and empirical evaluations to demonstrate these trade-offs across various graph encoding schemes.", "questions": "1. How do you see your theoretical results transferring to practical graph learning tasks beyond counting substructures (e.g., property prediction on molecular graphs)?\n\n2. Have you considered adding comparisons with GNN baselines to better contextualize the empirical advantages of your transformer encodings?\n\n3. Could you clarify how robust your theoretical constructions are to architectural and optimization constraints in real transformers?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. This paper introduces a novel representational hierarchy that characterizes the relationship between depth and width in transformers for graph algorithmic tasks. The authors show that several problems—including connectivity and cycle detection—can be solved with fixed (constant) depth and linear width relative to the number of nodes.\n\n2. The author proves that more complex tasks, such as subgraph counting and Eulerian cycle verification, require quadratic width. The work establishes both upper and lower bounds on the necessary width for a variety of graph problems, providing a hierarchy of task complexity. \n\n3. The paper includes empirical results that demonstrate the practical advantages of using shallow, wide transformers in terms of training and inference time, while exploring different graph encoding schemes like adjacency rows, edge lists, and Laplacian eigenvectors.\n\nWeaknesses:\n1. The theoretical results and conclusions primarily focus on tasks like connectivity and triangle counting. While important for understanding algorithmic complexity, these tasks are relatively simple and may not generalize well to practical graph learning tasks such as graph classification, molecular property prediction, or social network analysis. This limits the direct applicability of the proposed width-depth trade-offs in real-world scenarios.\n\n2. In the experimental section evaluating graph encodings, the authors do not include comparisons with state-of-the-art GNN architectures such as GCN, GIN, or GraphSAGE. Without these baselines, it's difficult to assess the practical competitiveness of the proposed transformer-based encodings and to understand the empirical relevance of the theoretical findings for practitioners choosing between GNNs and transformers.\n\n3. The theoretical analysis assumes highly expressive MLP layers and precise control over attention weights to simulate operations such as computing matrix powers. While this is standard in theory papers, these assumptions may not hold in practice for real transformer architectures with finite width MLPs, limited numerical precision, and non-convex optimization. This gap between theory and practice limits the direct relevance of the derived width-depth bounds for deployed models.", "was_revised": true, "final_justification": "Good paper.", "rebuttal": "We thank the reviewer for the thorough and positive review. \n\nWeaknesses:\n\n1) 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.\n\n2) 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.\n\n3) 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.\n \nQuestions:\n\n1) 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. \n2) 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.\nThat’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.\n\n3) 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. \n\n[1] C. Sanford, D. Hsu, and M. Telgarsky. Transformers, parallel computation, and logarithmic depth, 2024\n\n[2] C. Sanford, D. J. Hsu, and M. Telgarsky. Representational strengths and limitations of transformers, 2024"}, {"review_id": "uyetCpFjp4", "reviewer": "Reviewer_KP4t", "summary": "This paper studies how transformer depth and width affect graph reasoning tasks. It shows that constant-depth, wide transformers can solve many tasks efficiently, with a theoretical hierarchy for width requirements. Using node-adjacency inputs, experiments confirm that shallow, wide models match deep ones in accuracy while training faster on both synthetic and real graph datasets.", "questions": "The graph inputs using adjacency rows resemble Graphormer-style encodings rather than token-based input sequences commonly used in transformers. The authors should clarify how these formats are aligned. The detailed questions are aligned with the weakness\n\nFurthermore, they should explain why there is a significant performance gap between real-world applications, prior work, and the idealized results reported on synthetic tasks.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "This paper presents a novel theoretical investigation into how transformer architectures—specifically their depth and width—affect their ability to solve graph algorithmic tasks. The key insight is that increasing the model's width can allow constant-depth transformers to solve a variety of graph problems, including tasks that previously required deeper architectures. The authors establish a theoretical hierarchy of width requirements and validate their findings with empirical evidence.\n\nThe work offers a valuable contribution toward understanding the algorithmic capabilities of transformers for graph tasks. However, several key aspects of the formulation and analysis remain unclear or underexplored, particularly in how graph representations are structured and interpreted by the transformer.\n\nWhat exactly is the output for the 2-cycle detection task? Is it a binary classification task, or does it require identifying the specific edge pair forming the 2-cycle? This should be explicitly clarified in the experimental section.\n\nThe paper adopts a node-adjacency input format (each token is a row of the adjacency matrix), deviating from the sequential token-based representations used in prior works[1]. This raises the question: If node ordering changes, does the transformer still produce consistent predictions? If the answer is no, it calls into question the validity of experiments and the stability of results under permutation.\n\nThe paper states that each node's adjacency row is embedded as an input token. Does this imply that the transformer can read and interpret individual node features? A clearer explanation of how these embeddings are processed in the early layers is needed.\n\nThe claimed generalization across different input formats (e.g., edge list vs. adjacency row) seems questionable. In edge-list inputs, the model needs to merge multiple tokens corresponding to the same node, whereas in the adjacency-row setup, each node is represented once. How does the proposed theoretical framework reconcile these structural differences?\n\nThe molecular graph classification results reported are significantly below the performance of standard GNNs such as GCN or GAT (which often exceed 80% ACC)[2]. Given the synthetic tasks achieve near-perfect accuracy, the performance gap on real data deserves deeper analysis. Is the drop due to width, depth, tokenization method, or other modeling limitations?\n\nIn Section 4, please clarify whether the “n-node” and “n-edge” \n\n[1]Sanford C, Fatemi B, Hall E, et al. Understanding transformer reasoning capabilities via graph algorithms[J]. Advances in Neural Information Processing Systems, 2024, 37: 78320-78370.\n\n[2]Hu W, Fey M, Zitnik M, et al. Open graph benchmark: Datasets for machine learning on graphs[J]. Advances in neural information processing systems, 2020, 33: 22118-22133.", "was_revised": true, "final_justification": "I still have concerns about whether converting the graphs into adjacency rows would affect the validity of the proofs. Nevertheless, I will maintain my positive score, as the main contribution is interesting.", "rebuttal": "We thank the reviewer for the thorough and positive review.\n \nWeaknesses:\n\n*“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).\n\n*“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.\n\n*“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. \n“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.\n\n*“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.\n\n\nQuestions:\n\n*“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. \n\n*“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.\n\n\n[1] C. Sanford, D. Hsu, and M. Telgarsky. Transformers, parallel computation, and logarithmic depth, 2024\n\n[2] C. Sanford, D. J. Hsu, and M. Telgarsky. Representational strengths and limitations of transformers, 2024\n\n[3] Loukas, Andreas. What graph neural networks cannot learn: depth vs width, 2019"}]

Author rebuttal:

Meta-review: This paper studies the depth–width tradeoffs of transformers on graph algorithmic tasks. The key contributions are: (1) theoretical results showing that constant-depth, linear-width transformers can solve tasks such as connectivity and cycle detection, (2) theoretical results implying that more complex problems, including subgraph counting and Eulerian cycle verification, require nearly quadratic or quadratic width, and (3) empirical evidence that shallow, wide transformers can match the performance of deeper models while offering efficiency benefits in training and inference. The reviewers agreed that the paper provides novel and intellectually interesting insights into the expressiveness of transformers, and that both the theoretical and empirical findings can add value to the community. Notably, the new analysis angle explored by this work leads to novel results and could inspire future works in graph machine learning. I thus recommed a spotlight presentation.

For the camera-ready version, I encourage the authors to (1) better clarify the implications (e.g., advantages and disadvantages) of using non-permutation-invariant encodings, particularly for real-world prediction tasks, (2) improve clarity in the description of graph tasks and encodings (e.g., adjacency rows versus edge lists) as well as their potential limitations, and (3) strengthen the empirical evaluation, for example by providing further analysis of the performance gap on real datasets.
Decision: Accept (spotlight)