Graph Transformers Dream of Electric Flow
Authors: Xiang Cheng
Lawrence Carin
Suvrit Sra
Venue: ICLR 2025 Poster (2025)
Keywords: Transformer
Graph Neural Network
Primary area: learning on graphs and other geometries & topologies
TL;DR: we provide simple constructions showing how linear Transformers can learn to solve a number of canonical graph problems, with practical implications for learning positional encodings.

Abstract: We show theoretically and empirically that the linear Transformer, when applied to graph data, can implement algorithms that solve canonical problems such as electric flow and eigenvector decomposition. The Transformer has access to information on the input graph only via the graph's incidence matrix. We present explicit weight configurations for implementing each algorithm, and we bound the constructed Transformers' errors by the errors of the underlying algorithms. Our theoretical findings are corroborated by experiments on synthetic data. Additionally, on a real-world molecular regression task, we observe that the linear Transformer is capable of learning a more effective positional encoding than the default one based on Laplacian eigenvectors. Our work is an initial step towards elucidating the inner-workings of the Transformer for graph data. Code is available at https://github.com/chengxiang/LinearGraphTransformer

Published as a conference paper at ICLR 2025
GRAPH TRANSFORMERS DREAM OF ELECTRIC FLOW
Xiang Cheng', Lawrence Carin', Suvrit Sra?
'Department of Electrical and Computer Engineering, Duke University, USA Schooo of Computation, Information and Technology. Technical University of Munich, Germany (xiang. cheng, Icarin) @duke.
S. S.sa@tuum. de
ABSTRACT
We show theoretically and empirically that the linear Transformer, when applied graph data, implement algorithms that solve canonical problems such electric flow and eigenvector decomposition. The Transformer has access to in- formation on the input graph only via the graph's is incidence matrix. We present explicit weight configurations for implementing each algorithm, and we bound the constructed Transformers' errors by the errors of the underlying algorithms. Our theoretical findings are corroborated by experiments on synthetic data. Addition- ally, on a real-world molecular regression task, we observe that the linear Trans- former is capable of learning more effective positional encoding than the default one based on Laplacian cigenvectors. Our work is an initial step towards eluci- dating the inner-workings of the Transformer for graph data. Code is available at ormer
https: / g thub. com/ chengx ang/ Li nea reaeearrrrrrrrraeaa
INTRODUCTION
The Transformer architecture (Vaswani et al., 2017) has seen great success in the design of graph neural networks (GNNs) (Dwivedi Bresson, 2020; Ying et al., 2021; Kim et al., 2022; Müller et al., 2023), and it has demonstrated impressive performance in many applications ranging from prediction of chemical properties analyzing social networks (Yun et al., 2019; Dwivedi et al., 2023; Rong et al., 2020). In contrast to this empirical success, the underlying reasons for why Transformers adapt well to graph problems are less understood. Several works study the expressivity of iitention-based architectures (Kreuzer al., 2021; Kim et al., 2021; 2022; Ma et al., 2023), but such analyses often rely on the ability of neural networks to approximate arbitrary functions, and may require prohibitive number of parameters.
This paper is motivated by the need to understand, at a mechanistic level, how the Transformer processes graph-structured data. Specifically, we study the ability of a linear Transformer solve certain classes of graph problems. The linear Transformer is similar to the standard Transformer. but softmax-ban -base activation is replaced with linear attention, and MLP layers are replaced by linear layers. Notably, the linear Transformer contains no priori knowledge of the graph structure; all information about the graph is provided via an incidence matrix B. For unweighted graphs, the columns of B are just {-1, 0, v-vludd indicator vectors that encode whether an edge touches vertex; no other explicit positional or structural encodings are provided.
Even in this minimal setup, we are able to design simple configurations of the weight matrices of a Transformer that enable it to solve fundamental problems such as electric flow and Laplacian eigenvector decomposition. Furthermore, we provide explicit error bounds that scale well with the number of Transformer layers. Several of our constructions rely crucially on the structure of the linear attention module, and may help shed light the success of attention-based GNNs. We hope that our analysis paves the way to a better understanding of the learning landscape of graph Transformers, such concrete bounds on their generalization and optimization errors.
Besides enhancing our understanding of Transformers, our results are also useful for the practical design of graph Transformers. In Sections 3 and 4, show that the same linear Transformer architecture capable learning a number popular positional encodings (PE). In Section we provide experimental evidence that the linear Transformer learn better PEs than hard-coded PRs.

---

Published as a conference paper at ICLR 2025
Lemma
Task
Transformer Implements:
# layers for & error log(1/e)
Electric Flow (CT)
Gradient Descent
Flectric Flow (Ct)
Multiplicative Expansion
log (1/(1/e) log(1/E)
2
Resistive Embedding
)
Power Series
3
Heat Kernel (e (L)
Power Series
log(1/e) + 8Amax
5
Heat Kernel (e (e=
Multiplicative Expansion
log(1/e) + log( (max)
6 &&7 7
k-Eigenvector Decomp. of C
Subspace Iteration
(subspace-iteration steps)/k
Table 1: Summary of Error Bounds proved for various Transformer constructions. C is the graph Laplacian; L denotes its pseudoinverse.
1.1 SUMMARY OF CONTRIBUTIONS
Below, we summarize the main contributions of our paper.
1. We provide explicit weight configurations for which the Transformer implements efficient algo- rithms for several fundamental graph problems. These problems serve as important primitives in various graph learning algorithms, and have also been useful as PEs in Mlate-ofthhe-e GNNs.
(a) Lemma constructs a Transformer that solves electric flows by implementing steps of gradi- ent descent to minimize flow energy; consequently, it can also invert the graph Laplacian.
(b) Lemmas 2 and 3 construct Transformers that compute low-dimensional resistive embeddings and heat kernels. Both constructions are based on implementing suitable power series.
(c) By implementing multiplicatiiv polynomial expansion, Lemma 4 provides construction for electric flow with exponentially higher accuracy than Lemma 1. Similarly, Lemma pro- vides construction that computes the heat kernel using much fewer layers than Lemma 3. (d) Lemma 6, we show that the Transformer can implement subspace iteration for finding the top-k (or bottom-k) eigenvectors of the graph Laplacian. Central to this analysis is the ability of self-attention compute QR decomposition of the feature vectors.
We derive explicit error bounds for the Transformer based on the convergence rates of the underlying algorithm implemented by the Transformer. We summarize these results in Table 1.
2. In Section 5, we propose more efficient version of the linear Transformer with much fewer parameters. We show that this more efficient linear Transformer can nonetheless implement all the above-mentioned constructions. Further, show Lemma 10 that the pframeter-efffcieent linear Transformer has desirable invariance and cquivariance properties.
We test the empirical performance of our theory on synthetic random graphs. In Section 3.5, we verify that Transformers with few layers can achieve high accuracy in computing electric flows, resistive embeddings, as well as heat kernels. In Section 4.1, we verify that the Transformer can accurately compute top-k and bottom-k eigenevectors of the graph Laplacian.
In Section 6, we demonstrate the advantage of using the linear Transformer for Laplacian eigenvector PE on a molecular regression benchmark using the QM9 and ZINC datasets (Ruddigkeit et al., 2012; Ramakrishnan al., 2014; Irwin al., 2012). After replacing the Laplacian eigenvector- based PE with the linear Transformer, and training on the regression loss, we verify that the linear Transformer automatically learns a good PE for the downstream regression task that can outperform the original Laplacian eigenvector PE by wide margin.
replacement
1.2 RELATED WORK
Numerous authors have proposed different ways of adapting Transformers to graphs (Dwivedi & Bresson, 2020; Ying et al., 2021; Rampášek al., 2022; Müller et al., 2023). A particularly promis- ing approach is to use suitable positional encoding to incorporate structural information in the input, examples include Laplacian eigenvectors (Dwivedi & Bresson, 2020; Kreuzer et al., 2021), heat kernel (Choromanski et al., 2022), resistance distance and commute time (Ma et al., 2023; Vel- ingker et al., 2024; Zhang et al., 2023) and shortest path distance (Ying et al., 2021). Lim et al. (2022) designed neural network transform eigenvectors into an encoding that has certain invari- ance properties. Black et al. (2024) compared the expressivity of different PE schemes. (Srinivasan & Ribeiro, 2020) studied the relationship between PF and structural graph representations.
2

---

Published as a conference paper at ICLR 2025
Kim et al. (2021) explore the possibility of using pure Transformers for graph learning. They provide both nodes and edges as input tokens, with a simple encoding scheme. They also prove that such a Transformer is expressive
second-order invariant graph network.
A number of works have explored the use of learned PEs (Mialon et al., 2021; Eliasof et al., 2023;
Park et al., 2022; Ma et al., 2023; Kreuzer et al., 2021; Dwivedi et al., 2021). In particular Ma et al. (2023) is based on relative random walk probabilities (RRWP), and Kreuzer et al. (2021)'s learn
approach is based on learned eigenfunctions. In comparison, using a linearTrransfrmert PEs has two advantages: 1. self attention can implement operations such as orthogonalization, necessary for learning multiple eigenvectors (Lemma 6). Second, self-attention enables highly- efficient algorithms based on multiplicative polynomial expansions (Lemma 4). These enable linear Transformers to learn good PEs given only the incidence matrix as input.
Finally, we note several relevant papers that are unrelated to graph neural networks. A recent body of work proves the ability of Transformers to implement learning algorithms, to explain the in-context learning phenomenon (Schlag et al., 2021; Von Oswald et al., 2023). Surprisingly, our construction for Lemma bears several remarkable parallels to the gradient descent construction by Von Oswald et al. (2023). We conjecture that the proof of Lemma 4 may be applicable for understanding the GD++ algorithm in the same paper. In another direction, Charton (2021) show experimentally that Transformers can compute linear algebra operations such as eigenvector decomposition. Their work requires a relatively complicated matrix encoding and a large number of parameters.
PRELIMINARIES AND NOTATION
2.1 GRAPHS
We use G = (V,E) to denote a graph with vertex set V and edge set E; let n == | and = |8). We often identify the vertex i, with its index for i = 1...n, and the edge ej with j for j 1...d. In general, G has weighted edges, defined by r(-): E + Rt. We let ry == r(e)). A central object of interest is the incidence matrix B E RRndd defined as follows: to each edge ej- (u ~ v) E E assign an arbitrary orientation, e.g. ej
(u + v). The incidence matrix B is given by
-I/55, +1/15
if exists E V such that Ej (t: v) if exists E V such that Ej = (v + us) otherwise.
Bij =
(1)
We define the graph Laplacian as := BBT E R2 We use Amax to denote the maximum eigenvalue of L. Note that L always has 0 as its smallest eigenvalee,, with corresponding eigenvector vn I, the all-ones vector. This fact can be verified by noticing that each column of B sums to 0. For connected graph (as we will assume the case throughout the paper), the second-smallest eigenvalue is always non-zero, and we will denote it as Amin Finally, we define Inx := Inxn - IIT Inxx is the projection onto span C), and functions as the identity matrix when working within span(C).
2.2 LINEAR TRANSFORMER
We will use Zo E hR to denote the input to the Transformer. Zg encodes a graph 9, and each column of Zo encodes single vertex in h dimensions. Let WQ, W WW e gh denote the key, query and value parameter matrices. We define linear attention Attn as
Atlawv wwe, w (Z) =- V zz W kx2.
(2) Unlike standard attention, (2) does not contain softmax activation. We construct an L-layer Trans- former by stacking L layers of the attention module (augmented with linear operation on the skip connection). To be precise, let Zi denote the output of the (1 1)th layer of the Transformer. Then
Z == 21 + Attuwy ,w (Z,) + WzZ,
(3)
where WY. WP, W.K are the value, query and key weight matrices of the linear attention mod- ule at layer I, and W E gaxh is the weight matrix of the linear operation. Henceforth, we let W.R = (W/R)=o... denote
WV := ( h=o..., Wº := (W,)) J W.K := collections the parameters across all layers of an L-layer Transformer. Finally, we will often need to refer to specific rows of Z,. We will use [Zd)... denote rows to j of 7,-
3

---

Published as a conference paper at ICLR 2025
3 TRANSFORMERS AS POWERFUL SOLVERS FOR LAPLACIAN PROBLEMS
In this section, we discuss the capacity of the linear Transformer to solve certain classes of canon- ical graph problems. We begin with the problem of Electric Flow in Section 3.2, where the con- structed Transformer can be interpreted as implementing steps gradient descent with respect to the energy of the induced flow. Subsequently, in Section 3.3, we provide constructions for comput- ing the resistive embedding, as well as the heat kernel, based on implementing a truncated power series. Finally, in Section 3.4, provide faster alternative constructions for solving electric flow and computing heat kernels, based on implementing a multiplicative polynomial expansion. In each case, bound the error of the Transformer by the convergence rate of the underlying algorithms.
3.1 ADDITIONAL SETUP
We introduce some additional setup that is common to many lemmas in this section. We will gen- erally consider an L-layer Transformer, defined in (3), for some arbitrary L E Z+. As in (3), we use Z4 to denote the input to layer 1. The input Zo will encode information about graph g. along with a number of demand vectors 1 ... 1/x E F" We use V denote the n matrix whose ith column is 4h,. Unless otherwise stated, Z1 E (d+22)xx where n is the number of nodes, d is the number of edges, and & the number of demands/queries. Z == [B, V 0p
On parameter size: In straightforward implementation, the above Transformer has feature dimen- sion (d+ 2k). The size of W W WV W is O(h)) = Odd + k²2), which is prohibitively large as d can itself be O(n²). The size of parameter matrices can be significantly reduced to O
by imposing certain constraints on the parameter matrices; we present this reduction (7) Sec- tion 5. For simplicity of exposition, lemmas in this section will use the naive implementation in (3).
We verify later that all the constructions presented in this section can also be realized in (7).
3.2 SOLVING ELECTRIC FLOW WITH GRADIENT DESCENT
Assume we are given graph g = EV, along with non-negative vector of resistances r E Rd. Let R be the x d diagonal matrix with its diagonal. A flow is represented by f E Rd. where fy denotes the (directed) flow on edge ey. The energy of an electric flow given by Σÿ= Let di In denote a vector of demands. Throughout this paper, we will assume that the demand vectors satisfy flow conservation, i.e., (v, I) The v-electric flow is the unique minimizer of the following (primal) flow- flow-optimization problem (by convex duality, this is equivalent to a dual problem):
(primal)
min FER
Σn Ersf
subject the constraint
BR vb.
(4)
(dual)
min R
Φ LØ 26 To.
(5)
The argument is standard; for completeness, we provide proof of equivalence between (4) and (5)
in (8) in Appendix 10.1. It follows that the optimizer ø' of (5) has closed-form solution o² = Lh In Lemma below, we show simple construction that enables the Transformer in (3) to compute in parallel, the optimal potential assignments for a set of l demands { where v); E RR.
Motivation:
Effective Resistance Metric
An important practical motivation for solving the electric flow (or equivalently computing Ct) is to obtain the Effective Resistance matrix R E _R=x. GNNs that use positional encodings derived from R have demonstrated state-of-the-art performance on numerous tasks, and can be shown to have good theoretical expressivity (Zhang et al., 2023; Velingker et al., 2024; Black et al., 2024).
Formally. R is defined as Rij == (u+ -T Lt, uz). where u; denotes the vector that has in the 2th coordinate, and Os everywhere else. Intuitively, R.y is the potential drop required to send l-unit of electric flow from node to node j. Let e E _R" denote the vector of diagonals of Li (i.e. :=:= La). Then R = Ie + TIT 2ct; thus computing Li essentially also computes R.
Lemma (Transformer solves Electric Flow by implementing Gradient Descent) Consider
the setup in Section 3.1. Assume that (1hx, i) 0 for each i = 1..k. For any 8 > 0 and for any
4

