Generalizable Insights for Graph Transformers in Theory and Practice
Authors: Timo Stoll
Luis Müller
Christopher Morris
Venue: NeurIPS 2025 spotlight ()
Keywords: graph transformers
expressivity
structural encodings
structural embeddings
positional encodings
Primary area: deep_learning
TL;DR: We provide a principled, unified graph transformer architecture, study the impact of structural embeddings for expressivity, and do a large-scale experimental study to complement the theory.

Abstract: Graph Transformers (GTs) have shown strong empirical performance, yet current architectures vary widely in their use of attention mechanisms, positional embeddings (PEs), and expressivity. Existing expressivity results are often tied to specific design choices and lack comprehensive empirical validation on large-scale data. This leaves a gap between theory and practice, preventing generalizable insights that exceed particular application domains. Here, we propose the Generalized-Distance Transformer (GDT), a GT architecture using standard attention that incorporates many advancements for GTs from recent years, and develop a fine-grained understanding of the GDT's representation power in terms of attention and PEs. Through extensive experiments, we identify design choices that consistently perform well across various applications, tasks, and model scales, demonstrating strong performance in a few-shot transfer setting without fine-tuning. Our evaluation covers over eight million graphs with roughly 270M tokens across diverse domains, including image-based object detection, molecular property prediction, code summarization, and out-of-distribution algorithmic reasoning. We distill our theoretical and practical findings into several generalizable insights about effective GT design, training, and inference.

Generalizable Insights for Graph Transformers in Theory and Practice
Timo Stoll"
Luis Müller
Christopher Morris
Department of Computer Science
RWTH Aachen University
Aachen, Germany
timo stoll@log........ rwth-aachen.de
Abstract
Graph transformers (GTs) have shown strong empirical performance, yet current architectures vary widely in their use of attention mechanisms, positional embed- dings (PEs), and expressivity. Existing expressivity results are often tied to specific design choices and lack comprehensive empirical validation on large-scale data. This leaves gap between theory and practice, preventing generalizable insights that exceed particular application domains. Here, we propose the Generalized- Distance Transformer (GDT), GT architecture based on standard attention that incorporates many recent advancements for GTs, and we develop a fine-grained understanding of the GDT's representation power in terms of attention and PEs. Through extensive experiments, we identify design choices that consistently per- form well across various applications, tasks, and model scales, demonstrating strong performance ation covers eight million graphs with roughly 270M tokens across diverse domains, including image- based object detection, molecular property prediction, code summarization, and dittr--diittibttiion algorithmic reasoning. We distill our theoretical and practical findings into several generalizable insights about effective GT design, training, and inference.
few-shot transfer setting without fine-tuning. Our evalu-
1 Introduction
Graphs are fundamental data structure for representing relational data and are prevalent across
scientific and industrial domains. They naturally model interactions in chemistry [Gilmer et al., 2017
Jumper al. 2021], biology [Zitnik et al. 2018 Fout et al.] (017)), social and citation networks Kipf
and Welling 2017 Hamilton et al. [017]] recommendation systems (Ying et al.] [0188] Wu et al.
2020), computer vision [Xu al.] 2021]. and code analysis [Allamanis al. [018]] Hellendoorn
et al. 2021]. While graph neural networks (GNNs) Zhou et al. 2020 Bronstein et al.) 2021]
specifically message-pussing neural networks (MPNNs) [Gilmer al. 2017), remain the most prominent architectures in graph learning, recently, graph transformers (GTs) have emerged Müller al. 2024) and have found success in applications such as protein folding [Abramson et al. 2024 weather forecasting [Price et al.) 2025]. or robotics (Vosylius and Johns 2025]. Moreover, because graphs are a general modeling language, GTss can be seen as generalizations of traditional transformer architectures [Vaswani et al. 2017 Devlin et al.) 2019 Brown et al.) 2020]. As such, theoretical and practical insights about GTs can be leveraged improve our understanding of transformers' reasoning abilities and representation power [Sanford et al., 2024 Cheng et al. [025). In addition, LLMs with causal masking can be seen as GT's on special types of directed acyelic graphs, and tools
"Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Tokemization
Transformer encoder
Gush profztin
Nade profiction
Bige proiciion
Nataen
Node tokera
Edge so
N
<P
SU.M
30M
SC
Streamlined implementation
Largo-scale evaluation
Figure 1: Overview of the GDT and accompanying evaluation. Top left: We support node- and edge-level tokenization with corresponding absolute PEs (depicted below each token). Top right: We incorporate relative PEs and edge features via the attention bias. Bottom left: We provide effective and streamlined implementations for incorporating edge features and PEs. Bottom right: All empirical evaluations are done on large-scale datasets spanning various applications.
from graph learning can be used to study and understand their behavior at inference time Barbero
al. 2024 2025
Despite these promises, the progress of GTs hindered by lack of standardized methods for obtaining generalizable insights. Specifically, we identify three main obstacles in the current literature: architecture-tice expressivity, limited evaluation, and graph-speciife attention. Here, architecture tied expressivity refers to the shortcoming that current expressivity results are often tied to specific architectural designs, such as special attention mechanisms (Zhang et al., [023 Ma et al., 2023 Müller et al., 2024 Black et al. 2024) or choices of positional embeddings (PEs) [Tssssulin et al.
2022] Ma et al. 2023 Kim et al. 2022 Müller and Morris, 2024). In addition, empirically, GTss are often evaluated and compared small-scale datasets [Rampášek et al. [2022] Ma et al. 20033 where otherwise negligible implementation choices can be more prominent, leading to limited insights. In addition, GT's are rarely evaluated on their lepresentationnleaminng capabilities, for example, in zero or few-shot transfer settings. Finally, regarding graphhspeciff attention, most GTs deviate far from the traditional transformer architecture, making it challenging to derive generalizable insights about transformers beyond particular application domains.
Present work This work aims to overcome the above obstacles and provide a general and powerful graph transformer architecture. Through rigorous theoretical and empirical analysis, develop the
Transformer (GDT), a general graph transformer architecture whose expressivity can be characterized by the powerful Ceneralized-Distane Weisfeiler-Leman algorithm [hhang et al. 2023). Concretely, the GDT
1. captures MPNNs, most graph transformers, and many other transformer models, e.g., causal and bi-directional transformers;
2. is effective across application domains, as well as on graph-, node-, and edge-level prediction tasks; and
3. is evaluated at sufficient data scale and can learn transferable representations, allowing for sew-shot transfer and extrapolation.
Our provably expressive GDT architecture. supported by rigorous empirical evaluation, represents significant step toward developing highly effective, general- purposs graph models that enable generalizable insights across diverse domains.
Related work With GT architectures being successful in various domains, several approaches exist for applying transformers to graph learning tasks. Apart from pure transformer architectures
such Dwivedi and Bresson 2020 Ying et al. 2021a Kim al. 2022 Müller and Morris 2024)

---