---

Published as a conference paper at ICLR 2025
L-layer Transformer. there exists a choice of weights W WO, W WR, such that each layer of the Transformer (3) implements a step of gradient descent with respect to the dual electric flow objective in (5). with stepsize 8. Consequently, the following holds for all i 1...k and for any graph Laplacian with maximum eigenvalue Amaa I 1/6 and minimum nontrivial eigenvalue Amin:
IZlld L'vb/1 $ exp( exp(-8LAmin 1/slll2
VAmiu
Discussion. In the special case when k n and V == Inxa LTT,, F1la+x+1...dt s Lt. An e-approximate solution requires L = O (log(1/E)) layers: this is exactly the convergence rate of gradient descent on a Lipschitz smooth and strongly convex function. We defer details of the proof of Lemma I to Appendix 10.1, and we provide the explicit choice of weight matrices in (10). On a high level, we show that a single attention layer can implement exactly a single gradiens [Zil oV F., ([Z1)444++). The log(1/s) rate then follows immediately from the convergence rate of gradient descent, combined with smoothness and (restricted) strong convex of Fet. In Lemma 4 below, we show alternate construction that reduces this to Olog log(1/))).
descent step wrt the dual objective Fe (5), i.c. [Z4+1leta=
We highlight that the constructed weight matrices are very sparse; each of WV W W W contains single identity matrix in a sub-block. This sparse structure makes it possible to drastically reduce the number of parameters needed, which we exploit in Section design more parameter efficient Transformer. We provide experimental validation of Lemma I in Section 3.5.
3.3 IMPLEMENTING TRUNCATED POWER SERIES
In this section, we present two more constructions: one for computing V (Lemma 2), and one for computing the heat kernel e (Lemma 3). Both quantities have been successfully used for positional encoding in various GNNs. The constructions proposed in these two lemmas are also similar, and involve implementing the power series of the respective targets.
3.3.1 COMPUTING THE PRINCIPAL SQUARE RoOT VC
Motivation Resistive Embedding
The following fact relates the effective resistance matrix R. to any "square root" of L):
Fact 1 Let M denote any matrix that satisfies MM Lt. Lel R Rn denote the matrix of effective resistances (see Section 3.2). Then Rij = |M;;-MMMll
- -Mill where M, is the tth row of M.
One can verify the above by noticing that JIM, M,I1 MIM.M + MJ.MM Mj 22M,M, [4], + [4], 2Lij. In some settings, it is more natural to use the rows of M to embed node position, instead of directly using R: By assigning an embedding vector wi = =M; to vertex i, the Fuclidean distance between W, and w equals the resistance distance. The matrix M is under-
determined, and for any m > n, there are infinitely many choices of M that satisfy MMM = Lt. Fact I applies to any such M. Velingker al. (2024) uses the rows of M L B for resistive embedding. Under this choice, M, has dimension = (8), which can be quite large. To deal with this, they additionally performs
mnmension-reductionn step using Johnson Lidenstrauss.
Among all valid choices of M, there is a unique choice that is symmetric and minimizes |M]] namely, US- where T = L is the eigenvector decomposition of L. We reserve Vct to denote this matrix; / Cf is called the principal square root of Lt. In practice, VLi might be preferable to, say, Li B because has an embedding dimension of n, as opposed to the possibly much larger d. We present Lemma 2 a Transformer construction for computing VCF.
Lemma 2 (Principal Square Root Vi) Consider the setup in Section 3.1. Assume that th... E
Ra satisfy (xby, 7) O. For any L-layer Transformer (3), there exists configuration of weights WV WQ, W R such that the following holds: For any graph with maximum Laplacian eigen- value less than Amax and minimum non-trivial Laplacian eigenvalue greater than Amins and for all i L..k:
c Liduniua Aanax
| VCtull
1|1all2
Amin v L/ Am/ax
5

---

Published as a conference paper at ICLR 2025
Discussion. We defer a proof of Lemma to Appendix 10.2. The high-level idea is that each layer of the Transformer implements
additional term of the power series expansion of vLJ. Under VLT. An E approximation requires log(1/E) layers. We consider the more general setup involving arbitrary v/ss as they are useful for projecting the resistive emhedding onto lower-dimensional space; this is relevant when v s are trainable parameters (see e.g., the setup Appendix 14.3). We empirically validate Lemma
the choice k n and V Inxn (1/n)II", [Zzla+8+1...d
2 in Section 3.5.
3.3.2 COMPUTING THE HEAT KERNEL: (xp(-
Finally, we present a result on learning heat kernels. The heat kernel has connections to random walks and diffusion maps Coifman & Lafon (2006). It plays central role in semi- supi-super leamn- ing on graphs (Xu et al., 2020); it also used for positional encoding (Choromanski et al., 2022). Note that sometimes, the heat kernel excludes the nullspace of L and is defined as e e- 11 /n.
Lemma (Heat Kernel =E) Consider the setup in Section 3.1. Assume that 1/.. R satisfy (W:, 1) O. Let s 0 be an arbitrary temperature parameter. There exists configuration of weights for the L-layer Transformer (3) such that the following holds: for any input graph whose Laplacian satisfies 8sAmax S L, and for all 1...k.
121,,---
5 2- L+88Amax
Discussion, We defer the proof of Lemma Appendix 10.3. To obtain approximation error, we need number of layers L 2 (log(1/s) sAmax). As with the preceding lemmas, the flexibility of choosing any number of t 's enables the Transformer learn a low-dimensional projection of the s sAmax is fundamental, stemming from the fact that the truncation
heat kernel. The dependence error of the power series of e -& begins to shrink only after (s) the first terms. In Lemma in the next section, weaken this dependence from s'maa to log( smmax) We empirically validate Lemma 3 in Section 3.5.
3.4 IMPLEMENTING MULTIPLICATIVE POLYNOMIAL EXPANSION
We present two alternative Transformer constructions that can achieve vastly higher accuracy than the ones in preceding sections: Lemma computes an é-accurate electric flow in exponentially fewer layers than Lemma Lemma approximates the heat kernel with higher accuracy than Lemma when the number of layers small. The key idea in both Lemmas 4 and 5 is to use the Transformer implement a multiplicative polynomial; this in turn makes key use of the self-attention module.
The setup for Lemmas 4 and 5 differs in two ways from that presented in Section 3.1. First, the input to layer 1, Zí, are now in 3 instead (d4+2))xn When the graph 9 is sparse and the number of demands/queries & is small, the constructions in Lemma and may use considerably less memory. This difference is fundamental, due to the storage required for raising matrix powers. Second, the input is also different;; in particular, information about the graph is provided via L as part of the input Zo. as opposed to via the incidence matrix B as done in Section 3.1. This difference not fundamental: one can compute C = Bº from B in single attention layer; in the spirit of brevity, we omit this step. We begin with the faster construction for electric flow:
Lemma Let 8 > O. Let ZJJ = [(ixxn - -L), 8L), Inxns 8laxn]. Then there exist a choice of W Wº, W.K R for L-layer Transformer (3) such that for any graph with Laplacian with smallest non-trivial eigenvalue Aunin and largest eigenvalue Amax I 1/8,
|||Z)|an41..s =t1l2
exp (-824 Amin)
Amin
Discussion. Lemma 4 shows that the Transformer can compute e-approximation to Li (which is sufficient but not necessary for solving arbitrary electric flow demands) using log log(1/e) layers. This is much fewer than the log(1/E) layers required in Lemma 1. The key idea in the proof is to implement a multiplicative polynomial expansion for L We defer the proof to Appendix 10.4.
Next, show the alternate construction for computing the heat kernel:

---