most GT designs incorporate changes to the attention mechanism [Bo et al., 2023 Kreuzer et al.
2021
Ma al. 2023]. or use attention jointly with MPNNs [amppäsek et al. [022 Choi et al.
2024 see Müller et al. [024] for an overview of GTs. Moreover, [hhang et al. [2023] propose
a modified attention mechanism for a GT to simulate the Generalized Distance Weisjeiler-
algorithm (GD-WL), variant of the Weisfeiler-Leman algorithm (1-WL. (Weisfeiler and Leman
1968] incorporating distance information. Indeed, there exists an extensive literature on deriving
architectures more expressive than the 1-WL test, both for GNNs [Azizian and Lelarge 2021| Maron
ctt al. 2019a b. Morris et al. 6020,Pung et al.] 2023] as well as GT's |Ma et al.) 20224] Zhang et al.
2023
2024, Kim et al. [002 Müller and Morris 20244 Müller et al. 2024] As noted by Müller et al.
2024]. , GTss heavily rely on structural and positional information captured by a positional embedding
to increase expressiveness. Common choices include absolute PEs such as SAN [Kreuzer et al.
2021] LPE [Miller and Morris, 2024). SPE [Huang et al., 2024). and SignNet/BasisNet [Lim et al.
2023 RWSE [Dwivedi et al. 2021]. J. RRWP [Ma et al. [023]] as well PEs based substructure counting (Ying et al. 202 al. In terms of theoretical and empirical evaluation of GT's, the closest related works on the theoretical side are Zhang et al.) (2024, Black et al. (2024). Rampášsk et al.) [2022] and et al. [002).. However, neither of these works considers standard attention or compares design choices such as PÉs on large-scale data.
2 Generalized-
Transformer
In this section, we derive the GDT by combining multiple methods from the recent graph learning literature, while maintaining standard attention and compatibility with most traditional transformer models. Moreover, we prove that the GDT is powerful enough to simulate the general and expressive GD-WL algorithm [Zhang et al.] 2023). We will first introduce some notation and necessary background, and then develop our theoretical framework.
2.1 Expressivity and Weisfeiler-Leman variants
We consider finite graphs G == (V(G), E(G), ly, lg) with nodes V(G), edges E(G). Note that for simplicity we assume that the nodes and edges are already embedded via node embeddings lv: V(G)= - Rd, and edge embeddings e:: V(G)² + IRd, where d E N+ the embedding dimension and (v, w) is simply the all-zero vector if there is no edge between nodes v and w. We always fix an arbitrary order on the nodes ((G) to be consistent with vectorial representations such as those used in transformers. We study the expressivity of a graph model via its ability to distinguish non-isomorphic graphs, which is common practice for graph neural networks and GTs (Morris et al. 2019 Abboud et al. 22222 Zhang et al. 2023 Black et al. 2024 Müllrr and Morris 2024]. Such notion of expressivity is often studied in the context of the new k-dimensional Weisfeiler- algorithm (k- WL) [Cai et al. 1992]. a hierarchy of graph isomorphism heuristics with increasing expressivity and computational complexity as k > O grows. MPNNs without PEs typically have 1-WL expressiivt Another important graph isomorphism heuristic in the context of this work is the GD-WL variant (Zhang et al., 2023), which we formally introduce here. Concretely, given a graph G = (V) F(G),, ), we seek to iteratively update colors for each node v E V(G), denoted (C()), where > 0 denotes the iteration number. We initialize (2)(v) with the node colors consistent with εv. that (v) = xe(ww) if and only if (v( = (v(w), for all pairs of nodes v, w. Then, the
GD-WL updates the color (v) of node E (G). as
X
(v) = hash { (do(v, w), xc((w)
V(G)))
(1)
where do: V(G)2 - R+ is a distance between nodes in G and hash is an injective function, mapping each distinct multiset to previously unused color. The expressivity of the GD-WI. depends on the choice of dg. Setting dG(v, w) if and only if o and w have an edge in G, yields 1-WL expressivity. In practice, the GD- WD-WLFF is often implemented with GT, where de is incorporated via modified attention [Ma et al. 2023 Zhang et al.] 2023). In Section 2.3 for the first time, we prove that a GT with standard attention can simulate the GL- with de being incorporated as a PE.
2.2 Defining the GDT
While many variations of GT's exist, we consider the standard transformer encoder based on Vaswani ct al. (017). This allows us to use standard attention layer, without modifications commonly
3

---

seen in other GTs. Concretely, the GDT processes matrix of initial token embeddings X E Rixdd derived from G, using scaled dot-product attention and subsequent application of a multi-layer perceptron (MLP). Here T. E N+ denotes the number of tokens, typically in the order of the number of nodes, and d denotes the embedding dimension. We now describe tokenization and attention, and how we incorporate edge embeddings into the GDT.
Tokenization For this study, we will consider two possible tokenizations: (a) node-level tok- enization, where each token corresponds to node in G and the initial token embeddings are constructed from node embeddings lv; and (b) edge-level tokenization, where each token cor- responds to either a node or edge in G and the initial token embeddings are constructed from the node embeddings by and the edge embeddings & for node- and edge-tokens, respec- tively. In practice, kenization on a transformation G' of G. with V(G") = {vu,)) E(G') = {((u, v), (w, 2))
use the fact that edge-level tokenization is equivalent to node-level to- E V(G)) E(G) and
w V
w V
Special tokens As a convention, and following many prior works on transformer encoders, we use special [cls] token to read out graph-level representations from the GT. For simplicity, we treat the [cls] token as a virtual node connected to all other nodes. This virtual node is also equipped with unique node embedding ev [cls]) and unique edge embeddings [g([cls], v) Lg [c1s], w) and (v, [cls]) = (g(w, [cls]) ), for all pairs of nodes u, w E V(G).
Attention For the attention, let Q,K, V E RR 1xd and B R.x. be the attention bias. We define biased attention as
Attention(44 Q, B) softmax QK + B)V,
where softmax is applied row-wise. While many variations of the standard transformer layer exist, generally takes the form
X MLP (AAtttettion(x''aa X'WK, (WW,B))
(2)
where Wo. WK. Wv E dxd are learnable linear transformations, and we use a two-layer MLP commonly found in transformer encoder layers; see Appendix B for formal definition. In practice, transformers typically have additional normalizations and residual connections. They are implemented using multi-hear Melli-head attention with attention bias tensor B E IR Lxx heads; see Appendix B for formal definition. Note that Equation (2) is general formulation whose special cases include the local GT (Dwivedi and Bresson 2020). , an aatentiio-bbsed variant of MPNNs with B = 0 if nodes and j share an edge and B = 00 else; attention with causal
Lxxh where is the number of attention
masking (Vaswani et 2017] with B, 0 i < j and B 0o else; as well as many relative
PEs (Shaw et al. 2018 Beltagy et al. 2020
Press et al. 2022
Edge embeddings To incorporate edge embeddings into the GDT, we distinguish between node- level and edge-level GT. For the edge-level GT, edge embeddings are explicitly incorporated via edge tokens. For the node-level case, we adapt the strategy from [eehler-Speicher et al.) [2025], which is itself adapted from Graphormer [Ying et al., 2021a]. to incorporate edge embeddings into the attention bias via an additional projection to the number of attention heads. Formally, for all pairs of nodes j.j E V(G) U [[cls]),
By = p(=((())))))
where p: Rd + h is a neural network, such as a linear transformation or an MLP.
Making predictions For supervised learning with the GDT, we can make graph-, node-, and edge-level predictions by applying an MI.P head the [cls] token embedding, the node token embeddings, and the edge token embeddings. Note that we can leverage edge-level tokenization for edge-level tasks, which provides explicit edge token embeddings. We apply k-nearest- neighhors (k- NN) to the token embeddings after the last layer for few-shot transfer without additional fine-tuning.
Absoluee and relative PEs We can incorporate two classes of PEs, absolute PEs such as RWSE [Dwivedi et al. 2021], LPE [Kreuzer et al.) 2021 Müller and Morris 2024). and SPE (Huang et al. 2024]. which are added at the teken- and relative PEs such as RRWP Ma et al. 2023) which describe relational information between two tokens. Concretely, absolute PE takes the form

---

P E R.ixd where the row P; is the embedded PE vector corresponding to token i. We then project and add P; to the node embedding of token i obtain the initial token embeddings, or formally,
X; (i( P.W.p.
where Wr E IRdxd learnable weight matrix. Moreover, a relative PE takes the form U RLxL Lxd, which we project and add to the edge embeddings to construct the attention bias B. Note that we only consider relative PEs in node-level tokenization. Concretely, for all pairs of nodes i,j V(G) U {[cls]},
Bi = p(((((()))) + U.y We.
where Wy Rdxh is learnable weight matrix. We note that the GDT is Since we always assume the presence of, potentially trivial, edge embeddings, the GDT has, at the very least, embedding of the adjacency matrix as its attention bias, forming a kind of default relative PE. We will refer to this PE NoPE.
if
and only the absolute and relative PEs used are permutation-equivarinnl
2.3 The expressive power of the GDT
We now have the necessary definitions to formally state our theoretical result for the expressivity of the GDT. Importantly, result allows us study GT expressivity solely through PE choice, effectively decoupling model expressivity from attention selection. Concretely, we show that the GDT, with absolute and relative PEs, is sufficient simulate the GD-WL., as well that the GD-WL provides an upper bound on the expressivity of the GDT; see Appendix C for the proof.
Theorem (informal). The following holds:
1. For every choice of distance function, there exists selection of PEs and a parameterization of the GDT sufficient to simulate the GD-WL.
2. For every choice of PEs and parameterization of the GDT, there exists distance function and an initial coloring of the GD-WL sufficient to simulate the GDT.
The central problem we face when proving the first statement is how injectively encode the multisets in Equation (I) with weighted mean, whereas existing results for encoding multisets use sums (Xu al., 2019 Morris iet al. 2019 Zhang et al. 2023). To overcome this limitation, we first note that the weighted mean of tetttmaxaatatett classical result from number theory, namely that sums of distinct exponential numbers are linearly independent over the algebraic numbers, known as the Lindemann -eiirsstrasss theorem [Baker] 1990]. In the proof of Theorem | we show that this linear independence property is sufficient for injectivity, provided that there are at least two distinct token embeddings, a property always satisfied in the presence of the [CLS] token. We note that our expressivity result explicitly uses property of softmax-attention instead of leveraging idealized versions of softmax, such as saturated softmax or
This is because softmax-attenttn computes
is essentially normalized sum of exponential numbers. We then leverage
hardmax, commonly used for expressivity results for graph transformers Zhang et al. (2023 Müller and Morris 2024) and transformers in general [Pérez et al., 2019 Hahn 2020 Merrill et al. 2022
Merrill and Sabharwal 2024
Insight 1: The expressivity of biased attention can be characterized by the GD-WL.
A consequence of Theorem is that the GDT with NoPE is equivalent to 1 1-WL; Appendix C for a formal discussion this fact. With Theorem | we have characterized the expressivity of the GDT in terms of the GD-WL. In the next section, show that this expressivity can be enhanced using PEs. To this end, we present a range of new PE expressivity results, yielding the most fine- grained picture of GT expressivity.
3
The expressive power of positional embeddings
This section provides comprehensive theoretical expressiveness hierarchy of PEs based on the works of Black et al. (2024) and Zhang al. [2024), including novel results on PE expressiveness.
Based on the theoretical results from Scction 2.3 we expand on GDT expressiveness by introducing
5

---

Signfles
Basishet
LPE
RWSE
I-WL
GRIT
RRWP
SPE
(a)
(b)
Figure 2: (a): Overview of our theoretical PE results the context of existing results for PE expressivity, A B (A B, A & B): algorithm A is strictly more powerful (at least as powerful, incomparable) than/to B (b): Trees proposed by Cvetković 1988) used in the proof of Theorem 2
PE expressiveness, establishing a pathway between our transformer architecture and incorporating graph structure information. Furthermore, leveraging the PE expressiveness results, we obtain initial guidelines for empirically evaluating PE design choices. Here, we introduce the four PEs central to our theoretical and empirical study; see Appendix for results for additional PEs.
PEs We consider mandom-wllk-bare PÉs and those based on the graph Laplacian' 's eigenvalues. Random-walk-base PEs are embeddings of the vandom-wall probabilities obtained from multiple powers of the degree-nonee normalized adjacency matrix of the graph. We consider RWSE (Dwivedi et al., 2021]. an absolute PE which uses only the return probabilities of random walks for each node and has linear-time complexity, and RRWP [Ma et al. 2023 relative PE, which uses all random walk probabilities between two nodes and has quadratic runtime complexity.
Laplacian PEs are embeddings of the eigenvectors and eigenvalues of the graph Laplacian; see Appendix for a definition. Here, we consider LPE [Krezzr et al.) [022 Müller and Morris) (202)) an absolute PE which uses a linear-time embedding method but suffers from a lack of basis-invariance, making the PE non-equivariant to the permutation of nodes [Lim et al. 20223] In addition, we consider SPE (Huang et al. 2024), an absolute PE which is permutation-cquuvaaiann but has quadratic runtime complexity. We restrict ourselves to this selection as other common PEs, such as the shortest path distance or resistance distance, can be approximated by RWSE or RRWP [Black et al. _024) Further details and formal definitions are presented in Appendix B
1-WL and random-walk PEs Tönshoff et al. 2023 already show that there are pairs of graphs with n nodes, distinguishable by the 1-WL, requiring random walks with at least O(n) steps to be distinguished. Here, we show that RWSE is incomparable to the 1-WL. This holds independent of the number of random walk steps, and as a result, we can consider RWSE to provide additional information as PE to a pure transformer architecture by differentiating 1-WL. indistinguishable graphs; see Appendix for the proof.
Theorem 2. The RWSE embedding is incomparable to the 1-WL test.
We briefly highlight the most essential proof idea. Concretely, the selected trees introduced by Cvetković [988), shown in Figure 2 are known not to be distinguishable using their eigenvalues and graph angles. However, all trees can be distinguished by the 1-WL test [Cai al. 1992]. At the same time, it is well-known that RWSE can distinguish indistinguishable CSL graphs by the 1-WL (Dwivedi al. 202T). Further, we note that Theorem (roovidesss not only a single pair of graphs but rather an infinite number of trees indistinguishable by RWSE. Finally, we show the following result relating RRWP to RWSE.
Proposition RRWP strictly more expressive than RWSE, given the same random walk length.
Random-wall PEs and eigen PEs We provide results for RWSE, RRWP, LPE, and SPE. In contrast to previous works [a et al. 2023 Zhang et al., 2024], we analyze the expressivity of RRWP directly, without using the GRIT architecture. We find that RRWP is approximated by SPE, which in turn is strictly weaker than the 3-WL test [Zhang et al. 2024 Further, expand on proofs by Lim

---

13M (RAWP)
13M (LPE)
15M IRWSE)
90M (LPE)
90M (RWSE)
160M (LPE)
160M (RWSE)
Bridges
Cycle detection
COCO Pascal
Extrapolation on MST
1.000
1.00
0.50
SOTA
0.995
0.40
Score
0.990
0.35
0.90
0.985
0.30
0.25
0.85
0.980
0.15
20
40
60
3
50
100
150
200
250
Shots (graphs)
#-shots (graphs) log scale
nodes
Figure 3: Results of inference-time experiments. From left to right: Few-shot transfer from BRIDGES to CYCLES with 3-NN over 3 random seeds; few-shot transfer from COCO PASCAL with 5-NN over 10 random seeds; extrapolation beyond training data on MST over 3 random seeds.
et al. 2023 to approximate RWSE using LPE. Taken together, we obtain a fine-graine gra-grained hierarchy of PEs, which summarize in the following result.
Proposition 4. SPE is at least expressive LPE and RRWP, LPE is at least expressive RWSE.
We obtain an even more fine- fine-grained hierarchy of Sigen-vector-bast PEs by including additional embeddings as discussed in Appendix(D As a consequence of the hierarchy, all PEs considered in this section can distinguish graphs not distinguishable by the 1-WL. or, equivalently, the GDT with NoPE.
Insight 2: Any PE in (RWSE, RRWP, LPE, SPE) enhances the expressivity of the GDT.
We present a summary of our results in Figure and highlight our contributions to a completed theoretical expressiveness hierarchy of PEs, complementing the work of Zhang et al.) [2024] and Black et al. [2024). Together with the theoretical insights obtained in Section [2 we arrive at a detailed understanding of the expressivity of the GDT with four popular PEs.
4 Experiments
In this section, empirically evaluate GDT model various real-world and synthetic datasets, at graph- node-, edge-level, and in- and out-of-distribution. Concretely, we compare the performance and efficiency of the PEs in Section 3 and study few-shot transfer, parameter scaling, and size generalization capabilities of the GDT. In the process, we hope to gain a deeper understanding of the relationship between empirical performance and expressivity, based on the results presented in Section 3 and derive generalizable insights for GT's Next, we describe our implementation design, dataset selection, and experimental schedule, and present our empirical results.
Implementation We base implementation the torch. .n. Transf oetaeaffrrmmernnneeee.e... proposed in Py [Paszke et al. 2019]. This allows us to use memory and runtime-efficient attention implementations such FlashAttention (Dao al. 2022] and Memory Efficient Attention [Rabe and Staats] [021]]. In addition, we seek to harmonize implementation differences across PEs to reduce the impact of implementation-spetie number and width of MIP layers and the same activation functions across all PFs. A complete overview of our implemented model architecture is given in Appendix A
advantages
much possible by using the same
Real-world datasets For consistency across graph-, node-, and edge-level tasks, we measure dataset size by the number of input tokens. For the real-world tasks, we evaluate our models on PCQM4Mv2 (PCQ) (Hu et al. 2021], molecular property prediction dataset with 52.5M tokens, COCO (Dwivedi et al.) 2022] an image-based object detection dataset with 58.8M tokens, and
OGB-Code2 (CODE) Hu al. 2020 code summarization datasct with 56. 7M tokens. We focus
7

---

exclusively on large-scale datasets from diverse domains to derive generalizable insights for GT performance. For few-shot transfer, we select PASCAL [Dwivedi et al. 2022], which has the same image domain as COCO but uses different object categories, Bechler-SSpicche et al. [2025] already demonstrate strong transfer from COCO to PASCAL. through fine-tuning. We give an overview of state-of-the-art performance on these datasets in Appendix
Algorithmic reasoning datasets In addition to real-world tasks, we add synthetic algorithmic reasoning tasks for graph algorithms inspired by the CLRS benchmark [Velickovic et al., [022]. Our selection includes the minimum spanning tree problem (MST), detecting bridges in a graph (BRIDGES), and calculating the maximum flow in an undirected graph (FLOw). Here, BRIDGES and MST are edge-level tasks, and FLOW is graph-level task. We further consider the task of detecting whether node lies on a cycle (CYCLES), node-level complement to BRIDGES, to evaluate transfer learning capabilities. Following the literature in algorithmic reasoning for transformer architectures [Zhou et al., [022] 2024a|b) and in particular, graph algorithmic reasoning (Diao and Loynd, 2023 Velickovic et al. [022 Markeeva et al. 2024, Müller et al.) 2024], we evaluate in the size generalization setting where test-time graph instances are up to 16 times larger than those seen during training. Size generalization has been recently identified as a key challenge for graph learning
[Morris et al. 2024]. An expanded introduction to each task is available in Appendix A
4.1 Experimental design
In the first step, we evaluate different PE choices from Section for the GDT on all six upstream tasks. We also consider NoPE, which uses only edge embeddings to infer the graph structure. We fix the parameters 15M; see Appendix [A] for the choice of hyperparameters. Additionally, we compute the runtime and memory efficiency observed for each PE and task. Due to the high memory requirements of storing full random-wal matrices for RRWP on large datasets, we compute RRWP matrices at runtime. To allow a fair comparison between PEs that accounts for computational efficiency, we set a compute budget of 5 GPU days for the 16M models. Furthermore, we evaluate the GDT in comparision to GrDphormer-GD [hhng al. 2023 on BREC [Wang and Zhang 2024). a benchmark evaluating theoretical expressiveness on graph samples. For this, we use RWSE and LPE as PEs for both architectures.
In the second step, we select the best models from the first step and further evaluate them using few-shot transfer, scaling model size, and extrapolating the graph size. In particular, we assess few-shot transfer from Coco to PASCAL, as well as few-shot transfer from BRIDGES to CYCLES. Note that even though BRIDGES is an edge-level task and CYCLES is a node-level task, we should expect strong transfer,
node lies on a cycle if and only if at least one of its incident edges is not a bridge. For scaling, we train additional models with 90M and 160M parameters for PCQ and MST. Finally, we provide extrapolation results for up to 256 nodes (16x the size the training graphs) on MST.
4.2 Discussion of base models
We present our task results in Table T as well as runtime and memory requirements in Figure 4 RRWP performs best of all selected PEs on 4 out of 6 tasks. However, due to the need to compute RRWP matrices at runtime, for Coco and CODE we use additional resources to provide results. Most notably, RWSE and LPE perform significantly better than NoPE and SPE for all tasks except FLOw, but do not face any efficiency issues. Furthermore, LPE and RWSE perform similarly across tasks, placing second and third, respectively, and are often competitive with the less efficient RRWP. Despite theoretical results observed in Section 3 we note the differences in experimental results to be less pronounced. This aligns with previous work on PEs, indicating discrepancies between theory and empirical evaluation. However, extend this observation by providing an evaluation at scale and a direct comparison PEs on a single architecture.
Insight 3: PE efficiency can vary greatly while predictive performance differences are less pronounced.
Due to their favorable efficiency and competitive predictive performance, we selected LPE and RWSE for our scaling and extrapolation experiments and few-shot transfer. For few-shot transfer from
8

---

Table 16M parameter results for different PEs over random seeds. PCQ MAE is in micro electron volt (meV) for clarity of presentation. The mean rank is computed by sorting the models' scores for each task.
Mean Rank
PCQ
COCO F
CODE FI
FLOW MAE L
MST FI
BRIDGES FI f
PE
MAE 4
NoPE
3.50
93.6 0.05
43.12 + 00.85
19.27
+ 00.20
1.73
+ 0.39
93.29
0038
55.36
24.44
LPE
2.50
92.7 0.
44.83
19.48
1.75
+ 0.12
91.08
91.76
SPE
4.00
94.1
0.06
43.87
+ 00.54
19.35
00.11
1.98
+ 0.34
92.52
00.12
54.81
21.20
RWSE
2.67
92.9 0.6
43.82
19.39
1.49
93.26
87.34
RRWP
2.33
90.4
0.3
39.91
4: 01.07
19.42
00.10
1.45
:: 0.06
96.04
00.91
99.21
00.09
(c)
model
100
4,0
SPE
SOM (LPE)
3.5
15M (RWSE)
3.0
100M ILPE!
RINSE
RWSE
160M (RWSE)
LPE
RRWP
POQ (lower better) MST (higher betterl
0.04 0.06
4000
6000
8000
10000
task
Millonn tokens /s
GPU Momory [MB]
Figure 4: (a): Results 90M and 160M models for PCQ and MST evaluated on LPE and RWSE. (b): Number tokens evaluated per second during training for each PE. Results are obtained by averaging runtimes per token across tasks. (c): Average GPU memory requirement for each PE.
BRIDGES to CYCLES, additionally select RRWP due its significantly better OOD performance on BRIDGES.
With results for BREC shown in Table observe the performance of GDT and Graphormer- models to be comparable and differences to be negligible, aligning experimental results to theoretical observations made in Theorem 1 and showcasing non-trivial performance. Further, the difference in expressiveness of RWSE and LPE can be observed for both models. However, we note that BREC results depend on specific hyperparameter choices and are often unstable during training. An overview of the hyperparameters selected for BREC can be found in Appendix A.7
4.3 Extended evaluation
We present the scaling results in Figure (a), few-shot transfer in Figure (a) and (b), and extrapo- lation results in Figure (c). For scaling, we observe that the relative performance between PEs relatively robust to model scale. In three out of four cases, in- and improves consistently with increasing model scale. The only exception the 160M model with LPE on MST, which drops off slightly compared to its 90M counterpart but still outperforms both 15M models on this task.
performance
Insight 4: Scaling the GDT generally improves in- and out-of-distribution performance.
For few-shot transfer, we find that all three evaluated models can demonstrate strong performance when transferring from BRIDGES to CYCLES with just few shots. In particular, the 15M model with LPE already achieves near-perfect performance with shots and significantly better than RWSE and RRWP up 60 shots. When transferring from COCO to PASCAL, observe performance increases even for 1000 shots where both RWSE and LPE surpass the current SOTA on PASCAL, despite seeing less than 10% of the available training samples at inference-time; see Appendix for an overview of state-of-the-arr performance on PASCAL.
Insight 5: Representations learned by the GDT allow for effective few-shot transfer.
Finally, we find all PEs and model scales to extrapolate well on MST. particular, we still observe an Fl score of around 85 256 nodes or 16x the graph sizes seen during training.

---

Table 2: Results of GDT and Graphormer- GD models on the BREC benchmark. Each column
indicates the number of samples correctly distinguished by each model.
Model
PE
Basic
Regular
Extension
CFI
Total
Graphormer- GD
RWSE
57
50
96
203
Graphormer-GD
LPE
55
40
85
3
183
GDT
RWSE
57
50
96
203
GDT
LPE
54
39
84
180
5 Limitations
Currently, the GDT can only make use memory-efficient attention at inference time, due use of learnable attention bias. For example, the learnable attention bias is not compatible out-of-the-bon with Altentont [Dao 2024] or Attentttntoon [Dong et al. 2025]. Moreover, many more variants exist that could be included in study; for example, PEs listed in Section Finally,
we note that our current implementation does not take the sparsity of the attention bias into account, which can lead to prohibitive memory requirements for very large graphs.
6 Conclusion
We establish the GDT, a generalizable, expressive graph transformer based on the standard trans- former implementation. We show the GDT to be equivalent to the GD-WL in terms of theoretical expressiveness, augmented in expressivity by using PEs and their respective expressiveness. Further, demonstrate strong empirical performance across multiple domains and large-scale datasets, determining an empirical hierarchy of PEs. We also show the GDT to be able to learn transferable rep- resentations, extrapolate on graph size for synthetic tasks, and results being robust concerning model scale. Thereby, we provide generalizable theoretical and empirical insights for graph transformers.
Acknowledgments and Disclosure of Funding
TS, LM, and CM are partially funded by DFG Emmy Noether grant (468502433) and RWTH Junior Principal Investigator Fellowship under Germany's Excellence Strategy. We thank Erik Müller for crafting the figures.
10

---

References
R. Abboud, R. Dimitrov, and I. Ceylan. Shortest path networks for graph property prediction. In Learning Graphs Conference (LoG), 2022.
J. Abramson, J. Adler, and J. Dunger. Accurate structure prediction of biomolecular interactions with alphafold 3. Nature, 630:493-5500 500, 2024.
M. Allamanis, M. Brockschmidt, and M. Khademi. Learning to represent programs with graphs. In Interaational Conference Learning Representations (ICLR), 2018.
W. Azizian and M. Lelarge. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations (ICLR), 2021.
A. Baker. Transcendental Number Theory. Cambridge University Press, 1990.
F. Barbero, A. Banino, S. Kapturowski, D. Kumaran, J. G. M. Araújo, A. Vitvitskyi, R. Pascanu, and P. Veličković. Transformers need glasses! information over-squashing in language tasks. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
Barbero, Álvaro Arroyo, X. Gu, C. Perivolaropoulls, M. Bronstein, Veličković, and Pascanu. Why do Ilms attend to the first token? Arxiv preprint, 2025.
M. Bechler-Speicher, B. Finkelshtein, F. Frasca, L. Müller, J. Tönshoff, A. Siraudin, V. Zaverkin, M. M. Bronstein, M. Niepert, B. Perozzi, M. Galkin, and C. Morris. Position: Graph learning will lose relevance due to poor benchmarks. In International Conference on Machine Learning (ICML) Position Paper Track, 2025.
I. Beltagy, M. E. Peters, and A. Cohan. Longformer: The long-document transformer. Arxiv preprint, 2020.
M. Black, Z. Wan, G. Mishne, A. Nayyeri, and Y. Wang. Comparing graph transformers via positional encodings. In International Conference on Machine Learning (ICMI., 2024.
D. Bo, C. Shi, Wang, and R. Liao. Specformer: Spectral graph neural networks meet transformers. In International Conference on Learning Representations (ICLR), 2023.
M. M. Bronstein, J. Bruna, T. Cohen, and P. Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. Arxiv preprint, 2021.
T. B. Brown, B. Mann, N. Ryder, M. Subbiah,
J. Kaplan, Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert- G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, Sutskever, and D. Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
J. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identifications. Combinatorica, 1244)3399-410, 1992.
D. Chen, L. O'Bray, and K. M. Borgwardt. Structure-aware transformer for graph representation learning. In International Conference on Machine Learning (ICMI., 2022.
D. Chen, T. H. Schulz, and K. Borgwardt. Learning long range dependencies on graphs via random walks. In International Conference on Learning Representations (ICLR), 2025.
Z. Chen, H. Tan, T. Wang, T. Shen, T. Lu, Q Peng. C. Cheng, and Qi. Graph propagation transformer for graph representation learning. In International Joint Conference on Artificial Intelligence (IJCAI), 2023.
X. Cheng, L. Carin, and Sra. Graph transformers dream of electric flow. In International Conference on Learning Representations (ICLR), 2025.
Y. Y. Choi, S. W. Park, M. Lee, and Y. Woo. Topology-infornet graph transformer. In Proceedings of the Geometry- Representation Learning and Generative Modeling Workshop (GRaM), 2024.
11

---

K. M. Choromanski, V. Likhosherstov, D. Dohan, X. Song, A. Gane T. Sarlós, P. Hawkins, J. Q. Davis, A. Mohiuddin, L. Kaiser, D. B. Belanger, L. J. Colwell, and A. Weller. Rethinking attention with performers. In 9th International Conference on Learning Representations, ICLR 2021, 2021.
D. Cvetković. Constructing trees with given eigenvalues and angles. Linear Algebra and its Applications, 105:1-8, 1988.
T. Dao. Flashattention-2: Faster attention with better parallelism and work partitioning. In Interna- tional Conference on Learning Representations (ICLR), 2024.
Dao, Y. Fu, S. Ermon, A. Rudra, and C. Ré. Flashattention: Fast and memory-efficiet exact attention with io-awareness. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Pupers), 2019.
C. Diao and R. Loynd. Relational attention: Generalizing transformers for graph-structured tasks. In International Conference on Learning Representations (ICLR), 2023. 2023.
J. Dong, B. FENG, D. Guessous, Y. Liang, and H. He. Flexattention: A programming model for generating fused attention variants. In Conference on Machine Learning and Systems, 2025.
V. P. Dwivedi and X. Bresson. A generalization of transformer networks to graphs. Arxiv preprint, 2020.
V. P. Dwivedi, S. Kaba, R. Mascarenhas, L. Navickas, A. Salekin, A. Zela, Y. Bengio, and X. Bresson. Graph neural networks with learnable structural and positional representations. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
V. P. Dwivedi, L. Rampášek, M. Galkin, A. Parviz, G. Wolf, A. Luu, and D. Beaini. Long range graph benchmark. In Advances in Neural Information Processing Systems (NeurIPS) Datasets and Benchmarks Truck, 2022.
A. Fout, J. Byrd, B. Shariat, and A. Ben-Hur. Protein interface prediction using graph convolutional networks. In Advances Neural Information Processing Systems (NeurIPS), 2017.
S. Geisler, Y. Li, D. J. Mankowitz, A. T. Cemgil, S. Günnemann, and C. Paduraru. Transformers meet directed graphs. In International Conference on Machine Learning (ICML), 2023.
Gilmer, S. S. Schoenholz, F. Riley. O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning (ICML), 2017.
M. Hahn. Theoretical limitations of self-attention in neural sequence models. Trans. Assoc. Comput. Linguistics, 8:1 1711 2020.
W. L. Hamilton, R. Ying, and J. Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
V. Hellendoorn, Z. Ye, C. Shipwright, J. Gilmer, and D. Tarlow. Global context-aware code summarization. In IEEE/ACM International Conference on Software Engineering (ICSE), 2021.
D. Hendrycks and K. Gimpel. Bridging nonlinearities and stochastic regularizers with gaussian error linear units. ArXiv preprint, 2016.
W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open graph bench- mark: Datasets for machine learning on graphs. Advances Neural Information Processing Systems (NeurIPS), 2020.
W. Hu, M. Fey, H. Ren. M. Nakata, Y. Dong, and J. Leskovec. OGB-LSC: A large-scale challenge for machine learning on graphs. Advances Neural Information Processing Systems (NeurIPS) Datasets and Benchmarks Track (Round 2), 2021.
12

---

Y. Huang, W. Lu, J. Robinson, Y. Yang, M. Zhang, S. Jegelka, and P. Li. On the stability of expressive positional encodings for graphs. In International Conference on Learning Representations (ICLR), 2024.
J. Jumper, R. Evans, and A. Pritzel. Highly accurate protein structure prediction with alphafold. Nature, 596:583-5899 2021.
J. Kim, D. Nguyen, S. Min, S. Cho, M. Lee, H. Lee, and S. Hong, Pure transformers are powerful graph learners. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
N. Kipf and M. Welling. Semi-supervised classificatiin with graph convolutional networks. In International Conference Learning Representations (ICLR), 2017.
D. Kreuzer, D. Beaini, A. Loukas, R. Urtasun, and P. Lio. Rethinking graph transformers with spectral attention. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
H. Li, M. Wang, T. Ma, S. Liu, Z. Zhang, and P.-Y. Chen. What improves the generalization of graph transformers? A theoretical dive into the self-attention and positional encoding. In Proceedings of the 4/st International Conference
Machine Learning (ICMI.) 2024.
D. Lim, J. D. Robinson, L. Zhao, T. E. Smidt, S. Sra, H. Maron, and S. Jegelka. Sign and basis invariant networks for spectral graph representation learning. In International Conference on Learning Representations (ICLR), 2023.
L. Ma, C. Lin, D. Lim, A. Romero-Soriano, K. Dokania, M. Coates, P. H.S. Torr, and S.-N. Lim. Graph Inductive Biases in Transformers without Message Passing. In International Conference on Machine Learning (ICML), 2023.
L. Ma, S. Pal, Y. Zhang, J. Zhou, Y. Zhang, and M. Coates. Ckgconv: General graph convolution with continuous kernels. In International Conference Machine Learning (ICML), 2024.
L. Markeeva, S. McLeish, B. Ibarz, W. Bounsi, O. Kozlova, A. Vitvitskyi, C. Blundell, T. Goldstein, A. Schwarzschild, and P. Velickovic. The cirs-text algorithmic reasoning language benchmark. Arxiv preprint, 2024.
H. Maron, H. Ben-Hamu, N. Shamir, and Lipman. Invariant and equivariant graph networks. In International Conference Learning Representations (ICLR), 2019a.
H. Maron, E. Fetaya, N. Segol, and Y. Lipman. On the universality of invariant networks. In International Conference on Machine Learning (ICML), 2019b.
W. Merrill and A. Sabharwal. The expressive power of transformers with chain of thought. In International Conference on Learning Representations (ICLR), 2024.
W. Merrill, A. Sabharwal, and N. A. Smith. Saturated transformers are constant-depth threshold circuits. Trans. Assoc. Comput. Linguistics, 10:843-856 2022.
C. Morris, M. Ritzert, M. Fey, W. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI Conference on Artificial Intelligence, 2019.
C. Morris, G. Rattan, and P. Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems (NeurIPS), 2020.
C. Morris, F. Frasca, N. Dym, H. Maron, i. i. Ceylan, R. Levie, D. Lim, M. M. Bronstein, M. Grohe, and S. Jegelka. Position: Future directions in the theory of graph machine learning. In International Conference on Machine Learning (ICML), 2024.
L. Müller and Morris. Aligning transformers with weisfeiler-leman. In International Conference on Machine Learning (ICML), 2024.
Müller, M. Galkin, C. Morris, and Rampásek. Attending to graph transformers. Transactions Machine Learning Research (TMLR), 2024.
13

---

L. Müller, D. Kusuma, B. Bonet, and C. Morris. Towards principled graph transformers. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein,
L. Antiga, A. Desmaison, A. Köpf, E. Z. Yang, Z. De M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, high-performance deep
learning library. Advances in Neural Information Processing Systems (NeurIPS), 2019.
O. Press, N. Smith, and M. Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. In International Conference on Learning Representations (ICLR), 2022.
Price, Gonzalz,,,,zalez, and F. e. a. Alet. Probabilistic weather forecasting with machine learning. Nature, 637:84-90, 2025.
O. Puny, D. Lim, B. T. Kiani, H. Maron, and Lipman. Equivariant polynomials for graph neural networks. In International Conference on Machine Learning (ICML), 2023.
J. Pérez, J. Marinković, and P. Barceló. On the turing completeness of modern neural network architectures. In International Conference on Learning Representations (ICLR), 2019.
M. N. Rabe and C. Staats. Self-attention does not need o(n2) memory. Arxiv preprint, 2021.
L. Rampášek, M. Galkin, V. P. Dwivedi, A. T. Luu, G. Wolf, and D. Beaini. Recipe for general, powerful, scalable graph transformer. In Advances in Neural Information Processing Systems (NeurlPS), 2022.
C. Sanford, B. Fatemi, E. Hall, A. Tsitsulin, M. Kazemi, J. Halcrow, B. Perozzi, and V. Mirrokni. Understanding transformer reasoning capabilities via graph algorithms. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
P. Shaw, J. Uszkoreit, and A. Vaswani. Self-attention with relative position representations. In Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies. Volume 2 (Short Papers), 2018.
J. Tönshoff, M. Ritzert, H. Wolf, and M. Grohe Walking out of the weisfeiler leman hierarchy: Graph learning beyond message passing. Transactions on Machine Learning Research (TMLR), 2023.
A. Tsitsulin, D. Mottin, D. Karras, E. Müller, and M. M. Bronstein. Graph transformers with spectral attention. In International Conference Learning Representations (ICLR), 2022.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Velickovic, A. P. Badia, D. Budden, R. Pascanu, Banino, M. Dashevskiy, R. Hadsell, and C. Blundell. The CLRS algorithmic reasoning benchmark. In International Conference on Machine Learning (ICML), 2022.
V. Vosylius and E. Johns. Instant policy: International Conference Learning Representations (ICLR), 2025.
In-context imitation learning via graph diffusion. In
Y. Wang and M. Zhang. An empirical study of realized GNN expressiveness. In Proceedings of the 1sst International Conference on Machine Learning (ICML), 2024.
Y. Wang, J. Lu, N. Jaitly, J. Susskind, and M. A. Bautista. Simplefold: Folding proteins simpler than you think, 2025.
B. Weisfeiler and A. Leman. The reduction of graph to canonical form and the algebra which appears therein. Mruuchno-Techichessee Informatsia, 129): 1968.
Q Wu, W. Zhao, Z. Li, D. P. Wipf, and J. Yan. Nodeformer: A scalable graph structure learning transformer for node classification. Advances Neural Information Processing Systems (NeurIPS), 2022.
14

---

Z. Wu, S. Pan, F. Chen, G. Long. C. Zhang, and S. Y. Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Y. Xing, X. Wang, Y. Li, H. Huang, and C. Shi. Less is more: on the over-globalizing problem in graph transformers. In Forty-first International Conference on Machine Learning (ICML), 2024.
D. Xu, Y. Zhu, C. B. Choy, and L. Fei-Fei. Learning the graphical structure of scene graphs. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021.
K. Xu, W. Hu, J. Leskovec, and S. Jegglkk. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019.
C. Ying, T. Cai, Luo, Zheng, G. Ke, D. He, Y. Shen, and Liu. Do transformers really perform badly for graph representation? In Advances in Neural Information Processing Systems (NeurIPS), 2021a.
R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and Leskovee. Graph convolutional neural networks for web-scale recommender systems. In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018
Z. Ying, T. Cai, S. Luo, S. Zheng, G. Ke, D. He, Y. Shen, and T.-Y, Liu. Do transformers really perform badly for graph representation? In Advances in Neural Information Processing Systems (NeurIPS), 2021b.
B. Zhang, S. Luo, L. Wang, and D. He. Rethinking the expressive power of gnns via graph biconnectivity. In International Conference on Learning Representations (ICLR), 2023.
B. Zhang, L. Zhao, and H. Maron. On the expressive power of spectral invariant graph neural networks. In International Conference on Machine Learning (ICML), 2024.
H. Zhou, A. Nova, H. Larochelle, A. C. Courville, B. Neyshabur, and H. Sedghi. Teaching algorithmic reasoning via in-context learning. Arxiv preprint, 2022.
H. Zhou, A. Bradley, E. Littwin, N. Razin, O. Saremi, J. M. Susskind, S. Bengio, and P. Nakkiran. What algorithms can transformers learn? A study in length generalization. In International Conference on Learning Representations (ICLR), 2024a.
J. Zhou, G. Cui, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun. Graph neural networks: A review of methods and applications. Al Open, 1:57-81, 2020.
Y. Zhou, U. Alon, X. Chen, X. Wang, R. Agarwal, and Zhou. Transformers can achieve length generalization but not robustly. Arxiv preprint, 2024b.
M. Zitnik, M. Agrawal, and J. Leskovec. Modeling polypharmacy side effects with graph convolu- tional networks. In Bioinformatics, 2018
15

---

Table 3: Hyperparameters for our 16M models.
Hyperparameter
PCQ
COCO
CODE
FLOW
MST
BRIDGES
Learning rate
le-4
4e-4/3.5e-4
le-4/1.5e-4
le-4/2e-4
3e-4
2e-4/1e-4
Batch size
256
32
32
256
256
256
Optimizer
AdamW
AdamW
AdamW
AdamW
AdamW
AdamW
Grad. clip norm
Num. layers
16
16
16
16
16
Hidden dim.
384
384
384
384
384
384
Num. heads Activation
16
16
16
16
16
16
ReLU
ReLU
ReLU
ReLU
ReLU
ReLU
RWSE/RRWP Steps
32
32
16
Num eigvals/eigyecs
32
32
32
16
16
16
Hidden dim. RWSE/RRWP
768
768
768
768
768
768
Hidden dim, LPE/SPE
384
384
384
384
384
Num. layers &
2
2
2
2
Num. layers
2
2
2
2
2
GNN type p (SPF)
GIN
GIN
GIN
GIN
GIN
GIN
Edge encoder
MLP
MLP
MLP
MLP
MLP
MLP
Weight decay
0.1
0.1
0.1
0.1
0.1
0.1
Dropout
0.1
0.1
0.1
0.1
0.1
0.1
Attention dropout
0.1
0.1
0.1
0.1
0.1
0.1
#Steps
2M
1M
200k
11718
11718
11718
#Warmup steps
20k
10k
118
118
118
A
Experimental details
Here, we present hyperparameter choices, architecture design, and dataset selections for the empirical evaluation of our GT architecture.
A.1 Data sources and licenses
PCQM4MV2 available at http:://gg.....tttrrrrrr//////or under a CC
BY 4.0 license. OGB-Code2 is available at htttp:://ogt htt.::pp....taoooodddddddd/d/ooa graphprop/ #ogbg-code2 under a MIT license. The COCO-SP and PASCAL-VOC-SP
as part of the LRGB benchmark [Dwivedi et al. 2022] are available at httttps://gitthhii wwwpwhuw....//.aa/aaeae..a...eea wttp:/hwwb..oo///jaayayvveeeeldd Irgb under a CC BY 4.0 license. BREC available at pactts://gittie com Bear/GrrahPKKUBBB under MIT license. Statistics for all datasets, including the algorithmic reasoning datasets, available in 5
A.2 Hyperparameters
Table 3 and Table give overview of the hyperparameters used for models highlighted in our work. Given the large number of hyperparameters and the scale of the tasks, we did not perform grid search any other large-scale hyperparameter optimization. Nonetheless, rate for each task and model size. Across the experiments, we select the hyperparameters based on the best validation score and then evaluate on the test set. We search for suitable learning rates on the 16M models to determine which models to scale. Due to the increased computational demand, we then reduce the learning rate for the 100M models.
swept the learning
For PCQ, we the learning rate lc-4 after sweeping the learning rate over the (7c-5, le-4, 3e-4). Further, we set the learning rate for COCO to 4e-4 for iigen-ifformation- based embeddings and 3.5e-4 for RWSE after sweeping over (7e-5, 1e-4, 3e-4, 4e-4). For CODE, we reduce the learning rate to 1.5e-4 (RWSE) with the same sweep with PCQ, and across all MST runs, we keep the learning rate at 3e-4 for the 16M models, reducing the learning rate to le-4 (LPE) and 7e-5 (RWSE) for the 90M model and 7e-5 for the 160M model at MST with the same initial sweep for COCO. Furthermore, for FLOW, we set the learning rate to le-4 (LPE, SPE, NoPE) and 2e-4 (RWSE, RRWP), respectively. We obtain similar results for BRIDGES with le-4 (RWSE, LPE) and 2c-4
16

---

Table 4: Hyperparameters for our 90M and 160M models.
Hyperparameter
PCQ(90M)
MST(90M)
MST(160M)
Learning rate
lc-4
lc-4/7c-5
7c-5
Batch size
256
256
256
Optimizer
AdamW
AdamW
AdamW W
Grad. clip norm
1
Num. layers
24
24
24
Hidden dim.
768
768
1024
Num. heads Activation
16
16
ReLU
ReLU
ReLU
RWSE/RRWP steps
32
32
32
Num. eigvals/eigyees
32
32
32
Hidden dim. RWSE/RRWP
768
768
768
Hidden dim. LPE/SPE Num. layers ø
384
384
384
2
2
Num. layers P
2
2
2
GNN lype (SPF)
GIN
GIN
GIN
Edge encoder
MLP
MLP
MLP
Weight decay
0.1
0.1
0.1
Dropout
0.1
0.1
0.1
Atlention dropout
0.1
0.1
0.1
#Steps
2M
11718
11718
#Warmup steps
20k
118
118
Table 5: Dataset statistics.
Statistic PCQ
Coco
CODE
FLOW
MST
BRIDGES
# Graphs # Avg. Nodes
3.746M
123,286
452,741
1M
1M
1M
14.13
476.88
125.2
16/64
16/64
16/64
# Avg. Edges
14.56
3,815.08
124.2
48.1 1/213/233
31.66/209.34
48.46/
395.02
Prediction level
graph
node
graph F1
graph
edge
edge
Metric
MAE
Fl
MAE
F1
F1
(RRWP, SPE, NoPE) as the learning rate, using the initial sweep from PCQ. In addition, we evaluated each PE with (8.32) random walk steps or eigenvectors and (4,16) for algorithmic reasoning tasks. Regarding PE encoder design, we selected a simple MI. architecture with two layers where applicable. However, use the same number of layers, heads, and embedding dimensions across datasets our transformer architecture, thereby keeping the architecture unchanged. Otherwise, we follow previous literature for initial hyperparameter choices, namely the GraphGPS (Rampášek et al. 2022], GRIT [Ma et al. 2023), and Graphormer (Ying et al. 202 la] papers. We used an AdamW optimizer for each experiment with 3 0.9 and B2 0.999. Further, the learning rate scheduler uses a cosine annealing schedule with 1 % warm-up over the total number of steps. Additionally, we an LI loss for regression targets and cross-entropy loss for classification targets, except CODE, where we use the proposed loss function. In Table 6 and Table 7 we further report runtimes and memory usage of all models evaluated in work.
A.3 Architecture
In the following, we showcase the implementation of our GT architecture and the injection of PE information into the attention mechanism. We consider an Encoder, Processor, Decoder architecture with additional preprocessing for the PEs and graph-specific features.
17

---

Preprocessing First, we preprocess each dataset to include the respective eigenvalues and eigenvec- tors of the graph Laplacian and the powers of the random walk matrices. These are then applied the respective PE encoder, which is an MIP with two layers that casts the PE features to the embedding dimension. We consider transformed graphs for edge-level tasks, such as BRIDGES and MST, as a special case. In this case, the graph is converted to constitute the edge-leve graph corresponding to the original graph. Then, node features and PE features are computed on this transformed graph. For the GDT, we provide maximum context size per dataset. Tokens exceeding the context size are then removed.
Encoder The node and edge features of each dataset's graphs are then fed into linear layer, mapping them to the embedding dimension. These feature embeddings are specific to each dataset and embed graph-specific features. For CODE we consider additional preprocessing steps, as described by (Hu et al. 2021] to derive the respective graph structure. Further, we add [cls] token as it is standard practice read out graph-level representations Ying al. 2021b
Processor Following our description of the GDT architecture shown in Section 2 single layer in the GDT architecture computes the expression shown in Definition [uusing GELU as a nonlinearity. In the case of absolute PEs, they are added to the node embeddings before the initial layer; for relative PEs, they are added to the attention bias B. The GT layer then computes full multi-head scaled- dot-product attention over node-level tokens, adding B to the unnormalized attention matrix before applying softmax. We refer to Appendix [B.] for a detailed discussion. From this representation, including node and edge features, relative and absolute PEs, and the embedded graph structure, the processor computes representations of node- and graph-level features. We then stack multiple GT layers together: 12 for the 16M model and 24 for the 100M model.
Decoder After the last layer, an MLP decoder with two layers is applied to provide the prediction head of the model. Since each dataset has its prediction target, we provide a decoder for each dataset mapping the last layer output to the prediction target, where W, E Rddd and W2 E Rdxo are learnable weight matrices and is the respective output dimension for each task, i.c.,
W WaLayerNomm(GELU(M
For clarity, omit bias terms throughout this section. Each result is then passed to the respective loss function to compute the gradient step.
A.4 Algorithmic reasoning data
For our synthetic experiments, evaluate on three out-of-distribttion algorithmic reasoning tasks derived from the CLRS benchmark (Velickovic et al.) [022]. totaling 100M tokens. These tasks assess size generalization
controlled synthetic setting with randomly generated graphs. Unlike CLRS. we do not train models with intermediate algorithmic steps. Here, we describe graph generation and each algorithmic reasoning task in detail.
Graph generation We develop a heuristic graph-generation method that produces graphs with desirable problem-specific properties, such as reasonable distribution of shortest-path lengths or the number of bridges. Concretely, we begin by sampling an Erdos-Renn Renyi graph G with nodes and edge probability and denote the connected components of G with Cl...., Cm- For each E [m]] we randomly choose component C₁ with j * i. Then, we select random nodes e C₁ and C and augment G with the edge (i,j). We repeat this process times. We select parameters p and K for each task based on problem-specific characteristics. We detail these choices in the task descriptions, which we provide next.
Maximum flow In FLOw, the task to predict the maximum flow value in an edge-weighted directed graph. The task uses discrete node features indicating whether a node is the source, the sink, or neither. The task uses the flow capacity between two nodes as continuous scalar-valued edge features. FLOw is graph-level regression task.
Minimum spanning tree MST, the task is to predict the set of edges that forms the minimum spanning tree (MST) in weighteighted graph with mutually distinct edge weights, ensuring the
18

---

Table 16M//0M/160N models runtime results single step, averaged across 000 steps. Each value is given i seconds/step.
PE
#Param.
PCQ
COCO
CODE
FLOW
MST
BRIDGES
NoPE
16M
0.079
0.105
0.0921
0.071
0.096
0.072
LPE
16M
0.084
0.109
0.104
0.071
0.106
0.088
SPE
16M
0.091
0.123
0.105
0.059
0.106
0.085
RWSE
16M
0.072
0.101
0.102
0.071
0.091
0.088
RRWP
16M
0.137
0.135
0.219
0.066
0.1452
0.101
LPE
90M
0.167
0.184
RWSE
90M
0.159
0.186
LPE
160M
0.219
0.246
RWSE
160M
0.219
0.237
uniqueness of the MST. The task uses the weight of each edge as continuous scalar-valued edge features. MST is a binary edge classification task where the class label indicates whether an edge is contained within the MST.
Bridges In BRIDGES, the task is to predict the set of edges that are bridges in an undirected graph. The task does not use any node or edge features. BRIDGES a binary edge classification task where the class label indicates whether an edge is a bridge in the graph.
A.5 Runtime and memory
Here we provide additional information on the runtime and memory requirements of our GDT. We sample runtime of each experiment by running multiple steps and averaging their runtime. For memory consumption, we consider the model's ' complete forward pass and estimate the allocated memory using PyTorch's memory profiling. All computations were made using bfloat16 precision during computation. We run the experiments on single node consisting of one L40 GPU with 40GB VRAM. 12 CPU cores, and 120GB RAM for all runtime and memory computations. In case of COCO and CODE with RRWP a PE, we used 2 140 GPUs. We further note that the presented runtimes are final runtimes obtained from the selected experiments, and significantly more runtime was used to obtain the chosen hyperparameter choices. We note that the automatic compilation is performed automatically by corphecompile, improves the runtime and memory scaling significantly across all tasks.
Table shows the runtime for single step, averaged across 000 training steps obtained for each model. Timings were obtained using torch functionality. Further Table 7shows the memory requirement for 000 steps of each model. We further note the runtime speed improvements during inference experiments from Section while using FlashAttention [Dao et al. 2022).
Hardware optimizations Efficient neural network compilation is already available via CUDA implementations PyTorch and other programming languages such as Triton. We use tomplec throughout all our experiments. In addition, we want to highlight FlashA (Dao et al. 2022). available for the standard transformer, and used the GDT an example of architecture-specife hardware optimizations that can reduce runtime and memory requirements.
A.6 Comparison with state-of-the-art
While our study focuses exclusively on the GDT, we provide SOTA performance numbers for our real-world tasks to understand whether the GDT performance is competitive with the best models in the literature. Concretely, for PCQ without 3D positions, the best models typically achieve between 0.0809 and 0.0859 MAE [Chen et al. 2023 Müller et al. 2024 Ma et al., 2023 Rampášek et al.) 2022]. For COCO and PASCAL, we find models are generally evaluated on 500K parameter budget and achieve up to 43.98 and 49.12 2 FI, respectively [Chen et al. 2025 Note that we do not adhere to this budget when training COCO find it overly restrictive given the considerable size
19

---

Table 16M/90M/160M models memory requirements in MB for 1 000 steps of each model during
training.
PE
#Param.
PCQ
COCO
CODE
FLOW
MST
BRIDGES
NoPE
16M
3120.63
5117.57
9749.29
1702.69
3255.37
2456.55
LPE
16M
3221.13
5239.89
9852.71
1763.87
3401.60
2499.54
SPE
16M
3161.32
5157.65
9763.58
1730.19
3290.09
2490.0
RWSE
16M
3131.57
5147.34
9766.30
1713.27
3276.84
2474.63
RRWP
16M
5419.56
5223.77
19221.97
2253.85
5522.04
3723.31
LPE
90M
9844,48
10197.77
RWSE
90M
9659.54
9947.07
LPE
160M
13513.76
13986.39
RWSE
160M
13266.44
13647.66
of this dataset. Consequently, we also use the pre-trained 15M model when performing few-shot transfer from COCO to PASCAL.. Finally, CODE, the best models score somewhere between 19.37 CChen et al.
2022 and 22.22 F1 [Geisler et al. 2023).
A.7 BREC Evaluation
We selected RWSE and LPE as two representative PEs for the random-wall and eigen PE, respectively, We further evaluated RRWP PEs but observed training instability in both models, which we attribute to the small dataset size in BREC (only 64 samples per task). The small-scale dataset size seems to affect the relative PE RRWP more than the node-level with GDT and Graphormer-Ch GD, differing only in the attention style. Moreover, we choose 4 layers, an embedding dimension 64, 4 attention heads, and 8 random walks and eigenvalues, respectively, We generally observed training instabilities caused by the multiplicative Φ1 of Graphormer-Gii (Zhang we manually initialize the weights of 01
RWSE and IPE. Our implementation aligns
iet al., 2023). To achieve the performance seen Table 2 and Ø2 and such that Graphormer-Gi initially performs standard attention (akin to the GDT).
A.8 Scaling Results
Here, we provide additional results for scaling the GDT 90M and 160M parameters. These results correspond to the results seen in Figure
Table 8: 90M and 160M parameter results for different PEs over 2 random seeds. PCQ MAE is in miero electron volt (meV) for clarity of presentation.
PCQ (90M) MST (90M)
MST (160M) F1
PE
MAE
F1
LPE
89.7 044
92,86 + 0u.1
93.11 + oL0I
RWSE
88.9 0
94.29 00.68
95.80 00.15
RRWP
86.5
A.9
Note on Architecture Selection
By using standard quadratic attention, seen in transformers for other domains, we can leverage existing thcoretical insights and empirical improvements observed in the literature. In addition, these assumptions make our proposed architecture, theory, compatible with existing frameworks for improving training and inference resources, such FlashAttention [Dao et al.] 2022 and FlexAttention [Dong al. (2025). While GTs with linear time scaling exist, we note that quadratic attention has been successfully applied in GTs for real-world tasks, such as the works of [Abramson] al. 2024 Wang al., 2025 on protein folding and pPice al. 2025) on weather forecasting. Moreover, linear attention variants can often be understood as approximations of quadratic attention, thereby leveraging theoretical results obtained for quadratic attention GT' [Xing al., 2024 Wu
al. 2022 Choromanski et al. 2021
20

---

B Background
Here, we provide background material on various concepts and definitions used in our work.
Basic notations Let N. = {1,2. and No == N (0). The set I denotes the set of non- negative real numbers. For set X, A C X denotes the strict subset and A C X denotes the subset. For n E N. let [n] == (1...., n) C N. We use B...B to denote multisets, i.e., the generalization of sets allowing for multiple, finitely many instances for each of its elements. For two non-empty sets X and Y, let y denote the set of functions from X to Y. Given a set X and a subset A C X, define the indicator function 1A= X {0, such that a = 1 if x E A, and 1 1 otherwise. Let M be an n X m matrix, n > 0 and m > O, over R. then M,.,, J. E [n]. E [ma] are the ith row and jth column, respectively, of the matrix M. We denote with Set(M) the set of rows of M. Let N be an n X n matrix, n > O, then the trace Tr(N) = Eiein No. In what follows, O denotes an all-zero vector with an appropriate number of components.
0
Graphs An (undirected) graph G is pair (V(G), E(G)) finite sets of vertices V(G) and edges E(G) S {fu, o} - VG) u # v}. vertices or nodes V(G) and edges E(G) S {fu, v} S V(G) u + v). The order of a graph G is its number [V()) of vertices. If not stated otherwise, we set n == |V(G) and call G an n-order graph. We denote the set of all n-order (undirected) graphs by Gn and the of all (undirected) graphs up to vertices by Ggn- In a directed graph, we define E(G) C VV)), where each edge (u, v) has a direction from w to c. Given a directed graph G' and vertices u, V(G), we say that is child of if (u, v) E E(G)). A (directed) graph G is called connected if, for any u, v E V(G), there exist r E N and {uI...., ,, S V(G), such that (u, 21), (11, u2)............. (ur, v) E EGG). and analogously for undirected graphs by replacing directed edges with undirected ones. We say that graph G is disconnected if it is not connected. For graph G and an edge e E E(G), we denote by G e the graph induced by removing edge [n]. we denote its adjacency matrix if and only if [u, E E(G)). The neighborhood of a vertex v E ((G) is denoted by NG(v) == {u E V(G) {u, u) E E(G)), where we usually omit the subscript for ease of notation, and the degree of vertex v is NN(())-- A graph G is a tree connected, but G' \ e is disconnected for any e E B(G). A tree or a disjoint collection of trees is known as a forest.
from G. For an n-order graph G E 9.. assuming V(G)
by (G) f0, 1) 1m=xx, where A
A rooted tree (G,r) is a tree where specific vertex r is marked as the root. For a rooted (undirected) tree, we can define an implicit direction on all edges as pointing away from the root; thus, when we refer to the children of a vertex u in a rooted tree, we implicitly consider this directed structure.
For 5 S VGG,, the graph GiS] == (S, Es) is the subgraph induced by S, where Es == {(u. v) E
E(G) | u, E S}. A (vertex- )labeled graph is pair (G, lG) with a graph G = (V)G), E(G)) and a (vertex-)
function l:: V(G) + E, where Σ is an arbitrary countable label set. For vertex E V(G), (v( denotes its label. A Boolean (vertex- (e-reex-)ddlabeled gruph is a pair (G, (c) with a graph G = (V))),(())) and a label function Eo: VGG + {0, 1)dd We denote the set of all n-order Boolean d-labeled graphs as G An attributed graph is a pair (G, ag) with a graph G == (VVG)), E(G)) and an (vertex-)attribute function ag: VGG + Rixd for d > O. That is, unlike labeled graphs, vertex annotations may come from an uncountablc set. The attribute or feature of u E VG) is ag(v). We denote the class of all n-order graphs with d-dimensional, real-valued vertex features by GR.-
Two graphs G and H are isomorphic if there exists a bijection :o: V(G) - V(H) that preserves adjacency, i.e., (u, v) E E(G) if and only if (ę((),, p(v)) E E(H). In the case of labeled graphs we additionally require that (a(v) E (P(()) for E VG). Moreover, we call the equivalence classes induced by ~ isomorphism types and denote the isomorphism type of G by r()). A graph class is set of graphs closed under isomorphism Given two graphs G and H with disjoint vertex sets, we denote their disjoint union by GÚH.
B.1 Transformers
Here, we will introduce attention with an additive attention bias and the transformer architecture.
21

---

Definition 5 (Attention (with bias)). Let Q, K, V E Rexd and B E R with n, E N We define biased attention
Attention Q, V, B) softmax(d QK + B)V,
where softmax is applied row-wise and defined, for vector E R
exp(x11
exp(xn)
softmax(x)) = Eve(n) (xpe()))(((;))) exp(2;;
Σ exp (4))
E R=xaxh, and let Wo. WK, Wv Rddd Wo E Raxd be learnable parameters, with n, d E N Let h N be the number of heads, such that d, E N for which d = h dr. We call d,, the head dimension and define h-head attention over X
Definition 6 (Multi-head attention (with bias)). Let X E Ruxd,
MHA(X X B) = [X]
Wo.
where, for all i E [k],
= Attention ( ( XW XW V B,), Q K
with B; E Quxxn denoting the attention bias for the i-head, indexed along the third dimension of B, w(0 w (6) w E Rdxds and
Wq= = W (1)
W (h) m
WK = W w(()
W. W w(!)
Definition 7 (Two-layer MLP). Let X E Iaxd with n, d, dg E N+, where dy is the hidden dimension. We define a two-layer MLP
MLP(x) W>
where MLP is applied independently to each row æ IR 1xd in X. Here, W1 E Rdxdy is the in-projection matrix, W2 E Rd the out-prooection matrix. and or E R is an element-wise activation function such as GELU [Hendrycks and Gimpel 2016].
Definition 8 (Transformer architecture). Let X E Rnxd be a token matrix and B E R be an attention bias, with d E N+. The I. + 1-th transformer layer updates token representations X E IR ngd as
X' +-
X MHA(LayerNNorm X'), B), (AP(LayyrNorm(X')
X X'
where MLP defined in Definition
B.2
Extended notation for the theoretical analysis of the GDT
Here, we introduce some notation for the GDT that we will use in our theoretical analysis.
Learnable parameters We give an overview of all learnable parameters of the GDT Table g practice, node and edge features are typically present as integers or continuous feature vectors, and we embed them using learnable MLPs. We refer to such parameters as embedding parameters. Note that in Table 9 we exclude embedding parameters, as for simplicity, we assume in our framework that node and edge features are already embedded.
In
Let d, d,, T, h & N+ denote the number of embedding dimensions, the number of hidden dimensions, the number of layers, and the number of attention heads, respectively. Then, the number of learnable parameters (excluding embedding parameters) is given by
# params = 3d + de + dd, + d + + 3ld + 2T 2ddd,
=(3T 1) (2T 1)dd + 3d (dy + 1)h. We denote the complete set of learnable parameters in Table with (dd, dy T. h).
22

---

Table 9: Overview of learnable parameters in the GDT, excluding embedding parameters. Here, d E N+ is the embedding dimension, d, N is the hidden dimension, and T E N+ is the number of layers. The suffix xT indicates that the parameters occur in each of the T layers.
Purams.
Dims.
Module
Description
[y([el)])
1xd d
Learnable embedding for the [cls] token
ful [g[[cls].)
d
Token embeddings
Learnable emhedding for the out out-going edges from the [cls] token Learnable embedding for the in-coming edges to the [cls] token
ER(s [cls])
1 X
Wr
d
Weight matrix for the node-level PEs
x dy.dy k) 1x
MLP upplied to edge embesklings
Attention bias
Wy
Weight matrix for the relative PEs in the attention bias
We xI
d d
Query weight matrix in multi-head attention
Wx XT
d
MHA Dctestio
Key weight mutrix in multi-head attention
Wy
d
Value weight matrix multi- head attention
W;
dx
Input projection of the MLP
W2 XT
x
MLP Deiation
Output projection of the MLP
Graph transformer representations Here, we introduce some short-hand notation for graph transformer representations. Given token matrix X and attention bias B, we write (' to denote the representation of node E (()) after i transformer layers with X and B as input. Note that, since we fix an arbitrary order of the nodes, if u is the i-th node in this order, X*(v) X
B.3 Extended notation for the theoretical analysis of PEs
Here, we introduce the notations used by Zhang et al. [2024] in their paper on PE expressiveness. We adapt this notation to fit LPE [Müller and Morris| 2024| SAN [Kreuzer et al.) 2021]. and SignNet
[Lim et al.) 2023 and use it in proofs in Appendix D We introduce the notation for the color refinement algorithm and propose one for each PE. The respective algorithms for BasisNet [Lim
ct al. 2023 and SPE (Huang et al. 2024 are given by Zhang et al. [2024).
Definition 9. [Zhan et al. 2024 We call any graph invariant k-dim color mapping. The family of k-dim color mappings is denoted by Mj. Each color mapping defines an equivalence relation "'x between rooted graphs G.,, H, marking vertices and G ~x H" iff (a( XHx (v). Further, denote the family of k-dim spectral color mappings by Ma. Similar M2 the family of spectral color mappings is obtained from the color mappings acting on {(G,, A): G, G. E AM(G) where A (G) denotes the eigenvalues a matrix M.
Definition 10. [Zhang et al., 2024] A function T' mapping from Mr, to Mr, is called a color transform. We assume that all color transforms are order-preserving with respect to color mappings. Given T(x) N X. a color transform is also called color refinement, and T denotes the times composition of T. In addition, 7 is the stable color refinement obtained from T with l' the smallest integer where further iterations do not induce different partition of the underlying nodes in a graph, resulting in I' o T T Following Zhang et al. [2024] 7 is well defined.
coloring algorithm is then formed by concatenating a stable color transform T M - Mr and pooling function U: M₁-- + My.
Definition 11. We say that color mappings X1, X2 equivalent given that GO ~x1 H iff G" ~x2
H Furthermore, we say that a color mapping X1 is finer/more expressive than X2 G ~xa Ho GD ~x H" noted by 3.
Lemma 12. [Zhang et al. 2024 Let T2: MR, - Ms, and U1. U2: Mr. Mcs be color refinements. If T. and U1
3 U2 then U1 o T1 - U2 o Tzz
Lemma 13. [Zhang et al. 2024 Let Ti: MR, + Mr, and and Ms, + Mk, be color refinements
and T M2 + My be the stable refinement of Mr. Further let Un: MRs Mr, and U2 Mr. + MR, be color refinements. Then it follows. If o U2 o Tpp o U, = U, a T U, then
U2 T U1 3 T2o Un Un.
The two lemmas above provide straightforward approach to determining whether architecture A is more expressive than architecture Ag [Zhang et al. (024). To prove that A, more expressive than Ag, we show that T2 T = T holds, with T. being the color refinement of A, respectively.
23

---

Definition 14. [Zhagg et al. 2024 We define the following color refinements corresponding to the induced refinements of each algorithm. We define global pooling as providing an injective coloring of multiset using hash function. In this case, we consider the multiset over nodes in graph. Other pooling operations are defined below.
Global pooling: Define Top: M1 + Mo and X E M1 such that for graph G and a color mapping X Mj it holds:
(T)(()) = hash (xx((): V(G))).
The 1-WL refinement gives the 1-WL coloring update, generalized to all nodes in the graph rather than just neighboring graphs.
1-WL refinement: Given TWL: M1 + M1 such that for any choice of x E M1:
(w) hash(xa (kca())atpp(( u)): e V(G)
We then define one- and two-dimensional spectral pooling, which allows for pooling over distinct eigenvalues similar to the global pooling refinement.
Spectral Pooling: Define Tsp2: M2 + M1 and TSPI: Mi X M
M1 such that for E M2 and
[Xss)(X) = hash (ExG(A, u): A A")
(xs22())a[(,, v) hash (xx u, v): À A (G))).
A pooling variant without the spectrum is denoted by Tp2 and Tp1-
To allow for examination of BasisNet and SPE, consider the 2-IGN refinement. This refinement obtained from evaluating the expressiveness of 2-IGN and its basis functions as defined by Maron
et al. [2019a].
2-1GN refinement: With TiGN: M2 + M2. X M2 as any color mapping and (c) = given
v, otherwise O:
(X)o(()]a(u, hash(xo x,, u), xa xx())) xa(u, du u)),
(xa(u, w E V(G)) Exa(w, u): w V())
(x)(o,w): V(G) [xa(w,)): we VVG))
(xc(w, w V(G) (xa(w,x): w, [(G)
duv (x w V(G))), &nv (xxa(w,u): E (G)))) 8un (fxx w): w E (())))) dn (xa w, V(G)
Further, we use BasisNet pooling refinement and Siamese IGN refinement describe the BasisNet computation process.
BasisNet Pooling: Given Tep: Mg - M and x E Mg:
[Te(()) u) hash(xa(A, u, v), ux V(G)), fxo(A, u): v V(G) (xa(A, u v) v v(G) (xG(A, w): w V(G))).
Siamese IGN refinement: Given TIIA:: M + M and M [TsaAM u, v) = [xax(x(A, ; (),
We further provide additional color refinement algorithms based on the encodings introduced through- out this work: Given the initial color refinement of SAN as XsAN(A, u) = (Aı, Am, u where X; denote the eigenvalues and n the eigenvector of the graph Laplacian associated to the node Then we define the SAN color refinement alongside the existing refinements as follows:
[ = Top TENc (XSAN)
with TENc denoting the transformer encoder layer. The complete BasisNet refinement is given by the concatenation of refinements given in Definition Definition 14
TaaassNall Top TwL TsP1 Top TSiAM(XBaiss..

---

Following the definition of BasisNet as color refinement in Definition 14 and assuming a message passing GNN for p. the color refiement of SignNet using the initial SignNet color refinement XSign(A A, u, w) = (A, V4, V and To: Má - M is given by:
Tiignool Top T WL TsP2 (x(Sgg)))
where V denotes the eigenvector associated to the eigenvalue and the node u and Tg be the refinement depending on the choice of Φb. However, we note Tiax T. by definition of SignNet and BasisNet.
The refinement for the LPE encoding is given similarly to the BasisNet and SPE refinement by replacing with a color refinement that 1-WL expressive. Furthermore. we assume á to be spectral color refinement with expressiveness up 2-IGN. Common choices for include MLPs or GNNs known to be less expressive than a 2-IGN. With initial colorings XLPE u, w) = (A, V V and PE MMA - MA the refinement follows:
[TLPE(Ol Top o TWL Tsp2 T (XLPE),
where V denotes the eigenvector associated to node u.
B.4 Positional encodings
In the following, define positional encodings.
RWSE
Definition 15. Let = D- A be the random walk matrix, with D denoting the degree matrix and A the adjacency matrix of a graph G. The random walk structural encodings (RWSE) are given by:
P. = R,, R
Definition 16. Let p., be the RWSE encoding vector and F: RR Rdd a MI.P with two layers, and d denoting the encoding dimension. Then the RWSE encoding computed by F(P..) and denoted by PRW (G) for graph G with random walk length k.
RRWP
Definition 17. Let R D- with D as the diagonal degree matrix and A as the adjacency matrix, be the random walk operator, and & the maximum length the random walk. Then the relative random walk probabilities (RRWP) are defined as:
P.j R, R,, R Jag
The initial node encoding Po is then defined as RG for each node in the graph.
Definition 18 (RRWP Encoding Computation). Let be the RRWP encoding tensor and MLP R + Rdd where d denotes the encoding dimension, be a multi-layer neural network. Then the encoding MLP(PP (LP(P....) is computed element-wise by the multi-layer neural network. RRWP is then denoted by PRR (G) for graph G with random walk length k:
Spectral Attention Networks (SAN) Kreuzer et al. (202T) propose incorporating eigenvalues and cigenvectors into positional-encoding neural network. SAN encoding can be computed using row-wise neural networks by selecting the lowest eigenvalues and their associated eigenvectors.
Definition 19. Let Φ: TR + be a linear layer and p: R + R be transformer encoder layer with sum aggregation. Further V. denotes the i-th column of the eigenvector matrix V. Then the SAN encoding is defined as follows:
SAN(V, A) p((o(V(.))) (VV. A)J).
generalization of the SAN encoding is given by the LPE encoding of Müller and Morris 2024 in Definition 23
25

---

SignNet Since the computation of eigenvectors using the eigenvector decomposition is not sign invariant, and both V, and -V; are valid eigenvectors of the graph Laplacian Lim et al. [2023 propose the construction of sign-invariant encoding using eigenvector information. Considering the l smallest eigenvalues and associated eigenvectors from the eigenvalue decomposition, SignNet computes the corresponding encoding using neural network architecture.
Definition 20. Let .I.... ........ O&: : R + and p: R + be permutation equivariant neural networks from vectors to vectors. Then the SignNet encodings are computed using:
SignNer(VV - م( (Vi) + éi (-)) oR (v. + (=(-))))
Commonly, .1,... ou are selected as element-wise MLPs or DeepSets (Lim al. 2023 and p as GIN with sum aggregation and the adjacency matrix of the original graph.
BasisNet Proposed as an extension of SignNet by Lim al. 2023], BasisNet encodings provide an encoding invariant to the basis of eigenspaces obtained from the graph Laplacian. Since the orthogonal group (1) denotes sign invariance, BasisNet also incorporates sign invariance.
Definition 21. Let Vi denote the orthonormal basis of an d,-dimensional eigenspace of the graph Laplacian. Further, denotes the number of cigenspaces. Given unrestricted neural networks od.:... 62, : IR - IR, shared across the subspaces with the same dimension d, and a permutation equivariant neural network p: R IR BasisNet encodings are computed the following:
BasisNet( (V) = p(los, (V 6a, (VVV)))).
Implementation wise Lim et al. 2023 propose 2-IGNs [Maron al. 2019a for od, and FFN with sum aggregation for p. They note that neural networks could be replaced with k-IGNs; however, they deemed it infeasible for efficient computation. This reduces the computation to the following
with p: IR R and IGNa, R= R denoting an IGN from matrices vectors:
BasisNet(V) = FIN(, (V1V7) IGNa, (VVV"))..
SPE Following notation from |Huang al. [024], the SPE encoding is computed using the smallest eigenvalues and associated eigenvectors obtained from an eigenvalue decomposition. With sufficient conditions for neural networks Φ1, .... ob and p. SPE stable with respect to the graph Laplacian.
Definition 22. Given .1... Lipschitz continuous, permutation equivariant neural network. Then the SPE encoding is computed by:
Φb: TR R Lipschitz continuous, equivariant FFNs and p: IR IR
SPE(V, A) divg ... Vdiagó (*)) with .1.... d& and p applied row wise. Further, we denote the SPE embedding on graph G by PSPE
Commonly, is considered an clement-wise MLP, and p is GIN using the adjacency matrix of the original graph. HHang et al. [0044] propose to split tensor
= V (a))
(di) E gxxxxi
into n matrices of shape n x which are then passed into the GIN p and aggregated using sum aggregation into single x d matrix.
LPE Initially introduced by Kreuzer et al. [021] and generalized by Müller and Morris (2024).
the LPE encodings are computed similarly to the previously introduced SPE encodings. Instead of using the eigenvector matrix V E Raax each i-th column consisting of one eigenvector denoted by V. E R is used.
Definition 23, Let Φ: R - R be row-wise applied FFN and p: ER - permutation equivariant network. Furthermore, é E R denotes a learnable parameter. Then the LPE are given by:
LPE(V, A) P(((VV - c), o(V X +)))
Setting = 0 reduces the LPE to the encoding provided by Kreuzer et al. (2021). As proposed by Müller and Morris [2024) p sums the input tensor concerning its first dimension and applies an FFN. In contrast to the SAN encoding, transformer encoder is used to compute the encoding. Similar to previous embeddings, we denote LPE embeddings for graph by PLPE with & as the number of eigenvalues used.
26

---

C Proving that the GDT can simulate the GD-WL
Here, we prove Theorem Concretely, formally state and prove both statements in Theorem 1 Appendix C.T and Appendix C.2 respectively.
C.1
Lower-bound on the expressivity of the GDT
Here, we prove that we can compute the GD-WL Zhang et al. 2023 with the GDT, our GT defined in Section 2 Concretely, given graph = EG) recall from Section 2.3 the GD-WL as updating the color (G) of node E V(G),
(w) = hash (da(v, w)), (w))
(w)
V(G))),
where de is a distance between nodes in G and hash is an injective map. In the transformer, we will represent node colors as one-hot vectors of some arbitrary but fixed dimension d. Furthermore, we will incorporate pairwise distances through the attention bias. We then show that a single GT layer compute the color update in Equation (T). We demonstrate this result by leveraging specific properties of softmax attention. For notational convenience, we will denote with X E (0. 1) bxd the one-hot color matrix of the GD-WL after iterations.
We begin by stating our main result. Afterwards, we develop our proof techniques and prove the result.
Stating the main result We will formally state our theorem, showing that our GT can simulate the GD-WL. Afterwards, we give an overview of the proof, including the key challenges and ideas.
Theorem 24. Let G (V(G), E(G)) be graph with N nodes and node distance function da V(G)² + Q Lei d h E N denote the number of embedding dimensions, the number of hidden dimensions, the number of layers, and the number of attention heads, respectively. Let == n++1 and let X LRd and B LL be initial token embeddings and attention bias constructed according to Section 2 using node distance dG. Then, there exist weights for the parameters in (dd, dj. T. h) such that X = X',for all t 2 0, an arbitrary but fixed hash, and using dg as the distance function.
Proof overview The central problem we face when proving the above theorem is how to injectively encode the multisets in Equation (1) with softmax-attention This is because e computes a weighted mean, whereas existing results for encoding multisets use sums (Xu et al. 2019 Morris al., 2019 Zhang al. 2023 Because these multisets are at the core of proof,
formally introduce them here.
Definition 25 restance-paired multisets). Given graph G E(G)) with E N+ nodes and let L == n + 1, for each token v E V(G) U [cls]], }. we construct a vector e E Q1xL from the distances of to tokens in V(G) U { [[cls]] }. such that
0; == w)),
where wy VGG, for i [n], is the i-th token in an arbitrary but fixed ordering of nodes in V(G) and wy is the [cls] token. We fix the distance of [cls] to all tokens as meX do(v, +1.
We represent node colors one-hot vectors and stack them into matrix X E {0, 1] with E N+ and where XL, representing the color of the [cls] token, receives special color, not used by any node. We then write the distance saaance--piredd multiset in Equation (I as
[u]x = (w;,, X;) x))B BEEL)-
We can then restate the update of token E V(G) U [[cis]} by the GD-WL as
XG
+ (b) = hash ([))x.))
(3)
For notational convenience, for every æ E set(X), we define A(x) = E E [L] X, = x} as the set of token indices with token representation æ. Further, write
[w] = uu i A(x)
and
[w),,== = {v + wy E [w]=,] E [Z]]. again for notational convenience, where w QixL is the distance vector corresponding to another node E VGG) U [[cls]].
27

---

Recall that we introduced the distance function de into the attention via the attention bias B. Now, to injectively encode distance- paired multisets, we want prove that there exists weights Wq, WK. Wv such that for two tokens v, w E V(G) U {[cls] with corresponding distance vectors v, w,
softmax X (x) (XXWk) + u = softmax [ (w) Wx(XWx)" wVXWV.
and only if [u]x = [w]x Note that for simplicity, we omit the scaling factor in the attention and that we wrote and to indicate the corresponding row of B for tokens and w, respectively. We will now simplify, by setting We = WK- = 0 and Wv = and arrive at the condition
softmax(v) X softmax (w) X < [e]x x - [w]xx
Here, we prove the above holds under mild conditions in the following lemma. Note that we split up the forward and backward directions of the lemma, as we will use different proof strategies for each direction.
Lxd be matrix whose rows are one-hot vectors, for some L, d E N+ Further, we require X to have at least two distinct rows. Then,
Lemma 26. Let u, w QIxL with max; V; max, w; and let X E [0, 13
softmax(1) v) X softmax(w) ( = >>]e = =w)]x
(4)
and
softmax(v) X softmax(w) = [b) x = [ux]
(5)
As mentioned above, we will treat the forward and backward directions differently. The backward
direction is fairly straightforward, seeing that softmax(1) (v) X is function over [e]x. For the forward
direction, the idea is first to notice that the condition [v]xx [w] x on the right side of Equation (4)
is equivalent to comparing the multiset of distances paired with each distinct one-hot vector in X
independently, as distinct one-hot vectors do not have common non-7ero channels; see the following lemma for precise statement of this property and see Appendix F for the proof.
Lemma 27. Let v. w QIXL and let X E {0,1) Lx be matrix whose rows are one-hol vectors, for some L, d E N Then, [u]x (w] x. if, and only if. for every æ E X)). [w] = [w)
To understand the implication of this result in the context of proving Lemma 26 the left side of Equation 4 as follows.
let us first rearrange
Lemma 28. Let v, w 1x and let X E {0, 13 be matrix whose rows are one-hot vectors, for some L, d N+. Then, softmax( ()) softmax( w)), X, if and only if. for every æ E set(
Σ (())
(a. 3:) 0,
where 0g = softmax(u); and 3, == softmax(w);
Lemma 28 and Lemma 27 can be seen as complementary decompositions of the left and right side of Equation (4) for each unique one-hot vector in X, As a result, we can restate Lemma [6]as as follows.
Lemma 29 (Decomposed Lemma 26). Let v, w E Q1xL with max; U, = .max, w; and let X e {0, 1 be a matrix whose rows one-hot vectors, for some L, E N Further, require X to have at least two distinct rows. Then,
Σ (a: (() =EA(xx)
3:)== =0 = |0] [w]
(6)
for all x set({ X), where a; := softmax( and 3, = softmax(w); and softmax(v) v) X softmax( w) X = [u]x [w]xx
(7)
To prove Lemma 29 we leverage a known result about exponential numbers (as used within softmax)
from transcendental number theory, namely that set of exponential numbers with distinct rational coefficients is linearly independent, also known as the Lindemann-Weiersee To understand intuitively how this theorem is used, let us assume for simplicity that the softmax is unnormalized, meaning that we can write the left side of Equation (6) as
theorem [Baker] 1990).
Σ
(exp(v,)= exp(w.)) 0.
(E)(
With the help of the Seattemmann-eeesstern theorem, we obtain the following claim, which we prove in Appendix E
28

---

Claim 30. Let A, B C Q be finite multisets with |A| = |B]. Then, the sum
Σ REA
exp(a)
Σ cxp(b) 0,
if, and only if, A = B.
Hence, with the unnormalized softmax, the left side of Equation (6) holds if and only if [v] |w]m- However, the full softmax also introduces normalization, which we denote with Zo _k=1 exp(Uk)
and Zz Ek=1 exp(wk), respectively. As result, we have the condition
Σ (x)(
(at - 3.) =
(8)
Σ ie (=))
Zn exp(o:) 1 exp(wx:)
ZB
Σ exp(v:)
23 eep((xi) (wi) Za =0
(10)
Zg
(E)(m)
+
Σ
exp(v:) Zz - exp(w:) . Ba
(11)
(E)(
Σ
exp(u, + ww) - exp(w: + +xa) = =0.
(12)
(EA(2) k=1
exp(U, + w)) - Σ
exp(wr + vi) = 0.
(13)
(a)) k=1
JEA(z) 1=1
Note that the multiset of exponents in the positive exponentials is (m) and the set of exponents in the negative exponentials is [w),,v- Using Claim 30 follows.
we can now restate Lemma 29 once more as
Lemma 31 (Multi-set only version of Lemma 29 Let E Qixh with max, max; w; and lei X E {0, 1) a matrix whose rows are one-hot vectors, for some I,, d E N+ Further, we require X to have at least two distinct rows. Then,
[w]a, [w]z,e = [b] [W]er
(14)
for all set(X) and
softmax(v) X = softmax( w) X [v]x = [w]xx.
(15)
We will give the full proof with all details in this section.
First, we will review some number theory background, formally state the Lindemann-Weierstrass theorem and its implications and then give the proof of Lemma 31 Using Lemma and in particular, the equivalent Lemma 26 finally prove Theorem 24
Number theory We will formally introduce the necessary background on number theory and the theorem. A number is algebraic if it is the root of a non-zero single-variable polynomial with finite degree and rational coefficients. For example, all rational numbers with a, E N are algebraic, as they are the roots of the polynomial ax - with integer coefficients. On the other hand, number is transcendental if and only if it is not algebraic. For example, is known that exp(a) is transcendental a is algebraic and non-zero. This last fact follows from the Winderaa--Weiersrrass theorem, which we state next [Baker 1990
Theorem 32 (Baker 1990], Theorem 1.4). Let ai.... On be distinct algebraic numbers. Then, exp(ai), (op(ai),.... ...., exp((.. (nn) are linearly independent with algebraic rational coefficients.
Here, we will use the fact that attention uses the exp function in the softmax and use Theorem 32 to compute injective representations of the GD-WI. multisets by expressing them as sums of exponential numbers.
29

---

Proving Lemma 26
We now prove Lemma 31 equivalent to Lemma 26
Lemma 33 (Proof of Lemma 31). Let w E QixL with max, U; max; w; and let X E {0, 1) 1 be a matrix whose rows are one-hot vectors, for some E N Further, we require X to have at least two distinct rows. Then,
[M]a, [w]z,. [0]a = |w]ar
for all a E set( X) and
softmax(w) X softmax(w)) - [w]x = [w]]x.
Proof. Note that by assumption X has at least two distinct rows and hence, A(x) C [L]. As result, the forward implication follows from the following claim.
Claim 34. For æ E set( X), if max; v; max; wi and Aax) C [x]]. then, [m|a,, (u))are 7 (
Proof. Let == max; v; max, w, We begin by sorting the entries in [v]a and [w]a in descending order, obtaining sorted vectors v* and w". By assumption, we have that ví wi = K. Now, let i E [[[ be the smallest number for which vf * w. If no such exists, then [v] [w]] Otherwise, without loss of generality, we assume that u. > w. We now show that then, the sum of + K appears least once more in w than in [w] a,v-
First, note that there cannot exist some j for which wz + K oo. + K. Second, for each
j < i, n3 = unz, meaning that for each such j where vj + of + K appears in [v) w + K = V.- + K appears in [w]=,.-
Hence, D.- + K appears least once more in [v) le than in [wm] le implying [w]a,, w * [w] w. As result, we have that [v] = [w]a V [w] # [w] which is logically equivalent to [w]æ, [w]2,0 [0] = [w].- This shows the statement.
To see why in Claim 34 is important that A(x) a strict subset of [ni], we note that A(x) = [M]]
implies [m] = w m.us irrespective of whether [w] [w) Notably, the proof holds if there exists at least one E [4] A(æ), irrespective whether v, = w..
The backward direction follows directly from the fact that softmax(v) and softmax(w) are functions over [u]xx and tw]xx. respectively.
Together with Claim 34 this shows the statement.
Proving the GD-WL simulation result Now that Lemma 26 has been proven, we will prove the main result, Theorem
next.
Theorem 35 (Proof of Theorem 24 Let (V(G), E(G) be graph with E N+ nodes and
node distance function da V(G - Q Let d, d,, E N+ denote the number of embedding dimensions, the number of hidden dimensions, the number of layers, and the number of atlention L be initial token
heads, respectively. Let L := n and let X gLxd and embeddings and attention bias constructed according to Section 2 using node distance dg. Then, there exist weights for the parameters in Old, dj, T, h) such that X = X', for all 2 0, an arbitrary but fixed hash, and using de as the distance function.
Proof. Note that the GD-WL producess finite number of colors at each iteration, and B is constructed from de whose co-domain is compact for graphs with finite size. Hence, since each transformer layer a composition of continuous functions, the domain of each transformer layer is compact. Recall that we want to show that the t-th transformer layer can simulate
X (v) hash((u)
for all V(G) U [[cls]], where X E {0. 10.1Lxx x is a one-hot color matrix of the GD-WI. colors iteration I. Let o arbitrary but fixed. We say that v is the i-th node an arbitrary but fixed ordering of V (G).
30

---

We restate the transformer layer definition in a simplified form, omitting multiple heads, residual streams, and LayerNorm. In particular, we state that the layer updates only the i-th row of the token matrix.
( ( MLP(softmax( (X ( X W +
(vv)
where recall that the i-th row of B is We set We Wx to all-zeros and Wy to the identity matrix and obtain
MLP(softmax( v) )
We prove the statement by induction over For the base case O, the token matrix X contains the one-hot colors of the nodes in ((G) as well as the special one-hot color of the [cls] token. Setting X = X, we have that X {0, (0.d know that X has at least two distinct rows.
Lxd and X X Further, due the [cls] token,
Finally, note that, by construction, for each pair of distance vectors max, v = max; W; max,, de (v, w) + 1 and that every distance vector Qxxx, These two conditions hold throughout the induction and we will use them the induction step to apply Lemma 26
In the induction step for t >> O, we assume that
1. X 10,1)xxd
2. X X
3. X has at least two distinct rows
We want to prove that the same holds for t + Let v, w E ([cGs( be arbitrary but fixed. Note that x (x) = x++(w) if and only if [v]
[w]xt. By the induction hypothesis, we have that [ø]x* = [w]x if and only if [w]x+ = [w]x+ x Further, by Lemma 26 we have that
softmax( v) softmax(w)Xx (w) = [e] x [w)x
and as a consequence,
softmax(v) X softmax(w) X
+ (t) x++
Hence, there exists an injective function f' that maps, for each token v E V(G) U [[cls]) with distance vector the vector softmax(r) X ' to one-hot vector of (v) with d dimensions. Since the domain of the 1-th transformer layer is compact, f is continuous. Hence, by universal function approximation, there exist weights of the MLP such that, for each E V(G) U [[cis]]. 1++ a one-hot vector x ++1 (u). As a result,
1. X ++1 E 10x1
2. X H+1 = X
3. X has at least two distinct rows.
This completes the induction and proves the statement.
C.2 Upper-bound on expressivity of the GDT
Moreover, we can prove an upper bound on the expressivity of the GDT using technique adapted from Müller et al. 22024. We begin by showing the following result.
Lemma 36. Let G == EGG),v Ev) be a graph with n nodes and without edge embeddings, let We, WK. Wv Rddd be arbitary but fixed weight matrices with E N+, and let Quxa be an attention bias. Let
(X,U) = X XWR, XWv, W.v,B. B).
There exists a distance finnttioo de over U(G)U and functions f, with
((X:) h(((da(i,)) xx))
such that for all X and all i, axx (); f(X)).
31

---

Proof. We define de with have co- co-domain Q2 such that
do(i, [B,,, ((==))]
for i,j E V(G) ([els]) where [-] the concatenation operation and T(i = -) the indicator function. We denote with (o the k-th element in j)( for k E (1,2). Let
g X2) = exp(X, (xxx
We choose h as follows. We note that by definition, 1 = da () da(i,j)2 for all + j. Hence, can decompose its input into three arguments:
1. X,, identified from the tuple (do(i.)), where d(i,j)2 1, i.e.,, i=
2. the multiset of distances (d.
3. the multiset of vectors {X,}
Then, h computes
Way == exp(o(X,; do(i,
and
Wij
Kaj == Σn Wik
for all i,j. Finally, h computes
Σ wij X, Wv, XW,,
for all i, to obtain a aX, (X,
Intuitively, the above lemma shows that biased attention can be written as a function over the multiset in the GD-WL if the distance function is metric. We use this result show that the GD-WL is at least as expressive as a GDT with relative PEs.
Proposition 37. Let G = (V(G), lv) be a graph without edge embeddings and let B E Quxx" be an attention bias. Let dddd,,Thhh Th N denote the number of embedding dimensions, the number of hidden dimensions, the number of layers. and the number of attention heads, respectively. For any choice of parameters (dd, dy; T, for the GDT, there exists distance function de over (G) J { [cls]] and hash function hash for the GD-WL. such that for all 2 and all pairs of nodes i.J E VG),, (i) = x²() if and only if X X
Proof. We prove the statement by induction over t. For t = O, the statement holds by definition, as the initial token embeddings X without any absolute PE are simply the node embeddings vv and the initial colors of the GD-WL are chosen to be consistent with the node embeddings εv. For >
we assume by the induction hypothesis that for all pairs of nodes i E V(G),, 2 -x) if
and only if X
1-1 X By definition, X is computed via Equation ( namely
X MLP (Attentenn X WW X'-LWK, ' -v, B)),
where the MLP is applied row-wise. Let
1. f denote the function in Lemma 36 consistent with projections We, WK, Wy and atten- tion bias B.
2. onehot: [n] {0, 1)"h denote the function that maps numbers 1...., to their correspond- ing n-dimensional one-hot vector.
Then, for all i, we have that
MLP o f onehot(x 1-1 MLP (n
if and only if
x
=
Finally, there are at most n distinct rows X Let h be a function that injectively maps each unique row in X to a color in [n). We choose hash = h MLP f onehot, and have that, for all pairs of
nodes i.j E (G), x (i) = x)) if and only if X X This completes the induction and hence concludes the proof.
D
32

---

C.3 Expressivity of the GDT
Together, Theorem 24 and Proposition 37 correspond to the first and second statements in Theorem [] respectively, A consequence of Theorem 24 the fact that the GDT with NoPE is equivalent to the 1-WL. In particular, let G == (V(G), ev, (v, be a graph with n nodes. Let (e, w) := 1, for all v, E V(G), where 1 is the vector containing 1 in every element. Further, let (,( v) == 2, for all E V(G), where 2 the vector containing 2 in every element. Then, the GDT with NoPE equivalent, according to Theorem 24 to the following update of the GD-WL:
Xx(()) ++1 (v) = hash {f (d (x)))) w E V(G) XG
where du v) 2, da(e, w) = 1 if (u, E EG)), and do(e, w) = 0, else, for all v, w E V(G). This can be equivalently written as
XG (v) hash(())((),, lxc((w): : E No(v)
giving the 1-WL update rule.
D Proofs of Section 3
To guide our proofs of Section 3 we introduce CSL-graphs, obtaining the fact that RWSE cannot distinguish all of these graphs. These results are then expanded to provide an introduction to Theorem
2 We first present the result and proof of Theorem [ using a simplified version that minimizes the number of random walk steps, leveraging results from Tönshoff et al.) (2023). In addition, the proofs Proposition and Proposition 47 are then given with additional details on the expressiveness hierarchy obtained from the definition of each PE. We provide additional incremental results for our selection of PEs, complementing those from Section 3
Warm-up: CSL graphs We begin by introducing class of simple and intuitive, yet not 1-WL distinguishable graphs, so-called CSL graphs. These graphs consist of an n-node cycle with skip connections of length k, originating from each node. CSL graphs are canonical example of graph class requiring a distance measure, motivating additional PEs [Rampášek et al. 2022 Müller et al.) 2024). Here, we show that they cannot be fully distinguished by RWSE and provide guidance on how to find pairs of CSL graphs indistinguishable by RWSE. We first introduce CSL graphs G(n,k) and their properties to prove the following results.
Definition 38. Let n, k be natural numbers and k < n - 1. ((,.)) defines an undirected graph which is 4-regular. The set of nodes is given by ((G
{o..... . - 1}. A two-step process gives the edges. First, to construct a cycle in the CSL graph, every edge { + 13 E ((.()))) for j E {O...., n - 2}. Additionally {n 1, 0} E ((, holds. Furthermore, the skip links are introduced by defining the sequence $1 and 8 (st + k) mod and deriving the edges with {s, 81+13 E (GG(n)))
In addition, we introduce the notation used throughout the following proofs. Considering the skip links introduced in the CSL graphs we denote such a skip link by the mapping s* (V)(()))) - VG (n.)) with s(v;)= = (((+k) mod for nodes (uI...., }. A traversal to the next node 0,+1 or 1 from node U/ is denoted by s' and s -1 respectively. We further provide specific random walks using a tuple of the visited nodes in graph.
Proposition 39. Two CSL graphs (()),k)) and H ((2.k))) with n1 n2 non isomorphic if kr, K2 are co-prime natural numbers.
Given the definition of CSL graphs, it is possible derive isomorphism results for them. Furthermore, we note that CSL graphs are 1-WL indistinguishable but can be distinguished by various WL. variants, such GD-WI. (Zhang al. 2023].
Proposition 40. There exists at least one pair of CSL graphss that RWSE cannot distinguish for any choice of random walk length.
Nonetheless, we note that the expressive power of RWSE is sufficient to distinguish many 1-WL indistinguishable graphs; for example, most CSL graphs can already be characterized by RWSE. Furthermore, a minimum step number is given depending on the skip length of each CSL graph.
33

---

Figure 5: A pair of CSL graphs G10,2, H1,33 We note that the path marked in blue does not exist in graph G or has no replacement path.
Proposition 41. Let n E N+ with n > k:kk + 1) + +1. RWSE can distinguish any pair of CSL graphs with nodes and skip length k, k + 1, with random walk length of k
With Definition 38 we derive the proofs for each lemma individually.
For Proposition 41 we consider a subclass of CSL graphs. The minimum node number is specifically chosen to prevent a random walk of steps from completing a cycle in the graph, even when using sh+1 for each step. We follow a two-step process for the proof: First, we gather paths existing one graph but not the other. Then, second step, we show that all different paths of length at most & exist in both graphs. Further, we highlight that for random walks of length less than k. the paths are equal in both graphs.
Proof of Proposition 41
Proof. Let G (n.)) and ((..++1) be two CSL graphs with skip link mappings & and s Further let n > k(k + 1) + 1. To distinguish them, we denote the same node in both graphs with uo and wg. Then, for ls random walk steps, first examine whether there exist paths in G(r,k) which present in H H(n,k+1)- These include (No..... 1 Up) and (vo,.... (oo.-...Uu-R+> un) valid paths in G(m.k). which provide two step walks with one skip link each. However, we note that such paths are not possible in H (1) the skip link * has a length k + 1 and therefore no corresponding walk exists. addition, we show that there exists no other walk in H(n,--1). which is not present in ((, For this, we must consider the cases of k even or odd.
Case I: k is even: In this case, we must consider all combinations of skip links and s² s functions. Since we assume an even number of steps, know that all return walks with even number of skip links or no skip links exist in both graphs. However, walks with an uneven number of skip links cannot return to up or Wo. with the skip link size of k k 1, no return walks with at most steps exist. As can be seen, the skip length does not influence the existence of any of the proposed walks; therefore, they exist both in (m,,)) and H (n,
Case 2: k is uneven: Given an uneven k we conclude that no return walks with a length of exist since steps return neither skip link nor an uneven number of any combination of skip links and steps can return to the origin node.
For step numbers lower than & the same cases apply in permuted order, depending on the step number. Also, due to the minimal n chosen, no instances exist where circumference of the graph circle occurs in any combination of steps. As for both cases, there exist paths which are not present in G(,,)). it follows that there exist additional walks for G( which do not occur in H(n,++)) Due to the structure of CSL graphs, the number of random walks, including both returning and non-returning random walks, is the same across all nodes in both graphs, resulting in the statement of Proposition 41
Since the RWPE encoding is different if a single step returns a different return walk probability, RWPE can distinguish ((,,)): H(nk+1)) with the given random walk steps.
For the following pair of CSL graphs, we consider the computation of the number of returning walks. This enables us to compute the random walk probabilities for single node directly. Due to the design
34

---

of CSL graphs, each node in graph has the same random walk return probability, thereby allowing us derive the proof of Proposition 40
We consider two CSL graphs G(L1,)) and H(1.,)). With the computation of the number of returning walks of length r, W given by W = =E XG. where X, denotes the eigenvalues of the adjacency matrix, we can compute the number of returning walks for each node in both graphs, since due to the graph structure the number of returning walks is equal for each node. Furthermore, we know that the number of total walks is equal in both graphs, given the graph structure seen in Figure 5 From this, compute the fraction of returning walks of varying length r for each node, resulting in the computation of the RWSE embedding. Since both the number of returning walks and the total number of walks are equal for each node in both graphs,
Proof of Proposition 40
in the we receive the same RWSE embedding for G(11,3) and H(11,4).
proof of Proposition
In addition to the indistinguishability results obtained for RWSE, we propose a result that initially distinguishes RWSE from RRWP. We then refine this result in Proposition 42, showcasing RRWP to be strictly more expressive than RWSE.
Proposition 42. RRWP can distinguish all pairs of non-isomorphic CSL. graphs.
In contrast to RWSE, the RRWP embedding uses the full random walk matrix and information about random walks between any two nodes. Because of this, RRWP can capture information that is not visible to RWSE due to the restriction to the diagonal of the random walk matrix.
Proof of Proposition 42
Proof. We consider two arbitrary CSL graphs ((.. and Hins) with i co-prime and i + j. Then we can compute the RRWP encoding for each node by computing the random walk matrix. We saw from previous CSL graphs that the random walk matrix diagonal can be equal for both graphs, depending on the choice of j. and the number of random walk steps. However, for RRWP, we also consider non-diagonal elements. Due to * j. the RRWP tensor elements differ for each random walk of length 1, since different nodes are connected. Given any injective MLP layer, different RRWP tensor elements result in different RRWP embeddings for the nodes of both graphs, allowing the CSL graphs to be distinguished by RRWP.
Li
Using the above results for CSL graphs, we derive a first bound for RWSE that depends on the graph structure of the CSL graphs. However, CSL graphs are not distinguishable by 1-WL, leaving open the comparison between RWSE and 1-WL. In the following, we want to further improve our understanding of RWSE and its expressiveness. We first provide an introduction and intermediate result given by Lemma to limit the expressiveness to random walks of sufficient length. Afterwards, we provide the proof of Theorem 2 concluding our examination of RWSE.
Introduction to Theorem To prove Theorem 2, we first provide an intermediate result from leveraging the graphs introduced by Tönshoff et al. [2023] for their work. This allows us to derive graphs that need a certain number of random walk steps, depending on their graph structure. We then expand on this concept in our proof of Theorem by giving an example of graphs not distinguishable by RWSE.
Lemma 43. There exists at least one pair of non-isomorphic graphs with order 3n 1 that can be distinguished by RWSE only with a random walk length of least O(n).
Since RWSE requires returning random walks to construct the respective embedding, graphs exist that are only distinguishable by random walks of specific length. However, we want to provide a class of graphs requiring at least (nn) steps. Furthermore, we want these graphs to be 1-WL distinguishable, providing a first step to Theorem [ where we show the indistinguishabiiity of RWSE and 1-WL. Following Tönshoff et al. [023) and their evaluation of another random bask- GNN architecture (CraWL), we adapt their counterexample to our evaluation of RWSE.
Proof. We provide proof by giving a constructed graph only distinguishable by random walks of length greater than v 1, fulfilling the necessary condition of O(n) for the walk length. Following Tönshoff et al. (2023) with their counterexample for the Cra algorithm, we adapt the corresponding graphs for the RWSE embedding. Since we only consider the return probabilities of random walks
35

---

Figure 6: A pair of graphs from the construction method provided by Tönshoff al. [2023]. Note that these graphs can only be distinguished by a returning random walk length O(n) while being 1-WL distinguishable.
in the RWSE embedding, disregard information from other random walks. Given the graphs in Figure 6 with n nodes, we consider the blue marked nodes. Since the returning walks are the same for both nodes for any walk of length r S 1, the graphs cannot be distinguished for any RWSE embedding with a walk length of r. Due to the graph construction, the corresponding walks for all other nodes the same in both graphs. However, due the cycle colored in blue, the return walk probabilities differ in both graphs for walks with a length r' 2 This results in pair of graphs only distinguishable by random walks of length at least n. Results from Tönshoff al. [2023 allow for constructing further examples with nodes and order 3n 1. By construction, these graphs are distinguishable by 1-WL Tönshoff et al. 2023 resulting in the stated lemma.
we can now expand the set of graphs not distinguishable by RWSE, while 1-WL distinguishable. Combining both results, we can determine expressiveness of RWSE and further investigate the expressive power of random walks.
With the results from Lemma 433
graphs limiting the
We provide example pair of trees not distinguishable by the RWSE encoding. In contrast, all trees are known to be distinguishable by the 1-WL algorithm (Cai et al 1992]. Combining the findings from Theorem with the CSL graph results in Proposition 41 follows that RWSE embeddings incomparable to the 1-WL color refinement algorithm.
Proof of Theorem 2 For this proof, we first consider a pair of trees shown by Cvetkovid [988].
Originally introduced examples of trees with differing eigenvalues and graph angles, thereby distinguishable by the EA-iivariant, these graphs are not distinguishable by the RWSE embedding for arbitrary number of random walk steps. The proof is split into multiple steps, containing parts of both trees that need to be considered.
Proof. We separate the graph as shown in figure into backbones I, and subtrees X, Y1, Y2 and the original tree G. X stays the same throughout both graphs. whereas Y1, Y2 change their edges connecting them to the graph. In the first step, we consider the probability of returning one of the backbone nodes. Going from either of the backbone nodes to the original tree G has probability of
Figure pair of trees given by Cvetković 1988 The grey node denotes an arbitrary tree concatenated to the existing tree. Each part of the tree is colored according to its respective appearance. We further label both backbone nodes in orange, denoting the left backbone node with / and the right backbone node with J.
36

---

Furthermore, going to X from either backbone node has the probability Once in either part of X, the return probability to the backbone node is given by px. which is equal in both graphs. Finally, the probability of going to Y1, Y2 is denoted by PY,PY,, respectively, again equal for both graphs. Further, the return probabilities Y1 and Y2 are equal, as can be easily seen from the combination of Y1 and Y2 with the respective backbone node. This allows for complete evaluation of the backbone nodes, assigning them probabilities pr and p..
Secondly, we consider random walks on the nodes of the subtree X, without returning to either backbone node. Since X equal in both graphs, the return probabilities are also the same, denoted by x. However, they differ from the return probabilities in Y1 and Y2, given by y1 and y2 respectively. As result, RWSE can distinguish X, Y1, Y2 without connecting to the backbone nodes.
Combining our previous knowledge, we now consider return probabilities for nodes in V1 and V2 without restricting ourselves to the subtrees. We know that the probability of walking towards the backbone node is given by the respective position of each node in Y1, Y2, equal in both trees. Once the random walk arrives either backbone node, the probability return to said backbone given by either pJ or PJ and a probability of L to return to the originating subgraph. As ps and P.J are equal in both graphs and pY,,PY, are equal, it follows that the return probability for nodes y/1 Y1 is equal across both graphs, denoted by PvrT- The same holds for Y2 with the return probabilities denoted by PyrT-
Finally, for both graphs, the nodes are assigned the RWSE probability vectors Pls PJ once, Px 17 times, and Py: T. PyrT 8 times each. Furthermore, the two backhone nodes of both graphs cannot be distinguished using the RWSE embedding. Therefore, the graphs are equal under RWSE, however as shown by (Cai et al. 1992] every pair of trees can be distinguished using the 1-WL test, resulting in the incomparability of RWSE and the 1-WL test.
Combining the results of Proposition 40
Lemma 43 and Theorem obtain fine- tree-grained observa-
tions of graph structures not distinguishable by RWSE. While random walks are sufficiently robust to distinguish many common graph structures and graphs not distinguishable by 1-WI., RWSE still fails to distinguish specific trees and graphs originally proposed by TTöshooff et al. (2023).
In the following, we provide proof's supplementing the theoretical expressiveness hierarchy introduced by Zhang et al. [2024] and Black et al. [2024). We first give an intermediate result relating RWSE and RRWP, thereby providing a lower bound for RRWP and an upper bound for RWSE. Further, we propose adapted results for LPE and SPE, comparing them to other PEs and to each other. The significant results are shown in Proposition] and Proposition
4
The proof of Proposition is is given by simply evaluating the corresponding embeddings for both RWSE and RRWP. Since both embeddings use the same MLP encoder layer, we restrict ourselves to evaluating random walk matrices directly. We first state an extended version of Proposition and provide a proof.
Proof of Proposition 3
Lemma 44 (Proposition 3 in the main paper). Let G, H be two non-isomorphic graphs and PRW(G), PRW (H) the generated RWSE encodings for both graphs with a random walk length
k k. Then for the generated RRWP encodings P&R (G), PRR, (RR(H)) it follows:
PR = In addition, least one pair of graphs exists that is distinguishable by RRWP but not by RWSE.
= (G) P (H).
Proof. Given random walk matrices RG = DE Ao, RH == Dij Ah, its power matrices up to the power of k and the corresponding RRWP embeddings PER (G), PRR (H) for two non-isomorphic graphs we can directly deduce that for each tensor in the RRWP embeddings, corresponding to the RRWP embedding for a single node in each graph, the diagonal elements of the random walk matrix are the same for each power up to k. Therefore, it directly follows that (R) = (PR((F)
results in PRW (G) = pRW (H), with PRW (G), PRW (H) denoting the RWSE encodings obtained from the same random walk matrices. We provide simple example of a pair of graphs that are not distinguishable by the RWSE embedding, whereas RRWP can distinguish between them. This example follows directly from Proposition 40 since it is proven there that RWSE cannot distinguish this pair of graphs. However, it directly follows from the definition of the random walk matrix. It assumes that the MI.P encoder preserves identity and that the two graphs can be distinguished by their differences in skip lengths, as defined by CSL graphs.
D
37

---

We now want to consider the expressive power of LPE with respect to RWSE. For this, we use results obtained by by|Bacck al. (2024] and Zhang et al. [024 and combine them with similar results obtained for SignNet and BasisNet [im et al. 2023 Our additional observations are highlighted in Proposition 4
We provide an expanded version of Proposition 4 split into three parts Lemma 46 and Proposition 47). considering the expressive power of SAN [Kreuzer et al. 2021] and RWSE first, expanding the proof to LPE and SPE in Lemma 46 and finally upper bounding RRWP by using SPE. With these three parts, we are then able to derive the proposition.
Proof of Proposition
(Lemma
45
Lemma 45 (RWSE and SAN). Let the number k of eigenvalues X E R" and eigenvectors V E R used in the SAN encoding be equal to the number of nodes in non-isomorphic graphs G, H. Then given the encodings PSA (G); P PSAN(H) with it follows:
PEAN(G) Pk SAA = PRW(G) PR (R)(H).
for pair of RWSE encodings PRw (G), PRW (H) and an arbitrary number of random walk steps. ( Lemma 46. (RWSE and LPE) Given Lemma 45 and the LPE embeddings ( ( for two non-isomorphic graphs G, H with ic nodes it follows:
P = PL. (H) = PRW (G) PRW (H),
for pair of RWSE embeddings pRW (H) and arbitrary number of random walk steps. The same result follows by replacing LPE with SignNet, BasisNet, or SPE as the eigenvector based embedding.
In the following, we provide the proofs for both lemmas. Since Lemma 44 proposes extension of the previous lemma, first show the specialized case for the SAN embedding and expand it to the more general case of eigenvector-base encodings. With proofs provided for both lemmas, we can directly derive Proposition by combining them with Proposition 47
Proof of Lemma 45 and Lemma 46
Proof. The proof follows the comparison between SignNet and RWSE presented by Lim et [2023] Since the RWSE embedding is determined by the random walk matrix and its powers, we first determine a corresponding relation between the random walk matrix (D-1 -1A) and eigenvalues and cigenvectors of the normalized graph Laplacian. Due to the definition of the random walk matrix, the eigenvectors of said matrix are determined by v. = D D-1/22,, where v; denotes the corresponding eigenvector of the normalized graph Laplacian. This results in the following equation relating the random walk matrix diagonal to the eigenvectors of the graph Laplacian [Lim et al. 2023
(diag D DODDD-AAA D-'A))* diag
Σ X1) 2))
(16)
Following Lim et al. 2.23). the linear layer can approximate Σ and the transformer encoder to approximate (1 X, * as both are permutation equivariant functions from vectors to vectors. Since eigenvalues and eigenvectors are directly given to the SAN embedding and the linear and transformer encoder layer being able to approximate (1 X₂) k for each X; the approximation directly follows. This approximation assumes using all l eigenvalues and the complete eigenvectors obtained from the decomposition.
However, for each embedding, we must consider whether eigenvalues and eigenvectors can be recovered and (1 A₂)* can be approximated. We split the following proof for each encoding and assume we use all eigenvalues and cigenvectors.
For Lemma 46 we consider Equation 16
For LPE, we can directly recover eigenvalues and eigenvectors from the input to each embedding by using the eigenvectors V; passed to LPE. Using a sufficiently expressive & and LPE is able to approximate (1 )₂ This follows directly from the assumption that ò and p permutation- equivariant MLPs or more expressive neural network architectures, thereby able to approximate the given functions, as in the SAN case [Lim al. 2023
For SPF, a slightly different case has to considered. Since SPE uses the projection matrices obtained from VVT, the eigenvectors must be recovered.
38

---

Instead of directly recovering eigenvectors, we use the properties of the underlying projection matrices. From this, we can directly recover the eigenvectors needed from Vdiag((, 6, which can be reverted by p to retain the eigenvectors. For the eigenvalues, we consider o; to be saanvaalu--rreeevviie functions, allowing us to recover the eigenvalues from the diagonalized representation. The remaining proof follows from the observations made by |im et al. [2023] for SignNet and BasisNet. In addition, SignNet and BasisNet Lim et al. [2023) prove that both embeddings can approximate the RWSE embedding given suitable & and p.
for suitable
Proposition 47 (RRWP and SPE), Given the SPE embeddings (G)E()), PL for two non- isomorphic graphs G, H with nodes follows:
PE (G) = P (H) + PRR(GG) = PRR
=G))=PR(HH))
for pair of RRWP embeddings PR PRR(G), (RR(H) and an arbitrary number of random walk steps.
With the partial hierarchy for LPE and SPE, we want examine random walk-based PEs further. Since RWSE is upper bounded by LPE and incomparable to the 1-WL, it remains to propose an upper bound of RRWP, known to be more expressive than RWSE from Proposition 3
Following Zhang et al. 2024] with their proof of a representation of the page rank distance using projection matrices, we show that RRWP can be represented using the page rank distance and that such distance can be approximated using information recovered from the SPE embedding. We note that proof of SPE being more expressive than GRIT is provided by Zhang et al. (2024). Nonetheless, we reduce the proof to involve the RRWP embedding to align with our theory framework.
Proof of Proposition 47
First, we consider the representation of the RRWP embedding using the generalized PageRank distance. For this, we consider RRWP distance-based embedding of the form
PRR (u,,) D (u, v), (D DDDDAA)( (u, v), (D* v)),
for nodes u, V E (G). Thereby, the RRWP embedding for selection of nodes can be represented by the multi-dimensional page rank distance PR for given weight sequence y/:
PR(u, Σ MD (D-1A)((,,))
t=0
From Zhang et al. [024 obtain the following equality satisfying the needed relation between page rank distance and projection matrices.
Σ (D- = Σ Σ 74(1 - A1)* )aa)))P((a Pi(u, =)((cg(()--1)))c((())))
with (u v) denoting the element at position (u, v) of the i-th projection matrix. However, we still need to recover node-degree information from the SPE encoding and demonstrate that SPE retains the projection matrix information.
Given the property of projection matrices to recover the underlying matrix using eigenvalue decom- position /Zhang et al., 2024]. we recover node degree information using the diagonal of the graph Laplacian. Since SPE uses the graph Laplacian to compute eigenvalues and eigenvectors, we can directly recover relevant degree information via the following equation.
A.P.
1=1
72
diag(L) diag(
X.P.)
A,dia P.))
L
X (P,,uu
Following the definition of the SPE encoding, eigenvalues and the elements of the projection matrix can be recovered using suitably expressive & and p. Given á to be 2-IGN and p to be MLP or
39

---

1-WL expressive GNN, deg(u) 1/2 can be approximated by P. whereas Σ,
Ek=o Y ),)*
can be approximated by 2-IGN as shown by Maron et al. 2019a Lim et a. [023] This allows
for approximating the RRWP embedding via the PageRank distance using SPE an upper bound, concluding our proof.
Combining the results of Lemma 45
Proposition 47 and Proposition 3 we obtain Proposition
directly, supplementing the hierarchy of PEs in their theoretical expressiveness. These results provide comprehensive theoretical expressiveness hierarchy, showing that random walk-based embeddings are more expressive than the 1-WL test but are bounded by eigeninformation-basse embeddings. We note that all embeddings are bounded by the 3L test as shown by Zhang et al. 2024
Additional results on theoretical expressiveness Using notation established in section Ap- pendix B.3 we provide additional proofs complement the framework established by (Black et al.] (2024) and Zhang et al. [2024] concerning theoretical expressiveness of PEs. At first, we consider highlighting the connection between SAN and SignNet. Then we consider SignNet and BasisNet, expanding on the results of Lim et al. 2023 and adapting them to LPE. We provide additional results to improve the hierarchy of theoretical expressiveness in PEs and to examine LPE further, relating to other cigenvector-base
the proof Lemma
embeddings.
Throughout these proofs, we consider the respective & and p to selected as MLPs or GNNs. For s. we choose, based on previous analysis by ZZhng et al. [2024). function mapping at most as expressive as 2-IGN. Similarly, for P. we select any 1-WL expressive GNN or MLP. Note that these assumptions differ from the selections made in our empirical evaluation.
Lemma 48, Given a sufficiently expressive e and for SignNet, aligning with the implementation of Lim el [2023] and the original implementation of the SAN embedding, SignNet is least as expressive as the SAN embedding.
Proof. Let SAN and SignNet be represented by the respective color refinement algorithms shown in Definition 14 To show Lemma 48 we need to show that
Top
WL. Tsp2 (xigi) Tap TENc (X(AN)))
Since assume standard transformer encoder to be most 1-WL expressive and knowing that Tor is order preserving concerning Definition we can reduce the above equation to the following expression:
TwL TsP2 o Ty (x = TwL o Tz (XSAN).
This expression can now be evaluated. Given two non-isomorphic graphs G, H and arbitrary nodes u, V(G) and x, e (HH) the following holds true:
Twn Tsp2 To (XSinnn b)) Twi TsP2 (ign v))
Tsp2 o (XSinn(,, v)) = Tsp T (ign(i: v)) (To(xSign(4) u, e)}} (xggnn,,, y)) (Ta V V*) = (AT V V.)
From the equivalence of the multisets, it follows directly that XsaN(u, v) XSAN(I, v) holds for any choice of nodes given an injective Tg.
With the proof of the SAN embedding concluded, we further evaluate the connections between BasisNet and SignNet and the LPE embedding. First, we show that BasisNet can approximate SignNet, an observation highlighting the differences in expressiveness noted by Lim et al. [2023] In the second part of the proof, we conclude our comparison of eigenvector-basee embeddings and LPE with BasisNet. Throughout the proof we again assume OsN, ÓLPE to at most 2-IGN expressive and PSN, PLPE to be 1-WL expressive.
Proof. Let SignNet and BasisNet be represented by the color refinement algorithms from Defini- tion 14 Then for two non-isomorphic graphs G, H with nodes u, v E (G) and x, E VHH) we consider the color refinement algorithms for both encodings. With this it follows that we have to
40

---

show Top TwL o Typi o TEP TSIAM (XBasis) ) = Top o TWL o Tsp2 TignSig Since Top TWL is order preserving we only consider the relation TSPi TBP (X I Tsp2 To (xSign). First
of all, we show that TSIAM (CBsis) 3 Ta (xiig)::
TRIAM(Raass) u, v) - TSIAM (A [XiGN(XBosis (AH (a,
[TioN (XBasis (AG, (a =
directly approximate the cigenvalues used in SignNet's initial encoding. Furthermore, a 2-IGN architecture at least as expressive as the architectures used for in SignNet. Since the multisets of the projection matrices allow us to approximate the eigenvectors used by the SignNet encoding, the initial encoding of SignNet can be approximated, allowing for the approximation of (i(gg)))).
Using the definition of IGN color refinement,
(TiaN(XRasis (Aa, (u, v) (X (A ;))) (v,y)) + SignnAA u, v) = XSinn(AH, = To (xSign) v) T (xiin)) (AH, v)
Given that X = (XBass) we now only have to show that TBP( I (X) Using the same nodes as above:
TRp(X) u) = Tnr(x)(A + "xa(A, u. Xn(A,2, A v) = (xo(A, a,, BA
() (A,(A, v.a) [(H))A ve [(G) = (A, e V(H))A (io(A, u.)) w, E ( (A, 8, u,) v, (H))A (Ts2(()(A,,, sxr
Since both parts of the relation Tnp TsiAM < Tsp (xSigg) hold and all color refinements are considered to be order-preserving and expressiveness preserving, the proof directly follows.
In case of the LPE embedding, the proof follows the same structure with T3 being replaced with TL as given in Definition 14 Since do not assume To to be more expressive than T and both being bounded by 2- IGN in expressiveness, we can replace To: and therefore, we omit the proof.
E Additional technical proofs
Multiset operations Let D be a finite set with an arbitrary but fixed order. We denote the i-th
element of the order on D by D,. Let be a finite multiset over D. We write == {(a, D:) | i [IDI]] with a; 2 0, the multiplicity of element D; in A.
We define |A| = E, a, Further, let B {(b, D2) [[II]} be another finite multiset over D.
We define
An B = (m, b,), D.) i [|a]]]
and
B\B ((ax b, D,) i [[D]]]
We note that A B is symmetric while B \ A is not symmetric. Nonetheless, prove that if [A] = [B,, then [A \ B| is symmetric.
Claim 49. Let A, be two multisets over a finite domain. If |||| = [B]. then [A B = |B A/.
Proof. We have that
IA BI
Σ maxfa, b;, Σ a, min b.) |A| JAn
Hence, if || = BB, then
n B and since |A n B] is symmetric, |A B = AM--AnDA - -IAn
[A \ B B n A
B Al.
41

---

Claim 50 (Proof of Claim 30
Let A, C Q be finite multisets with |A| -B]. Then, the sum
Σ RЕΛ
exp(a)
Σ DE
exp(b) = 0,
if, and only if, A = B.
EoeB exp(b). Note that for each element a in A that also exp(b) 0. Hence, define A = A B and B B A and have that f(A, B) = f(A", B Further, since according to the lemma statement |A| = |B], we
Proof. Let f(A,
EaEs exp(a)
appears as b in B, we have that exp(a)
have that | [B3|; Claim 49
We first show that f(A, B) = 0 if and only A B. this end, note that the sum is the positive and the negative summands cancel out, that is, if A" B = and hence, A B. If A + B, then the above sum a non zero sum of exponentials with algebraic exponents, and thus, by Theorem 32 non-zero. Hence, have A B + f(A, B) 0.
O
Lemma 51 (Proof of Lemma 28
Let v, Q1xL and let X {0. 1 be a matrix whose rows are one-hot vectors, for some L, d E Nt, Then, softmax(v). x softmax(w) every set( X),
( X, if and only if. for
(a: 3.) = 0, (E)(x)
Σ
where a; == softmax(u), and 3, == softmax(w):
Proof.
We have
softmax(v) X - softmax(w) X
(a: 3:) X; = E Σ
(a::
- Bi) xc
#Eset(X X) iE)(())
Since the rows X are one-hot vectors, set(X) is linearly independent we have that
Σ
Σ (a: - 5,) x 0,
(xset(X) (E((()
if, and only if, EieA(a) (a: - Bi) 0, for all æ E set(X).
Lemma 52 (Proof of Lemma 27 Let
Qixb and let X E {0, 1] be matrix whose rows are one-hot vectors, for some L,, E N+. Then, [w]x = [w]x. if and only for every x E set( X),,
(0; i [n] A X; = =3 {wu I [m] X; =x
Proof. We define, for each a E set(X).
V(x) = [u E [m] A X; = W(w): w: i [n] X, =
For the forward implication, assume towards contradiction that [w]x [w]x but there exists an x E set(X) such that (xx * (x). However, then there also exists number e E V(x) that appears times in V (x) but y times in W (z)), with * y. Without loss of generality, we assume that æ < y. Then, the tuple (v, æ) appears fewer times in [v]x than in [w] w]xx, implying [v]x * [w]x. contradiction.
For the backward implication, assume towards a contradiction that for all æ set X), V(x): W(x) but [w] * [w] Then, there exists tuple (v, x) that appears times in [u]x x but times in [w] x. with x + y. Without loss generality, we assume that x < y. But then, the vector æ, there exists number that appears fewer times in V(X) than in W W(X), implying V(X) * W(X), contradiction. This shows the statement.
42

---

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: The main claims of the paper are that we propose new model, develop an understanding of its representation power, and evaluate extensively on large-scale datasets to derive generalizable insights. We describe the model in detail in Section 2 provide central expressivity results Section 2.3 and Section and evaluate the model extensively in
Section 4
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 the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it 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:
We discuss the limitations in the main paper in Section 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are 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-spectne specs-eefiii,,nnn asymptotic approximations only holding locally). The authors should reflect on 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, authors should discuss possible limitations of their approach to 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 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 proof's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
43

---

Answer: [Yes]
Justification: We provide detailed proofs, including all assumptions in Appendix and Appendix D as well as extensive background with all necessary definitions in Appendix
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 or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to 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 the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide detailed information in the main paper in Section 4 which should suffice reproduce the results on our real-world tasks. For the algorithmic tasks, which we design and implement for this work, additional details graph generation and detailed task descriptions are required, which we detail fully in Appendix A
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 make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it 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 to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (c.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
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) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
44

---

5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide our code base in the supplementary material which sufficient to download or generate the data required to reproduce the experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
guuides/CodeSubmisstte
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
sosooooocossiooooooooooooooo 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 as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is 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: training and test details are provided in Appendix A in particular in Ap- pendix A.2 discussing hyperparameters detail.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a 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, 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: We report standard deviation over multiple random seeds in Table I well standard eтror over multiple random seeds in Figure 3 For better clarity, we provide the standard deviation over random seeds of our scaling experiments Figure (a) in Appendix A in tabular form.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
45

---

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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 errors 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 out of 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: We provide runtime and memory requirements in Appendix A.5 in tabular form. These requirements are computed from empirical measurements on single L40 GPU.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as 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 the paper conform, in every respect, with the NeurlPS Code of Ethics /tttps://neurips... httpaarrp....pppp.ai//ecccccaaad
Answer: [Yes]
Justification: Our research conforms to the code of ethics.
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 circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in 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: In this work, conduct foundational research in the of machine learn- ing without any immediate positive or negative societal impact that must be addressed specifically.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
46

---

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 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to 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 to 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 intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal 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 system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our models are trained on standard benchmarks or on synthetic algorithmic tasks without any immediate risks for misuse.
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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or 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?
Answer: [Yes]
Justification: We provide licenses for each dataset in Appendix A
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.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, wwwpppppppphhooooopppppooooooppo thcode. com com/datasets
47

---

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 it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: While we do introduce new synthetic tasks, we do not release these as datasets benchmark. However, thoroughly document how to reproduce the data used in these tasks, as well as how the models are evaluated on these tasks.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an 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 sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in 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 in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
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 the NeurIPS Code of Ethics and the guidelines for their institution.
48

---

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
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, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: We do not use LLMs such that they impact the core method development in this research.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy http:p///eeeriissc.c/ofeeeeeeeee for what should should not be described.
49


Reviews:
[{"review_id": "O3KUTx8vrd", "reviewer": "Reviewer_Agzt", "summary": "The paper introduces the Generalized-Distance Transformer (GDT), a graph transformer architecture that aims to bridge the gap between theoretical expressivity and practical performance in graph learning. Sepcifically, the authors provide comprehensive comparison among position encodings and experimental validation.", "questions": "See Weaknesses.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. The paper provides strong thoeretical proof to compare each of variants of GT.\n\n2. The experiments span 8 million graphs across diverse tasks and domains, including out-of-distribution reasoning. The GDT’s ability to learn transferable representations (e.g., few-shot COCO-to-PASCAL transfer) highlights its practical utility.\n\n3. The work provides practical guidelines for GT design, such as the importance of PEs and attention mechanisms, which are broadly applicable beyond the proposed architecture.\n\nWeaknesses:\n\n1. While the authors provide detailed proof. These information mostly are not surprising, and the authors basically confirm these intuitive idea. For example, insight 1 & 2 are sort of intuitive, as it seems that the authors are simply claiming biased attention and positional encodings are useful. Also, insight 3 has been widely observed in previous work, as these models' performances do not vary too much. I believe the interesting part is in insight 4 & 5.\n\n2. The rankings experimantal results do not align with the theoretical results, which means the Table 1 does not match the expressive power of positional embeddings.\n\n3. There are also some other works[1] analyzes the expressive power of graph transformer. It seems that there's overlap between [1] and Section3 in this paper. Could the authors further discuss the difference from the previous work? \n\n4. Few-shot experiments seem not sufficient. As the authors test this work on 6 benchmarks, the authors only investigate two few shot cases (Bridges -> Cycle detection & COCO -> Pascal). Could the authors conduct more experiments to provide a more convincing results?\n\n[1]What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding", "was_revised": true, "final_justification": "After I further elaborate my concerns, the authors provide a sufficiently persuasive feedback. I do not have any major concern to this work and have lifted my score.", "rebuttal": "We thank the reviewer for their effort in reviewing our work. We are happy to hear that the reviewer finds insights 4 and 5 in our paper interesting. In the following, we address their concerns about insights 1-3.\nFirst, the reviewer says\n> While the authors provide detailed proof. These information mostly are not surprising, and the authors basically confirm these intuitive idea. For example, insight 1 & 2 are sort of intuitive, as it seems that the authors are simply claiming biased attention and positional encodings are useful.\n\nFrom a theoretical perspective, we consider proving these results to be important, although they may be regarded as intuitive. As our paper aims to provide rigorous theoretical proof for results obtained, we highlight insights 1 and 2 as theoretical contributions to the understanding of graph transformers. As we highlight in the paper, weighted means, as computed by standard attention, do not fit into the sum-aggregation-based proofs of expressivity common in graph learning. As such, we leverage a specific property of softmax to circumvent issues usually encountered with weighted means in terms of injectively mapping multisets.\nSince many previous works use a modified attention layer, their results cannot be directly applied to our proposed architecture. We provide a rigorous proof to allow a theoretical and empirical comparison of graph transformers using standard attention. \n\n> Also, insight 3 has been widely observed in previous work, as these models' performances do not vary too much.\n\nPrevious works ([1], [2], [3]) often compare their proposed PEs favorably to other works in both theory and empirical evaluation. However, we show that these differences are not as pronounced as suggested by previous works when evaluated at scale. Further, we find that the efficiency of the PE is vital to its usage on real-world data at scale, observations not made in previous works such as [1] and [2]. \n\n\n\nNext, the reviewer says \n> The rankings experimantal results do not align with the theoretical results, which means the Table 1 does not match the expressive power of positional embeddings.\n\nMany previous PE designs are motivated by their enhanced theoretical expressiveness. In our study, we find that theoretical expressiveness does not necessarily correlate with (predictive) performance at scale. Note expressiveness does not necessarily imply a small generalization gap, but purely measures a model’s approximation capacity.\nSimilar results can be observed in the works of Huang et al. [1] and Black et al. [4], showcasing experimental results that do not align with previously obtained theoretical expressiveness. However, in our work, we additionally study the computational cost of each PE in practice, which reveals a far more critical axis to successfully scaling GTs.\n\n\n> There are also some other works[5] analyzes the expressive power of graph transformer. It seems that there's overlap between [5] and Section3 in this paper. Could the authors further discuss the difference from the previous work? \n\nWe believe the paper noted by the reviewer to be fundamentally different in its scope than our proposed paper. In [5], the major theoretical results concern the generalization properties of graph transformers, while we investigate theoretical expressivity concerning our proposed architecture and combinations with PEs. We would kindly ask the reviewer to point us to where they believe overlap exists with our work. Nonetheless, we find the suggested work to be relevant to our work and will add it to our related work.\n\n\n> Few-shot experiments seem not sufficient. As the authors test this work on 6 benchmarks, the authors only investigate two few shot cases (Bridges -> Cycle detection & COCO -> Pascal). Could the authors conduct more experiments to provide a more convincing results?\n\nWe note that finding additional few-shot tasks is not trivial, for several reasons:\n\n1. The node and edge feature spaces of upstream and downstream task need to be aligned. This prohibits, for example, transferring from molecular tasks in OGB to other molecular tasks (e.g., QM9). The authors in [6] have recently highlighted this issue for graph foundation models in general.\n2. Upstream and downstream tasks need to be related. The few-shot transfer we present in the paper leverages the fact that upstream and downstream tasks are semantically related. To obtain additional few-shot tasks requires to find a pair of tasks (A, B) where A is a large-scale pre-training dataset and B has the same feature domain as A, as well as is semantically related. For example, many OGB tasks share the same feature domain as PCQM4Mv2 (2D molecules), but lack plausible biological or chemical relationships. This is also due to the narrow prediction space of PCQM4Mv2, as it merely predicts the HOMO LUMO Gap.\n\nWe regard it as a fundamental challenge for future to develop benchmarks which contain aligned feature spaces, semantically related tasks, and large pre-training datasets to allow for rigorous benchmarking of few-shot transfer capabilities such as those we demonstrate with the GDT. Our code base allows for an easy and comprehensive extension to new training and few-shot objectives. This enables us to include additional few-shot tasks derived from pretraining data in the future as they become available.\n\n**If you are content with our provided answers, consider updating your score. Please also let us know if there are any remaining questions/concerns on your side.**\n\n### References\n[1] On the Stability of expressive Positional Encodings for Graphs, Huang et al, ICLR 2024\n\n[2] Graph Inductive Biases in Transformers without Message Passing, Ma et al, ICML 2023\n\n[3] Sign and Basis Invariant Networks for Spectral Graph Representation Learning, Lim et al, ICLR 2023\n\n[4] Comparing Graph Transformers via Positional Encodings, Black et al, ICML 2024\n\n[5] What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding, Li et al, ICML 2024\n\n[6] Position: Graph Foundation Models are Already Here, Mao et al., ICML 2024"}, {"review_id": "djunnHaywY", "reviewer": "Reviewer_RXcq", "summary": "This paper introduces Generalized-Distance Transformer (GDT), a new graph transformer (GT) architecture designed to bridge the gap between theoretical expressiveness and practical performance across diverse domains. The authors aim to provide generalizable insights for the design and application of GTs by leveraging standard attention mechanisms alongside advanced positional embeddings (PEs). Experiments over various datasets and tasks show the effectiveness of the proposed GT.", "questions": "- Why do you not consider other GT variants?\n\n- How would GDT extend to dynamic graphs (e.g., temporal social networks) or heterogeneous graphs (e.g., knowledge graphs with multiple node/edge types)?", "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:\n\n- I am not an expert in this field. But it seems that the GDT is shown to be provably expressive. The work advances GT theory by linking standard attention-based architectures to the GD-WL algorithm.\n\n- Experiments span graph-, node-, and edge-level tasks, in- and out-of-distribution settings, and model scales (15M to 160M parameters). Datasets include both real-world benchmarks and synthetic algorithmic tasks. The results show the generalizability and effectiveness of the proposed GT.\n\nWeaknesses:\n\n- The scope of the theoretical contributions and practical applications in this paper needs to be clearly defined. In Section 2.2, the authors state: “While many variations of GTs exist, we consider the standard transformer encoder based on Vaswani et al. [2017].” However, they do not explain why other variants are excluded. Additionally, the paper focuses primarily on four types of positional embeddings (PEs). Are there other PEs available? If so, why were those not considered? This point was not sufficiently clarified.\n\n- Some experimental findings may be difficult to interpret for readers who are not specialists in the field. For example, in Section 4.3, the performance of LPE slightly declines on the MST task with the 160M-parameter model (compared to the 90M model). The paper merely states that it “still outperforms both 15M models” but does not further analyze the cause of this fluctuation. It is recommended to include additional experiments or analyses to improve the robustness of the conclusion.", "was_revised": true, "final_justification": "I keep my positive score.", "rebuttal": "We thank the reviewer for their effort and are happy to address their concerns in the following. The reviewer says \n> The scope of the theoretical contributions and practical applications in this paper needs to be clearly defined. In Section 2.2, the authors state: “While many variations of GTs exist, we consider the standard transformer encoder based on Vaswani et al. [2017].” However, they do not explain why other variants are excluded.\n\nAn essential consideration in our paper for both theoretical and empirical results is that we use a standard attention and do not provide any alterations to the attention layer, as is typical in other works on graph transformers. As a result, we do not have to redesign the transformer specifically for graph tasks. This allows us, for example, to use highly optimized standard transformer implementations in practice. However, we agree with the reviewer that further clarification on this may be beneficial and will add additional explanation to the paper.\n\n> Additionally, the paper focuses primarily on four types of positional embeddings (PEs). Are there other PEs available? If so, why were those not considered? This point was not sufficiently clarified.\n\nWhile a plethora of different PEs are available, our study focuses on the most common and popular types of PEs for GTs: those based on eigeninformation of the graph Laplacian and those based on random-walk probabilities. For those two types, we selected RWSE and RRWP as two common choices of random-walk PEs ([1], [2], [3]). For the eigen PEs, LaplacianPEs ([4], [2]) and SPE [5] are a popular choice. In our study, we use LPE, a slight variant of LaplacianPEs, which is expressive and empirically powerful for standard transformers [6].  \n\nFinally, the reviewer says\n\n> Some experimental findings may be difficult to interpret for readers who are not specialists in the field. For example, in Section 4.3, the performance of LPE slightly declines on the MST task with the 160M-parameter model (compared to the 90M model). The paper merely states that it “still outperforms both 15M models” but does not further analyze the cause of this fluctuation. It is recommended to include additional experiments or analyses to improve the robustness of the conclusion.\n\nWe observe the performance of LPE and RWSE on the MST tasks to be rather saturated. As both models provide better test scores than the underlying 15M models, we propose beneficial results due to scaling of the model. Further, we note that the size generalization performance of the 160M model with LPE is increased over the 90M model, while showing similar performance at the graph size seen during training. \n\nWe are happy to answer the questions of the reviewer below.\n\nFirst, the reviewer asks,\n> Why do you not consider other GT variants?\n\nWe do not consider other GT variants in our work, as the scope of our paper is to provide theoretical and empirical results for our GT without modifications to attention. With previous works relying on these modifications, we aim to highlight the generality of standard transformers and leverage their existing optimized implementations while still being theoretically and empirically powerful on graph data. We will add this distinction more clearly to our work. \n\nNext, the reviewer asks,\n\n> How would GDT extend to dynamic graphs (e.g., temporal social networks) or heterogeneous graphs (e.g., knowledge graphs with multiple node/edge types)?\n\nWe do not consider the temporal setting in our evaluation of the GDT, but find it interesting for future work. Heterogeneous graphs could be naturally extended to and captured by the GDT: Different node types can be encoded differently into node embeddings, and edge types can be distinguished by either edge-level tokenization or edge-based biased attention. \n\n**Please let us know if there are any remaining questions/concerns on your side.**\n\n### References\n[1] Graph Inductive Biases in Transformers without Message Passing, Ma et al., ICML 2023\n\n[2] Recipe for a General, Powerful, Scalable Graph Transformer, Rampášek et al., NeurIPS 2022\n\n[3] Do Transformers Really Perform Bad for Graph Representation?, Ying et al., NeurIPS 2021\n\n[4] Rethinking Graph Transformers with Spectral Attention, Kreuzer et al., NeurIPS 2021\n\n[5] On the Stability of expressive Positional Encodings for Graphs, Huang et al, ICLR 2024\n\n[6] Aligning Transformers with Weisfeiler-Leman, Müller and Morris, ICML 2024"}, {"review_id": "a90RgHcOc5", "reviewer": "Reviewer_5CNk", "summary": "This paper starts with introducing GDT, a generalization of recent graph transformer architectures. It then proves that GDTs can be designed and parameterized to simulate the GD-WL algorithm in general. Importantly, in this proof, the paper works with full softmax attention. Using this framework, it evaluates the relative expressiveness of position embeddings used in recent graph transformers. Finally, empirical results are provided to evaluate the applicability of the developed theory.", "questions": "- And I correct in assuming that GDT always assumes the existence of edge features. And if they are not present in the dataset then these are assigned to 1/0 based on the adjacency?", "limitations": "Yes, limitations have been properly addressed in the paper.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "### Strengths\n\n- Being able to rigorously show that a graph transforner with softmax attention is able to emulate GD-WL is a big contribution.\n    \n- Since the goal of this work is to takl about expressibility of different position embeddings, and not necessarily their “optimizability”, the choice of restricting experimental evaluation to only large graphs was a good idea.\n    \n\n### Weaknesses\n\n- One real-world dataset per task-type (graph/node/edge classificaiton), seems a little low.\n    \n- While the theory predicts SPE is atleast as expressive as LPE, the results in Table 1 show that the performance of SPE is much worse than LPE. How would you explain that?\n    \n- Since all 3 real-world datasets considered have a similar number of tokens, what causes RRWP to be OOT on COCO and Code? Also, what would be the estimated training time for RRWP on COCO and Code? If getting results for RRWP on these datasets is feasible, I would suggest including the results and noting down the extra compute time needed for it in the paper.  \n    Excluding a method based on the inefficiency of current implementation seems a bit wrong. After all, transformers is also slow in theory, but once researchers designed fast attention kernels, using attention became feasible, even for large datasets.", "was_revised": true, "final_justification": "The authors have resolved my concerns regarding missing RRWP performance numbers.", "rebuttal": "We thank the reviewer for their effort and are happy to address their concerns in the following. First, the reviewer says \n> One real-world dataset per task-type (graph/node/edge classificaiton), seems a little low.\n\nNote that while we use fewer real-world datasets than is common in most graph learning papers, we consider exclusively datasets with large scale. We motivate this in our paper by increasing the generalizability of the insights and allowing training at scale. While we only pre-train on three real-world datasets, we provide additional empirical results typically not found in graph transformer papers, such as size generalization and few-shot transfer experiments.\n\n> While the theory predicts SPE is atleast as expressive as LPE, the results in Table 1 show that the performance of SPE is much worse than LPE. How would you explain that?\n\nAs observed in previous works [1],[2], theoretical expressiveness does not necessarily imply an increased performance on real-world or synthetic datasets. With SPE designed to be both stable and theoretically expressive, this design may lead to reduced performance on real-world tasks. Furthermore, most PEs are designed concerning their theoretical expressiveness or specific architectures. Therefore, empirical performance of PEs may not align with the results shown in theory. In general, theoretical expressiveness does not necessarily improve empirical performance in PEs [3][4]. As such, studying the interplay between expressiveness and generalization in GTs is a promising research direction. Our streamlined GT architecture provides an ideal basis for this.\n\nFinally, the reviewer notes\n> Since all 3 real-world datasets considered have a similar number of tokens, what causes RRWP to be OOT on COCO and Code? Also, what would be the estimated training time for RRWP on COCO and Code? If getting results for RRWP on these datasets is feasible, I would suggest including the results and noting down the extra compute time needed for it in the paper.\n\nWe agree with the reviewer to include RRWP where possible for an extended empirical evaluation. To address this issue, we optimized our code to compute RRWP at runtime for both datasets, allowing us to include the results for Coco and Code. These results can be seen in Table 1, highlighting the performance of RRWP on Code. With an F1 score of 19.42 RRWP performs slightly better than RWSE, SPE, and the NoPE baseline model.  However, we note RRWP to be unstable in training on Coco, with collapses in validation performance observed for multiple learning rates and seeds. Further, RRWP performs worse than other PEs on Coco, \nFurthermore, adding to insight 3 of the paper, we provide the runtime and memory requirements of RRWP computed for both experiments in Table 2. As observed with other datasets, computing RRWP at runtime adds runtime and memory overhead, leading to increased runtime for both tasks compared to other PEs. Especially with Code, we observe double the runtime and memory requirements compared to other PEs. However, the memory requirements for Coco remain similar to those of other PEs. Nonetheless, RRWP requires additional runtime for both tasks. \n\nTest performance:\n| | CoCo (F1) | Code (F1)  |\n| -- | -- | -- |\nRRWP-32|  39.91 $\\pm$ 1.07 |  19.42$\\pm$ 0.1|\n\n\nComputational requirements:\t \n\nThe computational requirements were computed by running the respective GDT with RRWP for 1000 steps. The GPU memory requirement is computed as the maximum GPU memory allocated during these steps. Runtime was measured as the average runtime for a single step, averaged across 1000 steps.\n| | CoCo | Code  |\n| -- | -- | -- |\nGPU mem. [MB] | 5223.77  |  19221.97 |\nRuntime [s]  | 0.1352 |  0.219\n\nWe are happy to answer the reviewer's question:\n\n> And I correct in assuming that GDT always assumes the existence of edge features. And if they are not present in the dataset then these are assigned to 1/0 based on the adjacency?\n\nCorrect. This is equivalent to learning an initial edge embedding, which is the same across all edges (but helps the model to distinguish neighbors from non-neighbors in the attention).\n\n**Please let us know if there are any remaining questions/concerns on your side.**\n\n### References\n[1] On the Stability of expressive Positional Encodings for Graphs, Huang et al, ICLR 2024\n\n[2] Comparing Graph Transformers via Positional Encodings, Black et al, ICML 2024\n\n[3] Aligning Transformers with Weisfeiler-Leman, Müller and Morris, ICML 2024\n\n[4] Recipe for a General, Powerful, Scalable Graph Transformer, Rampášek et al., NeurIPS 2022"}, {"review_id": "lDSHM3Eg6M", "reviewer": "Reviewer_7xCc", "summary": "This paper proposes a new graph transformer architecture called the Generalized Distance Transformer (GDTransformer). Unlike some existing graph transformer architectures that use architectural components specialized to graphs, GDTransformer uses the standard transformer architecture. Despite this, the paper proves that GDTransformer matches the expressive power of GDGraphormer. Given that the expressive power of the GDTransformer is determined by the choice of relative positional encoding, the authors prove several theoretical results comparing the expressive power of different positional encodings. The authors then empirically compare the performance of GDTransformer with different positional encoding on a mixture of real-world and algorithmic benchmarks. The authors also perform a set of experiments on the few-shot learning and size generalization capabilities of GDTransformer.", "questions": "## Suggestions\n\n- I feel the term \"distance\" is misused in this paper, as it is applied to functions that are not metrics by the mathematical definition. For example, line 109 uses $d_G$ for the adjacency function, which is not a metric. Thus, it feels like a misnomer to call the proposed architecture GDTransformer, when it can use any relative positional encoding, not just distances.\n\n- The name \"GDTransformer\" is very similar to GDGraphormer introduced in [Zhang et al, 2023]. It might be a good idea to change the name to avoid confusion.\n\n- One of the key selling points of this paper is that GDTransformer is a simplificiation of previous graph transformer architectures while maintaining the same theoretical expressive power. However, there is little dicussion of previous graph transformer architectures, so the novelty of GDTransformer may not be obvious to readers. I would suggest adding some discussion comparing GDTransformer to the existing graph transformer architectures it improves on.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\n\n- This paper prove (Theorem 1) that the standard transformer architecture has the same expressive power as specially designed graph transformers like GDGraphormer; namely, both have the same expressive power as the GD-WL test. In contrast to GDGraphormer that used the relative PE both inside and outside of the softmax, GDTransformer proves that it is sufficient to use the relative PE inside of the softmax. Most standard transformer implementation only use relative positional encodings inside of the softmax. This results means that the one can use standard transformer implementations rather than specialized implementations. This will significantly simplify future implementations of graph transformers.\n- The authors prove (Theorem 2, Propositions 3 & 4) several new results comparing the expressive power of different positional encodings, e.g. SPE >= LPE, RRWP. \n- The authors provide several experiments comparing different choices of positional encodings, including experiments testing few-shot generalization and size generalization. This and the previous result can help practitioners choose among the different options of positional encodings.\n\n# Weaknesses\n\n- There is a disconnect between the theoretical results and the experiments. The theoretical results prove that GDTransformer matches the expressive power of GDGraphormer (Theorem 1) and prove some PEs are more expressive than others (Theorem 2, Propositions 3 & 4). The experiments in Table 1 does compare different positional encodings so validates Theorem 2 and Propositions 3 & 4; however, I am not sure how the experiments in Figure 3 connect to the theoretical results. These experiments test the generalization capabilities of GDTransformer, but I am not sure how this fits into the larger message of the paper. Is there a reason why GDTransformer would generalize better than GDGraphormer or other graph transformer or GNN models? Conversely, there is no experimental validation of Theorem 1.  \nTo the this point, I feel like the biggest weakness of the paper is that there is no comparison between GDTransformer and existing graph transformer models. I feel like such a comparison is necessary to the message of the paper. I see these experiments as serving two purposes.\n    - Theorem 1 shows that GDTransformer has the same expressive power as GDGraphormer while being simpler. Therefore, I feel like there should be an experimental comparison between GDTransformer and GDGraphormer to empirically validate this theorem. Potentially they could be compared on the BREC dataset [Wang and Zhang, 2024], which tests the expressive power of a GNN.\n    - Figure 3 tests the generalization abilities of GDTransformer. However, there is no point of comparison for generalization, so it is unclear how unique GDTransfomers generalization capabilities are.\n- While the authors compare some of the most prominent positional encodings, there are many others that are not included in their comparison, most notably the shortest-path or resistance distances used in GD-Graphormer, which is perhaps the most similar architecture to GDTransformer in the literature.", "was_revised": true, "final_justification": "Thank you for your rebuttal. I think the additional BREC experiments help connect the theoretical and experimental sections. I am also satisfied with the answers to my questions. I still feel that the results of Table 3 don't entirely fit into the paper; however, I acknowledge that this experiment is insightful even if it is somewhat disconnected from the rest of the paper. I believe that the contribution of proving a standard transformer like GDTransformer matches the expressivity of GD-WL will help to simplify the field of graph transformers research, so I am updating my score to \"Accept\".", "rebuttal": "We thank the reviewer for their effort and are happy to discuss their concerns below. \nFirst, the reviewer says \n> There is a disconnect between the theoretical results and the experiments. [...] The experiments in Table 1 does compare different positional encodings so validates Theorem 2 and Propositions 3 & 4; however, I am not sure how the experiments in Figure 3 connect to the theoretical results. These experiments test the generalization capabilities of GDTransformer, but I am not sure how this fits into the larger message of the paper. Is there a reason why GDTransformer would generalize better than GDGraphormer or other graph transformer or GNN models? \n\nWe note that Figure 3 is not intended to show that the GDT is better at generalization than Graphormer-GD or other architectures. Instead, the figure shows capabilities observed with pre-trained GDT models, which might be found in other architectures as well and might be extended to additional tasks. We believe our results provide empirical motivation for the capabilities of GTs in general, with the GDT serving as an example of a GT possessing these capabilities.\n\nNext, the reviewer notes\n> Theorem 1 shows that GDTransformer has the same expressive power as GDGraphormer while being simpler. Therefore, I feel like there should be an experimental comparison between GDTransformer and GDGraphormer to empirically validate this theorem. Potentially they could be compared on the BREC dataset [Wang and Zhang, 2024], which tests the expressive power of a GNN.\n\nWe agree with the reviewer that providing empirical expressiveness results on the BREC dataset provides empirical insights into Theorem 1. Hence, we provide these results for the GDT and Graphormer-GD architectures in the following table:\n\n| Model | PE | Basic | Regular | Extension | CFI | Total |\n|-|-|-|-|-|-|-|\n| Graphormer-GD | RWSE | 57 | 50 | 96 | 0 | 203 |\n| Graphormer-GD | LPE | 55 | 40 | 85 |3 | 183|\n| GDT | RWSE | 57 | 50 | 96| 0 | 203 |\n| GDT | LPE | 54 | 39 | 84 | 3  | 180 |\n\nWe observe that both PEs showcase non-trivial performance on BREC, and that the differences between GDT and Graphormer-GD are negligible. We add a few remarks to these results:\n\nWe choose RWSE and LPE as two representative PEs for random-walk and eigen PE, respectively. We also tried RRWP PEs but observed training instabilities for both models, which we attribute to the very small dataset size of BREC (only 64 samples per task). The small-scale dataset size seems to affect the relative PE RRWP more than the node-level PE RWSE and LPE.\nOur implementation aligns GDT and Graphormer-GD as much as possible, differing essentially only in the style of attention. As such, we expect our comparison to be fair. Moreover, we choose 4 layers, an embedding dimension of 64, 4 attention heads, and 8 random-walk and eigenvalues, respectively.\nWe generally observed training instabilities caused by the multiplicative $\\phi_1$ of Graphormer-GD (see [9], Equation 5). We tried different choices of element-wise functions for $\\phi_1$ but observed Graphormer-GD to be unable to distinguish most graphs in BREC. To achieve the performance above, we manually initialize the weights of $\\phi_1$ and $\\phi_2$ such that Graphormer-GD initially performs standard attention (akin to the GDT).\n\nIn general, we find BREC to be only partially suitable as an empirical evaluation of Theorem 1, as results on BREC may be skewed by hyperparameter choices and the fact that BREC contains only a few training samples. As such, results on BREC do not necessarily indicate a particular theoretical expressiveness advantage. We provide rigorous proof with Theorem 1 of an equivalent expressiveness to Graphormer-GD, while retaining an architecture that does not rely on modifications in attention. \n\n\nIn addition, the reviewer says\n>Figure 3 tests the generalization abilities of GDTransformer. However, there is no point of comparison for generalization, so it is unclear how unique GDTransfomers generalization capabilities are.\n\nWhile we agree that such a comparison would certainly be interesting, the scope of the generalization experiments was not to provide a comprehensive evaluation of graph transformer architectures but rather to demonstrate additional capabilities of pre-trained models obtained from the GDT. We further do not claim these capabilities to be exclusive to the GDT and instead consider them to be promising insights for graph transformers at large. \n\n\n> While the authors compare some of the most prominent positional encodings, there are many others that are not included in their comparison, most notably the shortest-path or resistance distances used in GD-Graphormer, which is perhaps the most similar architecture to GDTransformer in the literature.\n\nWe intentionally limit the choice of PEs to commonly used PEs in literature and to PEs providing the most powerful theoretical expressiveness: those based on eigeninformation of the graph Laplacian and those based on random-walk probabilities. For those two types, we selected RWSE and RRWP as two common choices of random-walk PEs ([2], [3], [5]). For the eigen PEs, LaplacianPEs ([5], [6]) and SPE [7] are a popular choice. In our study, we use LPE, a slight variant of LaplacianPEs, which has been shown to be expressive and empirically powerful for standard transformers [8].  As the shortest path and resistance distance are theoretically less expressive than SPE [1] we decided not to include them in the current comparison. \n However, we agree that the evaluation of additional PEs may pose great future work. \n\n\n> I feel the term \"distance\" is misused in this paper, as it is applied to functions that are not metrics by the mathematical definition. For example, line 109 uses for the adjacency function, which is not a metric. Thus, it feels like a misnomer to call the proposed architecture GDTransformer, when it can use any relative positional encoding, not just distances.\n\nAligning our architecture with the definitions by [Zhang et al., 2023], we consider a distance measure to not necessarily constitute a metric. We agree that functions are used that are not metrics by mathematical definition. However, we consider distance as an abstract measure of space between points of information. Similar to Zhang et al. (2023), we consider the adjacency function, which is referred to as a distance in their work. \n\n\n> The name \"GDTransformer\" is very similar to GDGraphormer introduced in [Zhang et al, 2023]. It might be a good idea to change the name to avoid confusion.\n\nThe Graphormer-GD, as introduced by Zhang et al, 2023, is compared in its expressive power to the GD-WL, the same expressiveness that the GDT achieves. Since we call our model Generalized Distance Transformer (GDT) and provide a more straightforward implementation of Graphormer-GD, we believe the names are not too close and that GDT is a suitable name for our architecture. \n\n\n> One of the key selling points of this paper is that GDTransformer is a simplificiation of previous graph transformer architectures while maintaining the same theoretical expressive power. However, there is little dicussion of previous graph transformer architectures, so the novelty of GDTransformer may not be obvious to readers. I would suggest adding some discussion comparing GDTransformer to the existing graph transformer architectures it improves on.\n\nWe agree that adding a discussion on the differences between the GDT and other graph transformer architectures would improve the readability of our work. \nTherefore, we add a discussion concerning popular graph transformer architectures and their differences to the GDT in the following (and will include this discussion in the paper):\nConsidering the Graphormer-GD, holding the same theoretical expressiveness, the GDT simplifies the architecture involved by removing the need for additional element-wise functions \\phi_1^h and \\phi_2^h in the attention layer, thereby enabling the GDT to benefit from results obtained for standard biased attention. \nIn addition, concerning GRIT [2], the GDT does not require changes to attention, as well as an adaptive degree scaler. Furthermore, GRIT is designed to work with the RRWP PE, which our GDT implementation includes out of the box, allowing for a variety of PEs to be used without adaptation of the architecture design. \nCompared to additional works such as Graphormer [3] and Token-GT [4], we note both improved empirical performance as well as the removal of attention or other architecture modifications in the GDT.  \nGraphGPS [5] assumes the transformer architecture to be combined with a GNN to improve performance. However, this deviates significantly from transformer architectures, whereas the GDT provides a pure transformer implementation. \nOverall, the GDT provides a theoretical and empirically powerful and straightforward implementation of a graph transformer, aligning with transformer architectures found across domains. \n\n**If you are content with our provided answers, consider updating your score. Please also let us know if there are any remaining questions/concerns on your side.**\n\n### References\n[1] Comparing Graph Transformers via Positional Encodings, Black et al, ICML 2024\n\n[2] Graph Inductive Biases in Transformers without Message Passing, Ma et al., ICML 2023\n\n[3] Do Transformers Really Perform Bad for Graph Representation?, Ying et al., NeurIPS 2021\n\n[4] Pure Transformers are Powerful Graph Learners, Kim et al. \n\n[5] Recipe for a General, Powerful, Scalable Graph Transformer, Rampášek et al., NeurIPS 2022\n\n[6] Rethinking Graph Transformers with Spectral Attention, Kreuzer et al., NeurIPS 2021\n\n[7] On the Stability of expressive Positional Encodings for Graphs, Huang et al, ICLR 2024\n\n[8] Aligning Transformers with Weisfeiler-Leman, Müller and Morris, ICML 2024\n\n[9] Rethinking the Expressive Power of GNNs via Graph Biconnectivity, Zhang et al., ICLR 2023"}]

Author rebuttal:

Meta-review: Despite strong performance, Graph Transformer (GT) architectures lack unified theoretical and practical insights due to diverse attention mechanisms, positional embeddings, and expressivity approaches. This paper proposes the Generalized-Distance Transformer (GDT), which integrates recent GT advancements into a standard attention framework, and provide a fine-grained analysis of its representational power. All the reviewers agree that the paper provides strong theoretical insight and should be accepted.
Decision: Accept (spotlight)