Published as a conference paper at ICLR 2025
Lemma 5 (Fast Heat Kernel) Let s > O. Let L be the number of Transformer layers. Let Zo (Inxn - 3 sL). Then there exist a choice of WV, WW2, ,WK,, K W such that for any graph whose
Laplacian C satisfies smmux S 3²
1z
33-433113 L+1 2X max
Discussion. Lemma 5 shows that the Transformer can compute an e-approximation e using ([log(1/E) + log((>masz) layers. The dependence is the same as Lemma 3, but the log(s>max) is an improvement. When the number of layers is small, Lemma 5 gives a significantly more accurate approximation. The proof is based on the well- approximation e" = (1 + (1+x/L)² z/ proof details for Lemma to Appendix 10.4.
We defer
3.5 EXPERIMENTS
In Figure we experimentally verify that the Transformer is capable of learning to solve the three objectives presented in Lemmas 1, 2 and 3. The setup is as described in Section 3.1, with the Transformer described in (3) with & n, but with the following important difference: the
output of each layer is additionally normalized as follows: [Zt]1... + [Z))..../lll /Il Zt)..... llr,
[2)......4422 [Z]], 1.. / [1) m0222l pl where ||l| the Frobenius norm. Without 22....
this normalization, training the Transformer becomes very difficult beyond 5 layers.
We consider two kinds of random graphs: fully-connected graphs (n = 10, 45) and Circular Skip Links (CSL) graphs (n 10, d 20). Edge resistances are randomly sampled. We provide details on the sampling distributions in Appendix 13. For each input graph G, we sample n demands p1...0h E R" independently from the unit sphere. Let v = [v.]... The input to the Transformer is [ VT, Onxn]. consistent with the setup described in Section 3.1. The training/test loss
27
is given by lossy
E
where U E {cl. 0.5L We
i=
M
learn the correct solutions only up to scaling, because we need to normalize Zi per-layer. The expectation is over randomness in sampling L and V. We plot the log of the respective losses against number of layers after training has converged. As can be seen, in each plot, and for both types of architectures, the loss appears to decrease exponentially with the number of layers.
CSL linerr
CSLiinerr
CSL Hinar
TCinser
rC-lneer
TE-áneer
Ingitoos)
logiloos))
logiLoss)
-
Layer
Layer
Layer
((a) losser (electric)
1(b) loss ver (resistive)
I(c) (08. (heat)
Figure 1: lossy against number of layers at convergence for U E {(t,, Sot.VDi,e -0.5)
4 TRANSFORMERS CAN IMPLEMENT SUBSPACE ITERATION TO COMPUTE EIGENVECTORS
We present a Transformer construction for computing the eigenvectors of the graph Laplacian L. The Laplacian eigenvectors are commonly used for positional encoding (see Section 1.2). In partic- ular, the eigenvector for the smallest non-trivial eigenvalue has been applied with great success in graph segmentation (Shi & Malik, 1997) and clustering (Bühler & Hein, 2009). Our construction is based on the subspace iteration algorithm (Algorithm 1), aka block power method see (Bentbib & Kanber, 2015). The output & of Algorithm I converges to the top-k cigenvectors of L. In Corollary 7, we present a modified construction that instead computes the bottom-k & eigenvectors of L. For the purposes of this section, we consider a variant of the Transformer defined in (3).
WY.W 2 Z, + Atto Ww w. (Zi) + R Z₁
Z normalize (
(6)
7

---

Published as a conference paper at ICLR 2025
ALGORITHM 1 Subspace lteration
go E R while not converged do
x has full column rank.
Φ Lo;
P--1 QR(
QR( returns the matrix in the QR decomposition of Φb
end while
where normalize(2) Z) applies row-wise normalization: [normalize(Z)] [2],/||(z,, ll2 for d + 1...d k. We use B, Raxd and $ B to denote refer to specific columns of Z defined as -,== =: [B," b The notation is chosen 4 in Zi in (6) corresponds to $ in Algorithm 1. We initialize Bn = B and let Φn be some arbitrary matrix with full column rank. 4 becomes orthogonal after the first QR step of Algorithm 1.
Lemma 6 (Subspace Iteration for Finding Top l Eigenvectors) Consider the Transformer de- fined in (6). There exists a choice of WV WQ, W such that + layers of the Transformer implements iteration of Algorithm 1. Consequently, the output D of L-layer Transformer approximates the top-k eigenvectors of L to the same accuracy as L/(k + +1) steps of Algorithm 1.
Discussion. We bound the Transformer's error by the error of Algorithm 1. but do not provide an explicit convergence rate. This omission is because the convergence rate of Algorithm 1 itself is difficult to characterize, and has complicated dependence on pairwise spectral gaps of o The high-level proof idea is to use self-attention to orthogonalize the columns of Φ (Lemma 8. We defer the proof of Lemma to Appendix 11. We experimentally validate Lemma 6 in Section 4.1.
The construction in Lemma 6 explicitly requires k layers to perform a QR decomposition of & plus layer to multiply by L. The layer usage can be much more efficient in practice: First, multiple L-multiplications can take place before single QR-factorizatio performing QR decomposition can be implemented in a single layer with i parallel heads.
step. Second, the & layers for
In graph applications, one is often interested in the bottom-k eigenvectors of C. The following corol- lary shows that a minor modification of Lemma will instead compute the bottom & eigenvectors.
Corollary (Subspace Iteration for Finding Bottom k Eigenvectors) Consider the same setup as Lemma 6. Let μ > 0 be some constant. There exists construction for L-layer Transformer (similar to Lemma 6), which implements Algorithm I with replaced by pl - L. and & approxi- mates the bottom k eigenvectors of C if >max(C) S p.
We provide short proof in Appendix 11. The key idea is that minor modification of the construc- tion in Lemma 6 will instead compute the bottom & eigenvectors. Alternative to the construction in Corollary 7, one also first compute L (via Lemma 4), followed by subspace iteration for Lt.
4.1 EXPERIMENTS FOR LEMMA
We verify Lemma 6 and Corollary 7 experimentally by evaluating the ability of the Transformer (3) to learn top-k and bottom-k eigenvectors. As in Section 3.5, we consider two kinds of random graphs with has a randomly sampled resistance; see Appendix 13 for details. For a graph g with Laplacian L, let X S )2 S ...Aio denote its eigenvalues. Let vi,-.., Vio denote its eigenvectors. A₁ is always and 01 is always i/Vn.
10 nodes: fully connected (d 45 edges) and CSL (d 20 edges); each edge is
The Transformer architecture is as defined in Section 6, with & = We increase the dimension of i to (2n) x n, and thus the dimension Z, to (d - n + n) x n. We read out the last n rows of Zr. as output. The purpose of increasing the dimension is to make the architecture identical to the one used in the experiments in Section 3.5; the construction in Lemmas and Corollary 7 extend to this setting by setting appropriate parameters to O. In addition, layer by its Frohenius norm, i.e., [ &- / a ( r (the proof of Lemma 6 still holds as subspace iteration is saaling-invariane
also normalize [Zi] each
The input to the Transformer is ZØ = =[B Lo). and we make Pn E 2 a trainable parameter along with WV WQ, W R We define loss; := E. E[min {1l [llØr,; 1all2. I + v: v= where ér, is the tth row of o2 and expectation is taken with
8

---

Published as a conference paper at ICLR 2025
respect to randomness in sampling the graph; the min is required because eigenvectors are invariant to sign-flips. We train and evaluate the Transformer on two kinds of losses: loss Ei=1 loss;
and loss 10 == To E loss,. We plot the results in Figure 2, and summarize our findings below:
1. 2(a) and 2(d): Both l0ss and I appear to decrease exponentially with the number of Transformer layers, for both FC and CSL graphs. This is consistent with Lemma 6 and Corollary 7.
2. In Figures 2(e) and 2(f), when the Transformer is trained on lossi-lu, larger eigenvectors are learned more accurately, with the exception of lossg. This is mostly consistent with our con- struction in Lemma 6, where the larger eigenvectors are computed more quickly.
In contrast, in Figures 2(b) and 2(c), when the Transformer is trained on lossi-5, the smaller eigenvectors are learned more accurately. This consistent with our construction in Corollary 7, where the smaller eigenvectors of L are also the larger eigenvectors of al L, and are thus computed more quickly. One expects to observe the same ordering if the Transformer is instead computing L first, followed by subspace iteration.
We omit loss| from Figures 2(b), 2(c), 2(e), 2(l) because ea a constant so loss goes 0 extremely fast, making it hard to see the other lines.
1.-
fully connected
3.5
0.0-
log(Loss)
1.-
logllsss)
leglooss
-1.0-
03-
-3.0
1.5
1.0
2.2-
1.5
-33
-3.0
# Layers
# Layer
# Layer
2(a) Joss 5
2(b) [ FC
2(c) [loss:] (=2..5 CSL
fully connected
3.--
0.0-
7.00-
-3.3
-03-
2.35-
log(loss)
1.04
1.50-
-15
-35
125-
-13-
235-
10
-3.0
-35
050-
# Layers
Layer
LLaer
2(d) loss
2(e)
[loss:] 10 FC
2(f) (loss:)
) 10 CSL
Figure 2: loo(s) ) vs. number of layers. Top row: various losses for the Transformer trained on loss Bottom row: various losses for the Transformer trained on l0ss
PARAMETER-EFFICIEN IMPLEMENTATION
As explained in Section 1. the sizes of the Wºº, W WV, W matrices can scale with O(n²) in the worst case, where is the number of nodes. This makes the memory requirement prohibitive. To alleviate this, we present below in (7) a more efficient Transformer implementation than the one defined in (3). The representation in (7) is strictly more constrained than (3), but it is still expressive enough to implement all the previous constructions. For each layer I, let ax af af af be scalar weight parameters, and let W. W.O. W.K. W. E
R 2k Let B,, dy evolve as
B (1 + a B + +ay BJ (ffa K B,BT + +DW T W
(7)
T (1 [[+W W. R कT V. (T at
(afaf
+ W.W. wKK...7)
with initialization Bo := B, and D Oux]]. We verify that (7) matches (3), with Z [BT, Φ/]]: the difference is that certain blocks of WY, W W.K. W.R constrained to be zero or

---

Published as a conference paper at ICLR 2025
some scaling of identity. Nonetheless, verify that the constructions in Lemmas 1, 2, and 6 can all be realized within the constrained dynamics (7). We prove this in Lemma 9 in Appendix 12. In Figure 15, show that the efficient implementation (7) performs similarly (and in many cases better than) the standard implementation (3) on all the synthetic experiments.
Besides the reduced parameter size, we highlight two additional advantages of (7):
1. Let TF. (B, @) (resp TF, (B, D)) be defined as the value of B, (resp 4,7) when initialized at Bo B and Do = under the dynamics (7). Let U gaxd be some permutation matrix over edge indices. Then
(a) TF is equivariant to edge permutation, i.e. (BU,
U TF.
(b) TF| is invariant to edge permutation, i.e. TF. (BU, ②) TF? (B,
We provide a short proof of this Lemma 10 in Appendix 12.
B₁ is sparse, then BJ Bj can efficiently computed using sparse matrix multiply. This the case for all of our constructions for all layers I.
6 LEARNING POSITIONAL ENCODING FOR MOLECULAR REGRESSION
In Sections 3.5 and 4.1, based Lt, VC, e- and EVD(L), when the training loss is explicitly the recovery loss for that embedding. An natural question is then: Can a GNN perform as well on downstream task if we replace its PE by a linear Transformer, and train the GNN together with the linear Transformer? There are two potential benefits to this approach: First, the Transformer can learn a PE that is better-suited to the task than hard-coded PEs, and thus achieve higher accuracy. Second, the Transformer with a few layers/dimensions may learn to compute only the most relevant features, and achieve comparable accuracy to the hard-coded PE using less computation.
that the Transformer is capable of learning variety of embeddings
To test this, we evaluate the performance of our proposed linear Transformer on molecular regres- sion task on two real-world datasets: QM9 (Ruddigkeit al., 2012; Ramakrishnan et al., 2014) and ZINC (Irwin et al., 2012). The regression target is constrained solubility (Dwivedi et al., 2023). Our experiments are based on the Graph Transformer (GT) implementation from Dwivedi & Bresson (2020). In Table 2, we compare three loss values: GT without PE, GT with Laplacian Eigenvector as PE (LapPE), and GT with Linear Transformer output as PE. We use LapPE as baseline because it was the PE used in Dwivedi & Bresson (2020). We present details of the datasets in Appendix 14.1. The linear Transformer architecture is a modified version of (7), detailed in Appendix 14.2. Other experiment details, including precise model definitions, can be found in Appendix 14.3.
Model
# Parameters
Loss
ZINC
Graph Transformer
800771 891
0.286 + 0.0078
Graph Transformer + LapPE
800771
0.201 + 0.0034
Graph Transformer Linear Transformer
800771 + 488
0.138 = 0.012
Graph Transformer
799747 - 512
0.419 + 0.0047
QM9
Graph Transformer LapPE
799747
0.227 + 0.0094
Graph Transformer + Linear Transformer
799747 + 240
0.221 + 0.0060
Table Regression Loss for ZINC and QM9 for different choices of PE.
The difference between GT and GT + LapPE is substantial for both QM9 and ZINC, highlighting the importance of PE in both cases. Going from GT + LapPE to GT + Linear Transformer for ZINC, there is a significant further improvement in loss (about 30%). This is remarkable, consid- ering that the linear Transformer accounts for less than 0.7% of the total number of parameters. Note that the SOTA eтror for ZINC regression is significantly lower than 038 on more recent ar- chitectures; the significance of our result is in demonstrating the improvement just by replacing the LapPE with the linear Transformer, while keeping everything else fixed. In contrast, going from GT + LapPE to GT Linear Transformer for QM9, the difference is essentially zero. We conjecture that this may because QM9 molecules (average of about nodes and 19 edges) are considerably smaller than ZINC (average of about 23 nodes and 40 edges). Thus there may not be too many additional useful features to learn, and LapPE close to optimal. It is still consistent with our theory, for the Linear Transformer to do well as LapPE.
10

---

Published as a conference paper at ICLR 2025
7 ETHICS STATEMENT
The authors have adhered to ICLR's code ethics during the writing of this paper, and when conducting the research described herein. There are ethics concerns which need be highlighted.
REPRODUCIBILITY
We use both synthetic data and open-source molecular datasets in our experiments. Details of our experiment procedures and implementations have been provided in Section 3.5, Section 4.1, Section and Appendix 14.
ACKNOWLEDGEMENTS
Suvrit Sra Acknowledges generous support from the Alexander von Humboldt Foundation's AI Professorship. The authors thank Aaron Schild for the many valuable discussions. and Professor Xavier Bresson from the National University of Singapore for sharing the code which facilitated some of the experiments in this work.

---

Published as a conference paper at ICLR 2025
REFERENCES
AH Bentbib and Kanber. Block power method for svd decomposition. Analele ştimtifice ale Universitäti" Ovidius" Constanja. Seria Matematicä, 23(2):45-58, 2015.
Mitchell Black, Zhengchao Wan, Gal Mishne, Amir Nayyeri, and Yusu Wang. Comparing graph transformers via positional encodings. arXiv preprint arXiv:2402. 14202, 2024.
Thomas Bühler and Matthias Hein. Spectral clustering based on the graph p-laplacian. In Proceed- ings of the 26th annual international conference on machine learning, pp. 81-88, 2009.
François Charton. Linear algebra with transformers. arXiv preprini 1r.Xv:2112.018800 2021.
Krzysztof Choromanski, Han Lin, Haoxian Chen, Tianyi Zhang, Arijit Sehanobish, Valerii Likhosh- erstov, Jack Holder,, Tamas Sarlos, Adrian Weller, and Thomas Weingarten. From block- toeplitz matrices to differential equations graphs: towards general theory for scalable masked transformers. In International Conference on Machine Learning, pp. 3962-3983, PMLR, 2022.
Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic analysis, 21(1):5-30, 2006.
Vijay Prakash Dwivedi and Xavier Bresson. generalization of transformer networks graphs. arXiv preprint arXiv:2012.09699 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. arXiv preprint arXiv:2110.07875. 2021.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1-48, 2023.
Moshe Eliasof, Fabrizio Frasca, Beatrice Bevilacqua, Eran Treister, Gal Chechik, and Haggai Maron. Graph positional encoding via random feature propagation. In International Conference on Machine Learning, pp. 9202-9223. PMLR, 2023.
John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zine: free tool to discover chemistry for biology. Journal of chemical information and modeling, 52 (7)11777-1668 2012.
Jinwoo Kim, Saeyoon Oh, and Seunghoon Hong. Transformers generalize deepsets and can be extended to graphs & hypergraphs. Advances Neural Information Processing Systems, 34: 28016-28028, 2021.
Jinwoo Kim, Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae I Lee, Honglak I Lee, and Seunghoon Hong. Pure transformers are powerful graph learners. Advances in Neural Information Processing Systems, 35:14582-14595, 2022.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 11-21618-21621 2021.
Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv preprint arXiv:2202.1 13013, 2022.
Liheng Ma, Chen Lin, Derek Lim, Adriana Homero-Soriano, Puneet K Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim. Graph inductive biases in transformers without message passing. In International Conference on Machine Learning, pp.
PMLR, 2023.
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. arXiv preprint arXiv:2106.05667, 2021.
Luis Müller, Mikhail Galkin, Christopher Morris, and Ladislav Rampášek. Attending to graph transformers. arXiv preprint arXiv:2302.04181, 2023.
12

---

Published as a conference paper at ICLR 2025
Wonpyo Park, Woonggi Chang, Donggeon Lee, Juntae Kim, and Seung won Hwang. Grpe: Relative positional encoding for graph transformer. arXiv preprint arXiv:2201.1278// 2022.
Richard Peng and Daniel A Spielman. An efficient parallel solver for sdd linear systems. In Pro- ceedings of the forty-sixth annual ACM symposium on Theory of computing, pp. 333-342, 2014.
Raghunathan Ramakrishnan, Pavlo Dral, Matthias Rupp, and Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):177, 2014.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35:14501-14511 2022.
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data. Advances in neural information processing systems, 33: 125-125259111,1 2020.
Lars Ruddigkeit, Ruud Van Deursen, Lorenz C Blum, and Jean-Louis Reymond. Enumeration of 166 billion organic small molecules in the chemical universe database gdb-17. Journal of chemical (1 1) 11:2264422888 2875, 2012.
information and modeling, 52(1
Imanol Schlag, Kazuki Irie, and Jürgen Schmidhuber. Linear transformers are secretly fast weight programmers. In International Conference on Machine Learning. pp.
PMLR, 2021.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. In Proceedings of IEEE computer society conference on computer vision and pattern recognition, pp. 731-737. IEEE, 1997.
Balasubramaniam Srinivasan and Bruno Ribeiro. beddings and structural graph representations. In International Conference Learning Repre- sentations, 2020. URL https: http///ppeereiieeeeeeeeeeeeeeeee net/ forum? woworrmmidssxxaaaaee SdxsSxxFSSKKK..
On the equivalence between positional node em-
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information
processing systems, pp. 5998-6008, 2017. URL http: http:///axvvvvvo arxiv. org/abs 11006 03762.
Ameya Velingker, Ali Sinop, Ira Ktena, Petar Veličković. and Sreenivas Gollapudi. Affinity-aware graph networks. Advances in Neural Information Processing Systems, 36, 2024.
Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordy- intsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. In International Conference on Machine Learning, pp. 35151-35174 PMLR, 2023.
Bingbing Xu, Huawei Shen, Qi Cao, Keting Cen, and Xueqi Cheng. Graph convolutional networks using heat kernel for semi-supervised learning. arXiv preprint urXiv:2007.16002 2020.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Vin Liu. Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34:28877-28888 2021.
Seongjun Yun, Minbyul Jeong, Rachyun Kim, Jaewoo Kang, and Hyunwoo Kim. Graph trans- former networks. Advances in neural information processing systems, 32, 2019.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivity. arXiv preprint arXiv:2301.095000 2023.
13

---

Published as a conference paper at ICLR 2025
10
PROOFS FOR SECTION 3
10.1
ELECTRIC FLOW
Proof of Primal Dual Equivalence for Electric Flow By convex duality, the primal problem in (4) can be reformulated as
d Σ
rzff
min
B:BR/2
f=1
= min max f Rs - 20h (BR! v/)
max min [Rf
Rf - -20² (BR -v)
max o BB Φ + 20" +
min Φ Lb 26 T 4 $ER
(8)
Proof of Lemma
Let (0) gradient is given by
$0 CØ TT denote (1/2 times) the dual optimization objective from (5). Its
VF = Lb v.
Let Zı denote the output after / layers of the Transformer (3), i.. Zi evolves according to (3):
Zi+1 Zi W/ ZiZ7 w/? w Z + W
We use BJ to denote the first d rows of Zı, AT to denote the (d + 1)th row (d + k))th row of Zi and T to denote the last k rows of Z₁, i... Zi
B,
A
For i 1...k, let 0i,a denote the zth
4
column of d, Then there exists a choice of WV WQ W W such that for all i
Φ1-1, = 01, - (
Before proving (9), we first consider its consequences. We can verify that F2F = L. which is in turn upper and lower bounded by Amin L Amax. By standard analysis of gradient descent for strongly convex and Lipschitz smooth functions, for d we verify that for all = 1...k
1ØL L c/2b
1 0f 12
5 (1 8Amin 11
6 Lmmin 100
0, 12
e LAmin 11,; 12
exp (-8LAmia)
|
Amin
where oj == arg ming (6) Ct... As a final note, only weakly convex along I direction, but we can ignore this because di,; will always be orthogonal to as long as Φo,i is (as we assumed in the lemma statement).
The remainder of the proof will be devoted to showing (9). Recall that the input the Transformer
B T
Zo is initialized as Zo
V 0kxn
E R (k)))))xn For some fixed ö, our choice of parameter matrices
14

---

Published as a conference paper at ICLR 2025
will be the same across layers:
Tdaxd
Odxk
Oaxk
Laxd
Oaxk
Odxc]]
Oaxd
Oaxc
0axk
W/
Okxd
Okxk
Okak
W W
Opxd
O
Okxk
W
Oxxd
Okeck
0kxk
Okxd
Okxk
-dIxkk]
Oxxd
Oexk
0kxkJ
Opxd
dlaxk
0k
(10)
By the choice of WV W in (10), we verify that for all layers I, Bt = Bu = B, so that
z (W?) W.K Z = L. Again by choice of WV W in (10), A = for all I. thus follows from induction that
1++1 1: 6C + 8V
(11)
11+1, = 0r,1 - -LLoii + 8qb; = 01,4 5V 5V (0L,)
for = 1...k,
thus proving (9).
10.2 RESISTIVE EMBEDDING
Proof of Lemma
Let I == Jaxn 11TT. Let ò ;= 1/Amax.
Consider the matrix power series, which converges under our choice of 8:
VCT vōv (i- Vi-vvy(i-(i--
21
(I
82)
V8 Σ
1
1
4
where the second inequality uses the fact that (1 - 1-- i.
We define or
v8(2) 1
Odxc
0dxk Okxk Okxk
Laxa
Oaxk
0dxk
Oaxd Oaxd 0kxd
0axk Okxk on orTc
0dxk
W. V
Oxxd
W:O w.k.
Oaxd
Okxk
Okxk
W
0kxk 0k
Okxd
Okxk
Oxxd
Obxk
0kxkJ
(12)
B
Define Zi
A
We verify that for all Bi B, and
A1+1 -1- - 88)
1
2 = = + an = Σ au - -2-1-
10
where we use the fact that v /v by assumption. Therefore,
| CTeb S Σ as 82);
1elll
By upper and lower bounds of Stirling's formula 2 4 6 - & S. eVT.. we can bound az I V Using the fact that (î - OL) x (1 - dAmin I - -ddmin in I, and using the bound on -IAAA min
geometric sum, the above bounded by Amiu V8L | The conclusion follows by plugging in 8 1/ 1/Amax-
10.3 HEAT KERNEL
Proof of Lemma
The power series for - is given by
(-s)L
3c
!!
1=0
15

---

Published as a conference paper at ICLR 2025
(=s)²
We define or
For each layer I, define
Oaxk
0axk
Taxd
Oaxc
0axk
O
Oaxk
0dxi]
wY
Okxd
Texc
Dxxk
Wi w/K
Okxd
Okxk
Dexk
W
Okxd
-leck
Okxk
Okxd
OkxR
OEX
Onxd
Okeck
O
Okxd
ailxxk
OR
Bi
Define Z
A
We verify that for all 1, B₁ = B, and
Φ
A4+1 LA, = c
11+1 11 + a
Σ
ozL.
1=0
Therefore,
1212, - el
Σ
a,L
1villz
i=++1
By lower bound of Stirling's formula, TA 2 (L//)².
Therefore, for 2 8s7max we have |archll 112 S 2- 3-488AAmor For 2 2, the infinite sum within factor of the first term, thus | a, 2 1-tSsamas
10.4
FASTER CONSTRUCTIONS
Proof of Lemma
We begin by recalling the Taylor expansion of Lt:
C 6 E
(recall that ;= Lnxn II /n). Our proof of this section uses a simple but powerful alternative expansion (see for example Peng & Spielman (2014)): for any integer t,
t II E=
2'
I (i-(i))))
M I=0
(i SCY.
(13)
Notice that é terms in the LHS equals 2' terms of the RHS. This is exactly why we will get a doubly exponential convergence. As seen in the proof of Lemma 1, each term in the RHS of (13) coincides with one step of gradient descent. Therefore, if one layer of the Transformer can implement one additional product on the LHS, L layer Transformer can efficiently implement 2" steps of gradient descent. In the remainder of the proof, we will show exactly this. For all layers 1, let
Tuxn
Onxn
Onxn]
Tnxx
Onxn
0nxn
-nxn
Onxn
0nxn
wV- = Onxn Onxn Lnx
Onxn
WPO' T w.K
Tnxa
Onxn
0nxn
W.R =
Onxn Onxn
Onxn
0nxn
Onxn
Onxn]
Onxn
Onxn
0axn
0pxn
0nxn_
Let T =: [T,
Ar, Φ1), where Pt, A1, T B Under the configuration of weight matrices
above, we verify that Ar Inxo for all I, and thus 2, TTw w Zi
ArT 2f
Ti. for all
Next, we verify by induction that Pi+1 = Pr Pí r. T r.r, (i 88- Note that I is symmetric.
I + [i (i-5C) oc)²) 2')
Finally, we verify that 4:+1 41 + ITT d.
2b. Thus by induction.
-
I
I + (i - 60)2').
t=0
16

---

Published as a conference paper at ICLR 2025
Finally, again using (13), the residual term is given by
(f-)c)-
1 =5
2
Noting that (f -6-) x 8 min L)I, we can bound
exp (2min)
||ct - --ll22222 $
Amin
Proof of Lemma 5
Let C 3 We will use the bound
(I sC/C) <e- <
-C/C) (1+233
where the second inequality holds by our assumption that sAmax < 1//C. Therefore,
- - -exp(- - 2
2s² 1²212 X
C (emp(-sL)) sL)1l2 -
-leep(=s
We will now show that Zz, = (T -L/CC) Let us define, for all 1,
wY Inxns W. wiR Inxn:
W -Inxn-
Then we verify that 7+11 74 74 + 7, 7, 74 = z (by symmetry of Zi). Thus by induction,
Zi 2 = -I-sL/C) (I (I-sie sC/CC/
11 PROOFS FOR SECTION 4
Lemma 8 (Single Index Orthogonalization) Consider the same setup Lemma 6, with Trans- former defined in (6). Let Ø1,j E IR" denote the jth column of Dy. For any 1..ck, there exists a choice of WV WQ, WKK W such that
Ø141,5 = d14L.
DIL15 = 01.1
(d (1.)) Ø157
|01+1.1
$=41
for any j # i,
01+1.5 $1.j.
Proof of Lemma Recall that Z, [Bt Dy). Let A E R denote the matrix where Aμ = 1 and is 0 everywhere else. Let H denote the matrix where Hjj = for all j > i, and is 0 everywhere else. Let the weight matrices be defined
wV
Oaxd Okxd
0axk
w w
Oaxd O
Oaxck H
W =0
Under the above definition, BT B is constant across all layers l. We verify that o evolves as
$ 4 क A H
We verify that the effect of left-multillication by A "selects the ith row of 47 Φy"" and the effect of right-multillication by H "selects the (i + 1)th h columns of 4, 4,". Thus
0
AΦ 4H T
The conclusion be verified by right right-multiplying the above matrix with TT, and then applying columnn-wise normalization to Φ (or equivalently, applying row-wise normalization to [2] [Z)a..4+e) described in (6).
17

---

Published as a conference paper at ICLR 2025
Proof of Lemma
Recall that Zi B
Assume for now that Bt B for all layers L. Let Φ1,1 denote the gth
+
column of by. Let be some fixed layer with weights
w
0axd
Odxk
W. W.K
Laxd
Oaxk Opck
W.R
Laxd Oxxd
Odxck - -leck
(14)
Okxd
1ack]
Oxxd
Combined with (6), these imply that P.+1 Le,, and that 0141,1 11+1,1/
This im- plements the first step in the loop of Algorithm 1. Although Algorithm does not contain the normalization step, the result is identical, because QR(P) is invariant to column-scallin saauunn of t
We now show (different) configuration of weight matrices which enable a sequence of layers to perform QR decomposition: Consider the construction Lemma 8. For each layer to make 11+ orthogonal with to 01.j for all j > i. By putting & such layers in sequence, we can ensure that 01+k,s orthogonal to Øt+k.j for all 1...k and for all j = i + I...k. Thus 4144 is exactly the column-orthogonal matrix in a QR decomposition of +
can use a single
Finally, we observe that B₁ is unchanged in both (14) and construction of Lemma 8. Thus we verify the assumption at the beginning of the proof that B B for all I. This concludes the proof.
Proof of Corollary 7
The construction is almost identical to that in the proof of Lemma above. The only difference is that we replace the weight configuration in (14) by
W.
Oaxd
0axk [xck]
wiO
w/
Taxd Oaxd
0axk Okxk]
W.R
Taxd 0axk Okxd
Okxd
(a 1)lxxk
- where the change is highlighted red. Under this, we verify that 6141 = ( L)
The remainder of the proof, including construction for the QR(() operation, are unchanged from Lemma 6.
12 LEMMAS AND PROOFS FOR SECTION 5
Lemma (Constructions under (7)) The constructions in Lemmas 2, 3 and can be realized
within the constrained dynamics (7).
Proof of Lemma'
In general, we verify that (7) is equivalent to (3) with weights satisfying the following form:
WY-
Ta Laxd Odx2k W.V.v
W.O
aa laxd
Odx22
W.K
Taxk Laxd
Odx2k W.K.
Ozaxd
Ozkxd
Ozkxd
Taf Taxd
Odx2R W.
w
Ozkxd
Below, we state the weight configurations for (7) which will recover the constructions in each of the stated lemmas. Note that there a small change in notation: as defined in Section 5 corresponds to [Ar; bb.) from the proofs of Lemmas 1, and 3.
We leave the simple verification of this equivalence to the reader.
The construction in Lemma is equivalent to (7) with weight configuration ox
ap = of = 1,
a 0, W.K.
O 0laxk
Oxx
W W.K. 0, W
0 Ōl
Ok
Okxk
Okx
The construction in Lemma 2 is equivalent to (7) with weight configuration ox 0, 0, = a = 1,
of = W.
Xmaa O
1
Lock
Okxk 0xxk
wo, = w.K. = 0. W.R.
0kxk
0
0
Amas
18

---

Published as a conference paper at ICLR 2025
The construction in Lemma 3 is equivalent to (7) with weight configuration ax
0, aj
0
=a 1,
af w/ the temperature parameter.
Ta
Oexk
w/
w.k 0, W.
1ack
0kxk
where is
Okxk
Oaxk]
Ixc
0kxkJ
The construction in Lemma 6 is equivalent to (7) with the following weight configurations:
1. To implement the first step inside the loop of Algorithm 1, let of O, a. af 1,
0f R
0. w/:
Oxxk
Okeck
w.O = w 0. W. = 0xex Oxxk -1k*k
0kek
Oaxk
1xxk]
2. To implement the QR decomposition step inside the loop of Algorithm 1, we will need to
equivalent construction in Lemma 8. Let ax
0. aj
Q =af 1, a. 0. and let
W V
O
w.. T w.k. Oxxk
Oxx
O&x
W 0. where A and H are
Okxk
A
H
as defined in the proof of Lemma 8.
Lemma 10 (Invariance and Equivariance) Lel TFF and TF? be as defined in Section 5. Let U Ddxd be any permutation matrix. Then for all layers I,
TF (BU, b) U TF TF (BU, Φ) TF (B, +)
(15)
Proof
We will prove these two claims by induction simultaneously. Recall from (7) that
k. Bi+ (1 + BR avva (aQIaR:B.B] + 2.W, w w.kk0
8 (I+ W R.
D. + W.V. T7 [q W Q W K. 47
Recall from the definition that TF (B, 4) == Bo = B and TF (B, 4) = 40 = 4. Thus (15) holds by definition. Now suppose (15) holds for some By (7),
2)
=(1 + an) T TF (BU,
av. TF. (BU, +)
(BU, TFP b) TF [BU, BUU $)
TF. [BU, 4)
(BU, k. TF (BU, (BU,))
=(1 + an.UU (B.
+vr TF (B, 4) [Q.10x TF (B, TF の)) [F
aV. (B, )) TF [B b) T W TF (B, 0))
where we use the fact that UUT laxd. By similar steps as above, also verify that
TBU 2) = TF
This concludes the proof.
13 DETAILS FOR SYNTHETIC EXPERIMENTS
We consider two ways of sampling random graphs:
1. Fully Connected (FC) graphs: 10 nodes and 45 edges.
19

---

Published as a conference paper at ICLR 2025
2. Circular Skip Links (CSL) graphs: 10 nodes and d 20 edges. The skip-length is sampled uniformly at random from (2,4, 8). See (Dwivedi et al., 2023) for detailed definition of CSL graphs.
For both FC and CSL graphs, the resistance of an edge e r(e) ed((), where u(e) independently sampled uniformly from |- 2].
14 DETAILS FOR MOLECULAR REGRESSION EXPERIMENT
Below, we provide various details for the molecular regression experiment in Section 6.
14.1 DATASET DETAILS
For QM9, the training set size is 20,000, the validation set size 2000, the test set size is 100,000. The vaining/validation set are subsampled from the full training/validation set. The average number of nodes is 8.79, and the average number of edges is 18.8.
For ZINC, the training set size is 20,000, the validation set size is 2000, the test set size is 24,445. The training/validation set are subsampled from the full training/validatton set. The average number of nodes is 23.16, and the average number of edges is 39.83.
14.2 ARCHITECTURE FOR MOLECULAR REGRESSION EXPERIMENT
The linear Transformer we use for the experiment in Section 6 is described in (16) below:
B (R.i) + +vv (D 1/2 B D 1/2 + b, Q.4 W (.
TT (T+W 8. + w.v (i 1/2 B,B, DT 1/2 + B1, W. w Φ0
B4 + B141/||B4+1||
01+1, + d1-1://l0u44all
i=l.)
(16)
It is similar to the memory memory-efficient Transformer architecture (7) from Section 5, with number of modifications which we explain below. Let the input to the transformer Zo E gd+k where denotes the number of edges, and k is the dimension of learned features.
1. Scaling by D-1: The GT in Dwivedi & Bresson (2020) uses eigenvectors of the normalized Laplacian C == D0112 where D is the diagonal matrix whose ith diagonal entry is given by [D]; := |C.,l Σラ= BByl- To be consistent with this setup, we modify the dy- namics in (7) add the scaling by D. 1/2
the part of the self-similarity matrix involving Bi, highlighted in red (16), where Dj the diagonal matrix with the yth diagonal entry given by
Dila == BBlgs
With this additional scaling in the dynamics, the same weight constructions in all the lemmas in this paper will compute the corresponding quantities for the normalized Laplacian E instead. For instance, with the D, 1/2 scaling, the construction in Lemma I computes L!, and the construction in Lemma 6 computes the top-k eigenvectors of É. This can be verified using the following two facts: First, in all our constructions, t interacts with B₁ only via the self-similarity matrix B, BJ Second, D 1/2 2 BB 1/2 Σ.
2. Independently scaled similarity matrix: For each layer I, introduce additional scalar pa- rameters 3r, Br,2, Br,,, 31,4. One layer of (16) is more expressive than one layer of (7) but less expressive than two layers of (7) (ignoring the difference due to D 1112).
Diagonal constraints on W: We constrain V. WQ.0 K,0 to be diagonal, and W W n, to be a scaling of identity.
20

---

Published as a conference paper at ICLR 2025
4. Weight sharing: Layers 31, 3/ + 1, 2 share the same parameters, for all integers 1. Phrased another way, each layer is looped 3 times.
5. Per-layer Scaling: after each layer, we scale Bj to have Frobenius norm 1, and we scale each column of 2 to have Euclidean norm I.
Items 2-4 useful for reducing the parameter count and improving generalization. Item 5 makes training feasible for deeper layers. The construction in Lemma 4 for subspace iteration can still be realised under the changes in items 2-5. Under the change in item 1, the construction in Lemma will find eigenvectors of L. instead of L.
14.3 EXPERIMENT DETAILS
The GT we use has 128 hidden dimensions, 8 heads, and layers. The position encoding dimension is 3 for QM9, and 6 for ZINC.
The linear Transformer we use contain described in Section 14.2. The dimension of tb, is 8. We use 1 linear map. with parameters M, to project & down to the PE dimension [PE_dim=3 for QM9 and PE Pe_dim=6 for ZINC). This output is then passed to the GNN in the same way as the LapPE. To clarify the distinction among three models, we provide pseudo-code for Graph Transformer, Graph Transformer + LapPE and Graph Transformer + linear Transformer below:
layers, with parameters shared every 3 layers, as
Let GT denote the graph transformer from (Dwivedi Bresson, 2020). Let denote the collection of basic graph information, including edge list, edge features, and node features. Let LapPE(G) return the Laplacian eigenvector positional encoding for G. Let B be the incidence matrix of G. Let LT denote the linear Transformer, which takes B as input ( can be viewed internal parameters of LT)
Then the predictions for each model in Table 2 given by
Graph Transformer
CT,G,None GT LapPE()))
Graph Transformer + LapPE
Graph Transformer linear Transformer
GT GT(G:1inear(,,L((()
(17)
The trainable parameters are given by
(all the parameters of GT) + (all the parameters LTT)
= (all the parameters of GT) + (M, &o (a's, f'', W's from (16))).
Before training on the actual regression task, pretrain the linear Transformer to return the top PE dim Laplacian eigenvectors. This gives a good initialization, and improves the optimization landscape.
We train using AdamW. Graph Transformer parameters are updated with initial 0.001 Ir. Linear Transformer parameters are updated with initial 0.01 Ir. For ZINC. we train for 2000 epochs with Ir halved every 800 epochs. For QM9, we train for 1000 epochs with Ir halved ever 400 epochs. The means and standard deviations in Table are each computed over 4 independent seeded runs.
21

---

Published as a conference paper at ICLR 2025
15
EXPERIMENTS FOR EFFICIENT IMPLEMENTATION
(ogitee)
Layer
Layer
Layer
Liyer
3(a) losset (electric)
3(b) loss VET (resistive)
3(c) lossexp (-0.52) (heat)
3(d) Eigenvector
Figure 3: Plot of loss against number of layers for the 4 problems. Figures (3(a), 3(b), 3(c), 3(d) correspond to Figures ing pair of plots are identical, except for the architecture used: all plots in Figure are made using the efficient implementation described in Section
respectively. The experiment setup of each correspond-
22


Reviews:
[{"review_id": "XnotUdpKJv", "reviewer": "Reviewer_ryVa", "summary": "The paper investigates the capabilities of the linear Transformer when applied to graph data, particularly its ability to implement algorithms for core graph tasks without explicit positional encodings. The authors demonstrate that the linear Transformer, which uses the graph incidence matrix as input, can solve canonical problems like electric flow computation and eigenvector decomposition. Key contributions include explicit configurations for weight matrices, error bounds for each task, and empirical results validating theoretical findings on synthetic data.", "questions": "Please address the points raised in the previous section.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "**Originality**: This paper introduces a novel use of a linear Transformer, to perform core graph algorithms like electric flow and eigenvector decomposition without explicit positional encodings. \n\n**Quality**: The paper offers rigorous theoretical analysis with explicit weight constructions and error bounds for each algorithm.\n\n**Clarity**: The paper is well-organized, clearly written, and enjoyable to read.", "weaknesses": "1. Since the paper’s contribution is primarily theoretical, providing a proof sketch under the main results would be highly beneficial. Additionally, a more detailed description of the weight matrices would enhance clarity.\n\n2. The theoretical results are not particularly surprising given the use of a linear Transformer. Could these results also apply to GNNs?\n\n3. The practical impact of the proposed approach is unclear, as the empirical results are limited compared to numerous existing works. For instance, the performance on the ZINC dataset is significantly lower than the state-of-the-art, with an error approximately twice as large.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ogfSlFv3Qp", "reviewer": "Reviewer_fauP", "summary": "The authors introduce a simplified (linear) Transformer architecture (no softmax activation in self-attention layers) and use it to show (theoretically and empirically) that it can implement graph algorithms. In particular they present a series of lemmas providing bounds in approximating the solution to problems like flow and heat kernel computation, finding resistive embeddings and performing eigenvalue decomposition (assuming specific weight matrices). Their input encodings include the incidence matrix representation of the graph and then the approximate solution will land in a subset of columns in the output encodings' matrix,  after passing through a a number L of transformer layers (where L is decided by the target approximation error). A parameter efficient variant is also presented. The linear transformer is tested on a series of small graph instances of the problems (e.g. of the order of 10 nodes and 20 edges) and for learning a positional encoding (PE) for a molecular regression task.", "questions": "- How would the analysis be impacted if nonlinearity in self-attention was re-introduced? In order to \"understand, at a mechanistic level, how the Transformer processes graph-structured data\" (lines 32-33), we are expected to remove only non-essential elements of Transformer architecture (and nonlinearity seems to be a critical one). The linearity in the Transformer, means that if its operations are expanded for a number of layers we'll reduce to a simple matrix operator.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The idea is novel and appealing: using a transformer to compute the solution to a graph problem as part of the latent vectors in its node output representations adds another level of applicability of transformers well beyond language understanding or generation.\n\n- Lemmas are well organized, follow similar themes and the narrative is smooth and clear.", "weaknesses": "- Removing the nonlinear softmax terms from standard transformer architecture, facilitates analysis but severely impacts the power of the model.\n\n- Complexity of the approach is prohibitive: it can be O(n^4) and this explains their experimentation with very small synthetic graphs. Parameter efficient implementation is promising, but still the original idea is far from being scalable and thus practically testable beyond a couple of tens' of graph nodes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rIvgqXYXDl", "reviewer": "Reviewer_BwGA", "summary": "The paper shows that Linear Transformers (and their variant) using the incidence matrix can implement canonical problems, such as electric flow and subspace iteration. While the contribution is mainly theoretical, the authors also empirically validate their findings, and further show that on existing molecular datasets the linear transformer is capable of learning better performing positional encodings than standard laplacian eigenvectors.", "questions": "Q1. Can you elaborate on the practical implications of your findings (see W1)?\n\nQ2. I think the eigenvectors you converge to have sign/basis ambiguities derived from the choice of $\\Phi_0$. How do you deal with these ambiguities? Do you perform sign flipping at every forward pass?\n\nQ3. I think denoting by $d$ the number of edges (Line 128) is a bit confusing, because $d$ is usually the embedding dimension. Also, in Equation 1, since $j= 1, \\ldots, d$ is the first index of $B$, I think $B \\in \\mathbb{R}^{d \\times n }$, but you wrote $B \\in \\mathbb{R}^{n \\times d }$ (Line 132). Please clarify.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The results are interesting. I particularly appreciated the structure of the paper, in which experimental results are shown after their corresponding theoretical claims instead of having them all the end, which highlights the connection between the presented theory and the experimental results.", "weaknesses": "W1. Generally speaking, I think the impact of the paper tends to be a bit limited. This is especially true because the considered architecture (linear Transformers), and in particular its variant which includes an L2 normalization, is not widely used. The main implication I can see is to use the variant of the linear transformer in place of existing predefined positional encodings, and therefore as an additional component of a bigger architecture.\n\n\nW2. I find a bit confusing that the authors claim that the input to the Transformer is only the graph incidence matrix, without any other positional encoding (Lines 11-13), while for instance for the subspace iteration $\\Phi_0$ is required to be some arbitrary column-orthogonal matrix. I think -- depending on the graph -- $\\Phi_0$ might need to be a positional encoding to ensure all columns are orthogonal (note that if $\\Phi_0$ is a random matrix then it is a positional encoding [Srinivasan and Ribeiro, 2020]). I think the authors need to clarify this point and adjust accordingly in the entire paper.\n\n\nSrinivasan and Ribeiro, 2020. On the Equivalence between Positional Node Embeddings and Structural Graph Representations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fcQWhgFiqS", "reviewer": "Reviewer_PYgD", "summary": "The papers show theoretically and empirically that the linear transformer can approximate the hypothesis function space of several graph problem (electric flow and Laplacian eigenvector decomposition). The authors also conduct a real-world experiment on molecular regression, in which positional encoding outputs by transformers are adopted.", "questions": "* While the paper concerns two graph problems: electric flow and Laplacian eigenvector decomposition, why the title mentions only the first one?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The organisation of the paper is clear, it's easy to understand the main contribution of the paper. And mathematically, it's generally well-written.\n* The idea of solving the traditional graph problem with a Transformer is novel. \n* For the proposed lemmas, the paper provides the relevant experiments which are quite nice.", "weaknesses": "* My main concern is that since the neural network is a universe approximator, it's not surprising that it (in this paper, even it concerns linear Transformer, which is more like in a polynomial function) can solve approximate the hypothesis function space of several graph problems. I wonder how the lemmas shown in the paper can provide us with more useful information.\n* The paper lacks a conclusion section.\n* The real-world experiment concerns only the Laplacian eigenvector decomposition, it would be nice to have another for the electric flow.\n* See the questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)